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

加密数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string encode(int num) {
        string ans;
        string tmp;
        num++;
        while (num) {
            tmp.push_back(num % 2 == 0 ? '0' : '1');
            num >>= 1;
        }
        for (int i = tmp.size() - 2; i >= 0; i--) {
            ans.push_back(tmp[i]);
        }
        return ans;
    }
};

最小公共区域

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    map<string, string>maps;
    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
        vector<string>v1, v2;
        for(int i = 0; i < regions.size(); ++i){//建立并查集
            string fa = regions[i][0];
            for(int j = 1; j < regions[i].size(); ++j){
                maps[regions[i][j]] = fa;
            }
        }
		//将region1与region2的所有父结点对应放到v1与v2中。
		//然后寻找v1与v2第1个相交的元素
        v1.push_back(region1);
        v2.push_back(region2);
        string tmp = region1;
        while(maps.find(tmp) != maps.end()){
            tmp = maps[tmp];
            v1.push_back(tmp);
        }
        tmp = region2;
        while(maps.find(tmp) != maps.end()){
            tmp = maps[tmp];
            v2.push_back(tmp);
        }
        for(int i = 0; i < v1.size(); ++i){
            if(find(v2.begin(), v2.end(), v1[i]) != v2.end()){
                return v1[i];
            }
        }
        return "";
    }
};

近义词句子

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
vector<string>res, words;
string tmp;
vector<vector<string>>v(15);
void generate(int idx, int n){//DFS生成句子
    if(idx >= n){
        tmp.clear();
        for(int i = 0; i < n; ++i){
            if(i == 0){
                tmp.append(words[i]);
            }
            else{
                tmp.append(" ");
                tmp.append(words[i]);
            }
        }
        res.push_back(tmp);
        return;
    }
    for(auto str:v[idx]){
        words.push_back(str);
        generate(idx + 1, n);
        words.pop_back();
    }
}

class Solution {
public:
    vector<string> generateSentences(vector<vector<string>>& sy, string text) {
        set<string>sets[15];
        for(int i = 0; i < 15; ++i){//全局变量需要重置，不然执行结果与本地不相同
            v[i].clear();
        }
        res.clear();
        words.clear();
        int idx = 0, cnt = -1;
        vector<string>sen;
        for(int i = 0; i < sy.size(); ++i){//根据同义词组，将同义的放到同一个set中
            if(i == 0){
                ++cnt;
                idx =cnt;
            }
            else{
                idx = -1;
                for(int j = 0; j <= cnt; ++j){
                    if(sets[j].find(sy[i][0]) != sets[j].end() || sets[j].find(sy[i][1]) != sets[j].end()){
                        idx = j;
                    }
                }
                if(idx == -1){
                    ++cnt;
                    idx = cnt;
                }
            }
            for(auto str:sy[i]){
                sets[idx].insert(str);
            }
        }
        istringstream s(text);
        string str;
        while(s >> str){//句子拆成单词
            sen.push_back(str);
        }
        for(int i = 0; i < sen.size(); ++i){
            bool flag = false;
            for(int j = 0; j <= cnt; ++j){
                if(sets[j].find(sen[i]) != sets[j].end()){//如果同义词组中找到该词，则将该同义词组中所有元素放到v[i]中
                    flag = true;
                    for(auto iter :sets[j]){
                        v[i].push_back(iter);
                    }
                    break;
                }
            }
            if(!flag){
                v[i].push_back(sen[i]);
            }
        }
        generate(0, sen.size());//DFS生成句子
        return res;
    }
};

不相交的握手

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int h[1001];
    int numberOfWays(int num_people) {
        int n = num_people / 2;
        h[0] = 1;
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j < i; ++j)
                h[i] = (h[i] + 1ll * h[j] * h[i - 1 - j]) % 1000000007;
        return h[n];
    }
};

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

力扣排行榜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Leaderboard {
public:
    map<int, int> a;
    Leaderboard() {
        
    }
    
    void addScore(int playerId, int score) {
        a[playerId] += score;
    }
    
    int top(int K) {
        vector<int> data;
        for (auto it = a.begin(); it != a.end();it++) {
            data.push_back(it->second);
        }
        sort(data.begin(), data.end());
        int ret = 0;
        for (int i = 0;i < K;i++) {
            ret += data[data.size() - i - 1];
        }
        return ret;
    }
    
    void reset(int playerId) {
        a[playerId] = 0;
    }
};

