LeetCode合集

LeetCode1704 判断字符串两段是否相等

题目整体没有什么难度，使用了最简单的得到两个子串后分别计数并比较是否相等。

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
class Solution {
public:
    bool halvesAreAlike(string s) {
        int length = s.length();
        string firstHalfStr = s.substr(0, length / 2);
        string SecondHalfStr = s.substr(length / 2, length / 2);

        if(isTwoStrSame(firstHalfStr, SecondHalfStr)) {
            return true;
        }
        else {
            return false;
        }
    }

private:
    bool isTwoStrSame(string str1, string str2) {
        int num1 = getNum(str1);
        int num2 = getNum(str2);

        if(num1 == num2) {
            return true;
        }
        else {
            return false;
        }
    }
    int getNum(string str1) {
        int i;
        int len = str1.length();
        int num = 0;

        for(i = 0;i < len;i++) {
            if(str1[i] == 'a' || str1[i] == 'A' || str1[i] == 'e' || str1[i] == 'E' || str1[i] == 'i' || str1[i] == 'I' || str1[i] == 'o' || str1[i] == 'O' || str1[i] == 'u' || str1[i] == 'U') {
                num += 1;
            }
        }

        return num;
    }
};

但是这样开销比较大，看题解发现还可以使用双指针或者使用位运算。

LeetCode202 快乐数

题目整体比较简单，核心思路大致为需要使用一个set保存已经出现过的平方和取值，每次计算时候需要在集合中进行查找，如果搜索到中止，如果没有搜索到将这个值加入集合。

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
#include<vector>
#include<set>
class Solution {
public:
    bool isHappy(int n) {
        set<int> all_sum_results;
        bool flag = false;
        int current_value = n;
        int current_value_sum = 0;

        while(!flag) {
            current_value_sum = getSum(current_value);
            current_value = current_value_sum;

            if(current_value_sum == 1) {
                return true;
            }

            if(all_sum_results.find(current_value_sum) != all_sum_results.end()) {
                //already exists! loop occurred
                flag = true;
            }
            else {
                all_sum_results.insert(current_value_sum);
            }

        }

        return false;

    }
private:
int getSum(int current_value) {
    vector<int> num_bits;
    int sum_value = 0;

    while(current_value) {
        sum_value += (current_value % 10) * (current_value % 10);
        current_value /= 10;
    }

    return sum_value;
}
};

其他解题思路使用快慢指针来找出循环，非常巧妙，避免当set太大的时候存储开销过大。（循环的时候判断此时取值是否为1，如果是1说明是快乐数，如果不是1说明出现loop）

其他一些位运算的使用技巧可以参考https://www.zhihu.com/question/38206659。

1
2
3
4
5
6
7
8
9
10
bool isHappy(int n) {
        int slow = n, fast = n;
        do{
            slow = bitSquareSum(slow);
            fast = bitSquareSum(fast);
            fast = bitSquareSum(fast);
        }while(slow != fast);
        
        return slow == 1;
    }

LeetCode1710 卡车上的最大单元数

思路比较简单，在truckSize允许的前提下每次都选择对应unit最大的boxType。所以需要对一个二维数组按照按照unit数目进行排序。

需要自定义vector sort中的比较器。需要注意，comp函数需要定义为static类型，否则编译报错。

同时因为每次拿完一个就调用了erase函数，所以需要考虑到仍然有剩余空间但已经没有箱子的情况，否则会运行报内存错误。

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
#include<algorithm>
class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        int boxTypeNum = boxTypes.size();
        int res = 0;
        int remainingSize = truckSize;

        sort(boxTypes.begin(),boxTypes.end(),comp);
        while(remainingSize != 0) {
            if(boxTypes.empty()) {
                break;
            }
            int currentNum = boxTypes[0][0];
            int currentUnit = boxTypes[0][1];

            if(currentNum <= remainingSize) {
                remainingSize -= currentNum;
                res += currentNum * currentUnit;
            }
            else {
                res += remainingSize * currentUnit;
                remainingSize = 0;
            }

            boxTypes.erase(boxTypes.begin());
        }

        return res;
    }
private:
    static bool comp(vector<int>& box1, vector<int>& box2) {
        return box1[1] > box2[1];
    }
};

LeetCode 1603设计停车系统

这个题目没有难点，简单维护一个现有车位的变量即可。

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 ParkingSystem {
public:
    ParkingSystem(int big, int medium, int small) {
        RemainingBig = big;
        RemainingMed = medium;
        RemainingSmall = small;
    }
    
    bool addCar(int carType) {
        if(carType == 1) {
            if(RemainingBig >= 1) {
                RemainingBig -= 1;
                return true;
            }
        }
        else if(carType == 2) {
            if(RemainingMed >= 1) {
                RemainingMed -= 1;
                return true;
            }
        }
        else if(carType == 3) {
            if(RemainingSmall >= 1) {
                RemainingSmall -= 1;
                return true;
            }
        }

        return false;
    }
private:
    int RemainingBig;
    int RemainingMed;
    int RemainingSmall;
};

