2024-07-01

题目传送门：2065. 最大化一张图中的路径价值 - 力扣（LeetCode）

这道题看上去非常的吓人，但是我们注意一下数据范围便可以发现，由于每条边的时间以及总的时间限制最小为10最大为100，这说明我们至多只会经过图上的 10 条边。并且由于图中每个节点的度数都不超过 4，因此我们可以枚举（暴搜）所有从节点 0 开始的路径。暴搜终止条件就是超时了。

最后实现代码如下：

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:
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        int n = values.size();
        vector<vector<pair<int,int>>> g(n);
        for (auto edge : edges) {
            g[edge[0]].emplace_back(edge[1], edge[2]);
            g[edge[1]].emplace_back(edge[0], edge[2]);
        }

        vector<bool> vis(n, false);
        vis[0] = true;
        int ans = 0;

        function<void(int, int, int)> dfs = [&](int u, int time, int value){
            if(u == 0) {
                ans = max(ans, value);
            }
            for(auto [v, dist]:g[u]){
                if (time + dist <= maxTime) {
                    if(!vis[v]) {
                        vis[v] = true;
                        dfs(v, time+dist, value+values[v]);
                        vis[v] = false;
                    } else {
                        dfs(v, time+dist,value);
                    }
                }
            }
        };

        dfs(0, 0, values[0]);
        return ans;

    }
};

2024-07-02

题目传送门：3115. 质数的最大距离 - 力扣（LeetCode）

正好借此题复习一下欧拉筛。因为数的范围最大只到100，因此预处理一下100内的质数然后分别找出队列左边第一个质数的下标和右边第一个质数的下标即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maximumPrimeDifference(vector<int>& nums) {
        int MAX=100, n = nums.size();
        vector<bool> vis(101, false);
        vector<int> primes;
        for(int i=2;i<=MAX;++i){
            if (!vis[i]) primes.push_back(i);
            for(auto prime : primes){
                if (i * prime > MAX) break;
                vis[i * prime] = true;
                if (i % prime == 0) break;
            }
        }
        vis[0] = true; vis[1] = true;
        int i=0,j=n-1;
        while(vis[nums[i]]) i++;
        while(vis[nums[j]]) j--;
        return j-i;
    }
};

2024-07-03

题目传送门：3099. 哈沙德数 - 力扣（LeetCode）

快乐签到题

最后实现代码如下：

1
2
3
4
5
6
7
8
class Solution {
public:
    int sumOfTheDigitsOfHarshadNumber(int x) {
        int ans = 0, xx = x;
        while (x) ans += x%10, x /= 10;
        return xx%ans==0?ans:-1;
    }
};

2024-07-04

题目传送门：3086. 拾起 K 个 1 需要的最少行动次数 - 力扣（LeetCode）

贪心+二分

最后实现代码如下：

1

2024-07-05

题目传送门：3033. 修改矩阵 - 力扣（LeetCode）

签到题喜加一

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> modifiedMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int>col_max = matrix[0];
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                col_max[i] = max(col_max[i], matrix[j][i]);
            }
        }
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(matrix[i][j]==-1) matrix[i][j] = col_max[j];
            }
        }
        return matrix;
    }
};

2024-07-06

题目传送门：3101. 交替子数组计数 - 力扣（LeetCode）

可以把他当成一个DP来处理，开一个和数组一样长的DP数组，dp每一项记录以该项结尾能构成的子数组数。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    long long countAlternatingSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<long long>dp(n+2, 0);
        dp[1] = 1;
        for(int i=2;i<=n;++i){
            if (nums[i-1] ^ nums[i-2]) dp[i] = 1 + dp[i-1];
            else dp[i] = 1;
        }
        long long ans=0;
        for(int i=1;i<=n;++i) ans += dp[i];
        return ans;
    }
};

仔细观察上述代码，我们发现dp数组也可以被我们优化掉：

优化后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    long long countAlternatingSubarrays(vector<int>& nums) {
        int n = nums.size();
        long long cnt = 0, ans = 0;
        for(int i=1;i<=n;++i){
            if (i!=1&&nums[i-1] ^ nums[i-2]) cnt++;
            else cnt = 1;
            ans += cnt;
        }
        return ans;
    }
};

其实就是一道遍历题

2024-07-07

