发表更新LeetCode / 算法21 分钟读完 (大约3190个字)

LeetCode-21

1234. 替换子串得到平衡字符串

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:
    bool isBalance(int* count, int avg) {
        return count['Q'] <= avg && count['R'] <= avg && count['E'] <= avg && count['W'] <= avg;
    }
    int balancedString(string s) {
        int count[128] = {0};
        for (char c : s) {
            count[c]++;
        }
        int len = s.length();
        int avg = len / 4;

        if (isBalance(count, avg)) {
            return 0;
        }
        int res = len;
        for (int l = 0, r = 0; l < len; l++) {
            while (r < len && !isBalance(count, avg)) {
                count[s[r]]--;
                r++;
            }
            if (!isBalance(count, avg)) {
                break;
            }
            res = min(res, r - l);
            count[s[l]]++;
        }
        return res;
    }
};

1138. 字母板上的路径

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:
    string alphabetBoardPath(string target) {
        int x = 0, y = 0;
        string res = "";
        for(char c : target) {
            int next_x = getX(c), next_y = getY(c);
            char step_x = 'L', step_y = 'U';
            int diff_x = x - next_x, diff_y = y - next_y;
            
            if(next_x > x) {
                step_x = 'R';
                diff_x = -diff_x;
            }
            if(next_y > y) {
                step_y = 'D';
                diff_y = - diff_y;
            }
            if(next_y == 5) {
                for(int i = 0; i < diff_x; i++) {
                    res += step_x;
                }
                for(int i = 0; i < diff_y; i++) {
                    res += step_y;
                }

            } else {
                for(int i = 0; i < diff_y; i++) {
                    res += step_y;
                }
                for(int i = 0; i < diff_x; i++) {
                    res += step_x;
                }
            }
            
            res += "!";
            x = next_x;
            y = next_y;
        }
        return res;
    }
    int getX(char c) {
        return (c - 'a') % 5;
    }
    int getY(char c) {
        return (c - 'a') / 5;
    }
};

如果默认先纵向走，再横向走，那么当从外部到z时，需要先横向走再纵向走
如果默认先横向走，再纵向走，那么当从z到外部时，需要先纵向走再横向走

2335. 装满杯子需要的最短总时长

阅读更多
发表更新LeetCode / 算法7 分钟读完 (大约1111个字)

LeetCode-20

1758. 生成交替二进制字符串的最少操作数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minOperations(string s) {
        int len = s.size();
        return min(cal(s, len, true), cal(s, len, false));
    }
    int cal(const string& s, int len, bool flag) {
        int count = 0;
        for(int i = 0; i < len; i++) {
            if(flag && s[i] == '0' || !flag && s[i] == '1') {
                count++;
            }
            flag = !flag;
        }
        return count;
    }
};

813. 最大平均值和的分组

超时暴搜

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 len = 0;
    vector<int> sum;
    double largestSumOfAverages(vector<int>& nums, int k) {
        len = nums.size();
        sum = vector<int>(len+1, 0);
        for(int i = 1; i <= len; i++) {
            sum[i] = nums[i-1] + sum[i-1];
        }
        return search(nums, k, 1, 1, 0, 0);
    }
    double search(vector<int>& nums, int k, int i, int K, double left_value, int last_j) {
        if(k == K || i == len) {
            return left_value + (sum[len] - sum[last_j] + 0.0) / (len - last_j);
        }
        return max(search(nums, k, i+1, K+1, left_value + (sum[i] - sum[last_j] + 0.0)/(i-last_j), i), search(nums, k,i+1, K, left_value, last_j));
    }

    double max(double a, double b) {
        return a > b ? a : b;
    }
};

昨天第一个思路是用排序，找出最大的m个数，这m个数恰好将数组分成k个部分，发现不可行。
然后暴力搜索，超时了，暴搜时考虑添加隔板，其中left_value表示当前搜索下标i之前的分组平均值

阅读更多
发表更新LeetCode / 算法3 分钟读完 (大约387个字)

LeetCode-19