数组变换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> transformArray(vector<int>& arr) {
        vector<int> a = arr;
        vector<int> b;
        int n = arr.size();
        while (1) {
            b = vector(n, 0);
            b[0] = a[0];
            b[n - 1] = a[n - 1];
            for (int i = 1;i < n - 1;i++) {
                if (a[i] < a[i - 1] && a[i] < a[i + 1]) {
                    b[i] = a[i] + 1;
                }
                else if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
                    b[i] = a[i] - 1;
                } else {
                    b[i] = a[i];
                }
            }
            if (a == b) {
                break;
            }
            a = b;
        }
        return a;
    }
};

树的直径

树的直径的解法，两次 BFS

  1. 任取一点 BFS，选择最长路径的节点，假设这个点为 a
  2. 从 aa= 开始 BFS，最长路径就是树的直径
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
class Solution {
public:
    //写个注释，返回值第一维代表最远的点，第二维代表start跟最远点的距离
    pair<int, int> bfs(vector<vector<int>>& e, int start) {
        vector<int> d(e.size(), -1);
        
        queue<int> Q;
        Q.push(start);
        d[start] = 0;
        
        pair<int, int> ret;
        
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            ret.first = x;
            ret.second = d[x];
            for (auto& y : e[x]) {
                if (d[y] == -1) {
                    d[y] = d[x] + 1;
                    Q.push(y);
                }
            }
        }
        return ret;
    }
    
    int treeDiameter(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        vector<vector<int>> e(n, vector<int>());
        for (auto& edge: edges) {
            e[edge[0]].push_back(edge[1]);
            e[edge[1]].push_back(edge[0]);
        }
        
        pair<int, int> p;
        p = bfs(e, 0);
        p = bfs(e, p.first);
        
        return p.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
class Solution {
public:
    int n, dp[105][105];
    int minimumMoves(vector<int>& arr) {
        n = (int)arr.size();
        for (int i = 1; i <= n; ++ i) 
            dp[i][i] = 1;
        
        for (int i = 1; i < n; ++ i) 
            dp[i][i + 1] = arr[i - 1] == arr[i] ? 1 : 2;
        
        for (int len = 3; len <= n; ++ len) {
            for (int i = 1; i + len - 1 <= n; ++ i) {
                int j = i + len - 1;
                dp[i][j] = j - i + 1;
                for (int k = i; k < j; ++ k) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
                if (arr[i - 1] == arr[j - 1]) {
                    dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
                }
            }
        }
        return dp[1][n];
    }
};

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

等差数列中缺失的数字

1
2
3
4
5
6
int missingNumber(vector<int>& arr) {
    // 数组求和
    int sum = accumulate(arr.begin(), arr.end(), 0);
    // 公式求和 - 数组求和
    return (arr.size() + 1) * (arr.front() + arr.back()) / 2 - sum;
}

安排会议日程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
    // 区间排序
    sort(slots1.begin(), slots1.end());
    sort(slots2.begin(), slots2.end());
    int i = 0, j = 0, n1 = slots1.size(), n2 = slots2.size();
    while (i < n1 && j < n2) {
        // 当前对比区间为 第一个人的第 i 个区间，第二个人的第 j 的区间
        // 区间开始为两个人开始的最晚值，区间结束为两个人结束的最早值
        int st = max(slots1[i][0], slots2[j][0]), en = min(slots1[i][1], slots2[j][1]);
        // 重叠区间够会议时间
        if (en >= st + duration) return {st, st+duration};
        // 谁的结束时间比较早，向后移动一位
        if(slots1[i][1] > slots2[j][1]) j++;
        else i++;
    }
    return {};
}

