Posted on | In , |
Words count in article: 546 | Reading time ≈ 2

1534. 统计好三元组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        int nCount = 0,nSize = arr.size();

        for(int i  = 0; i < nSize - 2;++i){
            for(int j =i+1;j<nSize -1 ;++j){
                for(int k = j+1;k<nSize;k++){
                    if(abs(arr[i] - arr[j])<=a && abs(arr[j] - arr[k])<=b && abs(arr[i]-arr[k])<=c){
                        nCount ++;
                    }
                }
            }
        }
        return nCount;
    }
};

1535. 找出数组游戏的赢家

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        int n = arr.size(), i = 1, ans = arr[0], t=k;
        while(t-- && i < n)//模拟k次
        {
            if(ans < arr[i])//碰见比我大的
            {
                ans = arr[i];//更改答案
                t = k-1;//该大数，还要模拟k-1次
            }
            i++;
        }
        return ans;
    }
};

1536. 排布二进制网格的最少交换次数

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 minSwaps(vector<vector<int>>& grid) {
        int n = grid.size(); //网格规模
        vector<int> a; //记录每一行后缀0个数的数组
        for(int i = 0; i < n; i++)
        {
            int count = 0;
            for(int j = n - 1; j >= 0; j--)
            {
                if(grid[i][j] == 0) count++; //数每一行的后缀0
                else break;
            }
            a.push_back(count); 
        }
        int count = 0; //交换次数
        for(int i = 0; i < n - 1; i++)
        {
            if(a[i] >= n - i - 1) continue;//满足条件，该行直接跳过
            else{//不满足条件
                int j = i; //用新参数遍历找满足条件的后缀0
                for(; j < n; j++)
                {
                    if(a[j] >= n - i - 1) break;
                }
                if(j == n) return -1; //找不到，直接返回-1
                for(; j > i; j--) //找到了最先满足条件的后缀0个数 
                {
                    swap(a[j], a[j - 1]); //每一行交换上去
                    count++; //记录交换次数
                }
            }
        }
        return count;
    }
};

1537. 最大得分

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
class Solution {
public:
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        long sum1 = 0, sum2 = 0;
        long res = 0;
        int i = 0, j = 0;
        while(i < nums1.size() && j < nums2.size()){
            if(nums1[i] == nums2[j]){
                res += (max(sum1, sum2) + nums1[i]);
                sum1 = 0;
                sum2 = 0;
                i++;
                j++;
            }
            else if(nums1[i] < nums2[j]){
                sum1 += nums1[i];
                i++;                
            }
            else{
                sum2 += nums2[j];
                j++;
            }            
        }
        while(i < nums1.size()){
            sum1 += nums1[i];
            i++;
        }
        while(j < nums2.size()){
            sum2 += nums2[j];
            j++;
        }
        res += max(sum1, sum2);
        return res % ((int)pow(10, 9) + 7 );
    }
};

Posted on | In , |
Words count in article: 480 | Reading time ≈ 2

重新排列字符串

1
2
3
4
5
6
7
8
9
class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        string res = s;
        for(int i = 0; i < indices.size(); ++i)
            res[indices[i]] = s[i];
        return res;
    }
};

灯泡开关 IV

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minFlips(string target) {
        int flag = true;
        int res = 0;
        for(int i=0; i<target.size(); i++) {
            if(flag && target[i] == '1') {
                flag = false;
                res++;
            } else if(flag == false && target[i] == '0') {
                flag = true;
                res++;
            }
        }
        return res;
    }
};

好叶子节点对的数量

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans;
    vector<int> dfs(TreeNode* root, int distance) {
        if (root->left == nullptr&&root->right == nullptr)
            return{ 1 };
        vector<int>v1, v2,v3;
        if (root->left)
            v1 = dfs(root->left, distance);
        if (root->right)
            v2 = dfs(root->right, distance);
        for (int i : v1)
            for (int j : v2)
                if (i + j <= distance)
                    ans++;
        for (int i : v1)
            v3.push_back(i + 1);
        for (int j : v2)
            v3.push_back(j + 1);
        return v3;
    }
    int countPairs(TreeNode* root, int distance) {
        ans = 0;
        dfs(root, distance);
        return ans;
    }
};

