本文档是对LeetCode详细解释和扩展101中的问题。 

 打开 LeetCode 网站，如果我们按照题目类型数量分类，最多的几个题型有数组、动态规划、 数学、字符串、树、哈希表、深度优先搜索、二分查找、贪心算法、广度优先搜索、双指针等等。 本书将包括上述题型以及网站上绝大多数流行的题型，并且按照难易程度和类型进行分类。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-W76O4oIC-1657023302337)(pictureforMD/image-20220521093822599.png)]

 第一个大分类是算法。本书先从最简单的贪心算法讲起，然后逐渐进阶到二分查找、排序算法和搜索算法，最后是难度比较高的动态规划和分治算法。

 第二个大分类是数学，包括偏向纯数学的数学问题，和偏向计算机知识的位运算问题。这类问题通常用来测试你是否聪敏，在实际工作中并不常用，笔者建议可以优先把精力放在其它大类上。

 第三个大分类是数据结构，包括 C++ STL内包含的常见数据结构、字符串处理、链表、树和 图。其中，链表、树、和图都是用指针表示的数据结构，且前者是后者的子集。最后我们也将介绍一些更加复杂的数据结构，比如经典的并查集和 LRU。

 顾名思义，贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。 举一个最简单的例子：小明和小王喜欢吃苹果，小明可以吃五个，小王可以吃三个。已知苹果园里有吃不完的苹果，求小明和小王一共最多吃多少个苹果。在这个例子中，我们可以选用的贪心策略为，每个人吃自己能吃的最多数量的苹果，这在每个人身上都是局部最优的。又因为全局结果是局部结果的简单求和，且局部结果互不相干，因此局部最优的策略也同样是全局最优的策略。

题目描述：

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。 所以你应该输出1。

示例 2:

输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2.

提示：

1 <= g.length <= 3 * 10⁴ 0 <= s.length <= 3 * 10⁴ 1 <= g[i], s[j] <= 2³¹ - 1

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/assign-cookies

思路

 本题有两种思路：

  1.饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使剩下的饼干可以满足更多的孩子，我们应该选取满足这个孩子且大小最小的饼干给这个孩子。满足这个孩子之后，我们再采用同样的策略去考虑剩下孩子里饥饿度最小的孩子，直到没有满足条件的饼干存在。

  2.饥饿度高的孩子吃大尺寸的饼干不容易造成浪费，小尺寸的饼干可以满足饥饿度小的孩子，所以我们先考虑饥饿度较高的孩子。为了尽量使剩下的饼干可以满足更多的孩子，我们应该选取满足这个孩子且大小最小的饼干。满足这个孩子之后，我们再采取同样的策略去考虑剩下的孩子里饥饿度较高的孩子，直到没有满足条件的饼干存在。

 具体实现要将饥饿度和饼干大小从小到大排序，这样就可以从饥饿度最小的孩子和大小最小的饼干（或饥饿度最大的孩子和大小最大的饼干）出发，计算有多少个可以满足条件的饼干孩子对。

题解

//先满足饥饿度小的孩子
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
		sort(g.begin(), g.end());
		sort(s.begin(), s.end());
		int child = 0, cookie = 0;
		while (child < g.size() && cookie < s.size()) {
			if (g[child] <= s[cookie])	++child;
			++cookie;
		} 
		return child;//此时child指向最后可以满足的孩子的下一个孩子，下标等于已满足孩子的数量 
    }
};

//先满足饥饿度大的孩子
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
		sort(g.begin(), g.end());
		sort(s.begin(), s.end());
		int index = s.size() - 1;
		int result = 0;
		for (int i = g.size() - 1; i >= 0; i--) {
			if (index >= 0 && g[i] <= s[index])	{//index>=0 一定要放在前面，当不符合此条件时不进行后续判断 
				--index;
				++result;
			} 
		}
		return result;
    }
};

​ 小结：对数组或字符串排序是常见的操作，方便之后的大小比较。在之后的讲解中，若我们谈论的是对连续空间的变量进行操作，我们并不会明确区分数组和字符串，因为他们本质上都是在连续空间上的有序变量集合。一个字符串“abc”可以被看作一个数组 [‘a’,‘b’,‘c’]。

题目描述：

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目 。

示例 1：

输入：ratings = [1,0,2] 输出：5 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2] 输出：4 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

n == ratings.length 1 <= n <= 2 * 10⁴ 0 <= ratings[i] <= 2 * 10⁴

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/candy

