刷题题解
- BM32 合并二叉树（**）
算法：递归，树的遍历
思路：
- 根左右顺序访问节点，将不同树的两个节点求和，放到一个新建的节点中，再一起访问左孩子和右孩子节点，
- 如果访问到的某一个树的节点为空，返回另一个节点，都为空的话自动返回空节点
- BM56 有重复项数字的全排列（****）（去重操作需要注意）
算法：回溯
思路：
- 给定的数组排序（保证字典序），使用一个visit数组来做记录访问过的数据
- 对每个数组的值，进行回溯尝试，当index的值到数组最后一个元素时，返回加入到res结果数组中；
- 因为涉及到了去重操作， 主要有两种去重，一种是在遍历数组的时候，防止对同一数组的多次访问；另一种是对邻近的值去重操作（当前的节点和前一个节点值相同，前一个的值已被访问，要注意，当前节点的下标是大于1，而且在if语句中要放在逻辑判断的最前面）
- BM3 链表中的节点每k个一组翻转（难度****）（比较复杂）
算法：递归， 反转链表思路：
- 分组递归，首先遍历k个节点，得到该组的tail节点（最后不足k个，返回head节点；tail节点是下一组的头节点）;
- pre指向空， cur是当前节点， temp是下一个节点， cur->next = pre, pre移到cur, cur移到temp, 简单说就是这两个节点都向后移一位；
- cur指向tail节点的时候，返回pre节点，这时pre节点是当前组的倒序的第一个节点；
- 对于每一次递归， 返回值为head->next = 反转该组链表；
- 二叉树的层次遍历（难度**）（主要是思想，代码难度不大）
leetcode 102. 二叉树的层序遍历
算法：队列
步骤：
- 根节点放入队列，
- 队列不为空，进行以下操作： 重要的是，for循环遍历当前层的所有节点，然后插入左孩子节点和右孩子节点
while(!q.empty()){
int n = q.size();
vector<int> v;
for(int i = 0 ;i < n; i++){
TreeNode* temp = q.front();
q.pop();
v.push_back(temp->val);
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}
res.push_back(v);
}
- 两数之和（难度*）（回顾为主）
leetcode
步骤： for循环遍历每个数，循环每次查询target-nums[i]，若没有在map中找到，num[i]加入到map中.
思路： 两数之和，把可能的值放进去，然后在map中查询，注意先放入的是有可能是结果之一，然后靠target-nums[i],之后的另一个值去查询map中的值。
- 三数之和（难度***）（去重操作需要关注）
leetcode 923. 三数之和的多种可能
算法： 双指针， 去重
步骤：
- for循环遍历，先确定一个值，再使用双指针找剩下的两个值
- while（left<right），前后指针夹击， 如果双指针指向的值<target-arr[i],left++;相反right--;
- 去重操作：当if(arr[left] + arr[right] == target-arr[i])时，需要分两种情况，由于本题是返回所有情况，所以重复值也需要计算。对于重复值。分两种情况讨论： 1）arr[left] != arr[right]，表示双指针指向的值不同，计算两个指针指向的值的数量分别是多少，假设分别为j和k，那么res+=j * k,记得去完重后right--;left++; 2） arr[left] == arr[right]，表示双指针指向的值相同，假设剩下[4,4,4],表示3个中选择两个，（排列组合），公式法 (n2){n\choose 2}(2n), n为3， 这里可以计算得到为right-left+1
(nk)=n(n−1)⋯(n−k+1)k!=n!k!(n−k)!{n \choose k} = \frac{n(n-1)\cdots(n-k+1)}{k!} = \frac{n!}{k!(n-k)!}(kn)=k!n(n−1)⋯(n−k+1)=k!(n−k)!n!
时间复杂度：双指针可以使两数之和在线性时间内完成，三数之和在O(n^2)内完成
- 四数之和（难度****）（去重重点关注）
leetcode 18. 四数之和
步骤：
- 先确定i，j两个指针，遍历i，j，之后left和right双指针指向j+1和n-1位置；
- 去重操作（本题返回的数组是不重复的值）：
1）对i的去重，i-1和i相同，i++；若最小的4个数字（包括i）仍然大于target，说明之后都大于目标值，直接返回；若i和最大的三个数字小于目标值，说明本次for循环中的i的剩下三个数字都小于目标值，直接进入下一个i+1，注意这里的i+1的值是大于i的
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
if((long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target){
break;
}
if((long)nums[n-1]+nums[n-2]+nums[n-3]+nums[i]<target){
continue;
}
2）对j的去重，第一个和i相同；第二个要注意是j+1和j+2，不是i；第三个也和i一样
if (j > i+1 && nums[j] == nums[j - 1]) {
continue;
}
if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2]>target){
break;
}
if((long)nums[n-1]+nums[n-2]+nums[j]+nums[i]<target){
continue;
}
3）left和right去重，分两种情况，第一种nums[left] != nums[right]，left和right分别夹击，直到对应的重复值的最后一个；第二种nums[left] == nums[right]，说明剩下的元素left-right中的值都是一样的，直接返回结果
if(nums[left] != nums[right]){
while(left+1<right&&nums[left] == nums[left+1]) left++;
while(left<right-1&&nums[right] == nums[right-1]) right--;
}else{
break;
}
left++;
right--;
- BM92 最长无重复子数组（难度***）（滑动窗口思路和哈希表保存频次）
算法：滑动窗口，哈希表， 双指针
步骤：
- 哈希表存储数组的每个值的出现次数
- 双指针实现滑动窗口， left和right从0开始， 遍历right指针， 每次操作map[arr[right]]++; ,出现次数+1
- 遍历right时， 当map[arr[right]]>1, 也就是说right指向的值已经存在哈希表中， 说明是重复值， left指针后移一位，同时map[arr[left++]]--;， 这样做是为了保证哈希表中的数据是left-right之间的频次
- res = max(res, right - left +1);
- BM15 删除有序链表中重复的元素-I（难度*）（节点的声明和对象内存分配）
步骤没有什么，主要是节点中的ListNode* res(0);和ListNode* res = new ListNode(0);有什么不同，
- 前者只是声明，将一个指针初始化为
nullptr它没有分配任何内存空间。这个语句只是将 res 指向一个空地址，也就是说，它并没有创建任何对象，只是声明了一个指针变量。 - 因此，在这个代码中，我们需要使用 new 运算符来分配一个新的 ListNode 对象，以便作为头结点。如果不使用 new 运算符，那么 res 将永远指向空地址，无法作为一个有效的头结点。
- 也就是说，之后的
res->next = head;不分配地址是无法使用的。
- BM16 删除有序链表中重复的元素-II(难度**)（指针要提前两位）
和上题不同的是只保留出现一次的元素，删掉所有重复的（上题保留一个）重点是指针要提前两个位置，起点从res开始，例如49，48，48，是需要把48全部删掉的
- BM13 判断一个链表是否为回文结构(难度**** )(用到了快慢指针和链表反转)
算法：快慢指针， 反转链表
步骤：
- 首先快慢指针移动，当快指针指向链表尾元素或者已经超过尾元素且指向nullptr时，慢指针这时在链表中间位置,例子12321，这时慢指针在3，
- slow慢指针后的所有元素反转链表
- 前后两部分判断值相等，slow指针和head指针开始
- BM18 二维数组中的查找（难度***)(思想重要，两种方式)
算法： 二分查找，分治， 递归（判断应该在哪个区间）
步骤：
- 第一种方法：因为是有序数组，左上最小，右下最大，这没有规律，但是左下和右上就不一样了，左下元素的上面元素都要小于他，右边的元素都要大于他，利用这一点，从左下角元素开始，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。 时间复杂度为O(M+N)数组的行列长度
- 第二种方法（二分查找）：重要这里我们需要重点强调的是区间划分的范围，注意是从
0 - n-1的，同时，递归结束条件也很重要if (x1 > x2 || y1 > y2) return false;
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
if (m == 0) return false;
int n = matrix[0].size();
if (n == 0) return false;
return searchMatrix(matrix, target, 0, 0, m - 1, n - 1);
}
bool main(vector<vector<int>>& matrix, int target, int x1, int y1, int x2, int y2) {
if (x1 > x2 || y1 > y2) return false;
int xm = (x1 + x2) / 2;
int ym = (y1 + y2) / 2;
int mid = matrix[xm][ym];
if (mid == target) return true;
else if (mid > target) {
return searchMatrix(matrix, target, x1, y1, xm - 1, y2) || searchMatrix(matrix, target, xm, y1, x2, ym - 1);
} else {
return searchMatrix(matrix, target, xm + 1, y1, x2, y2) || searchMatrix(matrix, target, x1, ym + 1, xm, y2);
}
}
时间复杂度O(log^2(n))
如果当前值大于目标值，区间划分为（x1, xm-1, y1, y2）,左半部分；区间划分为（xm, x2, y1, ym-1）,右上部分；
如果当前值小于目标值，区间划分为（xm+1, x2, y1, y2）,右半部分；区间划分为（xm, x2, ym+1, y2）,左下部分；
- BM31 对称的二叉树(难度**)（双指针递归思想很重要，不要看题目简单，思路却很重要，要多看）
算法： 递归
步骤：
主要方法：
- 根节点变两个指针，递归查询
- 递归结束条件，两个指针都为空，说明是对称的；若一个指针为空，另一个不为空，或者值不相等，那么就无法构成对称树；
- 指针递归
return recursion(left->left, right->right) && recursion(left->right, right->left);
方法二：层次遍历，每一层节点放入队列
- BM80 买卖股票的最好时机(一)(难度***)（思想很重要，要重点关注）
算法：动态规划，贪心
步骤：
- 方法一：贪心 贪心思路比较简单，第i天之前的最小价值的股票，假设当天卖出，判断最终价值是不是最大就好了；
- 方法二：dp表示第i天的最大收益 dp的思路是第i天的状态有两种，股票只能买一次：
- 一种是没有持有股票，可能是i-1天之前卖了或者就没买，这种就和dp[i][0] = dp[i-1][0]一样就好了，也可能是第i天，也就是当天卖出了，dp[i-1][1] + prices[i], 比较这两种情况的最大值就好了
- 另一种是当天持有股票，可能i-1天之前就持有了，dp[i][1] = dp[i-1][1]，也可能是当天刚买的， -prices[1], 比较最大收益就好了
- 最后返回dp[n-1][0]
- BM82 买卖股票的最好时机(三)（难度**** ）（思想非常主要，每天有5种状态）
与上题不同的是：可以买入卖出两次，但是必须卖了才能买，动态规划的状态有5种，
- dp[i][0]表示到第i天为止没有买过股票的最大收益
- dp[i][1]表示到第i天为止买过一次股票还没有卖出的最大收益
- dp[i][2]表示到第i天为止买过一次也卖出过一次股票的最大收益
- dp[i][3]表示到第i天为止买过两次只卖出过一次股票的最大收益
- dp[i][4]表示到第i天为止买过两次同时也买出过两次股票的最大收益
动态规划主要的是状态转移方程
- NC28 最小覆盖子串（难度*****）（非常经典的题，需要琢磨）
题目：给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。
算法：哈希表，滑动窗口，双指针
步骤：
- 哈希表
unordered_map<char, int> m;, 遍历t赋值； count为m的长度, 设最小长度为minLen;- while循环双指针遍历， 首先right指针后移，m[s[right]]--, 直到m[S[right]] == 0时count--；表示某个字符已经全部找到， right指针会一直向后移，表示t的最后一个能在s中找到的值，即右边界；
- 在right循环内部， 当count==0时，表示表示所有字符已经全部找到，计算左边界，左边界也是从0开始， 注意，
while（count==0）， 也就是说当count>0时才跳出，关键是什么时候大于0； - 如果s中left指向的值能够在哈希表m中找到，
m[S[left]]++;， 当m[S[left]] > 0，count++; - 这里需要注意的是， 举个例子S="XXZ", T="XZ", 会不会出现不是最小的窗口那？ 这里需要关注的就是
if (m[S[left]] > 0) count++;这一行代码， 注意， 只有当>0时， 该字符的count才会＋1， 解释一下， right向后指时， 遇到第二个'X'时， m[S[right]]已经是-1了， （1 -> 0 -> -1， 两次），所以当指向第二个'X'时， m[S[left]]才会变成1
#include <unordered_map>
class Solution {
public:
/**
*
* @param S string字符串
* @param T string字符串
* @return string字符串
*/
string minWindow(string S, string T) {
int n = S.size();
string res;
unordered_map<char, int> m;
for (char c : T) m[c]++;
int left = 0, right = 0;
int count = m.size();
int minLen = INT_MAX;
while (right < n) {
if (m.find(S[right]) != m.end()) {
m[S[right]]--;
if (m[S[right]] == 0) count--;
}
right++;
while (count == 0) {
if (right - left < minLen) {
minLen = right - left;
res = S.substr(left, minLen);
}
if (m.find(S[left]) != m.end()) {
m[S[left]]++;
if (m[S[left]] > 0) count++;
}
left++;
}
}
return res;
}
};
华为工作强度 840人发布