压缩字符串 II

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:
    int dp[105][105];
    int n;
    int dfs(int st, int k, string& s) {
        if (st == n) return 0;
        int& r = dp[st][k];
        if (r != -1) return r;
        if (k) r = dfs(st + 1, k - 1, s); // case1: 删除当前位置字符

        // case2: 保留当前字符，并枚举该字符连续的长度（所以遇到不同字符必须删除，才能维护其连续性）
        int c = 1; // 记录当前字符的连续个数
        for (int i = st + 1; i <= n; i++) {
            int t = dfs(i, k, s) + 1 + (c >= 100 ? 3 : c >= 10 ? 2 : c > 1 ? 1 : 0);
            if (r == -1 || r > t) r = t;
            if (i == n) break;
            if (s[i] == s[st]) c++; // 相同, 个数加1
            else if (k-- <= 0) break; // 否则删除不同的字符
        }
        return r;
    }
    int getLengthOfOptimalCompression(string s, int k) {
        n = s.size();
        memset(dp, -1, sizeof dp);
        dfs(0, k, s);
        return dp[0][k];
    }
};

Posted on | In , |
Words count in article: 295 | Reading time ≈ 1

在区间范围内统计奇数数目

1
2
3
4
5
6
7
class Solution {
public:
    int countOdds(int low, int high) {
        int res=(high-low)/2;
        return low%2||high%2?res+1: res;
    }
};

和为奇数的子数组数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numOfSubarrays(vector<int>& arr) 
    {
        int odd = 0, even = 1;  
        long long res = 0;
        int sum = 0;
        for (int num: arr)
        {
            sum += num;
            res += (sum % 2 == 0? odd: even);
            if (sum % 2 == 0)   even++;
            else                odd++;
        }
        return res % 1000000007;
    }
};

字符串的好分割数目

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:
    int numSplits(string s) {
        int ans = 0;

        vector<int> l_dic(26, 0);
        vector<int> r_dic(26, 0);
        int left = 0;
        int right = 0;

        for (int i = 0; i < s.size(); i++) {
            int c = s[i] - 'a';
            right += (r_dic[c] == 0);
            r_dic[c]++;
        }

        for (int i = 0; i < s.size() - 1; i++) {
            int c = s[i] - 'a';
            left += (l_dic[c] == 0);
            l_dic[c]++;
            r_dic[c]--;
            right -= (r_dic[c] == 0);
            ans += (left == right);
        }

        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
class Solution {
public:
    int minNumberOperations(vector<int>& target) {
        target.push_back(0);

        int ans = 0;
        stack<int> st;
        st.push(0);

        for (int i = 0; i < target.size(); i++) {
            while (st.top() > target[i]) {
                int t = st.top();
                st.pop();
                ans += t - max(st.top(), target[i]);
            }
            if (st.top() == target[i]) continue;

            if (st.top() < target[i]) {
                st.push(target[i]);
            }
        }
        return ans;
    }
};

Posted on | In , |
Words count in article: 589 | Reading time ≈ 3

换酒问题

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int numWaterBottles(int a, int b) {
        int res = a;
        while (a >= b)
        {
            res += a/b;
            a = a/b+a%b;
        }
        return res;
    }
};

子树中标签相同的节点数

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<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        vector<vector<int>> v(n);
        for (auto &e : edges)
        {
            int x = e[0], y = e[1];
            v[x].push_back(y);
            v[y].push_back(x);
        }
        vector<vector<int>> s(n, vector<int>(26));
        
        vector<int> res(n);
        function<void(int,int)> dfs = [&](int x, int pre)
        {
            s[x][labels[x]-'a'] ++;
            for (auto y : v[x])
            {
                if (y == pre) continue;
                dfs(y, x);
                for (int i = 0; i < 26; ++i) s[x][i] += s[y][i];
            }
            res[x] = s[x][labels[x]-'a'];
        };
        
        dfs(0, -1);
        return res;
    }
};

