2025-02-01

题目传送门：81. 搜索旋转排序数组 II - 力扣（LeetCode）

这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。

可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4,5,6][4, 5, 6] 和 [7,0,1,2][7, 0, 1, 2] 两个部分，其中左边 [4,5,6][4, 5, 6] 这个部分的数组是有序的，其他也是如此。

这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l,mid][l, mid] 和 [mid+1,r][mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

对于数组中有重复元素的情况，二分查找时可能会有 a[l]=a[mid]=a[r]a[l]=a[mid]=a[r]，此时无法判断区间 [l,mid][l,mid] 和区间 [mid+1,r][mid+1,r] 哪个是有序的。

例如 nums=[3,1,2,3,3,3,3]nums=[3,1,2,3,3,3,3]，target=2target=2，首次二分时无法判断区间 [0,3][0,3] 和区间 [4,6][4,6] 哪个是有序的。

对于这种情况，我们只能将当前二分区间的左边界加一，右边界减一，然后在新区间上继续二分查找。

最后实现代码如下：

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
class Solution {
public:
    bool search(vector<int> &nums, int target) {
        int n = nums.size();
        if (n == 0) {
            return false;
        }
        if (n == 1) {
            return nums[0] == target;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
                ++l;
                --r;
            } else if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return false;
    }
};

2025-02-02

题目传送门：598. 区间加法 II - 力扣（LeetCode）

就是找所有操作中的最小行号和最小列号相乘就可以了。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxCount(int m, int n, vector<vector<int>>& ops) {
        if (ops.size()==0) return m*n;
        int minR = ops[0][0], minC = ops[0][1];
        for (auto & op : ops) {
            minR = min(minR, op[0]);
            minC = min(minC, op[1]);
        }
        return minR * minC;
    }
};

2025-02-03

题目传送门：680. 验证回文串 II - 力扣（LeetCode）

双指针即可

最后实现代码如下：

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
class Solution {
public:
    bool checkPalindrome(const string& s, int low, int high) {
        for (int i = low, j = high; i < j; ++i, --j) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }

    bool validPalindrome(string s) {
        int low = 0, high = s.size() - 1;
        while (low < high) {
            char c1 = s[low], c2 = s[high];
            if (c1 == c2) {
                ++low;
                --high;
            } else {
                return checkPalindrome(s, low, high - 1) || checkPalindrome(s, low + 1, high);
            }
        }
        return true;
    }
};

2025-02-04

题目传送门：922. 按奇偶排序数组 II - 力扣（LeetCode）

分类排序完成后，再合并即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        vector<int> odd, even;
        for (auto &num : nums) {
            if (num % 2) odd.emplace_back(num);
            else even.emplace_back(num);
        }
        vector<int> ans;
        for(int i=0;i<odd.size();++i){
            ans.emplace_back(even[i]);
            ans.emplace_back(odd[i]);
        }
        return ans;
    }
};

2025-02-05

题目传送门：90. 子集 II - 力扣（LeetCode）

暴搜+集合set熟练运用

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        int n = nums.size();
        set<vector<int>> se;
        for(int i=0;i<(1<<n);++i){
            vector<int> tmp;
            int nw = i;
            for(int j=0;j<n;++j){
                if ((nw>>j)&1) tmp.push_back(nums[j]);
            }
            sort(tmp.begin(), tmp.end());
            se.insert(tmp);
        }
        vector<vector<int>> ans;
        for(auto & itm : se){
            ans.push_back(itm);
        }
        return ans;
    }
};

2025-02-06

题目传送门：47. 全排列 II - 力扣（LeetCode）

同上，暴搜+集合set熟练运用

最后实现代码如下：

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
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        set<vector<int>> se;
        int n = nums.size();
        vector<bool> flag(n,false);
        vector<int>  tmp;
        function<void(int)> func = [&](int cnt){
            if (cnt == n) {
                se.insert(tmp); return;
            }
            for(int i=0;i<n;++i){
                if (!flag[i]) {
                    tmp.push_back(nums[i]);
                    flag[i] = true;
                    func(cnt+1);
                    tmp.pop_back();
                    flag[i] = false;
                }
            }
        };
        func(0);
        vector<vector<int>> ans;
        for (auto & itm : se) {
            ans.push_back(itm);
        }
        return ans;
    }
};