思路

​ 做完了题目 455，你会不会认为存在比较关系的贪心策略一定需要排序或是选择？虽然这一 道题也是运用贪心策略，但我们只需要简单的两次遍历即可：把所有孩子的糖果数初始化为 1； 先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的 糖果数加 1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1，若左边孩子当前的糖果大于右边孩子的糖果数，则不用改变。通过这两次遍历， 分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系。

题解

class Solution {
public:
    int candy(vector<int>& ratings) {
		vector<int> candy(ratings.size(), 1);
		for (int i = 1; i < ratings.size(); i++) {
			if (ratings[i] > ratings[i - 1])	candy[i] = candy[i - 1] + 1;
		}
		for (int j = ratings.size() - 1; j > 0; j--) {
			if (ratings[j - 1] > ratings[j])	candy[j - 1] = max(candy[j - 1], candy[j] + 1); 
		}
		return accumulate(candy.begin(), candy.end(), 0);
    }
};

​ 关于std::accumulate的用法：https://cloud.tencent.com/developer/section/1009763

题目描述

给定一个区间的集合 intervals ，其中 intervals[i] = [start_i, end_i] 。返回需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

1 <= intervals.length <= 105 intervals[i].length == 2 -5 * 10⁴ <= start_i < end_i <= 5 * 10⁴

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/non-overlapping-intervals

思路

​ 人类在处理这种问题时潜意识往往运用贪心算法。示例1中，我们会选取前三个区间，删除最后一个区间。为什么呢？因为我们潜意识里默认要选取结尾最小的区间，这样才能留下位置给其他区间。总结来说，本题的贪心策略即是：优先选取结尾数值小且不相交的区间。

​ 具体实现方法是：既然我们要优先选取结尾数值小的，我们就要先对区间按结尾大小进行增序排序，每次选取结尾最小且和前一个选择的区间不重复的区间。我们使用C++的Lambda表达式，结合std::sort()函数进行自定义排序。

题解

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
		if (intervals.size() == 0)	return 0;
		sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
			return a[1] < b[1];
		});
		int result = 0, pre = intervals[0][1];//第一个区间的结尾值 
		for (int i = 1; i < intervals.size(); i++) {
			if (intervals[i][0] < pre) result++;//重叠,需要删除此区间 
			else pre = intervals[i][1]; //不重叠，不需要删除，将pre后移 
		}
		return result; 
    }
};

​ 本题Lambda表达式的参数需要加个引用，否则会超时。关于Lambda表达式如果有些遗忘可以参考：

​ https://en.cppreference.com/w/cpp/language/lambda

题目描述

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

示例 1：

输入：flowerbed = [1,0,0,0,1], n = 1 输出：true

示例 2：

输入：flowerbed = [1,0,0,0,1], n = 2 输出：false

提示：

1 <= flowerbed.length <= 2 * 10⁴ flowerbed[i] 为 0 或 1 flowerbed 中不存在相邻的两朵花 0 <= n <= flowerbed.length

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/can-place-flowers

思路

​ 贪心算法，如果某个位置前后都没有种花，则可以种。全局来看，会种最多的花。但是此题要判断边界条件：首位置如果后面没种花，则可以种，尾位置如果前面没种花，则可以种。为避免分类讨论，我们可以在首尾添加一个0，以表示上述这两种情形。

题解

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
    	int count = 0;
    	flowerbed.insert(flowerbed.begin(), 0);
		flowerbed.push_back(0); 
    	int size = flowerbed.size();
        for (int i = 1; i < flowerbed.size() - 1; i++) {
			if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0 && flowerbed[i] == 0) {
                count++;
                flowerbed[i] = 1;
            }
		}
		if (count - n >= 0)	return true;
		return false;
    }
};

​ 在首尾添加0的做法，体现了防御式编程思想，对数组长度只有1的样例也可以通过。

题目描述

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [x_start, x_end] 表示水平直径在 x_start 和 x_end之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x_start，x_end， 且满足 x_start ≤ x ≤ x_end，则该气球会被引爆 。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2 解释：气球可以用2支箭来爆破:

在x = 6处射出箭，击破气球[2,8]和[1,6]。 在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4 解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2 解释：气球可以用2支箭来爆破:

在x = 2处发射箭，击破气球[1,2]和[2,3]。

在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示:

