2024年2月14日力扣题目训练
2024年2月14日力扣题目训练
2024年2月14日第二十一天编程训练，今天主要是进行一些题训练，包括简单题3道、中等题2道和困难题1道。惰性太强现在才完成，不过之后我会认真完成的,我会慢慢补回来，争取一天发两篇，把之前的都补上。
605. 种花问题
链接: 种花问题
难度： 简单
题目：
运行示例：
思路：
这道题可以采用贪心策略完成。我们需要在不打破种植规则的情况下在花坛内种入 n朵花，那么我们需要在不打破种植规则的情况下种入尽可能多的花，然后判断可以种入的花的最多数量是否大于或等于 n。我们需要判断在已经有花的范围内还能种多少花。
代码：
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int count = 0;
int m = flowerbed.size();
int pre = -1;
for(int i = 0; i < m; i++){
if(flowerbed[i] == 1){
if(pre < 0){
count += i/2;
}else{
count += (i - pre - 2) / 2;
}
if(count >= n) return true;
pre = i;
}
}
if(pre < 0){
count += (m+1)/2;
}else{
count += (m - pre - 1)/2;
}
return count >= n;
}
};
617. 合并二叉树
链接: 合并二叉树
难度： 简单
题目：
运行示例：
思路：
这道题我们可以看就是利用遍历然后对对应位置的值进行相加即可，我们可以采用深度优先遍历和广度优先遍历，我采用深度优先遍历。
代码：
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1 == NULL) return root2;
if(root2 == NULL) return root1;
TreeNode* newroot = new TreeNode(root1->val + root2->val);
newroot->left = mergeTrees(root1->left,root2->left);
newroot->right = mergeTrees(root1->right,root2->right);
return newroot;
}
};
628. 三个数的最大乘积
链接: 最大乘积
难度： 简单
题目：
运行示例：
思路：
这道题就是排序，然后找三个数相乘最大，若全是正数肯定是最大的三个数相乘，但是注意如果有负数的话，两个最小负数与最大正数相乘也可能是最大。
代码：
class Solution {
public:
int maximumProduct(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n = nums.size();
return max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);
}
};
289. 生命游戏
链接: 生命游戏
难度： 中等
题目：
运行示例：
思路：
这道题我们可以复制原数组，利用复制后的数组来修改现在数组的状态。
代码：
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int neighbors[3] = {0, 1, -1};
int rows = board.size();
int cols = board[0].size();
vector<vector<int> >copyBoard(rows, vector<int>(cols, 0));
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
copyBoard[row][col] = board[row][col];
}
}
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
int liveNeighbors = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
int r = (row + neighbors[i]);
int c = (col + neighbors[j]);
if ((r < rows && r >= 0) && (c < cols && c >= 0) && (copyBoard[r][c] == 1)) {
liveNeighbors += 1;
}
}
}
}
if ((copyBoard[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
board[row][col] = 0;
}
if (copyBoard[row][col] == 0 && liveNeighbors == 3) {
board[row][col] = 1;
}
}
}
}
};
299. 猜数字游戏
链接: 猜数字游戏
难度： 中等
题目：
运行示例：
思路：
这道题就是利用遍历，然后统计出错的个数以及正确的个数。
代码：
class Solution {
public:
string getHint(string secret, string guess) {
int bulls = 0;
vector<int> ctS(10),ctG(10);
for(int i = 0; i < secret.size(); i++){
if(secret[i] == guess[i]) bulls++;
else{
ctS[secret[i]- '0']++;
ctG[guess[i] - '0']++;
}
}
int count = 0;
for(int i = 0 ;i < 10; i++){
count += min(ctS[i],ctG[i]);
}
return to_string(bulls) + 'A' + to_string(count) + 'B';
}
};
149. 直线上最多的点数
链接: 直线上最多的点数
难度： 困难
题目：
运行示例：
思路：
这道题我们就是可以利用枚举，我们找任意两点构成直线，看其他点是否共线。改进的话就是利用哈希表记录所有共线的斜率情况。
代码：
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int ans = 2;
if(points.size() == 1) return 1;
for(int i = 0; i < points.size()-1; i++){
vector<int> pointa = points[i];
for(int j = i+1; j < points.size(); j++){
vector<int> pointb = points[j];
int number = 2;
for(int k = 0; k < points.size() && k!=i && k!= j;k++){
vector<int> pointc = points[k];
int s1 = (pointb[1] - pointa[1])*(pointc[0]-pointa[0]);
int s2 = (pointc[1] - pointa[1])*(pointb[0]-pointa[0]);
if(s1 == s2) number++;
}
ans = max(ans,number);
}
}
return ans;
}
};
改进
class Solution {
public:
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int maxPoints(vector<vector<int>>& points) {
int ans = 1;
if(points.size() == 1) return 1;
for(int i = 0; i < points.size(); i++){
vector<int> pointa = points[i];
unordered_map<string,int>map;
int maxv = 0;
for(int j = i+1; j < points.size(); j++){
vector<int> pointb = points[j];
int s1 = pointb[1] - pointa[1];
int s2 = pointb[0] - pointa[0];
int k = gcd(s1, s2);
string key = to_string(s1 / k) + "_" + to_string(s2 / k);
map[key]++;
maxv = max(maxv,map[key]);
}
ans = max(ans,maxv+1);
}
return ans;
}
};
