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

5356. 矩阵中的幸运数

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
class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix) {
        if(matrix.empty()) return {};
        vector<int> ret;
        unordered_map<int, int> rol;
        unordered_map<int, int> com;
        int m = matrix.size(), n = matrix[0].size(); 
        for(int i=0; i<m; i++) {
            int curmin = INT_MAX;
            for(int j=0; j<n; j++) {
                curmin = min(curmin, matrix[i][j]);
            }
            rol[i] = curmin;
        }
        for(int i=0; i<n; i++) {
            int curmax = INT_MIN;
            for(int j=0; j<m; j++) {
                curmax = max(curmax, matrix[j][i]);
            }
            com[i] = curmax;
        }
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(matrix[i][j] == rol[i] && matrix[i][j] == com[j]) {
                    ret.push_back(matrix[i][j]);
                }
            }
        }
        return ret;
    }
};

5357. 设计一个支持增量操作的栈

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
const int MAXN = 1000;

class CustomStack {
	int data[MAXN];
	int size;
	int top;
	public:
		CustomStack(int maxSize): size(maxSize), top(0) {}

		void push(int x) {
			if (top < size) {
				data[top++] = x;
			}
		}

		int pop() {
			if(top > 0) {
				return data[--top];
			}
			return -1;
		}

		void increment(int k, int val) {
			for(int i = 0, n = min(k, top); i < n; i++) {
				data[i] += val;
			}
		}
};

5179. 将二叉搜索树变平衡

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
        void PreOrder(vector<TreeNode*>& tmp, TreeNode* root){
        stack<TreeNode*> stack;
        TreeNode* p=root;
        while(p!=NULL || !stack.empty()){
            while(p!=NULL){
                stack.push(p);
                p=p->left;
            }
            p=stack.top();
            stack.pop();
            tmp.push_back(p);
            p=p->right;
        }
    }
    
    TreeNode* balanceBSTCore(vector<TreeNode*>& tmp, int m, int n){
        if(m>n)
            return NULL;
        int k=(m+n)/2;
        tmp[k]->left=balanceBSTCore(tmp,m,k-1);
        tmp[k]->right=balanceBSTCore(tmp,k+1,n);
        return tmp[k];
    }
    
    TreeNode* balanceBST(TreeNode* root) {
        vector<TreeNode*> tmp;
        PreOrder(tmp, root);
        int size=tmp.size()-1;
        return balanceBSTCore(tmp,0,size);
    }
};

1383. 最大的团队表现值

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 maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        long mod = 1000000007;
        long res = 0;
        long sum = 0;
        vector<vector<int>> es;
        for(int i=0; i<n; i++) es.push_back({efficiency[i], speed[i]});
        sort(es.rbegin(), es.rend());
        priority_queue<int, vector<int>, greater<int>> q;
        for(int i=0; i<n; i++) {
            sum += es[i][1];
            int eff = es[i][0];
            q.push(es[i][1]);
            bool flag = false;
            while(q.size() > k) {
                if(q.top() == es[i][1]) flag = true;
                sum -= q.top();
                q.pop();
            }
            if(!flag) res = max(res, eff*sum);
        }
        return (int)(res%mod);
    }
};

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

1374. 生成每种字符都是奇数个的字符串

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    string generateTheString(int n) {
        if(n & 1){
            return string(n,'a');
        }else{
            return string(n-1,'a') + "b";
        }
    }
};

1375. 灯泡开关 III

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        int m=0, cnt=0;
        for(int i=0; i<light.size(); i++) {
            m = max(light[i], m);
            if(m == i+1) cnt++;
        }
        return cnt;
    }
};

1376. 通知所有员工所需的时间

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 numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<vector<int>> my_son(manager.size());
        for(int i=0;i<manager.size();i++){
            if(manager[i]!=-1) my_son[manager[i]].push_back(i);
        }
        queue<pair<int,int>> Q;
        Q.push({headID,0});
        int max=0;
        pair<int,int> cur;
        while(!Q.empty()){
            cur=Q.front();
            Q.pop();
            if(cur.second>max) max=cur.second;
            for(auto it:my_son[cur.first]){
                Q.push({it,cur.second+informTime[cur.first]});
            }
        }
        return max;
    }
};

