LeetCodeHot100

Austin Deng2026/3/25大约 54 分钟

LeetCodeHot100

这篇文章记录了本人在 LeetCode 刷 LeetCode 热题100的相关代码、解题思路以及关键知识点等等

1. 两数之和[easy]

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

思路

用一个map记录之前遍历过的数以及对应的下标，如果之后的遍历刚刚好遇到需要的数(与之相加和为target)，直接返回即可

时间复杂度O(n)，一次遍历数组即可
空间复杂度O(n)，需要一个额外的map

代码

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        int n = nums.size();

        for(int i=0; i<n; i++) {
            if(m.count(nums[i])){
                return {i, m[nums[i]]};
            }else {
                m[target-nums[i]] = i;
            }
        }

        return {};
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {2, 7, 11, 15};
    int target1 = 9;
    vector<int> res1 = sol.twoSum(nums1, target1);
    cout << "Test case 1: nums = [2,7,11,15], target = 9" << endl;
    cout << "Result: [" << res1[0] << ", " << res1[1] << "]" << endl;
    cout << "Sum check: " << nums1[res1[0]] << " + " << nums1[res1[1]] << " = " 
         << nums1[res1[0]] + nums1[res1[1]] << endl << endl;

    vector<int> nums2 = {3, 2, 4};
    int target2 = 6;
    vector<int> res2 = sol.twoSum(nums2, target2);
    cout << "Test case 2: nums = [3,2,4], target = 6" << endl;
    cout << "Result: [" << res2[0] << ", " << res2[1] << "]" << endl;
    cout << "Sum check: " << nums2[res2[0]] << " + " << nums2[res2[1]] << " = " 
         << nums2[res2[0]] + nums2[res2[1]] << endl << endl;

    vector<int> nums3 = {3, 3};
    int target3 = 6;
    vector<int> res3 = sol.twoSum(nums3, target3);
    cout << "Test case 3: nums = [3,3], target = 6" << endl;
    cout << "Result: [" << res3[0] << ", " << res3[1] << "]" << endl;
    cout << "Sum check: " << nums3[res3[0]] << " + " << nums3[res3[1]] << " = " 
         << nums3[res3[0]] + nums3[res3[1]] << endl << endl;

    // 额外测试：无解情况
    vector<int> nums4 = {1, 2, 3};
    int target4 = 7;
    vector<int> res4 = sol.twoSum(nums4, target4);
    cout << "Test case 4: nums = [1,2,3], target = 7" << endl;
    if (res4.empty()) {
        cout << "No solution found (empty vector returned)" << endl;
    } else {
        cout << "Result: [" << res4[0] << ", " << res4[1] << "]" << endl;
    }

    return 0;
}

2. 字母异位词分组[minor]

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：
在 strs 中没有字符串可以通过重新排列来形成 "bat"。
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

思路
每个互为字母异位词的单词都包含相同的字母，因此把每个单词排序之后作为key，使用一个map记录同一个key的字母异位词即可

代码中使用了unordered_map数据结构，不禁令人想问unordered_map 和 map有什么区别呢？

C++ 中 unordered_map 和 map 的区别

特性	std::map	std::unordered_map
底层实现	红黑树 (自平衡二叉搜索树)	哈希表
元素顺序	根据键自动排序 (默认std::less，通常为升序)	无序 (顺序取决于哈希函数和插入顺序)
时间复杂度	插入、删除、查找：O(log n)	平均情况：插入、删除、查找：O(1) 最坏情况：O(n)
需要键的类型提供	必须定义比较操作 (如 <或自定义比较器)	必须定义哈希函数 (如 std::hash) 和相等比较 (如 ==)
迭代器性质	提供有序遍历，迭代器稳定 (除被删除元素外)	提供无序遍历，插入操作可能导致迭代器失效
内存使用	通常较低 (树节点开销)	通常较高 (维护哈希桶)
使用场景	需要元素有序遍历或按范围查询	需要极快的单点访问，且不关心顺序

核心总结与选择建议：

1. 有序 vs 无序：

这是最直观的区别。如果你需要按键的顺序（如字母顺序、数字大小）来遍历或处理元素，用 stdunordered_map。

2. 性能权衡：

std::map 的 O(log n)操作非常稳定，适合元素数量大或对单次操作最坏时间有要求的场景。
std::unordered_map 在平均情况下常数时间的访问速度极快，是大多数“查找表”的首选。但其性能严重依赖于哈希函数的质量。自定义类型作为键时，必须提供良好的哈希函数。

3. 自定义键类型：

为自定义类型使用 std::map，你只需要重载 <运算符或提供比较函子。
为自定义类型使用 std::unordered_map，你必须做两件事：
1. 提供计算哈希值的函子（或特化 std::hash）
2. 重载 ==运算符或提供相等比较函子

#include <iostream>
#include <map>
#include <unordered_map>

