2024-06-01

题目传送门：2928. 给小朋友们分糖果 I - 力扣（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 distributeCandies(int n, int limit) {
        int ans = 0;
        function<void(int, int)> dfs =[&](int cnt,int res) {
            if(cnt == 3 && res == 0) {
                ans ++; return;
            }
            if(cnt == 2){
                if(res<=limit) dfs(cnt+1,0);
            } else {
                int tmp = min(res,limit);
                for(int i=0;i<=tmp;++i){
                    dfs(cnt+1,res-i);
                }
            }
        };
        dfs(0,n);
        return ans;
    }
};

2024-06-02

题目传送门：575. 分糖果 - 力扣（LeetCode）

签到题目，不再赘述。

最后实现代码如下：

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

2024-06-03

题目传送门：1103. 分糖果 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
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        function<bool(int,int)> addup = [&](int x,int tar){
            int xx = 0;
            for(int i=1;i<=x;++i){
                xx += i;
                if (xx > tar) return false;
            }
            return true;
        };
        int l=1, r=candies/num_people+1000;
        while (l<r) {
            int mid = l + ((r-l)>>1);
            if (addup(mid,candies)) l = mid+1;
            else r = mid;
        }
        l -= 1;
        int res=0;
        for(int i=1;i<=l;++i){
            res += i;
        }
        res = candies - res;
        vector<int> ans;
        for(int i=1;i<=num_people;++i){
            int tmp = i;
            int nans = 0;
            while(tmp<=l) {
                nans += tmp;
                tmp += num_people;
            }
            if (tmp == l+1) nans += res;
            ans.push_back(nans);
        }
        return ans;
    }
};

2024-06-04

题目传送门：3067. 在带权树网络中统计可连接服务器对数目 - 力扣（LeetCode）

这道题是一道较为典型的搜索回溯的题目，递归函数每次返回当前节点下（包含当前节点）满足距离整除signalSpeed的节点数量。
需要注意的是，在回溯的时候最后判断一下当前递归函数，是不是在递归根节点就可以了（最后一步操作和其余节点的操作不太一样）。

最后实现代码如下：

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
class Solution {
public:
    vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
        int n = edges.size()+1;
        vector<vector<pair<int,int>>>es(n);
        for(auto &edge : edges) {
            es[edge[0]].emplace_back(edge[1],edge[2]);
            es[edge[1]].emplace_back(edge[0],edge[2]);
        }
        vector<int> final_ans;
        function<int(int, int, int)> dfs = [&](int u, int fa, int nw_dis) {
            int nw = 0;
            if (fa != -1) {
                if (nw_dis%signalSpeed==0) nw += 1;
                for (auto &tmp : es[u]) {
                    if (tmp.first == fa) continue;
                    nw += dfs(tmp.first,u,nw_dis+tmp.second);
                }
            } else {
                vector<int> ans;
                for (auto &tmp : es[u]) {
                    if (tmp.first == fa) continue;
                    ans.push_back(dfs(tmp.first,u,nw_dis+tmp.second));
                }
                int nn = ans.size();
                for(int i=0;i<nn;++i){
                    for(int j=i+1;j<nn;++j){
                        nw += ans[i] * ans[j];
                    }
                }
            }
            return nw;
        };

        for (int i=0;i<n;++i) {
            final_ans.push_back(dfs(i,-1,0));
        }
        return final_ans;
    }
};

2024-06-05

题目传送门：3072. 将元素分配到两个数组中 II - 力扣（LeetCode）

离散化+树状数组

首先对队列中的值进行一个离散化操作(使用unordered_map),然后分别对两个队列维护两个树状数组进行查询和更新即可（前缀和查询+单点更新）