1710. 卡车上的最大单元数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(boxTypes.begin(), boxTypes.end(), [](vector<int>& x, vector<int>& y)->bool {
            return x[1] > y[1];
        });
        int n = boxTypes.size();
        int ret = 0;
        for(int i = 0; i < n; i++) {
            if(truckSize) {
                ret += min(truckSize, boxTypes[i][0])*boxTypes[i][1];
                truckSize -= min(truckSize, boxTypes[i][0]);
            } else {
                break;
            }
        }
        return ret;
    }
};
// 50 + 27 + 14 = 91

简单题，排个序就行

775. 全局倒置与局部倒置

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isIdealPermutation(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (abs(nums[i] - i) > 1) {
                return false;
            }
        }
        return true;
    }
};

最开始想复杂了，想用差分数组统计个数

阅读更多
发表更新LeetCode / 算法30 分钟读完 (大约4482个字)

LeetCode-dp

leetcode 101的动态规划专题

基本动态规划：一维

70. 爬楼梯

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

dp数组表示上n层楼有几种可能
转移方程是 $ dp[i] = dp[i-1] + dp[i-2] $
上到第i层有可能从第i-1层或i-2层上来，则上到i层的可能数目就是 $ dp[i-1] + dp[i-2] $
由于dp[i]只需要前两个数的数据，所以可以优化掉dp数组，用两个变量代替，节省数组空间

198. 打家劫舍

阅读更多
发表更新LeetCode / 算法23 分钟读完 (大约3439个字)

LeetCode-18

1668. 最大重复子字符串

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:
    int maxRepeating(string sequence, string word) {
        int len1 = sequence.size();
        int len2 = word.size();
        int maxk = 0, k = 0;
        for(int i = 0; i < len1;) {
            bool flag = true;
            int next = i+1;
            bool flag1 = false;
            for(int j = 0; j < len2; j++) {
                if(sequence[i+j] != word[j]) {
                    flag = false;
                    break;
                }
                if(!flag1 && j != 0 && sequence[i+j] == word[0]) {
                    next = i+j;
                    flag1=true;
                }
            }
            // cout << i << " " << k << " " << maxk << endl;
            if(flag) {
                k++;
                i += len2;
            } else {
                maxk = max(k, maxk);
                if(k == 0) {
                    i+=1;
                } else {
                    i = i-len2+1;
                }
                k = 0;
            }
            // cout << i << endl;
        }
        return max(maxk, k);
    }
};

笨方法，从右向左找，适当回溯

754. 到达终点数字

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int n = (sqrt(8.0*target+1)-1)/2; //8.0,防止int溢出
        int sum = (n+1)*n/2;
        if(sum == target) {
            return n;
        }
        int diff = target-sum;
        if((n % 2 == 1 && diff % 2 == 0) || (n % 2 == 0 && diff % 2 == 1)) {
            n += 1;
        } else if(diff %2 == 1) {
            n += 2;
        } else {
            n += 3;
        }
        return n;
    }
};
阅读更多
发表更新LeetCode / 算法7 分钟读完 (大约1043个字)

LeetCode-17

1662. 检查两个字符串数组是否相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
        return join(move(word1)) == join(move(word2));
    }
    string join(vector<string>&& word) {
        string s;
        int len = word.size();
        if(len <= 0) return s;
        for(int i = 0; i < len-1; i++) {
            s += word[i];
        }
        s+=word[len-1];
        return s;
    }
};

实现一个join函数就好了

481. 神奇字符串

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 magicalString(int n) {
        int bit = 3;
        int count = 1;
        bool q[100005] = {false};
        int queue_front = 0;
        int queue_rear = 0;
        bool cur=1;
        bool gen=0;
        while(bit < n) {
            bit += cur+1;
            q[queue_front++] = gen;
            if(cur) {
                q[queue_front++] = gen;
            }
            gen=1-gen;
            count+=gen?cur+gen:0;
            cur = q[queue_rear++];
        }
        return count -(bit>n && gen);
    }
};

关键在于想清楚如何生成这个神奇字符串，题目中说，s的前几个字符是12211
1生成1,s=1
2生成22，因为前一个1生成了1，这个2不能也生成1,s=122
2生成11，因为前一个2生成了2，这个2不能也生成2,s=12211
1生成2，前一个2生成了1，这个1就只能生成2了,s=122112
1生成1,s=1221121
2生成22,s=122112122

