LeetCode 75

备战夏令营机试，创建此贴记录题解，激励刷题打卡。

1768. 交替合并字符串

书写格式类似于归并排序

 1class Solution {
 2public:
 3    string mergeAlternately(string word1, string word2) {
 4        string res = "";
 5        
 6        // 交替合并公共长度
 7        int i = 0;
 8        while(i < word1.size() && i < word2.size()) {
 9            res += word1[i];
10            res += word2[i];
11            i++;
12        }
13
14        // 收尾
15        while(i < word1.size()) res += word1[i++];
16        while(i < word2.size()) res += word2[i++];
17
18        return res;
19    }
20};

1071. 字符串的最大公因子

 1class Solution {
 2public:
 3    string gcdOfStrings(string str1, string str2) {
 4        int len = str1.size();
 5        if(str1.size() > str2.size()) swap(str1, str2);
 6        
 7        // 求最大，从大到小枚举长度
 8        for(int i = len; i >= 1; i--) {
 9            // 剪枝
10            if(str1.size() % i || str2.size() % i) continue;
11    
12            string p = str1.substr(0, i);
13            bool st = true;
14
15            // 判断 p 能否除尽 str1，不能除尽就标记
16            for(int j = 0; j + i - 1 < str1.size(); j += i)
17                if(str1.substr(j, i) != p) {
18                    st = 0;
19                    break;
20                }
21
22            // 判断 p 能否除尽 str2
23            for(int j = 0; j + i - 1 < str2.size(); j += i)
24                if(str2.substr(j, i) != p) {
25                    st = 0;
26                    break;
27                }
28
29            // 都能除尽返回之大公因子串
30            if(st) return p;
31        }
32        return "";
33    }
34};

1431. 拥有最多糖果的孩子

 1class Solution {
 2public:
 3    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
 4        // 求出当前最多糖果数
 5        int maxc = 0;
 6        for(int i = 0; i < candies.size(); i++)
 7            maxc = max(maxc, candies[i]);
 8        
 9        // 遍历
10        vector<bool> res;
11        for(int i = 0; i < candies.size(); i++) {
12            if(candies[i] + extraCandies >= maxc)
13                res.push_back(true);
14            else
15                res.push_back(false);
16        }
17        return res;
18    }
19};

605. 种花问题

 1class Solution {
 2public:
 3    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
 4        // 改变数组处理边界问题
 5        flowerbed.insert(flowerbed.begin(), 0); // 从 vector 容器头部插入
 6        flowerbed.push_back(0);
 7        
 8        // 枚举判断，满足情况就种一朵花
 9        for(int i = 1; i < flowerbed.size() - 1; i++) {
10            if(flowerbed[i] == 0 && flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
11                flowerbed[i] = 1;
12                n--;
13            }
14        }
15
16        return n <= 0;
17    }
18};

345. 反转字符串中的元音字母

理解题面：找出这个串种的元音字母，翻转后替换原有的元音序列

 1class Solution {
 2public:
 3    string reverseVowels(string s) {
 4        string ans = "";
 5        
 6        for(int i = 0; i < s.size(); i++)
 7            if(s[i] == 'a' || s[i] == 'A' || s[i] == 'e' || s[i] == 'E' || 
 8            s[i] == 'i' || s[i] == 'I' || s[i] == 'o' || s[i] == 'O' || 
 9            s[i] == 'u' || s[i] == 'U')
10                ans += s[i];
11        
12        reverse(ans.begin(), ans.end());
13
14        int j = 0;
15        for(int i = 0; i < s.size(); i++) {
16            if(s[i] == 'a' || s[i] == 'A' || s[i] == 'e' || s[i] == 'E' || 
17            s[i] == 'i' || s[i] == 'I' || s[i] == 'o' || s[i] == 'O' || 
18            s[i] == 'u' || s[i] == 'U') {
19                s[i] = ans[j++];
20            }
21        }
22
23        return s;
24    }
25};

283. 移动零 $\bigstar$

 1class Solution {
 2public:
 3    void moveZeroes(vector<int>& nums) {
 4        int l = 0, r = 0;
 5
 6        // r 寻找非零数，找到一个非零数挪到最前边
 7        // l 从 0 开始
 8        for(int r = 0; r < nums.size(); r++) {
 9            if(nums[r]) {
10                nums[l++] = nums[r];
11            }
12        }
13        
14        // 补 0 
15        while(l < nums.size()) {
16            nums[l++] = 0;
17        }
18    }
19};

392. 判断子序列