int main() {
    // std::map - 有序输出
    std::map<std::string, int> ordered_map = {{"zebra", 2}, {"apple", 5}};
    for (const auto& p : ordered_map) {
        std::cout << p.first << " "; // 输出：apple zebra
    }
    std::cout << std::endl;

    // std::unordered_map - 无序输出
    std::unordered_map<std::string, int> unordered_map = {{"zebra", 2}, {"apple", 5}};
    for (const auto& p : unordered_map) {
        std::cout << p.first << " "; // 输出可能是：zebra apple 或 apple zebra
    }
    return 0;
}

代码

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        for(string& str:strs) {
            string key = str;
            sort(key.begin(), key.end());
            m[key].emplace_back(str);
        }
        vector<vector<string>> res;
        for(auto it = m.begin(); it != m.end(); it++) {
            res.emplace_back(it->second);
        }
        return res;
    }
};

// 测试函数
void testGroupAnagrams() {
    Solution solution;
    
    // 测试用例1：标准情况
    {
        vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        vector<vector<string>> result = solution.groupAnagrams(strs);
        
        cout << "测试用例1: " << endl;
        for(const auto& group : result) {
            cout << "[";
            for(size_t i = 0; i < group.size(); i++) {
                cout << group[i];
                if(i != group.size() - 1) cout << ", ";
            }
            cout << "]" << endl;
        }
        cout << endl;
    }
    
    // 测试用例2：空数组
    {
        vector<string> strs = {};
        vector<vector<string>> result = solution.groupAnagrams(strs);
        
        cout << "测试用例2 (空数组): " << endl;
        cout << "分组数量: " << result.size() << endl << endl;
    }
    
    // 测试用例3：单个元素
    {
        vector<string> strs = {"abc"};
        vector<vector<string>> result = solution.groupAnagrams(strs);
        
        cout << "测试用例3 (单个元素): " << endl;
        for(const auto& group : result) {
            cout << "[";
            for(size_t i = 0; i < group.size(); i++) {
                cout << group[i];
                if(i != group.size() - 1) cout << ", ";
            }
            cout << "]" << endl;
        }
        cout << endl;
    }
    
    // 测试用例4：无字母异位词
    {
        vector<string> strs = {"abc", "def", "ghi"};
        vector<vector<string>> result = solution.groupAnagrams(strs);
        
        cout << "测试用例4 (无字母异位词): " << endl;
        for(const auto& group : result) {
            cout << "[";
            for(size_t i = 0; i < group.size(); i++) {
                cout << group[i];
                if(i != group.size() - 1) cout << ", ";
            }
            cout << "]" << endl;
        }
        cout << endl;
    }
    
    // 测试用例5：包含空字符串
    {
        vector<string> strs = {"", "a", "", "b"};
        vector<vector<string>> result = solution.groupAnagrams(strs);
        
        cout << "测试用例5 (包含空字符串): " << endl;
        for(const auto& group : result) {
            cout << "[";
            for(size_t i = 0; i < group.size(); i++) {
                cout << "\"" << group[i] << "\"";
                if(i != group.size() - 1) cout << ", ";
            }
            cout << "]" << endl;
        }
    }
}

int main() {
    testGroupAnagrams();
    return 0;
}

3. 最长连续序列[minor]

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：

输入：nums = [1,0,1,2]
输出：3

思路

题目要求连续的序列不必在原数组中是连续的，最朴素的方法就是排序然后一次遍历，找出最长连续子序列
但是排序的时间复杂度至少O(logn)，不符合题目要求

显然符合O(n)要求的只能一重遍历，不能排序

可以用一个set记录数组中存在的数，然后一次遍历数组，找到每个连续序列的开头，再依次查找连续的序列元素即可
使用set有一个好处就是能帮助去重

C++ 中 unordered_set 和 set 的区别

和上一题的 unordered_map 与 map 的区别是类似的，只是容器类型从关联数组变成了集合。

代码

#include <vector>
#include <unordered_set>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s;
        for(const int& i: nums) {
            s.insert(i);
        }

        int res = 0;
        for(const int& i: s) {
            if(!s.count(i-1)) {
                int step = 1;
                int curr = i;

                while(s.count(curr+1)) {
                    step++;
                    curr++;
                }

                res = max(res, step);
            }
        }

        return res;
    }
};

