Leetcode刷题笔记

本文最后更新于 2025年4月6日 下午

常用数据结构和算法

动态数组

创建二维动态数组

1
vector<vector <int> > ivec(m ,vector<int>(n,0));    //m*n的二维vector，所有元素为0

以打印杨辉三角为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result;
        if(numRows >= 1)
        result.push_back(vector<int>(1,1));		// 向第一行添加一个1
        else return result;
        if(numRows >= 2)
        result.push_back(vector<int>(2,1));		// 向第二行添加2个1
      	// 或写成result.push_back({1,1});
        else return result;
        for(int i = 2; i < numRows; i++){
            result.push_back(vector<int>(i + 1,1));
            for(int j = 1; j < i; j++)
            {
                result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
            }
        }
        return result;

    }
};
位运算

位运算可以简化很多操作，如判断一个数是否是2的幂，可以采用

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

LCP40 心算挑战

题目

「力扣挑战赛」心算项目的挑战比赛中，要求选手从 N 张卡牌中选出 cnt 张卡牌，若这 cnt 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 cnt 张卡牌数字总和。 给定数组 cards 和 cnt，其中 cards[i] 表示第 i 张卡牌上的数字。 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。

输入：cards = [1,2,8,9], cnt = 3

输出：18

解释：选择数字为 1、8、9 的这三张卡牌，此时可获得最大的有效得分 1+8+9=18。

思路和算法

将cards从大到小排序后，先贪心的将前cnt个数字加起来，若此时sum为偶数，直接返回即可。

若此时答案为奇数，有两种方案:

  • 在数组后面找到一个最大的奇数与前cnt个数中最小的偶数进行替换；

  • 在数组后面找到一个最大的偶数与前cnt个数中最小的奇数进行替换。

两种方案选最大值即可。

代码
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
class Solution {
public:
    int maxmiumScore(vector<int>& cards, int cnt) {
        sort(cards.begin(), cards.end(), greater<int>());
        int score = 0;
        int ans = 0;
        int odd = 0;
        int even = 0;
        for (int i = 0; i < cnt; ++i) {
        score += cards[i];
        if(cards[i] %2 == 0) even = cards[i];
        else odd = cards[i];
        }
        if(score % 2 == 0){
            return score;
        }
        else{
            for(int j = cnt; j < cards.size(); j++)
            {
            if(cards[j] %2 == 0 && odd) 
                ans = max(ans, score - odd + cards[j]);
            else if (even)
                ans = max(ans, score - even + cards[j]);
            }

        }
        return ans;
    }
};
复杂度分析

时间复杂度：$O(nlogn)$，其中$n$为数组的长度，主要开销在排序。

空间复杂度：$O(1)$。

T110 平衡二叉树

题目

给定一个二叉树，判断它是否是平衡二叉树。

思路和算法

根据定义，一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉树，因此可以使用递归的方式判断二叉树是不是平衡二叉树，递归的顺序可以是自顶向下或者自底向上。对于自顶向下，具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        } else {
            return max(height(root->left), height(root->right)) + 1;
        }
    }

    bool isBalanced(TreeNode* root) {
        if (root == NULL) {
            return true;
        } else {
            return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
        }
    }
};

由于是自顶向下递归，因此对于同一个节点，函数height会被重复调用，导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，函数height只会被调用一次。自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 −1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        int leftHeight = height(root->left);
        int rightHeight = height(root->right);
        if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return max(leftHeight, rightHeight) + 1;
        }
    }

    bool isBalanced(TreeNode* root) {
        return height(root) >= 0;
    }
};

T134 加油站

题目

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

思路和算法

核心的思路就是，假设我们从0行驶到5，之后就不能继续往前行驶，那么从1～5开始行驶也肯定不能往前行驶，因此从6开始考虑，这样只需要遍历一遍即可。

代码
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
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1;
            }
        }
        return -1;
    }
};

T136 只出现一次的数字

题目

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

输入：nums = [4,1,2,1,2]

输出：4

思路和算法