注意：需要注意的是题目要求判断的是严格大于，因此需要进行一定的操作将后缀和转化为前缀和；还有就是树状数组的下标从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
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    vector<int> resultArray(vector<int>& nums) {
        int n = nums.size();
        function<int(int)> lowbit = [&](int x){
            return x & (-x);
        };
        function<void(vector<int>&,int)> updateBIT = [&](vector<int>& bit, int a){
            int n = bit.size();
            while(a<n){
                bit[a]++;
                a += lowbit(a);
            }
        };
        function<int(vector<int>&,int)> queryBIT = [&](vector<int>& bit,int a){
            int sum = 0;
            while(a>0){
                sum += bit[a];
                a -= lowbit(a);
            }
            return sum;
        };

        vector<int> bit1(100002, 0), bit2(100002, 0);
        vector<int> arr1, arr2, ans, nnums = nums;
        unordered_map<int,int> mp;
        sort(nnums.begin(), nnums.end());
        int cnt = 0, prev = -1;
        for(auto num : nnums) {
            if (num != prev) cnt++;
            mp[num] = cnt;
            prev = num;
        }
        arr1.push_back(0); updateBIT(bit1, cnt+1-mp[nums[0]]);
        arr2.push_back(1); updateBIT(bit2, cnt+1-mp[nums[1]]);
        for(int i=2;i<n;++i){
            int q1 = queryBIT(bit1, cnt-mp[nums[i]]);
            int q2 = queryBIT(bit2, cnt-mp[nums[i]]);
            if (q1 > q2) updateBIT(bit1, cnt+1-mp[nums[i]]),arr1.push_back(i);
            else if (q1 < q2) updateBIT(bit2, cnt+1-mp[nums[i]]),arr2.push_back(i);
            else {
                if (arr1.size() <= arr2.size()) updateBIT(bit1, cnt+1-mp[nums[i]]),arr1.push_back(i);
                else updateBIT(bit2, cnt+1-mp[nums[i]]),arr2.push_back(i);
            }
        }
        for(int arr:arr1){ans.push_back(nums[arr]);}
        for(int arr:arr2){ans.push_back(nums[arr]);}
        return ans;
    }
};

2024-06-06

题目传送门：2938. 区分黑球与白球 - 力扣（LeetCode）

此题可以简单的抽象为一道贪心题目，「将所有的黑球都移动到右侧，将所有的白球都移动到左侧」，即0都在1的左侧。不难想到，对于每个白球需要移动多少次，取决于他前面有多少个黑球。因此遍历队列进行贪心即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    long long minimumSteps(string s) {
        int n = s.size();
        long long ans=0;
        int tmp_blk = 0;
        for(int i=0;i<n;++i){
            if(s[i]=='0') ans += tmp_blk;
            else tmp_blk++;
        }
        return ans;
    }
};

2024-06-07

题目传送门：3038. 相同分数的最大操作数目 I - 力扣（LeetCode）

签到遍历题。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n=nums.size(),poi = 0,pre=-1,ans=0;
        while(poi+2<=nums.size()){
            int tmp = nums[poi] + nums[poi+1];
            if(poi==0) pre = tmp,ans++;
            else if(pre == tmp) ans++;
            else break;
            poi += 2;
        }
        return ans;
    }
};

2024-06-08

题目传送门：3040. 相同分数的最大操作数目 II - 力扣（LeetCode）

刚做没有仔细看题目，以为是一个大暴搜，然后毫无意外的TLE了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int ans = 0, n = nums.size();
        function<void(int,int,int,int)> dfs = [&](int l, int r, int sum_num, int tmp_ans) {
            ans = max(ans, tmp_ans);
            if (r-l+1<2) return;
            if (nums[l]+nums[l+1] == sum_num || (l == 0 && r == n-1)) dfs(l+2, r, nums[l]+nums[l+1], tmp_ans+1);
            if (nums[r]+nums[r-1] == sum_num || (l == 0 && r == n-1)) dfs(l, r-2, nums[r]+nums[r-1], tmp_ans+1);
            if (nums[l] + nums[r] == sum_num || (l == 0 && r == n-1)) dfs(l+1,r-1,nums[r]+nums[l], tmp_ans+1);
        };
        dfs(0,n-1,-1,0);
        return ans;
    }
};