LeetCode1752 检查数组是否经排序和轮转得到

考虑到源数组是非递减顺序，所以如果可以轮转得到，数组实际上是分为两部分，左边部分是一个递增序列，右边部分是一个递减的序列。所以考虑使用双指针来解决。

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
bool check(vector<int>& nums) {
        int size = nums.size();
        int left_pointer =  0;
        int right_pointer = size - 1;
        bool move_flag_1 = false;
        bool move_flag_2 = false;

        if(size == 1 || size == 0) {
            return true;    //special case
        } 
        while(left_pointer != right_pointer) {
            move_flag_1 = false;
            move_flag_2 = false;

            if(nums[left_pointer+1] >= nums[left_pointer]) {
                left_pointer += 1;
                move_flag_1 = true;
            }
            if(nums[right_pointer-1] <= nums[right_pointer]) {
                right_pointer -= 1;
                move_flag_2 = true;
            }

            if(left_pointer >= right_pointer) {
                return true;
            }
            //forget third condition 
            if((left_pointer == right_pointer - 1) && (nums[left_pointer] >= nums[size-1]) && (nums[size-1] <= nums[0])) {
                return true;
            }
            if(!(move_flag_1||move_flag_2)) {
                break;
            }
        }

        return false;
    }

但是这样的思路只能通过101/105个测试用例，一个无法通过的示例为[2,4,1,3]。最终left_pointer停在4，right_pointer停在1，且满足4比3大。但是忘记考虑数组起始两个下标之间的关系，加上第三个条件式(nums[size-1] <= nums[0])通过。

LeetCode1614 括号的最大嵌套深度

因为是涉及到括号匹配以及最大深度的问题，所以使用stack。一开始想的很麻烦，想要在pop的时候判断栈中是否为空，从而确定是需要做max操作还是直接相加。

后来直接看解题思路发现最大深度其实只需要判断栈中元素个数最多时候的数值即可。因此在push和pop的时候同时维护一个size，实现比较简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int maxDepth(string s) {
        int length = s.length();
        stack<char> parenthese;
        int depth = 0;
        int res = 0;
        int i;

        for(i = 0;i < length;i++) {
            if(s[i] == '(') {
                parenthese.push(s[i]);
                depth += 1;
                res = max(res, depth);
            }
            if(s[i] == ')') {
                parenthese.pop();
                depth -= 1;
            }
        }

        return res;
    }

LeetCode1732 找到最高海拔

题目非常简单，只需要维护一个maxHeight变量并且在循环的时候不断更新当前最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
int largestAltitude(vector<int>& gain) {
        int maxHeight = 0;
        int currentHeight = 0;
        int i;

        for(i = 0;i < gain.size();i++) {
            currentHeight += gain[i];
            maxHeight = max(maxHeight, currentHeight);
        }

        return maxHeight;
    }

LeetCode1051 高度检查器

这个题目没有什么难度，最直观的方法直接调用algorithm库中的sort函数进行排序，并且再循环一次找到不匹配的数目即可。

这样需要额外复制一个数组，空间复杂度为O(N)，或者可以自己实现排序算法，统计每一次交换即可进一步优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int heightChecker(vector<int>& heights) {
        int i;
        int size = heights.size();
        int res = 0;
        vector<int> sorted_heights = heights;

        sort(sorted_heights.begin(), sorted_heights.end());
        for(i = 0;i < size;i++) {
            if(sorted_heights[i] != heights[i]) {
                res += 1;
            }
        }

        return res;
    }

LeetCode2469 温度转换

看到题目有误差要求以为需要进行类型转换才能得到正确数据，但是直接写也能ac，没有难度。

1
2
3
4
5
6
7
8
vector<double> convertTemperature(double celsius) {
        vector<double> res;

        res.push_back(celsius + 273.15);
        res.push_back(celsius * 1.80 + 32.00);

        return res;
}

LeetCode2236 断根结点是否等于子结点之和

题目已经给出二叉树恰好有三个节点，所以不用判断指针是否null，直接加和即可。

1
2
3
4
5
6
7
bool checkTree(TreeNode* root) {
        if(root -> val == (root->left -> val) + (root -> right -> val)) {
            return true;
        }

        return false;
    }

LeetCode1929 数组串联

题目没有难度，不过为了减小空间消耗可以直接在数组后面继续添加，用取模运算对应下标即可。

