刷题记录

Ikko Lv4
  2025-08-11 14:06:55 2025-08-11 14:06:55 Created   2025-12-29 23:24:29 2025-12-29 23:24:29 Updated    3.7k Words  17 Mins  

递归怎么写

又写错一道递归，于是乎总结一下递归的写法。

  1. 假设函数已经写好了
  2. 当前节点该怎么做
  3. 找“最小不需要处理的情况”
  4. return 用来“兑现函数定义”
    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
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        TreeNode* invertTree(TreeNode* root) {
            swap(root->left,root->right);
            return root;
        }
        TreeNode* swap(TreeNode* l,TreeNode* r) {
            if(l->left) l=swap(l->left,l->right);
            if(r->left) r=swap(r->left,r->right);
            TreeNode* temp=l;
            r=l;
            l=temp;
            return 

            
        }
    };

直线上最多的点数

这题有两个坑。1.首先不能用double存斜率，必须是化简字符形式，并且如此做还能解决斜率为无穷大的情况。2.对于每个i，每轮要清空map矩阵。因为在遍历i时已经把能和i共线的点遍历完了，若不清空则会出现平行线问题。

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
#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm> // 为了使用 __gcd (C++17前) 或 std::gcd (C++17)

using namespace std;

class Solution {
public:
    // 辅助函数：求最大公约数
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 2) return n;

        int result = 0;

        for (int i = 0; i < n; i++) {
            // Key 是字符串 "dy_dx"，Value 是计数
            unordered_map<string, int> count;
            int localMax = 0;

            for (int j = i + 1; j < n; j++) {
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];

                // 求最大公约数，进行化简
                int g = gcd(dx, dy);
                dx /= g;
                dy /= g;
                
                // 统一符号习惯：
                // 比如 (-1, -2) 和 (1, 2) 是一样的。
                // 我们通常规定：如果在 x 轴上是负的，就全取反；
                // 如果 x 是 0 (垂直线)，那么确保 y 是正的。
                if (dx < 0) {
                    dx = -dx;
                    dy = -dy;
                } else if (dx == 0) {
                    dy = abs(dy);
                }

                // 拼装成唯一 Key
                string key = to_string(dy) + "_" + to_string(dx);
                
                count[key]++;
                localMax = max(localMax, count[key]);
            }
            result = max(result, localMax + 1);
        }
        return result;
    }
};

异或运算的原理

异或运算（用符号 ^ 表示）有以下几个关键性质：

  1. 任何数和 0 异或，结果仍是它本身：
  2. 任何数和自身异或，结果为 0：
  3. 异或运算满足交换律和结合律：

Python 代码实现

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
def singleNumber(nums: list[int]) -> int:
    """
    使用异或运算找出数组中只出现一次的数字。

    Args:
        nums: 一个非空整数数组，其中一个元素只出现一次，其余元素均出现两次。

    Returns:
        那个只出现了一次的元素。
    """
    single = 0
    for num in nums:
        single ^= num
    return single

# 示例 1
nums1 = [2, 2, 1]
print(f"输入: {nums1}, 输出: {singleNumber(nums1)}")  # 输出: 1

# 示例 2
nums2 = [4, 1, 2, 1, 2]
print(f"输入: {nums2}, 输出: {singleNumber(nums2)}")  # 输出: 4

# 示例 3
nums3 = [1]
print(f"输入: {nums3}, 输出: {singleNumber(nums3)}")   # 输出: 1

摩尔投票算法（Boyer-Moore Voting Algorithm）。

这个算法的核心思想是“同归于尽”：如果一个数是多数元素（出现次数大于 ），那么它出现的次数比其他所有元素的出现次数总和还要多。我们可以通过互相抵消的方式来找到它。

摩尔投票算法的步骤

  1. 初始化：

    • candidate（候选人）变量：用于存储当前的多数元素候选。
    • count（计数器）变量：用于记录 candidate 的出现次数，初始值为0。

  2. 遍历数组：

    • 遍历数组 nums 中的每个元素 num。
    • 如果 count 为0，这意味着当前的 candidate 和之前的所有元素都抵消了。此时，我们将当前的 num 设为新的 candidate。
    • 如果当前的 num 等于 candidate，则 count 加1。
    • 如果当前的 num 不等于 candidate，则 count 减1。

  3. 返回结果：

    • 遍历结束后，candidate 变量中存储的值就是多数元素。由于题目保证多数元素总是存在，所以我们不需要额外的步骤来验证。

