为了后面的机试，是时候捡起C++算法题了。

模拟

[66] 加一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Easy
// 字符串，vector，倒序遍历
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for(auto iter=digits.rbegin();iter!=digits.rend();iter++){
            if(*iter!=9){
                (*iter)++;
                break;
            }else{
                *iter = 0;
            }
        }

        // 如果数字类似于999，前置补1
        if (digits.front() == 0){
            digits.insert(digits.begin(),1);
        }

        return digits;
    }
};

[1768] 交替合并字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>
using namespace std;
class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int min_len = min(word1.length(),word2.length());
        
        string ans;
        for(int i = min_len; i > 0 ; i --){
            ans += word1[min_len - i];
            ans += word2[min_len - i];
        }

        ans += word1.substr(min_len);
        ans += word2.substr(min_len);

        return ans;
    }
};

[389] 找不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>
#include <iostream>
using namespace std;
class Solution {
public:
    char findTheDifference(string s, string t) {
        sort(s.begin(),s.end());
        sort(t.begin(),t.end());
        for(int i = 0; i < max(s.length(), t.length()); i++){
            if (!s[i]){return t[i];}
            if (!t[i]){return s[i];}
            if(s[i]!=t[i]){
                // cout << s[i] << "不同于" << t[i] << " ";
                if(s[i] == t[i+1]){
                    return t[i];
                }else if (s[i+1] == t[i]){
                    return s[i];
                }
            }
        }
        return 0;
    }
};

[28] 找出字符串中第一个匹配项的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int strStr(string haystack, string needle) {
        int len_1 = needle.length();
        int len_2 = haystack.length();
        if(len_1 >= len_2){
            return int(needle == haystack) - 1;
        }
        for(int i = 0; i <= len_2 - len_1; i++){
            if (haystack.substr(i,len_1) == needle){
                return i;
            }
        }
        return -1;
    }
};

[242] 有效的字母异位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <vector>
using namespace std;
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() != t.length()){return false;}
        vector<int> alpha(26,0);
        for (size_t i = 0; i < s.length(); ++i) {
            alpha[s[i] - 'a']++;
            alpha[t[i] - 'a']--;
        }

        for (int count : alpha) {
            if (count != 0)
                return false;
        }
        
        return true;
    }
};

[283] 移动零

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
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        int num_of_zero = 0;
        while(n--){
            if(nums[i] != 0){
                i++;
            }else{
                num_of_zero++;
                nums.erase(nums.begin() + i);
            }
        }
        nums.resize(nums.size() + num_of_zero);
    }
};

// 以为用标准库find会快些，结果时空都变慢了
using namespace std;
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int num_of_zero = 0;
        auto it = find(nums.begin(),nums.end(),0);

        while(it != nums.end()){
            num_of_zero++;
            nums.erase(it);
            it = find(nums.begin(),nums.end(),0);
        }
        nums.resize(nums.size() + num_of_zero);
    }
};

[459] 重复的子字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        for (int i = 1; i * 2 <= n ; i ++){
            if(n%i==0){
                bool match = true;
                for(int j = i;j<n;j++){
                    if(s[j] != s[j-i]){
                        match = false;
                        break;
                    }
                }
                if(match){
                    return true;
                }
            }
        }
        return false;
    }
};

AcWing

动态规划 DP 背包

1