1
2
3
4
5
6
7
8
9
10
vector<int> getConcatenation(vector<int>& nums) {
        int size = nums.size();
        int i;

        for(i = size;i < size * 2;i++) {
            nums.push_back(nums[i % size]);
        } 

        return nums;
    }

LeetCode1672 最富有的客户资产总量

题目很简单，维护一个max_assets每次循环一行更新即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maximumWealth(vector<vector<int>>& accounts) {
        int max_assets = 0;
        int row = accounts.size();
        int col = accounts[0].size();   //input is not empty
        int i;
        int j;

        for(i = 0;i < row; i++) {
            int current_assets = 0;
            for(j = 0;j < col; j++) {
                current_assets += accounts[i][j];
            }
            max_assets = max(max_assets, current_assets);
        }

        return max_assets;
    }

LeetCode1742 盒子中小球的最大数量

因为给出的盒子无限，并且也不知道小球加和的范围，所以不能直接自己声明一个vector，并且把对应下标作为盒子的编号，这样会导致空间的浪费。所以使用C++中的stl map类型，用来记录对应box id以及存放小球的数目。最后实现一个自定义的比较函数cmp，找到map中value最大的元素。

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
public:
    int countBalls(int lowLimit, int highLimit) {
        map<int,int> index_num_box;
        int i;

        for(i = lowLimit; i <= highLimit; i++) {
            int currentIndex = getSum(i);
            if(index_num_box.find(currentIndex) != index_num_box.end()) {
                index_num_box[currentIndex] += 1;
            }
            else {
                index_num_box[currentIndex] = 1;
            }
        }

        return max_element(index_num_box.begin(), index_num_box.end(), cmp) -> second;
    }
private:
int getSum(int num) {
    int res = 0;

    while(num) {
        res += num % 10;
        num /= 10;
    }

    return res;
}
static bool cmp(const pair<int,int> pair1, const pair<int,int> pair2) {
    return pair1.second < pair2.second;
}

LeetCode14 最长公共前缀

考虑每个匹配的char都要进行一遍循环，直到遇到了第一个不匹配的字符或者某个字符串已经匹配完成（长度最小）。

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
string longestCommonPrefix(vector<string>& strs) {
        string res = "";
        int string_num = strs.size();
        bool flag = true;
        int res_num = 0;
        int i;

        if(string_num == 1) {
            return strs[0];
        }

        while(flag) {
            char current_char = ' ';
            for(i = 0;i < string_num; i++) {
                string current_string = strs[i];

                if(current_string.size() == res_num) {
                    flag = false;
                    break;  //come to the minimum length string
                }

                if(i == 0) {
                    current_char = current_string[res_num];
                }
                else if(current_string[res_num] != current_char) {
                    flag = false;
                    break;  //mismatch
                }
            }
            if(flag) {
                res += current_char;
                res_num += 1;
            }
        }

        return res;
    }

看题解发现可以先对strs进行排序，排序之后比较第一个和最后一个字符串即可，他们两个的相同部分是所有str的最长公共前缀。

LeetCode541 反转字符串

题目本身难度不大，不过需要考虑各种情况，并且下标处理的时候想了很久，需要多考虑几个例子。为了避免每种情况都写一个循环，所以先做判断并且记录需要增加的step，三种情况用相同的循环体去处理。

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
string reverseStr(string s, int k) {
        int left_pointer = 0;
        int str_length = s.size();
        int step = 0;
        int current_k = k;

        while(left_pointer < str_length) {
            int right_pointer = left_pointer + k * 2;

            if(right_pointer <= str_length) {
                //left_pointer += 2 * k;
                step = 2 * k;
            }
            else if(left_pointer + k <= str_length) {
                //left_pointer = str_length;
                step = str_length - left_pointer;
            }
            else if(left_pointer < str_length) {
                //反转剩下的全部
                current_k = str_length - left_pointer;
                step = str_length - left_pointer;
            }

            //正常反转k个
            int i = left_pointer;
            int j = 0;
            for(j = 0;j < current_k / 2;j++) {
                char current_invert_char = s[left_pointer + current_k - j - 1];
                s[left_pointer + current_k - j - 1] = s[i];
                s[i] = current_invert_char;
                i++;
            }

            left_pointer += step;
        }

        return s;
    }

LeetCode111 二叉树的最小深度

题目比较简单，不过不能直接当root为null的时候返回0，这样会导致边树的最小深度永远为1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minDepth(TreeNode* root) {
        if(root == nullptr) {
            return 0;
        }
        TreeNode* left_child = root -> left;
        TreeNode* right_child = root -> right;

        if(left_child == nullptr && right_child == nullptr) {
            return 1;
        }
        else if(left_child == nullptr) {
            return 1 + minDepth(right_child);
        }
        else if(right_child == nullptr) {
            return 1 + minDepth(left_child);
        }

        return min(minDepth(left_child), minDepth(right_child)) + 1;
    }