// 测试函数
void testLongestConsecutive() {
    Solution solution;
    
    // 测试用例1：标准情况
    {
        vector<int> nums = {100, 4, 200, 1, 3, 2};
        int result = solution.longestConsecutive(nums);
        cout << "测试用例1: [100, 4, 200, 1, 3, 2]" << endl;
        cout << "最长连续序列长度: " << result << endl;
        cout << "期望: 4 (序列: 1, 2, 3, 4)" << endl << endl;
    }
    
    // 测试用例2：空数组
    {
        vector<int> nums = {};
        int result = solution.longestConsecutive(nums);
        cout << "测试用例2 (空数组): []" << endl;
        cout << "最长连续序列长度: " << result << endl;
        cout << "期望: 0" << endl << endl;
    }
    
    // 测试用例3：单个元素
    {
        vector<int> nums = {5};
        int result = solution.longestConsecutive(nums);
        cout << "测试用例3 (单个元素): [5]" << endl;
        cout << "最长连续序列长度: " << result << endl;
        cout << "期望: 1" << endl << endl;
    }
    
    // 测试用例4：有重复元素
    {
        vector<int> nums = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
        int result = solution.longestConsecutive(nums);
        cout << "测试用例4 (有重复元素): [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]" << endl;
        cout << "最长连续序列长度: " << result << endl;
        cout << "期望: 9 (序列: 0, 1, 2, 3, 4, 5, 6, 7, 8)" << endl << endl;
    }
    
    // 测试用例5：负数
    {
        vector<int> nums = {-5, -3, -4, -2, -1, 0, 1};
        int result = solution.longestConsecutive(nums);
        cout << "测试用例5 (负数): [-5, -3, -4, -2, -1, 0, 1]" << endl;
        cout << "最长连续序列长度: " << result << endl;
        cout << "期望: 7 (序列: -5, -4, -3, -2, -1, 0, 1)" << endl << endl;
    }
    
    // 测试用例6：不连续序列
    {
        vector<int> nums = {10, 20, 30, 40};
        int result = solution.longestConsecutive(nums);
        cout << "测试用例6 (不连续序列): [10, 20, 30, 40]" << endl;
        cout << "最长连续序列长度: " << result << endl;
        cout << "期望: 1" << endl << endl;
    }
    
    // 测试用例7：多个连续序列
    {
        vector<int> nums = {1, 2, 3, 10, 11, 12, 20, 21, 22, 23};
        int result = solution.longestConsecutive(nums);
        cout << "测试用例7 (多个连续序列): [1, 2, 3, 10, 11, 12, 20, 21, 22, 23]" << endl;
        cout << "最长连续序列长度: " << result << endl;
        cout << "期望: 4 (序列: 20, 21, 22, 23)" << endl << endl;
    }
}

int main() {
    testLongestConsecutive();
    return 0;
}

4. 移动零[easy]

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:
1 <= nums.length <= 104
-2^31 <= nums[i] <= 2^31 - 1

思路

思路1：使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部
思路2：两次遍历，记录零的个数，填入到数组尾部

代码

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int cnt = 0;
        int idx = 0;
        for(int i=0; i<nums.size(); i++) {
            if(nums[i] == 0) {
                cnt += 1;
            } else {
                nums[idx] = nums[i];
                idx += 1;
            }
        }

        for(int i=nums.size()-1; i>=0 && cnt>0; i--) {
            nums[i] = 0;
            cnt--;
        }
    }
};

// 测试函数
void testMoveZeroes() {
    Solution solution;
    
    // 测试用例1: 普通情况
    {
        vector<int> nums = {0, 1, 0, 3, 12};
        vector<int> expected = {1, 3, 12, 0, 0};
        solution.moveZeroes(nums);
        cout << "测试用例1: ";
        assert(nums == expected);
        for (int num : nums) cout << num << " ";
        cout << "✓" << endl;
    }
    
    // 测试用例2: 全零数组
    {
        vector<int> nums = {0, 0, 0, 0};
        vector<int> expected = {0, 0, 0, 0};
        solution.moveZeroes(nums);
        cout << "测试用例2: ";
        assert(nums == expected);
        for (int num : nums) cout << num << " ";
        cout << "✓" << endl;
    }
    
    // 测试用例3: 无零数组
    {
        vector<int> nums = {1, 2, 3, 4, 5};
        vector<int> expected = {1, 2, 3, 4, 5};
        solution.moveZeroes(nums);
        cout << "测试用例3: ";
        assert(nums == expected);
        for (int num : nums) cout << num << " ";
        cout << "✓" << endl;
    }
    
    // 测试用例4: 单元素零
    {
        vector<int> nums = {0};
        vector<int> expected = {0};
        solution.moveZeroes(nums);
        cout << "测试用例4: ";
        assert(nums == expected);
        for (int num : nums) cout << num << " ";
        cout << "✓" << endl;
    }
    
    // 测试用例5: 单元素非零
    {
        vector<int> nums = {5};
        vector<int> expected = {5};
        solution.moveZeroes(nums);
        cout << "测试用例5: ";
        assert(nums == expected);
        for (int num : nums) cout << num << " ";
        cout << "✓" << endl;
    }
    
    // 测试用例6: 零在末尾
    {
        vector<int> nums = {1, 2, 3, 0, 0};
        vector<int> expected = {1, 2, 3, 0, 0};
        solution.moveZeroes(nums);
        cout << "测试用例6: ";
        assert(nums == expected);
        for (int num : nums) cout << num << " ";
        cout << "✓" << endl;
    }
    
    // 测试用例7: 零在开头
    {
        vector<int> nums = {0, 0, 1, 2, 3};
        vector<int> expected = {1, 2, 3, 0, 0};
        solution.moveZeroes(nums);
        cout << "测试用例7: ";
        assert(nums == expected);
        for (int num : nums) cout << num << " ";
        cout << "✓" << endl;
    }
    
    // 测试用例8: 交错零
    {
        vector<int> nums = {1, 0, 2, 0, 3, 0, 4};
        vector<int> expected = {1, 2, 3, 4, 0, 0, 0};
        solution.moveZeroes(nums);
        cout << "测试用例8: ";
        assert(nums == expected);
        for (int num : nums) cout << num << " ";
        cout << "✓" << endl;
    }
    
    cout << "\n所有测试用例通过！" << endl;
}