抛掷硬币

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double probabilityOfHeads(vector<double>& prob, int target) {
    int len = prob.size();
    // dp[i][j] 代表    掷了 i 个骰子，正面向上的个数为 j
    vector<vector<double>> dp(len+1, vector<double>(target+1, 0));
    // 初始，掷出 0 的概率为 1
    dp[0][0] = 1.0;s
    for (int i = 1; i <= len; i++) {
        for (int j = min(i, target); j > 0; j--)
            // 递推公式， dp[i][j] = dp[i-1][j] * 当前骰子反面在上的概率 + dp[i-1][j-1] * 当前骰子正面在上的概率
            dp[i][j] = dp[i-1][j] * (1 - prob[i-1]) + dp[i-1][j-1] * prob[i-1];
        // 单独对 0 的情况进行更新
        dp[i][0] = dp[i-1][0] * (1 - prob[i-1]);
    }       
    
    return dp[len][target];
}

分享巧克力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maximizeSweetness(vector<int>& a, int K) {
    // 二分的边界 left = *min_element(a.begin(), a.end());
    // right = accumulate(a.begin(), a.end(), 0) / ( K + 1) + 1;
    int left = 0, right = 1e9 + 7, len = a.size();
    while (left < right) {
        // mid 向上取整，在一般的二分里 left = mid + 1, right = mid
        // 在当前这个二分中 left = mid, right = mid - 1  所以向上取整时，可以防止无限循环
        int mid = (left + right + 1) >> 1, cnt = 0, tem = 0;
        // 计算当前 mid 是否满足
        for (int i = 0; i < len; i++) {
            if (tem + a[i] >= mid) cnt++, tem = 0;
            else tem += a[i];
        }
        // cnt >= K + 1 时  代表当前可以这样拆分
        if (cnt >= K + 1) left = mid;
        else right = mid - 1;
    }
    return left;
}

Posted on | In , |
Words count in article: 973 | Reading time ≈ 6

1260. Shift 2D Grid

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<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int n = grid.size();
        int m = grid[0].size();
        
        while(k>0){
            auto temp = grid;
            
            for(int i=0; i<n; i++){
                for(int j=0; j<m-1; j++){
                    temp[i][j + 1] = grid[i][j];
                }
            }
            
            for(int i=0; i<n-1; i++){
                temp[i+1][0] = grid[i][m-1];
            }
            
            temp[0][0] = grid[n-1][m-1];
            grid = temp;
            k--;
        }
        return grid;
    }
};

1261. Find Elements in a Contaminated Binary Tree

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class FindElements {
public:
    vector<int> hash;
    
    void bfs(TreeNode* root, int val){
        if(root){
            hash.push_back(val);
            if(root->left){
                bfs(root->left, 2*val+1);
            }
            if(root->right){
                bfs(root->right, 2*val+2);
            }
        }
    }
    
    FindElements(TreeNode* root) {
        bfs(root, 0);
    }
    
    bool find(int target) {
        bool flag = false;
        for(int i=0; i<hash.size(); i++){
            if(hash[i] == target){
                flag = true;
                break;
            }
        }
        if(flag) return true;
        return false;
    }
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */

1262. Greatest Sum Divisible by Three

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:
    int maxSumDivThree(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % 3 == 0) return sum;
        else if(sum % 3 == 1){
            return helper(nums, 1, 2, sum);
        }
        else{
            return helper(nums, 2, 1, sum);
        }
    }
    
    int helper(vector<int>& nums, int mod1, int mod2, int sum){
        int min_val = INT_MAX;
        for(int& i: nums){
            if(i%3 == mod1 && i < min_val){
                min_val = i;
            }
        }
        
        int min1 = INT_MAX, min2 = INT_MAX;
        for(int& i: nums){
            if(i%3 == mod2){
                if(i < min1){
                    min2 = min1;
                    min1 = i;
                }
                else if(i < min2){
                    min2 = i;
                }
            }
        }
        if(min1 == INT_MAX || min2 == INT_MAX) return sum-min_val;
        return max(sum-min1-min2, sum-min_val);
    }
};

1263. Minimum Moves to Move a Box to Their Target Location

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
class Solution {
public:
    int m, n;
    vector<vector<int>> dict;
    vector<vector<int>> walk;
    vector<vector<int>> dir{{0,-1}, {0,1}, {1,0}, {-1,0}};
    