仔细思考后，发现其实target只会存在三种情况：

  1. nums[0] + nums[1]
  2. nums[0] + nums[n-1]
  3. nums[n-2] + nums[n-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
class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        vector<vector<int>> dp(n,vector<int>(n, -1));
        function<int(int,int,int)> dfs = [&](int l, int r, int sum_num){
            // ans = max(ans, tmp_ans);
            if (r-l+1<2) return 0;
            if (dp[l][r]!=-1) return dp[l][r];
            int tmp = 0;
            if (nums[l]+nums[r]==sum_num) tmp = max(tmp, 1+dfs(l+1, r-1, sum_num));
            if (nums[l]+nums[l+1]==sum_num) tmp = max(tmp, 1+dfs(l+2, r, sum_num));
            if (nums[r]+nums[r-1]==sum_num) tmp = max(tmp, 1+dfs(l, r-2, sum_num));
            dp[l][r] = tmp;
            return dp[l][r];
        };
        ans = max(ans, 1+dfs(2, n-1, nums[0]+nums[1]));
        dp = vector<vector<int>>(n, vector<int>(n, -1));
        ans = max(ans, 1+dfs(1, n-2, nums[0]+nums[n-1]));
        dp = vector<vector<int>>(n, vector<int>(n, -1));
        ans = max(ans, 1+dfs(0, n-3, nums[n-2]+nums[n-1]));
        return ans;
    }
};

2024-06-09

题目传送门：312. 戳气球 - 力扣（LeetCode）

最后实现代码如下：

1

2024-06-10

题目传送门：881. 救生艇 - 力扣（LeetCode）

贪心，因为每条船最多做两个人，所以最优策略是看能否将当前剩余人群中最重的人和最轻的人塞入一条船中，如果不行则最重的人需要单独一条船，对队列排序后进行双指针求解即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int n = people.size();
        sort(people.begin(), people.end());
        int l = 0, r=n-1, ans = 0;
        while (l<=r) {
            if (people[l]+people[r] <= limit) {
                l ++;
            }
            r -- ;
            ans ++;
        }
        return ans;
    }
};

2024-06-11

题目传送门：419. 甲板上的战舰 - 力扣（LeetCode）

遍历扫描，因为战舰只能水平或竖直放置，按照从左到右从上到下的顺序，统计战舰最左端和最上端部分的个数即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        int ans = 0;
        function<bool(int,int)> judge = [&](int x,int y){
            if (board[x][y]!='X') return false;
            if (x-1>=0 && board[x-1][y]=='X') return false;
            if (y-1>=0 && board[x][y-1]=='X') return false;
            return true;
        };
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if (judge(i, j)) ans++;
            }
        }
        return ans;
    }
};

2024-06-12

题目传送门：2806. 取整购买后的账户余额 - 力扣（LeetCode）

if语句签到题。

最后实现代码如下：

1
2
3
4
5
6
7
8
class Solution {
public:
    int accountBalanceAfterPurchase(int purchaseAmount) {
        int cost = purchaseAmount / 10 * 10;
        if (purchaseAmount % 10 >= 5) cost += 10;
        return 100 - cost;
    }
};

2024-06-13

题目传送门：

最后实现代码如下：

1

2024-06-14

题目传送门：2786. 访问数组中的位置使分数最大 - 力扣（LeetCode）

简单的动态规划，状态转移是对当前的下标i：

  • 选择一个之前的子序列，最后一个数和当前下标i奇偶性相同
  • 选择一个之前的子序列，最后一个数和当前下标i奇偶性不同