但是上面这种做法效率会非常低。

2025-02-07

题目传送门：59. 螺旋矩阵 II - 力扣（LeetCode）

大模拟

最后实现代码如下：

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:
    vector<vector<int>> generateMatrix(int n) {
        int maxNum = n * n;
        int curNum = 1;
        vector<vector<int>> matrix(n, vector<int>(n));
        int row = 0, column = 0;
        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  // 右下左上
        int directionIndex = 0;
        while (curNum <= maxNum) {
            matrix[row][column] = curNum;
            curNum++;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || matrix[nextRow][nextColumn] != 0) {
                directionIndex = (directionIndex + 1) % 4;  // 顺时针旋转至下一个方向
            }
            row = row + directions[directionIndex][0];
            column = column + directions[directionIndex][1];
        }
        return matrix;
    }
};

2025-02-08

题目传送门：63. 不同路径 II - 力扣（LeetCode）

简单的动态规划问题

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(), m = obstacleGrid[0].size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        // if (obstacleGrid[0][0]) return 0;
        dp[1][1] = obstacleGrid[0][0]==0?1:0;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                if (obstacleGrid[i-1][j-1]) continue;
                dp[i][j] += dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[n][m];
    }
};

2025-02-09

题目传送门：80. 删除有序数组中的重复项 II - 力扣（LeetCode）

双指针即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) {
            return n;
        }
        int slow = 2, fast = 2;
        while (fast < n) {
            if (nums[slow - 2] != nums[fast]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};

2025-02-10

题目传送门：

最后实现代码如下：

1

2025-02-11

题目传送门：

最后实现代码如下：

1

2025-02-12

题目传送门：1760. 袋子里最少数目的球 - 力扣（LeetCode）

二分一下就可以啦

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        function<bool(int)> judge = [&](int ball){
            int nw = 0;
            for(auto num : nums){
                nw += (num-1) / ball;
            }
            return nw <= maxOperations ? true : false;
        };
        int l = 1, r=1e9+1;
        while(l<r){
            int mid = (r-l)/2 + l;
            if (judge(mid)) r = mid;
            else l = mid+1;
        }
        return l;
    }
};

2025-02-13

题目传送门：1742. 盒子中小球的最大数量 - 力扣（LeetCode）

模拟题

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int countBalls(int lowLimit, int highLimit) {
        function<int(int)> func = [&](int cnt){
            int ans = 0;
            while(cnt){
                ans += (cnt%10);
                cnt /= 10;
            }
            return ans;
        };
        vector<int> buk(100,0);
        for(int i=lowLimit;i<=highLimit;++i){
            buk[func(i)]++;
        }
        int ans = buk[func(lowLimit)];
        for(int i=0;i<99;++i) ans = max(ans,buk[i]);
        return ans;
    }
};

2025-02-14

题目传送门：1552. 两球之间的磁力 - 力扣（LeetCode）

二分一下啦

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        function<bool(int)> judge = [&](int interval){
            int pre = position[0], cnt = 1;
            for(int i = 1; i < position.size(); ++i) {
                if (position[i] - pre >= interval) {
                    pre = position[i];
                    cnt += 1;
                }
            }
            return cnt >= m;
        };
        int l = 1, r = 1e9+1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (judge(mid)) l =mid+1;
            else r = mid;
        }
        return l-1;
    }
};

2025-02-15

题目传送门：1706. 球会落何处 - 力扣（LeetCode）

模拟题，简单模拟下就好。

最后实现代码如下：

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
39
40
41
42
43
44
45
class Solution {
public:
    vector<int> findBall(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<int> ans;
        for(int i=0; i<m; ++i){
            int nw = i;
            bool flag = false;
            for(int j=0;j<n;++j){
                if(grid[j][nw]==1){ // 如果当前块是朝右
                    if (nw!=m-1) {
                        if (grid[j][nw+1]==1){
                            nw++;
                        } else {
                            flag = true;break;
                            // if(j!=n-1) {flag = true;break;}
                            // nw++;
                        }
                    } else { // 如果是最后一列
                        flag = true;break;
                        // if(j!=n-1) {flag = true;break;}
                        // nw++;
                    }
                } else {
                    if (nw!=0) {
                        if (grid[j][nw-1]==-1){
                            nw--;
                        } else {
                            flag = true;break;
                            // if(j!=n-1) {flag=true; break;}
                            // nw--;
                        } 
                    } else {
                        flag = true;break;
                        // if(j!=n-1) {flag=true; break;}
                        // nw--;
                    }
                }
            }
            if (!flag) ans.push_back(nw);
            else ans.push_back(-1);
        }  
        return ans;
    }
};

2025-02-16

题目传送门：1299. 将每个元素替换为右侧最大元素 - 力扣（LeetCode）

模拟简单题啦，遍历一遍即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int n = arr.size();
        vector<int> ans(n,-1);
        for(int i=n-2;i>=0;--i){
            ans[i] = max(arr[i+1],ans[i+1]);
        }
        return ans;
    }
};

2025-02-17

题目传送门：1287. 有序数组中出现次数超过25%的元素 - 力扣（LeetCode）

排序后，计数判断即可～

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int n = arr.size();
        int prev = -1;
        int cnt = 1;
        for(int i=0; i<n; ++i){
            if (arr[i]!=prev) {
                cnt = 1;
                prev = arr[i];
            }
            else {
                cnt++;
            }
            if (cnt*4 > n) return prev;
        }
        return -1;
    }
};

2025-02-18

题目传送门：2080. 区间内查询数字的频率 - 力扣（LeetCode）

哈希表+二分查找，对于每个值都建立一个列表，按照顺序维护他出现的位置，然后对这个列表进行upper_bound-lower_bound即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class RangeFreqQuery {
public:
    unordered_map<int,vector<int>> mp;
    RangeFreqQuery(vector<int>& arr) {
        int n = arr.size();
        for (int i=0;i<n;++i){
            mp[arr[i]].push_back(i);
        }
    }
    
    int query(int left, int right, int value) {
        vector<int>& tmp = mp[value];
        return upper_bound(tmp.begin(),tmp.end(),right) - lower_bound(tmp.begin(),tmp.end(),left);
    }
};

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * RangeFreqQuery* obj = new RangeFreqQuery(arr);
 * int param_1 = obj->query(left,right,value);
 */

2025-02-19

题目传送门：624. 数组列表中的最大距离 - 力扣（LeetCode）

  1. 对于每个数组，维护一个最大值列表和最小值列表（用列表形式存储每个数组中的最大值和最小值）。
  2. 然后找出这个列表中的最大值、次大值以及最小值、次小值。
  3. 如果最大值和最小值不在一个数组中的话，返回他们两个的差。
  4. 如果在的话，就返回max(最大值-次小值，次大值-最小值)

最后实现代码如下：

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
class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        int n = arrays.size();
        vector<int> maxx, minn;
        for (auto arr : arrays) {
            int nn = arr.size();
            minn.push_back(arr[ 0 ]);
            maxx.push_back(arr[nn-1]);
        }
        int max_num1=maxx[0],max_loc1=0,max_num2=maxx[0],max_loc2=0;
        int min_num1=minn[0],min_loc1=0,min_num2=minn[0],min_loc2=0;
        for( int i = 0; i < n ; ++ i ) {
            if (maxx[i] > max_num1) max_num1 = maxx[i], max_loc1 = i;
            if (minn[i] < min_num1) min_num1 = minn[i], min_loc1 = i;
        }
        if (max_loc1 == 0 && n > 1) max_loc2 = 1, max_num2 = maxx[1]; 
        if (min_loc1 == 0 && n > 1) min_loc2 = 1, min_num2 = minn[1];
        for( int i = 0; i < n ; ++ i ) {
            if (maxx[i] > max_num2 && i != max_loc1) max_num2 = maxx[i], max_loc2 = i;
            if (minn[i] < min_num2 && i != min_loc1) min_num2 = minn[i], min_loc2 = i;
        }
        return max_loc1 != min_loc1 ? max_num1-min_num1 : max(max_num1-min_num2, max_num2-min_num1);
    }
};

2025-02-20

题目传送门：2595. 奇偶位数 - 力扣（LeetCode）

模2除2，做统计即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> evenOddBit(int n) {
        vector<int> ans(2,0);
        int cnt = 0;
        while ( n ) {
            ans[cnt%2] += n%2;
            n /= 2;
            cnt++;
        }
        return ans;
    }
};

本站由 @anonymity 使用 Stellar 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。