1377. T 秒后青蛙的位置

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 node {
        int id;
        double p;
        int t;
        node(int a, double b, int c) {
            id = a; p = b; t = c;
        }
    };
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        vector<int> vis(n+1);
        vector<vector<int>> gh(n+1);
        for(auto& edge: edges) {
            gh[edge[0]].push_back(edge[1]);
            gh[edge[1]].push_back(edge[0]);
        } 
        queue<node> q;
        q.push(node(1, 1.0, 0));
        vis[1] = 1;
        while(!q.empty()) {
            node u = q.front(); q.pop();
            if(u.id == target && u.t == t) return u.p;
            int sz = 0;
            for(int i=0; i<gh[u.id].size(); i++) {
                if(vis[gh[u.id][i]] == 0) {
                    sz++;
                }
            }
            if(u.t < t) {
                int flag = 0;
                for(int i=0; i<gh[u.id].size(); i++) {
                    if(vis[gh[u.id][i]] == 0) {
                        flag = 1;
                        vis[gh[u.id][i]] = 1;
                        q.push(node(gh[u.id][i], u.p/sz, u.t+1));
                    }
                }
                if(flag == 0) {
                    q.push(node(u.id, u.p, u.t+1));
                }
            }
        }
        return 0.0;
    }
};

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

1370. 上升下降字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string sortString(string s) {
        vector<int> tmp(26);
        for(int i=0; i<s.size(); i++) tmp[s[i]-'a'] ++;
        string ret;
        while(ret.size() < s.size()) {
            for(int i=0; i<26; i++) if(tmp[i]) ret+=i+'a', tmp[i]--;
            for(int i=25; i>=0; i--) if(tmp[i]) ret+=i+'a',tmp[i]--;
        }
        return ret;
    }
};

1371. 每个元音包含偶数次的最长子字符串

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 findTheLongestSubstring(string s) {
        string v = "aeiou";
        int state = 0;
        int maxSize = 0;
        unordered_map<int, int> mp;
        mp[0] = -1;
        for(int i=0; i<s.size(); i++) {
            for(int k=0; k<5; k++) {
                if(v[k] == s[i]) {
                    state ^= (1 << k);
                    break;
                }
            }
            if(mp.find(state) != mp.end()) {
                maxSize = max(maxSize, i-mp[state]);
            } else {
                mp[state] = i;
            }
        }
        return maxSize;
    }
};

1372. 二叉树中的最长交错路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int ans=0;
    void dfs(TreeNode* root,int dir,int dis){//(当前结点，左/右孩子，路径长度)
        if(!root)return;
        ans=max(ans,dis);
        if(dir){//如果当前结点是其父结点的右孩子
            dfs(root->left,0,dis+1);//搜索其左孩子时，满足ZigZig，路径长度+1
            dfs(root->right,1,1);//搜索其右孩子时，不满足ZigZig，路径长度置为1
        } 
        else{//如果当前结点是其父结点的左孩子
            dfs(root->left,0,1);//搜索其左孩子时，不满足ZigZig，路径长度置为1
            dfs(root->right,1,dis+1);//搜索其右孩子时，满足ZigZig，路径长度+1
        }       
    }
public:
    int longestZigZag(TreeNode* root) {
        dfs(root->left,0,1);
        dfs(root->right,1,1);
        return ans;
    }
};