最后实现代码如下（使用堆优化，因为我定义的dp数组是以当前数为结尾（必须选当前数）最大的子序列）：

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:
    long long maxScore(vector<int>& nums, int x) {
        long long n = nums.size();
        vector<long long> dp(n+1,0);
        dp[0] = nums[0];
        priority_queue<long long> pq[2];
        pq[nums[0]%2].push(nums[0]);
        for (long long i=1;i<n;++i) {
            long long tmp_mod = nums[i] % 2;
            long long ans1 = -1e7, ans2 = -1e7;
            if (!pq[tmp_mod].empty())   ans1 = pq[tmp_mod].top() ;
            if (!pq[1-tmp_mod].empty()) ans2 = pq[1-tmp_mod].top();
            dp[i] = max(ans1, ans2-x) + nums[i];
            pq[tmp_mod].push(dp[i]);
        }
        long long ans = dp[0];
        for(long long i=1;i<n;++i) {
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

2024-06-15

题目传送门：2779. 数组的最大美丽值 - 力扣（LeetCode）

差分数组，此题相当于问给定n个区间，被覆盖最多元素的次数是多少，初始化一个全0的差分数组，对于每一个区间，区间最开始的元素对应位置在差分数组中+1，最后元素对应位置的下一个位置在差分数组中-1。最后对差分数组求前缀和就可知每个元素被覆盖的次数了，找出最大即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        vector<int> cnts(200003,0);
        for (auto &num : nums) {
            cnts[max(0,num-k)]++;
            cnts[num+k+1]--;
        }
        int max_ele = *max_element(nums.begin(),nums.end());
        int ans = cnts[0], nw = cnts[0];
        for(int i=1; i<=max_ele+k; ++i) {
            nw += cnts[i];
            ans = max(ans,nw);
        }
        return ans;
    }
};

2024-06-16

题目传送门：521. 最长特殊序列 Ⅰ - 力扣（LeetCode）

今天的签到题还有点意思，有点脑筋急转弯的感觉，题面描述那么多，其实只需要判断两个字符串是不是相同即可。相同返回-1，不相同返回最长字符串长度即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int findLUSlength(string a, string b) {
        if (a.compare(b) == 0) {
            return -1;
        }
        return max(a.size(), b.size());
    }
};

2024-06-17

题目传送门：522. 最长特殊序列 II - 力扣（LeetCode）

最后实现代码如下：

1

2024-06-18

题目传送门：2288. 价格减免 - 力扣（LeetCode）

模拟题，先使用空格对字符串进行划分，然后再判断一个字符串中除了$其余是否都是数字，如果是转为int进行计算后，加入答案中去。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string discountPrices(string sentence, int discount) {
        double dis = 1 - (discount / 100.0);
        stringstream ss(sentence);
        string ans, w;
        while (ss >> w){ // 按照空格进行分割
            if(!ans.empty()) {
                ans += ' ';
            }
            if (w.length() > 1 && w[0] == '$' && all_of(w.begin()+1, w.end(), ::isdigit)) {
                stringstream s;
                s << fixed << setprecision(2) << '$' << stoll(w.substr(1)) * dis;
                ans += s.str();
            } else {
                ans += w;
            }
        }
        return ans;
    }
};

2024-06-19

题目传送门：2713. 矩阵中严格递增的单元格数 - 力扣（LeetCode）

此题好像在蓝桥杯上遇见过

最后实现代码如下：

1

2024-06-20

题目传送门：2748. 美丽下标对的数目 - 力扣（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 countBeautifulPairs(vector<int>& nums) {
        int n = nums.size();
        function<int(int, int)> gcd = [&](int a,int b){
            if (a%b==0) return b;
            return gcd(b, a%b);
        };
        function<int(int)> rnum = [&](int x){
            while(x>9) x /= 10;
            return x;
        };
        int ans = 0;
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                int maxx = max(rnum(nums[i]), nums[j]%10);
                int minn = min(rnum(nums[i]), nums[j]%10);
                if (gcd(maxx, minn)==1) ans++;
            }
        }
        return ans;
    }
};