LeetCode108 将有序数组转换为二叉搜索树

给定一个升序的数组，需要将他转变为一个BST。实际上，这个BST的中序遍历就是对应的升序数组，但是如果只给定了BST的中序遍历，并不能唯一确定对应的树。就算加上了高度平衡（左右子树高度差小于等于1），也不能唯一确定（因为数组长度一定存在是偶数的情况，中间下标可以有两种情况）。

很直观的想法是中间的数会作为root节点，然后左边数组对应构造左子树，右边数组对应构造右子树。递归完成即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = nullptr;
        int middle_index = nums.size() / 2;

        if(nums.size() == 0) {
            return nullptr;
        }

        root = new TreeNode(nums[middle_index]);

        vector<int> left_arr(nums.begin(), nums.begin() + middle_index);
        vector<int> right_arr(nums.begin() + middle_index + 1, nums.end());

        root->left = sortedArrayToBST(left_arr);
        root->right = sortedArrayToBST(right_arr);
        
        return root;
    }

LeetCode2169 得到0的操作数

很简单，直接判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int countOperations(int num1, int num2) {
        int res = 0;
        while(num1 != 0 && num2 != 0) {
            if(num1 >= num2) {
                num1 = num1 - num2;
            }
            else {
                num2 = num2 - num1;
            }

            res += 1;
        }

        return res;
    }

LeetCode2185 统计包含给定前缀的字符串

遍历一遍str数组，对每一个字符串提取前缀长度的子串，并判断是否相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int prefixCount(vector<string>& words, string pref) {
        int size = words.size();
        int pref_size = pref.length();
        int count = 0;
        int i;

        for(i = 0;i < size; i++) {
            string current_pref = words[i].substr(0, pref_size);

            if(current_pref == pref) {
                count += 1;
            }
        }

        return count;
    }

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

一开始的做题思路是分别从左右两边循环一遍，找出对应操作数，并且返回两者之间的较小值。但是这样只能通过81/89个case，比如考虑10010100这个串，不管是左边还是右边对应的操作数都是5，实际上最小的操作数是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
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
int minOperations(string s) {
        int left_op = 0;
        int right_op = 0;
        int both_op = 2;
        int size = s.length();
        string another_s = s;
        string another_s_1 = s;
        int i;

        for(i = 0;i < size - 1; i++) {
            if(s[i] == '0' && s[i+1] == '1') {
                continue;
            }
            if(s[i] == '1' && s[i+1] == '0 ') {
                continue;
            }
            else if(s[i] == '0' && s[i+1] == '0') {
                s[i+1] = '1';
                left_op += 1;
            }
            else if(s[i] == '1' && s[i+1] == '1') {
                s[i+1] = '0';
                left_op += 1;
            }
        }

        for(i = size - 1;i > 0; i--) {
            if(another_s[i] == '1' && another_s[i-1] == '0') {
                continue;
            }
            if(another_s[i] == '0' && another_s[i-1] == '1') {
                continue;
            }
            else if(another_s[i] == '0') {
                another_s[i-1] = '1';
                right_op += 1;
            }
            else if(another_s[i] == '1') {
                another_s[i-1] = '0';
                right_op += 1;
            }
        }

        another_s_1[0] = another_s_1[0] == '1' ? '0' : '1';
        another_s_1[size-1] = another_s_1[size-1] == '1' ? '0' : '1';
        for(i = 0;i < size - 1; i++) {
            if(another_s_1[i] == '0' && another_s_1[i+1] == '1') {
                continue;
            }
            if(another_s_1[i] == '1' && another_s_1[i+1] == '0 ') {
                continue;
            }
            else if(another_s_1[i] == '0' && another_s_1[i+1] == '0') {
                another_s_1[i+1] = '1';
                both_op += 1;
            }
            else if(another_s_1[i] == '1' && another_s_1[i+1] == '1') {
                another_s_1[i+1] = '0';
                both_op += 1;
            }
        }

        return min(min(left_op, right_op), both_op);
    }

题解中的思路更简单，一个字符串s最终可以有两个交替字符串，分别是以0开头和以1开头的情况。并且这两种的操作数之和等于整个字符串的长度。所以实际只需要遍历一遍，就可以直接相减得到另外一个的操作数。

1
2
3
4
5
6
7
8
9
10
int minOperations(string s) {
        int cnt = 0;
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            if (c != ('0' + i % 2)) {
                cnt++;
            }
        }
        return min(cnt, (int)s.size() - cnt);
    }