1373. 二叉搜索子树的最大键值和

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 maxsum = 0;
    int maxSumBST(TreeNode* root) {
        dfs(root);
        return maxsum;
    }
    vector<int> dfs(TreeNode* root) {
        if (!root) return {true, INT_MAX, INT_MIN, 0};
        auto lArr = dfs(root->left);
        auto rArr = dfs(root->right);
        int sum = 0, curmax, curmin;
        if (!lArr[0] || !rArr[0] || root->val >= rArr[1] || root->val <= lArr[2]) {
            return {false, 0, 0, 0};
        }
        curmin = root->left ? lArr[1] : root->val;
        curmax = root->right ? rArr[2] : root->val;
        sum += (root->val + lArr[3] + rArr[3]);
        maxsum = max(maxsum, sum);
        return {true, curmin, curmax, sum};
    }
};

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

5344. 有多少小于当前数字的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> ret;
        vector<int> tmp = nums;
        sort(tmp.begin(), tmp.end());
        int count = 0;
        unordered_map<int, int> mp;
        for(int i=0; i<tmp.size(); i++){
            if(i > 0 && tmp[i] == tmp[i-1]){
                count++; continue;
            }
            mp[tmp[i]] = count;
            count++;
        }
        for(int i=0; i<nums.size(); i++){
            ret.push_back(mp[nums[i]]);
        }
        return ret;
    }
};

5345. 通过投票对团队排名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
  string rankTeams(vector<string>& votes) {
    string S;
    int n = votes[0].size();
    vector<vector<int>> cnt(26, vector<int>(n, 0));
    for (auto &c: votes[0]) S.push_back(c);
    for (auto &v: votes) {
      for (int i = 0; i < v.size(); i++)  cnt[v[i] - 'A'][i]++;
    }
    sort(S.begin(), S.end());
    sort(S.begin(), S.end(), [&cnt](char l, char r) {
      return cnt[l-'A'] > cnt[r-'A'];
    });
    return S;
  }
};

5346. 二叉树中的列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
  vector<int> L;
  bool dfs(TreeNode* root, vector<int> &cur) {
    if (L.size() <= cur.size() && equal(L.begin(), L.end(), cur.end() - L.size())) return true;
    if (root == NULL) return false;
    cur.push_back(root->val);
    if (dfs(root->left, cur)) return true;
    if (dfs(root->right, cur)) return true;
    cur.pop_back();
    return false;
  }
  
  bool isSubPath(ListNode* head, TreeNode* root) {
    L.clear();
    while (head) L.push_back(head->val), head = head->next;
    vector<int> cur;
    return dfs(root, cur);
  }
};

5347. 使网格图至少有一条有效路径的最小代价

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
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int inf = 0x3f3f3f3f;
        vector<vector<int> > cost(n, vector(m, inf));
        cost[0][0] = 0;
        queue<pair<int, int>> Q;
        Q.push({0, 0});
        while (!Q.empty()) {
            auto cur = Q.front(); Q.pop();
            int x = cur.first, y = cur.second, tx, ty;
            for (int i = 1; i <= 4; ++i) {
                tx = x, ty = y;
                if (i == 1) ty++;
                else if (i == 2) ty--;
                else if (i == 3) tx++;
                else tx--;
                
                if (tx >= 0 && ty >= 0 && tx < n && ty < m) {
                    int extra = i != grid[x][y];
                    if (cost[tx][ty] > extra + cost[x][y]) {
                        cost[tx][ty] = extra + cost[x][y];
                        Q.push({tx, ty});
                    }
                }
            }
        }
        return cost[n-1][m-1];
    }
};

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

5323. 根据数字二进制下 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
class Solution {
public:
    int find(int n){
        int count = 0;
        while(n){
            n = n&(n-1);
            count++;
        }
        return count;
    }
    static bool cmp(vector<int>& a, vector<int>& b){
        if(a[1]==b[1]) return a[0] < b[0];
        return a[1] < b[1];
    }
    vector<int> sortByBits(vector<int>& arr) {
        vector<vector<int>> v(arr.size(), vector<int>(2));
        for(int i=0; i<arr.size(); i++) {
            v[i][0] = arr[i];
            v[i][1] = find(arr[i]);
        }
        sort(v.begin(), v.end(), cmp);
        vector<int> ret;
        for(int i=0; i<arr.size(); i++)
            ret.push_back(v[i][0]);
        return ret;
    }
};

5325. 包含所有三种字符的子字符串数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numberOfSubstrings(string s) {
        int ret = 0;
        int n = s.size();
        int mp[3] = {0,0,0};
        mp[s[0]-'a']++;
        mp[s[1]-'a']++;
        int i =0;
        for(int j=i+2; j<n; j++){
            mp[s[j]-'a']++;
            while(mp[0]&&mp[1]&&mp[2]){
                ret += n-j;
                mp[s[i++]-'a']--;
            }
        }
        return ret;
    }
};

5326. 有效的快递序列数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    const int MOD = 1000000007;

    int countOrders(int N) {
        long long P = 1;
        for (int n = 2; n <= N; n++) {
            long long a = 2 * (n - 1) + 1;
            long long b = a * (a - 1) / 2 + a;
            P = (b * P) % MOD;
        }

        return P;
    }
};

5324. 每隔 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
27
28
29
class Cashier {
public:
    int discount;
    int n;
    unordered_map<int, int> priceMap;
    int index = 0; 
    
    Cashier(int n, int discount, vector<int>& products, vector<int>& prices) {
        this->n = n;
        this->discount = discount;
        
        for (int i = 0; i < products.size(); i++) {
            priceMap[products[i]] = prices[i];
        }
    }
    
    double getBill(vector<int> product, vector<int> amount) {
        index++;
        double sum = 0;
        for (int i = 0; i < product.size(); i++) {
            sum += priceMap[product[i]] * amount[i];
        }
        if (index % n == 0) {
            sum = sum - (discount * sum) / 100;
        }
        
        return sum;
    }
};

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

5169. 日期之间隔几天

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def daysBetweenDates(self, date1, date2):
        import datetime
        d1 = datetime.datetime.strptime(date1, '%Y-%m-%d')
        d2 = datetime.datetime.strptime(date2, '%Y-%m-%d')
        if(d1 > d2):
            d = d1 - d2
        else:
            d = d2 - d1
        return d.days

5170. 验证二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        vector<int> visited(n);
        queue<int> q;
        q.push(0);
        int count = 0;
        while(!q.empty()){
            int cur = q.front(); q.pop();
            if(visited[cur]) return false;
            visited[cur] = 1;
            if(leftChild[cur] != -1) q.push(leftChild[cur]);
            if(rightChild[cur] != -1) q.push(rightChild[cur]);
            count++;
        }
        return count == n;
    }
};

5171. 最接近的因数

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:
    vector<int> closestDivisors(int num) {
        int n1 = num+1, n2 = num+2;
        vector<int> ret(2);
        int curmin = INT_MAX;
        for(int i=1; i<=sqrt(n1); i++){
            int f = n1 % i;
            if(f == 0 && abs(n1/i-i)<curmin){
                curmin = abs(n1/i-i);
                ret[0] = i; ret[1] = n1/i;
            }
        }
        for(int i=1; i<=sqrt(n2); i++){
            int f = n2 % i;
            if(f == 0 && abs(n2/i-i)<curmin){
                curmin = abs(n2/i-i);
                ret[0] = i; ret[1] = n2/i;
            }
        }
        return ret;
    }
};

5172. 形成三的最大倍数

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
71
72
73
74
75
76
77
78
79
class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        vector<vector<int>> v(3);
        int sum = 0;
        for (auto x : digits)
        {
            v[x%3].push_back(x);
            sum += x;
            sum %= 3;
        }
        vector<int> r;
        for (int i = 0; i < 3; ++ i)
        {
            sort(v[i].begin(), v[i].end(), greater<int>());
        }
        
        if (sum == 0)
        {
            for (int i = 0; i < 3; ++ i)
            {
                int c = v[i].size();
                for (int j = 0; j < c; ++ j) r.push_back(v[i][j]);
            }
        }
        else if (sum == 1)
        {
            if (v[1].size() >= 1)
            {
                for (int i = 0; i < 3; ++ i)
                {
                    int c = v[i].size();
                    if (i == 1) c --;
                    for (int j = 0; j < c; ++ j) r.push_back(v[i][j]);
                }
            }
            else
            {
                for (int i = 0; i < 3; ++ i)
                {
                    int c = v[i].size();
                    if (i == 2) c -= 2;
                    for (int j = 0; j < c; ++ j) r.push_back(v[i][j]);
                }
            }
        }
        else if (sum == 2)
        {
            if (v[2].size() >= 1)
            {
                for (int i = 0; i < 3; ++ i)
                {
                    int c = v[i].size();
                    if (i == 2) c --;
                    for (int j = 0; j < c; ++ j) r.push_back(v[i][j]);
                }
            }
            else
            {
                for (int i = 0; i < 3; ++ i)
                {
                    int c = v[i].size();
                    if (i == 1) c -= 2;
                    for (int j = 0; j < c; ++ j) r.push_back(v[i][j]);
                }
            }
        }
        
        if (r.empty()) return "";
        
        sort(r.begin(), r.end(), greater<int>());
        if (r[0] == 0) return "0";
        
        string ret;
        for (auto x : r)
            ret += x+'0';
        return ret;
    }
};

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

5340. 统计有序矩阵中的负数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int count = 0;
        for(int i=0; i<grid.size(); i++){
            int cur = 0;
            for(; cur<grid[0].size(); cur++){
                if(grid[i][cur] < 0) break;
            }
            count += grid[0].size()-cur;
        }
        return count;
    }
};

5341. 最后 K 个数的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class ProductOfNumbers {
public:
    vector<int> cot;

    ProductOfNumbers() {}
    
    void add(int num) {
        cot.push_back(num);
    }
    
    int getProduct(int k) {
        int ret = 1;
        int count = 0;
        for(int i=cot.size()-1; i>=0; i--){
            ret *= cot[i];
            count++;
            if(count == k) break;
        }
        return ret;
    }
};

5342. 最多可以参加的会议数目

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:
    static bool cmp(vector<int>& a, vector<int>& b){
        if(a[1] == b[1]) return a[0] < b[0];
        return a[1] < b[1];
    }
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end(), cmp);
        vector<int> visited(100005);
        int ret = 0;
        for(int i=0; i<events.size(); i++){
            for(int j=events[i][0]; j<=events[i][1]; j++){
                if(!visited[j]){
                    visited[j] = 1;
                    ret ++;
                    break;
                }
            }
        }
        return ret;
    }
};

5343. 多次求和构造目标数组

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 Solution {
public:
    bool isPossible(vector<int>& target) {
        priority_queue<int> q;
        long long s = 0;
        for(int i=0; i<target.size(); i++){
            q.push(target[i]);
            s += target[i];
        }
        while(true){
            if(q.top() == 1) return true;
            long long p = q.top();
            q.pop();
            if(q.top() == 1){
                if((p-1) % (s-p) == 0) return true;
                else return false;
            }else{
                long long n = (p-q.top())/(s-p)+1;
                long long x = p-(s-p)*n;
                s = p-(s-p)*(n-1);
                if(x <= 0) return false;
                q.push(x);
            }
        }
        return false;
    }
};

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

5311. 将数字变成 0 的操作次数

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int numberOfSteps (int num) {
        int count = 0;
        while(num){
            if(num % 2 == 0) num /= 2;
            else num -= 1;
            count++;
        }
        return count;
    }
};

5312. 大小为 K 且平均值大于等于阈值的子数组数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        for(int i=1; i<arr.size(); i++){
            arr[i] += arr[i-1];
        }
        int count = 0;
        for(int i=k; i<arr.size(); i++){
            if((arr[i]-arr[i-k])/k >= threshold) 
                count++;
        }
        if(arr[k-1]/k >= threshold) count++;
        return count;
    }
};