最多的不重叠子字符串

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
public:
    using pii = pair<int, int>;
    vector<string> maxNumOfSubstrings(string s) {
        int n = s.size();
        const int INF = 1000000000;
        
        vector<vector<int>> pos(26);
        
        vector<int> L(26, INF), R(26, -INF);
        vector<int> cnt(26);
        for (int i = 0; i < n; ++i)
        {
            pos[s[i]-'a'].push_back(i);
            L[s[i]-'a'] = min(L[s[i]-'a'], i);
            R[s[i]-'a'] = max(R[s[i]-'a'], i);
            cnt[s[i]-'a'] ++;
        }
        
        vector<pii> H;
        for (int i = 0; i < 26; ++i)
        {
            if (cnt[i] == 0) continue;
            int x = L[i], y = R[i], tot = cnt[i];
            vector<int> u(26);
            u[i] = 1;
            while (y-x+1 != tot)
            {
                for (int j = 0; j < 26; ++j)
                {
                    if (!u[j] && cnt[j] != 0)
                    {
                        auto it = lower_bound(pos[j].begin(), pos[j].end(), x);
                        if (it != pos[j].end() && *it <= y)
                        {
                            u[j] = 1;
                            tot += cnt[j];
                            x = min(x, L[j]);
                            y = max(y, R[j]);
                        }
                    }
                }
            }
            H.push_back({x, y});
        }
        
        sort(H.begin(), H.end(), [](const pii &a, const pii &b)
             {
                 return abs(a.first-a.second) < abs(b.first-b.second);
             });
        
        vector<string> res;
        vector<int> ok(H.size());
        for (int i = 0; i < H.size(); ++i)
        {
            if (ok[i]) continue;
            auto [x, y] = H[i];
            for (int j = 0; j < H.size(); ++j)
            {
                auto [L, R] = H[j];
                if (L <= x && y <= R) ok[j] = 1;
            }
            res.push_back(s.substr(x, y-x+1));
        }
        return res;
    }
};

找到最接近目标值的函数值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int closestToTarget(vector<int>& arr, int target) {
        int ans = abs(arr[0] - target);
        vector<int> valid = {arr[0]};
        for (int num: arr) {
            vector<int> validNew = {num};
            ans = min(ans, abs(num - target));
            for (int prev: valid) {
                validNew.push_back(prev & num);
                ans = min(ans, abs((prev & num) - target));
            }
            validNew.erase(unique(validNew.begin(), validNew.end()), validNew.end());
            valid = validNew;
        }
        return ans;
    }
};

Posted on | In , |
Words count in article: 501 | Reading time ≈ 3

好数对的数目

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

仅含 1 的子串数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
    int numSub(string s) {
        int n = s.size();
        ll curr = 0, ans = 0;
        for (char c : s) {
            if (c == '1')
                curr++;
            else {
                ans += curr * (curr + 1) / 2;
                ans %= MOD;
                curr = 0;
            }
        }
        ans += curr * (curr + 1) / 2;
        ans %= MOD;
        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
const double eps = 1e-8;

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<double> prob(n);
        prob[start] = 1;
        vector<vector<pair<int, double>>> adj(n);
        for (int i = 0; i < edges.size(); ++i) {
            int u = edges[i][0], v = edges[i][1];
            double p = succProb[i];
            adj[u].emplace_back(v, p);
            adj[v].emplace_back(u, p);
        }
        priority_queue<pair<double, int>> pq;
        vector<bool> vis(n);
        pq.push({1, start});
        while (!pq.empty()) {
            auto top = pq.top();
            double p = top.first;
            int u = top.second;
            pq.pop();
            if (vis[u])
                continue;
            vis[u] = true;
            if (p < eps)
                continue;
            for (auto edge : adj[u]) {
                int v = edge.first;
                double now = p * edge.second;
                if (prob[v] < now) {
                    prob[v] = now;
                    pq.push({prob[v], v});
                }
            }
        }
        
        return prob[end]; 
    }
};

服务中心的最佳位置

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
const double eps = 1e-8;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

double calc(double ax, double ay, double bx, double by) {
    double dx = bx - ax, dy = by - ay;
    return sqrt(dx * dx + dy * dy);
}

class Solution {
public:
    double getMinDistSum(vector<vector<int>>& positions) {
        int n = positions.size();
        double x = 0, y = 0;
        for (auto v : positions) {
            x += v[0];
            y += v[1];
        }
        x /= n, y /= n;
        auto dist = [&](double cx, double cy) {
            double ans = 0;
            for (auto v : positions) 
                ans += calc(cx, cy, v[0], v[1]);
            return ans;
        };
        double d = dist(x, y);
        double step = 100.0;
        int done = 0;
        while (step > eps) {
            done = 0;
            for (int i = 0; i < 4; ++i) {
                double nx = (double)x + step * dx[i];
                double ny = (double)y + step * dy[i];
                double t = dist(nx, ny);
                if (t < d) {
                    d = t;
                    x = nx;
                    y = ny;
                    done = 1;
                    break;
                }
            }
            if (!done)
                step /= 2;
        }
        
        return d;
    }
};

Posted on | In , |
Words count in article: 436 | Reading time ≈ 2