题目传送门：1958. 检查操作是否合法 - 力扣（LeetCode）

大模拟题目，遍历8个方向，只有第一个和当前颜色不同在继续判断，最后记得判断最后一个块的颜色和传入颜色是否相同即可。

最后实现代码如下：

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
class Solution {
public:
    bool checkMove(vector<vector<char>>& board, int rMove, int cMove, char color) {
        int n = board.size(), m = board[0].size();
        function<bool(int, int)> judge = [&](int x,int y){
            if (x<0||y<0||x>=n||y>=m) return false;
            return true;
        };
        function<bool(char, int)> judge_col = [&](char nw_color,int rev){
            if (rev&&(nw_color!=color)) {
                if (nw_color=='B'&&color=='W') return true;
                if (nw_color=='W'&&color=='B') return true;
                return false;
            }
            if (!rev&&(nw_color==color)) return true;
            return false;
        };
        vector<vector<int>> dirs = {{-1,0},{1,0},{0,-1},{0,1},{1,1},{-1,-1},{-1,1},{1,-1}};
        for (auto dir : dirs){
            if(judge(rMove+dir[0],cMove+dir[1])&&judge_col(board[rMove+dir[0]][cMove+dir[1]],1)){
                int cnt = 1;
                while(judge(rMove+dir[0]*cnt,cMove+dir[1]*cnt)&&judge_col(board[rMove+dir[0]*cnt][cMove+dir[1]*cnt],1)) cnt++;
                if (judge(rMove+dir[0]*cnt,cMove+dir[1]*cnt)&&judge_col(board[rMove+dir[0]*cnt][cMove+dir[1]*cnt],0)) return true;
            }
        }
        return false;
    }
};

2024-07-08

题目传送门：724. 寻找数组的中心下标 - 力扣（LeetCode）

快乐签到题，遍历一遍即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum_all = 0, n = nums.size();
        for(int i=0;i<n;++i) sum_all += nums[i];
        int sum_now=0;
        for(int i=0; i<n; ++i) {
            if (sum_now == sum_all-nums[i]-sum_now) return i;
            sum_now += nums[i];
        }
        return -1;
    }
};

2024-07-09

题目传送门：3102. 最小化曼哈顿距离 - 力扣（LeetCode）

需要使用技巧：曼哈顿距离转切比雪夫距离，详情可见灵神的题解：【图解】曼哈顿距离转切比雪夫距离（Python/Java/C++/Go）

转换公式如下：

∣x1−x2∣+∣y1−y2∣=max⁡(∣x1′−x2′∣,∣y1′−y2′∣)\left| x_1 - x_2 \right| + \left| y_1 - y_2 \right| = \max \left( \left| x_1' - x_2' \right|, \left| y_1' - y_2' \right| \right)

其中左侧为曼哈顿距离，右侧为切比雪夫距离，坐标变换关系如下所示：

(x′,y′)=(x+y,y−x)\left( x', y' \right) = \left( x + y, y - x \right)

做了上面的变换后，我们的任务就很简单了。可以定义两个有序集合，分别维护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
26
class Solution {
public:
    int minimumDistance(vector<vector<int>>& points) {
        multiset<int> xs, ys;
        for (auto& p : points) {
            xs.insert(p[0] + p[1]);
            ys.insert(p[1] - p[0]);
        }

        int ans = INT_MAX;
        // 枚举被移除的点
        for (auto& p : points) {
            int x = p[0] + p[1], y = p[1] - p[0];
            xs.erase(xs.find(x)); // 移除一个 x
            ys.erase(ys.find(y)); // 移除一个 y

            int dx = *xs.rbegin() - *xs.begin(); // 最大x-最小x
            int dy = *ys.rbegin() - *ys.begin(); // 最大y-最小y
            ans = min(ans, max(dx, dy));

            xs.insert(x);
            ys.insert(y);
        }
        return ans;
    }
};

这种方法写法上最为简单，当然我们也可以维护每个坐标的最大次大以及最小次小值，一共8个值。

2024-07-10

题目传送门：2970. 统计移除递增子数组的数目 I - 力扣（LeetCode）

咋一看以为很难，但是看到数据范围是50，果断进行枚举子数组的初始和结束端点即可。