阅读更多
发表更新LeetCode / 算法12 分钟读完 (大约1774个字)

LeetCode-16

934. 最短的桥

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
class Solution {
public:

    int indexMap[105][105] = {0}; //岛屿点，对应一个岛
    int n;
    int edgex[105*105] = {0};
    int edgey[105*105] = {0};
    int edgei[105*105] = {0};
    int edgej[105*105] = {0};
    int edgecount = 0;
    int edgeicount = 0;
    int shortestBridge(vector<vector<int>>& grid) {
        n = grid.size();
        int islandCount = 0;
        int p1x,p1y;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1 && indexMap[i][j] == 0) {
                    ++islandCount;
                    dfs(grid, i, j, islandCount);
                }
            }
        }
        int min=INT_MAX;
        for(int i = 0; i < edgecount; i++) {
            for(int j = 0; j < edgeicount; j++) {
                int path = abs(edgex[i]-edgei[j]) + abs(edgey[i] - edgej[j]) - 1;
                if(min >= path) {
                    min = path;
                }
            }
        }
        return min;
    }
    void dfs(vector<vector<int>>& grid, int x, int y, int index) {
        if(x < 0 || y < 0 || x >= n || y >= n) return;
        if(indexMap[x][y] != 0 || grid[x][y] != 1) return;
        indexMap[x][y] = index;
        bool flag = (y-1 >= 0 && grid[x][y-1] == 0) || (y+1 < n && grid[x][y+1] == 0) || (x+1 < n && grid[x+1][y] == 0) || (x-1 >= 0 && grid[x-1][y] == 0);
        dfs(grid, x, y-1, index);
        dfs(grid, x, y+1, index);
        dfs(grid, x+1, y, index);
        dfs(grid, x-1, y, index);
        if(flag) {
            if(indexMap[x][y]==1) {
                edgex[edgecount]=x;
                edgey[edgecount]=y;
                edgecount++;
            } else if(indexMap[x][y]==2) {
                edgei[edgeicount]=x;
                edgej[edgeicount]=y;
                edgeicount++;
            }
        }
    }
};

和之前写的一道题有点像，827. 最大人工岛
827. 最大人工岛我先dfs找到所有连通子图和包围岛的0点，然后找这些点中有无同时包围多个岛的，把他们的面积加起来取最大值

这道题也可以使用相同的方法，找到每个岛屿的边界点，然后计算边界点的距离(只有两个岛，两个岛之间肯定是可以连通的，且不管使用那条途径，最短距离一定是 $ abs(x_1 - x_2) + abs(y_1-y_2)-1 $)

看答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    void dfs(int x, int y, vector<vector<int>>& grid, queue<pair<int, int>> &qu) {
        if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] != 1) {
            return;
        }
        qu.emplace(x, y);
        grid[x][y] = -1;
        dfs(x - 1, y, grid, qu);
        dfs(x + 1, y, grid, qu);
        dfs(x, y - 1, grid, qu);
        dfs(x, y + 1, grid, qu);
    }

    int shortestBridge(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue<pair<int, int>> qu;
                    dfs(i, j, grid, qu);
                    int step = 0;
                    while (!qu.empty()) {
                        int sz = qu.size();
                        for (int i = 0; i < sz; i++) {
                            auto [x, y] = qu.front();
                            qu.pop();
                            for (int k = 0; k < 4; k++) {
                                int nx = x + dirs[k][0];
                                int ny = y + dirs[k][1];
                                if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                                    if (grid[nx][ny] == 0) {
                                        qu.emplace(nx, ny);
                                        grid[nx][ny] = -1;
                                    } else if (grid[nx][ny] == 1) {
                                        return step;
                                    }
                                }
                            }
                        }
                        step++;
                    }
                }
            }
        }
        return 0;
    }
};
阅读更多
发表更新LeetCode / 算法11 分钟读完 (大约1618个字)

LeetCode-14

927. 三等分

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
class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {
        int sum = countOne(arr);
        int len = arr.size();
        if(sum % 3 != 0) {
            return {-1,-1};
        }
        if(sum == 0) {
            return {0, len -1};
        }