为什么这个算法有效？

想象一下，多数元素就像是“统治者”，它拥有的票数比其他所有元素的票数总和还要多。

  • 当遇到和 candidate 相同的元素时，count 加1，表示“统治者”的票数增加。
  • 当遇到和 candidate 不同的元素时，count 减1，表示“统治者”的票数被“其他元素”抵消了一张。
  • 由于多数元素的票数超过总票数的一半，它永远无法被完全抵消。最终，count 的值会大于0，而 candidate 最终存储的就是这个多数元素。

Python 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def majorityElement(nums: list[int]) -> int:
    candidate = 0
    count = 0

    for num in nums:
        if count == 0:
            candidate = num
        
        if num == candidate:
            count += 1
        else:
            count -= 1
    
    return candidate

# 示例 1
nums1 = [3, 2, 3]
print(f"输入: {nums1}, 输出: {majorityElement(nums1)}")  # 输出: 3

# 示例 2
nums2 = [2, 2, 1, 1, 1, 2, 2]
print(f"输入: {nums2}, 输出: {majorityElement(nums2)}")  # 输出: 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
#include <vector>

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) return 0;

        // 默认全都是质数 (true)
        vector<bool> isPrime(n, true);
        int count = 0;

        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                count++;
                // 性能优化：如果 i*i 已经大于 n 了，就没必要再筛了
                // 比如 n=25，当 i=5 时，5*5=25 已经越界
                if ((long long)i * i < n) {
                    // 从 i*i 开始排除，因为 2*i, 3*i 在之前已经被 2 和 3 筛过了
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = false;
                    }
                }
            }
        }
        return count;
    }
};

关键if ((long long)i * i < n) 否则会溢出，如将long long放入for循环条件中则增加执行开销。int: 在现代系统中几乎总是 32 位（最大约 21 亿）。

long long: C++ 标准规定至少 64 位，在所有现代系统中都是 64 位。

long: 这是一个“流浪汉”。在 Windows (64位) 上，它竟然只有 32 位（和 int 一样大）；而在 Linux/macOS (64位) 上，它是 64 位。
另外vector很慢可以使用

1
vector<char> isPrime(n, 1);

char c = 1;,00000001,1,SOH (标题开始，不可见控制字符)
char c = ‘1’;,00110001,49,字符 ‘1’ (可见的数字符号)

快速大小写转换

利用ASCII码表中大小写字母的对应关系进行转换，大写字母和小写字母之间相差32。

1
2
3
4
5
6
char upper = 'G';
// 大写变小写：加上这个距离
char lower = upper + ('a' - 'A'); // 'G' + 32 = 'g'

// 小写变大写：减去这个距离
char backToUpper = lower - ('a' - 'A'); // 'g' - 32 = 'G'

不使用+-

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int getSum(int a, int b) {
    while (b != 0) {
        unsigned carry = (unsigned)(a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

};

加油站

贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int total = 0;   // 全局油量
    int curr = 0;    // 当前油量
    int start = 0;

    for (int i = 0; i < gas.size(); i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        curr += diff;

        if (curr < 0) {
            // i 之前都不可能作为起点
            start = i + 1;
            curr = 0;
        }
    }

    return total >= 0 ? start : -1;
}

LRU缓存

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
class LRUCache {
public:
    int cap;
    list<pair<int,int>> cache; 
    unordered_map<int, list<pair<int,int>>::iterator> mp;

    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        if (mp.count(key) == 0) return -1;

        // 把访问的节点移动到链表头
        auto it = mp[key];
        cache.splice(cache.begin(), cache, it);
        return it->second;
    }

    void put(int key, int value) {
        if (mp.count(key)) {
            // key 已存在
            auto it = mp[key];
            it->second = value;
            cache.splice(cache.begin(), cache, it);
        } else {
            // key 不存在
            if (cache.size() == cap) {
                // 删除最久未使用
                auto last = cache.back();
                mp.erase(last.first);
                cache.pop_back();
            }
            cache.emplace_front(key, value);
            mp[key] = cache.begin();
        }
    }
};