    bool isVaild(vector<vector<char>> &grid, int i, int j){
        if(i < 0 || i >= m || j < 0 || j>= n) return false;
        return grid[i][j] != '#';
    }
    
    bool dfs(vector<vector<char>> &grid, int x, int y, int i, int j){
        if(!isVaild(grid, x, y)) return false;
        if(walk[x][y] == 1 || grid[x][y] == '#') return false;
        walk[x][y] = 1; // 记录是否已经走过，用于判断是不是在一直循环某个路
        if(x == i && y == j) return true;
        for(auto &d: dir){
            if(dfs(grid, x+d[0], y+d[1], i, j)) return true;
        }
        return false;
    }
    
    bool canWalk(vector<vector<char>> &grid, int x, int y, int i, int j){
        if(!isVaild(grid, x, y) || !isVaild(grid, i, j)) return false;
        int start = x * n + y, end = i * n + j;
        if(dict[start][end] != -1) return dict[start][end];
        bool ans = dfs(grid, x, y, i, j);
        walk = vector<vector<int>>(m, vector<int>(n, 0));
        return (dict[start][end] = ans);
    }
    
    int minPushBox(vector<vector<char>>& grid) {
        if(grid.empty()) return 0;
        m = grid.size(), n = grid[0].size();
        dict = vector<vector<int>>(m*n, vector<int>(m*n, -1));
        for(int i=0; i<m*n; i++){
            dict[i][i] = 1;
        }
        int start = -1, goal = -1, person = -1;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == 'B') start = i*n+j;
                else if(grid[i][j] == 'T') goal = i*n+j;
                else if(grid[i][j] == 'S') person = i*n+j;
            }
        }
        set<pair<int, int>> visit; 
        walk = vector<vector<int>>(m, vector<int>(n, 0));
        queue<pair<int, int>> q;
        visit.insert({person, start});
        q.push({person, start});
        int ans = 0;
        while(!q.empty()){
            ans += 1;
            int l = q.size();
            for(int i=0; i<l; i++){
                auto f = q.front();
                q.pop();
                int cur = f.second;
                int x = cur/n, y = cur%n;
                int p = f.first;
                grid[x][y] = '#';
                for(auto &d: dir){
                    int bx = x + d[0], by = y + d[1];
                    int px = x - d[0], py = y - d[1];
                    if(isVaild(grid, bx, by) && canWalk(grid, p/n, p%n, px, py) && visit.count({px * n + py, bx * n + by}) == 0){
                        if (bx == goal / n && by == goal % n) return ans;
						visit.insert({ px * n + py, bx * n + by });
						q.push({ px * n + py, bx * n + by });
                    }
                }
                grid[x][y] = '.';
            }
        }
        return -1;
    }
};

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

1252. Cells with Odd Values in a Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        int rem[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++)
                rem[i][j] = 0;
        }
        for(auto& i: indices){
            for(int j=0; j<m; j++) rem[i[0]][j]++;
            for(int j=0; j<n; j++) rem[j][i[1]]++;
        }
        int c = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(rem[i][j] % 2 == 1){
                    c++;
                }
            }
        }
        return c;
    }
};

1253. Reconstruct a 2-Row Binary Matrix

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
class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        vector<vector<int>> temp(2);
        for(int i=0; i<2; i++) temp[i].resize(colsum.size());
        for(int i=0; i<colsum.size(); i++){
            if(colsum[i] == 2){
                if(upper == 0 || lower == 0)
                {
                    vector<vector<int>> ret;
                    return ret;
                }
                temp[0][i] = 1;
                temp[1][i] = 1;
                upper--;
                lower--;
            }
        }
        for(int i=0; i<colsum.size(); i++){
            if(colsum[i] == 1){
                if(upper>0){
                    upper--;
                    temp[0][i] = 1;
                }
                else if(lower>0){
                    lower--;
                    temp[1][i] = 1;
                }
                else
                {
                    vector<vector<int>> ret;
                    return ret;
                }
            }
        }
        if(upper == 0 && lower == 0)
            return temp;
        else{
            vector<vector<int>> ret;
            return ret;
        }
    }
};

