Zj_W1nd's BLOG

Algorithm-leetcode

算法
2025/04/07

lc的输入传引用，并且无需自己设计输入输出格式，只需要实现核心函数即可

考虑在每个方向上都做1-2道题。

数组操作

1-3：数组操作，双指针为主，C++上学期考完csp已经手生了，不会用vec了。需要利用有序信息。保留连续两个重复元素，有序数组，不额外开空间：

双指针一个用于遍历搜索，另一个用于标记修改位置，通用思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // 试一下上一题的快慢指针
        // 数组有序，如果有需要删除的元素，那么在首次遍历到这个元素之后+2肯定不会漏
        // 不让开新数组？
        int n=nums.size();
        if(n<=2) return n;
        int fast=2,slow=2;// 0,1直接保留不用看
        while(fast < n){
            if(nums[fast]!=nums[slow-2])//无
                nums[slow++]=nums[fast];
            fast++;
        }
        return slow;
    }
};

4 多数元素 数组统计

统计指标相关的问题最暴力的就是hashmap一对一，比如找多数元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

多数元素的问题：hashmap，摩尔投票（新鲜），排序取中间，随机摩尔投票是一个专门解决绝对众数的算法。具有On的时间复杂度和O1的空间复杂度，效率比较高。

初始化： 票数统计 votes = 0 ， 众数 x。循环： 遍历数组 nums 中的每个数字 num 。当 票数 votes 等于 0 ，则假设当前数字 num 是众数。当 num = x 时，票数 votes 自增 1 ；当 num != x 时，票数 votes 自减 1 。返回值： 返回 x 即可。正确性略

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = 0, votes = 0;
        for (int num : nums){
            if (votes == 0) x = num;
            votes += (num == x ? 1 : -1);
        }
        return x;
    }
};

5 轮转数组

额外空间略，关注原地算法。

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
// 方法一：交换。比较符合直觉的O1思路。不过需要遍历的轮数gcd(k,n)是推导的结果
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                swap(nums[next], prev);
                current = next;
            } while (start != current);
        }
    }
};
// 方法2: 巧妙的思路，最后的k%n个元素会变到开头
// 联想到翻转操作的数组原语
// 我们只需要先翻转整个数组，再分别翻转前k%n个和其余的，翻转三次即可
class Solution {
public:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }

    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};

简单的贪心

买卖股票：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 用一个结构数组打包然后直接排序
        // 贪心
        int cost = INT_MAX, profit = 0;
        for (int price : prices) {
            cost = min(cost, price);
            profit = max(profit, price - cost);
        }
        return profit;
    }
};

135 分糖果

开始没憋出来，题解没看懂但是看了一点一下想出来了。中途数组排序状态变化会影响结果的，或者说对”部分区间排序“或者所谓的”极大值“/“极小值”有要求的，可以考虑这个思路。我们先从左到右遍历一遍，只关注增幅度，不是增加的不管。然后反向重新遍历一遍，也是一样的思路，最终结果在两次中取最大就行了。

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
class Solution {
public:
    int candy(vector<int>& ratings) {
    // 两次遍历取最大
        int n=ratings.size();
        int sum=0;
        vector<int> v(n);
        v[0]=1;
        for(int i=1;i<n;i++){
            if(ratings[i]>ratings[i-1]){
                v[i]=v[i-1]+1;
            }
            else v[i]=1;
        }
        for(int i=n-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                v[i]=max(v[i+1]+1,v[i]);
            }
            else v[i]=max(1,v[i]);
        }

        for(int e : v){
            sum += e;
        }
        return sum;
    }
};

滑动窗口

最小字串问题

“in”，存在于而不关心具体位置 => unordered_map
如果是英文字符或者数字的话完全可以用数组下标做一一映射，快速随机存取而无需hashmap

  • 128长数组相当于是ascii字符的哈希表

  • 不要太复杂的算法，用好基本的数据结构就行，觉得要更多信息就开空间存不要怕

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
class Solution {
public:
    unordered_map <char, int> ori, cnt;

    bool check() {
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        for (const auto &c: t) {
            ++ori[c];
        }

        int l = 0, r = -1;
        int len = INT_MAX, ansL = -1, ansR = -1;

        while (r < int(s.size())) {
            if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]];
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                }
                if (ori.find(s[l]) != ori.end()) {
                    --cnt[s[l]];
                }
                ++l;
            }
        }

        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};