int main() {
    testMoveZeroes();
    return 0;
}

5. 盛最多水的容器[minor]

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49

示例 2：

输入：height = [1,1]
输出：1

思路

这题很明显用双指针一前一后找到最大的盛水量的索引

具体的：

初始化左指针在数组的首部，右指针在数组的尾部
计算当前左指针和右指针所能盛水的量，更新记录最大值
当左指针的数值较右指针小时，移动左指针向右；否则移动右指针向左
重复第二步直到左右指针相遇

时间复杂度：O(N)
空间复杂度：O(1)

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1;
        int res = 0;

        while (i < j) {
            int curr = min(height[i], height[j]) * (j - i);
            res = max(res, curr);

            if (height[i] <= height[j]) {
                i++;
            } else {
                j--;
            }
        }

        return res;
    }
};

// 测试用例
int main() {
    Solution solution;
    
    // 测试用例1: 示例
    vector<int> height1 = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    int result1 = solution.maxArea(height1);
    cout << "Test 1: " << result1 << " (Expected: 49)" << endl;
    
    // 测试用例2: 两个元素
    vector<int> height2 = {1, 1};
    int result2 = solution.maxArea(height2);
    cout << "Test 2: " << result2 << " (Expected: 1)" << endl;
    
    // 测试用例3: 递增序列
    vector<int> height3 = {1, 2, 3, 4, 5};
    int result3 = solution.maxArea(height3);
    cout << "Test 3: " << result3 << " (Expected: 6)" << endl;
    
    // 测试用例4: 递减序列
    vector<int> height4 = {5, 4, 3, 2, 1};
    int result4 = solution.maxArea(height4);
    cout << "Test 4: " << result4 << " (Expected: 6)" << endl;
    
    // 测试用例5: 高墙在中间
    vector<int> height5 = {4, 3, 2, 1, 4};
    int result5 = solution.maxArea(height5);
    cout << "Test 5: " << result5 << " (Expected: 16)" << endl;
    
    // 测试用例6: 只有一个元素
    vector<int> height6 = {1};
    int result6 = solution.maxArea(height6);
    cout << "Test 6: " << result6 << " (Expected: 0)" << endl;
    
    // 测试用例7: 随机测试
    vector<int> height7 = {2, 3, 4, 5, 18, 17, 6};
    int result7 = solution.maxArea(height7);
    cout << "Test 7: " << result7 << " (Expected: 17)" << endl;
    
    return 0;
}

6. 三数之和[minor]

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：
3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

思路

代码

7. 接雨水[major]

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：
n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

思路

代码

8. 无重复字符的最长子串[minor]

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成

思路

代码

9. 找到字符串中所有字母异位词[minor]

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

1 <= s.length, p.length <= 3 * 10^4
s 和 p 仅包含小写字母

思路

代码

10. 和为 K 的子数组[minor]

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数
子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7

思路

代码

11. 滑动窗口最大值[major]

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

思路

代码

12. 最小覆盖子串[major]

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的最短窗口子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。
测试用例保证答案唯一。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

m == s.length
n == t.length
1 <= m, n <= 10^5
s 和 t 由英文字母组成

思路

代码

13. 最大子数组和[minor]

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

思路

代码

14. 合并区间[minor]

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：

输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

提示：

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

思路

代码

15. 轮转数组[minor]

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5

思路

代码

16. 除了自身以外数组的乘积[minor]

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
输入保证数组 answer[i] 在 32 位整数范围内

思路

代码

17. 缺失的第一个正数[major]

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

思路

代码

18. 矩阵置零[minor]

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

思路

代码

19. 螺旋矩阵[minor]

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

思路

代码

20. 旋转图像[minor]

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

思路

代码

21. 搜索二维矩阵 II[minor]

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10^9 <= matrix[i][j] <= 10^9
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9

思路

代码

22. 相交链表[easy]

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须保持其原始结构。

自定义评测：

评测系统的输入如下（你设计的程序不适用此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

思路

代码

23. 反转链表[easy]

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：

输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

思路

代码

24. 回文链表[easy]

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true
示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路

代码

25. 环形链表[easy]

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

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

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

示例 1：

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

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

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个有效索引。

思路

代码

26. 环形链表 II[minor]

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

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

不允许修改链表。

示例 1：

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

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

思路

代码

27. 合并两个有序链表[easy]

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

思路

代码

28. 两数相加[minor]

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

思路

代码

29. 删除链表的倒数第 N 个结点[minor]

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

思路

代码

30. 两两交换链表中的节点[minor]

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：

输入：head = []
输出：[]
示例 3：

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

思路

代码

31. K 个一组翻转链表[major]

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

思路

代码

32. 随机链表的复制[minor]

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。

思路

代码

33. 排序链表[minor]

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

思路

代码

34. 合并 K 个升序链表[major]

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：

输入：lists = []
输出：[]
示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

思路

代码

35. LRU 缓存[minor]

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

思路

对于任意一颗树而言，前序遍历的形式总是

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