1 <= points.length <= 105 points[i].length == 2 -231 <= x_start < x_end <= 231 - 1

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons

思路

​ 从直觉来看，只要让弓箭从气球重叠最多的位置射出，就可以引爆最多数量的气球。每次发射弓箭都引爆最多数量的弓箭，那么最终就用了最少数量的弓箭来引爆所有气球。具体来说，为了让气球尽可能重叠，我们应该对气球的左区间进行从小到大增序排序（Lambda），然后遍历一遍气球，当左区间大于上一个重叠气球区间最小右边界，那么就需要多一只箭来引爆此气球；否则还可以用上一只箭来引爆这组气球，并更新重叠气球区间最小右边界。

题解

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
		sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b){
			return a[0] < b[0];
		});
		int count = 1;
		int last = points[0][1];
		for (int i = 1; i < points.size(); i++) {
			if (points[i][0] <= last)	last = min(last, points[i][1]);
			else {
				count++;
				last = points[i][1];
			}	
		}
		return count;
    }
};

题目描述

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

输入：S = “ababcbacadefegdehijhklij” 输出：[9,7,8] 解释： 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

提示：

S的长度在[1, 500]之间。 S只包含小写字母 ‘a’ 到 ‘z’ 。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/partition-labels

思路

​ 人类在思考这道题时会扫描整个字符串，然后凭直觉进行划分，怎么划分的呢？仔细想想，既然要让同一个字符只能出现在一个区间内，那么这个字符的第一次出现的位置和最后一次出现的位置一定都是在这个区间内的。而这个区间是需要一直维护的，我们维护区间的左边界start和右边界end，end要根据当前遍历的字符最后一次出现的位置下标进行更新。当我们遍历到end时，就说明我们之前遍历的所有字符其最后一次出现位置都在end之前（如果不是则end还会更新）。此时我们要记录这个区间的长度为end-start+1，然后进入下一个区间start=end-1，end=start，重复这个过程，直到遍历到最后一个字符。具体来讲，我们要先遍历一遍字符串，将每个字符的最后出现位置下标存入哈希表，然后再次按上述步骤遍历字符串。

题解

class Solution {
public:
    vector<int> partitionLabels(string s) {
		int last[26] = {0};
		for (int i = 0; i < s.size(); i++) {
			last[s[i] - 'a'] = i;//不断更新字符的最后出现位置 
		}
		int start = 0, end = 0;
		vector<int> partition;//用来存储各个划分区间的长度 
		for (int i = 0; i < s.size(); i++) {
			end = max(end, last[s[i] - 'a']); //一定放在前面，先更新end再判断是不是遍历到了end 
			if (i == end) {
				partition.push_back(end - start + 1);
				start = end + 1;
				end = start; 
			}
		}
		return partition;
    }
}

​ 为了满足你的贪心策略，是否需要一些预处理？注意在处理数组前，统计一遍信息（如频率、个数、第一次出现位置、最后一次出现位置等）可以使题目难度大幅降低。

题目描述

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

输入：prices = [7,1,5,3,6,4] 输出：7 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

提示：

1 <= prices.length <= 3 * 10⁴ 0 <= prices[i] <= 10⁴

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii

思路

