秋招已经基本结束，重新整理一下各种笔记资料，这里整理一下leetcode分类刷题的资料。

「github地址」：

更加详细的分类刷题笔记，请跳转github页面查看，这里主要整理部分相关类型的题目，代码解析以及全文的pdf版本，请到小哲AI公众号中回复leetcode自取。

一、 双指针1.1 对撞指针1.2 快慢指针二、 哈希表三、二分查找四、数组和矩阵五、链表六、栈和队列七、 树和递归7.1 递归7.2 BFS与DFS（包括迭代法遍历二叉树）7.3 二叉搜索树7.4 回溯八、贪心九、分治十、动态规划10.1 动态规划10.2 背包问题更多文章请关注一、 双指针

主要有两种： 「对撞指针」和「快慢指针」

1.1 对撞指针

❝

对撞指针的问题,一般是数组首尾各有一个指针,这俩指针往中间移动过,解决相对应的问题

❞

167 有序数组的 Two Sum 2 (easy)125 验证回文串(easy)11 盛最多水容器(medium)1.2 快慢指针

❝

快慢指针是指两个指针从头开始一个快一个慢指针, 一般就是, 最经典的题目就是针对链表的问题(「快慢指针查找链表的中心点」).

❞

141 判断列表是否存在环(easy)283 移动零(easy)26 删除排序数组中的重复项(easy)80 删除排序数组中的重复项 II(medium)二、 哈希表

哈希表是一种很有用的数据结构, 其作用主要是「以空间换时间」, 在c++中主要是unordered_set与unordered_map,在python中主要是set与dict.

1 两数之和 (Easy)217 存在重复元素 (Easy)594 最长和谐子序列 (Easy)128 最长连续序列 (Hard)349 两个数组的交集（easy）350 两个数组的交集 II（easy）242 有效的字母异位词（easy）202 快乐数（easy）205 同构字符串（easy）451 根据字符出现频率排序（medium）15 三数之和（medium）18 四数之和（medium）454 四数相加 II（medium）49 字母异位词分组（medium）447 回旋镖的数量（easy）219 存在重复元素 II（easy）三、二分查找

二分查找是针对一个排序列表,每次利用中间元素折半去掉部分元素,减少重复的查找遍历.

对于一个排序数组nums,查找指定的一个数字target,采用二分查找的解题思路利用target与nums数组的中间元素相比较, 如果target> nums[mid],说明target在数组的后半部分,如果target < nums[mid], 说明target在数组的前半部分如果target == nums[mid], 找到target.

二分查找的典型解题思路模板代码:

int binary_search(vector<int>& nums, int target){ int l = 0, r = nums.size() - 1; while (l <= r){  int mid = l + (r - l) / 2;  // 直接采用(r+l)/2. 容易出现整形溢出  // 找到对应的元素,返回索引  if (nums[mid] == target) return mid;  // target比中间值大,说明存在数组后半部分  else if (nums[mid] < target)   l = mid + 1;  // target小, 说明存在数组的前半部分.  else   r = mid - 1; } return -1;}

「两个非常困扰而且易错的细节点:」

while循环的判断条件是l<r还是l<=r当target != nums[mid]时, 使用mid还是mid (+或者-) 1

解决这两个问题的只需要考虑清楚,「查找区间的封闭情况」, 例如对于上边写的代码,采用的方式为(「左右均为闭区间」)[l, r], 因此决定了循环判断条件为l<=r. 同时 l = mid + 1与r = mid - 1, 在过程中「始终保持全闭区间的情况不变」

当然代码也可以采用左开右闭或者左闭右开的区间进行查找,然后判断需要如何更改这两个问题.

69 x 的平方根 (Easy)744 寻找比目标字母大的最小字母 (Easy)278 第一个错误的版本 (Easy)540 有序数组中的单一元素 (Medium)153 寻找旋转排序数组中的最小值 (Medium)34 在排序数组中查找元素的第一个和最后一个位置(medium)四、数组和矩阵240 Search a 2D Matrix II (Medium)378 Kth Smallest Element in a Sorted Matrix ((Medium))287 Find the Duplicate Number (Medium)697 Degree of an Array (Easy)766 Toeplitz Matrix (Easy)565 Array Nesting (Medium)五、链表

针对链表这种数据结构,采用指针访问元素,而且指针只可向一个方向移动, 几种主要的操作:

快慢指针,找到链表的中点通过pre cur与nex三个指针模拟题目中的流程注意「虚拟头节点」(在头节点前边新建一个虚拟节点指向头节点)的使用160 相交链表 (Easy)206 反转链表 (Easy)21 合并两个有序链表 (Easy)83 删除排序链表中的重复元素 (Easy)234 回文链表 (Easy)19 删除链表的倒数第N个节点 (Medium)24 两两交换链表中的节点 (Medium)445 两数相加 II (Medium)725 分隔链表 (Medium)328 奇偶链表 (Medium)六、栈和队列

❝

「栈: 先进先出 队列: 先进后出」

❞

利用这两类数据结构的特性解题.

其中一类非常经典的题目是: 「单调栈(leetcode496题, 经典题目)」.

「单调递减栈」, 是指针对每一个待遍历的元素x, 将x与栈顶元素相比, 如果大于栈顶元素将栈顶元素出栈, 重新循环对比,直到小于栈顶元素,然后将x入栈.「单调递增栈」: 同理分析232 用栈实现队列 (Easy)225 用队列实现栈 (Easy)155 最小栈 (Easy)20 有效的括号 (Easy)1021 删除最外层的括号 (easy)496 下一个更大元素 I (easy)503 下一个更大元素 II (Medium)739 每日温度 (Medium)232 用栈实现队列 (Easy)题解: 两个栈实现 栈的特点时先进后出, 而队列是先进先出使用两个栈实现先进先出stackin控制入队, stackout控制出队当入队时,直接压入stackin即可出队时, 当stackout为空时,将stackin中的元素依次弹出压入stackout中, 然后执行stackout的出栈也就是出队操作.示例 先入队[1,2], 然后执行一次出队, 再入队[3,4], 然后执行两次出队入队之后stackin为[1,2], stackout为空执行出队时,将stackin中元素依次压入stackout中, 此时stackout为[2,1], 出队1, stackout为[2], stackin为空再次入队, stackin为[3,4], 此时stackout为[2]执行第一次出队时, stackout非空直接出队2, 此时stackin为[3,4], stackout为空当再次执行出队时, stackout为空,与第二步相同.

class MyQueue {public:    stack<int> stackin;    stack<int> stackout;    /** Initialize your data structure here. */    MyQueue() {    }        /** Push element x to the back of queue. */    void push(int x) {        stackin.push(x);    }        /** Removes the element from in front of queue and returns that element. */    int pop() {        // 如果stackout为空,将stackin中的元素依次放入stackout        if(stackout.empty())            while (!stackin.empty() ){                int tmp = stackin.top();                stackin.pop();                stackout.push(tmp);            }        // 返回stackout的栈顶元素        int tmp = stackout.top();        stackout.pop();        return tmp;    }        /** Get the front element. */    int peek() {        // 如果stackout为空,将stackin中的元素依次放入stackout        if(stackout.empty())            while (!stackin.empty() ){                int tmp = stackin.top();                stackin.pop();                stackout.push(tmp);            }        // 返回stackout的栈顶元素        return stackout.top();    }        /** Returns whether the queue is empty. */    bool empty() {        if (stackin.empty() && stackout.empty())            return true;        else            return false;    }};

class MyStack {public:    /** Initialize your data structure here. */    queue<int> q1;    queue<int> q2;    MyStack() {    }        /** Push element x onto stack. */    void push(int x) {        q2.push(x);        while(!q1.empty()){            q2.push(q1.front());            q1.pop();        }        swap(q1, q2);    }        /** Removes the element on top of the stack and returns that element. */    int pop() {        int tmp = q1.front();        q1.pop();        return tmp;    }        /** Get the top element. */    int top() {        return q1.front();    }        /** Returns whether the stack is empty. */    bool empty() {        return q1.empty();    }};

class MinStack {public:    stack<int> s1;    stack<int> s2;  // 辅助栈    /** initialize your data structure here. */    MinStack() {    }        void push(int x) {        s1.push(x);        if (s2.empty())            s2.push(x);        else{            int tmp = s2.top();            if (x <= tmp)                s2.push(x);            else                s2.push(tmp);        }    }        void pop() {        s1.pop();        s2.pop();    }        int top() {        return s1.top();    }        int getMin() {        return s2.top();    }};

层次遍历（BFS）

102 二叉树的层序遍历(medium)637 二叉树的层平均值 (Easy)513 找树左下角的值 (medium)

深度优先遍历（DFS）

144 二叉树的前序遍历 (meidum)145 二叉树的后序遍历 (hard)94 二叉树的中序遍历 (Medium)

宽度优先遍历（BFS）采用「队列」的方式，依次遍历一棵树。

基本的套路代码，就是102题目中的代码思路。

7.3 二叉搜索树

二叉搜索树是指 「左子树的节点值均小于根节点的值， 右子树的节点值大于根节点的值（递归的概念，对于每个节点都成立）」

二叉搜索树的「中序遍历是排序数组」

235 二叉搜索树的最近公共祖先 (Easy)108 将有序数组转换为二叉搜索树 (Easy)653 两数之和 IV - 输入 BST (Easy)530 二叉搜索树的最小绝对差 (Easy)501 二叉搜索树中的众数 (Easy)669 修剪二叉搜索树 (medium)230 二叉搜索树中第K小的元素 (Medium)538 把二叉搜索树转换为累加树 (medium)109 有序链表转换二叉搜索树 (Medium)236 二叉树的最近公共祖先 (Medium)7.4 回溯

「回溯法其实就是暴力法」。经常使用的暴力法就是「多层循环」， 但是面对「树形结构」的话很难采用循环的方式进行遍历。这时就要采用「递归回溯」的方法实现暴力法。

这类题目看似比较难，但是其实时很简单规范的套路性的代码， 下边几道题会有一个「固定的模板套路」， 请耐心体会。

17 电话号码的字母组合(medium)93 复原IP地址（medium）131 分割回文串(medium)46 全排列(medium)47 全排列 II(medium)77 组合(medium)39 组合总和(medium)40 组合总和 II216 组合总和 III78 子集(medium)90 子集II(medium)79 单词搜索(medicum)200 岛屿数量（medium）130 被围绕的区域(medium)417 太平洋大西洋水流问题（medium)51 N皇后（hard）52 N皇后 II（hard）37 解数独（hard）八、贪心

贪心算法是指每步都选择最优的策略，以此达到全局的最优。「局部最优—>全局最优」

贪心策略的选择必须具备「无后效性」，也就是说某个状态以前的过程不会影响以后的状态，只与当前状态有关。

455 分发饼干 (Easy)121 买卖股票的最佳时机 (Easy)122 买卖股票的最佳时机 II (Easy)605 种花问题 (Easy)665 非递减数列 (Easy)53 最大子序和 (Easy)435 无重叠区间 (Medium)452 用最少数量的箭引爆气球 (Medium)406 根据身高重建队列(Medium)763 划分字母区间 (Medium)九、分治

「分而治之」： 就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并

241 为运算表达式设计优先级 (Medium)95 不同的二叉搜索树 II (Medium)十、动态规划10.1 动态规划

动规就是「以空间换取时间。」

动态规划常常适用于有「重叠子问题和最优子结构」性质的问题。

一些思考的套路： 递归 （自顶向下）——> 记忆化递归（自顶向下消除重复） ——> 动态规划（自底而上）

斐波那契数列70 爬楼梯（easy）198 打家劫舍（easy）213 打家劫舍 II（medium）矩阵路径64 最小路径和（medium）62 不同路径（medium）数组区间303 区域和检索 - 数组不可变（easy）413 等差数列划分（medium）分割整数343 整数拆分（medium）279 完全平方数（medium）91 解码方法（medium）最长递增子序列300 最长上升子序列（medium）646 最长数对链（medium）376 摆动序列（medium）最长公共子序列1143 最长公共子序列（medium）股票交易121 买卖股票的最佳时机（easy）122 买卖股票的最佳时机II（easy）123 买卖股票的最佳时机 III（hard）188 买卖股票的最佳时机 IV（hard）309 最佳买卖股票时机含冷冻期（medium）714 买卖股票的最佳时机含手续费（medium）字符串编辑583 两个字符串的删除操作（medium）72 编辑距离（hard）650 只有两个键的键盘（medium）斐波那契数列 这类题目是斐波那契数列是最简单的动态规划的问题，对于这类题目，我会「首先使用递归」直观解决问题， 「然后利用记忆化递归」的方法去重，「最后使用动态规划」实现自底而上的方法。矩阵路径

这类题目是在一个矩阵中找寻满足题意的路径。

依然采用 递归-> 记忆化递归 -> 动态规划的三种方法来求解这个问题。

数组区间分割整数最长递增子序列最长公共子序列股票交易 对于这类股票交易的问题，可以使用一个同意的模板来解决这类问题。状态方程为：

状态转移方程：状态方程中的 i 表示第i天， k表示剩余的操作次数(这里以购买作为操作次数的记录）， 0表示不持有股票，1表示持有股票再第i天不持有股票， 那么其最大利润为上一天不持有股票与上一天持有股票卖掉二者的最大值dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])在第i天持有股票，那么其最大利润为上一天持有股票与上一天不持有股票，然后重新购买二者的最大值dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

base case：#时间从第一天开始dp[0][k][0] = 0dp[0][k][1] = -prices[0]# k为0表示不允许交易dp[i][0][0] = 0dp[i][0][1] = -infinity

当然利用这种方法进行处理并不一定是最优的，有时候会存在大量的冗余， 这里主要引入这种统一的解决思路

10.2 背包问题

「以空间换取时间。」

0-1背包是背包问题的一个主要的表现形式，在「01背包」的基础上发展出来的还有「完全背包」以及「多维背包」问题。

0-1背包

问题描述为： 存在一个容量为 C 的背包，和N类物品。这些物品分别有两个属性，重量w 和价值 v，每个物品的重量为w[i], 价值为v[i]，「每种物品只有一个」。在不超过背包容量的情况下能够装入最大的价值为多少？（这个背包可以不装满）。

如果采用暴力法，每个物品都有装入与不装入两种情况，复杂度为2的n次幂，复杂度为指数级别的复杂度。如果使用动态规划，时间复杂度会降低至O（N*C）。

dp[i][j] 为将前i件物品装进容量为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=Cdp表为(N+1)x(C+1)维的二维数组

1. 不装入第i件物品时，dp[i][j] = dp[i-1][j];2. 装入第i件物品，dp[i][j] = dp[i-1][ j-w[i] ] + v[i];  (j > w[i] 背包的容量大于w[i])状态转移方程： dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])  

第0个物品时不存在的，价值为0。dp[0][:] = 0;

// 定义dpvector<vector<int>> dp(N+1, vector<int>(C+1, 0))// 定义base casefor (int j = 0; j < c+1; j++) dp[0][j] = 0;// 执行状态转移for (int i = 1; i < N+1; i++){ for (int j = C; j >= 0; j--){  dp[i][j] = dp[i-1][j];  if (j >= w[i])   dp[i][j]  = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);  }}return dp[N][C];

初始dp[j]均为0for (int i = 1; i < N+1; i++){ for (int j = C; j >= 0; j--){  if (j >= w[i])   dp[j]  = max(dp[j], dp[j-w[i]] + v[i]);  }}

dp[i][j] 为将前i件物品装进容量为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=Cdp表为(N+1)x（C+1）维的二维数组

完全背包与01背包的思路基本一致，只是每种物品可以有无限多个，因此每次装入第i种物品后，还能继续装入i种物品。

状态转移方程

1. 不装入第i种物品时，dp[i][j] = dp[i-1][j];2. 装入第i件物品，dp[i][j] = dp[i][ j-w[i] ] + v[i];  (j > w[i] 背包的容量大于w[i])状态转移方程： dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i])  