LeetCode2451 差值数组不同的字符串

这个题的难度在于如何高效的找到一个数组中的不重复元素。一开始想的是在计算过程中就一起维护一个diff_index，从而不需要额外再判断一遍。

1
2
3
4
if(current_diff != diff[diff_index]) {
    diff_index = i;
    break;
}

实际上只要当出现不一致的时候，能够再向前或者向后找一个元素，用三个元素就可以判断出到底哪个是重复的哪个是唯一的。所以最终用一个flag，如果找到第一个不一样的元素，就再向后算一个diff，加入vector并中止循环。这样会减少时间复杂度，因为只要找到有不一样的元素就可以退出，如果唯一元素出现的位置比较靠前而数组又很长，可以省去计算后面元素的开销。

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
string oddString(vector<string>& words) {
        int length = words.size();
        int str_length = words[0].size();
        vector<vector<int>> diff;
        int diff_index = 0;
        bool flag = false;
        int i;
        int j;

        for(i = 0;i <length;i++) {
            string current_str = words[i];
            vector<int> current_diff;
            for(j = 0;j < str_length - 1;j++) {
                current_diff.push_back(current_str[j+1] - current_str[j]);
            }
            diff.push_back(current_diff);
            if(flag) {
                break;
            }
            if(current_diff != diff[diff_index]) {
                diff_index = i;
                flag = true;
                continue;   //可以计算出下一个元素，不会直接退出循环
            }
        }

        if(diff_index > 0 && diff_index <= length - 2) {
            if(diff[diff_index] == diff[diff_index+1]) {
                diff_index -= 1;
            }
        }

        return words[diff_index];

    }

LeetCode1779 找到最近的有相同 X 或 Y 坐标的点

比较简单，在循环判断坐标是否有效的同时维护min_dist以及对应下标index即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
        int size = points.size();
        int min_dist = 10001;
        int index = -1;   
        int i;

        for(i = 0;i < size; i++) {
            if(points[i][0] == x || points[i][1] == y) {
                //a valid point
                int current_dist = abs(points[i][0] - x) + abs(points[i][1] - y);
                if(current_dist < min_dist) {
                    index = i;
                    min_dist = current_dist;
                }
            }
        }

        return index;
    }

LeetCode100 相同的树

题目非常简单，因为树相关的问题大部分都是递归完成，即分解成左子树和右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr) {
            return true;
        }
        else if(p == nullptr || q == nullptr) {
            return false;
        }

        if(p -> val == q -> val) {
            return isSameTree(p -> left, q -> left) && isSameTree(p -> right, q -> right);
        }

        return false;
    }

LeetCode88 合并两个有序数组

本来以为是给每个数组弄一个指针比较放进数组，但是发现跟之前做的不太一样，需要把结果保存到其中一个已经预先分配好空间的vector中。而如果再用之前的方法，从左边开始依次比较，则每次比较出需要从另一个数组插入的时候，会发现需要把原来的每个都往后移一个。

看了题解的思路，是从后往前确定放进去哪个，并且当另外一个数组的全部元素都正确插入后循环结束。

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
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int nums1_pointer = m - 1;
        int nums2_pointer =  n - 1;
        int total_size = m + n;
        int current_insert_index = total_size - 1;

        if(m == 0) {
            nums1 = nums2;//直接赋值
            return;
        }
        else if(n == 0) {
            return;
        }

        while(nums2_pointer >= 0) {
            //nums2中仍然有元素没有插完
            if(nums1_pointer < 0) {
                nums1[current_insert_index] = nums2[nums2_pointer];
                nums2_pointer --;
                current_insert_index --;
                continue;
            }   //如果最前面是空的，数组下标会减到-1

            int current_num1_val = nums1[nums1_pointer];
            int current_num2_val = nums2[nums2_pointer];

            if(current_num1_val < current_num2_val) {
                nums1[current_insert_index] = current_num2_val;
                nums2_pointer --;
                current_insert_index --;
            }
            else if(current_num1_val >= current_num2_val) {
                nums1[nums1_pointer] = 0;
                nums1[current_insert_index] = current_num1_val;
                nums1_pointer --;
                current_insert_index --;
            }
        }

        return;
    }

LeetCode1796 字符串中第二大的数字

题目难度不大，因为使用set存出现过的数字，可以直接调用insert不需要在自己判断元素是否出现的逻辑，并且会自己排序，也不需要再额外调用sort函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int secondHighest(string s) {
        set<int> nums;
        int size = s.size();
        int res = 0;
        int i;

        for(i = 0;i < size;i++) {
            if(s[i] >= '0' && s[i] <= '9') {
                nums.insert(s[i] - '0');
            }
        }
        if(nums.size() <= 1) {
            return -1;
        }

        //sort(nums.begin(),nums.end());

        set<int>::iterator it = nums.end();
        it --;
        it --;
        res = *(it);
        return res;
    }