矩阵

不要担心空间，只管加就行了，遍历一遍信息全记下来

数独判断，行列和3*3。

自己的方法写一半觉得太烂了，是暴力遍历，check3次遍历三次。而且小范围33还写的很烂。看别人的算法应该是函数传入左上角位置然后循环卡在33里面就行。

遍历一遍的方法是

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 isValidSudoku(vector<vector<char>>& board) {
        //使用位运算加速
        vector<int> rows(9);
        vector<int> cols(9);
        vector<int> block(9);

        for(int i=0;i<9;++i){
            for(int j=0;j<9;++j){
                if(board[i][j]=='.')continue;
                int x = board[i][j]-'0';
                if(rows[i]>>x&1 || cols[j]>>x&1 || block[(i/3)*3+j/3]>>x&1){
                    return false;
                }
                //加入
                rows[i] |= 1<<x;
                cols[j] |= 1<<x;
                block[(i/3)*3+j/3] |= 1<<x; //(i,j)位于第(i/3)*3+j/3个九宫格
            }
        }
        return true;
    }
};

本质是二维数组，这里为了加速优化成了bitmap的感觉，每一位标记对应数字是否出现过。

哈希表

统计异位词，及字母一致顺序不同的单词，重新输出链表。先看标答1。标答主要是确定用哈希表之后，考虑用什么做哈希表的键。

或者说，标答开始就认为我们应当用某个特征去归类顺序不同但字母一致的单词，然后用哈希表处理，用统一化的特征作为key，按照这个统一过的key直接塞进哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string& str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            mp[key].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

我也有个思路，不过是自己实现的更快的哈希表。用bitmap统计字母出现与否，也就是整数+位运算记录是否存在。但是测例过不了，发现是需要统计字母数量，同样的字母组合数量不同bitmap没法表示，还是排序或者用26项数组来做。

区间

合并区间。自己的不对的算法。右端点排序不能保证可合并区间相邻，对于每一个区间都需要考察剩下的所有区间，所以是O(n^2)算法。

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:
    static bool cmp(const vector<int>& a,const vector<int>& b){
        // 算法课讲过的贪心？先要对区间排序然后遍历吧？
        return a[1]<b[1];
    }

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 对于任意的A,B两个区间，有如下规则：
        // 如果A的右端点属于B区间，那么就将二者合并为[min(lefta,leftb),rightb]
        int n=intervals.size();
        vector<bool> if_combine(n,false);
        // 优先排序 Ologn
        sort(intervals.begin(),intervals.end(),cmp);
        vector<vector<int>> result;
        for(int k=0;k<n;k++){
            vector<int> tmp(2);
            tmp=intervals[k];
            for(int i=k+1;i<n;i++){
                if(i==n) i--;
                if(if_combine[i]) continue;
                if(tmp[1]>=intervals[i][0]){
                    tmp[0]=min(tmp[0],intervals[i][0]);
                    tmp[1]=intervals[i][1];
                    // 该区间已经被我们合并
                    if_combine[i]=true;
                }
            }
            if(!if_combine[k]) result.push_back(tmp);
        }
        return result;
    }
};

贪心对了，不过左端点排序的性质更好：可合并区间必定连续

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) {
            return {};
        }
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (int i = 0; i < intervals.size(); ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (!merged.size() || merged.back()[1] < L) {
                merged.push_back({L, R});
            }
            else {
                merged.back()[1] = max(merged.back()[1], R);
            }
        }
        return merged;
    }
};

栈

加减法括号计算器。官解：

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 calculate(string s) {
        stack<int> ops;
        ops.push(1);
        int sign = 1;

        int ret = 0;
        int n = s.length();
        int i = 0;
        while (i < n) {
            if (s[i] == ' ') {
                i++;
            } else if (s[i] == '+') {
                sign = ops.top();
                i++;
            } else if (s[i] == '-') {
                sign = -ops.top();
                i++;
            } else if (s[i] == '(') {
                ops.push(sign);
                i++;
            } else if (s[i] == ')') {
                ops.pop();
                i++;
            } else {
                long num = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    num = num * 10 + s[i] - '0';
                    i++;
                }
                ret += sign * num;
            }
        }
        return ret;
    }
};

我自己写的没法处理单目运算符负号，想的是LR规约那种感觉。单目运算符±的好的处理办法就是官解那种，无论如何最后都是加，符号栈里放的是一个符号位，读到就设置，并且每个括号重新push符号位。