最后实现代码如下：

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 incremovableSubarrayCount(vector<int>& nums) {
        int n = nums.size();
        function<bool(int, int)> judge = [&](int x,int y){
            int prev = 0;
            for(int i=0;i<n;++i){
                if (i>=x&&i<=y) continue;
                if (nums[i] <= prev) return false;
                prev = nums[i];
            }
            return true;
        };
        int ans = 0;
        for(int i=0;i<n;++i){
            for(int j=i;j<n;++j){
                ans = judge(i,j)?ans+1:ans;
            }
        }
        return ans;
    }
};

2024-07-11

题目传送门：2972. 统计移除递增子数组的数目 II - 力扣（LeetCode）

一道非常有意思的双指针题目，首先我们先找到能被删掉的最短后缀，删掉一个子数组相当于，将原数列分为了一个前缀和后缀，定义l为剩余前缀的最后一个数,j为剩余后缀开始的第一个数。

由于我们已经找到了最短后缀，因此l前面的数是具有一定单调性质的。而对于j（最开始就是最后一个数）他的停止条件是如果当前j大于j+1，因此j也有一定的单调性，我们遍历j的时候,只需比较j位置的数是否大于l位置的数，如果不是则将l--，找到第一个小于j位置的l，那么l前面的所有前缀肯定都满足条件，答案加上现目前前缀数总和(l+2)即可。因为j也有单调性的缘故，倒着遍历j时之前被更新l--掉的地方就不用看了。肯定不满足当前j的条件。

本人语文水平有限，更为清晰的题解请看：灵茶山艾府：双指针，O(n) 时间 O(1) 空间（Python/Java/C++/C/Go/JS/Rust）

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    long long incremovableSubarrayCount(vector<int>& nums) {
        int n = nums.size();
        int l=0;
        for(int i=1;i<n;++i){
            if (nums[i] > nums[i-1]){
                l++;
            } else break;
        }
        if(l==n-1) return (long long) n*(n+1)/2;
        long long ans = l+2;
        for(int j=n-1;j >= 0&&(j == n - 1|| nums[j] < nums[j + 1]);--j){ // 枚举后缀开始的第一个数
            while( l>=0 && nums[l]>= nums[j]) l--;
            ans += l+2;
        }
        return ans;
        
    }
};

2024-07-12

题目传送门：2974. 最小数字游戏 - 力扣（LeetCode）

签到题，模拟题

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> numberGame(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> arr;
        for(int i=0;i<n/2;++i){
            arr.push_back(nums[i*2+1]);
            arr.push_back(nums[i*2]);
        }
        return arr;
    }
};

2024-07-13

题目传送门：3011. 判断一个数组是否可以变为有序 - 力扣（LeetCode）

模拟题，根据1的个数将数组划分为几段区间，然后维护每一个区间的最大最小值，如果每两个相邻区间都是下一个区间的最小值大于上一个区间的最大值则满足条件返回true，否则不满足条件返回false。

最后实现代码如下：

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 canSortArray(vector<int>& nums) {
        int n = nums.size();
        function<int(int)> judge = [&](int u){
            int cnt = 0;
            while(u){
                cnt += (u&1);
                u = u>>1;
            }
            return cnt;
        };
        vector<int> arr;
        for(int i=0;i<n;++i) arr.push_back(judge(nums[i]));
        vector<pair<int,int>> pairs;
        int prev = -1,minn,maxx;
        for(int i=0;i<n;++i) {
            if(prev == arr[i]){
                maxx = max(nums[i],maxx);
                minn = min(nums[i],minn);
            }
            else {
                if(i!=0) pairs.emplace_back(minn,maxx);
                prev = arr[i];
                maxx = nums[i];
                minn = nums[i];
            }
        }
        pairs.emplace_back(minn,maxx);
        int m = pairs.size();
        for(int i=1;i<m;++i){
            if (pairs[i-1].second > pairs[i].first) return false;
        }
        return true;
    }
};

2024-07-14

题目传送门：807. 保持城市天际线 - 力扣（LeetCode）

维护每行每列的最大值就可以了。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<int> rows(n,0);
        vector<int> cols(m,0);
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                rows[i] = max(rows[i],grid[i][j]);
                cols[j] = max(cols[j],grid[i][j]);
            }
        }
        int ans = 0;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                ans += min(rows[i],cols[j]) - grid[i][j];
            }
        }
        return ans;
    }
};