        int p1,p2,p3;
        p1 = p2 = p3 = 0;
        int i = 0;
        int cur = 0;
        while(i < len) {
            if(arr[i] == 1) {
                if(cur == 0) {
                    p1 = i;
                } else if(cur == sum/3) {
                    p2 = i;
                } else if(cur == 2*sum/3) {
                    p3 = i;
                }
                cur++;
            }
            i++;
        } //把1平均分成3份，p1 p2 p3分别找到三段的第一个1的位置
        // printf("%d %d %d\n", p1, p2, p3);
        int x = p1,y = p2,z = p3;
        int farclen = len - p3;
        if(p1 + farclen > p2 || p2 + farclen > p3) {
            return {-1, -1};
        }
        while(x < p2 && y < p3 && z < len) {
            if(arr[x] != arr[y] || arr[y] != arr[z]) {
                return {-1, -1};
            }
            x++;y++;z++;
        }
        // printf("%d %d %d\n", x, y, z);
        return {p1+farclen-1, p2+farclen};
    }
    int
     countOne(vector<int>& arr) {
        int count = 0;
        for(int a : arr) {
            count += a;
        }
        return count;
    }
};

难，看懂解析思路后才写出来的

刚开始的思路是找0，把1分成了n段，取n/3 , 2n/3和 n段后面的0，然后向右移动双指针比较

后来发现有超级长的输入，超时了

解析的思路与我刚好相反，先数1的个数，如果是0或者不能被3整除，说明不能分成三段

1的个数为n，找到第0 n/3 2n/3个1，记为p1, p2, p3

p3到后末尾的长度就是三个子串的长度，如果p1 或 p2 + 字串长度分别大于p2 p3，说明无解

然后向后比较，若后面的数完全相同则有解

阅读更多
发表更新LeetCode / 算法29 分钟读完 (大约4309个字)

LeetCode-15

904. 水果成篮

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 totalFruit(vector<int>& fruits) {
        int len = fruits.size();
        vector<int> v(len);
        int i = 0;
        int cur = fruits[i];
        i++;
        int max_diff = 1;
        int typea = fruits[0], typeb = -1, typec = -1;
        vector<int> last(len+1);
        int curr = 0;
        int j = 1;
        while(j < len) {
            while(j < len && fruits[j] == fruits[curr]) {
                j++;
            }
            last[j] = curr;
            curr = j;
            j++;
        }
        while(i < len) {
            int diff = 1;
            typeb = typec = -1;
            while(i < len) {
                if(fruits[i] != typea && fruits[i] != typeb) {
                    if(typeb == -1) {
                        typeb = fruits[i];
                    } else if(typec == -1) {
                        typec = fruits[i];
                    }
                }
                if(typec == -1) {
                    diff++;
                } else {
                    break;
                }
                i++;
            }
            max_diff = diff > max_diff ? diff : max_diff;
            if(i-1 >= 0 && i < len){
                typea = fruits[i-1];
                i = last[i]+1;
            }
        }
        return max_diff;
    }
};

想法很简单，就是从左往右遍历，数当前遇到了几种水果，当遇到第三种水果后，更新一下装入水果的最大值，三种水果记录为typea, typeb, typec
然后回溯，找到前一个节点在左侧最后一个typea后第一次出现的位置（其实也是typea最后出现的位置的后两个位置）

优化(空间，放弃last数组)

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 totalFruit(vector<int>& fruits) {
        int len = fruits.size();
        vector<int> v(len);
        int i = 0;
        int cur = fruits[i];
        i++;
        int max_diff = 1;
        int typea = fruits[0], typeb = -1, typec = -1;
        while(i < len) {
            int diff = 1;
            typeb = typec = -1;
            int lasta = i-1, lastb = 0;
            while(i < len) {
                if(fruits[i] != typea && fruits[i] != typeb) {
                    if(typeb == -1) {
                        typeb = fruits[i];
                    } else if(typec == -1) {
                        typec = fruits[i];
                    }
                }
                if(fruits[i] == typea) {
                    lasta = i;
                } else if(fruits[i] == typeb) {
                    lastb = i;
                }
                if(typec == -1) {
                    diff++;
                } else {
                    break;
                }
                i++;
            }
            max_diff = diff > max_diff ? diff : max_diff;
            if(i-1 >= 0 && i < len){
                if(fruits[i-1] == typea) {
                    i = lastb + 2;
                } else if(fruits[i-1] == typeb) {
                    typea = typeb;
                    i = lasta + 2;
                }
                // printf("%d, %d, %d\n", i, lasta, lastb);
            }
        }
        return max_diff;
    }
};