根据异或操作的性质，只需要将数组的所有元素进行一次异或运算，得到的结果就是只出现一次的数字。C++种异或运算符为^

代码
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for(int i = 0; i < nums.size(); i++){
            result ^= nums[i];
        }
        return result;
    }
};

T141 环形链表

题目

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

img

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

思路和算法一：哈希表

https://leetcode.cn/problems/linked-list-cycle/solutions/440042/huan-xing-lian-biao-by-leetcode-solution

最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。

具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> seen;
        while (head != nullptr) {
            if (seen.count(head)) {
                return true;
            }
            seen.insert(head);
            head = head->next;
        }
        return false;
    }
};
复杂度分析

时间复杂度：$O(N)$，其中 $N$ 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。

空间复杂度：$O(N)$，其中$ N$ 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。

思路和算法二：快慢指针

我们定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};
复杂度分析

时间复杂度：$O(N)$，其中$N$ 是链表中的节点数。

当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。

当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 $N$ 轮。

空间复杂度：$O(1)$。我们只使用了两个指针的额外空间。

T222 完全二叉树的节点个数

题目

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

思路和算法

https://leetcode.cn/problems/count-complete-tree-nodes/solutions/495655/wan-quan-er-cha-shu-de-jie-dian-ge-shu-by-leetco-2/

使用二进制数和二叉树的对应关系进行查找，如100代表根节点的左孩子的左孩子，也是完全二叉树的第6个节点。这样就可以通过对最低层的节点十进制序号进行二分查找，并使用位运算进行二进制匹配，就可以在更快的时间内完成。

代码
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
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int level = 0;
        TreeNode* node = root;
        while (node->left != nullptr) {
            level++;
            node = node->left;
        }
        int low = 1 << level, high = (1 << (level + 1)) - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (exists(root, level, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    bool exists(TreeNode* root, int level, int k) {
        int bits = 1 << (level - 1);
        TreeNode* node = root;
        while (node != nullptr && bits > 0) {
            if (!(bits & k)) {
                node = node->left;
            } else {
                node = node->right;
            }
            bits >>= 1;
        }
        return node != nullptr;
    }
};
复杂度分析

时间复杂度：$O(h^2)/O(log^2n)$。

空间复杂度：$O(1)$。

T258 各位相加

题目

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。

输入: num = 38
输出: 2
解释: 各位相加的过程为：
38 –> 3 + 8 –> 11
11 –> 1 + 1 –> 2
由于 2 是一位数，所以返回 2。

进阶：你可以不使用循环或者递归，在 O(1) 时间复杂度内解决这个问题吗？

思路和算法

https://leetcode.cn/problems/add-digits/solutions/1301157/ge-wei-xiang-jia-by-leetcode-solution-u4kj/

假设整数num的十进制表示有n位，从最低位到最高位依次是$a_0$到$a_{n−1}$，则 num可以写成
$$
\sum_{i=0}^{n-1}a_i \times (10^i-1) + \sum_{i=0}^{n-1}a_i
$$

对于任意非负整数 $i$，$10^i−1$ 都是 9 的倍数。由此可得num与其各位相加的结果模 9 同余。重复计算各位相加的结果直到结果为一位数时，该一位数即为 num 的数根，num 与其数根模 9 同余。由于最终结果取值为0～9，我们可以对num先减去1再取余，最后加上1，这样就能同时处理num是9的倍数（结果为9）和num为0的情况。

代码
1
2
3
4
5
6
class Solution {
public:
    int addDigits(int num) {
        return (num - 1) % 9 + 1;
    }
};
复杂度分析

时间复杂度：$O(1)$。

空间复杂度：$O(1)$。

T290 单词规律

题目

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = “abba”, s = “dog cat cat dog”

输出: true

示例 2:

输入:pattern = “abba”, s = “dog cat cat fish”

输出: false

示例 3:

输入: pattern = “aaaa”, s = “dog cat cat dog”

输出: false

思路和算法

https://leetcode.cn/problems/word-pattern/solutions/523102/dan-ci-gui-lu-by-leetcode-solution-6vqv/

在本题中，我们需要判断字符与字符串之间是否恰好一一对应。即任意一个字符都对应着唯一的字符串，任意一个字符串也只被唯一的一个字符对应。在集合论中，这种关系被称为「双射」。

想要解决本题，我们可以利用哈希表记录每一个字符对应的字符串，以及每一个字符串对应的字符。然后我们枚举每一对字符与字符串的配对过程，不断更新哈希表，如果发生了冲突，则说明给定的输入不满足双射关系。

在实际代码中，我们枚举 pattern 中的每一个字符，利用双指针来均摊线性地找到该字符在 str 中对应的字符串。每次确定一个字符与字符串的组合，我们就检查是否出现冲突，最后我们再检查两字符串是否比较完毕即可。

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:
    bool wordPattern(string pattern, string str) {
        unordered_map<string, char> str2ch;
        unordered_map<char, string> ch2str;
        int m = str.length();
        int i = 0;
        for (auto ch : pattern) {
            if (i >= m) {
                return false;
            }
            int j = i;
            while (j < m && str[j] != ' ') j++;
            string tmp = str.substr(i, j - i);
            if (str2ch.count(tmp) && str2ch[tmp] != ch) {
                return false;
            }
            if (ch2str.count(ch) && ch2str[ch] != tmp) {
                return false;
            }
            str2ch[tmp] = ch;
            ch2str[ch] = tmp;
            i = j + 1;
        }
        return i >= m;
    }
};
复杂度分析