LeetCode771 宝石与石头

非常简单，循环遍历一遍并且对每个字符都判断是否是宝石，因此将判断逻辑单独抽象出来写成一个函数。

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
int numJewelsInStones(string jewels, string stones) {
        int size = stones.size();
        int res = 0;
        int i;

        for(i = 0;i < size; i++) {
            if(isJewel(jewels, stones[i])) {
                res ++;
            }
        }

        return res;
    }

    bool isJewel(string jewels, char current_stone) {
        int size = jewels.size();
        int i;

        for(i = 0;i < size; i++) {
            if(jewels[i] == current_stone) {
                return true;
            }
        }

        return false;
    }

LeetCode1486 数组异或操作

直接用遍历进行按位异或的操作，但是感觉应该会有更简单的数学上的方法。

1
2
3
4
5
6
7
8
9
10
11
int xorOperation(int n, int start) {
        int i;
        int res = start;

        for(i = 1;i < n;i++) {
            int current_val = start + 2 * i;
            res  = res ^ current_val;
        }

        return res;
    }

LeetCode824 山羊拉丁文

处理逻辑比较简单，注意到可以直接用stringstream来完成给定string按照空格分隔。并且直接在分隔的同时对word进行逐词处理，不用先转成vector之后再遍历一遍处理。

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
public:
    string toGoatLatin(string sentence) {
        string res = "";
        string current_word = "";
        stringstream str_input(sentence);
        int index = 1;

        while(str_input >> current_word) {
            int i;

            if(isVowel(current_word[0])) {
                res += current_word + "ma";
            }
            else {
                res += performNonVowelChange(current_word) + "ma";
            }

            for(i = 0; i < index; i++) {
                res += "a";
            }

            res += " ";
            index++;
        }

        res.erase(res.size() - 1, 1);
        return res;
    }

private:
    bool isVowel(char current_char) {
        if(current_char == 'a' || current_char == 'e' || current_char == 'i' || current_char == 'o' || current_char == 'u') {
            return true;
        }
        if(current_char == 'A' || current_char == 'E' || current_char == 'I' || current_char == 'O' || current_char == 'U') {
            return true;
        }

        return false;
    }
    string performNonVowelChange(string original_word) {
        string res = original_word;
        
        res += original_word[0];
        res.erase(0,1);

        return res;
    }

LeetCode203 移除链表元素

因为需要在遍历的同时将相同取值的元素删除，所以同时需要维护一个prev的指针。而且会有可能在head处匹配的值就是相等的，那么还需要修改head的取值，并且因为head前面没有其他元素，所以在head的时候curr和prev是相同的。并且当匹配完成的时候指针已经更新过了，直接continue跳过下面正常的后移一位，否则会有元素被跳过，删除不了。

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
ListNode* removeElements(ListNode* head, int val) {
        ListNode* current_node = head;
        ListNode* prev_node = head;

        while(current_node != nullptr) {
            int current_val = current_node -> val;

            if(current_val == val && current_node == head) {
                head = head -> next;
                current_node = head;
                prev_node = head;
                continue;
            }
            else if(current_val == val) {
                prev_node -> next = current_node -> next;
                current_node = current_node -> next;
                continue;
            }

            if(current_node == head && current_node != nullptr) {
                current_node = current_node -> next;
            }
            else if(current_node != nullptr){
                current_node = current_node -> next;
                prev_node = prev_node -> next;
            }
        }

        return head;
    }

LeetCode1790 仅执行一次字符串交换能否使两个字符串相等

因为只交换一次就要让两个字符串相等，所以很显然遍历一次两个字符串只能有两个位置的下标对应不上（只有一个不对应或者超过2个不对应都不能满足）。而且一开始只是简单这样比较，会导致一些testcase不过，比如”znb”和”anc”，也是有两个位置的下标无法对应，但是还需要进一步确保对应下标上的字符交换后相等。

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
bool areAlmostEqual(string s1, string s2) {
        int size = s1.size();
        int diff_num = 0;
        char diff_s1_first = ' ';
        char diff_s2_first = ' ';
        char diff_s1_second = ' ';
        char diff_s2_second = ' ';
        int i;

        for(i = 0;i < size;i++) {
            if(s1[i] != s2[i]) {
                diff_num += 1;
                if(diff_num == 1) {
                    diff_s1_first = s1[i];
                    diff_s2_first = s2[i];
                }
                else {
                    diff_s1_second = s1[i];
                    diff_s2_second = s2[i];
                }
            }
            if(diff_num > 2) {
                return false;
            }
        }

        if(diff_s1_first != diff_s2_second || diff_s2_first != diff_s1_second) {
            return false;
        }
        return true;
    }