第0个物品时不存在的，价值为0。dp[0][:] = 0;

// 定义dpvector<vector<int>> dp(N+1, vector<int>(C+1, 0))// 定义base casefor (int j = 0; j < c+1; j++) dp[0][j] = 0;// 执行状态转移for (int i = 1; i < N+1; i++){ for (int j = 0; j <=C ; j++){  dp[i][j] = dp[i-1][j];  if (j >= w[i])   dp[i][j]  = max(dp[i][j], dp[i][j-w[i]] + v[i]);  }}return dp[N][C];

初始dp[j]均为0for (int i = 1; i < N+1; i++){ for (int j = 0; j <= C; j++){  if (j >= w[i])   dp[j]  = max(dp[j], dp[j-w[i]] + v[i]);  }}

问题描述为： 存在一个容量为 C 的背包，和N类物品。这些物品分别有三个属性，重量w ，价值 v和数量n，每种物品的重量为w[i], 价值为v[i]，「每种物品分别有n[i]个」。在不超过背包容量的情况下能够装入最大的价值为多少？（这个背包可以不装满）。

与前边的01背包类似，不同之处在于第i件物品的数目为n[i]，这里的分析思路就是针对第i种物品，分别可以装入0，1，2，3, ... ,n[i]件（同时还得满足不能超过背包的容量）。