转变日期格式

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
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
    string ans;
public:
    string reformatDate(string date) {
        int n=date.size(),i;
        ans="";
        for(i=n-4;i<n;i++)ans+=date[i];
        ans+='-';
        for(i=0;date[i]!=' ';i++);
        i++;
        if(date[i]=='J')
        {
            ans+='0';
            if(date[i+1]=='a')ans+='1';
            else if(date[i+2]=='n')ans+='6';
            else ans+='7';
        }
        else if(date[i]=='F')
        {
            ans+='0';
            ans+='2';
        }
        else if(date[i]=='M')
        {
            ans+='0';
            if(date[i+2]=='r')ans+='3';
            else ans+='5';
        }
        else if(date[i]=='A')
        {
            ans+='0';
            if(date[i+1]=='p')ans+='4';
            else ans+='8';
        }
        else if(date[i]=='S')
        {
            ans+='0';
            ans+='9';
        }
        else if(date[i]=='O')
        {
            ans+='1';
            ans+='0';
        }
        else if(date[i]=='N')
        {
            ans+='1';
            ans+='1';
        }
        else if(date[i]=='D')
        {
            ans+='1';
            ans+='2';
        }
        ans+='-';
        if(date[1]>='0'&&date[1]<='9')for(i=0;i<2;i++)ans+=date[i];
        else
        {
            ans+='0';
            ans+=date[0];
        }
        return ans;
    }
};

子数组和排序后的区间和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int s[1005],a[1000005];
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        int i,j,m=0,ans=0;
        for(i=0;i<n;i++)s[i+1]=s[i]+nums[i];
        for(i=1;i<=n;i++)for(j=i;j<=n;j++)a[++m]=s[j]-s[i-1];
        sort(a+1,a+m+1);
        for(i=left;i<=right;i++)
        {
            ans+=a[i];
            if(ans>=1000000007)ans-=1000000007;
        }
        return ans;
    }
};

三次操作后最大值与最小值的最小差

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

石子游戏 IV

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int f[100005];
    bool work(int n)
    {
        if(~f[n])return f[n];
        if(!n)return 0;
        for(int i=1;i*i<=n;i++)if(!work(n-i*i))return f[n]=1;
        return f[n]=0;
    }
public:
    bool winnerSquareGame(int n) {
        memset(f,-1,sizeof(f));
        return work(n);
    }
};

Posted on | In , |
Words count in article: 420 | Reading time ≈ 2

5452. 判断能否形成等差数列

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        if(arr.size() <= 2) return true;
        sort(arr.begin(), arr.end());
        int cur = arr[1]-arr[0];
        for(int i=1; i<arr.size()-1; i++) {
            if(arr[i+1]-arr[i] != cur) return false;
        }
        return true;
    }
};

5453. 所有蚂蚁掉下来前的最后一刻

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int curmax = 0;
        for(auto& l: left) {
            curmax = max(curmax, l);
        }
        for(auto& r: right) {
            curmax = max(curmax, n-r);
        }
        return curmax;
    }
};

5454. 统计全 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
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        vector<vector<int> > left(n,vector<int>(m));
        int now = 0;
        for(int i=0;i<n;i++){
            now = 0;
            for(int j=0;j<m;j++){
                if(mat[i][j] == 1) now ++;
                else now = 0;
                left[i][j] = now;
            }
        }
        int ans = 0,minx;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                minx = 0x3f3f3f3f;
                for(int k=i;k>=0;k--){
                    minx = min(left[k][j],minx);
                    ans += minx;
                }
            }
        }
        return ans;
    }
};

5455. 最多 K 次交换相邻数位后得到的最小整数

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:
    string minInteger(string num, int k) {
        if (k == 0)
            return num;
        //special return
        if (num.size() * num.size() < k) {
            sort(num.begin(), num.end());
            return num;
        }
        for (int i = 0; i < num.size(); i++) {
            char tem = num[i];
            int flag = 0;
            int index;
            //find minChar
            for (int j = i + 1; j < i + 1 + k && j < num.size(); j++) {
                if (num[j] < tem) {
                    //update
                    tem = num[j];
                    flag = 1;
                    index = j;
                }
            }
            if (flag) {
                //loop swap update
                for (int t = index; t >= i + 1; t--) {
                    char temp = num[t];
                    num[t] = num[t - 1];
                    num[t - 1] = temp;
                }
                flag = 0;
                k = k - (index - i);
            }
            //return
            if (k == 0)
                break;
        }
        return num;
    }
};