​ 首先要清楚两点：1.只有一只股票；2.当前只有买卖股票这两种操作；3.要想获得利润至少以两天为一个交易单元。 ​ 有的同学可以想到，不就是选一个价格低的日期买入，再选一个价格高的日期卖出，如此循环。如果想到最终利润是可以分解的，那么这题就好解决了。假如我们第一天买入，第三天卖出，那么利润可以表示为price[3]-price[0],相当于(price[3]-price[2]+price[2]-price[1]+price[1]-price[0]，此时我们就把利润分解为了以天为单位的数组。将所有正数相加就是最大利润。只收集正利润就是贪心算法贪的地方。局部最优：收集每天的正利润；全局最优：求得最大利润。另外，有的同学可能会陷入“第一天怎么没有利润，第一天到底算不算利润？”的困惑中。第一天当然没有利润，至少到第二天才有利润，所以利润序列比股票序列少一天。

题解

class Solution {
public:
    int maxProfit(vector<int>& prices) {
		int result = 0;
		for (int i = 1; i < prices.size(); i++) {
			if ((prices[i] - prices[i - 1]) > 0)	result += prices[i] - prices[i - 1];
		}
		return result;
    }
};

题目描述

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [h_i, k_i] 表示第 i 个人的身高为 hi ，前面 正好 有 k_i个身高大于或等于 h_i 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [h_j, k_j] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 解释： 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。 示例 2：

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

提示：

1 <= people.length <= 2000 0 <= h_i <= 106 0 <= k_i < people.length 题目数据确保队列可以被重建

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/queue-reconstruction-by-height

思路

​ 本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后在按照另一个维度重新排列。其实如果大家认真做了135. 分发糖果，就会发现和此题有点点的像。在135. 分发糖果我就强调过一次，遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。如果两个维度一起考虑一定会顾此失彼。

​ 是先确定k还是先确定h呢，也就是究竟先按h排序呢，还先按照k排序呢？如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），这个顺序就是我们依次插入结果集的顺序。如果不这样的话，后续插入身高相同的但k较小的，会使之前插入的相同身高的人的k不符合要求，从输出结果我们也可以看出，如果两个人身高相同，则一定是k值小的在前面。

​ 此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！那么只需要按照k为下标重新插入队列就可以了，为什么呢？因为我们已经根据身高从高到低排序了，优先按身高高的people的k来插入，后续插入节点也不会影响前面已经插入的节点（就算后续节点（低身高的插入到了高身高的前面，也不会影响，因为k是代表其前面身高大于等于他的人数），最终按照k的规则完成了队列。

题解

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort (people.begin(), people.end(), [](vector<int>& a, vector<int>& b){
        	return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
		});
        vector<vector<int>> result;
        for (int i = 0; i < people.size(); i++) result.insert(result.begin() + people[i][1], people[i]);
        return result;
    }
};

​ 另外我们知道，在vector中插入元素是很耗时的，所以我们可以尝试用list来存储结果，最后再转化成vector。

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort (people.begin(), people.end(), [](vector<int>& a, vector<int>& b){
        	return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
		});
        list<vector<int>> result;
        for (int i = 0; i < people.size(); i++) {
        	std::list<vector<int>>::iterator it = result.begin();
            int position = people[i][1];
        	while (position--)	it++;//寻找插入位置
			result.insert(it, people[i]); 
		}
        return vector<vector<int>>(result.begin(), result.end());
    }
};

题目描述

给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

示例 1:

输入: nums = [4,2,3] 输出: true 解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。

示例 2:

输入: nums = [4,2,1] 输出: false 解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

提示：

n == nums.length 1 <= n <= 10⁴ -10⁵ <= nums[i] <= 10⁵

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/non-decreasing-array 思路

​ 本题难就在于需要考虑两个贪心情况，当nums[i] > nums[i+1]时，此时需要更改元素值，要么将nums[i]缩小，要么将nums[i+1]放大。

• 如果将nums[i]缩得太小，则有可能导致之前判断无误的nums[0,i]之内重新出现递减情况（j=[0,i],nums[i]<nums[j])，所以此时应该使用贪心策略：缩小nums[i]时，尽可能使nums[i]大，于是num[i]缩小到nums[i+1]。
• 如果将nums[i+1]放的太大，则有可能导致数列之后出现递减情况，所以此时应该使用贪心策略：放大nums[i+1]时，尽可能使nums[i+1]小，于是nums[i+1]放大到nums[i]。

​ 具体来讲，我们遍历数组，如果遇到nums[i]>nums[i+1]时（递减情况），如果还能修改则判断应该按上述哪种方案修改：

• 当nums[i+1] >= nums[i-1]时，例如[2,3,2,2]，此时应该缩小nums[i]至nums[i+1]，如果放大nums[i+1]，则可能导致后面的数组出现递减情况。

• 当nums[i+1] < nums[i-1]时，例如[3,3,2]，此时应该放大nums[i+1]至nums[i]，如果缩小nums[i]，则可能导致前面的数组出现递减情况。

  如果不能再修改就直接返回false。

题解

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
    	if (nums.size() == 1)	return true;
    	int count = nums[0] <= nums[1] ? 1 : 0;//前两个元素是否需要修改，count为剩余修改次数
		for (int i = 1; i < nums.size() - 1; i++) {
			if (nums[i] > nums[i + 1]) {
				if (count) {//还有剩余修改机会 
					//判断应该修改nums[i]还是nums[i+1] 
					if (nums[i + 1] >= nums[i - 1]) nums[i] = nums[i + 1];
					else nums[i + 1] = nums[i];
				 	count--;
				}
				else return false;//还要修改但无修改机会，返回false 
			}
		} 
	    return true;//想要修改的次数小于等于1，返回true 
    }
};

