剑指Offer(专项突破版)

BT Agency by Mohamed Chahin

引言

本书全面、系统地总结了在准备程序员面试过程中必备的数据结构与算法。无论是计算机相关专业的应届毕业生还是初入职场的程序员，本书总结的数据结构和算法的基础知识及解题经验都不仅可以帮助他们提高准备面试的效率，还可以增加他们通过面试的成功率。

以下所有题目均来源 LeetCode 中国官网，题解由 doocs/leetcode 贡献者提供，正在完善中，欢迎贡献你的题解！
快速搜索题号、题解、标签等，请善用 Control+F（或者 Command+F）。

整数

整数除法[1]

题目描述

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1

示例 1：

输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7

示例 2：

输入：a = 7, b = -3
输出：0
解释：7/-3 = truncate(-2.33333..) = -2

示例 3：

输入：a = 0, b = 1
输出：0

示例 4：

输入：a = 1, b = 1
输出：1

提示:

$-2^{31}$ <= a, b <= $2^{31} - 1$
b != 0

注意：本题与主站 29 题相同：https://leetcode-cn.com/problems/divide-two-integers/

解法

一个很直观的想法是基于减法实现除法。例如，为了求 19/2 可以从 19 中不断减去 2，那么减去 9 个 2 以后就剩下 1，可以得到 19/2 = 9，但是效率很低，当被除数是 n,除数是 1 的时候，算法复杂度最差为 O(n)。如果将上述解法做一些调整，当被除数大于除数时，继续判断是不是大于除数的 2 倍？ 4 倍？ 8 倍？….如果被除数大于除数的 $2^k$ 倍，那么将被除数减去除数的 $2^k$ 倍，之后再重复以上步骤。

举个例子 19/2，19 大于 2，也大于 4 (2 * $2 ^ 1$)，也大于 8 (2 * $2 ^ 2$)，也大于 16 (2 * $2 ^ 3$)，但是小于 32 (2 * $2 ^ {4}$)，于是将 19 - 16 得到 3，并记录此时的答案 8，此时被除数变为 3，除数还是 2，重复上述结果得到此时答案为 1，剩下被除数 1，已经小于 2，最终结果为 8 + 1 = 9。算法复杂度为 O(logn)。

上述分析过程都是基于被除数和除数都是正整数，如果存在负整数则可以将他们先转化为正整数进行计算，最后根据符号调整结果。但是对于 32 位 int 来讲，最大的正数为 $2^{31}-1$,最小的负数为 $-2^{31}$,如果将负数转化为正数会溢出，所以可以将正数都转化为负数计算，核心部分就是对两个负数进行除法，返回的结果可以用无符号数返回，最后进行正负号调整。另外所有的结果中存在一种情况无法用 int 表示结果，那就是被除数为 $-2^{31}$，除数为 -1，这时候直接特殊判断输出 INT_MAX 就行。

通过下面这段伪代码，不难理解除法本质上就是减法，但是一次循环只能做一次减法，效率太低会导致超时，所以再加上快速幂的思想优化即可：

sign = -1 if a * b < 0 else 1
a = abs(a)
b = abs(b)
cnt = 0
while a >= b:
    a -= b
    cnt += 1
return sign * cnt

完整代码如下：

class Solution {
public:
    int divide(int a, int b) {
        if (a == INT_MIN && b == -1) {
            return INT_MAX;
        }
        int sign = 2;
        if (a > 0) {
            sign--;
            a = -a; 
        }
        if (b > 0) {
            sign--;
            b = -b;
        }

        unsigned int res = divideCore(a, b);
        return sign == 1? -res: res;        
    }

    int divideCore(int a, int b) {
        int res = 0;
        while(a <= b) {
            int value = b;
            unsigned int cnt = 1;

            while(value >= 0xc0000000 && a <= value + value) {
                cnt += cnt;
                value += value;
            }
            res += cnt;
            a -= value;
        }

        return res;
    }
};

这里 divideCore() 中 a <= b 是因为全部转换为负数，数值大的反而小。

二进制加法[2]

题目描述

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "10"
输出: "101"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

提示：

每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。

注意：本题与主站 67 题相同：https://leetcode-cn.com/problems/add-binary/

解法

模拟笔算加法的过程，注意进位：

class Solution {
public:
    string addBinary(string a, string b) {
        string res;
        int carry = 0;

        int i = a.size() - 1;
        int j = b.size() - 1;

        while (i >= 0 || j >= 0) {
            int digitA = i >= 0 ? a.at(i--) - '0' : 0;
            int digitB = j >= 0 ? b.at(j--) - '0' : 0;
            int sum = digitA + digitB + carry;
            carry = sum >= 2 ? 1 : 0;
            sum = sum >= 2 ? sum - 2 : sum;
            res += to_string(sum);
        }

        if (carry == 1) res.push_back('1');
        reverse(res.begin(), res.end());
        return res;
    }
};

前 n 个数字二进制中 1 的个数[3]

题目描述

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

示例 1:

输入: n = 2
输出: [0,1,1]
解释: 
0 --> 0
1 --> 1
2 --> 10

示例 2:

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

说明 :

0 <= n <= 10^5

进阶:

给出时间复杂度为 O(n*sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗？
要求算法的空间复杂度为 O(n)
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount ）来执行此操作

注意：本题与主站 338 题相同：https://leetcode-cn.com/problems/counting-bits/

解法

最直观的做法是对从 $0$ 到 $n$ 的每个整数直接计算「一比特数」。每个 $\texttt{int}$ 型的数都可以用 32 位二进制数表示，只要遍历其二进制表示的每一位即可得到 1 的数目。

利用 $\text{Brian Kernighan}$ 算法，可以在一定程度上进一步提升计算速度。$\text{Brian Kernighan}$ 算法的原理是：对于任意整数 $x$，令 $x=x&(x-1)$，该运算将 $x$ 的二进制表示的最后一个 1 变成 0。因此，对 $x$ 重复该操作，直到 $x$ 变成 $0$，则操作次数即为 $x$ 的「一比特数」。

对于给定的 $n$，计算从 $0$ 到 $n$ 的每个整数的「一比特数」的时间都不会超过 $O(\log n)$，因此总时间复杂度为 $O(n \log n)$。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n + 1);
        for (int i = 1; i <= n; i++) {
            res[i] = res[i & (i - 1)] + 1;
        }

        return res;
    }
};