通过左子树的节点数，可以定位到左子树的前序遍历结果

因此我们可以得到：根节点+左子树的前序和中序+右子树的前序和中序

使用递归构建整棵树即可

时间复杂度：O(n)，其中 n 是树中的节点个数
空间复杂度：O(n)，其中 n 是树中的节点个数

代码


#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <climits>

using namespace std;

/**
 * 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:
    unordered_map<int, int> idx;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = inorder.size();
        for (int i = 0; i < n; i++) {
            idx[inorder[i]] = i;
        }
        TreeNode* root = dfs(preorder, inorder, 0, n - 1, 0, n - 1);
        return root;
    }

    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pre_left, int pre_right, int in_left, int in_right) {
        // 终止条件
        if (pre_left > pre_right || in_left > in_right) {
            return nullptr;
        }
        // 构造根节点
        TreeNode* root = new TreeNode(preorder[pre_left]);

        // 找到这个根节点在中序的位置
        int curr = preorder[pre_left];
        int curr_idx = idx[curr];

        // 左子树的节点数
        int left_num = curr_idx - in_left;

        root->left = dfs(preorder, inorder, pre_left + 1, pre_left + left_num, in_left, curr_idx - 1);
        root->right = dfs(preorder, inorder, pre_left + 1 + left_num, pre_right, curr_idx + 1, in_right);

        return root;
    }
};

// 层序遍历打印二叉树（用于验证结果）
void printTree(TreeNode* root) {
    if (!root) {
        cout << "[]" << endl;
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    vector<int> res;
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node) {
            res.push_back(node->val);
            q.push(node->left);
            q.push(node->right);
        } else {
            res.push_back(INT_MIN); // 用INT_MIN表示空节点
        }
    }
    // 去除末尾的空节点
    while (!res.empty() && res.back() == INT_MIN) {
        res.pop_back();
    }
    // 输出
    cout << "[";
    for (size_t i = 0; i < res.size(); i++) {
        if (res[i] == INT_MIN) {
            cout << "null";
        } else {
            cout << res[i];
        }
        if (i != res.size() - 1) {
            cout << ",";
        }
    }
    cout << "]" << endl;
}

// 测试用例
int main() {
    Solution sol;
    
    // 测试用例1: 普通二叉树
    // 前序遍历: [3,9,20,15,7]
    // 中序遍历: [9,3,15,20,7]
    // 预期树: [3,9,20,null,null,15,7]
    vector<int> preorder1 = {3, 9, 20, 15, 7};
    vector<int> inorder1 = {9, 3, 15, 20, 7};
    TreeNode* root1 = sol.buildTree(preorder1, inorder1);
    cout << "Test case 1: ";
    printTree(root1);
    
    // 测试用例2: 单节点
    vector<int> preorder2 = {1};
    vector<int> inorder2 = {1};
    TreeNode* root2 = sol.buildTree(preorder2, inorder2);
    cout << "Test case 2: ";
    printTree(root2);
    
    // 测试用例3: 左斜树
    // 前序遍历: [1,2,3]
    // 中序遍历: [3,2,1]
    // 预期树: [1,2,null,3]
    vector<int> preorder3 = {1, 2, 3};
    vector<int> inorder3 = {3, 2, 1};
    TreeNode* root3 = sol.buildTree(preorder3, inorder3);
    cout << "Test case 3: ";
    printTree(root3);
    
    // 测试用例4: 右斜树
    // 前序遍历: [1,2,3]
    // 中序遍历: [1,2,3]
    // 预期树: [1,null,2,null,3]
    vector<int> preorder4 = {1, 2, 3};
    vector<int> inorder4 = {1, 2, 3};
    TreeNode* root4 = sol.buildTree(preorder4, inorder4);
    cout << "Test case 4: ";
    printTree(root4);
    
    // 测试用例5: 空树
    vector<int> preorder5 = {};
    vector<int> inorder5 = {};
    TreeNode* root5 = sol.buildTree(preorder5, inorder5);
    cout << "Test case 5: ";
    printTree(root5);
    
    return 0;
}

48. 路径总和 III[minor]

思路

代码

49. 二叉树的最近公共祖先[minor]

思路

代码

50. 二叉树中的最大路径和[minor]

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其最大路径和。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

树中节点数目范围是 [1, 3 * 10^4]
-1000 <= Node.val <= 1000

思路

这是一道困难题，但是又是经典的一看就会，一写就废

首先明确题目是需要使用递归，那么要如何递归，边界是什么

对于每个节点，我们要找到包含该节点的最大路径，那么就是当前节点的值加上左右节点的最大路径，即：
currNode = root->val + right + left;
我们需要明确这里left和right的含义，它们表示这个节点的最大贡献，节点的最大贡献可以理解为以当前节点为起点的最大路径和
对于一个节点而言，最大贡献就等于root->val + max(left,right)
通过递归找到左右节点的最大贡献，考虑左右节点为负数的时候，我们需要丢弃掉，因此：
left = max(dfs(root -> left), 0);
right = max(dfs(root -> right), 0);

时间复杂度：O(N)
空间复杂度：O(N)

代码

#include <iostream>
#include <algorithm>
#include <climits>
#include <queue>
using namespace std;

/**
 * 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) {}
};

/**
 * Solution class for binary tree max path sum
 */