​ 双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多 个数组的多个指针。

​ 若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口（两个指针包围的 区域即为当前的窗口），经常用于区间搜索。

​ 若两个指针指向同一数组，但是遍历方向相反，则可以用来搜索，待搜索的数组往往是排好序的。

​ 对于 C++ 语言，指针还可以玩出很多新的花样。一些常见的关于指针的操作如下。

指针与常量

int x;
int* p1 = &x;//指针可以被修改，值也可以被修改
const int* p2 = &x;//指针可以被修改，但值不可以被修改（const int）
int* const p2 = &x;//指针不可以被修改，但值可以被修改（* const）
const int* const p2 = &x;//指针不可以被修改，值也不可以被修改
//区别方法：左定值，右定向（const在*左边，底层const，指针所指的对象是常量；const在*右边，顶层const，指针本身是常量）

指针函数与函数指针

//addition是指针函数，（返回类型是指针的函数）
int* addition(int a, int b) {
    int* sum = new int(a + b);
    return sum;
}
int* m = addition(1,2);

int subtraction(int a, int b) {
    return a - b;
}

//minus是函数指针，（指向函数的指针）
int (*minus)(int, int) = subtraction;

int opeartion(int x, int y, int (*func)(int, int)) {//第三个形参类型为函数指针
	return (*func)(x, y);	
}
int n = operation(3, *m, minus);//第一个实参类型为int，第一个实参类型为int型指针的值即int，第三个实参类型为函数指针

题目描述

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。 示例 2：

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

输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted

思路

​ 本题其实很简单，因为数组都是按非递减排好序的，只需用两个遍历方向相反的指针，一个从左往右，一个从右往左遍历。当双指针指向的元素之和大于target时，说明应该减小总和，于是右边的指针要向左前进一位；当双指针指向的元素之和小于target时，说明应该增大总和，于是左边的指针要向右前进一位；当双指针指向的元素之和等于target时，说明这两个元素就是我们想要的值，返回双指针下标即可。

题解

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
		int left = 0, right = numbers.size() - 1;
		while (left < right) {
			int sum = numbers[left] + numbers[right];
			if (sum == target)	break;
			else if (sum < target)	left++;
			else	right--;
		} 
		return vector<int>{left + 1, right + 1};
    }
};

题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] 解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -10⁹ <= nums1[i], nums2[j] <= 10⁹

进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/merge-sorted-array

思路

​ 这道题题意是让把所有元素按非递减顺序放入nums1数组，那么应该先从小往大放，还是从大往小放呢？应该从大往小放。因为这样避免了nums1数组中元素的移动，如果从小往大放，先往nums1数组的左侧加入小元素则会导致nums1数组的其他元素往后移动。正因为nums1数组后面已经预留了位置，所以我们应该从右往前比较两个数组最大的元素，选取一个最大的放入nums1数组的结尾（n+m-1）。

​ 具体来讲：我们设置两个指针初始值为m-1和n-1，分别指向nums1和nums2的末尾，即nums1的m-1位和nums2的n-1位。另外设置一个指针pos，指向要加入nums1数组的位置，初始为m+n-1。每次将两指针指向的元素最大值复制到pos指向的nums1数组的位置，同时将有最大值的那个数组指针向左移动一位，pos指针也要向左移动一位。最后应该注意，当nums1元素被复制完，不要忘了将nums2的元素继续复制；如果nums2的元素已经复制完，剩余nums1元素则不需要改变，因为初始就是有序的。

题解

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
		int pos = m-- + n-- - 1;//pos初始值为m+n-1
		//指向两数组的指针初始值为m-1和n-1
		while (m >= 0 && n >= 0) {//两数组都没复制完
			nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--]; 
		} 
		while (n >= 0) {//nums1数组复制完
			nums1[pos--] = nums2[n--]; 
		}
		//nums2数组复制完则不用再操作了，因为nums1数组本来就有序 
    }
};

题目描述

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

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

不允许修改 链表。

示例 1：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AYnBzvFj-1657023302339)(pictureforMD/circularlinkedlist.png)]

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CG3sXq3v-1657023302340)(pictureforMD/circularlinkedlist_test2.png)]

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wO0HctMY-1657023302340)(pictureforMD/circularlinkedlist_test3.png)]

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