只出现一次的数字[4]

题目描述

给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现 三次。请你找出并返回那个只出现了一次的元素。

示例 1：

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

示例 2：

输入：nums = [0,1,0,1,0,1,100]
输出：100

提示：

1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现一次外，其余每个元素都恰出现三次

进阶：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

注意：本题与主站 137 题相同：https://leetcode-cn.com/problems/single-number-ii/

解法

统计所有数字每个位中 1 出现的次数，对于某个位，1 出现的次数一定是 3 的倍数 +1 或 0。对这个数 %3 得到的结果就是那个出现一次的数字在该位上的值：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> bit(32);
        for (int num : nums)
            for (int i = 0; i < 32; i++)
                bit[i] += (num >> (31 - i)) & 1;

        int res = 0;
        for (int i = 0; i < 32; i++)
            res = (res << 1) + bit[i] % 3;
        return res;    
    }
};

单词长度的最大乘积[5]

题目描述

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

示例 1:

输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。

示例 2:

输入: words = ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。

示例 3:

输入: words = ["a","aa","aaa","aaaa"]
输出: 0 
解释: 不存在这样的两个单词。

提示：

2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母

注意：本题与主站 318 题相同：https://leetcode-cn.com/problems/maximum-product-of-word-lengths/

解法

因为只有 26 个小写字符，所以可以用一个哈希表存储字符的出现情况，然后枚举最大乘积：

class Solution {
public:
    int maxProduct(vector<string>& words) {
        vector<vector<bool>> hash(words.size(), vector<bool>(26, false));
        for (int i = 0; i < words.size(); i++)
            for (char c: words[i])
                hash[i][c - 'a'] = true;

        int res = 0;
        for (int i = 0; i < words.size(); i++) {
            for (int j = i + 1; j < words.size(); j++) {
                int k = 0;
                for (; k < 26; k++) {
                    if (hash[i][k] && hash[j][k])
                        break;
                }

                if (k == 26) {
                    int prod = words[i].size() * words[j].size();
                    res = max(res, prod);
                }
            }
        }
            
        return res;
    }
};

数组

排序数组中两个数字之和[6]

题目描述

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。

假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

示例 1：

输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[0,2]

示例 3：

输入：numbers = [-1,0], target = -1
输出：[0,1]

提示：

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 递增顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

注意：本题与主站 167 题相似（下标起点不同）：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

解法

双指针：

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

        while(i < j && numbers[i] + numbers[j] != target) {
            if (numbers[i] + numbers[j] < target)
                i++;
            else
                j--;
        }

        res.push_back(i);
        res.push_back(j);
        return res;
    }
};

数组中和为 0 的三个数[7]

题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

注意：本题与主站 15 题相同：https://leetcode-cn.com/problems/3sum/

解法

枚举第一个数，然后用双指针确定另外两个数。注意去重：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;

        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            int i = k + 1;
            int j = nums.size() - 1;
            if (k > 0 && nums[k] == nums[k - 1])
                continue;

            while(i < j) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    res.push_back(vector<int>{nums[k], nums[i], nums[j]});
                    i++;
                    j--;

                    while(i < j && nums[i] == nums[i - 1]) i++;
                    while(i < j && nums[j] == nums[j + 1]) j--;
                } else if (nums[i] + nums[j] + nums[k] < 0) {
                    i++;
                } else {
                    j--;
                }
            }
        }
        
        return res;
    }

};

和大于等于 target 的最短子数组[8]

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

注意：本题与主站 209 题相同：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

解法

同向双指针，注意边界条件：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right;
        int sum = 0; 
        int minlen = INT_MAX;

        for (right = 0; right < nums.size(); right++) {
            sum += nums[right];
            while(left <= right && sum >= target) {
                minlen = min(minlen, right - left + 1);
                sum -= nums[left++];
            }
        }

        return minlen == INT_MAX? 0: minlen;
    }
};

乘积小于 K 的子数组[9]

题目描述

给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1:

输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

示例 2:

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

提示:

1 <= nums.length <= 3 * 10^4
1 <= nums[i] <= 1000
0 <= k <= 10^6

注意：本题与主站 713 题相同：https://leetcode-cn.com/problems/subarray-product-less-than-k/

解法

利用滑动窗口，我们能求出每个不同 right 结尾的合法子数组的个数：

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int left = 0, right;
        long mul = 1;
        int count = 0;

        for (right = 0; right < nums.size(); right++) {
            mul *= nums[right];

            while(left <= right && mul >= k) {
                mul /= nums[left++];
            }

            count += right >= left? right - left + 1: 0;
        }

        return count;
    }
};

和为 k 的子数组[10]

题目描述

给定一个正整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

示例 2 :

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

提示:

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

注意：本题与主站 560 题相同： https://leetcode-cn.com/problems/subarray-sum-equals-k/

解法

数组中既有正数又有负数，无法使用双指针。可以利用前缀和思想，快速判断子数组的和。前缀和思想。遍历数组求前缀和，把前缀和以及这个和出现的次数作为键值对存入哈希表中。

举例理解：数组的前 i 个数字之和记为 sum，如果存在一个 j（j < i），数组的前 j 个数字之和为sum - k，那么数组中从第 j + 1个数字开始到第 i 个数字结束的子数组之和为 k。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        if (nums.size() < 0) return 0;

        int presum = 0;
        int count = 0;
        unordered_map<int, int> mp;
        mp[0] = 1;

        for (int right = 0; right < nums.size(); right++) {
            presum += nums[right];
            count += mp[presum - k];
            mp[presum]++;
        }

        return count;
    }
};