1254. Number of Closed Islands

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 fill(vector<vector<int>> & g, int i, int j){
        if(i<0 || j<0 || i>=g.size() || j>=g[i].size() || g[i][j] )
            return 0;
        return (g[i][j] = 1) + fill(g, i+1, j) + fill(g, i, j+1) + fill(g, i-1, j) + fill(g, i, j-1);
    }
    int closedIsland(vector<vector<int>>& g, int res = 0) {
        for(int i=0; i<g.size(); i++){
            for(int j=0; j<g[i].size(); j++){
                if(i * j == 0 || i == g.size()-1 || j == g[i].size()-1)
                    fill(g, i, j);
            }
        }
        for(int i=0; i<g.size(); i++){
            for(int j=0; j<g[i].size(); j++){
                res += fill(g, i, j)>0;
            }
        }
        return res;
    }
};

1255. Maximum Score Words Formed by Letters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int dfs(vector<string> &ws, vector<int> &cnt, vector<int> &score, int i){
        if(i >= ws.size()) return 0;
        auto skipGain = dfs(ws, cnt, score, i+1), gain = 0, formed = 1;
        vector<int> cnt1(begin(cnt), end(cnt));
        for(auto ch: ws[i]){
            if(--cnt1[ch-'a'] < 0) formed = 0;
            gain += score[ch-'a'];
        }
        return max(skipGain, formed ? gain+dfs(ws, cnt1, score, i+1) : 0);
    }
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<int> cnt(26);
        for(auto ch: letters) ++cnt[ch-'a'];
        return dfs(words, cnt, score, 0);
    }
};

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

1247. Minimum Swaps to Make Strings Equal

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 minimumSwap(string A, string B) {
        auto cnt = [&](auto target) -> int {
            return count_if(A.begin(), A.end(), [=](auto c){ return c == target; }) +
                   count_if(B.begin(), B.end(), [=](auto c){ return c == target; });
        };
        auto x = cnt('x'),
             y = cnt('y');
        if (x % 2 || y % 2)
            return -1;
        auto a = 0,
             b = 0;
        for (auto i=0; i < A.size(); ++i) {
            if (A[i] == B[i])
                continue;
            a += A[i] == 'x';
            b += B[i] == 'x';
        }
        return (a / 2) + (b / 2) + ((a % 2) + (b % 2));
    }
};

1248. Count Number of Nice Subarrays

Exactly K times = at most K times - at most K - 1 times

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
       return atMost(nums, k) - atMost(nums, k-1);
    }
    
    int atMost(vector<int> &nums, int k){
        int res = 0;
        int i = 0;
        int n = nums.size();
        for(int j=0; j<n; j++){
            k -= nums[j] % 2;
            while(k < 0) k += nums[i++] % 2;
            res += j-i+1;
        }
        return res;
    }
};

Minimum Remove to Make Valid Parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> st;
        for(auto i = 0; i < s.size(); i++){
            if(s[i] == '(') st.push(i);
            if(s[i] == ')'){
                if(!st.empty()) st.pop();
                else s[i] = '*';
            }
        }
        while(!st.empty()){
            s[st.top()] = '*';
            st.pop();
        }
        s.erase(remove(s.begin(), s.end(), '*'), s.end());
        return s;
    }
};

1250. Check If It Is a Good Array

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool isGoodArray(vector<int>& A) {
        int res = A[0];
        for (int a: A)
            res = gcd(res, a);
        return res == 1;
    }
};

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

1237. Find Positive Integer Solution for a Given Equation

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
/*
 * // This is the custom function interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 * public:
 *     // Returns f(x, y) for any given positive integers x and y.
 *     // Note that f(x, y) is increasing with respect to both x and y.
 *     // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 *     int f(int x, int y);
 * };
 */

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> ret;
        for(int i=1; i<=1000; i++){
            int flag = 0;
            for(int j=1; j<=1000; j++){
                if(customfunction.f(i,j) == z){
                    vector<int> cur;
                    cur.push_back(i);
                    cur.push_back(j);
                    ret.push_back(cur);
                }
                else if(customfunction.f(i,j) > z){
                    flag = 1;
                    break;
                }
            }
        }
        return ret;
    }
};