2024-06-21

题目传送门：LCP 61. 气温变化趋势 - 力扣（LeetCode）

签到题，遍历即可。

最后实现代码如下：

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

2024-06-22

题目传送门：2663. 字典序最小的美丽字符串 - 力扣（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
class Solution {  
public:  
    string smallestBeautifulString(string s, int k) {  
        int n = s.size();  
        function<char(int)> judge = [&](int loc){  
            for (int i=s[loc]-'a'+2;i<=k;++i) {  
                if (loc==0) return char(i-1+'a');  
                if (loc==1&&s[loc-1]!=i+'a'-1) return char(i-1+'a');  
                if (loc>=2&&s[loc-1]!=i+'a'-1&&s[loc-2]!=i+'a'-1) return char(i-1+'a');  
            }            return '!';  
        };        string ans = "";  
        for (int i=n-1;i>=0;--i) {  
            char nw = judge(i);  
            if (nw != '!') {  
                string tmp = s.substr(0, i);  
                tmp += nw;  
                bool flag=true;  
                for(int j=i+1; j<n; ++j){  
                    bool nw_flag = false;  
                    for(int c=1;c<=k;++c){  
                        if (c==tmp[j-1]-'a'+1) continue;  
                        if(j-2>=0&&tmp[j-2]-'a'+1==c) continue;  
                        tmp += char(c-1+'a');  
                        nw_flag = true;  
                        break;  
                    }                    if (!nw_flag) {flag=false;break;}  
                }                if (flag) return tmp;  
            }        }        return "";  
    }};

2024-06-23

题目传送门：520. 检测大写字母 - 力扣（LeetCode）

一行代码解决战斗！

最后实现代码如下：

1
2
3
4
5
6
class Solution {
public:
    bool detectCapitalUse(string word) {
        return (all_of(word.begin(), word.end(), [](unsigned char c) {return islower(c);})) || (all_of(word.begin(), word.end(), [](unsigned char c) {return isupper(c);})) || (isupper(word[0]) && all_of(word.begin()+1, word.end(), [](unsigned char c) {return islower(c);}));
    }
};

2024-06-24

题目传送门：503. 下一个更大元素 II - 力扣（LeetCode）

单调栈，注意，由于队列首位相接，可以通过将队列复制一份，使其长度加倍。这样对于前一份队列便可以和自己之前的元素进行比较，近似实现了队列首位相接的功能。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int max_ele = *max_element(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> ans(n,-1);
        vector<pair<int,int>> stk;
        for(int i=0;i<n*2-1;++i){
            int nw = nums[i%n];
            int tmp_n = stk.size();
            while (!stk.empty() && stk[tmp_n-1].second < nw && ans[stk[tmp_n-1].first] == -1){
                ans[stk[tmp_n-1].first] = nw;
                stk.pop_back(); tmp_n--;
            }
            if (i < n && max_ele!=nums[i]) stk.emplace_back(i, nums[i]);
        }
        return ans;
    }
};

2024-06-25

题目传送门：2732. 找到矩阵中的好子集 - 力扣（LeetCode）

可以通过严格证明得知，在n<=5的情况下，只需要考虑1，2行的情况。

严格证明过程见：严格证明+三种计算方法（Python/Java/C++/Go）

得知上述性质后，哈希表解决即可。（因为最多五列，所以哈希表也不大）

最后实现代码如下：

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
class Solution {
public:
    vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
        vector<int> ans;
        unordered_map<int, int> mp;
        int m = grid.size();
        int n = grid[0].size();
        for(int i=0; i<m; ++i){
            int st = 0;
            for(int j=0; j<n; ++j){
                st |= (grid[i][j] << j);
            }
            mp[st] = i;
        }

        if (mp.count(0)) {
            ans.push_back(mp[0]);
            return ans;
        }