时间复杂度：$O(n+m)$，其中 $n$ 为 $pattern$ 的长度，$m$ 为 $str$ 的长度。插入和查询哈希表的均摊时间复杂度均为 $O(n+m)$。每一个字符至多只被遍历一次。

空间复杂度：$O(n+m)$，其中 $n$ 为 $pattern$ 的长度，$m$ 为 $str$ 的长度。最坏情况下，我们需要存储 $pattern$ 中的每一个字符和 $str$ 中的每一个字符串。

T3128 直角三角形

题目

给你一个二维 boolean 矩阵 grid 。

请你返回使用 grid 中的 3 个元素可以构建的直角三角形数目，且满足3个元素值都为1。

注意：

  • 如果 grid 中 3 个元素满足：一个元素与另一个元素在 同一行，同时与第三个元素在 同一列 ，那么这 3 个元素称为一个 直角三角形 。这 3 个元素互相之间不需要相邻。

输入：grid = [[0,1,0],[0,1,1],[0,1,0]]

输出：2

解释：有 2 个直角三角形。

思路和算法

https://leetcode.cn/problems/right-triangles/solutions/2861202/zhi-jiao-san-jiao-xing-by-leetcode-solut-zbz2/

直接枚举三个点判断是否为直角三角形的方法未免过于低效，我们可以固定一个点，然后来统计其他两个点的合法方法数。

考虑枚举两条直角边的交点，然后将「该点所在行的其他点」与「该点所在列的其他点」一一匹配，即可得到所有以该点为直角边交点的所有方案。设 row 为交点所在行 1 的个数，col 为交点所在列 1 的个数，那么它的贡献是 (row−1)×(col−1)，将所有交点的贡献加起来就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    long long numberOfRightTriangles(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<int> col(m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                col[j] += grid[i][j];
            }
        }
        long long res = 0;
        for (int i = 0; i < n; i++) {
            int row = accumulate(grid[i].begin(), grid[i].end(), 0);
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    res += (row - 1) * (col[j] - 1);
                }
            }
        }
        return res;
    }
};
复杂度分析

时间复杂度：$O(nm)$，其中$n$是$grid$的行数，$m$是$grid$的列数。

空间复杂度：$O(m)$。

算法
#算法 #数据结构 #招聘
Leetcode刷题笔记
https://m0dzer0.github.io/2024/07/31/Leetcode刷题笔记/
作者
M0dZer0
发布于
2024年7月31日
许可协议