法一

 1class Solution {
 2public:
 3    bool isSubsequence(string s, string t) {
 4        if(s.size() == 0) return true;
 5        if(s.size() > t.size()) return false;
 6
 7        int j = 0;
 8        for(int i = 0; i < t.size(); i++) {
 9            if(s[j] == t[i]) j++;
10        }
11
12        return j == s.size();
13    }
14};

法二

 1class Solution {
 2public:
 3    bool isSubsequence(string s, string t) {
 4        if(s.size() == 0) return true;
 5        if(s.size() > t.size()) return false;
 6
 7        int i = 0, j = 0;
 8        while(i < t.size() && j < s.size()) {
 9            if(s[j] == t[i]) j++;
10            i++;
11        }
12
13        return j == s.size();
14    }
15};

1732. 找到最高海拔

 1class Solution {
 2public:
 3    int largestAltitude(vector<int>& gain) {
 4        int res = 0;
 5        int ans = 0;
 6
 7        for(int i = 0; i < gain.size(); i++) {
 8            res += gain[i];
 9            ans = max(ans, res);
10        }
11
12        return ans;
13    }
14};

724. 寻找数组的中心下标

 1class Solution {
 2public:
 3    int pivotIndex(vector<int>& nums) {
 4        int n = nums.size();
 5        vector<int> ans(n + 1);
 6
 7        ans[0] = 0;
 8        for(int i = 1; i <= n; i++)
 9            ans[i] = nums[i - 1];
10
11        for(int i = 1; i <= n; i++)
12            ans[i] += ans[i - 1];
13
14        for(int i = 1; i <= n; i++)
15            if(ans[i - 1] == ans[n] - ans[i])
16                return i - 1;
17
18        return -1;
19    }
20};

1207. 独一无二出现的次数

 1class Solution {
 2public:
 3    bool uniqueOccurrences(vector<int>& arr) {
 4        unordered_map<int, int> cnt1;
 5
 6        for(int i = 0; i < arr.size(); i++)
 7            cnt1[arr[i]] = 0;
 8
 9        for(int i = 0; i < arr.size(); i++)
10            cnt1[arr[i]]++;
11
12        unordered_map<int, int> cnt2;
13        
14        for(auto p : cnt1) {
15            cnt2[p.second] = 0;
16        }
17
18        for(auto p : cnt1) {
19            cnt2[p.second]++;
20            if(cnt2[p.second] > 1) return false;
21        }
22
23        return true;
24    }
25};

746. 使用最小花费爬楼梯

 1class Solution {
 2public:
 3    int minCostClimbingStairs(vector<int>& cost) {
 4        int n = cost.size();
 5
 6        vector<int> dp(n + 1);
 7
 8        dp[0] = dp[1] = 0;
 9        for(int i = 2; i <= n; i++)
10            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
11
12        return dp[n];
13    }
14};

238. 除自身意外数组的乘积

预处理前缀和与后缀和，注意边界。

除去 i 下标元素的乘积 = 0 至 i - 1 区间的前缀和 * i + 1 至 n - 1 区间的后缀和。

 1class Solution {
 2public:
 3    vector<int> productExceptSelf(vector<int>& nums) {
 4        int n = nums.size();
 5        vector<int> L(n + 1);
 6        vector<int> R(n + 1);
 7
 8        L[0] = 1;
 9        for(int i = 1; i <= n; i++)
10            L[i] = L[i - 1] * nums[i - 1];
11        
12        R[n] = 1;
13        for(int i = n - 1; i >= 0; i--)
14            R[i] = R[i + 1] * nums[i];
15
16        vector<int> ans;
17
18        for(int i = 1; i <= nums.size(); i++)
19            ans.push_back(L[i - 1] * R[i]);
20
21        return ans;
22    }
23};

334. 递增三元子序列

预处理开头至每个元素区间内的最小值，和每个元素至结尾区间内的最大值。
遍历每个元素的大小与左区间最小值和右区间最大值进行比较。

 1class Solution {
 2public:
 3    bool increasingTriplet(vector<int>& nums) {
 4        if(nums.size() < 3) return false;
 5
 6        vector<int> minNum(nums.size());
 7        minNum[0] = nums[0];
 8        for(int i = 1; i < nums.size(); i++)
 9            minNum[i] = min(minNum[i - 1], nums[i]);
10
11        vector<int> maxNum(nums.size());
12        maxNum[nums.size() - 1] = nums[nums.size() - 1];
13        for(int i = nums.size() - 2; i >= 0; i--)
14            maxNum[i] = max(maxNum[i + 1], nums[i]);
15
16        for(int i = 1; i < nums.size() - 1; i++)
17            if(nums[i] > minNum[i - 1] && nums[i] < maxNum[i + 1])
18                return true;
19        
20        return false;
21    }
22};