我自己写的在这个测试例子挂了：

1
1-(   -2)

我的方法是在数字栈开始压入一个0后面的不动，但是对每个括号都压入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
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
class Solution {
public:
    enum states{
        NUMBER,
        LEFT_PARENTHESE,
        RIGHT_PARENTHESE,
        OP
    };

    int calculate(string s) {
        // 编译原理这一块, 符号栈+规约
        int p=0,state=0;
        vector<int> stack_nums;
        stack_nums.push_back(0);
        vector<char> stack_ops;
        int result;
        // 自动机？
        while(p<s.length()){
            printf("reading: %c\n",s[p]);
            if(isdigit(s[p])) state=NUMBER;
            else if(s[p]=='(') state=LEFT_PARENTHESE;
            else if(s[p]==')') state=RIGHT_PARENTHESE;
            else if(s[p]=='+' || s[p] == '-') state=OP;
            else {
                printf("recognizing space\n");
                p++;
                continue;
            }
            switch(state){
                case NUMBER:{
                    // 检查符号栈
                    long num=0;
                    while (p < s.length() && s[p] >= '0' && s[p] <= '9') {
                        num = num * 10 + s[p] - '0';
                        p++;
                    }
                    printf("num: %ld\n",num);
                    if(stack_ops.empty()) {
                        stack_nums.push_back(num);
                        break;
                    }
                    printf("stack_nums.back():%d\n",stack_nums.back());
                    printf("stack_ops.back(): %c\n",stack_ops.back());
                    if(stack_ops.back()=='+'){
                        int x = stack_nums.back();
                        stack_nums.pop_back();
                        stack_ops.pop_back();
                        stack_nums.push_back(x+num);
                    }
                    else if(stack_ops.back()=='-'){
                        int x = stack_nums.back();
                        stack_nums.pop_back();
                        stack_ops.pop_back();
                        stack_nums.push_back(x-num);
                    }                   
                    else stack_nums.push_back(num);
                    break;
                }
                case LEFT_PARENTHESE:
                    stack_ops.push_back('(');
                    p++;
                    break;
                case RIGHT_PARENTHESE:
                    if(stack_ops.back()=='+'){
                        int x = stack_nums.back();
                        stack_nums.pop_back();
                        int y = stack_nums.back();
                        stack_nums.pop_back();
                        stack_ops.pop_back();
                        stack_nums.push_back(x+y);
                    }
                    else if(stack_ops.back()=='-'){
                        int x = stack_nums.back();
                        stack_nums.pop_back();
                        int y = stack_nums.back();
                        stack_nums.pop_back();
                        stack_ops.pop_back();
                        stack_nums.push_back(y-x);
                    }
                    printf("now it shoud be (: %c\n",stack_ops.back());
                    stack_ops.pop_back();
                    p++;
                    break;
                case OP:
                    stack_ops.push_back(s[p++]);
                    break;
            }
        }
        if(!stack_ops.empty()){
                    if(stack_ops.back()=='+'){
                        int x = stack_nums.back();
                        stack_nums.pop_back();
                        int y = stack_nums.back();
                        stack_nums.pop_back();
                        stack_ops.pop_back();
                        stack_nums.push_back(x+y);
                    }
                    else if(stack_ops.back()=='-'){
                        int x = stack_nums.back();
                        stack_nums.pop_back();
                        int y = stack_nums.back();
                        stack_nums.pop_back();
                        stack_ops.pop_back();
                        stack_nums.push_back(y-x);
                    }                
        }
        return stack_nums.back();
    }
};