class Solution {
public:
    int res = INT_MIN;
    
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return res;
    }

    int dfs(TreeNode* root) {
        if(!root) return 0;

        int left = max(dfs(root->left), 0);
        int right = max(dfs(root->right), 0);

        res = max(res, left + right + root->val);

        return max(left, right) + root->val;
    }
};

/**
 * Utility class for tree operations
 */
class TreeUtils {
public:
    // Create a binary tree from level order traversal
    TreeNode* createTreeFromLevelOrder(const vector<int>& nodes) {
        if (nodes.empty() || nodes[0] == INT_MIN) return nullptr;
        
        TreeNode* root = new TreeNode(nodes[0]);
        queue<TreeNode*> q;
        q.push(root);
        
        int i = 1;
        while (!q.empty() && i < nodes.size()) {
            TreeNode* current = q.front();
            q.pop();
            
            // left child
            if (i < nodes.size() && nodes[i] != INT_MIN) {
                current->left = new TreeNode(nodes[i]);
                q.push(current->left);
            }
            i++;
            
            // right child
            if (i < nodes.size() && nodes[i] != INT_MIN) {
                current->right = new TreeNode(nodes[i]);
                q.push(current->right);
            }
            i++;
        }
        
        return root;
    }
    
    // Delete tree to prevent memory leak
    void deleteTree(TreeNode* root) {
        if (!root) return;
        deleteTree(root->left);
        deleteTree(root->right);
        delete root;
    }
    
    // Print tree in level order for verification
    void printTreeLevelOrder(TreeNode* root) {
        if (!root) {
            cout << "Empty tree" << endl;
            return;
        }
        
        queue<TreeNode*> q;
        q.push(root);
        
        cout << "Tree (level order): ";
        while (!q.empty()) {
            TreeNode* current = q.front();
            q.pop();
            
            if (current) {
                cout << current->val << " ";
                if (current->left || current->right) {
                    q.push(current->left);
                    q.push(current->right);
                }
            } else {
                cout << "null ";
            }
        }
        cout << endl;
    }
};

/**
 * Test cases
 */
void runTestCases() {
    Solution solution;
    TreeUtils treeUtils;
    
    cout << "Binary Tree Maximum Path Sum - Test Cases" << endl;
    cout << "=========================================" << endl;
    
    // Test Case 1: Simple positive tree
    {
        cout << "\nTest Case 1: Simple positive tree [1,2,3]" << endl;
        vector<int> nodes = {1, 2, 3};
        TreeNode* root = treeUtils.createTreeFromLevelOrder(nodes);
        treeUtils.printTreeLevelOrder(root);
        
        int result = solution.maxPathSum(root);
        cout << "Maximum Path Sum: " << result << endl;
        cout << "Expected: 6" << endl;
        
        treeUtils.deleteTree(root);
        solution.res = INT_MIN;  // Reset for next test
    }
    
    // Test Case 2: Complex tree with negative numbers
    {
        cout << "\nTest Case 2: Complex tree [-10,9,20,null,null,15,7]" << endl;
        vector<int> nodes = {-10, 9, 20, INT_MIN, INT_MIN, 15, 7};
        TreeNode* root = treeUtils.createTreeFromLevelOrder(nodes);
        treeUtils.printTreeLevelOrder(root);
        
        int result = solution.maxPathSum(root);
        cout << "Maximum Path Sum: " << result << endl;
        cout << "Expected: 42" << endl;
        
        treeUtils.deleteTree(root);
        solution.res = INT_MIN;
    }
    
    // Test Case 3: Single node
    {
        cout << "\nTest Case 3: Single node tree [5]" << endl;
        vector<int> nodes = {5};
        TreeNode* root = treeUtils.createTreeFromLevelOrder(nodes);
        treeUtils.printTreeLevelOrder(root);
        
        int result = solution.maxPathSum(root);
        cout << "Maximum Path Sum: " << result << endl;
        cout << "Expected: 5" << endl;
        
        treeUtils.deleteTree(root);
        solution.res = INT_MIN;
    }
    
    // Test Case 4: All negative numbers
    {
        cout << "\nTest Case 4: All negative tree [-3,-1,-2]" << endl;
        vector<int> nodes = {-3, -1, -2};
        TreeNode* root = treeUtils.createTreeFromLevelOrder(nodes);
        treeUtils.printTreeLevelOrder(root);
        
        int result = solution.maxPathSum(root);
        cout << "Maximum Path Sum: " << result << endl;
        cout << "Expected: -1" << endl;
        
        treeUtils.deleteTree(root);
        solution.res = INT_MIN;
    }
    
    // Test Case 5: Complex tree
    {
        cout << "\nTest Case 5: Complex tree [5,4,8,11,null,13,4,7,2,null,null,null,1]" << endl;
        vector<int> nodes = {5, 4, 8, 11, INT_MIN, 13, 4, 7, 2, INT_MIN, INT_MIN, INT_MIN, INT_MIN, INT_MIN, 1};
        TreeNode* root = treeUtils.createTreeFromLevelOrder(nodes);
        treeUtils.printTreeLevelOrder(root);
        
        int result = solution.maxPathSum(root);
        cout << "Maximum Path Sum: " << result << endl;
        cout << "Expected: 48" << endl;
        
        treeUtils.deleteTree(root);
        solution.res = INT_MIN;
    }
    
    // Test Case 6: Tree with zeros
    {
        cout << "\nTest Case 6: Tree with zeros [0,1,1]" << endl;
        vector<int> nodes = {0, 1, 1};
        TreeNode* root = treeUtils.createTreeFromLevelOrder(nodes);
        treeUtils.printTreeLevelOrder(root);
        
        int result = solution.maxPathSum(root);
        cout << "Maximum Path Sum: " << result << endl;
        cout << "Expected: 2" << endl;
        
        treeUtils.deleteTree(root);
        solution.res = INT_MIN;
    }
    
    cout << "\n=========================================" << endl;
    cout << "All test cases completed!" << endl;
}