443. 压缩字符串

 1class Solution {
 2public:
 3    int compress(vector<char>& chars) {
 4        vector<char> res;
 5
 6        for(int i = 0, j = 0; i < chars.size(); i++) {
 7            j = i;
 8            // 双指针 i 指向相同元素开头，j 指向相同元素结尾
 9            while(j < chars.size() && chars[i] == chars[j]) j++;
10            int len = j - i;
11            res.push_back(chars[i]);
12            
13            if(len > 1) {
14                string s = to_string(len);
15                for(int i = 0; i < s.size(); i++)
16                    res.push_back(s[i]);
17            }
18
19            i = j - 1;
20        }
21
22        chars = res;
23        return res.size();
24    }
25};

11. 盛最多水的容器

木桶容量由短板决定, 移动长板的话, 水面高度不可能再上升, 而宽度变小了, 所以只有通过移动短板, 才有可能使水位上升。

 1class Solution {
 2public:
 3    int maxArea(vector<int>& height) {
 4        int i = 0, j = height.size() - 1;
 5        int res = -1;
 6
 7        while(i < j) {
 8            res = max(res, min(height[i], height[j]) * (j - i));
 9
10            if(height[i] > height[j]) j--;
11            else i++;
12        }
13
14        return res;
15    }
16};

1137. 第 N 个泰波那契数

 1class Solution {
 2public:
 3    int tribonacci(int n) {
 4        if(n == 0) return 0;
 5        if(n <= 2) return 1;
 6        
 7        vector<int> dp(n + 1);
 8
 9        dp[0] = 0, dp[1] = dp[2] = 1;
10
11        for(int i = 3; i <= n; i++)
12            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
13
14        return dp[n];
15    }
16};

1679. K 和数对的最大数目

哈希做法

 1class Solution {
 2public:
 3    int maxOperations(vector<int>& nums, int k) {
 4        int res = 0;
 5        unordered_map <int, int> cnt;
 6        
 7        for(auto num : nums) {
 8            if(cnt[k - num] > 0) {
 9                res++;
10                cnt[k - num]--;
11            }
12            else {
13                cnt[num]++;
14            }
15        }
16
17        return res;
18    }
19};

双指针做法

 1class Solution {
 2public:
 3    int maxOperations(vector<int>& nums, int k) {
 4        int res = 0;
 5
 6        sort(nums.begin(), nums.end());
 7
 8        int i = 0, j = nums.size() - 1;
 9        
10        while(i < j) {
11            int sum = nums[i] + nums[j];
12            if(sum == k) {
13                res++;
14                i++;
15                j--;
16            } else if(sum > k) j--;
17            else i++;
18        }
19
20        return res;
21    }
22};

494. 目标和

 1class Solution {
 2public:
 3    int cnt = 0;
 4
 5    // u 表示枚举到的位数
 6    // sum 表示当前位数的表达式之和
 7    void dfs(vector<int>& nums, int target, int u, int sum) {
 8        if (u == nums.size()) {
 9            if(sum == target) cnt++;
10        } else {
11            dfs(nums, target, u + 1, sum + nums[u]);
12            dfs(nums, target, u + 1, sum - nums[u]);
13        }
14    }
15
16    int findTargetSumWays(vector<int>& nums, int target) {
17        dfs(nums, target, 0, 0);
18        return cnt;
19    }
20};