LeetCode1821 判断国际象棋棋盘中一个格子的颜色

比较简单，发现当字母坐标和数字坐标之和是偶数的时候，格子才会是黑色的。

1
2
3
4
5
6
7
8
9
10
bool squareIsWhite(string coordinates) {
        char coordinate_letter = coordinates[0];
        char coordinate_number = coordinates[1];

        if((coordinate_number + coordinate_letter - 'a') % 2) {
            return false;
        }

        return true;
    }

LeetCode1678 设计Goal解析器

没有难度，因为出现的字符串没有嵌套，只会是顺序出现，而且假设所有字符串都是合法的，因此循环一遍就可以得到解析后的字符串。

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
string interpret(string command) {
        string res = "";
        int size = command.size();
        int i;

        for(i = 0;i < size;i++) {
            char current_char = command[i];

            if(current_char == 'G') {
                res += "G";
            }
            else if(current_char == '(') {
                if(command[i + 1] == ')') {
                    res += "o";
                    i += 1;
                }
                else if(command[i + 1] == 'a') {
                    res += "al";
                    i += 2;
                }
            }
        }

        return res;
    }

LeetCode1720 解码异或后的数组

非常简单，a = b ^ c，则 c = a ^ b。可以一次遍历解码出原始的数组，注意下标不要越界。

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> decode(vector<int>& encoded, int first) {
        vector<int> original;
        int size = encoded.size() + 1;
        int i;

        original.push_back(first);
        for(i = 1;i < size;i++) {
            original.push_back(original[i - 1] ^ encoded[i - 1]);
        }

        return original;
    }

LeetCode1827 最少操作使数组递增

一开始根据给出的两个例子只考虑到根据前两个数字判断整个数组，但是忽略了可能前n个数字都是递增的情况（如2,6,8,2,3,2）。所以每个数字$num_{i}$当前应该是什么值需要取决于他前一个数字$num_{i-1}$是否小于他，如果小于说明不用变化，如果大于说明变成$num_{i}$+1的操作数是最少的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minOperations(vector<int>& nums) {
        int size = nums.size();
        int res = 0;
        int i;

        if(size == 1 || size == 0) {
            return res;
        }

        for(i = 1;i < size;i++) {
            int current_num = nums[i] <= nums[i-1] ? nums[i-1] + 1 : nums[i];
            res += current_num - nums[i];
            nums[i] = current_num;
        }

        return res;
    }

LeetCode145 二叉树的后序遍历

后序遍历的顺序是左子树->右子树->根节点，并且在遍历之前先判断当前根节点是否为空。不过因为返回的是一个vector，所以需要将左子树和右子树返回回来的vector拼在一起。查到的一个方法是stl中的insert方法，可以实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;

        if(root == nullptr) {
            return res;
        }
        vector<int> left_res = postorderTraversal(root -> left);
        vector<int> right_res = postorderTraversal(root -> right);
        res.insert(res.end(), left_res.begin(), left_res.end());
        res.insert(res.end(), right_res.begin(), right_res.end());
        res.push_back(root -> val);

        return res;
    }

但是这样内存开销太大了，参考题解有一种更好的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void postorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        postorder(root, res);
        return res;
    }

LeetCode1832 判断句子是否为全字母句

思路非常简单，对句子进行一次遍历即可，用unordered_set记录已经存在过的字符，如果查找不到就插入。并且如果当句子长度很长且前面已经出现了全部字母之后，可以通过判断size直接退出（一个改进思路：不调用size函数，维护一个数值记录插入次数也可以，不确定能不能优化时间复杂度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool checkIfPangram(string sentence) {
        int size = sentence.size();
        unordered_set<char> letter_set;
        int i;

        for(i = 0;i < size;i++) {
            if(letter_set.find(sentence[i]) == letter_set.end()) {
                letter_set.insert(sentence[i]);
            }
            if(letter_set.size() == 26) {
                return true;
            }
        }
        
        return false;
    }

LeetCode290 单词规律

第一眼看上去有点难度，实际上就是维护一个map，保存从letter到对应word的一个映射关系。因为完整的字符串s是包含空格的，所以单独写了一个getCurrentWord的函数来得到下一个单词，并且修改指针的位置。

测试样例发现了一个问题，即第一次代码插入单词的时候没有检查value是否重复，即abba的模式会对四个dog返回true。而map只能保证key不重复，不能保证value不重复，因此每次加入之前又单独写了一个检查value是否已经存在的函数。