/**
 * Main function
 */
int main() {
    runTestCases();
    return 0;
}

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

1 <= n <= 9

思路

用模拟法直接套回溯的模板就行

创建一个nxn的棋盘，然后依次校验每个位置是否可以放得下一个皇后

回溯的核心代码是这个：

for (int i = 0; i < n; i++) {
    if (!isValid(board, row, i)) {
        continue;
    }
    board[row][i] = 'Q';
    dfs(board, row + 1, n);
    board[row][i] = '.';
}

时间复杂度： O(n!×n)
空间复杂度：O(n)

n是皇后的数量

代码

#include <vector>
#include <string>
#include <iostream>

using namespace std;

class Solution {
public:
    vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        dfs(board, 0, n);
        return res;
    }

    void dfs(vector<string>& board, int row, int n) {
        if (row == n) {
            res.push_back(board);
            return;  // 返回上一层
        }

        for (int i = 0; i < n; i++) {
            if (!isValid(board, row, i)) {
                continue;
            }
            board[row][i] = 'Q';
            dfs(board, row + 1, n);
            board[row][i] = '.';
        }
    }

    bool isValid(vector<string>& board, int row, int col) {
        int n = board.size();
        // 检查同一列
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        // 检查右上斜线
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        // 检查左上斜线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
};

// 测试函数
int main() {
    Solution sol;
    int n = 4;
    vector<vector<string>> result = sol.solveNQueens(n);
    cout << "n = " << n << " 的解法有 " << result.size() << " 种：" << endl;
    for (int i = 0; i < result.size(); i++) {
        cout << "解法 " << i + 1 << ":" << endl;
        for (const string& row : result[i]) {
            cout << row << endl;
        }
        cout << endl;
    }
    return 0;
}

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 10^4

思路

我使用的是动态规划实现的

设dp[n]表示最少需要多少个数的平方来表示整数 n
那么我们在1...n中枚举j,那么j的平方数就是j*j，当j*j<n时,还需要n-j*j才能够到n
于是问题就变成：求n-j*j的最少完全平方数

典型的大问题转换成同等的小问题，状态转移方程：dp[n] = 1 + min{j=1..x}dp[n-j*j],其中x表示根号下n

代码

#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;

class Solution {
public:
    int numSquares(int n) {
        if (n <= 0) return 0;
        
        vector<int> dp(n + 1, 0);
        
        for (int i = 1; i <= n; i++) {
            int curr = INT_MAX;
            
            for (int j = 1; j * j <= i; j++) {
                curr = min(curr, dp[i - j * j]);
            }
            
            dp[i] = 1 + curr;
        }
        
        return dp[n];
    }
};

// 更高效的解法（使用静态变量）
class Solution2 {
public:
    int numSquares(int n) {
        static vector<int> dp({0});
        
        if (n < dp.size()) {
            return dp[n];
        }
        
        // 扩展dp数组
        for (int i = dp.size(); i <= n; i++) {
            int curr = INT_MAX;
            for (int j = 1; j * j <= i; j++) {
                curr = min(curr, dp[i - j * j]);
            }
            dp.push_back(1 + curr);
        }
        
        return dp[n];
    }
};

// 四平方定理解法（更高效）
class Solution3 {
public:
    int numSquares(int n) {
        // 先检查是否满足四平方定理的特殊情况
        // 1. 如果n是平方数，返回1
        int sqrt_n = sqrt(n);
        if (sqrt_n * sqrt_n == n) {
            return 1;
        }
        
        // 2. 检查是否满足n = 4^a*(8b+7)，即返回3
        int temp = n;
        while (temp % 4 == 0) {
            temp /= 4;
        }
        if (temp % 8 == 7) {
            return 4;
        }
        
        // 3. 检查是否是两个平方数之和
        for (int i = 1; i * i <= n; i++) {
            int j = n - i * i;
            int sqrt_j = sqrt(j);
            if (sqrt_j * sqrt_j == j) {
                return 2;
            }
        }
        
        // 4. 否则返回3
        return 3;
    }
};

