排序算法的稳定性
数组中相等的数字原有的顺序是否可能在排序的过程中被打破，称之为排序算法的稳定性。具有稳定性的排序算法能保证不会改变原有的顺序。当要排序的内容是一个对象的多个属性，且其原本的顺序存在意义时，如果我们需要在二次排序后保持原有排序的意义，就需要使用到稳定性的算法。
| 排序方法 | 平均复杂度 | 最坏复杂度 | 最好复杂度 | 稳定性 |
|---|---|---|---|---|
| 插入排序 | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | 稳定 |
| 希尔排序 | O ( n 1.3 ) O(n^{1.3}) O(n1.3) | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | 不稳定 |
| 选择排序 | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | 不稳定 |
| 堆排序 | O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) | O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) | O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) | 不稳定 |
| 冒泡排序 | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | 稳定 |
| 快速排序 | O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) | O ( n 2 ) O(n^2) O(n2) | O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) | 不稳定 |
| 归并排序 | O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) | O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) | O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) | 稳定 |
时间复杂度:O(n²)
void Bubble_Sort(vector<int> & arr)
{
bool flag;
int n = arr.size();
for (int i = 0; i < n - 1; ++i) //最多需要排n-1趟
{
flag = false;
for (int j = 0; j < n - 1 - i; ++j)
{
if (arr[j] > arr[j + 1])
{
swap(arr[j], arr[j + 1]);
flag = true;
}
}
if (!flag) break; //没交换过，说明数组已经有序
}
}
时间复杂度:O(n²)
从第一个元素开始，抽出当前元素arr[i]，与之后的每个元素arr[j] (j>i) 进行比较，如果大于元素arr[j]，则将arr[j]往前移一格
void Insert_Sort(vector<int>& arr)
{
int n = arr.size();
for (int i = 0; i < n; ++i)
{
int current = arr[i];
int j = i-1;
while (j >= 0 && current < arr[j])
{
arr[j+1] = arr[j]; //把大于current的往后挪
--j;
}
//跳出循环:j== -1 或者current>=arr[j],此时把current插在j+1的位置上
arr[j+1] = current;
}
}
时间复杂度:O(nlogn)
用二分法递归地将原数组划分为两个有序的数组再合并，当数组长度为1时一定有序。
void merge(std::vector<int>& arr, int begin, int end, std::vector<int>& res)
{
int mid = begin + (begin + end) / 2;
int begin2 = mid + 1;
int pA = begin;
int pB = begin2;
while (pA <= mid && pB <= end)
{
if (arr[pA] < arr[pB])
{
res[pA + pB - begin2] = arr[pA];
++pA;
}
else
{
res[pA + pB - begin2] = arr[pB];
++pB;
}
}
//填入A或B的剩余部分
while (pA <= mid) res[pA++ + pB - begin2] = arr[pA];
while (pB <= mid) res[pA + pB++ - begin2] = arr[pB];
while (begin <= end)
arr[begin++] = res[begin];
}
void mergeSort(std::vector<int>& arr, int begin, int end, std::vector<int>& res)
{
if (begin >= end) return;
int mid = begin + (end - begin) / 2;
mergeSort(arr, begin, mid, res);
mergeSort(arr, mid + 1, end, res);
merge(arr, begin, end, res);
}
void Merge_Sort(std::vector<int>& arr,int begin,int end)
{
//res为保存临时排序结果使用的辅助数组,为避免反复申请空间的开销，提前创建一个
std::vector<int> res(end-begin+1);
mergeSort(arr, begin, end, res);
}
从数组中取出一个数，称之为基数（pivot）
遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域
将左右两个区域视为两个数组，重复前两个步骤，直到排序完成
每一趟的基数都会被放在最终的位置上
int partition(std::vector<int>& arr, int begin, int end)
{
int pivot = arr[begin]; //选取第一个数为基数
int left = begin + 1;
int right = end;
while (left < right)
{
//left移动到第一个大于基数的位置
while (left < right && arr[left] <= pivot) ++left;
//right移动到第一个小于基数的位置
while (left < right && arr[right] >= pivot) --right;
if (left < right)
{
std::swap(arr[left], arr[right]);
++left, --right;
}
}
//比较arr[right]和pivot
if (left == right && arr[left] > pivot) --left;
std::swap(arr[begin], arr[left]);
return left;
}
void Quick_Sort(std::vector<int> & arr,int begin,int end)
{
if (begin >= end) return;
int mid = partition(arr, begin, end);
Quick_Sort(arr, begin, mid - 1);
Quick_Sort(arr, mid + 1, end);
}
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
我们知道快速排序每一趟能够把选取的基数放在最终的位置上，然后再递归两边的区域，我们在此基础上改进一下，如果基数的位置<k就只递归右侧，>k就只递归左侧，直到某趟排序基数的位置为k。
class Solution {
public:
int quickSelect(vector<int>& a, int l, int r, int index) {
int q = randomPartition(a, l, r);
if (q == index) {
return a[q];
} else {
return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
}
}
inline int randomPartition(vector<int>& a, int l, int r) {
int i = rand() % (r - l + 1) + l;
swap(a[i], a[r]);
return partition(a, l, r);
}
inline int partition(vector<int>& a, int l, int r) {
int x = a[r], i = l - 1;
for (int j = l; j < r; ++j) {
if (a[j] <= x) {
swap(a[++i], a[j]);
}
}
swap(a[i + 1], a[r]);
return i + 1;
}
int findKthLargest(vector<int>& nums, int k) {
srand(time(0));
return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
}
};
时间复杂度：O(n)
空间复杂度：O(log n)
速度k应该在1~最大的一堆的数量之间，由于大于k时一定能吃完，小于k时一定不能吃完，因此可以使用二分排序：
如果在速度 speed 下可以在 h 小时内吃掉所有香蕉，则最小速度一定小于或等于 speed，因此将上界调整为 speed；若不能吃完，最小速度一定大于speed，因此将下界调整为 speed+1。
class Solution
{
public:
int minEatingSpeed(vector<int>& piles, int h) {
int low=1;
int high=0;
for(int pile:piles)
{
high=max(high,pile);
}
int k = high;
while(low<high)
{
int mid = low + (high-low)/2; //mid即为当前判断的speed
long time = getTime(piles,mid);
if(time<=h)
{
k = mid;
high = mid;
}
else{
low = mid+1;
}
}
return k;
}
long getTime(const vector<int>& piles, int speed) {
long time = 0;
for (int pile : piles) {
int curTime = (pile + speed - 1) / speed;
time += curTime;
}
return time;
}
};
最经典的题目，在此之上有很多变形
本质是将当前结点的next指向上一个结点，因此要额外保存两个信息：
当前结点的前驱结点和当前节点的下一个结点
迭代法：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr||head->next==nullptr) return head;
ListNode * p=head;
ListNode * last=nullptr;
ListNode * tmp=nullptr;
while(p->next!=nullptr)
{
tmp=p->next;
p->next=last;
last=p;
p=tmp;
}
p->next=last;
return p;
}
};
递归法:
class Solution {
public:
ListNode* reverseList(ListNode * now, ListNode* const &end)
{
if(now->next==end)
return now;
ListNode* nex=reverseList(now->next,end);
nex->next=now;
return now;
}
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(m==n) return head;
ListNode * st=head;
ListNode * ed=head;
for(int i=0;i<m-2;++i)
st=st->next;
for(int j=0;j<n-1;++j)
ed=ed->next;
ListNode * tail=ed->next;
ListNode * newtail;
if(m==1) newtail=reverseList(st,tail);
else newtail = reverseList(st->next,tail);
if(m==1)
head = ed;
else st->next=ed;
newtail->next=tail;
return head;
}
};
138. 复制带随机指针的链表 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head==NULL) return NULL;
Node * p=head;
for(;p!=NULL;p=p->next)
{
Node * tmp=p->next;
p->next=new Node(p->val);
p=p->next;
p->next=tmp;
}
Node* newhead=head->next;
for(p=head;p!=NULL;p=p->next->next)
{
if(p->random==NULL) p->next->random=NULL;
else p->next->random=p->random->next;
}
for(p=head;p!=NULL;)
{
Node* tmp=p->next;
if(p->next==NULL) break;
else {
p->next=p->next->next;
p=tmp;
}
}
return newhead;
}
};
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
二叉树前序遍历的顺序为：
先遍历根节点；
随后递归地遍历左子树；
最后递归地遍历右子树。
二叉树中序遍历的顺序为：
先递归地遍历左子树；
随后遍历根节点；
最后递归地遍历右子树。
class Solution {
private:
unordered_map<int, int> index;
public:
TreeNode * build(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right)
{
if (preorder_left > preorder_right) {
return nullptr;
}
// 前序遍历中的第一个节点就是根节点
int preorder_root = preorder_left;
// 在中序遍历中定位根节点
int inorder_root = index[preorder[preorder_root]];
// 先把根节点建立出来
TreeNode* root = new TreeNode(preorder[preorder_root]);
// 得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
// 递归地构造左子树，并连接到根节点
// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root->left = build(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
// 递归地构造右子树，并连接到根节点
// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root->right = build(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
// 构造哈希映射，帮助我们快速定位根节点
for (int i = 0; i < n; ++i) {
index[inorder[i]] = i;
}
return build(preorder, inorder, 0, n - 1, 0, n - 1);
}
};
也称二叉查找树或二叉排序树，其每个节点都具有如下性质:
左子树上的所有结点的值均小于根结点
右子树上的所有结点的值均大于根结点
没有值相等的节点
对二叉搜索树进行中序遍历，将得到一个由所有结点组成的有序的数组
新结点的插入和删除
插入：按照查找算法，如果要插入的结点值大于当前结点，则访问右子树，若小于当前结点则访问左子树，直到左子树或右子树为空时插入。 如果值已经存在则插入失败
删除: 如果要删除的结点是叶子结点，则直接删除。如果要删除的结点有一个子节点，则删除后用该子节点取代原来的位置。若有多个子节点，则对所有子节点进行中序遍历，找到一个大于要删除结点的左儿子小于其右儿子的结点互换。
平衡二叉搜索树,具有如下性质:
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
为什么需要平衡二叉树：普通二叉搜索树会在极端情况下退化为一根长度为n的链表，此时查找和删除的时间复杂度是O(n)，而平衡二叉树不会出现这个问题
如何插入和删除结点:
在插入一个结点时，如果破坏了上述性质，即插入后出现了某个结点左右子树的高度差大于等于2，
那么此时将这个结点进行左旋或者右旋。（如果右子树高就左旋，左子树高就右旋）
左旋
对x进行左旋，意味着"将x变成一个左子节点"。
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除
深度优先搜索一般以递归的方式实现，可以理解为走迷宫时，每次都走到死胡同再回头，回到上一个路口，选择一条没走过的路继续重复上述过程。是一种算法。
而回溯则是运用深度优先搜索算法来解决问题的一种思想或者方法。当一个状态转移不下去或者知道不正确时就回到上一个状态并撤销这个状态的影响。
拿一道很经典的题来举例：
79. 单词搜索 - 力扣（LeetCode）
简单说就是使用递归每次转移一个状态，如果发现不匹配就返回，转移另一个状态。
如何转移？用r,c来表示行，列坐标，那么有x+1,y+1,x-1,y-1四种转移方式（可以往上下左右四个方向走），注意转移后如果坐标越界了那么是无效状态。
代码如下：（我写的这个版本应该比官方题解清晰很多）
class Solution {
public:
bool isfind=false;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
int vis[10][10]={0};
void dfs(int dep,int r,int c,int &m,int &n,string & word,vector<vector<char>> & board)
{
if(dep==word.size()) {isfind=true; return;}
if(dep>word.size()) return;
for(int d=0;d<4;++d)
{
int r1=r+dx[d];
int c1=c+dy[d];
if(r1<0||r1>=m||c1<0||c1>=n || vis[r1][c1])
continue;
if(board[r1][c1]==word[dep])
{
vis[r1][c1]=1;
dfs(dep+1,r1,c1,m,n,word,board);
vis[r1][c1]=0;
if(isfind) return;
}
}
}
bool exist(vector<vector<char>>& board, string word) {
int m=board.size();
int n=board[0].size();
for(int r=0;r<m;++r)
for(int c=0;c<n;++c)
if(board[r][c]==word[0]){
vis[r][c]=1;
dfs(1,r,c,m,n,word,board);
vis[r][c]=0;
if(isfind) return true;
}
return isfind;
}
};
广度优先搜索可以理解为是按层从上往下遍历一个树，其中每个节点有多少子节点相当于有多少个状态可以转移。
此题中
动态规划主要的难点在于写出正确的状态转移方程以及边界条件，我们通过一些具体题目来分析:
198. 打家劫舍 - 力扣（LeetCode） (leetcode-cn.com)
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400
设 dp[i] 表示偷 0~i 的房子能获得的最大收益
只有两间房子(n=2)的时候，显然有 dp[1]=max(nums[0],nums[1])
当n>2时，假设i>2：那么有且只有两种选择：偷房间i和不偷房间i，所以可以写出状态转移方程：
d p [ i ] = m a x ( d p [ i − 2 ] + n u m s [ i ] , d p [ i − 1 ] ) dp[i]=max(dp[i-2]+nums[i], dp[i-1]) dp[i]=max(dp[i−2]+nums[i],dp[i−1])
int rob(vector<int> & nums)
{
int n=nums.size();
if(n==1) return nums[0];
vector<int> dp(n);
dp[0]=nums[0];
dp[1]=max(nums[0],nums[1]);
if(n>2)
for(int i=2;i<n;i++)
dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
return dp[n-1];
}
设置好边界条件，代码如上，最后返回dp[n-1]即可
下面我会贴一些常见的字符串题目
动态规划+回溯:
131. 分割回文串 - 力扣（LeetCode） (leetcode-cn.com)
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
1 <= s.length <= 16
s 仅由小写英文字母组成
首先我们要能判断一个子串是否是回文串，不然无法去分割
如果在一个回文串的两端添加一样的字符，形成的新字符串一定是回文串，而这可以囊括所有回文串，我们假定空字符串和单字符是回文串，那么"aa"就是由""加上两端’a’=='a’形成的，由此可以写出如下状态转移方程:
f(i,j) = f(i+1,j-1) && s[i]==s[j] (i<j)
=true (i>=j)
然后再通过回溯来寻找所有能满足所有子串都为回文串的划分方案
class Solution
{
private:
vector<vector<bool>> f; // f[i][j]表示子串i到j是否为回文串
vector<string> solve; //构造的题解
vector<vector<string>> ans; //最后返回的总答案
int n;
public:
void dfs(const string &s, int begin) // begin为新一段子串的开始索引
{
if (begin == n)
{
ans.push_back(solve);
return;
}
for (int end = begin; end < n; ++end)
{
if (f[begin][end])
{
ans.push_back(s.substr(begin, end - begin + 1));
dfs(s, end + 1); //找下一段为回文的子串
ans.pop_back();
}
}
}
vector<vector<string>> partition(string s)
{
n = s.size();
f.assign(n, vector<bool>(n, true));
for (int i = n - 1; i >= 0; --i)
for (int j = i + 1; j < n; ++j)
f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
dfs(s, 0);
return ans;
}
};
471. 编码最短长度的字符串 - 力扣（LeetCode） (leetcode-cn.com)
自顶而下的搜素算法：
class Solution
{
public:
string encode(string s)
{
vector<vector<string>> d(s.size(), vector<string>(s.size(), ""));
return dfs(s, 0, s.size() - 1, d);
}
string dfs(const string s, int i, int j, vector<vector<string>> &d)
{
if (i > j)
return "";
string &ans = d[i][j];
if (ans.size())
return ans;
int len = j - i + 1;
ans = s.substr(i, len);
if (len < 5)
return ans;
int p = (ans + ans).find(ans, 1);
if (p < len)
{
ans = std::to_string(len / p) + "[" + dfs(s, i, i + p - 1, d) + "]";
}
for (int k = i; k < j; ++k)
{
string a = dfs(s, i, k, d);
string b = dfs(s, k + 1, j, d);
if (a.size() + b.size() < ans.size())
ans = a + b;
}
return ans;
}
};
自底向上的区间DP：
string encode(string s) {
vector<vector<string>> d(s.size(),vector<string>(s.size(),""));
for(int len=1;len<=s.size();++len){
for(int i=0;i+len<=s.size();++i){
const int j=i+len-1;
string& ans=d[i][j];
ans=s.substr(i,len);
if(len >= 5){
int p=(ans+ans).find(ans,1);
if(p < ans.size()){
ans=to_string(ans.size()/p)+"["+d[i][i+p-1]+"]";
}
for(int k=i;k<j;++k){
if(d[i][k].size()+d[k+1][j].size() < ans.size()){
ans=d[i][k] + d[k+1][j];
}
}
}
}
}
return d[0][s.size()-1];
}
该题的本质是尝试使用小区间的答案来合并生成大区间的答案。
30. 串联所有单词的子串 - 力扣（LeetCode） (leetcode-cn.com)
注意一个很重要的条件，需要所有单词串在一起的子串，并且每个单词长度是一样的。从这点很容易想到使用滑动窗口来解决，每滑一次如果匹配到单词就标记该单词防止重复匹配，一旦匹配到不存在的单词就清空标记重新匹配。如何快速判断是否匹配？很容易想到用哈希表.因此本题大致的框架就出来了：滑动窗口+哈希表
class Solution
{
private:
public:
vector<int> findSubstring(string s, vector<string>& words)
{
vector<int> ans;
int wordnum=words.size();
int n=s.size();
if(!wordnum) return ans;
int wordlen=words[0].size();
int limit=wordnum*wordlen;
unordered_map<string,int> map;
for(auto &w:words)
++map[w]; //因为可能有重复出现的单词,所以不能简单设为1
for(int i=0;i<wordlen;++i) //以0到wordlen-1为偏移进行滑动窗口匹配
{
int left=i;
int right=i;
int cnt=0; //窗口内已达到数量的单词数
unordered_map<string,int> window;
while(right+wordlen-1<n)
{
string cur_right=s.substr(right,wordlen);
if(map.count(cur_right))
{
++window[cur_right];
//列表里该单词已被选完时，数量不增加
if(window[cur_right]==map[cur_right])
++cnt;
}
//左边界右移，出窗
if(right+wordlen-left>limit)
{
string cur_left=s.substr(left,wordlen);
if(map.count(cur_left))
{
if(window[cur_left]==map[cur_left])
--cnt;
--window[cur_left];
}
left+=wordlen;
}
//如果此时窗口长度正好，且窗口内所有单词都选够了数量
if(right-left+wordlen==limit && cnt==map.size())
{
ans.push_back(left);
}
//右边窗口向右滑动
right+=wordlen;
}
}
return ans;
}
};
44. 通配符匹配 - 力扣（LeetCode） (leetcode-cn.com)
模式p一共有三种字符：
a-z, ? , * 需要分别讨论
使用dp[i][j] 表示字符串s的前i个字符和模式p的前j个字符能否匹配
分类讨论p[j]:
如果pj是小写字母，那么s[i]必须为小写字母
dp[i][j]=(s[i] ==p[j] ) && dp[i−1][j−1]
如果pj是？，那么对s[i]无要求
dp[i][j]=dp[i-1][j-1]
如果pj是*，可以匹配0个或任意多个，那么0个的时候可以当p[j]不存在,
任意多个时可以当s[i]不存在,从s[i-1]转移
dp[i][j]=dp[i-1][j]||dp[i][j-1]
因为pj是*, i-1可以一直往前追溯到dp[0][j] 也就是说只要前面的pj都匹配，不论匹配了多少，*号都可以往后一直匹配
边界条件：
dp[0][0]=True，当字符串 ss 和模式 pp 均为空时，匹配成功；
dp[i][0] =False, (i>0)空模式无法匹配非空字符串；
dp[0][j] 需要分情况讨论：因为星号才能匹配空字符串，所以只有当模式 p 的前 j个字符均为星号时，dp[0][j]才为真。
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
dp[0][0] = true;
for (int i = 1; i <= n; ++i) {
if (p[i - 1] == '*') {
dp[0][i] = true;
}
else {
break;
}
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 1] | dp[i - 1][j];
}
else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
};
双指针主要适用于解决多重循环中重复遍历的问题
15. 三数之和 - 力扣（LeetCode） (leetcode-cn.com)
给你一个包含 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
-105 <= nums[i] <= 105
这道题正常来说我们需要三重for循环，但是对于3000的数据规模来说O(n^3)的复杂度显然过高。
很容易发现三重for循环中三个指针都重复走过彼此已经走过的地方，但是此题中三个数不允许有重复且没有顺序性，如果使用三重for循环在最坏的情况下必然会造成答案数组中出现大量重复的答案，去重又需要花费大量的时间。 因此三个指针完全不必指向彼此已经指过的地方。我们假设这三个指针（索引）为a,b,c. ,先将数组进行排序，这样在a<b<c的情况下，如果出现了符合题目的nums[a]+nums[b]+nums[c]==target. 那么a不动的情况下 b右移（且跳过相同的元素） 必然会有nums[a]+nums[b]+nums[c]>target, 此时必须将c左移否则b再往后和会始终>target。这里便体现出排序的作用，利用大小顺序以及和为定值的性质可以限制b的移动范围，且可以将c的移动关联到b的移动，从而将三重枚举实际上降为二重枚举。排序的第二个作用是，排完序之后相同的元素会相邻，这样在枚举a和b的时候如果遇到值相同的a或者b可以跳过来避免出现重复的三元组。
#define SUM nums[a]+nums[b]+nums[c]
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ans;
if(n<3) return ans;
int target=0;
sort(nums.begin(), nums.end());
int a=0,c=n-1,b=1;
for(;a<n-2;a++)
{
if(a>0 && nums[a]==nums[a-1]) continue; //跳过值重复的a
b=a+1;
c=n-1;
//剪枝，如果最左边三个的和已经超过target，那么已经不可能满足SUM=target了，可直接退出
if(nums[a]+nums[a+1]+nums[a+2]>target) break;
//如果最右边三个的和仍小于target，那么也不可能满足SUM=target了，可直接退出
if(nums[c-2]+nums[c-1]+nums[c]<target) break;
//如果当前的a加上最右边的两个小于target，那么直接移动a
if(nums[a]+nums[c-1]+nums[c]<target) continue;
while(b<c)
{
while(SUM>target && b<c) --c;
if(b==c) break;
if(SUM==target)
{
ans.push_back({nums[a],nums[b],nums[c]});
--c; //不需要再处理跳过重复的c，因为a和b不重复的情况下c不可能重复
}
++b;
while(b<c && nums[b]==nums[b-1]) ++b; //跳过重复的b
}
}
return ans;
}
下面这道题也一样，只不过需要枚举前两个指针，留后面两个双指针移动
18. 四数之和 - 力扣（LeetCode） (leetcode-cn.com)
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
(1) 0 <= a, b, c, d < n
(2) a、b、c 和 d 互不相同
(3) nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
#define SUM (long)nums[a]+nums[b]+nums[c]+nums[d]
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
int n=nums.size();
if(n<4) return ans;
int a,b,c,d;
sort(nums.begin(),nums.end());
for(a=0;a<n-3;++a)
{
if(a>0 && nums[a]==nums[a-1]) continue;
for(b=a+1;b<n-2;++b)
{
if(b>a+1 && nums[b]==nums[b-1]) continue;
c=b+1;
d=n-1;
while(c<d)
{
if(SUM==target)
{
ans.push_back({nums[a], nums[b], nums[c], nums[d]});
++c; //如果SUM==target那么单独移动c或者d都不可能再得到第二个解，只能同时移动
--d;
while(nums[c]==nums[c-1] && c<d) ++c;
while(nums[d]==nums[d+1] && c<d) --d;
}
else if(SUM < target) ++c; //如果比目标值小就右移c
else --d; //比目标值大就左移d
}
}
}
return ans;
}
};
需要注意的细节是如何避免重复的四元组又不遗漏答案
587. 安装栅栏 - 力扣（LeetCode）
这题的本质就是求凸包
用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边形，它能包含点集中所有的点。
Graham 算法
先选择边缘的一个点作为原点，如y最小的点，该点一定在凸包上
将其他点按照极角坐标大小排序，若极角大小相同按距离排序，排序后遍历数组，把点放入栈中，如果栈顶的点到当前点是左拐（用叉积判断）或同一直线上，将当前点压入栈，如果栈顶到当前点是右拐，弹出栈顶，考虑从新的栈顶到当前点是否为左拐，若还为右拐则重复上述过程。
class Solution
{
public:
//计算向量PQ和QR的叉积
int cross(const vector<int> &p, const vector<int> &q, const vector<int> &r)
{
return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
}
//计算两点距离的平方
int distance(const vector<int> &p, const vector<int> &q)
{
return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
}
vector<vector<int>> outerTrees(vector<vector<int>> &trees)
{
int n = trees.size();
if (n < 4)
{
return trees;
}
int ori = 0;
//找到y最小的点作为原点
for (int i = 0; i < n; ++i)
if (trees[i][1] < trees[ori][1])
ori = i;
swap(trees[ori], trees[0]);
sort(trees.begin() + 1, trees.end(), [&](const vector<int> &a, const vector<int> &b)
{
int diff=cross(trees[0],a,b);
if(diff== 0)
return distance(trees[0],a)<distance(trees[0],b);
else return diff>0; });
int r = n - 1; //将最后的和原点同一条直线的点按距离从大到小排序，距离远的应该排在前面
//因为最后连回原点是由远及近的
while (r >= 0 && cross(trees[0], trees[n - 1], trees[r]) == 0)
--r;
for (int l = r + 1, h = n - 1; l < h; ++l, --h)
swap(trees[l], trees[h]);
stack<int> st;
st.emplace(0);
st.emplace(1);
for (int i = 2; i < n; ++i)
{
int top = st.top();
st.pop();
while (!st.empty() && cross(trees[st.top()], trees[top], trees[i]) < 0)
{
top = st.top(); //抛弃掉当前的top
st.pop();
}
st.emplace(top);
st.emplace(i);
}
vector<vector<int>> ans;
while (!st.empty())
{
ans.emplace_back(trees[st.top()]);
st.pop();
}
return ans;
}
};
207. 课程表 - 力扣（LeetCode） (leetcode-cn.com)
两种解法：
DFS和BFS
1.DFS
如果当前搜索到了结点u，结点u出现在所有其前驱结点之后，那么u满足要求
当我们对图进行深度优先搜索时，回溯一个结点时将该结点放入栈中，那么栈中结点排布的顺序就是拓扑结构，链尾的元素最先进去。我们只需要在排的过程中持续检测是否有不符合拓扑排序的结点存在。
那么如何检测呢？我们可以将一个结点标记为三种状态，用0,1,2表示
0表示 v 为未搜索 ，1表示v访问了一次，即搜索过了但还没回溯回来
2表示v访问了两次，此时v回溯完，已经在栈中。
我们遍历访问当前搜索的结点所有的相邻结点（依赖的课程），如果都为2那么当前结点放入栈
如果遍历到了一个已经为1的说明存在环：2只能回溯时产生，不能继续往下搜索时产生
这题不需要记录整个拓扑排序的结果，因此可以不需要使用栈。
class Solution {
private:
vector<vector<int>> edges;
vector<int> visited;
bool ans = true;
void dfs(int u) {
visited[u]=1;
for(int v:edges[u])
{
if(!visited[v])
{
dfs(v);
if(!ans) return;
}
else if(visited[v]==1)
{
ans=false;
return;
}
}
visited[u]=2;
}
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
edges.resize(numCourses);
visited.resize(numCourses);
for(const auto& info:prerequisites)
edges[info[1]].push_back(info[0]);
for(int i=0;i<numCourses&&ans;++i)
if(!visited[i])
dfs(i);
return ans;
}
};
2.BFS
首先把入度为0的结点放入队列。BFS时遍历当前结点的每个相邻结点，并将他们的入度都减1。将其中入度变为0的结点放入队列。如果某个结点无法入队，说明存在环，不存在拓扑排序。
#include <vector>
#include <iostream>
#include <map>
#include <queue>
using namespace std;
class Solution {
private:
vector<vector<int>> edges;
vector<int> indegree; //入度
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
edges.resize(numCourses);
indegree.resize(numCourses);
for(const auto& info:prerequisites)
{
edges[info[1]].push_back(info[0]);
++indegree[info[0]]; //修0必须先修1，所以是由1入0，0的入度+1
}
queue<int> q;
for(int i=0;i<numCourses;++i) //把入度为0的点先加入队列
if(indegree[i]==0)
q.push(i);
int visited=0; //记录能入队的结点的数量
while(!q.empty())
{
int u=q.front();
q.pop();
++visited;
for(int v:edges[u]) //遍历所有u的相邻点
{
--indegree[v];
if(indegree[v]==0)
q.push(v);
}
}
return visited==numCourses; //如果所有结点都能入队说明可以拓扑排序
}
};
哈希表（又称散列表）的原理为：借助哈希函数，将键映射到存储桶地址。更确切地说，
首先开辟一定长度的，具有连续物理地址的桶数组；
当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；
当我们想要搜索一个键时，哈希表将使用哈希函数来找到对应的桶，并在该桶中进行搜索。
负载因子
实际利用桶的个数与桶的总数的比值。
又称装填因子，该参数反映了哈希表的稀疏程度。比较合理的负载因子是0.7
哈希函数
哈希函数的键与桶的对应关系具有确定性。也就是说，对于 key 所映射的桶地址，只由 key 键本身决定，而不由其他因素决定；
哈希函数不应太过复杂。太过于复杂的哈希函数将导致计算桶地址不能快速完成，从而无法快速定位桶；
映射结果的分布应具有均匀性。对于特定的桶空间，我们应尽量保证数据经过哈希函数映射之后，能够均匀地分布在桶的整个地址空间中。
一般来讲，结果分布越随机，越均匀的哈希函数，它的性能越好。如果分布过于集中，会增大发生哈希冲突的概率，且剩余的桶没有有效利用导致空间利用率低
解决冲突的方法
线性试探法
插入键 key 时，如果发现桶单元 bucket[hash(key)] 已经被占用，则向下线性寻找，直到找到可以使用的空桶
当 查找 某个键时，首先会通过哈希函数计算出桶的地址，然后比较该桶中保存的值是否为该键，如果不是，则继续向下寻找。如果查找到末尾，则会从头开始查找。
而 删除 某个键时，为了避免查找过程中出现信息丢失，会将删除位置标记为 deleted，当之后再进行线性查找时，遇到 deleted 会继续向下查找而不会中断。
链地址法
使用一个链表数组,来存储相应数据，插入时发生冲突就添加到链表的末尾
双重哈希法
发生冲突时，使用另一个哈希函数来避免冲突
公共溢出区法
建立另一个哈希表dict_overflow作为公共溢出区，将发生冲突的键保存在该哈希表中
若查找的键发生冲突，则在公共溢出区进行线性查找