Posted on | In , |
Words count in article: 443 | Reading time ≈ 2

5448. 判断路径是否相交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isPathCrossing(string path) {
        int x = 0, y = 0;
        map<pair<int, int>, int> mp;
        mp[{0,0}] = 1;
        for(auto& c: path) {
            if(c == 'N') y++;
            else if(c == 'S') y--;
            else if(c == 'E') x++;
            else if(c == 'W') x--;
            if(mp[{x, y}]) return true;
            else mp[{x,y}] = 1;
        }
        return false;
    }
};

5449. 检查数组对是否可以被 k 整除

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 canArrange(vector<int>& arr, int k) {
        map<int, int> mp;
        for(auto i: arr) {
            int m = i % k;
            if(m < 0) m += k;
            mp[m] ++;
        }
        if(mp[0] % 2 != 0) return false;
        if(k % 2 == 0) {
            for(int i=1; i<k/2; i++) {
                int j = k-i;
                if(mp[i] != mp[j]) return false;
            }
            if(mp[k/2] % 2 != 0) return false;
        } else {
            for(int i=1; i<=k/2; i++) {
                int j = k-i;
                if(mp[i] != mp[j]) return false;
            }
        }
        return true;
    }
};

5450. 满足条件的子序列数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        int maxn = 1e9+7;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int res = 0, pw[n];
        pw[0] = 1;
        for(int i=1; i<n; i++) pw[i] = (pw[i-1]*2) % maxn;
        for(int i=0, j=n-1; i<n; i++) {
            while(i<=j && nums[i]+nums[j] > target) j--;
            if(i > j) break;
            res = (res + pw[j-i]) % maxn;
        }
        return res;
    }
};

5451. 满足不等式的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef pair<int, int> PII;
class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        deque<PII> dq;
        dq.push_back({points[0][0], points[0][1] - points[0][0]});
        int ans = -2e9;
        for(int i = 1; i < points.size(); i ++) {
            
            while (dq.size() && points[i][0] - dq.front().first > k) dq.pop_front();
            if (dq.size()) ans = max(ans, dq.front().second + points[i][0] + points[i][1]);
            while (dq.size() && dq.back().second <= points[i][1] - points[i][0]) dq.pop_back();
            dq.push_back({points[i][0], points[i][1] - points[i][0]});
        }
        return ans;
    }
};

Posted on | In , |
Words count in article: 454 | Reading time ≈ 2

5432. 去掉最低工资和最高工资后的工资平均值

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    double average(vector<int>& salary) {
        double res = 0;
        int curmax = salary[0], curmin = salary[0];
        for(auto s: salary) {
            curmax = max(curmax, s);
            curmin = min(curmin, s);
            res += s;
        }
        return (res-curmax-curmin) / ((salary.size()-2)*1.0);
    }
};

5433. n 的第 k 个因子

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int kthFactor(int n, int k) {
        int c = 0;
        for(int i=1; i<=n; i++) {
            if(n % i == 0) {
                c++;
                if(c == k) return i;
            }
        }
        return -1;
    }
};

5434. 删掉一个元素以后全为 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
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n), right(n);
        int cur = 0;
        for(int i=0; i<n; i++) {
            if(nums[i] == 1) cur++;
            left[i] = cur;
            if(nums[i] == 0) cur = 0;
        }
        cur = 0;
        for(int i=n-1; i>=1; i--) {
            if(nums[i] == 1) cur++;
            if(nums[i] == 0) cur = 0;
            right[i-1] = cur;
        }
        int m = 0;
        for(int i=0; i<n; i++) {
            m = max(m, left[i] + right[i]);
        }
        if(m == n) return m-1;
        return m;
    }
};

5435. 并行课程 II

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
class Solution {
public:
    int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {
        vector<int> indegree(n+1, 0);
        vector<int> outdegree(n+1, 0);
        for(auto& p: dependencies) {
            indegree[p[1]]++;
            outdegree[p[0]]++;
        }
        queue<int> q;
        int res = 0;
        for(int i=1; i<=n; i++) {
            if(indegree[i] == 0) {
                q.push(i);
            }
        }
        while(!q.empty()) {
            int size = q.size();
            res ++;
            vector<int> f;
            for(int i=0; i<size; i++) {
                int c = q.front(); q.pop();
                f.push_back(c);
            }
            sort(f.begin(), f.end(), [&](int a, int b) {return outdegree[a] > outdegree[b];});
            int z = min(k, size);
            for(int i=0; i<z; i++) {
                int c = f[i];
                for(int j=0; j<dependencies.size(); j++) {
                    if(c == dependencies[j][0]) {
                        indegree[dependencies[j][1]]--;
                        if(indegree[dependencies[j][1]] == 0) q.push(dependencies[j][1]);
                    }
                }
            }
            if(k < size) {
                for(int i=k; i<size; i++) {
                    q.push(f[i]);
                }
            }
        }
        return res;
    }
};