提示：

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

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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/linked-list-cycle-ii 思路

​ 对于链表找环路的问题，有一个通用的解法——快慢指针（Floyd 判圈法）。给定两个指针， 分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步。如果 fast 可以走到尽头，那么说明没有环路；如果 fast 可以无限走下去，那么说明一定有环路，且一定存 在一个时刻 slow 和 fast 相遇。当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并 让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。具体证明，参考代码随想录相应题目:

 408考研真题曾经涉及到链表是否有环。可以使用快慢指针法，分别定义fast和slow指针，从头节点出发，快指针每次移动两个结点，慢指针每次移动一个节点。如果快慢指针在途中相遇，则说明这个链表有环。这很容易理解，我们知道快指针一定先比慢指针先进入环，而且快慢指针一定是在环中相遇。（快指针会不断在环里转圈等待慢指针进入环，然后相遇）换一种理解方式，因为快指针每次移动两个节点，慢指针每次移动一个节点，相对于慢指针而言，快指针是一个节点一个节点地靠近慢指针的，所以快慢指针一定可以相遇。

 寻找环的入口需要一定的数学推导。假设从头节点到环的入口节点的节点数为x，环的入口结点到快慢节点相遇节点的节点数为y，从相遇节点再到环的入口节点的节点数为z，则环一圈的节点数为y+z。当快慢指针相遇时，慢指针移动的节点数为x+y，快指针移动的节点数为x+y+n(y+z),n为快指针在环内转了n圈才与慢指针相遇。由此我们可以列出等式：（x+y）×2=x+y+n（y+z），化简得：x+y=n（y+z）。因为我们要寻找的是环的入口，所以要计算的是x。进一步变形得：x=n（y+z)-y,提取一个y+z出来：x=(n-1)(y+z)+z。**这里的n一定是大于或等于1的，因为快指针要至少在环内移动一圈才能遇到慢指针。**先令n=1，这说明快指针在环内移动一整圈之后又移动了y个节点后与慢指针相遇。等式就变为x=z。这意味着，如果定义一个指针index2在头节点，定义另一个指针index1在相遇节点，这两个指针每次只移动一个节点，这两个指针相遇的节点就是环的入口节点。如果n>1呢？其实判断方法是一样的。只不过index1指针会在环内多移动n-1圈，最后在环的入口与index2相遇。仔细揣摩上面的公式：x=(n-1)(y+z)+z。

题解