题解中的类似思路的支持各种运算符的简单解和通解，解决我上面测例挂的思路也简单粗暴，就是对可能的情况做替换。另外，这个题解也不是规约，按照规约的话应该是数字入栈去做消除，它是在操作入栈的时候直接对栈做完全计算。

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
class Solution {
public:
    void replace(string& s){
        int pos = s.find(" ");
        while (pos != -1) {
            s.replace(pos, 1, "");
            pos = s.find(" ");
        }
    }
    int calculate(string s) {
        // 存放所有的数字
        stack<int> nums;
        // 为了防止第一个数为负数，先往 nums 加个 0
        nums.push(0);
        // 将所有的空格去掉
        replace(s);
        // 存放所有的操作，包括 +/-
        stack<char> ops;
        int n = s.size();
        for(int i = 0; i < n; i++) {
            char c = s[i];
            if(c == '(')
                ops.push(c);
            else if(c == ')') {
                // 计算到最近一个左括号为止
                while(!ops.empty()) {
                    char op = ops.top();
                    if(op != '(')
                        calc(nums, ops);
                    else {
                        ops.pop();
                        break;
                    }
                }
            }
            else {
                if(isdigit(c)) {
                    int cur_num = 0;
                    int j = i;
                    // 将从 i 位置开始后面的连续数字整体取出，加入 nums
                    while(j <n && isdigit(s[j]))
                        cur_num = cur_num*10 + (s[j++] - '0');
                    // 注意上面的计算一定要有括号，否则有可能会溢出
                    nums.push(cur_num);
                    i = j-1;
                }
                else {
                    if (i > 0 && (s[i - 1] == '(' || s[i - 1] == '+' || s[i - 1] == '-')) {
                        nums.push(0);
                    }
                    // 有一个新操作要入栈时，先把栈内可以算的都算了
                    while(!ops.empty() && ops.top() != '(')
                        calc(nums, ops);
                    ops.push(c);
                }
            }
        }
        while(!ops.empty())
            calc(nums, ops);
        return nums.top();
    }
    void calc(stack<int> &nums, stack<char> &ops) {
        if(nums.size() < 2 || ops.empty())
            return;
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        char op = ops.top(); ops.pop();
        nums.push(op == '+' ? a+b : a-b);
    }
};
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
class Solution {
    Map<Character, Integer> map = new HashMap<>(){{
        put('-', 1);
        put('+', 1);
        put('*', 2);
        put('/', 2);
        put('%', 2);
        put('^', 3);
    }};
    public int calculate(String s) {
        s = s.replaceAll(" ", "");
        char[] cs = s.toCharArray();
        int n = s.length();
        Deque<Integer> nums = new ArrayDeque<>();
        nums.addLast(0);
        Deque<Character> ops = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == '(') {
                ops.addLast(c);
            } else if (c == ')') {
                while (!ops.isEmpty()) {
                    if (ops.peekLast() != '(') {
                        calc(nums, ops);
                    } else {
                        ops.pollLast();
                        break;
                    }
                }
            } else {
                if (isNumber(c)) {
                    int u = 0;
                    int j = i;
                    while (j < n && isNumber(cs[j])) u = u * 10 + (cs[j++] - '0');
                    nums.addLast(u);
                    i = j - 1;
                } else {
                    if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
                        nums.addLast(0);
                    }
                    while (!ops.isEmpty() && ops.peekLast() != '(') {
                        char prev = ops.peekLast();
                        if (map.get(prev) >= map.get(c)) {
                            calc(nums, ops);
                        } else {
                            break;
                        }
                    }
                    ops.addLast(c);
                }
            }
        }
        while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops);
        return nums.peekLast();
    }
    void calc(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() < 2) return;
        if (ops.isEmpty()) return;
        int b = nums.pollLast(), a = nums.pollLast();
        char op = ops.pollLast();
        int ans = 0;
        if (op == '+') {
            ans = a + b;
        } else if (op == '-') {
            ans = a - b;
        } else if (op == '*') {
            ans = a * b;
        } else if (op == '/') {
            ans = a / b;
        } else if (op == '^') {
            ans = (int)Math.pow(a, b);
        } else if (op == '%') {
            ans = a % b;
        }
        nums.addLast(ans);
    }
    boolean isNumber(char c) {
        return Character.isDigit(c);
    }
}

链表

k个一组翻转链表

CATALOG
  1. 1. 数组操作
    1. 1.1. 4 多数元素 数组统计
    2. 1.2. 5 轮转数组
    3. 1.3. 简单的贪心
    4. 1.4. 135 分糖果
  2. 2. 滑动窗口
  3. 3. 矩阵
  4. 4. 哈希表
  5. 5. 区间
  6. 6. 栈
  7. 7. 链表
Total : 73
2025
2024
2023
awdp pwn wp 算法 Android 逆向 linux awd php heap chop CSAPP Lab Develop Windows CVE go rust basic protobuf FSOP kernel exploits llvm Rust web fuzz exploit vm shellcode sandbox Others fuzzing 前端 develop kdump IDA 编译 ROP hvv
pwn linux CSAPP Reverse Develop Exploits pwn Exploit others kernel Web