dp[i][j] 为将前i件物品装进容量为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=Cdp表为(N+1)x（C+1）维的二维数组

1. 不装入第i种物品时，dp[i][j] = dp[i-1][j];2. 对于第i种物品， k为装入第i种物品的件数, k <= min(n[i], j/w[i])dp[i][j] = max{(dp[i-1][j − k*w[i]] + k*v[i]) for i in range(k)} dp[i][j] = max(dp[i][j], dp[i][j-k* w[i]]+ k* v[i])  

第0个物品时不存在的，价值为0。dp[0][:] = 0;

// 定义dpvector<vector<int>> dp(N+1, vector<int>(C+1, 0))// 定义base casefor (int j = 0; j < c+1; j++) dp[0][j] = 0; // 执行状态转移for (int i = 1; i < N+1; i++){ for (int j = C; j >=0 ; j--){  dp[i][j] = dp[i-1][j];  int tmp = min(n[i], j / w[i]);  for (int k = 0; k<=tmp; k++){   dp[i][j]  = max(dp[i][j], dp[i][j-k*w[i]] + k*v[i]);   } }}return dp[N][C];

初始dp[j]均为0for (int i = 1; i < N+1; i++){ for (int j = C; j >= 0; j--){   int tmp = min(n[i], j / w[i]);    for (int k = 0; k<=tmp; k++){   dp[j]  = max(dp[j], dp[j-k*w[i]] + k*v[i]);   } }}

❝

原文首发于「小哲AI」公众号，公众号主要分享人工智能前言算法解读，AI项目代码解析，以及编程、互联网求职等技术资料文章，偶尔也会分享个人读书笔记、工作学习心得，欢迎关注，一起学习。

❞