0 和 1 个数相同的子数组[11]

题目描述

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。

提示：

1 <= nums.length <= 10^5
nums[i] 不是 0 就是 1

注意：本题与主站 525 题相同： https://leetcode-cn.com/problems/contiguous-array/

解法

前缀和加哈希表，把 0 当作 -1 处理，题目变成求和为 0 的子数组：

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int presum = 0;
        int maxlen = 0;
        unordered_map<int, int> mp;
        mp[0] = -1;
        for (int i = 0; i < nums.size(); i++) {
            presum += nums[i] == 0? -1: 1;
            if (mp.find(presum) != mp.end())
                maxlen = max(maxlen, i - mp[presum]);
            else
                mp[presum] = i;    
        }

        return maxlen;
    }
};

左右两边子数组的和相等[12]

题目描述

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

示例 1：

输入：nums = [1,7,3,6,5,6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

示例 3：

输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

提示：

1 <= nums.length <= 104
-1000 <= nums[i] <= 1000

注意：本题与主站 724 题相同： https://leetcode-cn.com/problems/find-pivot-index/

解法

用前缀和进行预处理，避免重复计算。

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum = 0;
        int total = 0;
        for (int num: nums)
            sum += num;

        for (int i = 0; i < nums.size(); i++) {
            total += nums[i];
            if (total - nums[i] == sum - total)
                return i;
        }

        return -1;
    }
};

二维子矩阵的和[13]

题目描述

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。

示例 1：

输入:
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-10^5 <= matrix[i][j] <= 10^5
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 10^4 次 sumRegion 方法

注意：本题与主站 304 题相同： https://leetcode-cn.com/problems/range-sum-query-2d-immutable/

解法

动态规划-二维前缀和。

class NumMatrix {
private:
    vector<vector<int>> presum;

public:
    NumMatrix(vector<vector<int>>& matrix) {
        if (!matrix.size() || !matrix[0].size())
            return;
        presum.resize(matrix.size() + 1, vector<int>(matrix[0].size() + 1));
        
        for (int i = 0; i < matrix.size(); i++) {
            int rowsum = 0;
            for (int j = 0; j < matrix[0].size(); j++) {
                rowsum += matrix[i][j];
                presum[i + 1][j + 1] = presum[i][j + 1] + rowsum;
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return presum[row2 + 1][col2 + 1] - presum[row1][col2 + 1]
                                          - presum[row2 + 1][col1]
                                          + presum[row1][col1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */

字符串

字符串中的变位词[14]

题目描述

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例 1：

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例 2：

输入: s1= "ab" s2 = "eidboaoo"
输出: False

提示：

1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母

注意：本题与主站 567 题相同： https://leetcode-cn.com/problems/permutation-in-string/

解法

记录 s1 的哈希数组
确定左右指针的初始位置，并将当前所夹的子数组的字符出现情况与 s1 的哈希表进行比较
同时右移左右指针，左指针右移导致 ‘c’ 不在所夹的子数组中，所以将比较后的哈希数组中 ‘c’ 对应的值加 1，右指针右移导致 ‘b’ 进入所夹的子数组中，所以将比较后的哈希数组中 ‘b’ 对应的值减 1
重复步骤 3，直至找到答案或者遍历完 s2 均未找到答案

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.size() > s2.size())
            return false;

        vector<int> hash(26, 0), zero(26, 0);
        for (int i = 0; i < s1.size(); i++) {
            hash[s1[i] - 'a']++;
            hash[s2[i] - 'a']--;
        }

        if (hash == zero)
            return true;

        for (int i = s1.size(); i < s2.size(); i++) {
            hash[s2[i] - 'a']--;
            hash[s2[i - s1.size()] - 'a']++;
            if (hash == zero) return true;
        }

        return false;
    }
};

字符串中的所有变位词[15]

题目描述

给定两个字符串 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 * 104
s 和 p 仅包含小写字母

注意：本题与主站 438 题相同： https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

解法

和上一题一样的思路，利用固定长度滑动窗口：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        vector<int> hash(26, 0), zero(26, 0);

        if (p.size() > s.size())
            return res;

        for (int i = 0; i < p.size(); i++) {
            hash[p[i] - 'a']++;
            hash[s[i] - 'a']--;
        }

        if (hash == zero)
            res.push_back(0);

        for (int i = p.size(); i < s.size(); i++) {
            hash[s[i] - 'a']--;
            hash[s[i - p.size()] - 'a']++;

            if (hash == zero)
                res.push_back(i - p.size() + 1);
        }    


        return res;
    }
};

不含重复字符的最长子字符串[16]

题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

输入: s = ""
输出: 0

提示：

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

注意：本题与主站 3 题相同： https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

解法

因为 s 中可能会出现字母、数字、符号和空格，所以可以用哈希表表示窗口：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0)
            return 0;

        int left = 0;
        int maxlen = 0;
        unordered_set<char> hash;

        for (int right = 0; right < s.size(); right++) {
            while (hash.find(s[right]) != hash.end()) {
                hash.erase(s[left]);
                left++;
            }

            hash.insert(s[right]);
            maxlen = max(maxlen, right - left + 1);
        }

        return maxlen;
    }
};

含有所有字符的最短字符串[17]

题目描述

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。

如果 s 中存在多个符合条件的子字符串，返回任意一个。

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'

示例 2：

输入：s = "a", t = "a"
输出："a"

示例 3：

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

提示：

1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

注意：本题与主站 76 题相似（本题答案不唯一）：https://leetcode-cn.com/problems/minimum-window-substring/

解法

链表

删除链表的倒数第 n 个结点[21]

题目描述

给定一个链表，删除链表的倒数第 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

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

注意：本题与主站 19 题相同： https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