同时，输入并没有确保pattern和s的长度是完全吻合的，因此还要考虑到pattern多或者s多的情况。

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
public:
    bool wordPattern(string pattern, string s) {
        int size = pattern.size();
        map<char, string> letter_to_word;
        int str_pointer = 0;
        int i;

        for(i = 0;i < size;i++) {
            char current_char = pattern[i];
            string current_word;
            if(str_pointer == s.size()) {
                return false;
            }
            if(letter_to_word.find(current_char) == letter_to_word.end()) {
                //add the new word
                current_word = getCurrentWord(s, str_pointer);
                if(currentWordHasAppeared(letter_to_word, current_word)) {
                    return false;
                }
                letter_to_word.insert(pair<char, string>(current_char, current_word));
            }
            else {
                //check the current word
                current_word = getCurrentWord(s, str_pointer);
                if(current_word != letter_to_word[current_char]) {
                    return false;
                }
            }
        }
        if(str_pointer < s.size()) {
            return false;
        }

        return true;
    }
private:
    string getCurrentWord(string s, int& str_pointer) {
        string res;
        for(; str_pointer < s.size();str_pointer++) {
            if(s[str_pointer] == ' ') {
                str_pointer++;
                break;
            }
            res += s[str_pointer];
        }
        return res;
    }
    bool currentWordHasAppeared(map<char, string> letter_to_word, string current_word) {
        map<char, string>::iterator iter = letter_to_word.begin();
        for(;iter != letter_to_word.end();iter++) {
            if(iter -> second == current_word) {
                return true;
            }
        }

        return false;
    }

LeetCode2418 按身高排序

题目比较简单，按照身高需要排序的同时对姓名也进行排序。直接实现了一个简单的冒泡排序。

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
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int size = names.size();
        int i;
        int j;

        for(i = 0;i < size;i++) {
            int max_element_index = i;  //find the current max element index to swap with index i 
            int current_max = heights[i];
            for(j = i;j < size;j++) {
                if(heights[j] > current_max) {
                    max_element_index = j;
                    current_max = heights[j];
                }
            }
            string name_temp = names[i];
            names[i] = names[max_element_index];
            names[max_element_index] = name_temp;

            int height_temp = heights[i];
            heights[i] = current_max;
            heights[max_element_index] = height_temp;
        }

        return names;
    }

LeetCode993 最近的请求次数

一开始以为只需要维护简单的变量即可，后来发现要求返回的是3000ms之内的请求数，所以需要维护一个对应时间的数组。如果直接用<vector>还需要遍历前面的，并且删除的话需要移动元素，比较麻烦。所以想到使用stl中的queue，因为题目中保证单调递增，所以队列中最前面的元素肯定是时间距离最远的元素。所以每次都拿front元素判断是不是超过了3000ms即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class RecentCounter {
public:
    RecentCounter() {
        
    }
    
    int ping(int t) {
        request_time_queue.push(t);

        while(request_time_queue.front() < t - 3000) {
            request_time_queue.pop();
        }

        return request_time_queue.size();
    }
private:
    queue<int> request_time_queue;
};

LeetCode268 丢失的数字

因为范围已经给定是从0到n，所以直接思路就是直接对数组进行排序，然后依次遍历，只要找到跟下标不吻合的即为缺失数字。第二种思路是使用哈希的方法，需要两遍遍历，第一遍确定哪些数字存在，第二遍遍历一遍确认。

1
2
3
4
5
6
7
8
9
10
11
12
int missingNumber(vector<int>& nums) {
        int i;

        sort(nums.begin(), nums.end());
        for(i = 0;i < nums.size();i++) {
            if(nums[i] != i) {
                return i;
            }
        }

        return nums.size();
    }

题解中更快的直接用求和的高斯公式，能够根据数学的方法直接计算出缺失数字。

LeetCode412 Fizz Buzz

题目非常简单，直接写就可以。条件可以单独写出来，更容易检查。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<string> fizzBuzz(int n) {
        vector<string> res;
        int i;

        for(i = 1;i <= n;i++) {
            bool condition_1 = i % 3 == 0;
            bool condition_2 = i % 5 == 0;

            if(condition_1 && condition_2) {
                res.push_back("FizzBuzz");
            }
            else if(condition_1 && !condition_2) {
                res.push_back("Fizz");
            }
            else if(condition_2 && !condition_1) {
                res.push_back("Buzz");
            }
            else {
                res.push_back(std::to_string(i));
            }
        }

        return res;
    }
浅浅刷题
#LeetCode
LeetCode合集
http://example.com/2022/11/11/LeetCode合集/
作者
Jiayi Guo
发布于
2022年11月11日
许可协议