get(key)：
如果 key 不存在 → return -1

如果存在：

  1. 拿到链表节点
  2. 把该节点移动到链表头
  3. 返回 value
    put(key, value)
    分三种情况：
    情况 1：key 已存在
  4. 更新 value
  5. 把节点移动到链表头
    情况 2：key 不存在，缓存未满
  6. 新节点插入链表头
  7. map 记录 key → 节点
    情况 3：key 不存在，缓存已满
  8. 删除链表尾（LRU）
  9. map.erase(尾节点的 key)
  10. 插入新节点到头部
    注意点：list::iterator it;
    unordered_map<int, list::iterator> mp;
    list::iterator：指向 list 里某个元素的“指针”

std::list O(1)cache.splice(cache.begin(), cache, it);

参数 含义
cache.begin() 插入位置（链表头）
cache 源链表
it 要移动的节点

滑动窗口

我刚开始做的时候，字典或者哈希表都是只存当前滑动窗口的值，每次判断时，判断该字符在不在哈希表中。实际上可以用哈希表只存z字符出现的最后下标，然后判断该下标是否在当前窗口内。（即下标 >= i ）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        if (n <= 1) return n;

        unordered_map<char, int> cc;
        int i = 0, result = 0;

        for (int j = 0; j < n; ++j) {
            if (cc.count(s[j]) && cc[s[j]] >= i) {
                i = cc[s[j]] + 1;
            }
            cc[s[j]] = j;
            result = max(result, j - i + 1);
        }
        return result;
    }
};

最小覆盖子串

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 “”。

测试用例保证答案唯一。
此题思路在于，窗口不包含，右边界移动，包含时左边界移动。
不使用全局变量的几种方式：

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
1.
class Solution {
public:
    string minWindow(string s, string t) {
    unordered_map<char,int> ori, cnt;
    for (char c : t) ori[c]++;

    auto check = [&]() {
        for (auto &[c, need] : ori) {
            if (cnt[c] < need) return false;
        }
        return true;
    };

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

    while (r + 1 < s.size()) {
        if (ori.count(s[++r])) cnt[s[r]]++;

        while (check()) {
            if (r - l + 1 < len) {
                len = r - l + 1;
                ansL = l;
            }
            if (ori.count(s[l])) cnt[s[l]]--;
            l++;
        }
    }

    return ansL == -1 ? "" : s.substr(ansL, len);
}
};
2.
bool check(unordered_map<char,int>& ori,
           unordered_map<char,int>& cnt) {
    for (auto &[c, need] : ori) {
        if (cnt[c] < need) return false;
    }
    return true;
}

string minWindow(string s, string t) {
    unordered_map<char,int> ori, cnt;
    for (char c : t) ori[c]++;

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

    while (r + 1 < s.size()) {
        if (ori.count(s[++r])) cnt[s[r]]++;

        while (check(ori, cnt)) {
            if (r - l + 1 < len) {
                len = r - l + 1;
                ansL = l;
            }
            if (ori.count(s[l])) cnt[s[l]]--;
            l++;
        }
    }

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

环形链表II

找环的入口

解法一：字典

这个字典存的节点的地址（指针）而不是节点的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> visited;
        while (head != nullptr) {
            if (visited.count(head)) {
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};

解法二：快慢指针+数学推理

根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有

a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
有了 a=c+(n−1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。

因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。
作者：力扣官方题解

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:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr) {
            slow = slow->next;
            if (fast->next == nullptr) {
                return nullptr;
            }
            fast = fast->next->next;
            if (fast == slow) {
                ListNode *ptr = head;
                while (ptr != slow) {
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr;
    }
};

合并K个升序链表

我写的，for循环ans+list[i]合并，可以考虑归并排序思想，两两合并

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0) return nullptr;
        ListNode* head = lists[0];
        for(int i=1;i<lists.size();i++){
            if(lists[i]){
                head=merge(head,lists[i]);
            }
        }
        return head;
    }
    ListNode* merge(ListNode* node1,ListNode* node2){
        ListNode* head;
        if(!node1) return node2;
        if(!node2) return node1;
        if(node1->val<node2->val){
                head=node1;
                node1=node1->next;
            }
        else{head=node2;
            node2=node2->next;}
        ListNode* curr=head;
        while(node1&&node2){
            if(node1->val<node2->val){
                curr->next=node1;
                node1=node1->next;
            }
            else{curr->next=node2;
            node2=node2->next;}
            curr=curr->next;
        }
        if(node1){
            curr->next=node1;
        }
        else{curr->next=node2;}
        return head;
    }
};
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
class Solution {
public:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b;
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                tail->next = bPtr; bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }

    ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

