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

5436. 一维数组的动态和

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        vector<int> res = nums;
        for(int i=1; i<res.size(); i++)
            res[i] += res[i-1];
        return res;
    }
};

5437. 不同整数的最少数目

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 findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        map<int, int> mp;
        for(auto i: arr) mp[i]++;
        vector<int> cot;
        for(auto i: mp) {
            cot.push_back(i.second);
        }
        sort(cot.begin(), cot.end());
        int i=0;
        for(i=0; i<cot.size(); i++) {
            if(k >= cot[i]) {
                k -= cot[i];
            } else {
                break;
            }
        }
        return cot.size()-i;
        
    }
};

5438. 制作 m 束花所需的最少天数

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
typedef long long ll;

class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        int n = bloomDay.size();
        if (n / k < m)
            return -1;
        int l = 1, r = 1e9;
        auto check = [&](int x) {
            vector<bool> flower(n);
            for (int i = 0; i < n; ++i)
                if (bloomDay[i] <= x)
                    flower[i] = true;
            int bunch = 0, curr = 0;
            for (int i = 0; i < n; ++i) {
                if (flower[i])
                    curr++;
                else {
                    bunch += curr / k;
                    curr = 0;
                }
            }
            bunch += curr / k;
            return bunch;
        };
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid) < m)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return l;
    }
};

5188. 树节点的第 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
class TreeAncestor {
public:
    vector<int> dep;
    vector<int> f[20];
    vector<vector<int>> G;
    void DFS(int u){
        for(int i = 1; i < 20; i += 1) f[i][u] = f[i - 1][f[i - 1][u]];
        for(int v : G[u]){
            dep[v] = dep[u] + 1;
            f[0][v] = u;
            DFS(v);
        }
    }
    TreeAncestor(int n, vector<int>& parent) {
        G.resize(n);
        dep.resize(n);
        for(int i = 0; i < 20; i += 1) f[i].resize(n);
        for(int i = 1; i < n; i += 1) G[parent[i]].push_back(i);
        DFS(0);
    }
    
    int getKthAncestor(int node, int k) {
        if(dep[node] < k) return -1;
        for(int i = 19; ~i; i -= 1)
            if(k >= (1 << i)){
                k -= 1 << i;
                node = f[i][node];
            }
        return node;
    }
};

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor* obj = new TreeAncestor(n, parent);
 * int param_1 = obj->getKthAncestor(node,k);
 */

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

5420. 商品折扣后的最终价格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        vector<int> res;
        for(int i=0; i<prices.size(); i++) {
            int cur = prices[i];
            for(int j=i+1; j<prices.size(); j++) {
                if(prices[j] <= cur) {
                    cur -= prices[j];
                    break;
                }
            }
            res.push_back(cur);
        }
        return res;
    }
};

5422. 子矩形查询

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
class SubrectangleQueries {
public:
    vector<vector<int>> cur;
    
    SubrectangleQueries(vector<vector<int>>& rectangle) {
        cur = rectangle;
    }
    
    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for(int i=row1; i<=row2; i++) {
            for(int j=col1; j<=col2; j++) {
                cur[i][j] = newValue;
            }
        }
    }
    
    int getValue(int row, int col) {
        return cur[row][col];
    }
};

/**
 * Your SubrectangleQueries object will be instantiated and called as such:
 * SubrectangleQueries* obj = new SubrectangleQueries(rectangle);
 * obj->updateSubrectangle(row1,col1,row2,col2,newValue);
 * int param_2 = obj->getValue(row,col);
 */

5423. 找两个和为目标值且不重叠的子数组

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 {
    unordered_map<int, int> mp;
    int f[100005];
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        int sum = 0;
        mp[0] = 0;
        int n = arr.size(), ans = 0x3f3f3f3f;
        memset(f, 0x3f, sizeof(f));
        for (int i = 1; i <= n; ++i){
            sum += arr[i - 1];
            int gp = sum - target;
            f[i] = f[i - 1];
            if (mp.count(gp)){
                int pos = mp[gp];
                f[i] = min(f[i], i - pos);
                ans = min(ans, i - pos + f[pos]);
            }
            mp[sum] = i;
        }
        return ans == 0x3f3f3f3f ? -1: ans;
    }
};