2024-07-15

题目传送门：721. 账户合并 - 力扣（LeetCode）

本质这道题可以看成一个连通块问题（求有多少连通水洼），因此可以使用dfs解决问题。这道题主要难点在于使用哈希表将字符串映射成int类型对问题进行简化，细节操作见下面的代码实现。

最后实现代码如下：

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
class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();
        unordered_map<string, vector<int>> accounts_idx;
        for(int i=0;i<n;++i){
            for(int j=1;j<accounts[i].size();++j){
                accounts_idx[accounts[i][j]].push_back(i);
            }
        }
        vector<bool> vis(n,false);
        unordered_set<string> email_set;
        function<void(int)> dfs = [&](int i){
            vis[i] = true;
            for(int k = 1;k < accounts[i].size();++k){
                string email = accounts[i][k];
                if (email_set.contains(email)) continue;
                email_set.insert(email);
                for (int j : accounts_idx[email]) { // 遍历所有包含该邮箱地址的账户下标 j
                    if (!vis[j]) { // j 没有访问过
                        dfs(j);
                    }
                }
            }
        };
        vector<vector<string>> ans;
        for(int i=0; i<vis.size(); ++i){
            if (vis[i]) continue;
            email_set.clear();
            dfs(i);
            vector<string> res = {accounts[i][0]};
            res.insert(res.end(), email_set.begin(), email_set.end());
            sort(res.begin()+1, res.end());

            ans.push_back(res);
        }
        return ans;
    }
};

2024-07-16

题目传送门：2956. 找到两个数组中的公共元素 - 力扣（LeetCode）

签到题，但是可以学习一下如何使用vector初始化unordered_set类型的变量。
最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> nums1_set(nums1.begin(), nums1.end());
        unordered_set<int> nums2_set(nums2.begin(), nums2.end());
        int ans1 = 0,ans2 = 0;
        for(const int &num : nums1){
            if (nums2_set.find(num)!=nums2_set.end())ans1++;
        }
        for(const int &num : nums2){
            if (nums1_set.find(num)!=nums1_set.end())ans2++;
        }
        return vector<int>{ans1,ans2};
    }
};

2024-07-17

题目传送门：2959. 关闭分部的可行集合数目 - 力扣（LeetCode）

由于数据范围非常小，可以枚举所有关闭分部的情况，然后对于每种关闭方案，使用Floyd算法每次获得全局最短路信息，判断是否满足条件即可。

最后实现代码如下：

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
class Solution {
public:
    int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
        
        int max_stats = 1<<n, ans = 0;
        vector<vector<int>> dis(n,vector<int>(n, 1e9));
        for(int stat=0;stat<max_stats;++stat){
            
            
            for(int i=0;i<n;++i) dis[i][i] = 0;
            for(auto road : roads) {
                if (((stat>>road[0])&1)==0||((stat>>road[1])&1)==0) continue;
                dis[road[0]][road[1]] = min(dis[road[0]][road[1]], road[2]);
                dis[road[1]][road[0]] = min(dis[road[1]][road[0]], road[2]);
            }
            
            // Floyd
            for(int k=0;k<n;++k){
                if ((stat>>k)&1==0) continue;
                for(int i=0;i<n;++i){
                    if ((stat>>i)&1==0) continue;
                    for(int j=0;j<n;++j){
                        if ((stat>>j)&1==0) continue;
                        dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
                    }
                }
            }

            bool flag = true;
            for(int i=0;i<n;++i){
                for(int j=0;j<n;++j){
                    if(dis[i][j] > maxDistance && (stat>>i)&1 && (stat>>j)&1){
                        flag = false;
                        break;
                    }
                }
                if (!flag) break;
            }
            if (flag) ans++;
        }
        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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
        vector<vector<int>> g(n, vector<int>(n, INT_MAX / 2)); // 防止加法溢出
        for (int i = 0; i < n; i++) {
            g[i][i] = 0; // 也可以不写，下面判断 maxDistance 时要保证 j != i
        }
        for (auto& e: roads) {
            int x = e[0], y = e[1], wt = e[2];
            g[x][y] = min(g[x][y], wt);
            g[y][x] = min(g[y][x], wt);
        }