1238. Circular Permutation in Binary Representation

Gray code

https://cp-algorithms.com/algebra/gray-code.html

i ^ i >> 1 生成格雷码

start ^ i ^ i >> 1 保证第一个和最后一个 只差一个bit

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        vector<int> res;
        for (int i = 0; i < 1 << n; ++i)
            res.push_back(start ^ i ^ i >> 1);
        return res;
    }
};

1239. Maximum Length of a Concatenated String with Unique Characters

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 res = 0;
    int maxLength(vector<string>& arr) {
        vector<int> key(arr.size(), 0);
        for(int i=0; i<arr.size(); i++){
            int key_ = 0;
            for(char c: arr[i]){
                if((key_ & (1<<(c-'a'))) != 0){
                    key_ = INT_MAX;
                    break;
                }
                key_ |= 1 << (c-'a');
            }
            key[i] = key_;
        }
        dfs(key, arr, 0 ,0 , 0);
        return res;
    }
    void dfs(vector<int>& key,vector<string>&arr, int idx, int len, int cur_key){
        res = max(res,len);
        for(int i = idx ; i < key.size() ; i++)
            if((key[i]!= INT_MAX) && (cur_key & key[i]) == 0)
                dfs(key,arr,i+1,len + arr[i].size(), cur_key | key[i]);
    }
};

1240. Tiling a Rectangle with the Fewest Squares

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
class Solution {
public:
    vector<vector<int>> a;
    int tilingRectangle(int n, int m) {
        a = vector<vector<int>>(n, vector<int>(m));
        for(int i=1; ; i++){
            if(dfs(1, 0, n, m, i)) return i;
        }
        return 0;
    }
    bool dfs(int step, int cnt, int n, int m, int k){
        if(cnt == n * m) return true;
        if(step > k) return false;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(a[i][j]) continue;
                for(int l=0; i+l<n && j+l<m && a[i][j+l]==0; l++){
                    for(int ii=0; ii<=l; ii++){
                        for(int jj=0; jj<=l; jj++){
                            a[i+ii][j+jj] = 1;
                        }
                    }   
                    if(dfs(step+1, cnt+(l+1)*(l+1), n, m, k)){
                        return true;
                    }
                    for(int ii=0; ii<=l; ii++){
                        for(int jj=0; jj<=l; jj++){
                            a[i+ii][j+jj] = 0;
                        }
                    }  
                }
                // you will have to fill the first empty cell you find, so if you haven't succeeded, you fail
                return false;
            }
        }
        return false;
    }
};

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

1232. Check If It Is a Straight Line

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& c) {
        if(c.size() <= 2) return true;
        
        double k = ((c[1][1] - c[0][1])*1.0) / ((c[1][0] - c[0][0])*1.0);
        
        for(int i = 2; i<c.size(); i++){
            double cur = ((c[i][1] - c[0][1])*1.0) / ((c[i][0] - c[0][0])*1.0);
            
            if( cur != k ) return false;
        }
        
        return true;
    }
};

1233. Remove Sub-Folders from the Filesystem

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
bool cmp(string& a, string& b){
    return a.size() < b.size();
}

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(), folder.end(), cmp);
        vector<string> ret;
        
        for(auto str: folder){
            bool flag = true;
            
            for(auto retstr: ret){
                bool ff = true;
                int i;
                for(i=0; i<retstr.size(); i++){
                    if(retstr[i] != str[i]){
                        ff = false;
                        break;
                    }
                }
                if(ff && str[i] == '/'){
                    flag = false;
                    break;
                }
                    
            }
            
            if(flag)
                ret.push_back(str);
        }
        return ret;
    }
};