5421. 安排邮筒

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 {
    long long f[105][105];
    long long dis[105][105];
public:
    int minDistance(vector<int>& houses, int k) {
        int n = houses.size();
        sort(houses.begin(), houses.end());
        for (int i = 1; i <= n; ++i){
            for (int j = i; j <= n; ++j){
                int p = (j - i) >> 1;
                int mid = i + p;
                int pos = houses[mid - 1];
                long long res = 0;
                for (int t = i; t <= j; ++t)
                    res += abs(houses[t - 1] - pos);
                dis[i][j] = res;
            }
        }
        memset(f, 0x3f, sizeof(f));
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i){
            for (int t = 1; t <= i && t <= k; ++t){
                for (int j = i - 1; j >= 0; --j)
                    f[i][t] = min(f[i][t], f[j][t - 1] + dis[j + 1][i]);
            }
        }
        return f[n][k];
    }
};

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

5428. 重新排列数组

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> res(2*n);
        int z = 0;
        for(int i=0; i<n; i++) {
            res[z++] = nums[i];
            res[z++] = nums[i+n];
        }
        return res;
    }
};

5429. 数组中的 k 个最强值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> getStrongest(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        int mid = 0, n = arr.size();
        mid = arr[(n-1)/2];
        sort(arr.begin(), arr.end(), [&](int a, int b){
            return (abs(a-mid)>abs(b-mid)) || ((abs(a-mid) == abs(b-mid)) && a > b);
        });
        vector<int> res;
        for(int i=0; i<k ;i++) {
            res.push_back(arr[i]);
        }
        return res;
    }
};

5430. 设计浏览器历史记录

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 BrowserHistory {
public:
    int curid = 0;
    vector<string> cot;
    
    BrowserHistory(string homepage) {
        cot.push_back(homepage);
    }
    
    void visit(string url) {
        while((curid+1) < cot.size()) {
            cot.pop_back();
        }
        cot.push_back(url);
        curid++;
    }
    
    string back(int steps) {
        int n = curid-steps;
        if(n < 0) {
            curid = 0;
            return cot[0];
        } else {
            curid = n;
            return cot[n];
        }     
    }
    
    string forward(int steps) {
        int n = curid + steps;
        if(n >= cot.size()) {
            curid = cot.size()-1;
            return cot[curid];
        } else {
            curid = n;
            return cot[curid];
        }
    }
};

5431. 给房子涂色 III

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
#define inf 1e8
class Solution {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        //inf排除不可能的值
        vector<vector<vector<int>>> dp(m,vector<vector<int>>(n+1,vector<int>(target+1,inf)));
        //初始化
        if(houses[0]!=0) dp[0][houses[0]][1]=0;
        else{
            for(int i=1;i<=n;i++){
                dp[0][i][1]=cost[0][i-1];
            }
        }
        
        //dp状态转移
        for(int i=1;i<m;i++){
            if(houses[i]==0){//为0，穷举j1和j2
                for(int j1=1;j1<=n;j1++){
                    for(int k=1;k<=target;k++){
                        for(int j2=1;j2<=n;j2++){
                            //在穷举j1和j2中也会有j1==j2，注意哟
                            if(j1==j2) dp[i][j1][k]=min(dp[i][j1][k],dp[i-1][j2][k]+cost[i][j1-1]);
                            else dp[i][j1][k]=min(dp[i][j1][k],dp[i-1][j2][k-1]+cost[i][j1-1]);
                        }
                    }
                }
            }else{//不为0，穷举j2
                for(int k=1;k<=target;k++){
                    for(int j2=1;j2<=n;j2++){
                        int j1=houses[i];
                        if(j1==j2) dp[i][j1][k]=min(dp[i][j1][k],dp[i-1][j2][k]);
                        else dp[i][j1][k]=min(dp[i][j1][k],dp[i-1][j2][k-1]);
                    }
                }
            }
        }
        int ans=1e8;
        for(int i=1;i<=n;i++) ans=min(ans,dp[m-1][i][target]);
        if(ans==1e8) ans=-1;
        return ans;
    }
};

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