        vector<vector<int>> f(n);
        auto check = [&](int s) -> bool {
            for (int i = 0; i < n; i++) {
                if ((s >> i) & 1) {
                    f[i] = g[i];
                }
            }

            // Floyd 算法（只考虑在 s 中的节点）
            for (int k = 0; k < n; k++) {
                if (((s >> k) & 1) == 0) continue;
                for (int i = 0; i < n; i++) {
                    if (((s >> i) & 1) == 0) continue;
                    for (int j = 0; j < n; j++) {
                        f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
                    }
                }
            }

            // 判断保留的节点之间的最短路是否均不超过 maxDistance
            for (int i = 0; i < n; i++) {
                if (((s >> i) & 1) == 0) continue;
                for (int j = 0; j < n; j++) {
                    if ((s >> j) & 1 && f[i][j] > maxDistance) {
                        return false;
                    }
                }
            }
            return true;
        };

        int ans = 0;
        for (int s = 0; s < (1 << n); s++) { // 枚举子集
            ans += check(s);
        }
        return ans;
    }
};

2024-07-18

题目传送门：3112. 访问消失节点的最少时间 - 力扣（LeetCode）

Dijkstra板子题，正好重新进行复习一下，只需要在更新的时候判断一下当前更新方案是否合法（有可能需要更新的点已经消失了，此时就不用更新）

最后实现代码如下：

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
class Solution {
public:
    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
        vector<vector<pair<int,int>>> g(n);
        for(auto edge: edges){
            g[edge[0]].emplace_back(edge[1],edge[2]);
            g[edge[1]].emplace_back(edge[0],edge[2]);
        }
        vector<int> dis(n,INT_MAX/2);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        vector<bool> vis(n, false);
        dis[0] = 0;
        pq.push(make_pair(dis[0],0));
        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();
            if (vis[u]) continue;
            vis[u] = true;
            // if (dis[u] > disappear[u]) continue;
            for(auto tmp : g[u]){
                int val = tmp.second, v = tmp.first;
                if (dis[v] > dis[u] + val && disappear[v] > dis[u]+val) {
                    dis[v] = dis[u]+val;
                    pq.push(make_pair(dis[v],v));
                }
            }
        }
        for(int i=0;i<n;++i){
            if (dis[i]==INT_MAX/2) dis[i] = -1;
        }
        return dis;
    }
};

2024-07-19

题目传送门：3096. 得到更多分数的最少关卡数目 - 力扣（LeetCode）

模拟题吧，先算出获胜条件的阈值，然后从第一位开始往后遍历，过程中统计Alice的得分，大于等于阈值返回当前是第几轮游戏，如果数组遍历完了依然不满足条件返回-1表示无法获胜。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minimumLevels(vector<int>& possible) {
        int n = possible.size(),sumpos=0;
        for(int i=0;i<n;++i) {
            if (possible[i]==0) sumpos -= 1;
            else sumpos += 1;
        }
        int thre;
        if (sumpos >= 0) thre = sumpos / 2 + 1;
        else thre = (sumpos-1) / 2 + 1;
        int tmp = possible[0]==1?1:-1, ans = 1;
        for(int i=1;i<n;++i){
            if (tmp>=thre) return ans;
            ans++;
            tmp += possible[i]==1?1:-1;
            
        }
        return -1;
    }
};

2024-07-20

题目传送门：2850. 将石头分散到网格图的最少移动次数 - 力扣（LeetCode）

由于数据范围很小，可以使用枚举法解决此题，首先先遍历所有格子，对于为0的地方，将格子坐标存入less数组，对于大于1的地方，将格子坐标存入more数组，每超过1一次就存一次坐标进去（比如当前位置是3，则存两次该位置的坐标到more数组中）。最终我们会得到一个长度相同的more和less数组。

然后此时我们只需要枚举其中一个数组的全排列，计算不同方案所使用的步数，返回最小步数即可。C中对vector数组枚举全排列的函数是next_permutation,具体关于该函数的介绍见C专栏中的next_permutation部分。