解法

利用快慢指针和虚拟头节点。

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);

        ListNode* p = dummy;
        ListNode* q = head;
        while (n--)
            q = q->next;

        while (q) {
            p = p->next;
            q = q->next;
        }

        p->next = p->next->next;
        return dummy->next;
    }
};

链表中环的入口节点[22]

题目描述

给定一个链表，返回链表开始入环的第一个节点。从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

示例 1：

![](https://cdn.jsdelivr.net/gh/doocs/leetcode@main/lcof2/剑指 Offer II 022. 链表中环的入口节点/images/circularlinkedlist.png)

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

示例 2：

![](https://cdn.jsdelivr.net/gh/doocs/leetcode@main/lcof2/剑指 Offer II 022. 链表中环的入口节点/images/circularlinkedlist_test2.png)

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

示例 3：

![](https://cdn.jsdelivr.net/gh/doocs/leetcode@main/lcof2/剑指 Offer II 022. 链表中环的入口节点/images/circularlinkedlist_test3.png)

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

提示：

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

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

注意：本题与主站 142 题相同： https://leetcode-cn.com/problems/linked-list-cycle-ii/

解法

先利用快慢指针判断链表是否有环，没有环则直接返回 null。

若链表有环，我们分析快慢相遇时走过的距离：
$$
a + n(b + c) + b = a + (n + 1)b + c \\
a + (n + 1)b + c = 2(a + b) \to a = c + (n - 1)(b + c)
$$

我们会发现：从相遇点到入环点的距离加上 $n-1$ 圈的环长，恰好等于从链表头部到入环点的距离。

/**
 * 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) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (true) {
            if (fast == nullptr || fast->next == nullptr) 
                return nullptr;

            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) break;
        }


        fast = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }


        return fast;
    }
};

两个链表的第一个重合节点[23]

题目描述

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

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

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

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

示例 1：

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

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,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
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

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

进阶：能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

注意：本题与主站 160 题相同：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

解法

使用双指针，细想就会发现很简单很巧妙。

A 和 B 两个链表长度可能不同，但是 A + B 和 B + A 的长度是相同的，所以遍历 A + B 和遍历 B + A 一定是同时结束：

如果 A、B 相交的话 A 和 B 有一段尾巴是相同的，所以两个遍历的指针一定会同时到达交点
如果 A、B 不相交的话两个指针就会同时到达 A + B（B + A）的尾节点（然后同时变成nullptr）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* pa = headA;
        ListNode* pb = headB;

        while (pa != pb) {
            pa = pa? pa->next: headB;
            pb = pb? pb->next: headA;
        }

        return pa;
    }
};

反转链表[24]

题目描述

给定单链表的头节点 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

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

注意：本题与主站 206 题相同： https://leetcode-cn.com/problems/reverse-linked-list/

解法

直接背诵了，可以看到几个等式成一个环状收尾相连：

succ--cur->next--pre--cur--succ

完整代码如下：

/**
 * 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* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* succ = nullptr;

        while (cur) {
            succ = cur->next;
            cur->next = pre;
            pre = cur;
            cur = succ;
        }
        return pre;

    }
};

链表中的两数相加[25]

题目描述

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：

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

提示：

链表的长度范围为[1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0

进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。

注意：本题与主站 445 题相同：https://leetcode-cn.com/problems/add-two-numbers-ii/

解法

对链表进行翻转
设置一个空节点 dummy，也就是末尾节点，和一个进位数 carry
遍历链表 l1、l2，条件是链表1，2不为空和进位数大于 0
求出当前位数，生成节点
对当前节点的 next 指向上一个节点（逆序）和求进位到下一个的数
三目运算符对链表进行下一个指向判断

/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        l1 = reverse(l1);
        l2 = reverse(l2);
        ListNode* dummy = new ListNode(0);
        ListNode* l = dummy;

        while (l1 || l2) {
            int sum = (l1? l1->val: 0) + (l2? l2->val: 0) + carry;
            carry = sum >= 10? 1: 0;
            sum = sum >= 10? sum - 10: sum;
            
            l->next = new ListNode(sum);
            l = l->next;
            
            l1 = l1? l1->next: nullptr;
            l2 = l2? l2->next: nullptr;
        }

        if (carry)
            l->next = new ListNode(carry);
        return reverse(dummy->next);
    }


    ListNode* reverse(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* succ = nullptr;

        while (cur) {
            succ = cur->next;
            cur->next = pre;
            pre = cur;
            cur = succ;
        }

        return pre;
    }
};

重排链表[26]

题目描述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

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

示例 1:

输入: head = [1,2,3,4]
输出: [1,4,2,3]

示例 2:

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

提示：

链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000

注意：本题与主站 143 题相同：https://leetcode-cn.com/problems/reorder-list/

解法

相当于这 3 道问题，只需要 5 行代码将它们组合：

[链表的中间结点](https://doocs.github.io/leetcode/#/solution/0800-0899/0876.Middle of the Linked List/README)
[反转链表](https://doocs.github.io/leetcode/#/solution/0200-0299/0206.Reverse Linked List/README)
合并两个链表

/**
 * 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:
    void reorderList(ListNode* head) {
        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* slow = dummy;
        ListNode* fast = dummy;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* cur = dummy->next;
        ListNode* mid = slow->next;
        slow->next = nullptr;
        mid = reverseList(mid);

        while (mid) {
            ListNode* tmp = cur->next;
            cur->next = mid;
            cur = cur->next;

            mid = mid->next;
            cur->next = tmp;
            cur = cur->next;
        }
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* succ = nullptr;

        while (cur) {
            succ = cur->next;
            cur->next = pre;
            pre = cur;
            cur = succ;
        }

        return pre;
    }
};

回文链表[27]

题目描述

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

输入: head = [1,2,3,3,2,1]
输出: true

示例 2：

输入: head = [1,2]
输出: fasle

提示：

链表 L 的长度范围为 [1, 10^5]
0 <= node.val <= 9

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

注意：本题与主站 234 题相同：https://leetcode-cn.com/problems/palindrome-linked-list/

解法

先用快慢指针找到链表的中点，接着反转右半部分的链表。然后同时遍历前后两段链表，若前后两段链表节点对应的值不等，说明不是回文链表，否则说明是回文链表。

/**
 * 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:
    bool isPalindrome(ListNode* head) {
        if (head->next == 0) 
            return true;

        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* slow = dummy;
        ListNode* fast = dummy;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* cur = dummy->next;
        ListNode* mid = slow->next;
        slow->next = nullptr;
        mid = reverseList(mid);

        while (mid) {
            if (cur->val != mid->val)
                return false;

            cur = cur->next;
            mid = mid->next;    
        }

        return true;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* succ = nullptr;

        while (cur) {
            succ = cur->next;
            cur->next = pre;
            pre = cur;
            cur = succ;
        }

        return pre;
    }
};

展平多级双向链表[28]

题目描述

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

示例 1：

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

示例 2：

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：

输入的多级列表如下图所示：

  1---2---NULL
  |
  3---NULL

示例 3：

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

如何表示测试用例中的多级链表？

以 示例 1 为例：

1---2---3---4---5---6--NULL
        |
        7---8---9---10--NULL
            |
            11--12--NULL

序列化其中的每一级之后：

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]

合并所有序列化结果，并去除末尾的 null 。

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

提示：

节点数目不超过 1000
1 <= Node.val <= 10^5

注意：本题与主站 430 题相同： https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list/

解法

仔细观察一下这个结构，不难发现其实就是前序遍历二叉树：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

class Solution {
public:
    Node* flatten(Node* head) {
        flattenGetTail(head);
        return head;
    }

    Node* flattenGetTail(Node* head) {
        Node* cur = head;
        Node* tail = nullptr;

        while (cur) {
            Node* next = cur->next;
            if (cur->child) {
                Node* child = cur->child;
                Node* childTail = flattenGetTail(cur->child);

                cur->child = nullptr;
                cur->next = child;
                child->prev = cur;
                childTail->next = next;

                if (next)
                    next->prev = childTail;
                tail = childTail;

            } else {
                tail = cur;
            }


            cur = next;
        }

        return tail;
    }
};

排序的循环链表[29]

题目描述

给定循环升序列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

示例 1：

输入：head = [3,4,1], insertVal = 2
输出：[3,4,1,2]
解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。

示例 2：

输入：head = [], insertVal = 1
输出：[1]
解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。

示例 3：

输入：head = [1], insertVal = 0
输出：[1,0]

提示：

0 <= Number of Nodes <= 5 * 10^4
-10^6 <= Node.val <= 10^6
-10^6 <= insertVal <= 10^6

注意：本题与主站 708 题相同： https://leetcode-cn.com/problems/insert-into-a-sorted-circular-linked-list/

解法

头节点如果为空或仅为一个，直接返回 head或连成环
如果 insertVal 在链表的最小值和最大值之间，找到合适的位置插入
如果 insertVal 小于链表的最小值或大于链表的最大值，则在头节点和尾节点之间插入

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        Node* insert = new Node(insertVal);
        if (head == nullptr) {
            head = insert;
            head->next = head;
        } else if (head->next == nullptr) {
            head->next = insert;
            insert->next = head;
        } else {
            insertCore(head, insert);
        }

        return head;
    }

    void insertCore(Node* head, Node* insert) {
        Node* cur = head;
        Node* maxNode = head;
        Node* next = head->next;

        while (!(cur->val <= insert->val && insert->val <= next->val) && next != head) {
            cur = next;
            next = next->next;

            if (cur->val >= maxNode->val)
                maxNode = cur;
        }

        if (cur->val <= insert->val && insert->val <= next->val) {
            insert->next = next;
            cur->next = insert;
        } else {
            insert->next = maxNode->next;
            maxNode->next = insert;
        }


    }
};

哈希表

插入、删除和随机访问都是 O(1) 的容器[30]

题目描述

设计一个支持在平均时间复杂度 O(1) 下，执行以下操作的数据结构：

insert(val)：当元素 val 不存在时返回 true ，并向集合中插入该项，否则返回 false 。
remove(val)：当元素 val 存在时返回 true ，并从集合中移除该项，否则f返回 true 。
getRandom：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。

示例 :

输入: inputs = ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出: [null, true, false, true, 2, true, false, 2]
解释:
RandomizedSet randomSet = new RandomizedSet();  // 初始化一个空的集合
randomSet.insert(1); // 向集合中插入 1 ， 返回 true 表示 1 被成功地插入

randomSet.remove(2); // 返回 false，表示集合中不存在 2

randomSet.insert(2); // 向集合中插入 2 返回 true ，集合现在包含 [1,2]

randomSet.getRandom(); // getRandom 应随机返回 1 或 2

randomSet.remove(1); // 从集合中移除 1 返回 true 。集合现在包含 [2]

randomSet.insert(2); // 2 已在集合中，所以返回 false

randomSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2

提示：

-2^31 <= val <= 2^31 - 1
最多进行2 * 10^5 次 insert ， remove 和 getRandom 方法调用
当调用 getRandom 方法时，集合中至少有一个元素

注意：本题与主站 380 题相同：https://leetcode-cn.com/problems/insert-delete-getrandom-o1/

解法

由于题目要求删除和插入的时间复杂度为 O(1)，能够满足要求的只有哈希表，显然此处需要使用哈希表。

但是使用哈希表无法等概率返回其中的每个数值。若这些数值是保存在数组内，则可以轻松解决。但若只使用数组，那么删除和插入一个值时，都需遍历一遍数组找到数值对应的下标，则会使时间复杂度为 O(n)。

故可将哈希表和数组结合，数组内存数值实现 getRandom，哈希内存数值和下标的映射实现 insert 和 remove 的索引查找的时间复杂度为 O(1)，之后在数组内操作数值的插入和删除。具体来看操作就是：

插入

每次添加新数值时，先使用哈希表判断该数值是否存在，存在则直接返回 false。不存在则进行插入操作，只要将该数值添加到数组尾部即可，并将该数值和其下标的映射存入哈希表。

删除

删除同样需使用哈希表判断是否存在，若不存在则返回 false。存在则进行删除操作，在哈希表中删除时间复杂度为 O(1)，但是在数值中删除比较麻烦。若只是直接删除，则为了保证数组内存连续性需将删除数值后面的数值均前移一位，时间复杂度为 O(n)。比较好的处理方式是，用数组的最后一个数值去填充需要删除的数值的内存，其他数值在数组中的位置保持不变，并将这个拿来填充的数值的下标更新即可，最后只要删除数组最后一个数值，同样可以保证时间复杂度为 O(1)。

随机返回

只要随机生成数组下标范围内一个随机下标值，返回该数组下标内的数值即可。

class RandomizedSet {
    unordered_map<int, int> mp;
    vector<int> nums;
public:
    RandomizedSet() {

    }

    bool insert(int val) {
        if (mp.count(val))
            return false;

        mp[val] = nums.size();
        nums.push_back(val);
        return true;
    }

    bool remove(int val) {
        if (!mp.count(val))
            return false;

        int removeIndex = mp[val];
        nums[removeIndex] = nums.back();
        mp[nums.back()] = removeIndex;
        
        mp.erase(val);
        nums.pop_back();
        return true;
    }

    int getRandom() {
        return nums[rand() % nums.size()];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

[未解决]最近最少使用缓存[31]

有效的变位词[32]

题目描述

给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。

注意：若 *s* 和 *t* 中每个字符出现的次数都相同且字符顺序不完全相同，则称 *s* 和 *t* 互为变位词（字母异位词）。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

示例 3:

输入: s = "a", t = "a"
输出: false

提示:

1 <= s.length, t.length <= 5 * 104
s and t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

注意：本题与主站 242 题相似（字母异位词定义不同）：https://leetcode-cn.com/problems/valid-anagram/

解法

数组或哈希表累加 s 中每个字符出现的次数，再减去 t 中对应的每个字符出现的次数。遍历结束后，若字符中出现次数不为 0 的情况，返回 false，否则返回 true。

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size() || s == t)
            return false;

        vector<int> hash(26, 0), zero(26, 0);
        for (int i = 0; i < t.size(); i++) {
            hash[t[i] - 'a']++;
            hash[s[i] - 'a']--;
        }

        if (hash == zero)
            return true;

        return false;
    }
};

变位词组[33]

题目描述

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

注意：若两个字符串中每个字符出现的次数都相同且字符顺序不完全相同，则称它们互为变位词。

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

注意：本题与主站 49 题相同： https://leetcode-cn.com/problems/group-anagrams/

解法

遍历字符串，将每个字符串按照字符字典序排序后得到一个新的字符串，将相同的新字符串放在哈希表的同一个 key 对应 value 列表中。

key	value
`"aet"`	`["eat", "tea", "ate"]`
`"ant"`	`["tan", "nat"]`
`"abt"`	`["bat"]`

最后返回哈希表的 value 列表即可。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> hash(strs.size());

        for (auto str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            hash[key].emplace_back(str);
        }

        for (auto it = hash.begin(); it != hash.end(); it++) {
            res.emplace_back(it->second);
        }

        return res;
    }
};

外星语言是否排序[34]

题目描述

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

示例 1：

输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
输出：true
解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。

示例 2：

输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
输出：false
解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。

示例 3：

输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
输出：false
解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。

提示：

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
在 words[i] 和 order 中的所有字符都是英文小写字母。

注意：本题与主站 953 题相同： https://leetcode-cn.com/problems/verifying-an-alien-dictionary/

解法

用数组或哈希表存放字母顺序。依次遍历单词列表，检测相邻两单词是否满足字典序。

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        for (int i = 0; i < words.size() - 1; i++) {
            if (!isOrdered(words[i], words[i + 1], order))
                return false;
        }

        return true;
    }

    bool isOrdered(string word1, string word2, string order) {
        vector<int> hash(26, 0);
        for (int i = 0; i < 26; i++) {
            hash[order[i] - 'a'] = i;
        }

        int i;
        for (i = 0; i < word1.size() && i < word2.size(); i++) {
            char ch1 = word1[i];
            char ch2 = word2[i];
            if (hash[ch1 - 'a'] < hash[ch2 - 'a'])
                return true;
            else if (hash[ch1 - 'a'] > hash[ch2 - 'a'])
                return false;    
        }

        return i == word1.size();
    }

};

最小时间差[35]

题目描述

给定一个 24 小时制（小时:分钟 **”HH:MM”**）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

示例 1：

输入：timePoints = ["23:59","00:00"]
输出：1

示例 2：

输入：timePoints = ["00:00","23:59","00:00"]
输出：0

提示：

2 <= timePoints <= 2 * 10^4
timePoints[i] 格式为 “HH:MM”

注意：本题与主站 539 题相同： https://leetcode-cn.com/problems/minimum-time-difference/

解法

首先，遍历时间列表，将其转换为“分钟制”列表 mins，比如，对于时间点 13:14，将其转换为 13 * 60 + 14。

接着将“分钟制”列表按升序排列，然后将此列表的最小时间 mins[0] 加上 24 * 60 追加至列表尾部，用于处理最大值、最小值的差值这种特殊情况。

最后遍历“分钟制”列表，找出相邻两个时间的最小值即可。

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        if (timePoints.size() > 24 * 60)
            return 0;

        int res = 24 * 60;
        vector<int> mins;

        for (auto t: timePoints)
            mins.emplace_back(stoi(t.substr(0, 2)) * 60
                            + stoi(t.substr(3)));
        
        sort(mins.begin(), mins.end());
        mins.emplace_back(mins[0] + 24 * 60);

        for (int i = 1; i < mins.size(); i++)
            res = min(res, mins[i] - mins[i - 1]);
        
        return res;
    }
};

栈

后缀表达式[36]

题目描述

根据逆波兰表示法，求该后缀表达式的计算结果。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：
该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

1 <= tokens.length <= 104
tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + *也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

注意：本题与主站 150 题相同： https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

解法

利用栈存储运算数，每次遇到符号，对栈顶两个元素进行运算。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;

        for (string& t: tokens) {
            if (isNumber(t)) {
                s.push(stoi(t));
            } else {
                int a = s.top();
                s.pop();
                int b = s.top();
                s.pop();

                if (t[0] == '+')
                    s.push(a + b);
                else if (t[0] == '-')
                    s.push(b - a);
                else if (t[0] == '*')
                    s.push(a * b);
                else            
                    s.push(b / a);
            }
        }

        return s.top();
    }

    bool isNumber(string s) {
        if (s.size() > 1 || (s[0] >= '0' && s[0] <='9'))
            return true;

        return false;    
    }
};

小行星碰撞[37]

题目描述

给定一个整数数组 asteroids，表示在同一行的小行星。

对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。

找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例 1：

输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

示例 2：

输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。

示例 3：

输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。

示例 4：

输入：asteroids = [-2,-1,1,2]
输出：[-2,-1,1,2]
解释：-2 和 -1 向左移动，而 1 和 2 向右移动。 由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。

提示：

2 <= asteroids.length <= 10^4
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

注意：本题与主站 735 题相同： https://leetcode-cn.com/problems/asteroid-collision/

解法

可以类比成左右括号匹配：

向右移动的小行星（左括号）：不会引发碰撞，直接入栈
向左移动的小行星（右括号）：可能会和之前向右移动的小行星发生碰撞，特殊处理

因为答案需要碰撞后剩下的所有小行星，相当于栈里最后剩下的元素，所以可以直接用数组表示栈。

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> res;

        for (auto a: asteroids) {
            if (a > 0)
                res.push_back(a);
            else {
                while (!res.empty() && res.back() > 0 && res.back() < -a)
                    res.pop_back();
                
                if (!res.empty() && res.back() == -a)
                    res.pop_back();
                else if (res.empty() || res.back() < -a)
                    res.push_back(a);    
            }
        }

        return res;
    }
};

每日温度[38]

题目描述

请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100

注意：本题与主站 739 题相同： https://leetcode-cn.com/problems/daily-temperatures/

解法

如果当前元素比栈顶大，则让小项逐个出栈，直到当前元素比栈顶小，停止出栈
此时的栈顶元素就是当前项右边的第一个比自己大的元素索引，计算距离
当前项入栈

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> s;
        vector<int> res(temperatures.size(), 0);

        for (int i = temperatures.size() - 1; i >= 0; i--) {
            while (!s.empty() && temperatures[i] >= temperatures[s.top()])
                s.pop();

            if (s.empty())
                res[i] = 0;
            else
                res[i] = s.top() - i;
            s.push(i);
        }

        return res;
    }
};

直方图最大矩形面积[39]

题目描述

给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

1 <= heights.length <=10^5
0 <= heights[i] <= 10^4

注意：本题与主站 84 题相同： https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

解法

我们可以遍历每根柱子，以当前柱子 i 的高度作为矩形的高，那么矩形的宽度边界即为向左找到第一个高度小于当前柱体 i 的柱体，向右找到第一个高度小于当前柱体 i 的柱体。

对于每个柱子我们都如上计算一遍以当前柱子作为高的矩形面积，最终比较出最大的矩形面积即可。

我们遍历每个柱体，若当前的柱体高度大于等于栈顶柱体的高度，就直接将当前柱体入栈，否则若当前的柱体高度小于栈顶柱体的高度，说明当前栈顶柱体找到了右边的第一个小于自身的柱体，那么就可以将栈顶柱体出栈来计算以其为高的矩形的面积了。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> s;
        vector<int> res(temperatures.size(), 0);

        for (int i = temperatures.size() - 1; i >= 0; i--) {
            while (!s.empty() && temperatures[i] >= temperatures[s.top()])
                s.pop();

            if (s.empty())
                res[i] = 0;
            else
                res[i] = s.top() - i;
            s.push(i);
        }

        return res;
    }
};

[未解决]矩阵中最大的矩形[40]

题目描述

给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。

注意：此题 matrix 输入格式为一维 01 字符串数组。

示例 1：

输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = ["0"]
输出：0

示例 4：

输入：matrix = ["1"]
输出：1

示例 5：

输入：matrix = ["00"]
输出：0

提示：

rows == matrix.length
cols == matrix[0].length
0 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'

注意：本题与主站 85 题相同（输入参数格式不同）： https://leetcode-cn.com/problems/maximal-rectangle/

解法

队列

滑动窗口的平均值[41]

题目描述

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。

实现 MovingAverage 类：

MovingAverage(int size) 用窗口大小 size 初始化对象。
double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。

示例：

输入：
inputs = ["MovingAverage", "next", "next", "next", "next"]
inputs = [[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]

解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3

提示：

1 <= size <= 1000
-10^5 <= val <= 10^5
最多调用 next 方法 10^4 次

注意：本题与主站 346 题相同： https://leetcode-cn.com/problems/moving-average-from-data-stream/

解法

“循环数组/队列”实现。

class MovingAverage {
    int sum = 0;
    int capacity = 0;
    queue<int> q;

public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        capacity = size;
    }
    
    double next(int val) {
        q.push(val);
        sum += val;

        if (q.size() > capacity) {
            sum -= q.front();
            q.pop();
        }

        return double(sum)/ q.size();
    }
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage* obj = new MovingAverage(size);
 * double param_1 = obj->next(val);
 */

最近请求次数[42]

题目描述

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证每次对 ping 的调用都使用比之前更大的 t 值。

示例：

输入：
inputs = ["RecentCounter", "ping", "ping", "ping", "ping"]
inputs = [[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]

解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

提示：

1 <= t <= 10^9
保证每次对 ping 调用所使用的 t 值都 严格递增
至多调用 ping 方法 10^4 次

注意：本题与主站 933 题相同： https://leetcode-cn.com/problems/number-of-recent-calls/

解法

在第 1、100、3001、3002 这四个时间点分别进行了 ping 请求，在 3001 秒的时候，它前面的 3000 秒指的是区间 [1,3001]，所以一共是有 1、100、3001 三个请求， t = 3002 的前 3000 秒指的是区间 [2,3002], 所以有 100、3001、3002 三次请求。

可以用队列实现。每次将 t 进入队尾，同时从队头开始依次移除小于 t-3000 的元素。然后返回队列的大小 q.size() 即可。

class RecentCounter {
    queue<long> q;

public:
    RecentCounter() {

    }
    
    int ping(int t) {
        q.push(t);

        while (q.front() + 3000 < t) {
            q.pop();
        }


        return q.size();
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

往完全二叉树添加节点[43]

题目描述

完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第 n 层有 2n-1 个节点）的，并且所有的节点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：

CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v) 向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
CBTInserter.get_root() 将返回树的根节点。

示例 1：

输入：inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
输出：[null,1,[1,2]]

示例 2：

输入：inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
输出：[null,3,4,[1,2,3,4,5,6,7,8]]

提示：

最初给定的树是完全二叉树，且包含 1 到 1000 个节点。
每个测试用例最多调用 CBTInserter.insert 操作 10000 次。
给定节点或插入节点的每个值都在 0 到 5000 之间。

注意：本题与主站 919 题相同： https://leetcode-cn.com/problems/complete-binary-tree-inserter/

解法

完全二叉树只有最后一层是不满的，通过层序遍历就能找到应该插入的节点位置的父节点，然后将新节点插到该父节点下面即可。

/**
 * 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 CBTInserter {
    TreeNode* rt;
    queue<TreeNode*> q;
public:
    CBTInserter(TreeNode* root) {
        rt = root;
        q.push(root);
        while (q.front()->left && q.front()->right) {
            TreeNode* node = q.front();
            q.pop();
            q.push(node->left);
            q.push(node->right);
        }
    }
    
    int insert(int v) {
        TreeNode* parent = q.front();
        TreeNode* node = new TreeNode(v);

        if (parent->left == nullptr) {
            parent->left = node;
        } else {
            parent->right = node;
            
            q.pop();
            q.push(parent->left);
            q.push(parent->right);
        }

        return parent->val;
    }
    
    TreeNode* get_root() {
        return rt;
    }
};

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter* obj = new CBTInserter(root);
 * int param_1 = obj->insert(v);
 * TreeNode* param_2 = obj->get_root();
 */

二叉树每层的最大值[44]

题目描述

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
          1
         / \
        3   2
       / \   \  
      5   3   9

示例2：

输入: root = [1,2,3]
输出: [1,3]
解释:
          1
         / \
        2   3

示例3：

输入: root = [1]
输出: [1]

示例4：

输入: root = [1,null,2]
输出: [1,2]
解释:      
           1 
            \
             2

示例5：

输入: root = []
输出: []

提示：

二叉树的节点个数的范围是 [0,104]
-2^31 <= Node.val <= 2^31 - 1

注意：本题与主站 515 题相同： https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/

解法

“BFS 层次遍历”实现。

因为要求解二叉树每一层的最大值，所以使用二叉树的层次遍历是最适合不过的。但是因为需要求二叉树的每一层的最大值，所以需要确定哪些节点属于同一层。一种简单的方式就是，在遍历完当前层的最后一个节点之后，队列中所保存的节点数就是下一层的节点数。如图所示，红色节点为当前层的最后一个节点，绿色为处于队列中的下一层的所有节点。因为队列的初始状态是只有一个不为空的根节点，所以第一层就是一个节点，第二次就是遍历完根节点之后的队列中的节点，以此类推。

/**
 * 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:
    vector<int> largestValues(TreeNode* root) {
        int cur = 0;
        int next = 0;
        int max = INT_MIN;
        vector<int> res;
        queue<TreeNode*> q;
        
        if (root) {
            q.push(root);
            cur = 1;
        }

        
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            cur--;
            max = std::max(max, node->val);

            if (node->left) {
                q.push(node->left);
                next++;
            }

            if (node->right) {
                q.push(node->right);
                next++;
            }

            if (cur == 0) {
                res.push_back(max);
                max = INT_MIN;

                cur = next;
                next = 0;
            }
        }


        return res;
    }
};

二叉树最底层最左边的值[45]

题目描述

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

二叉树的节点个数的范围是 [1,10^4]
-2^31 <= Node.val <= 2^31 - 1

注意：本题与主站 513 题相同： https://leetcode-cn.com/problems/find-bottom-left-tree-value/

解法

若每次都记录当前层的最左端值，那么等遍历完二叉树，记录的当前层的最左端节点值就是最底层的最左端节点值，如图所示。

/**
 * 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:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);

        int bottomLeft = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();

                if (i == 0)
                    bottomLeft = node->val;

                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
        }

        return bottomLeft;
    }
};

二叉树的右侧视图[46]

题目描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

提示:

二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100

注意：本题与主站 199 题相同：https://leetcode-cn.com/problems/binary-tree-right-side-view/

解法

只需将面试题 45 中保存每一层最左端的节点值，改为保存每一层最右端的节点值并保存即可。

/**
 * 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:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if (!root)
            return res;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();

                if (i == size - 1)
                    res.push_back(node->val);

                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
        }


        return res;
    }
};