1464. 数组中两元素的最大乘积

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = 0;
        for(int i=0; i<nums.size(); i++) {
            for(int j=i+1; j<nums.size(); j++) {
                res = max(res, (nums[i]-1) * (nums[j]-1));
            }
        }
        return res;
    }
};

1465. 切割后面积最大的蛋糕

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 maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        long long maxh = 0, maxw = 0;
        sort(horizontalCuts.begin(), horizontalCuts.end());
        sort(verticalCuts.begin(), verticalCuts.end());
        long long  pre = 0;
        long long hh = h, ww = w;
        for(long long  h: horizontalCuts) {
            maxh = max(maxh, h-pre);
            pre = h;
        }
        maxh = max(hh-pre, maxh);
        pre = 0;
        for(long long  v: verticalCuts) {
            maxw = max(v-pre, maxw);
            pre = v;
        }
        maxw = max(ww-pre, maxw);
        return (int)(maxh*maxw %1000000007);
    }
};

1466. 重新规划路线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        set<int> st;
        st.insert(0);
        int res = 0;
        for(auto c: connections) {
            if(st.count(c[1])) {
                st.insert(c[0]);
            } else {
                res ++;
                st.insert(c[1]);
            }
        }
        return res;
    }
};

1467. 两个盒子中球的颜色数相同的概率

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
class Solution {
public:
    vector<int> left, right, bas;
    int ln = 0, rn = 0;
    int alls = 0;
    double tot, ak;
    
    double fac(int a){   // 求阶乘
        double ans = 1;
        for(int i = 1; i <= a; i ++) ans *= i;
        return ans;
    }
    
    double get(vector<int>& bas){   // 求排列数
        int n = 0;
        for(auto x:bas) n += x;
        double ans = fac(n);
        for(auto x:bas) ans /= fac(x);
        return ans;
    }
    
    
    void dfs(int i){
        if(ln > alls / 2 || rn > alls / 2) return ;  // 剪枝
        if(i == left.size()){   // 叶子节点
            // for(auto x:left) cout << x << " ";
            // cout << endl;
            // for(auto x:right) cout << x <<" ";
            // cout << endl;
            int a = 0, b = 0;
            for(auto x:left){
                if(x) a ++;
            }
            for(auto x:right){
                if(x) b ++;
            }
            if(a == b)   // 两个箱子中的球的颜色种类相同
                ak += get(left) * get(right);
            return;
        }
        for(int j = 0; j <= bas[i]; j++){   // 枚举当前颜色球，左右箱子中的个数
            left[i] = j;    
            right[i] = bas[i] - j;
            ln += j;   // 记录两个箱子中球的总数，用于剪枝
            rn += bas[i] - j;
            dfs(i + 1);   // 递归调用
            ln -= j;   // 恢复现场
            rn -= bas[i] - j;
        }
    }
    
    double getProbability(vector<int>& balls) {
        
        bas = balls;
        left = vector<int>(balls.size(), 0);
        right = vector<int>(balls.size(), 0);
        tot = get(balls);   // 求分母
        for(auto x:balls) alls += x;   
        dfs(0);  // 求分子
        // cout << ak << " " << tot << endl;
        return ak / tot; 
    }
};

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

1460. 通过翻转子数组使两个数组相等

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

1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool hasAllCodes(string s, int k) {
        unordered_set<string> set;
        for(int i=0; i+k<=s.size(); i++) {
            set.insert(s.substr(i, k));
        }
        return set.size() == pow(2, k);
    }
};

1462. 课程安排 IV

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 A[110][110];
    int N;
    void union1(int x,int y)
    {
        A[x][y]=1;
        for(int i=0;i<N;++i) if(A[i][x]) A[i][y]=1;
        for(int i=0;i<N;++i) if(A[y][i]) A[x][i]=1;
    }
    vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& pre, vector<vector<int>>& que) {
        int k=pre.size();
        N=n;
        memset(A,0,sizeof A);
        for(int i=0;i<k;++i)
            union1(pre[i][0],pre[i][1]);
        vector<bool> res;
        int qn=que.size();
        for(int i=0;i<qn;++i)
        {
            res.push_back((A[que[i][0]][que[i][1]])==1);
        }
        return res;
    }
};

1463. 摘樱桃 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
class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int row=grid.size();
        int col=grid[0].size();
        grid[0][0]++;
        grid[0][col-1]++;       //这里使起步时不为0，是为了与无效状态区别开，有一些"位置对"是机器人不可能到达的
        vector<vector<vector<int>>> dp(row,vector<vector<int>>(col, vector<int>(col,0)));
        dp[0][0][col-1]=grid[0][0]+grid[0][col-1];
        for(int l=1;l<row;l++){
            for(int i=0;i<col;i++){
                for(int j=0;j<col;j++){
                    int maxnum=0;
                    for(int m=-1;m<=1;m++){
                        if(m+i<0)continue;
                        if(m+i>=col)break;
                        for(int t=-1;t<=1;t++){
                            if(t+j<0)continue;
                            if(t+j>=col)break;
                            int a=i+m;
                            int b=j+t;
                            if(dp[l-1][a][b]!=0){
                                if(i==j)maxnum=max(maxnum,dp[l-1][a][b]+grid[l][i]);
                                else
                                    maxnum=max(maxnum,dp[l-1][a][b]+grid[l][i]+grid[l][j]);
                            }
                        }
                    }
                    dp[l][i][j]=maxnum;
                }
            }
        }
        int ans=0;
        for(int i=0;i<col;i++){
            for(int j=0;j<col;j++)
                ans=max(ans,dp[row-1][i][j]);
        }
        return ans-2;
    }
};

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

5416. 检查单词是否为句中其他单词的前缀

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 check(string a, string b) {
        if(a.size() < b.size()) return false;
        for(int i=0; i<b.size(); i++) {
            if(a[i]!=b[i]) return false;
        }
        return true;
    }
    int isPrefixOfWord(string sentence, string searchWord) {
        stringstream ss;
        ss << sentence;
        vector<string> cot;
        string cur;
        while(ss >> cur) {
            cot.push_back(cur);
        }
        for(int i=0; i<cot.size(); i++) {
            if(check(cot[i], searchWord)) {
                return i+1;
            }
        }
        return -1;
    }
};

5417. 定长子串中元音的最大数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxVowels(string s, int k) {
        unordered_map<char, int> mp;
        int curmax = 0;
        for(int i=0; i<s.size(); i++) {
            mp[s[i]]++;
            if(i >= k-1) {
                curmax = max(curmax, mp['a']+mp['e']+mp['i']+mp['o']+mp['u']);
                mp[s[i-(k-1)]]--;
            }
        }
        return curmax;
    }
};

5418. 二叉树中的伪回文路径

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
/**
 * 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 = 0;
    void dfs(vector<int>& count, TreeNode* root) {
        if(root == NULL) return;
        if(root->left == NULL && root->right == NULL) {
            count[root->val]++;
            int f1 = 0;
            for(int i=1; i<=9; i++) {
                if(count[i] % 2 == 1) f1++;
            }
            if(f1 <= 1) ans++;
            count[root->val]--;
            return;
        }
        count[root->val] ++;
        dfs(count, root->left);
        dfs(count, root->right);
        count[root->val] --;
    }
    int pseudoPalindromicPaths (TreeNode* root) {
        vector<int> count(10);
        dfs(count, root);
        return ans;
    }
};

5419. 两个子序列的最大点积

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<vector<int>> f(n+1, vector<int>(m+1,-5000000));
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                f[i][j] = max({nums1[i-1]*nums2[j-1], f[i][j-1], f[i-1][j], f[i-1][j-1]+nums1[i-1]*nums2[j-1]});
            }
        }
        return f[n][m];
    }
};

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

5412. 在既定时间做作业的学生人数

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        int res = 0;
        for(int i=0; i<startTime.size(); i++) {
            if(startTime[i] <= queryTime && endTime[i] >= queryTime) res ++;
        }
        return res;
    }
};

5413. 重新排列句子中的单词

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:
    string arrangeWords(string text) {
        map<int, vector<string>> mp;
        stringstream ss;
        ss << text;
        string cur; ss >> cur;
        cur[0] = 'a' + cur[0]-'A';
        mp[cur.size()].push_back(cur);
        while(ss >> cur) {
            mp[cur.size()].push_back(cur);      
        }
        string ret = "";
        for(auto v: mp) {
            for(auto s: v.second) {
                ret += s;
                ret += ' ';
            }
        }
        ret[0] = 'A' + ret[0]-'a';
        ret.pop_back();
        return ret;
    }
};

5414. 收藏清单

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> peopleIndexes(vector<vector<string>>& a) {
        int n = a.size();
        vector<int> ret;
        for (int i = 0; i < n; ++ i)
            sort(a[i].begin(), a[i].end());
        for (int i = 0; i < n; ++ i)
        {
            int flag = 0;
            for (int j = 0; j < n; ++ j) if (j != i)
            {
                if (a[i].size() > a[j].size()) continue;
                int ok = 0;
                int l = 0;
                for (int k = 0; k < a[i].size(); ++ k)
                {
                    while (l < a[j].size() && a[i][k] != a[j][l]) ++ l;
                    if (l == a[j].size())
                    {
                        ok = 1;
                        break;
                    }
                    l ++;
                }
                
                if (ok == 0)
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0) ret.push_back(i);
        }
        return ret;
    }
};

5415. 圆形靶内的最大飞镖数量

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
class Solution {
public:
    struct Point {
        double x, y;
        Point() {}
        Point(double x, double y){
            this->x = x;
            this->y = y;
        }
    };

    double dist(Point p1,Point p2) {
        return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
    }

    Point center(Point p1,Point p2, int r) {
        Point mid = Point((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
        double a = atan2(p1.x - p2.x, p2.y - p1.y), d = sqrt(r * r - pow(dist(p1, mid),2));
        return Point(mid.x + d * cos(a), mid.y + d * sin(a));
    }
    
    int numPoints(vector<vector<int>>& po, int r) {
        vector<Point> p(po.size());
        for(int i = 0; i < po.size(); i++) {
            p[i] = Point(po[i][0], po[i][1]);
        }
		int res = 1;
		for(int i = 0; i < p.size(); i++) {
			for(int j = 0; j < p.size(); j++) {
                if(i == j) continue;
				if(dist(p[i], p[j]) > 2.0 * r) {
                    continue;
                }
				Point c = center(p[i], p[j], r);
				int cnt = 0;
				for(int k = 0; k < p.size(); k++) {
					if(dist(c, p[k]) < 1.0 * r + 0.000001) {
                        cnt++;
                    }
                }
				res = max(res, cnt);
			}
		}
		return res;
    }
};

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

5396. 连续字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxPower(string s) {
        if(s.size() == 0) return 0;
        char cur = s[0];
        int res = 1;
        int c = 1;
        for(int i=1; i<s.size(); i++) {
            if(s[i] == s[i-1]) c ++;
            else {
                cur = s[i]; c = 1;
            }
            res = max(res, c);
        }
        return res;
    }
};

5397. 最简分数

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 gcd(int a, int b) {
        if(b == 0) return a;
	    return gcd(b, a % b);
    }
    vector<string> simplifiedFractions(int n) {
        vector<string> res;
        
        for(int i=2; i<=n; i++) {
            for(int j=1; j<i; j++) {
                if(gcd(i, j) == 1) {
                    string str = to_string(j) + "/" + to_string(i);
                    res.push_back(str);
                }
            }
        }
        
        return res;
    }
};

5398. 统计二叉树中好节点的数目

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
/**
 * 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 = 0;
    void dfs(TreeNode* root, int curmax) {
        if(root == NULL) return;
        if(root->val >= curmax) ans++;
        curmax = max(curmax, root->val);
        dfs(root->left, curmax);
        dfs(root->right, curmax);
    }
    int goodNodes(TreeNode* root) {
        dfs(root, INT_MIN);
        return ans;
    }
};

5399. 数位成本和为目标值的最大数字

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:
    string null="null";
    vector<int>v;
    map<int,string>m;
    bool cmp(string s1,string s2){
        if(s1.size()==s2.size())return s1>s2;
        return s1.size()>s2.size();
    }
    string dfs(int target){
        if(target==0)return ""; 
        if(m.count(target))return m[target];
        string answ="";
        for(int i=0;i!=v.size();i++){
            if(target>=v[i]){
                string ans=dfs(target-v[i]);
                if(ans!=null&&cmp(to_string(i+1)+ans,answ))answ=to_string(i+1)+ans;
            }
        }
        return m[target]=answ.empty()?null:answ;
    }
    string largestNumber(vector<int>& cost, int target) {
        v=cost;
        return dfs(target)==null?"0":dfs(target);
    }
};

Posted on | In , |
Words count in article: 793 | Reading time ≈ 4

5404. 用栈操作构建数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        vector<string> ret;
        int z = 0;
        for(int i=1; i<=n; i++) {
            if(z == target.size())
                break;
            if(target[z] == i) {
                ret.push_back("Push");
                z++;
            } else {
                ret.push_back("Push");
                ret.push_back("Pop");
            }
        }
        return ret;
    }
};

5405. 形成两个异或相等数组的三元组数目

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 countTriplets(vector<int>& arr) {
        for(int i=1; i<arr.size(); i++) {
            arr[i] ^= arr[i-1];
        }
        int res = 0;
        for(int i=0; i<arr.size()-1; i++) {
            for(int j=i+1; j<arr.size(); j++) {
                for(int k=j; k<arr.size(); k++) {
                    int a = 0, b = 0;
                    if(i == 0) {
                        a = arr[j-1];
                    } else {
                        a = arr[j-1] ^ arr[i-1];
                    }
                    b = arr[k] ^ arr[j-1];
                    if(a == b) {
                        res++;
                    }
                }
            }
        }
        return res;
    }
};

5406. 收集树上所有苹果的最少时间

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 {
private:
    vector<vector<int>> edges;
    vector<bool> has;
    int ans;
        
public:
    void dfs1(int u, int fa) {
        for (int v: edges[u]) {
            if (v != fa) {
                dfs1(v, u);
                has[u] = has[u] | has[v];
            }
        }
    }
    
    void dfs2(int u, int fa) {
        for (int v: edges[u]) {
            if (v != fa && has[v]) {
                ++ans;
                dfs2(v, u);
                ++ans;
            }
        }
    }
    
    int minTime(int n, vector<vector<int>>& _edges, vector<bool>& hasApple) {
        edges.resize(n);
        has = hasApple;
        for (const auto& e: _edges) {
            edges[e[0]].push_back(e[1]);
            edges[e[1]].push_back(e[0]);
        }
        dfs1(0, -1);
        
        ans = 0;
        dfs2(0, -1);
        return ans;
    }
};

5407. 切披萨的方案数

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
#define ll long long int

class Solution {
public:

    const ll mod=1e9+7;
    int ways(vector<string>& pizza, int k) {
        int row=pizza.size(),col=pizza[0].length();
        //计算num
        vector<vector<int>> num(row,vector<int>(col,0));
        if(pizza[0][0]=='A') num[0][0]=1;
        for(int i=1;i<row;i++) num[i][0]=num[i-1][0]+(pizza[i][0]=='A');
        for(int i=1;i<col;i++) num[0][i]=num[0][i-1]+(pizza[0][i]=='A');
        for(int i=1;i<row;i++) for(int j=1;j<col;j++)
                num[i][j]=num[i-1][j]+num[i][j-1]-num[i-1][j-1]+(pizza[i][j]=='A');
            
        //初始化dp
        vector<vector<vector<ll>>> dp(row,vector<vector<ll>>(col,vector<ll>(k+1,0)));
        dp[0][0][1]=1;

        //从k=2开始填充
        for(int x=2;x<=k;x++){
            for(int i=0;i<row;i++){
                for(int j=0;j<col;j++){
                    //dp为0代表不存在这种情况
                    if(dp[i][j][x-1]==0)
                        continue;
                    //穷举水平切
                    for(int z=i+1;z<row;z++){
                        if(hasA(num,i,j,z-1,col-1) && hasA(num,z,j,row-1,col-1)){
                            dp[z][j][x]+=dp[i][j][x-1];
                            dp[z][j][x]%=mod;
                        }
                    }
                    //穷举垂直切
                    for(int z=j+1;z<col;z++){
                        if(hasA(num,i,j,row-1,z-1) && hasA(num,i,z,row-1,col-1)){
                            dp[i][z][x]+=dp[i][j][x-1];
                           dp[i][z][x]%=mod;
                        }
                    }
                }
            }
        }
            
        //计算答案
        ll ans=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                ans+=dp[i][j][k];
            }
            ans%=mod;
        }
        return ans;
    }
        
    //计算存在A吗
    bool hasA(vector<vector<int>>& num,int sr,int sc,int er,int ec){
        int num1=0,num2=0,num3=0,res;
        if(sr!=0 && sc!=0) num1=num[sr-1][sc-1];
        if(sr!=0) num2=num[sr-1][ec];
        if(sc!=0) num3=num[er][sc-1];
        return num[er][ec]-num2-num3+num1>0;
    }
};

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

5400. 旅行终点站

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_map<string, int> mp;
        for(auto p: paths) {
            mp[p[0]]++;
        }
        for(auto p: paths) {
            if(mp[p[1]] == 0) return p[1];
        }
        return "";
    }
};

5401. 是否所有 1 都至少相隔 k 个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int c = k;
        for(int i=0; i<nums.size(); i++) {
            if(nums[i] == 0) c++;
            else {
                if(c < k) return false;
                c = 0; 
            }
        }
        return true;
    }
};

5402. 绝对差不超过限制的最长连续子数组

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 longestSubarray(vector<int>& nums, int limit) {
        int maxlen = 0, minnum = INT_MAX, maxnum = INT_MIN, len = 0;
        for(int i=0, j=0; j<nums.size(); ) {
            minnum = min(nums[j], minnum);
            maxnum = max(nums[j], maxnum);
            if(abs(maxnum-minnum) > limit) {
                i++;
                j = i;
                minnum = INT_MAX, maxnum = INT_MIN;
                len = 0;
            } else {
                len++;
                j++;
                maxlen = max(maxlen, len);
            }
        }
        return maxlen;
    }
};

1439. 有序矩阵中的第 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
class Solution {
public:
    vector<vector<int>> temp;
    int m, n;
    int kthSmallest(vector<vector<int>>& mat, int k) {
        temp = mat;
        m = mat.size(), n = mat[0].size();
        int left = 0, right = 0;
        for(int i=0; i<m; i++) left += mat[i][0], right += mat[i].back();
        int init = left;
        while(left <right) {
            int mid = (left + right) >> 1;
            int num = 1;
            dfs(mid, 0, init, num, k);
            if(num >= k) right = mid;
            else left = mid+1;
        }
        return left;
    }
    void dfs(int mid, int index, int sum, int& num, int k) {
        if(sum > mid || index == m || num > k) return;
        dfs(mid, index+1, sum, num, k);
        for(int i=1; i<n; i++) {
            if(sum + temp[index][i]-temp[index][0] <= mid) {
                num ++;
                dfs(mid, index+1, sum+temp[index][i]-temp[index][0], num, k);
            } else break;
        }
    }
};