/**
 * 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* fast = head;
        ListNode* slow = head;
        //判断有无环 
        do{
        	if (!fast || !fast->next)	return nullptr;
        	fast = fast->next->next;
			slow = slow->next; 
		} while (fast != slow);
		//有环则判断环起始位置 
		fast = head;
		while (fast != slow) {
			slow = slow->next;
			fast = fast->next;
		} 
		return fast;
    }
};

题目描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC” 示例 2：

输入：s = “a”, t = “a” 输出：“a” 示例 3:

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

提示：

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

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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/minimum-window-substring

思路

​ 本题使用滑动窗口求解，即两个指针 l 和 r 都是从最左端向最右端移动，且 l 的位置一定在 r 的左边或重合。注意本题虽然在 for 循环里出现了一个 while 循环，但是因为 while 循环负责移 动 l 指针，且 l 只会从左到右移动一次，因此总时间复杂度仍然是 O(n)。本题使用了长度为 128 的数组来映射字符，也可以用哈希表替代；其中 chars 表示目前滑动窗口内每个字符缺少的数量，flag 表示每个字符是否在 T 中存在。

​ 具体来讲：我们先遍历一遍字符串T，将字符串T中的字符记录在flag和chars中。此时flag中记录了每个字符在T中是否出现过，chars记录了每个字符在T中出现的次数。定义变量count用来记录滑动窗口中出现T中字符的数量，定义变量min_l用来记录l的最小位置，定义变量min_size用来记录滑动窗口最小大小。将l和r指针初始化为0，for循环向右移动r指针，当r指针指向的字符在T中出现过且此时滑动窗口内这个字符缺少的数量大于等于1，说明这个字符应该放入滑动窗口，此时++count,–chars[S[r]]。当count等于字符串T的长度时（说明滑动窗口内包含了所有T中的字符），此时尝试将l右移，以求最小的子串。更新min_l和min_size，如果l指针指向的字符在字符串T中出现过且chars[S[l]]>=0（说明l指向的字符是滑动窗口内应该包含的字符），–count，++chars[S[l]];指针l向右移动。当r指针指向字符串S的最后一个字符时，此时min_l就是要求的子串的左边界，子串大小为min_size。

题解

class Solution {
public:
    string minWindow(string s, string t) {
		vector<int> chars(128, 0);
		vector<bool> flag(128, false);
		for (int i = 0; i < t.size(); ++i) {
			flag[t[i]] = true;
			++chars[t[i]];
		} 
		int count = 0, l = 0, min_l = 0, min_size = s.size() + 1;
		for (int r = 0; r < s.size(); ++r) {
			if (flag[s[r]]) {
				if (--chars[s[r]] >= 0) ++count;
				while (count == t.size()) {
					if (r - l + 1 < min_size) {
						min_l = l;
						min_size = r - l + 1;
					}
					if (flag[s[l]] && ++chars[s[l]] > 0) --count;
					++l;
				}
			}
		}
		return min_size > s.size() ? "" : s.substr(min_l, min_size);
    }
};

​ 思路中讲解的可能比较乱，一句话总结本题的思想就是：当滑动窗口内未完全包含字符串T内所有字符，则右边界右移，否则左边界右移，以求最小子串。

题目描述

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a² + b² = c 。

示例 1：

输入：c = 5 输出：true 解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3 输出：false

提示：

0 <= c <= 2³¹ - 1

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/sum-of-square-numbers 思路

​ 本题很容易想到用双指针法：一个指针i指向1，一个指针j指向c-1，当i<=j时候计算两指针指向元素的平方和，如果等于c就返回true；如果大于c就–j；如果小于c就++i。但是我们没必要令j指针指向c-1，只要指向c^1/2就行了。另外我们需要注意，本题的c的取值范围，因此在计算平方和的时候要避免int型溢出的情况，需要使用long型避免溢出。

题解

class Solution {
public:
    bool judgeSquareSum(int c) {
		long i = 0, j = static_cast<int>(sqrt(c));
		while (i <= j) {
			long sum = i * i + j * j;
			if (sum == c)	return true; 
			else if (sum < c) ++i;
			else --j;
		}
		return false;
    }
};

题目描述

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: s = “aba” 输出: true

示例 2:

输入: s = “abca” 输出: true 解释: 你可以删除c字符。

示例 3:

输入: s = “abc” 输出: false

提示:

1 <= s.length <= 105 s 由小写英文字母组成

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/valid-palindrome-ii 思路

​ 遇到回文字符串的题目我们都会想到用双指针法，本题也一样，当i和j指针指向不同的字符时候，我们应该删除一个字符，删除i和j哪一个呢？都应该试试。如果都不行就返回false，如果有一个行则返回true。

​ 具体来讲，我们实现一个函数，其功能是判断回文数，主函数用双指针遍历字符，当第一次两指针指向不相等的元素时就调用实现的函数判断删除哪一个字符可以变成回文字符串，如果有一个可以就返回true。

​ 这里我有个疑问，如果第一次两指针指向字符不相等时不删除，而之后再删除会不会也会成为回文字符串？不会的，因为我们是使用双指针，两个指针同时向中心前进，如果第一次出现不相等字符时不处理，之后遇到再处理的话，则之前的没处理的字符会导致整个字符串不是回文字符串。

题解

class Solution {
public:
    bool validPalindrome(string s) {
 		int l = 0, r = s.size() - 1;
		while(l <= r) {
			if (s[l] != s[r])	return Istrue(s, l + 1, r) || Istrue(s, l, r - 1);
			++l;
			--r;
		} 
		return true;//都满足s[l]==s[r]则不用删除字符就是回文字符串 
    }

private:
    bool Istrue(string s, int l, int r) {//判断是否是回文字符串 
        while (l < r)
            if (s[l++] != s[r--]) return false;
        return true;
    }
};

题目描述

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：

输入：s = “abpcplea”, dictionary = [“ale”,“apple”,“monkey”,“plea”] 输出：“apple” 示例 2：

输入：s = “abpcplea”, dictionary = [“a”,“b”,“c”] 输出：“a”

提示：

1 <= s.length <= 1000 1 <= dictionary.length <= 1000 1 <= dictionary[i].length <= 1000 s 和 dictionary[i] 仅由小写英文字母组成

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting

思路

​ 本题要求将字符串s删除某些字符匹配到dictionary中最长的