Posted on | In , |
Words count in article: 656 | Reading time ≈ 3

1486. 数组异或操作

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int xorOperation(int n, int start) {
        int res = 0;
        for(int i=0; i<n; i++) {
            res ^= start+2*i;
        }
        return res;
    }
};

1487. 保证文件名唯一

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<string> getFolderNames(vector<string>& names) {
        unordered_set<string> past;
        unordered_map<string, int> next;
        for(string &i: names) {
            if(past.find(i) == past.end()) {
                past.insert(i);
                next[i] = 1;
            } else {
                int num = next[i];
                int original_size = i.size();
                string s = i;
                while(1) {
                    while(s.size() > original_size) s.pop_back();
                    s += '(' + to_string(num) + ')';
                    ++num;
                    if(past.find(s) == past.end()) {
                        next[i] = num;
                        next[s] = 1;
                        past.insert(s);
                        i = s;
                        break;
                    }
                }
            }
        }
        return names;
    }
};

1488. 避免洪水泛滥

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:
    vector<int> avoidFlood(vector<int>& rains) {
        int rains_size = rains.size();
        vector<int> ans(rains_size, 1);
        unordered_map<int, int> last_rain;
        set<int> sun;
        for(int i=0; i<rains_size; i++) {
            int ii = rains[i];
            if(ii == 0) {
                sun.insert(i);
                continue;
            }
            if(last_rain.find(ii) != last_rain.end()) {
                auto p = sun.lower_bound(last_rain[ii]);
                if(p == sun.end()) return {};
                ans[*p] = ii;
                sun.erase(p);
            }
            last_rain[ii] = i;
            ans[i] = -1;
        }   
        return ans;
    }
};

1489. 找到最小生成树里的关键边和伪关键边

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
public:  
    int p[110];
    
    int find(int a) {
        if (a != p[a]) p[a] = find(p[a]);
        return p[a];
    }

    int work1(int n, vector<vector<int>>& edges, int k) { // 不选第k条边的最小生成树的权重
        for (int i = 0; i < n; i ++ ) p[i] = i;
        int cost = 0, cnt = 0;
        for (auto& e:edges) {
            if (e[3] == k) continue;  //  如果是第k条边，则跳过
            int f1 = find(e[1]), f2 = find(e[2]);
            if (f1 != f2) {
                cost += e[0];
                cnt ++;
                if (cnt == n - 1) break;
                p[f1] = f2;
            }
        }
        if (cnt == n - 1) return cost;
        else return INT_MAX;
    }
    
    int work2(int n, vector<vector<int>>& edges, int k) { // 一定选第k条边的最小生成树的权重
        for (int i = 0; i < n; i ++ ) p[i] = i;
        int cost = 0, cnt = 0;
        
        for (auto& e : edges) {  // 先向第k条边加入到集合中
            if (e[3] == k) {
                cost += e[0];
                cnt ++;
                p[e[1]] = e[2];
                break;
            }
        }
        
        for (auto& e: edges) {
            int f1 = find(e[1]), f2 = find(e[2]);
            if (f1 != f2) {
                cost += e[0];
                cnt ++;
                if (cnt == n - 1) break;
                p[f1] = f2;
            }
        }
        if (cnt == n - 1) return cost;
        else return INT_MAX;
    }
    
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {        
        int m = edges.size();
        for (int i = 0; i < m; i ++ ) {
            auto& e = edges[i];
            swap(e[0], e[2]);
            e.push_back(i);
        }
        sort(edges.begin(), edges.end());
        int min_cost = work1(n, edges, -1);   // 求出最小生成树权重
        vector<vector<int>> ans(2);
        for (int i = 0; i < m; i ++ ) {
            if (work1(n, edges, i) > min_cost) ans[0].push_back(i);  // 判断是否为关键边
            else if (work2(n, edges, i) == min_cost) ans[1].push_back(i);  // 判断是否为伪关键边
        } 
        return ans;
        
    }
};