本题最后实现代码如下：

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
class Solution {
public:
    int minimumMoves(vector<vector<int>>& grid) {
        vector<pair<int,int>> less, more;
        for(int i=0;i<3;++i){
            for(int j=0;j<3;++j){
                if (grid[i][j]>1) {
                    for(int k=2; k<=grid[i][j]; ++k){
                        more.emplace_back(i, j);
                    }
                } else if (grid[i][j] == 0) {
                    less.emplace_back(i, j);
                }
            }
        }
        int ans = INT_MAX;
        do {
            int steps = 0;
            for(int i=0;i<more.size();++i){
                steps += abs(more[i].first - less[i].first) + abs(more[i].second - less[i].second);
            }
            ans = min(ans, steps);
        } while (next_permutation(more.begin(), more.end()));
        return ans;
    }
};

2024-07-21

题目传送门：1186. 删除一次得到子数组最大和 - 力扣（LeetCode）

该题目为经常练习的动态规划中的最大子数组和（最大子段和） 类题目，相比就是读了一个选择出来子数组后可以从中删除一个元素，那么我们可以在最大子数组和（最大子段和） 的常规解放上多一个状态维度，设计DP数组dp[n][2]含义如下，dp[i][0]表示以当前位置i的数结尾且未删除任何数可以达到的最大子数组和。dp[i][1]表示以当前位置i的数结尾且删除1个数可以达到的最大子数组和。这样定义后不难写出状态转移方程如下：

1
2
dp[i][0] = max(0, dp[i-1][0]) + arr[i-1];
dp[i][1] = max(0, max(dp[i-1][1], dp[i-2][0])) + arr[i-1];

从i=2开始循环

初始条件就是dp[1][0] = arr[0]; dp[1][1] = arr[0];

最后实现代码如下：

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

2024-07-22

题目传送门：2101. 引爆最多的炸弹 - 力扣（LeetCode）

首先根据炸弹爆炸半径建立一个有向图，然后对于每个点都DFS一遍，找到以当前点起爆能引爆的最大炸弹数，最后返回最大引爆数即可。

最后实现代码如下：

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
class Solution {
public:
    int maximumDetonation(vector<vector<int>>& bombs) {
        int n = bombs.size();
        vector<vector<int>> edges(n);
        for(int i=0;i<n;++i) {
            int xi = bombs[i][0], yi = bombs[i][1], vali = bombs[i][2];
            for(int j=0;j<n;++j){
                if(i==j) continue;
                int xj = bombs[j][0], yj = bombs[j][1];
                if (sqrt(double(xi-xj)*double(xi-xj)+double(yi-yj)*double(yi-yj)) <= (double)vali) {
                    edges[i].push_back(j);
                }
            }
        }
        
        int ans = 1;
        vector<bool> vis(n);
        function<int(int)> dfs = [&](int u){
            int tmp=1;
            vis[u] = true;
            for(auto v : edges[u]) {
                if(!vis[v]) tmp += dfs(v);
            }
            return tmp;
        };
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j) vis[j]=false;
            ans = max(ans, dfs(i));
        }
        return ans;
    }
};

2024-07-23

题目传送门：

最后实现代码如下：

1

2024-07-24

题目传送门：2766. 重新放置石块 - 力扣（LeetCode）

一道非常标准的C++ set 题，主要考察：

  • set初始化
  • set与vector互相转化
  • set基础操作（增删查）

详细知识点见C++专题，这里不再赘述

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> relocateMarbles(vector<int>& nums, vector<int>& moveFrom, vector<int>& moveTo) {
        set<int> se(nums.begin(), nums.end());
        int n = moveFrom.size();
        for(int i=0;i<n;++i){
            if (se.find(moveFrom[i])==se.end()) continue;
            se.erase(moveFrom[i]); se.insert(moveTo[i]);
        }
        return vector<int>(se.begin(),se.end());
    }
};

2024-07-25

题目传送门：2844. 生成特殊数字的最少操作 - 力扣（LeetCode）

观察数据范围可以看到数字最长为100位，所以此题简单贪心即可。从最后一位倒着遍历，碰到5就找最近的2，7；碰到0就找最近的0，5。在遍历的过程中维护操作最小值即可。

注意：一个0也是能够被25整除的

最后实现代码如下：

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 minimumOperations(string num) {
        int n = num.size();
        int ans = n;
        bool flag0 = false;
        for(int i=n-1;i>=0;--i){
            if (num[i]=='0') {
                flag0 = true;
                int tmp = n-1-i;
                int j=i-1;
                while (j>=0 && num[j]!='0' && num[j]!='5')j--;
                if (j!=-1) {tmp += (i-1-j); ans = min(ans, tmp);}
            }
            if (num[i]=='5') {
                int tmp = n-1-i;
                int j=i-1;
                while (j>=0 && num[j]!='2' && num[j]!='7')j--;
                if (j!=-1) {tmp += (i-1-j); ans = min(ans, tmp);}
            }
        }
        if (ans == n && flag0) ans--;
        return ans;
    }
};