1441. 用栈操作构建数组

阅读更多
发表更新LeetCode / 算法17 分钟读完 (大约2568个字)

LeetCode-13

1640. 能否连接形成数组

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:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        int arr_map[105] = {0};
        int len_arr = arr.size();
        for(int i = 0; i < len_arr; i++) {
            arr_map[arr[i]] = i+1;
        }
        int pie_len = pieces.size();
        for(int i = 0; i < pie_len; i++) {
            int i_len = pieces[i].size();
            int diff = arr_map[pieces[i][0]];
            if(diff == 0) {
                return false;
            }
            for(int j = 1; j < i_len; j++) {
                if(diff != arr_map[pieces[i][j]] - j) {
                    return false;
                }
            }
        }
        return true;
    }
};

4ms，和最快的思路刚好相反，用map存储arr的index，最快的思路是反过来，用map存一个piece的第一个index

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:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        int arr_map[105] = {0};
        int len_arr = arr.size();
        int pie_len = pieces.size();
        for(int i = 0; i < pie_len; i++) {
            arr_map[pieces[i][0]] = i+1;
        }
        int i = 0;
        while(i < len_arr) {
            int row = arr_map[arr[i]];
            if(row == 0) return false;
            vector<int>& subv = pieces[row-1];
            int i_len = subv.size();
            for(int j = 0; j < i_len; j++, i++) {
                if(arr[i] != subv[j]) {
                    return false;
                }
            }
        }
        return true;
    }
};

707. 设计链表

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
struct List {
    List *next;
    int val;
    List(int val0, List* next0 = nullptr):val(val0), next(next0) {}
};

class MyLinkedList {
private:
    List *root;
    List *tail;
    int size;
    inline List* getNode(int& index) {
        List *move = root;
        while(index > 0 && move->next != nullptr) {
            move = move->next;
            index--;
        }
        return move;
    }
public:
    MyLinkedList() {
        root = new List(0);
        tail = root;
        size = 0;
    }
    
    int get(int index) {
        List *move = getNode(index);
        return (move->next == nullptr) ? -1 : move->next->val;
    }
    
    void addAtHead(int val) {
        List* node = new List(val, root->next);
        root->next = node;
        if(root == tail) {
            tail = node;
        }
        size++;
    }
    
    void addAtTail(int val) {
        List* node = new List(val, tail->next);
        tail->next = node;
        tail = node;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        List *move = getNode(index);
        if(index > 0) {
            return;
        }
        List* node = new List(val, move->next);
        move->next = node;
        if(move == tail) {
            tail = node;
        }
        size++;
    }
    
    void deleteAtIndex(int index) {
        List *move = getNode(index);
        List *target = move->next;
        if(target != nullptr)  {
            move->next = target->next;
            if(target == tail) {
                tail = move;
            }
            delete target;
            size--;
        }
    }
};
阅读更多
关注我

链接

分类

最新文章

归档

标签

6.8242
Android1
Android FrameWork1
Android 高级开发瓶颈突破系列课11
Android-官方文档1
Android-官方源码6
Android面试查漏补缺2
C/C++1
Flutter1
Java基础1
Kotlin-Android21
Kotlin-Android 实习25
LeetCode45
LeetCode 1013
LeetCode周赛1
Linux/UNIX系统编程手册38
OI KIWI2
OS4
PAT-(Advanced-Level)-Practice2
PAT-(Basic-Level)-Practice44
blockchain1
fedfab13
gallery1
geth1
git1
gradle1
hexo2
linux2
misc1
projects1
shell2
刷题2
动态规划1
多线程1
排序1
数据库2
牛客2
算法43
×