5313. 时钟指针的夹角

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    double angleClock(int hour, int minutes) {
        double minu = (double)minutes;
        double hou = (hour%12)*5.0 + minu/60*5.0;
        double diff = abs(minu-hou);
        diff = min(diff, abs(60-diff));
        return diff/60*360;
    }
};

5314. 跳跃游戏 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    int minJumps(vector<int>& arr) {
        int ans = 0, c = 0, lop = 0; 
        vector<int> v; 
        map<int, vector<int>> m; 
        m.clear(); 
        
        for (int i = 0; i < arr.size(); ++ i){
            if (i && i != 1 && arr[i] == arr[i - 1]) continue;
            else{
                v.push_back(arr[i]); 
                m[arr[i]].push_back(c); 
                ++ c; 
            }
        }
        
        queue<int> Q;
        vector<bool> vis (v.size()+1, false);
        Q.push(0); vis[0] = true;
        
        while(!Q.empty()){
            lop = Q.size(); 
            for(int j = 0; j < lop; ++ j){
                int tmp = Q.front(); Q.pop();
                if(tmp == v.size() - 1) return ans; 
                if(tmp > 0 && !vis[tmp - 1]){ 
                    Q.push(tmp - 1);
                    vis[tmp - 1] = true;
                }
                if(tmp < v.size() - 1 && !vis[tmp + 1]){ 
                    Q.push(tmp + 1);
                    vis[tmp + 1] = true;
                }
                for(int i = 0; i < m[v[tmp]].size(); ++ i){ 
                    if(!vis[m[v[tmp]][i]]) { 
                        Q.push(m[v[tmp]][i]);
                        vis[m[v[tmp]][i]] = true;
                    }
                }
            }
            ++ ans; 
        }
        
        return ans;
    }
};

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

1331. 数组序号转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        map<int, int> mp;
        vector<int> arr2 = arr;
        sort(arr2.begin(), arr2.end());
        int k = 1;
        for(int i=0; i<arr2.size(); i++){
            if(mp[arr2[i]]) continue;
            mp[arr2[i]] = k++;
        }
        vector<int> res;
        for(int i=0; i<arr.size(); i++){
            res.push_back(mp[arr[i]]);
        }
        return res;
    }
};

1328. 破坏回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string breakPalindrome(string p) {
        if(p == "" || p.size() <= 1) return "";
        for(int i=0; i<p.size()/2; i++){
            if(p[i] != 'a'){
                p[i] = 'a';
                return p;
            }
        }
        p[p.size()-1] = 'b';
        return p;
    }
};

1329. 将矩阵按对角线排序

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
class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int Col = mat[0].size();
        int Row = mat.size();
        if(Row==1 || Row==0 || Col==1)
            return mat;
        for(int i = Row-2;i >= 0;i--)
        {
            int col = 0;
            vector<int> temp;
            for(int j = i;j < Row && col < Col;++j,col++)
                temp.push_back(mat[j][col]);
            sort(temp.begin(),temp.end());
            col = 0;
            for(int j = i;j < Row && col < Col;++j,col++)
                mat[j][col] = temp[col];
        }
        for(int i = 1;i <Col-1;++i)
        {
            int row = 0;
            vector<int> temp;
            for(int j = i;j < Col && row < Row;++j,row++)
                temp.push_back(mat[row][j]);
            sort(temp.begin(),temp.end());
            row = 0;
            for(int j = i;j < Col && row <Row;++j,row++)
                mat[row][j] = temp[row];
        }
        return mat;
    }
};