K个一组翻转链表

使用哨兵节点

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode() : val(0), next(nullptr) {}
 * ListNode(int x) : val(x), next(nullptr) {}
 * ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || k == 1) return head;

        // 1. 使用虚拟头节点，简化头部的处理逻辑
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        
        ListNode* pre = dummy;  // 上一组的结尾（翻转前的 dummy，翻转后的尾部）
        ListNode* end = dummy;  // 当前组的结尾

        while (end->next != nullptr) {
            // 2. 也就是找到每组的结尾 end
            for (int i = 0; i < k && end != nullptr; i++) {
                end = end->next;
            }
            // 如果剩余节点不足 k 个，不翻转，直接结束
            if (end == nullptr) break;

            // 记录下一组的开头，防止断链
            ListNode* start = pre->next;
            ListNode* nextGroupHead = end->next;

            // 3. 断开当前组与下一组的连接，以便独立翻转
            end->next = nullptr;

            // 4. 执行翻转，并将上一组的尾巴 pre 连接到翻转后的新头（即原来的 end）
            pre->next = reverseList(start);

            // 5. 连接翻转后的尾巴（原来的 start）到下一组的开头
            start->next = nextGroupHead;

            // 6. 重置指针，准备下一轮
            pre = start; // start 变成了当前组的尾巴，也就是下一组的 pre
            end = pre;   // end 重置回 pre，准备下一次寻找 k 个
        }

        return dummy->next;
    }

    // 这是一个标准的翻转整个链表的函数
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* next = curr->next;
            curr->next = pre;
            pre = curr;
            curr = next;
        }
        return pre; // 返回新的头节点
    }
};

做法二

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
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || k <= 1) return head;

        ListNode dummy(0);
        dummy.next = head;

        ListNode* last = &dummy;   // 已处理部分的尾
        ListNode* curr = head;     // 扫描指针

        int count = 0;

        while (curr) {
            count++;

            if (count == k) {
                // begin 是当前组的起点
                ListNode* begin = last->next;
                ListNode* end = curr;
                ListNode* nextGroup = end->next;

                // 反转 [begin, end]
                reverseSegment(last, begin, end);

                // last 移动到新尾
                last = begin;

                // 准备下一组
                curr = nextGroup;
                count = 0;
            } else {
                curr = curr->next;
            }
        }

        return dummy.next;
    }

private:
    // 反转 prev->next 到 end（闭区间）
    // 反转后 prev->next 指向 end
    void reverseSegment(ListNode* prev, ListNode* begin, ListNode* end) {
        ListNode* curr = begin;
        ListNode* stop = end->next;
        ListNode* prevNode = stop;

        while (curr != stop) {
            ListNode* next = curr->next;
            curr->next = prevNode;
            prevNode = curr;
            curr = next;
        }

        prev->next = end;
    }
};
  • Title: 刷题记录
  • Author: Ikko
  • Created at : 2025-08-11 14:06:55
  • Updated at : 2025-12-29 23:24:29
  • Link: http://ikko-debug.github.io/2025/08/11/算法/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
刷题记录
  1. 递归怎么写
  2. 直线上最多的点数
  3. 异或运算的原理
    1. Python 代码实现
  4. 摩尔投票算法（Boyer-Moore Voting Algorithm）。
    1. 摩尔投票算法的步骤
    2. 为什么这个算法有效？
    3. Python 代码实现
  5. 计数质数
  6. 快速大小写转换
  7. 不使用+-
  8. 加油站
  9. LRU缓存
  10. 滑动窗口
  11. 最小覆盖子串
  12. 环形链表II
    1. 解法一：字典
    2. 解法二：快慢指针+数学推理
  13. 合并K个升序链表
  14. K个一组翻转链表