2024-07-26

题目传送门：2740. 找出分区值 - 力扣（LeetCode）

读完题后，仔细理解一下不难发现就是找排序后相邻元素之间差值的最小。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int findValueOfPartition(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = nums[1] - nums[0], n = nums.size();
        for(int i=1;i<n;++i) ans = min(ans, nums[i]-nums[i-1]);
        return ans;
    }
};

2024-07-27

题目传送门：3106. 满足距离约束且字典序最小的字符串 - 力扣（LeetCode）

贪心，从最前面开始变，尽量让前面的字符接近a。

最后实现代码如下：

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:
    string getSmallestString(string s, int k) {
        function<int(char, char)> dist = [&](char a, char b){
            int dis = abs(a-b);
            return min(dis,26-dis);
        };
        for(char& c : s){
            if (dist(c,'a') <=k ) {
                k -= dist(c,'a');
                c = 'a';
                
            } else {
                char b = 'a';
                while(dist(c,b) > k) b++;
                c = char(b);
                break;
            }
        }
        return s;
    }
};

2024-07-28

题目传送门：699. 掉落的方块 - 力扣（LeetCode）

由于方块数量本身很少，所以可以采用枚举的方式进行最大高度更新，每次枚举到第i个方块，就遍历他前面i-1个方块，看当前方块是否落在前面方块上面，如果是则更新最大高度。依次遍历完所有的方块可得最终答案，时间复杂度为O(n2)O(n^2)。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        int n = positions.size();
        vector<int> heights(n);
        for(int i=0;i<n;++i){
            int left1 = positions[i][0], right1 = positions[i][0] + positions[i][1] - 1;
            heights[i] = positions[i][1];
            for(int j=0;j<i;++j){
                int left2 = positions[j][0], right2 = positions[j][0] + positions[j][1] - 1;
                if (right1 >= left2 && right2 >= left1) heights[i] = max(heights[i], heights[j] + positions[i][1]);
            }
        }
        for (int i = 1; i < n; i++) {
            heights[i] = max(heights[i], heights[i - 1]);
        }
        return heights;
    }
};

2024-07-29

题目传送门：682. 棒球比赛 - 力扣（LeetCode）

模拟题，C需要使用stoi用于字符串转整型，具体用法详见C专题。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int calPoints(vector<string>& operations) {
        vector<int> que;
        int n = 0;
        for(string operation : operations){
            if (operation == "C") que.pop_back(),n--;
            else if (operation == "D") que.push_back(que[n-1]*2),n++;
            else if (operation == "+") que.push_back(que[n-1]+que[n-2]),n++;
            else que.push_back(stoi(operation)),n++;
        }
        int ans = 0;
        for(int i=0;i<n;++i) ans += que[i];
        return ans;
    }
};

2024-07-30

题目传送门：2961. 双模幂运算 - 力扣（LeetCode）

快速幂板子题，快速幂算法详解见OI-Knowledge专题数学章节。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
        function<int(int,int,int)> ksm = [&](int a,int b,int m){
            if (b == 0) return 1;
            int nw = ksm(a,b/2,m)%m;
            if (b%2) return nw*nw%m*a%m;
            return nw*nw%m;
        };
        int n = variables.size();
        vector<int> ans;
        for(int i=0;i<n;++i){
            if (ksm(ksm(variables[i][0],variables[i][1],10),variables[i][2],variables[i][3])==target) ans.push_back(i);
        }
        return ans;
    }
};

2024-07-31

题目传送门：3111. 覆盖所有点的最少矩形数目 - 力扣（LeetCode）

贪心，排序后从小到大进行覆盖即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
        sort(points.begin(), points.end());
        int ans = 0, n = points.size();
        int prev = points[0][0]-1;
        for(int i=0;i<n;++i){
            if (points[i][0]<=prev) continue;
            ans+=1; prev = points[i][0]+w;
        }
        return ans;
    }
};

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