643. 子数组最大平均数 I

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

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

 1class Solution {
 2public:
 3    bool check(char a) {
 4        if(a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
 5            return true;
 6        return false;
 7    }
 8
 9    int maxVowels(string s, int k) {
10        int sum = 0;
11        for(int i = 0; i < k; i++)
12            if(check(s[i]))
13                sum++;
14
15        int res = sum;
16        for(int i = k; i < s.size(); i++) {
17            if(check(s[i - k])) sum--;
18            if(check(s[i])) sum++;
19            res = max(res, sum);
20        }
21
22        return res;
23    }
24};

1004. 最大连续 1 的个数 III

 1class Solution {
 2public:
 3    /*
 4        cnt 记录当前区间中 0 的个数
 5        res 记录区间中不超过 k 个零的前提下，区间的最大长度
 6        i 是区间右端点
 7        区间中 0 的数量大于 k 之后，就要从左边进行收缩，直到区间内 0 个数小于等于 k
 8    */
 9    int longestOnes(vector<int>& nums, int k) {
10        int res = 0;
11        for(int i = 0, j = 0, cnt = 0; i < nums.size(); i++) {
12            if(nums[i] == 0) cnt++;
13
14            while(cnt > k) {
15                if(nums[j] == 0) cnt--;
16                j++;
17            }
18
19            res = max(res, i -j + 1);
20        }
21
22        return res;
23    }
24};

2390. 从字符串中移除星号

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

735. 小行星碰撞

 1class Solution {
 2public:
 3    vector<int> asteroidCollision(vector<int>& asteroids) {
 4        stack<int> s;
 5        for(auto c : asteroids) {
 6            if (c < 0) {
 7                while(!s.empty() && s.top() > 0 && s.top() < abs(c))
 8                    s.pop();
 9                if (s.empty() || s.top() < 0) s.push(c);
10                if (!s.empty() && s.top() == abs(c)) s.pop();
11            } else {
12                s.push(c);
13            }
14            
15        }
16
17        vector<int> res;
18        while(!s.empty()) {
19            res.push_back(s.top());
20            s.pop();
21        }
22
23        reverse(res.begin(), res.end());
24
25        return res;
26    }
27};

933. 最近的请求次数

 1class RecentCounter {
 2public:
 3    queue<int> q;
 4    RecentCounter() {
 5
 6    }
 7    
 8    int ping(int t) {
 9        q.push(t);
10        while (t - q.front() > 3000) q.pop();
11        return q.size();
12    }
13};
14
15/**
16 * Your RecentCounter object will be instantiated and called as such:
17 * RecentCounter* obj = new RecentCounter();
18 * int param_1 = obj->ping(t);
19 */

104. 二叉树的最大深度

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    int maxDepth(TreeNode* root) {
15        if(root == NULL) return 0;
16        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
17    }
18};

198. 打家劫舍

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

1318. 或运算的最小翻转次数

 1class Solution {
 2public:
 3    vector<int> trans(int x) {
 4        vector<int> res;
 5        while(x) {
 6            res.push_back(x % 2);
 7            x /= 2;
 8        }
 9        return res;
10    }
11
12    int minFlips(int a, int b, int c) {
13        // 十进制转换为二进制数组
14        vector<int> x = trans(a);
15        vector<int> y = trans(b);
16        vector<int> z = trans(c);
17
18        // 补零
19        if(x.size() < z.size()) {
20            int c = z.size() - x.size();
21            while(c--) {
22                x.push_back(0);
23            }
24        }
25
26        // for(int i = 0; i < x.size(); i++)
27        //     cout << x[i] << ' ';
28        // cout << endl;
29
30        if(y.size() < z.size()) {
31            int c = z.size() - y.size();
32            while(c--) {
33                y.push_back(0);
34            }
35        }
36
37        // for(int i = 0; i < y.size(); i++)
38        //     cout << y[i] << ' ';
39        // cout << endl;
40
41        // for(int i = 0; i < z.size(); i++)
42        //     cout << z[i] << ' ';
43        // cout << endl;
44
45        // 统计
46        int res = 0;
47        for(int i = 0; i < z.size(); i++)
48        {
49            if(z[i] == 1) {
50                if(!x[i] && !y[i]) res++;
51            }
52            else {
53                if(x[i] && y[i]) res += 2;
54                else if(x[i] || y[i]) res++;
55            }
56        }
57
58        // 多余部分
59        for(int i = z.size(); i < x.size(); i++)
60            if(x[i] == 1) res++;
61
62        for(int i = z.size(); i < y.size(); i++)
63            if(y[i] == 1) res++;
64        
65        return res;
66    }
67};

136. 只出现一次的数字

巧用亦或

 1class Solution {
 2public:
 3    /*
 4    a ^ 0 = 0;
 5    a ^ a = 0;
 6
 7    a ^ a ^ b ^ b ^ c = c;
 8    */
 9    int singleNumber(vector<int>& nums) {
10        int res = 0;
11
12        for(auto c : nums)
13            res ^= c;
14        
15        return res;
16    }
17};

338. 比特位计数

 1class Solution {
 2public:
 3    int fun(int x)
 4    {
 5        int cnt = 0;
 6        while(x)
 7        {
 8            if(x % 2) cnt++;
 9            x /= 2;
10        }
11        return cnt;
12    }
13    
14    vector<int> countBits(int n) {
15        vector<int> res;
16        for(int i = 0; i <= n; i++)
17            res.push_back(fun(i));
18        return res;
19    }
20};

345. 反转字符串中的元音字母#

283. 移动零 $\bigstar$#

392. 判断子序列#

1732. 找到最高海拔#

724. 寻找数组的中心下标#

1207. 独一无二出现的次数#

746. 使用最小花费爬楼梯#

238. 除自身意外数组的乘积#

334. 递增三元子序列#

443. 压缩字符串#

11. 盛最多水的容器#

1137. 第 N 个泰波那契数#

1679. K 和数对的最大数目#

494. 目标和#

643. 子数组最大平均数 I#

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

1004. 最大连续 1 的个数 III#