        for (auto [x, i]: mp) {
            for (auto [y, j]: mp) {
                if (!(x & y)) {
                    return {min(i, j), max(i, j)};
                }
            }
        }
        return ans;
    }
};

2024-06-26

题目传送门：2741. 特别的排列 - 力扣（LeetCode）

状压DP板子题，需要注意的是vector不要一上来就开的很大，会报错😭。

最后实现代码如下：

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:
    int specialPerm(vector<int>& nums) {
        // sort(nums.begin(), nums.end());
        int n = nums.size();
        int maxx = pow(2, n);
        vector<vector<int>> dp(maxx,vector<int>(n,0));
        
        
        int MOD = 1e9 + 7;
        for(int i=0;i<n;++i) dp[1<<i][i] = 1;
        for(int i=1;i<maxx;++i){
            for(int j=0;j<n;++j){
                if (!(i>>j)&1) continue;
                for(int k=0;k<n;++k){
                    if (j==k) continue;
                    if(!(1&(i>>k))) continue;
                    if (max(nums[j],nums[k]) % min(nums[j],nums[k])) continue;
                    int ii = i ^ (1<<j);
                    dp[i][j] = (dp[i][j] + dp[ii][k]) % MOD;
    
                }
            }
        }
        int ans = 0;
        for(int i=0;i<n;++i) ans = (ans + dp[maxx-1][i]) % MOD;
        return ans;
    }
};

2024-06-27

题目传送门：2734. 执行子串操作后的字典序最小字符串 - 力扣（LeetCode）

贪心，从左到右遍历，如果不是a就让他变小，这样连续的改一串就可以。需要注意的特殊情况是，如果字符串为全a，此时将最后一个字符改为z即可。这种特殊情况特判一下就好。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    string smallestString(string s) {
        int n = s.size();
        int cnt = 0;
        bool flag = false;
        while(cnt<n&&s[cnt] == 'a') cnt++;
        while(cnt<n&&s[cnt]!='a') flag=true,s[cnt]=s[cnt]-1,cnt++;
        if (!flag) s[n-1] = 'z';
        return s;
    }
};

2024-06-28

题目传送门：2742. 给墙壁刷油漆 - 力扣（LeetCode）

此题为01背包问题的至少变形， 详细讲解见OI-Knowledge背包问题部分最后的变形3章节。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int paintWalls(vector<int> &cost, vector<int> &time) {
        int n = cost.size();
        vector<int> dp(n + 1, INT_MAX / 2); // 防止加法溢出
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            int nw_cost = cost[i], nw_time = time[i]+1;
            for(int j=n;j>=0;--j){
                dp[j] = min(dp[j], dp[max(0, j-nw_time)]+nw_cost);
            }
        }
        return dp[n];
    }
};

2024-06-29

题目传送门：2710. 移除字符串中的尾随零 - 力扣（LeetCode）

C++ string中substr练习题。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string removeTrailingZeros(string num) {
        int n = num.size();
        int i = 0;
        while (num[n-1-i]=='0') {
            i++;
        }
        return num.substr(0,n-i);
    }
};

2024-06-30

题目传送门：494. 目标和 - 力扣（LeetCode）

01背包变体，题目要求在每个数前面添加+或者-号，其实可以看作是初始都是减号，选出一些数变为+号，这就是01背包的思想了。只不过最后要求不像01背包是至多而是恰好需要注意。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        if (target < 0) target = -target;
        int sum_nums = 0;
        for(auto num : nums) sum_nums += num;
        if ((sum_nums+target)%2) return 0;
        int nw_target = (sum_nums+target)/2;
        vector<int> dp(nw_target+1, 0);
        dp[0] = 1;
        for(auto num : nums){
            for(int i=nw_target;i>=0;--i){
                if(i>=num) dp[i] += dp[i-num];
            }
        }
        return dp[nw_target];
    }
};

2024年6月勋章

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