1330. 翻转子数组得到最大的数组值

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
typedef long long ll;
class Solution {
public:
    int maxValueAfterReverse(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        if (n == 1)
            return 0;
        for (int i = 0; i < n - 1; ++i) {
            ans += abs(nums[i] - nums[i + 1]);
        }
        int raw = ans;
        for (int i = 1; i <= n - 2; ++i) {
            ans = max(ans,raw+abs(nums[n-1]-nums[i-1])-abs(nums[i]-nums[i-1]));
            ans = max(ans,raw+abs(nums[i+1]-nums[0])-abs(nums[i+1]-nums[i]));
        }
        int mx1 = INT_MIN;
        int mx2 = INT_MIN;
        int mx3 = INT_MIN;
        int mx4 = INT_MIN;
        for(int i = 1; i < n; ++i){
            ans = max(ans,raw + mx1 + nums[i] + nums[i-1] - abs(nums[i]-nums[i-1]));
            ans = max(ans,raw + mx2 - nums[i] + nums[i-1] - abs(nums[i]-nums[i-1]));
            ans = max(ans,raw + mx3 + nums[i] - nums[i-1] - abs(nums[i]-nums[i-1]));
            ans = max(ans,raw + mx4 - nums[i] - nums[i-1] - abs(nums[i]-nums[i-1]));
            mx1 = max(mx1,-(nums[i]+nums[i-1])-abs(nums[i]-nums[i-1]));
            mx2 = max(mx2,-(-nums[i]+nums[i-1])-abs(nums[i]-nums[i-1]));
            mx3 = max(mx3,-(nums[i]-nums[i-1])-abs(nums[i]-nums[i-1]));
            mx4 = max(mx4,-(-nums[i]-nums[i-1])-abs(nums[i]-nums[i-1]));
        } 
        return ans;
    }
};

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

1341. 方阵中战斗力最弱的 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
bool cmp(vector<int>& a, vector<int>& b){
    if(a[1] == b[1])
        return a[0] < b[0];
    return a[1] < b[1];
}
class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        vector<vector<int>> tmp(mat.size(), vector<int>(2, 0));
        for(int i=0; i<mat.size(); i++){
            tmp[i][0] = i;
            int j=0;
            for(; j<mat[i].size(); j++){
                if(mat[i][j] == 0)
                    break;
            }
            tmp[i][1] = j;
        }
        sort(tmp.begin(), tmp.end(), cmp);
        vector<int> ret;
        for(int i=0; i<k; i++)
            ret.push_back(tmp[i][0]);
        return ret;
    }
};

1342. 数组大小减半

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool cmp(int& a, int& b){
    return a > b;
}
class Solution {
public:
    int minSetSize(vector<int>& arr) {
        int size = arr.size();
        vector<int> a(100005, 0);
        for(auto& i: arr){
            a[i]++;
        }
        sort(a.begin(), a.end(), cmp);
        int count = 0;
        int ret = 0;
        for(int i=0; i<a.size(); i++){
            if(a[i] == 0) break;
            if(count >= size/2) break;
            count += a[i];
            ret++;
        }
        return ret;
    }
};

1339. 分裂二叉树的最大乘积

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(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    const static int mod = 1e9 + 7;
    long long ans = -1;
    long long sum = 0;
    long long dfs(TreeNode* root){
        if(root == NULL) return 0;
        long long t1 = dfs(root->left), t2 = dfs(root->right);
        ans = max(ans, max(t1*(sum-t1), t2*(sum-t2)));
        return root->val + t1 + t2;
    }
    int maxProduct(TreeNode* root) {
        sum = dfs(root);
        dfs(root);
        return (int)(ans % mod);
    }
};

1344. 跳跃游戏 V

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 maxJumps(vector<int>& arr, int d) {
        int n = arr.size();
        vector<vector<int>> temp;
        vector<int> dp(n, 1);
        int res = 1;
        for(int i=0; i<n; i++)
            temp.push_back({arr[i], i});
        sort(temp.begin(), temp.end());
        for(int i=0; i<n; i++){
            int index = temp[i][1];
            for(int j=index-1; j>=index-d && j>=0; j-- ){
                if(arr[j] >= arr[index]) break;
                dp[index] = max(dp[index], dp[j]+1);
            }
            for(int j=index+1; j<=index+d && j<n; j++ ){
                if(arr[j] >= arr[index]) break;
                dp[index] = max(dp[index], dp[j]+1);
            }
            res = max(res, dp[index]);
        }
        return res;
    }
};