力扣题目训练（21）

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11

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]);
    }
};
1
2
3
4
5
6
7
8

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;
                }
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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';
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

改进

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26