// 测试函数
void testSolution() {
    Solution sol;
    Solution2 sol2;
    Solution3 sol3;
    
    vector<pair<int, int>> test_cases = {
        {1, 1},    // 1 = 1^2
        {2, 2},    // 2 = 1^2 + 1^2
        {3, 3},    // 3 = 1^2 + 1^2 + 1^2
        {4, 1},    // 4 = 2^2
        {5, 2},    // 5 = 1^2 + 2^2
        {6, 3},    // 6 = 1^2 + 1^2 + 2^2
        {7, 4},    // 7 = 1^2 + 1^2 + 1^2 + 2^2
        {8, 2},    // 8 = 2^2 + 2^2
        {9, 1},    // 9 = 3^2
        {10, 2},   // 10 = 1^2 + 3^2
        {12, 3},   // 12 = 2^2 + 2^2 + 2^2
        {13, 2},   // 13 = 2^2 + 3^2
        {16, 1},   // 16 = 4^2
        {17, 2},   // 17 = 1^2 + 4^2
        {18, 2},   // 18 = 3^2 + 3^2
        {19, 3},   // 19 = 1^2 + 3^2 + 3^2
        {20, 2},   // 20 = 2^2 + 4^2
        {48, 3},   // 48 = 4^2 + 4^2 + 4^2
        {100, 1},  // 100 = 10^2
        {101, 2},  // 101 = 1^2 + 10^2
        {102, 3},  // 102 = 1^2 + 1^2 + 10^2
        {103, 4},  // 103 = 1^2 + 1^2 + 1^2 + 10^2
    };
    
    cout << "测试动态规划解法（Solution）:" << endl;
    for (const auto& test_case : test_cases) {
        int n = test_case.first;
        int expected = test_case.second;
        int result = sol.numSquares(n);
        cout << "numSquares(" << n << ") = " << result 
             << " (期望: " << expected << ")" 
             << (result == expected ? " ✓" : " ✗") << endl;
    }
    
    cout << "\n测试带缓存的解法（Solution2）:" << endl;
    for (const auto& test_case : test_cases) {
        int n = test_case.first;
        int expected = test_case.second;
        int result = sol2.numSquares(n);
        cout << "numSquares(" << n << ") = " << result 
             << (result == expected ? " ✓" : " ✗") << endl;
    }
    
    cout << "\n测试四平方定理解法（Solution3）:" << endl;
    for (const auto& test_case : test_cases) {
        int n = test_case.first;
        int expected = test_case.second;
        int result = sol3.numSquares(n);
        cout << "numSquares(" << n << ") = " << result 
             << (result == expected ? " ✓" : " ✗") << endl;
    }
    
    // 测试一些大数字
    cout << "\n测试大数字的性能对比:" << endl;
    vector<int> large_numbers = {1000, 10000, 100000};
    
    for (int n : large_numbers) {
        cout << "\nn = " << n << ":" << endl;
        
        // 使用动态规划解法
        clock_t start = clock();
        int result1 = sol.numSquares(n);
        clock_t end = clock();
        double time1 = double(end - start) / CLOCKS_PER_SEC;
        cout << "  动态规划解法: " << result1 << " (耗时: " << time1 << "秒)" << endl;
        
        // 使用带缓存的解法
        start = clock();
        int result2 = sol2.numSquares(n);
        end = clock();
        double time2 = double(end - start) / CLOCKS_PER_SEC;
        cout << "  带缓存解法: " << result2 << " (耗时: " << time2 << "秒)" << endl;
        
        // 使用四平方定理解法
        start = clock();
        int result3 = sol3.numSquares(n);
        end = clock();
        double time3 = double(end - start) / CLOCKS_PER_SEC;
        cout << "  四平方定理解法: " << result3 << " (耗时: " << time3 << "秒)" << endl;
    }
}

int main() {
    cout << "========== 完全平方数问题测试 ==========" << endl;
    cout << "问题描述：给定正整数n，找到若干个完全平方数（如1,4,9,16,...）" << endl;
    cout << "使得它们的和等于n。你需要让组成和的完全平方数的个数最少。" << endl;
    cout << "======================================" << endl << endl;
    
    testSolution();
    
    // 交互式测试
    cout << "\n========== 交互式测试 ==========" << endl;
    Solution sol;
    int n;
    while (true) {
        cout << "\n请输入一个正整数（输入0退出）: ";
        cin >> n;
        
        if (n == 0) {
            cout << "程序结束！" << endl;
            break;
        }
        
        if (n < 0) {
            cout << "请输入正整数！" << endl;
            continue;
        }
        
        int result = sol.numSquares(n);
        cout << n << " 最少需要 " << result << " 个完全平方数" << endl;
        
        // 显示如何组合
        cout << "可能的组合方式: ";
        int temp = n;
        while (temp > 0) {
            // 找到最大的平方数
            for (int j = sqrt(temp); j >= 1; j--) {
                int square = j * j;
                if (sol.numSquares(temp - square) + 1 == result) {
                    cout << square;
                    temp -= square;
                    if (temp > 0) cout << " + ";
                    break;
                }
            }
        }
        cout << " = " << n << endl;
    }
    
    return 0;
}