1234. Replace the Substring for Balanced String

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
class Solution {
public:
    int balancedString(string s)
    {
        int targetCounter = s.length() / 4;
        
        vector<int> counters(128, 0);
        
        for (char c: s)
            counters[c]++;
        
        counters['Q'] = counters['Q'] - targetCounter;
        counters['W'] = counters['W'] - targetCounter;
        counters['E'] = counters['E'] - targetCounter;
        counters['R'] = counters['R'] - targetCounter;
        
        if (counters['Q'] == 0 &&
            counters['W'] == 0 &&
            counters['E'] == 0 &&
            counters['R'] == 0)
            return 0;
        
        int left = 0;
        int right = 0;
        int len = s.length() + 1;
        
        while (right < s.length())
        {
            counters[s[right]]--;
            
            ++right;
            
            if (counters['Q'] <= 0 &&
                counters['W'] <= 0 &&
                counters['E'] <= 0 &&
                counters['R'] <= 0)
            {
                while (counters['Q'] <= 0 &&
                       counters['W'] <= 0 &&
                       counters['E'] <= 0 &&
                       counters['R'] <= 0)
                {
                    counters[s[left]]++;

                    ++left;
                }

                len = std::min(len, right - left + 1);
            }
        }
        
        return len;
        
    }
};

1235. Maximum Profit in Job Scheduling

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<vector<int>> jobs;
        for(int i=0; i<n; i++){
            jobs.push_back({endTime[i], startTime[i], profit[i]});
        }
        sort(jobs.begin(), jobs.end());
        map<int, int> dp = {{0, 0}};
        for(auto& job: jobs){
            int cur = prev(dp.upper_bound(job[1]))->second + job[2];
            if(cur > dp.rbegin()->second)
                dp[job[0]] = cur;
        }
        return dp.rbegin()->second;
    }
};

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

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
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(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n <= 0)
            return vector<TreeNode*>();
        return helper(1,n);
    }
    
    vector<TreeNode*> helper(int start, int end){
        if(start > end){
            return {nullptr};
        }
        vector<TreeNode*> res;
        
        for(int i=start; i<=end; i++){
            for(auto leftres: helper(start, i-1))
            {
                for(auto rightres: helper(i+1, end)){
                    TreeNode* node = new TreeNode(i);
                    node->left = leftres;
                    node->right = rightres;
                    res.push_back(node);
                }
            }
        }
        return res;
    }
};

dp:

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
/**
 * 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* CopyTree(TreeNode* root){
        if(!root) return NULL;
        TreeNode* newroot = new TreeNode(root->val);
        newroot->left = CopyTree(root->left);
        newroot->right = CopyTree(root->right);
        return newroot;
    }
    
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> pre;
        pre.push_back({nullptr});
        
        if(n <= 0) return {};
        
        vector<TreeNode*> cur;
        for(int i=1; i<=n; i++){
            for(TreeNode* node: pre){
                TreeNode* root = new TreeNode(i);
                root->left = node;
                cur.push_back(root);
                TreeNode* temp = node;
                while(temp){
                    TreeNode* newroot = new TreeNode(i);
                    if(temp->right){
                        TreeNode* node_right = temp->right;
                        newroot->left = temp->right;
                        temp->right = newroot;
                        TreeNode* newtree = CopyTree(node);
                        temp->right = node_right;
                        temp = temp->right;
                        cur.push_back(newtree);
                    }
                    else{
                        temp->right = newroot;
                        TreeNode* newtree = CopyTree(node);
                        cur.push_back(newtree);
                        temp->right = nullptr;
                        temp = temp->right;
                    }
                    delete newroot;
                }
            }
            pre = cur;
            cur.clear();
        }
        return pre;
    }
};

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

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

1
2
3
4
5
6
7
8
9
10
11
12
Example 1:

Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,1,2,1,1].
Example 2:

Input: [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,4,6].
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
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class NestedIterator {
private:
    stack<NestedInteger> s;
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        int len = nestedList.size();
        int i = 0;
        
        for(i = len-1; i>=0; i--){
            s.push(nestedList[i]);
        }
    }

    int next() {
        NestedInteger temp = s.top();
        s.pop();
        return temp.getInteger();
    }

    bool hasNext() {
        while(!s.empty()){
            NestedInteger temp = s.top();
            if(temp.isInteger())
                return true;
            else{
                s.pop();
                vector<NestedInteger> List = temp.getList();
                int len = List.size();
                int i = 0;
                
                for(i = len-1; i>=0; i--){
                    s.push(List[i]);
                }
            }
        }
        return false;
    }
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */