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

1332. 删除回文子序列

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int removePalindromeSub(string s) {
        if(s == "") return 0;
        for(int l=0, r=s.size()-1; l < r; l++, r--)
            if(s[l] != s[r])
                return 2;
        return 1;
    }
};

1333. 餐厅过滤器

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(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> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        vector<vector<int>> cot;   
        for(int i=0; i<restaurants.size(); i++){
            if(restaurants[i][2] != veganFriendly && veganFriendly == 1) continue;
            if(restaurants[i][3] > maxPrice) continue;
            if(restaurants[i][4] > maxDistance) continue;
            cot.push_back(restaurants[i]);
        }
        sort(cot.begin(), cot.end(), cmp);
        vector<int> ret;
        for(int i=0; i<cot.size(); i++)
            ret.push_back(cot[i][0]);
        return ret;
    }
};

1334. 阈值距离内邻居最少的城市

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
class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<int>> D(n, vector<int>(n, INT_MAX));
        for (auto& e : edges) {
        	D[e[0]][e[1]] = e[2];
        	D[e[1]][e[0]] = e[2];
        }
        for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (i == j || D[i][k] == INT_MAX || D[k][j] == INT_MAX)
						continue;
					D[i][j] = min(D[i][k]+D[k][j], D[i][j]);
				}
			}
		}
        int ret;
        int minNum = INT_MAX;
        for (int i = 0; i < n; i++) {
        	int cnt = 0; 
        	for (int j = 0; j < n; j++) {
        		if (i != j && D[i][j] <= distanceThreshold) {
        			cnt++;
        		}
        	}
        	if (cnt <= minNum) {
        		minNum = cnt;
        		ret = i;
        	}
        }
        return ret;
    }
};

1335. 工作计划的最低难度

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 minDifficulty(vector<int>& jobDifficulty, int d) {
        if(jobDifficulty.size() < d) return -1;
        int n = jobDifficulty.size(), day = d;
        vector<vector<int>> dp(n, vector<int>(d, INT_MAX));
        dp[0][0] = jobDifficulty[0];
        for(int i=1; i<n; i++){
            dp[i][0] = max(dp[i-1][0], jobDifficulty[i]);
        }
        for(int d=1; d<day; d++){
            for(int i=d; i<n; i++){
                int maxd = INT_MIN;
                for(int k=i-1; k>=d-1; k--){
                    maxd = max(maxd, jobDifficulty[k+1]);
                    dp[i][d] = min(dp[i][d], dp[k][d-1]+maxd);
                }
            }
        }
        return dp[n-1][day-1];
    }
};

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

5332. 检查整数及其两倍数是否存在

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        for(int i=0; i<arr.size(); i++){
            for(int j=i+1; j<arr.size(); j++){
                if(arr[i] == arr[j]*2 || arr[j] == arr[i]*2)
                    return true;
            }
        }
        return false;
    }
};

5333. 制造字母异位词的最小步骤数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minSteps(string s, string t) {
        vector<int> mp1(26);
        vector<int> mp2(26);
        for(int i=0; i<s.size(); i++){
            mp1[s[i]-'a']++;
            mp2[t[i]-'a']++;
        }
        int count = 0;
        for(int i=0; i<26; i++){
            int cur = mp1[i]-mp2[i];
            if(cur > 0) count += cur;
        }
        return count;
    }
};

1348. 推文计数

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 TweetCounts {
public:
    unordered_map<string,set<int> > r;
    TweetCounts() {
        
    }
    void recordTweet(string tn, int time) {
        r[tn].insert(time);
    }
    vector<int> getTweetCountsPerFrequency(string freq, string tn, int st, int et) {
        int f;
        if(freq=="minute")f = 60;
        else if(freq=="hour")f = 3600;
        else f = 86400;
        vector<int> res((et-st+f)/f);
        for(auto t:r[tn]){
            if(t>=st&&t<=et){
                int it = (t-st)/f;
                res[it]++;
            }
        }
        return res;
    }
};

5335. 参加考试的最大学生数

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
class Solution {
public:
    int maxStudents(vector<vector<char>>& seats) {
        int m=seats.size();
        int n=seats[0].size();
        vector<vector<int>> dp(m+1,vector<int>(1<<n));  //初始化

        for(int row=1;row<=m;row++){
            for(int s=0;s<(1<<n);s++){//遍历 2^n 个状态
                bitset<8> bs(s);//记录对应状态的bit位
                bool ok=true;
                for(int j=0;j<n;j++){
                    if((bs[j] && seats[row-1][j]=='#') || (j<n-1 && bs[j] && bs[j+1])){//不能坐在坏椅子上也不能在同一行相邻坐
                        ok=false;
                        break;
                    }
                }
                if(!ok){
                    dp[row][s]=-1;//说明坐在坏椅子上或相邻坐了，该状态舍弃
                    continue;
                }
                for(int last=0;last<(1<<n);last++){//找到一种当前行的可行状态后，遍历上一行的所有状态
                    if(dp[row-1][last]==-1)//上一行的状态被舍弃了，那就直接下一个状态
                        continue;
                    bitset<8> lbs(last);
                    bool flag=true;
                    for(int j=0;j<n;j++){
                        if(lbs[j] && ((j>0 && bs[j-1]) || (j<n-1 && bs[j+1]))){//如果找到的这个上一行状态的j位置坐了人，
                            flag=false;                                    //下一行的j+1位置或j-1位置也坐了人，那么该状态不合法，舍弃
                            break;
                        }
                    }
                    if(flag){//flag为真说明这个last状态的每个位置都合法
                        dp[row][s]=max(dp[row][s],dp[row-1][last]+(int)bs.count());//转移方程
                    }
                }

            }
        }
        int res=0;
        for(int i=0;i<(1<<n);i++){//在最后一行的所有状态中找出最大的
            if(dp[m][i]>res){
                res=dp[m][i];
            }
        }
        return res;
    }
};

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

5315. 6 和 9 组成的最大数字

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:
    string tostr(int n){
        string ret = "";
        while(n){
            ret += n % 10 + '0';
            n /= 10;
        }
        if(ret == "") ret = "0";
        reverse(ret.begin(), ret.end());
        return ret;
    }
    int toint(string n){
        int num = 0;
        for(int i=0; i<n.size(); i++){
            num = num * 10 + n[i]-'0';
        }
        return num;
    }
    int maximum69Number (int num) {
        string rem = tostr(num);
        for(int i=0; i<rem.size(); i++){
            if(rem[i] == '6'){
                rem[i] = '9';
                break;
            }
        }
        return toint(rem);
    }
};

1324. 竖直打印单词

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:
    vector<string> printVertically(string s) {
        vector<string> res;
        string tmp = "";
        int maxlen = 0;
        for(int i=0; i<s.size(); i++){
            if(s[i] == ' '){
                res.push_back(tmp);
                maxlen = max(maxlen, (int)tmp.size());
                tmp = "";
                continue;
            }
            tmp += s[i];
        }
        maxlen = max(maxlen, (int)tmp.size());
        res.push_back(tmp);
        vector<string> ret;
        for(int i=0; i<maxlen; i++){
            string cur = "";
            for(int j=0; j<res.size(); j++){
                if(i >= res[j].size()) cur += " ";
                else cur += res[j][i];
            }
            int end = cur.size()-1;
            for(; end>=0; end--){
                if(cur[end] != ' ')
                    break;
            }
            cur = cur.substr(0, end+1);
            ret.push_back(cur);
        }
        return ret;
    }
};

1325. 删除给定值的叶子节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if(root == NULL) return NULL;
        if(!root->left && !root->right && root->val == target)
            return NULL;
        if(root->left) root->left = removeLeafNodes(root->left, target);
        if(root->right) root->right = removeLeafNodes(root->right, target);
        if(!root->left && !root->right && root->val == target)
            return NULL;
        else return root;
    }
};

1326. 灌溉花园的最少水龙头数目

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 minTaps(int n, vector<int>& ranges) {
        vector<int> lands(n);
        for(int i=0; i<ranges.size(); i++){
            int l = max(0, i-ranges[i]);
            int r = min(n, i+ranges[i]);
            for(int j=l; j<r; j++){
                lands[j] = max(lands[j], r);
            }
        }
        int count = 0;
        int cur = 0;
        while(cur < n){
            if(lands[cur] == 0) return -1;
            cur = lands[cur];
            count++;
        }
        return count;
    }
};

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

1313. Decompress Run-Length Encoded List

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

1314. Matrix Block Sum

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<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> ret(m, vector<int>(n, 0));
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                int lx = max(0, i-K);
                int hx = min(m-1, i+K);
                int ly = max(0, j-K);
                int hy = min(n-1, j+K);
                int sum = 0;
                for(; lx<=hx; lx++)
                    for(int z=ly; z<=hy; z++)
                        sum += mat[lx][z];
                ret[i][j] = sum;
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
        int row = mat.size();
        int col = mat[0].size();
        vector<vector<int>> ret(row, vector<int>(col));
        vector<vector<int>> dp(row+1, vector<int>(col+1)); // +1边缘处理
        for(int i=0; i<row; i++)
            for(int j=0; j<col; j++)
                dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + mat[i][j];
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                int r1 = max(i-K, 0), c1 = max(j-K, 0);
                int r2 = min(i+K, row-1), c2 = min(j+K, col-1);
                ret[i][j] = dp[r2+1][c2+1]-dp[r1][c2+1]-dp[r2+1][c1]+dp[r1][c1];
            }
        }
        return ret;
    }
};

1315. Sum of Nodes with Even-Valued Grandparent

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
/**
 * 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:
    int sumEvenGrandparent(TreeNode* root) {
        int sum = 0;
        if(!root) return 0;
        if(root->val % 2 == 0){   
            if(root->left){
                if(root->left->left) sum += root->left->left->val;
                if(root->left->right) sum += root->left->right->val;
            }
            if(root->right){
                if(root->right->left) sum += root->right->left->val;
                if(root->right->right) sum += root->right->right->val;
            }
        }
        return sum + sumEvenGrandparent(root->left) + sumEvenGrandparent(root->right);
    }
};

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

1317. Convert Integer to the Sum of Two No-Zero Integers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool check(int n){
        while(n){
            if(n % 10 == 0) return false;
            n /= 10; 
        }
        return true;
    }
    vector<int> getNoZeroIntegers(int n) {
        for(int i=1; i<n; i++){
            if(check(i) && check(n-i))
                return {i, n-i};
        }
        return {0,0};
    }
};

1318. Minimum Flips to Make a OR b Equal to c

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:
    string tostr(int a){
        string ret = "";
        while(a){
            ret += a % 2 == 0? '0' : '1';
            a /= 2;
        }
        return ret;
    }
    int minFlips(int ia, int ib, int ic) {
        string a = tostr(ia);
        string b = tostr(ib);
        string c = tostr(ic);
        int count = 0;
        int maxlen = max(a.size(), max(b.size(), c.size()));
        while(a.size() != maxlen) a+='0';
        while(b.size() != maxlen) b+='0';
        while(c.size() != maxlen) c+='0';
        for(int i=0; i<maxlen; i++){
            if(c[i] == '0'){
                count += (a[i]=='1' ? 1: 0);
                count += (b[i]=='1' ? 1: 0);
            }else{
                if(a[i] == '0' && b[i] == '0') count++;
            }
        }
        return count;
    }
};

1319. Number of Operations to Make Network Connected

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> parent;
    int num;
    int find(int x){
        while(x != parent[x]){
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    void Union(int x, int y){
        int px = find(x);
        int py = find(y);
        num--;
        parent[px] = py;
    }
    int makeConnected(int n, vector<vector<int>>& connections) {
        parent.resize(n);
        num = n;
        for(int i=0; i<n; i++) parent[i] = i;
        int count = 0;
        for(auto& con: connections){
            int a = con[0], b = con[1];
            if(find(a) == find(b)) count++;
            else Union(a, b);
        }
        int ret = num-1;
        if(ret <= count) return ret;
        else return -1;
    }
};

1320. Minimum Distance to Type a Word Using Two Fingers

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 M[26][2] = {
        {0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, 
        {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, 
        {2, 0}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {2, 5}, 
        {3, 0}, {3, 1}, {3, 2}, {3, 3}, {3, 4}, {3, 5}, 
        {4, 0}, {4, 1}
    };
    int dist(int i, int j) {
        return abs(M[i][0] - M[j][0]) + abs(M[i][1] - M[j][1]);
    }
    const int INF = 1e8;
    int minimumDistance(string word) {
        int N = word.size();
        if (N < 2) return 0;
        vector<vector<vector<int> > > dp(N + 1, vector<vector<int> >(26, vector<int>(26, INF)));
        int step = 0;
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < 26; ++j) {
                dp[0][i][j] = 0;
            }
        }
        for (int i = 1; i <= N; ++i) {
            int curr = word[i - 1] - 'A';
            for (int j = 0; j < 26; ++j) {
                for (int k = 0; k < 26; ++k) {
                    dp[i][curr][j] = min(dp[i][curr][j], dp[i - 1][k][j] + dist(curr, k));
                    dp[i][curr][j] = min(dp[i][curr][j], dp[i - 1][curr][k] + dist(k, j));
                    
                    dp[i][j][curr] = min(dp[i][j][curr], dp[i - 1][j][k] + dist(curr, k));
                    dp[i][j][curr] = min(dp[i][j][curr], dp[i - 1][k][curr] + dist(k, j));
                }
            }
        }
        int res = INF;
        int ind = word[N - 1] - 'A';
        for (int i = 0; i < 26; ++i) {
            res = min(res, dp[N][ind][i]);
            res = min(res, dp[N][i][ind]);
        }
        return res;
    }
};

Posted on | In , |
Words count in article: 850 | Reading time ≈ 5

1309. Decrypt String from Alphabet to Integer Mapping

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

1310. XOR Queries of a Subarray

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int> rem(arr.size());
        for(int i=0;i<arr.size(); i++){
            if(i-1>=0) rem[i] = rem[i-1]^arr[i];
            else rem[i] = arr[i];
        }
        vector<int> ret(queries.size());
        for(int i=0; i<queries.size(); i++){
            if(queries[i][0] == queries[i][1]) ret[i] = arr[queries[i][0]];
            else if(queries[i][0] == 0) ret[i] = rem[queries[i][1]];
            else ret[i] = rem[queries[i][1]] ^ rem[queries[i][0]-1];
        }
        return ret;
    }
};

1311. Get Watched Videos by Your Friends

dfs莫名不过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    map<string, int> mp;
    vector<int> visited;
    void dfs(vector<vector<string>> &watchedVideos, vector<vector<int>> &friends, int id, int level){
        if(visited[id] == 1) return;
        if(level < 0) return;
        if(level == 0){
            for(int i=0; i<watchedVideos[id].size(); i++)
                mp[watchedVideos[id][i]]++;
        }
        visited[id] = 1;
        for(int i=0; i<friends[id].size(); i++){
            dfs(watchedVideos, friends, friends[id][i], level-1);
        }
    }
    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
        visited.resize(friends.size());
        visited[id] = 1;
        for(int i=0; i<friends[id].size(); i++){
            dfs(watchedVideos, friends, friends[id][i], level-1);
        }
        vector<pair<string, int>> ret1;
        for(auto it = mp.begin(); it != mp.end(); it++){
            ret1.push_back(*it);
        }
        sort(ret1.begin(), ret1.end(), cmp);
        vector<string> ret;
        for(auto it=ret1.begin(); it != ret1.end(); it++)
            ret.push_back(it->first);
        return ret;
    }
    static bool cmp(const pair<string, int>& a, const pair<string, int>& b)
	{
		if (a.second == b.second)
			return a.first < b.first;
		else
			return a.second < b.second;
	}
};

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 {
public:
	vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
		unordered_map<string, int> videosMap;
		queue<pair<int, int>> bfsQueue;
		vector<bool> visited(watchedVideos.size(), false);
		bfsQueue.push(make_pair(id, 0));
		visited[id] = true;
		while (!bfsQueue.empty())
		{
			const pair<int, int>& frontPair = bfsQueue.front();
			int frontId = frontPair.first;
			int frontLevel = frontPair.second;
			if (frontLevel == level - 1)
			{
				for (size_t i = 0; i < friends[frontId].size(); ++i)
				{
					int friendId = friends[frontId][i];
					if (!visited[friendId])
					{
						visited[friendId] = true;
						for (size_t j = 0; j < watchedVideos[friendId].size(); ++j)
						{
							string video = watchedVideos[friendId][j];
							if (videosMap.find(video) == videosMap.end())
								videosMap[video] = 1;
							else
								++videosMap[video];
						}
					}
				}
			}
			else
			{
				for (size_t i = 0; i < friends[frontId].size(); ++i)
				{
					int friendId = friends[frontId][i];
					if (!visited[friendId])
					{
						bfsQueue.push(make_pair(friendId, frontLevel + 1));
						visited[friendId] = true;
					}
				}
			}
			bfsQueue.pop();
		}
		vector<pair<string, int>> videosVec;
		for (auto it = videosMap.begin(); it != videosMap.end(); ++it)
			videosVec.push_back(make_pair(it->first, it->second));
		sort(videosVec.begin(), videosVec.end(), cmp);
		vector<string> videos;
		for (auto it = videosVec.begin(); it != videosVec.end(); ++it)
			videos.push_back(it->first);
		return videos;
	}

	static bool cmp(const pair<string, int>& a, const pair<string, int>& b)
	{
		if (a.second == b.second)
			return a.first < b.first;
		else
			return a.second < b.second;
	}
};

1312. Minimum Insertion Steps to Make a String Palindrome

动态规划 用字符串长度减去最长回文子序列的长度就是最少插入次数了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minInsertions(string s) {
        int n=s.size();
        int dp[n][n];
        memset(dp,0,sizeof(dp));
        for(int i=n-1;i>=0;--i){
            dp[i][i]=1;
            for(int j=i+1;j<n;++j){
                if(s[i]==s[j]){
                    dp[i][j]=dp[i+1][j-1]+2;
                }
                else{
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return n-dp[0][n-1];
    }
};

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

5295. Find N Unique Integers Sum up to Zero

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:
    vector<int> sumZero(int n) {
        vector<int> ret;
        if(n == 1) return {0};
        if(n == 0) return {0};
        int flag = n%2==0 ? 1 : 0;
        if(flag == 1){
            for(int i=0; i<n; i+=2){
                ret.push_back(i+1);
                ret.push_back((i+1)*(-1));
            }
        }else {
            int t = n-3;
            int i=0;
            for(; i<t; i+=2){
                ret.push_back(i+1);
                ret.push_back((i+1)*(-1));
            }
            ret.push_back(i+2);
            ret.push_back(i+3);
            ret.push_back((2*i+5)*(-1));
        }
        return ret;
    }
};

5296. All Elements in Two Binary Search Trees

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
/**
 * 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 inorder(TreeNode* root, vector<int>& con){
        if(!root) return;
        if(root->left) inorder(root->left, con);
        con.push_back(root->val);
        if(root->right) inorder(root->right, con);
    }
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> r1;
        vector<int> r2;
        inorder(root1, r1);
        inorder(root2, r2);
        int i=0;
        int j=0;
        vector<int> ret;
        while(i<r1.size() && j<r2.size()){
            if(r1[i] < r2[j]) ret.push_back(r1[i++]);
            else ret.push_back(r2[j++]);
        }
        while(i<r1.size()) ret.push_back(r1[i++]);
        while(j<r2.size()) ret.push_back(r2[j++]);
        return ret;
    }
};

5297. Jump Game III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool dfs(vector<int>& arr, int start, vector<int>& visited){
        if(arr.size() == 1 && start >=0 && start < arr.size()) return arr[0]==0;
        if(start < 0 || start >= arr.size() || visited[start] == 1) return false;
        if(arr[start] == 0) return true;
        visited[start] = 1;
        return dfs(arr, start-arr[start], visited)||dfs(arr, start+arr[start], visited);
    }
    bool canReach(vector<int>& arr, int start) {
        vector<int> visited(arr.size(), 0);
        return dfs(arr, start, visited);
    }
};

5298. Verbal Arithmetic Puzzle

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
80
81
82
83
84
85
86
87
88
89
90
class Solution {
    vector<vector<char>> lefts;
    vector<char> rights;
    unordered_map<char, int> map;
    unordered_set<int> used;
    bool check(int level, int idx, int sum) {
		// last check
        if (level >= rights.size()) {
			// check left length is larger than right
            if (level < lefts.size()) {
                return false;
            }
			// check leading zeros
            for (char ch : lefts.back()) {
                if (map[ch] == 0) {
                    return false;
                }
            }
            if (map[rights.back()] == 0) {
                return false;
            }
            return sum == 0;
        }
        //check equality at the end of each level, level < rights.size();
        if (level >= lefts.size() || idx >= lefts[level].size()) {
            char ch = rights[level];
            bool add = false;
            if (map.find(ch) == map.end()) {
				// try map right character
                if (used.count(sum % 10) > 0) {
                    return false;
                } else {
                    used.insert(sum % 10);
                    map[ch] = sum % 10;
                    add = true;
                }
            } else if (map[ch] != sum % 10) {
                return false;
            }
            if (check(level + 1, 0, sum / 10)) {
                return true;
            } else {
                if (add) {
					// reset mapping
                    used.erase(sum % 10);
                    map.erase(ch);
                }
                return false;
            }
        }
        char ch = lefts[level][idx];
        if (map.find(ch) != map.end()) {
			// this left character is already mapped
            return check(level, idx + 1, sum + map[ch]);
        }
        for (int i = 0; i <= 9; i++) {
			// enumerate to map left character
            if (used.count(i) > 0) {
                continue;
            }
            map[ch] = i;
            used.insert(i);
            if (check(level, idx + 1, sum + i)) {
                return true;
            }
            map.erase(ch);
            used.erase(i);
        }
        return false;
    }
public:
    bool isSolvable(vector<string>& words, string result) {
        int levels = 0;
        for (const string &str : words) {
            levels = max(levels, (int)str.length());
        }
        for (int level = 0; level < levels; level++) {
            lefts.emplace_back();
            for (const string &str : words) {
                if (level < str.length()) {
                    lefts[level].push_back(str[str.length() - level - 1]);
                }
            }
        }
        for (int i = result.length() - 1; i >= 0; i--) {
            rights.push_back(result[i]);
        }
        return check(0, 0, 0);
    }
};

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

5134. Replace Elements with Greatest Element on Right Side

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int curmax = arr[arr.size()-1];
        vector<int> ret(arr.size(), 0);
        ret[arr.size()-1] = -1;
        for(int i=arr.size()-2; i>=0; i--){
            ret[i] = curmax;
            if(arr[i] > curmax) curmax = arr[i];
        }
        return ret;
    }
};

5135. Sum of Mutated Array Closest to Target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int check(vector<int>& arr, int mid){
        int sum = 0;
        for(int i=0; i<arr.size(); i++){
            if(arr[i] > mid)
                sum += mid;
            else 
                sum += arr[i];
        }
        return sum;
    }
    int findBestValue(vector<int>& arr, int target) {
        sort(arr.begin(), arr.end());
        int l = 0;
        int r = arr[arr.size()-1];
        while(l < r){
            int mid = (l+r)>>1;
            if(check(arr, mid) >= target){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        int l1 = check(arr, l);
        int l2 = check(arr, l-1);
        if(abs(l1-target) < abs(l2-target)){
            return l;
        }else {
            return l-1;
        }
    }
};

1302. Deepest Leaves Sum

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(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxD = 0;
    int sum = 0;
    void getMD(TreeNode* root, int cur){
        if(!root) return;
        if(!root->left && !root->right){
            maxD = maxD > cur ? maxD: cur;
            return;
        }
        if(root->left) getMD(root->left, cur+1);
        if(root->right) getMD(root->right, cur+1);
    }
    void getSum(TreeNode* root, int cur){
        if(cur == maxD) {
            sum += root->val; return;
        }
        if(!root){
            return;
        }
        if(root->left) getSum(root->left, cur+1);
        if(root->right) getSum(root->right, cur+1);
    }
    int deepestLeavesSum(TreeNode* root) {
        getMD(root, 0);
        getSum(root, 0);
        return sum;
    }
};

1301. Number of Paths with Max Score

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
typedef long long ll;
const ll MOD = 1e9+7; 
const ll inf = 1e6;

class Solution {
    int n, m;
    int maze[110][110];
    pair<ll, ll> dp[110][110];
public:
    vector<int> pathsWithMaxScore(vector<string>& board) {
        n = board.size();
        m = board[0].size();
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i][j] >= '0' && board[i][j] <= '9') maze[i][j] = board[i][j]-'0';
                else if(board[i][j] == 'S' || board[i][j] == 'E') maze[i][j] = 0;
                else  maze[i][j] = -inf;
            }
        }
        for(int i=0; i<=n; i++){
            for(int j=0; j<=m; j++)
                dp[i][j] = {-inf, 0};
        }
        dp[n-1][m-1] = {0, 1};
        for(int i=n-1; i>=0; i--){
            for(int j=m-1; j>=0; j--){
                if(i == n-1 && j == m-1) continue;
                dp[i][j].first = max({dp[i+1][j].first, dp[i][j+1].first, dp[i+1][j+1].first});
                dp[i][j].second = 0;
                if(dp[i+1][j].first == dp[i][j].first){
                    dp[i][j].second += dp[i+1][j].second;
                    dp[i][j].second %= MOD;
                }
                if(dp[i][j+1].first == dp[i][j].first){
                    dp[i][j].second += dp[i][j+1].second;
                    dp[i][j].second %= MOD;
                }
                if(dp[i+1][j+1].first == dp[i][j].first){
                    dp[i][j].second += dp[i+1][j+1].second;
                    dp[i][j].second %= MOD;
                }
                dp[i][j].first += maze[i][j];
                dp[i][j].first = max(-inf, dp[i][j].first);
            }
        }
        if(dp[0][0].first<0 || dp[0][0].second == 0) return {0,0};
        return {dp[0][0].first, dp[0][0].second};
    }
};

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

5291. Find Numbers with Even Number of Digits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int count = 0;
        for(auto num: nums){
            int t = num;
            int rem = 0;
            if(t == 0) continue;
            while(t){
                t /= 10;
                rem++;
            }
            if(rem % 2 == 0) count++;
        }
        return count;
    }
};

5292. Divide Array in Sets of K Consecutive Numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        for(auto i: nums) mp[i]++;
        sort(nums.begin(), nums.end());
        for(int i=0; i<nums.size(); i++){
            int cur = nums[i];
            if(mp.find(cur) == mp.end()) continue;
            for(int j=cur; j<cur+k; j++){
                if(mp.find(j) == mp.end() || mp[j] == 0) return false;
                mp[j]--;
                if(mp[j] == 0) mp.erase(j);
            }
        }
        return mp.size() == 0;
    }
};

5293. Maximum Number of Occurrences of a Substring

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        unordered_map<string, int> subs{};
        int result = 0;
        for(int i=0; i<=s.size()-minSize; i++){
            string sub = s.substr(i, minSize);
            set<char> chars{};
            for(auto c: sub) chars.insert(c);
            if(chars.size() <= maxLetters) result = max(result, ++subs[sub]);
        }
        return result;
    }
};

5294. Maximum Candies You Can Get from Boxes

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 maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
        int result=0; //total number of candies
        vector<int> boxes(initialBoxes.begin(),initialBoxes.end()); //the boxes we have (including both open or not open)
        unordered_set<int> v; //the boxes that we have already visited
        while(true)
        {
            int flag=0; //check if the process ends
            for(int i=(int)boxes.size()-1;i>-1;i--)
            {
                 if(status[boxes[i]]==1&&v.find(boxes[i])==v.end())//is open and not visited yet
                 {
                     flag=1; //the process doesn't end
                     for(int j=0;j<keys[boxes[i]].size();j++) status[keys[boxes[i]][j]]=1; //we use the key to open the boxes
                     for(int j=0;j<containedBoxes[boxes[i]].size();j++) boxes.push_back(containedBoxes[boxes[i]][j]); //we get more boxes
                     v.insert(boxes[i]); //the box has been visited
                     result+=candies[boxes[i]]; //we get the candies
                     boxes.erase(boxes.begin()+i); //the box has been visited, we removed it from the BFS process
                 }
             }
             if(flag==0) break; //if the process ends
        }
        return result;
    }
};

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

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

push(int x), which pushes an integer x onto the stack.
pop(), which removes and returns the most frequent element in the stack.
If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned. 

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 FreqStack {
private:
    unordered_map<int,int> frequencyOfElement;
    unordered_map<int,list<int>> stack;
    int maxFrequency;
public:
    FreqStack() {
        frequencyOfElement.clear();
        stack.clear();
        maxFrequency = 0;
    }
    
    void push(int x) {       
        ++ frequencyOfElement[x];
        stack[ frequencyOfElement[x] ].push_front(x);
        maxFrequency = max(maxFrequency, frequencyOfElement[x]);
    }
    
    int pop() {
        int ans = stack[maxFrequency].front();
        stack[maxFrequency].pop_front();
        if(stack[maxFrequency].empty()){
            stack.erase(maxFrequency);
            -- maxFrequency;
        }
        -- frequencyOfElement[ans];
        return ans;
    }
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 */