1、知识点分布
填一下这个之前欠的天坑，复习一下算法入门的经典基础题。
除夕，正月初一，初二，一共写了三整天，除了吃饭就窝着补题。
每天30题+，整个人都写晕啦，终于写完啦（）
markdown生成
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("100.txt","r",stdin);
freopen("100.md","w",stdout);
for(int i = 1; i <= 100; i++){
string s; getline(cin,s);
cout<<"#### ";
printf("%03d: ",i);
cout<<s<<"\n";
printf("```cpp\n\n```\n");
}
return 0;
}
编号 题目 题号 分类
1 翻转二叉树 226 二叉树
2 合并二叉树 617 二叉树
3 二叉树的最大深度 104 二叉树
4 二叉树的中序遍历 94 二叉树
5 二叉树展开为链表 114 二叉树
6 把二叉搜索树转换为累加树 538 二叉树
7 从前序与中序遍历序列构造二叉树 105 二叉树
8 不同的二叉搜索树 96 二叉树
9 二叉树的最近公共祖先 236 二叉树
10 二叉树的层序遍历 102 二叉树
11 打家劫舍 III 337 二叉树
12 路径总和 III 437 二叉树
13 对称二叉树 101 二叉树
14 二叉树的序列化与反序列化 297 二叉树
15 二叉树的直径 543 二叉树
16 二叉树中的最大路径和 124 二叉树
17 验证二叉搜索树 98 二叉树
18 实现 Trie (前缀树) 208 字典树
19 单词拆分 139 字典树
20 全排列 46 搜索（回溯）
21 括号生成 22 搜索（回溯）
22 组合总和 39 搜索（回溯）
23 电话号码的字母组合 17 搜索（回溯）
24 目标和 494 搜索（回溯）
25 下一个排列 31 搜索（回溯）
26 零钱兑换 322 搜索（记忆化）
27 岛屿数量 200 搜索（联通块）
28 删除无效的括号 301 搜索（枚举）
29 课程表 207 搜索（拓扑排序）
30 除法求值 399 搜索（最短路）
31 每日温度 739 栈
32 接雨水 42 栈
33 最小栈 155 栈
34 字符串解码 394 栈
35 最大矩形 85 栈
36 回文链表 234 栈
37 有效的括号 20 栈
38 柱状图中最大的矩形 84 栈
39 最长有效括号 32 栈
40 反转链表 206 链表
41 合并两个有序链表 21 链表
42 排序链表 148 链表
43 相交链表 160 链表
44 合并K个升序链表 23 链表
45 环形链表 II 142 链表
46 LRU 缓存 146 链表
47 环形链表 141 链表
48 删除链表的倒数第 N 个结点 19 链表
49 两数相加 2 链表
50 字母异位词分组 49 字符串
51 回文子串 647 字符串
52 编辑距离 72 字符串
53 找到字符串中所有字母异位词 438 字符串
54 最小覆盖子串 76 字符串
55 无重复字符的最长子串 3 字符串
56 最长回文子串 5 字符串
57 正则表达式匹配 10 字符串
58 戳气球 312 数组（动态规划）
59 最佳买卖股票时机含冷冻期 309 数组（动态规划）
60 最大子数组和 53 数组（动态规划）
61 最长连续序列 128 数组（动态规划）
62 最长递增子序列 300 数组（动态规划）
63 打家劫舍 198 数组（动态规划）
64 分割等和子集 416 数组（动态规划）
65 乘积最大子数组 152 数组（动态规划）
66 搜索旋转排序数组 33 数组（二分）
67 在排序数组中查找元素的第一个和最后一个位置 34 数组（二分）
68 寻找两个正序数组的中位数 4 数组（二分）
69 数组中的第K个最大元素 215 数组（排序）
70 移动零 283 数组（排序）
71 前 K 个高频元素 347 数组（排序）
72 盛最多水的容器 11 数组（双指针）
73 颜色分类 75 数组（双指针）
74 最短无序连续子数组 581 数组（双指针）
75 三数之和 15 数组（双指针）
76 根据身高重建队列 406 数组（贪心）
77 除自身以外数组的乘积 238 数组（贪心）
78 多数元素 169 数组（贪心）
79 找到所有数组中消失的数字 448 数组（贪心）
80 任务调度器 621 数组（贪心）
81 买卖股票的最佳时机 121 数组（贪心）
82 两数之和 1 数组（贪心）
83 会议室 II 253 数组（贪心）
84 滑动窗口最大值 239 数组（贪心）
85 合并区间 56 数组（贪心）
86 和为 K 的子数组 560 数组（贪心）
87 跳跃游戏 55 数组（贪心）
88 不同路径 62 递推
89 完全平方数 279 递推
90 爬楼梯 70 递推
91 旋转图像 48 矩阵
92 最小路径和 64 矩阵
93 搜索二维矩阵 II 240 矩阵
94 最大正方形 221 矩阵
95 单词搜索 79 矩阵
96 汉明距离 461 位运算
97 子集 78 位运算
98 比特位计数 338 位运算
99 只出现一次的数字 136 位运算
100 寻找重复数 287 位运算
2、完整代码
001: 翻转二叉树 226
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
/**
* 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) {}
* };
*/
// 翻转以 root 为根的二叉树，然后返回翻转后的二叉树的根节点
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return nullptr;
if (root->left == nullptr && root->right == nullptr) {
return root;
}
TreeNode *left = invertTree(root->left);
TreeNode *right = invertTree(root->right);
root->right = left;
root->left = right;
return root;
}
};002: 合并二叉树 617
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-binary-trees
/**
* 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:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1==nullptr)return root2;
if(root2==nullptr)return root1;
TreeNode* m = new TreeNode(root1->val+root2->val);
m->left = mergeTrees(root1->left,root2->left);
m->right = mergeTrees(root1->right,root2->right);
return m;
}
};003: 二叉树的最大深度 104
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
//无脑dfs就行
/**
* 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 maxDepth(TreeNode* root) {
if(root==nullptr)return 0;
return max(maxDepth(root->left), maxDepth(root->right))+1;
}
};004: 二叉树的中序遍历 94
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
输入：root = [1,null,2,3]
输出：[1,3,2]- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
/**
* 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:
void dfs(TreeNode *u, vector<int>& res){
if(u==nullptr)return ;
dfs(u->left, res);
res.push_back(u->val);
dfs(u->right,res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int>res;
dfs(root, res);
return res;
}
};005: 二叉树展开为链表 114
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
/**
* 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:
void flatten(TreeNode* root) {
vector<TreeNode*>l;
pre(root, l);
int n = l.size();
for(int i = 1; i < n; i++){
TreeNode* pree = l[i-1], *curr = l[i];
pree->left = nullptr;
pree->right = curr;
}
}
void pre(TreeNode* root, vector<TreeNode*>& l){
if(root==nullptr)return ;
l.push_back(root);
pre(root->left, l);
pre(root->right, l);
}
};006: 把二叉搜索树转换为累加树 538
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree
/**
* 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 sum = 0;
TreeNode* convertBST(TreeNode* root) {
if(root != nullptr){
convertBST(root->right);
sum += root->val;
root->val = sum;
convertBST(root->left);
}
return root;
}
};007: 从前序与中序遍历序列构造二叉树 105
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
/**
* 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:
unordered_map<int, int> index;
TreeNode * build(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir){
if(pl > pr)return nullptr;
//根节点
int prt = pl;
int irt = index[preorder[prt]];
//
TreeNode* root = new TreeNode(preorder[prt]);
int lsz = irt-il;
root->left = build(preorder, inorder, pl+1,pl+lsz, il, irt-1);
root->right = build(preorder, inorder, pl+lsz+1,pr, irt+1,ir);
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);
}
};008: 不同的二叉搜索树 96
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees
class Solution {
public:
int numTrees(int n) {
//卡特兰数
long long x = 1;
for(int i = 0; i < n; i++){
x = x*2*(2*i+1)/(i+2);
}
return (int)x;
}
};009: 二叉树的最近公共祖先 236
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
unordered_map<int,TreeNode*>fa;
unordered_map<int,bool>vis;
void dfs(TreeNode * u){
if(u->left != nullptr){
fa[u->left->val] = u;
dfs(u->left);
}
if(u->right != nullptr){
fa[u->right->val] = u;
dfs(u->right);
}
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
fa[root->val] = nullptr;
dfs(root);
while(p != nullptr){
vis[p->val] = true;
p = fa[p->val];
}
while(q != nullptr){
if(vis[q->val])return q;
q = fa[q->val];
}
return nullptr;
}
};010: 二叉树的层序遍历 102
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
//开个队列往里面丢就是了，简称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<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>>res;
if(!root)return res;
queue<TreeNode*>q;
q.push(root);
while(q.size()){
int len = q.size();
res.push_back(vector<int>());
for(int i = 1; i <= len; i++){
auto t = q.front(); q.pop();
res.back().push_back(t->val);
if(t->left)q.push(t->left);
if(t->right)q.push(t->right);
}
}
return res;
}
};011: 打家劫舍 III 337
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-iii
/**
* 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:
//f[i]，选第i个点能获得的最大价值
//g[i]，不选第i个点能获得的最大价值
unordered_map<TreeNode*, int> f, g;
void dfs(TreeNode* u){
if(!u)return ;
dfs(u->left);
dfs(u->right);
f[u] = u->val+g[u->left]+g[u->right];
g[u] = max(f[u->left],g[u->left])+max(f[u->right],g[u->right]);
}
int rob(TreeNode* root) {
dfs(root);
return max(f[root], g[root]);
}
};012: 路径总和 III 437
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-iii
/**
* 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 dfs(TreeNode* u, int target){
if(!u)return 0;
int res = 0;
if(u->val==target)res++;
res += dfs(u->left,target-u->val);
res += dfs(u->right,target-u->val);
return res;
}
int pathSum(TreeNode* root, int targetSum) {
//暴力，从每个点开始搜.
if(!root)return 0;
int res = dfs(root,targetSum);
res += pathSum(root->left,targetSum);
res += pathSum(root->right,targetSum);
return res;
}
};013: 对称二叉树 101
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true/**
* 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:
bool check(TreeNode *p, TreeNode *q){//双指针
if(p==nullptr && q==nullptr)return true;
if(p==nullptr || q==nullptr)return false;
return p->val==q->val && check(p->left,q->right) && check(p->right,q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};014: 二叉树的序列化与反序列化 297
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例 1：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
void enc(TreeNode* u, string &res){
if(u==nullptr)res += "None,";
else{
res += to_string(u->val)+",";
enc(u->left,res);
enc(u->right,res);
}
}
string serialize(TreeNode* root) {
string res;
enc(root,res);
return res;
}
// Decodes your encoded data to tree.
TreeNode* dec(list<string>& li){
if(li.front()=="None"){
li.erase(li.begin());
return nullptr;
}
TreeNode* u = new TreeNode(stoi(li.front()));
li.erase(li.begin());
u->left = dec(li);
u->right = dec(li);
return u;
}
TreeNode* deserialize(string data) {
list<string>li;
string tmp="";
for(char ch : data){
if(ch==','){
li.push_back(tmp);
tmp.clear();
}else{
tmp.push_back(ch);
}
}
if(!tmp.empty())li.push_back(tmp);
return dec(li);
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));015: 二叉树的直径 543
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
/**
* 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 ans = 0;
int dfs(TreeNode *u){
if(u==nullptr)return 0;
int l = dfs(u->left);
int r = dfs(u->right);
ans = max(ans, l+r+1);
return max(l,r)+1;
}
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return ans-1;
}
};016: 二叉树中的最大路径和 124
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
/**
* 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 ans = INT_MIN;
int dfs(TreeNode* u){
if(u==nullptr)return 0;
int left = max(dfs(u->left), 0);
int right = max(dfs(u->right), 0);
int tmp = u->val+left+right;//以该节点为连接点能获得的最大价值
ans = max(ans, tmp);
return u->val+max(left,right);//节点的最大贡献值
}
int maxPathSum(TreeNode* root) {
dfs(root);
return ans;
}
};017: 验证二叉搜索树 98
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
/**
* 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:
bool dfs(TreeNode* root, long long mi, long long mx){//mi,mx表示当前树的最小值，最大值
if(root==nullptr)return true;
if(root->val<=mi||root->val>=mx)return false;
return dfs(root->left,mi,root->val)&&dfs(root->right, root->val, mx);
}
bool isValidBST(TreeNode* root) {
//递归遍历一遍，判断一下节点权值关系即可.
return dfs(root,LONG_MIN, LONG_MAX);
}
};018: 实现 Trie (前缀树) 208
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
示例：
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
提示：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree
class Trie {
public:
vector<Trie*>ch;
bool isEnd;
Trie():ch(26),isEnd(false){}
void insert(string word) {
Trie * node = this;
for(char x : word){
x -= 'a';
if(node->ch[x]==nullptr)node->ch[x] = new Trie();
node = node->ch[x];
}
node->isEnd = true;
}
Trie* searchPrefix(string word) {
Trie* node = this;
for (char x : word) {
x -= 'a';
if (node->ch[x] == nullptr) {
return nullptr;
}
node = node->ch[x];
}
return node;
}
bool search(string word) {
Trie* node = this->searchPrefix(word);
return node != nullptr && node->isEnd;
}
bool startsWith(string prefix) {
return this->searchPrefix(prefix) != nullptr;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/019: 单词拆分 139
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string>se;
for(auto str : wordDict){
se.insert(str);
}
//f[i]表示前i个字母能否被表示
vector<bool>f(s.size()+1);
f[0] = 1;
for(int i = 1; i <= s.size(); i++){
for(int j = 0; j < i; j++){
if(f[j] && se.find(s.substr(j,i-j))!=se.end() ){
f[i] = true;
break;
}
}
}
return f[s.size()];
}
};020: 全排列 46
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
class Solution {
public:
void dfs(vector<vector<int>> &res, vector<int>& nums, int cur, vector<int>&tmp){
if(cur == nums.size()){
res.push_back(tmp);
}else for(int i = 0; i < nums.size(); i++){
int ok = 1;
for(int j = 0; j < cur; j++){
if(tmp[j]==nums[i])ok = 0;
}
if(ok){
tmp.push_back(nums[i]);
dfs(res, nums, cur+1, tmp);
tmp.pop_back();
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<int>tmp;
dfs(res, nums, 0, tmp);
return res;
}
};021: 括号生成 22
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
class Solution {
public:
void dfs(int l, int r, int n, string& now, vector<string>&res){
if(now.size()==n*2){
res.push_back(now);
return ;
}
if(l<n){
now.push_back('(');
dfs(l+1,r,n,now,res);
now.pop_back();
}
if(r<l){
now.push_back(')');
dfs(l,r+1,n,now, res);
now.pop_back();
}
}
vector<string> generateParenthesis(int n) {
vector<string>res;
string now = "";
dfs(0,0,n,now, res);
return res;
}
};022: 组合总和 39
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
class Solution {
public:
vector<vector<int>>ans;
vector<int>tmp;
void dfs(vector<int>& candidates, int target, int cur){
if(cur == candidates.size()){
return ;
}
if(target == 0){
ans.push_back(tmp);
return ;
}
dfs(candidates, target, cur+1);
if(target - candidates[cur] >= 0){
tmp.push_back(candidates[cur]);
dfs(candidates, target-candidates[cur], cur);
tmp.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates, target, 0);
return ans;
}
};023: 电话号码的字母组合 17
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
class Solution {
public:
unordered_map<char,string>mp{
{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
{'6', "mno"}, {'7', "pqrs"},{'8', "tuv"},{'9', "wxyz"}
};
void dfs(vector<string>& res, string digits, int cur, string tmp){
if(cur == digits.size())res.push_back(tmp);
for(char ch : mp[digits[cur]]){
dfs(res, digits, cur+1, tmp+ch);
}
}
vector<string> letterCombinations(string digits) {
vector<string>res;
if(digits.empty())return res;
dfs(res, digits, 0, "");
return res;
}
};024: 目标和 494
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/target-sum
class Solution {
public:
int ans = 0;
void dfs(vector<int>&nums, int target, int cur, int sum){
if(cur == nums.size()){
if(sum == target)ans++;
return ;
}
dfs(nums, target, cur+1, sum+nums[cur]);
dfs(nums, target, cur+1, sum-nums[cur]);
}
int findTargetSumWays(vector<int>& nums, int target) {
dfs(nums,target,0,0);
return ans;
}
};025: 下一个排列 31
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation
class Solution {
public:
void nextPermutation(vector<int>& nums) {
next_permutation(nums.begin(),nums.end());
}
};026: 零钱兑换 322
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change
class Solution {
public:
vector<int>cnt;
int dfs(vector<int>&coins, int rem){
if(rem < 0)return -1;
if(rem == 0)return 0;
if(cnt[rem-1]!=0)return cnt[rem-1];
int mi = INT_MAX;
for(int x : coins){
int tmp = dfs(coins, rem-x);
if(tmp>=0 && tmp<mi){
mi = tmp+1;
}
}
cnt[rem-1] = mi==INT_MAX?-1:mi;
return cnt[rem-1];
}
int coinChange(vector<int>& coins, int amount) {
if(amount==0)return 0;
cnt.resize(amount);
return dfs(coins,amount);
}
};027: 岛屿数量 200
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
class Solution {
public:
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
void dfs(vector<vector<char>>& grid, int x, int y){
int n = grid.size(), m = grid[0].size();
grid[x][y] = '0';
for(int i = 0; i < 4; i++){
int nx = x+dx[i], ny = y+dy[i];
if(nx>=0&&nx<=n-1&&ny>=0&&ny<=m-1&&grid[nx][ny]=='1'){
dfs(grid,nx,ny);
}
}
}
int numIslands(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size();
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j]=='1'){
dfs(grid, i, j);
ans++;
}
}
}
return ans;
}
};028: 删除无效的括号 301
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-invalid-parentheses
class Solution {
public:
bool check(string s){ //判断序列是否合法
int cc = 0;
for(char ch : s){
if(ch=='(')cc++;
else if(ch==')'){
cc--;
if(cc<0){
return false;
}
}
}
return cc==0;
}
vector<string> removeInvalidParentheses(string s) {
vector<string>ans;
unordered_set<string>se;
se.insert(s);
//bfs每轮删一个括号直至出现合法字符串
while(1){
for(string x : se){
if(check(x))ans.push_back(x);
}
if(ans.size()>0)return ans;
unordered_set<string>nse;
for(string x : se){//枚举所有串
for(int i = 0; i < x.size(); i++){//枚举删哪个
if(i>0 && x[i]==x[i-1])continue;
if(x[i]=='(' || x[i]==')'){
nse.insert(x.substr(0,i)+x.substr(i+1,x.size()));
}
}
}
se = nse;
}
}
};029: 课程表 207
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/course-schedule
class Solution {
public:
vector<vector<int> >G;
vector<int>in;
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
G.resize(numCourses);
in.resize(numCourses);
for(auto x : prerequisites){
G[x[1]].push_back(x[0]);
in[x[0]]++;
}
queue<int>q;
for(int i = 0; i < numCourses; i++)
if(in[i]==0)q.push(i);
int cc = 0;
while(q.size()){
cc++;
int u = q.front(); q.pop();
for(int v : G[u]){
in[v]--;
if(in[v]==0)q.push(v);
}
}
return cc==numCourses;
}
};030: 除法求值 399
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
示例 1：
输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
示例 2：
输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出：[3.75000,0.40000,5.00000,0.20000]
示例 3：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-division
class Solution {
public:
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
//把出现的字符映射到数字
int n = 0;
unordered_map<string, int>var;
int m = equations.size();
for(int i = 0; i < m; i++){
if(var.find(equations[i][0])==var.end()){
var[equations[i][0]] = n++;
}
if(var.find(equations[i][1])==var.end()){
var[equations[i][1]] = n++;
}
}
//建图, n*n邻接矩阵
vector<vector<double>>G(n,vector<double>(n,-1.0));
for(int i = 0; i < m; i++){
int u = var[equations[i][0]], v = var[equations[i][1]];
G[u][v] = values[i];
G[v][u] = 1.0/values[i];
}
//floyed，处理出任意点对间的距离
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(G[i][k]>0&&G[k][j]>0){
G[i][j] = G[i][k]*G[k][j];
}
}
}
}
//处理题目询问
vector<double>ans;
for(auto q : queries){
double res = -1.0;
if(var.find(q[0])!=var.end() && var.find(q[1])!=var.end()){
int u = var[q[0]], v = var[q[1]];
if(G[u][v] > 0){
res = G[u][v];
}
}
ans.push_back(res);
}
return ans;
}
};031: 每日温度 739
请根据每日 气温 列表 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:
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/daily-temperatures
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int>ans(n);
stack<int>s;
for(int i = 0; i < n; i++){
while(s.size() && temperatures[i]>temperatures[s.top()]){
int pre = s.top() ;
ans[pre] = i-pre;
s.pop();
}
s.push(i);
}
return ans;
}
};032: 接雨水 42
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
stack<int>s;
int ans = 0;
for(int i = 0; i < n; i++){
while(s.size() && height[i]>height[s.top()]){
int t = s.top(); s.pop();
if(s.empty())break;
int left = s.top();
int curwid = i-left-1;
int curhei = min(height[left], height[i])-height[t];
ans += curwid*curhei;
}
s.push(i);
}
return ans;
}
};033: 最小栈 155
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
示例:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack
class MinStack {
public:
stack<int>stk, min_stk;
MinStack() {
min_stk.push(INT_MAX);
}
void push(int val) {
stk.push(val);
min_stk.push(min(min_stk.top(), val));
}
void pop() {
stk.pop();
min_stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return min_stk.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/034: 字符串解码 394
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-string
class Solution {
public:
string Todigit(string &s, int &cur){
string res = "";
while(isdigit(s[cur])){
res.push_back(s[cur++]);
}
return res;
}
string decodeString(string s) {
int len = s.size(), i;
stack<string>stk;
for(i = 0; i < len; i++){
char ch = s[i];
if(isdigit(ch)){
stk.push(Todigit(s,i));
i--;
}else if(isalpha(ch) || ch=='['){
stk.push(string(1,ch));
}else{
string tmp;
while(stk.top()!="["){
tmp += stk.top();
stk.pop();
}
stk.pop();
//reverse(tmp.begin(),tmp.end());
int pow = stoi(stk.top());
stk.pop();
string tt = "";
while(pow--)tt+=tmp;
stk.push(tt);
}
}
string ans = "";
while(stk.size()){
ans += stk.top(); stk.pop();
}
reverse(ans.begin(),ans.end());
return ans;
}
};035: 最大矩形 85
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。
示例 2：
输入：matrix = []
输出：0
示例 3：
输入：matrix = [["0"]]
输出：0
示例 4：
输入：matrix = [["1"]]
输出：1
示例 5：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-rectangle
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
if(m==0)return 0;
vector<vector<int> >left(m,vector<int>(n,0));
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(matrix[i][j]=='1'){
left[i][j] = (j==0?0:left[i][j-1])+1;
}
}
}
int res = 0;
for(int j = 0; j < n; j++){
vector<int>up(m,0), down(m, 0);
stack<int>stk;
for(int i = 0; i < m; i++){
while(!stk.empty() && left[stk.top()][j] >= left[i][j]){
stk.pop();
}
up[i] = stk.empty()?-1:stk.top();
stk.push(i);
}
stk = stack<int>();
for(int i = m-1; i>=0; i--){
while(!stk.empty() && left[stk.top()][j] >= left[i][j]){
stk.pop();
}
down[i] = stk.empty() ? m : stk.top();
stk.push(i);
}
for(int i = 0; i < m; i++){
int hei = down[i]-up[i]-1;
int area = hei*left[i][j];
res = max(res, area);
}
}
return res;
}
};036: 回文链表 234
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105] 内
来源：力扣（LeetCode）
链接：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) {
vector<int>vc;
while(head!=nullptr){
vc.push_back(head->val);
head = head->next;
}
for(int i = 0,j=vc.size()-1; i<j; i++,j--){
if(vc[i]!=vc[j]){
return false;
}
}
return true;
}
};037: 有效的括号 20
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
//遇到左括号就丢到栈里，遇到右括号就出栈判断是否匹配
class Solution {
public:
bool isValid(string s) {
stack<char>stk;
for(char ch : s){
if(ch=='('||ch=='['||ch=='{')stk.push(ch);
else{
if(stk.size()==0)return false;
char cc = stk.top();
if(cc=='('&&ch==')' || cc=='['&&ch==']' || cc=='{'&&ch=='}')stk.pop();
else return false;
}
}
return stk.size()==0;
}
};038: 柱状图中最大的矩形 84
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
提示：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int>left(n), right(n,n);//左侧,右侧最近的小于其高度的柱子
stack<int>stk;
for(int i = 0; i < n; i++){
while(stk.size() && heights[stk.top()] >= heights[i]){
right[stk.top()] = i; stk.pop();
}
left[i] = stk.size() ? stk.top() : -1;
stk.push(i);
}
int ans = 0;
for(int i = 0; i < n; i++){//枚举高度
ans = max(ans, (right[i]-left[i]-1)*heights[i]);
}
return ans;
}
};039: 最长有效括号 32
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
提示：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-valid-parentheses
class Solution {
public:
int longestValidParentheses(string s) {
int ans = 0;
stack<int>stk;
stk.push(-1);
for(int i = 0; i < s.size(); i++){
if(s[i]=='(')stk.push(i);
else{
stk.pop();
if(stk.empty()){
stk.push(i);
}else{
ans = max(ans, i-stk.top());
}
}
}
return ans;
}
};040: 反转链表 206
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-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:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr,* cur = head;
while(cur != nullptr){
ListNode * next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};041: 合并两个有序链表 21
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
/**
* 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* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr)return l2;
else if(l2 == nullptr)return l1;
else if(l1->val < l2->val){
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}else{
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};042: 排序链表 148
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-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* sortList(ListNode* head) {
if(head==nullptr || head->next==nullptr)return head;
ListNode* head1 = head;
ListNode* head2 = split(head);//一条链表分成两段分别递归
head1 = sortList(head1);
head2 = sortList(head2);
return mergr(head1, head2);
}
//双指针找单链表中点模板
ListNode* split(ListNode* head){
ListNode * l = head, *r = head->next;
while(r!=nullptr && r->next!=nullptr){
l = l->next;
r = r->next->next;
}
ListNode *mid = l->next;
l->next=nullptr;
return mid;
}
//合并两个排序链表模板
ListNode* mergr(ListNode* head1, ListNode* head2){
ListNode* tmp = new ListNode(0), *p = tmp;
while(head1!=nullptr && head2!=nullptr){
if(head1->val<head2->val){
p->next = head1;
p = p->next;
head1 = head1->next;
}else{
p = p->next = head2;
head2 = head2->next;
}
}
if(head1 != nullptr)p->next = head1;
if(head2 != nullptr)p->next = head2;
return tmp->next;
}
};043: 相交链表 160
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,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
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
/**
* 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) {
unordered_set<ListNode *> se;
ListNode* tmp = headA;
while(tmp != nullptr){
se.insert(tmp);
tmp = tmp->next;
}
tmp = headB;
while(tmp != nullptr){
if(se.count(tmp))return tmp;
tmp = tmp->next;
}
return nullptr;
}
};044: 合并K个升序链表 23
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= listsi <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
/**
* 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* merge(ListNode* a, ListNode* b){
if((!a)||(!b))return a? a : b;
ListNode head, *cur=&head, *i =a, *j=b;
while(i && j){
if(i->val < j->val){
cur->next = i;
i = i->next;
}else{
cur->next = j;
j = j->next;
}
cur = cur->next;
}
cur->next = (i?i:j);
return head.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* ans = nullptr;
for(int i = 0; i < lists.size(); i++){
ans = merge(ans, lists[i]);
}
return ans;
}
};045: 环形链表 II 142
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
/**
* 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) {
unordered_set<ListNode*>se;
while(head!=nullptr){
if(se.count(head))return head;
se.insert(head);
head = head->next;
}
return nullptr;
}
};046: LRU 缓存 146
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache
class LRUCache {
public:
struct node{
int key, val;
node * pre, *next;
node():key(0),val(0),pre(nullptr),next(nullptr){}
node(int _k, int _v):key(_k),val(_v),pre(nullptr),next(nullptr){}
};
unordered_map<int, node*>cache;
node *head, *tail;
int size, capacity;
void addToHead(node* t){
t->pre = head;
t->next = head->next;
head->next->pre = t;
head->next = t;
}
void removeNode(node* t){
t->pre->next = t->next;
t->next->pre = t->pre;
}
void moveToHead(node* t){
removeNode(t);
addToHead(t);
}
node* removeTail(){
node* t = tail->pre;
removeNode(t);
return t;
}
//主函数
LRUCache(int _capacity):capacity(_capacity),size(0){
head = new node();
tail = new node();
head->next = tail;
tail->pre = head;
}
int get(int key) {
if(!cache.count(key))return -1;
node * t = cache[key];
moveToHead(t); //定位后移动到双向链表头部
return t->val;
}
void put(int key, int value) {
if(!cache.count(key)){//不存在就新建
node* t = new node(key,value);
cache[key] = t;
addToHead(t); //添加到双向链表头部
size++;
if(size>capacity){//超出容量则删除尾部节点
node* re = removeTail();
cache.erase(re->key);
delete re;
size--;
}
}else{//存在就定位修改，然后移动到头部
node* t = cache[key];
t->val = value;
moveToHead(t);
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/047: 环形链表 141
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*>se;
while(head!=NULL){
if(se.count(head))return true;
se.insert(head);
head = head->next;
}
return false;
}
};048: 删除链表的倒数第 N 个结点 19
给你一个链表，删除链表的倒数第 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
//遍历一遍获得长度，删除第len-n+1个
/**
* 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:
int getlen(ListNode* head){
int cc = 0;
while(head != NULL){ cc++; head=head->next; }
return cc;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* res = new ListNode(0,head);//指向ans，防止空链表出现
int len = getlen(head);
ListNode* cur = res;
for(int i = 1; i < len-n+1; i++){
cur = cur->next;
}
cur->next = cur->next->next;
return res->next;
}
};049: 两数相加 2
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* l3 = new ListNode(-1);
ListNode* cur = l3;
int num = 0, jin = 0; //每位的和，进位
while(l1!=NULL || l2!=NULL){
num = 0;
if(l1 != NULL){
num += l1->val;
l1 = l1->next;
}
if(l2 != NULL){
num += l2->val;
l2 = l2->next;
}
if(jin)num++;
cur->next = new ListNode(num%10);
cur = cur->next;
if(num>=10)jin = 1;
else jin = 0;
}
if(jin){
cur->next = new ListNode(1);
}
return l3->next;
}
};050: 字母异位词分组 49
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示：
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/group-anagrams
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>>mp;
for(string s:strs){
string t = s;
sort(t.begin(),t.end());
mp[t].push_back(s);
}
vector<vector<string> >ans;
for(auto it = mp.begin(); it != mp.end(); it++){
ans.push_back(it->second);
}
return ans;
}
};051: 回文子串 647
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000
s 由小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindromic-substrings
class Solution {
public:
int countSubstrings(string s) {
int n = s.size(), ans = 0;
for(int i = 0; i < 2*n-1; i++){
int l = i/2, r = i/2+i%2;
while(l>=0&&r<n && s[l]==s[r]){
l--; r++; ans++;
}
}
return ans;
}
};052: 编辑距离 72
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/edit-distance
//题意：给出两个字符串a和b，将a通过删除，插入，替换变换成b，求最少操作次数。
//思路：f[i][j]表示将a[1~i]变成b[1~j]的最小操作次数，转移的时候分别考虑删除，插入和替换即可。
class Solution {
public:
int minDistance(string word1, string word2) {
word1 = "0"+word1; word2 = "0"+word2;
int n = word1.size(), m = word2.size();
int f[n+1][m+1];
memset(f,0,sizeof(f));
for(int i = 1; i <= n; i++)f[i][0] = i;//只能删除
for(int i = 1; i <= m; i++)f[0][i] = i;//只能插入
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);//删除a[i]或插入b[j]使之匹配, 次数+1
if(word1[i]==word2[j])f[i][j] = min(f[i][j],f[i-1][j-1]);//本来就相等
else f[i][j] = min(f[i][j],f[i-1][j-1]+1);//修改a[i]或b[j]
}
}
return f[n][m];
}
};053: 找到字符串中所有字母异位词 438
给定两个字符串 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 仅包含小写字母
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int slen = s.size(), plen = p.size();
if(slen<plen)return vector<int>();
//滑动窗口
vector<int>ans;
vector<int>scc(26), pcc(26);
for(int i = 0; i < plen; i++){
scc[s[i]-'a']++;
pcc[p[i]-'a']++;
}
if(scc==pcc)ans.push_back(0);
for(int i = 0; i < slen-plen; i++){
scc[s[i]-'a']--;
scc[s[i+plen]-'a']++;
if(scc==pcc){
ans.push_back(i+1);
}
}
return ans;
}
};054: 最小覆盖子串 76
给你一个字符串 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 <= 105
s 和 t 由英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
class Solution {
public:
unordered_map<char,int>z, cc;
bool check(){
for(auto p : z){
if(cc[p.first] < p.second){
return false;
}
}
return true;
}
string minWindow(string s, string t) {
for(char ch: t)z[ch]++;
int len = INT_MAX, ansl=-1,ansr=-1;
int l = 0, r = -1;
while(r < int(s.size())){
if(z.find(s[++r]) != z.end())cc[s[r]]++;
while(check() && l <= r){
if(r-l+1 < len){
len = r-l+1;
ansl = l;
}
if(z.find(s[l])!=z.end())cc[s[l]]--;
l++;
}
}
return ansl==-1?string():s.substr(ansl,len);
}
};055: 无重复字符的最长子串 3
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。示例 4:
输入: s = ""
输出: 0
提示：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int l = 0, r = 0, res = 0;
unordered_set<char>se;
se.insert(s[0]);
while(r < s.size()){
res = max(res, (int)se.size());
r++;
if(se.count(s[r])){
while(s[l]!=s[r]){ se.erase(s[l]); l++; }
se.erase(s[l]); l++;
}
se.insert(s[r]);
}
return res;
}
};056: 最长回文子串 5
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
class Solution {
public:
int p[2020];
string longestPalindrome(string s) {
string t="~#", ss;
for(int i=0; i<s.size(); i++)t=t+s[i]+'#';
int ans = 0, mid=0, r=0;
for(int i=1; i<t.size(); i++){
if(i<=r)p[i]=min(p[mid*2-i], r-i+1);
while(t[i-p[i]]==t[i+p[i]])p[i]++;
if(p[i]+i>r)r=p[i]+i-1, mid=i;
if(p[i]>ans){
ans=p[i];
ss = t.substr(mid-p[i]+1, 2*p[i]-1);
}
}
string sss="";
for(int i = 0; i < ss.size(); i++)
if(ss[i]!='#')sss+=ss[i];
return sss;
}
};057: 正则表达式匹配 10
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：
输入：s = "ab" p = ".*"
输出：true
解释："." 表示可匹配零个或多个（''）任意字符（'.'）。
示例 4：
输入：s = "aab" p = "cab"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5：
输入：s = "mississippi" p = "misisp*."
输出：false
提示：
1 <= s.length <= 20
1 <= p.length <= 30
s 只含小写英文字母。
p 只含小写英文字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching
//f[i][j]表示s的前i个能否被p的前j个匹配。
//转移若s[i]==p[j]则f[i][j]=f[i-1][j-1]. 否则若p[j]=.也可以匹配，若=*则再判断p[j-1]与s[i]的关系
class Solution {
public:
bool isMatch(string s, string p) {
s = " "+s; p = " "+p; //s,p可能为空
int n = s.size(), m = p.size();
bool f[n+1][m+1];
memset(f,false,(n+1)*(m+1));
f[0][0] = true;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(s[i-1]==p[j-1] || p[j-1]=='.'){
f[i][j] = f[i-1][j-1];
}
else if(p[j-1]=='*'){
if(p[j-2]!=s[i-1] && p[j-2]!='.'){//*找前一个，前一个匹配不上，再往前找
f[i][j] = f[i][j-2];
}else{ //匹配上了
f[i][j] = (f[i-1][j] || f[i][j-1] || f[i][j-2]);//多个字符,单个字符,没有匹配
}
}
}
}
return f[n][m];
}
};058: 戳气球 312
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] nums[i] nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 315 + 358 + 138 + 181 = 167
示例 2：
输入：nums = [1,5]
输出：10
提示：
n == nums.length
1 <= n <= 500
0 <= nums[i] <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/burst-balloons
class Solution {
public:
vector<vector<int>>dp;
vector<int>val;
int dfs(int l, int r){//区间(l,r)能获得的最大价值
if(l+1>=r)return 0;
if(dp[l][r]!=-1)return dp[l][r];
for(int i = l+1; i < r; i++){
int sum = val[l]*val[i]*val[r];
sum += dfs(l,i)+dfs(i,r);
dp[l][r] = max(dp[l][r], sum);
}
return dp[l][r];
}
int maxCoins(vector<int>& nums) {
int n = nums.size();
val.resize(n+2);
val[0] = val[n+1] = 1;
for(int i = 1; i <= n; i++)val[i]=nums[i-1];
dp.resize(n+2,vector<int>(n+2,-1));
return dfs(0,n+1);
}
};059: 最佳买卖股票时机含冷冻期 309
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
提示：
1 <= prices.length <= 5000
0 <= prices[i] <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()==0)return 0;
//f[i]到第i天为止的最大收益。
//0,1,2分别表示当前手上持有股票,不持有股票且明天为冷冻期,不持有且明天不是冷冻期
int n = prices.size();
vector<vector<int> >f(n, vector<int>(3));
f[0][0] = -prices[0];
for(int i = 1; i < n; i++){
f[i][0] = max(f[i-1][0], f[i-1][2]-prices[i]);
f[i][1] = f[i-1][0]+prices[i];
f[i][2] = max(f[i-1][1], f[i-1][2]);
}
return max(f[n-1][1], f[n-1][2]);
}
};060: 最大子数组和 53
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//以i结尾的连续子数组的最大和，f[i] = max{a[i], f[i-1]+a[i]}, res取max{f[i]}即可
int f = 0, res = nums[0];
for(int x : nums){
f = max(f+x, x);
res = max(res, f);
}
return res;
}
};061: 最长连续序列 128
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-consecutive-sequence
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int>se;
for(int x: nums)se.insert(x);
int ans = 0;
for(int x : se){
if(!se.count(x-1)){
int cur = x, cc = 1;
while(se.count(cur+1))cur++,cc++;
ans = max(ans, cc);
}
}
return ans;
}
};062: 最长递增子序列 300
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
进阶：
你可以设计时间复杂度为 O(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n==0)return 0;
//dp[i], 以i结尾的LIS
vector<int>dp(n,0);
for(int i = 0; i < n; i++){
dp[i] = 1;
for(int j = 0; j < i; j++){
if(nums[j]<nums[i]){
dp[i] = max(dp[i],dp[j]+1);
}
}
}
return *max_element(dp.begin(),dp.end());
}
};063: 打家劫舍 198
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 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 。
提示：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber
class Solution {
public:
int rob(vector<int>& nums) {
//f[i]表示前i间能获得的最大值
int n = nums.size();
if(n==0)return 0;
if(n==1)return nums[0];
vector<int>f(n,0);
f[0] = nums[0], f[1] = max(nums[0],nums[1]);
for(int i = 2; i < n; i++){
f[i] = max(f[i-2]+nums[i], f[i-1]);
}
return f[n-1];
}
};064: 分割等和子集 416
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
if(n < 2)return false;
int sum = accumulate(nums.begin(),nums.end(),0);
int mx = *max_element(nums.begin(),nums.end());
if(sum%2==1)return false; //奇数不可能
int target = sum/2;
if(mx > target)return false;//最大值>目标,不可能
//f[i][j]: 前i个数能否选出j
vector<vector<int>>f(n,vector<int>(target+1,0));
for(int i = 0; i < n; i++)f[i][0] = 1;
f[0][nums[0]] = 1;
for(int i = 1; i < n; i++){
int num = nums[i];
for(int j = 1; j <= target; j++){
if(j >= num){
f[i][j] = f[i-1][j]|f[i-1][j-num];
}else{
f[i][j] = f[i-1][j];
}
}
}
return f[n-1][target];
}
};065: 乘积最大子数组 152
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
class Solution {
public:
int maxProduct(vector<int>& nums) {
//f1,f2:以第i个数结尾的乘积最大，最小的子数组乘积。
//最小的对应负数的情况，负负得正。
vector<int>f1(nums), f2(nums);
for(int i = 1; i < nums.size(); i++){
f1[i] = max(f1[i-1]*nums[i], max(nums[i],f2[i-1]*nums[i]));
f2[i] = min(f2[i-1]*nums[i], min(nums[i],f1[i-1]*nums[i]));
}
return *max_element(f1.begin(),f1.end());
}
};066: 搜索旋转排序数组 33
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
if(n==0)return -1;
if(n==1)return nums[0]==target?0:-1;
int l = 0, r = n-1;
while(l <= r){
int mid = (l+r)/2;
if(nums[mid]==target)return mid;
if(nums[mid]>=nums[0]){//分割线左边
if(nums[0]<=target&&target<nums[mid]){
r = mid-1;
}else{
l = mid+1;
}
}else{//分割线右边
if(nums[mid]<target&&target<=nums[n-1]){
l = mid+1;
}else{
r = mid-1;
}
}
}
return -1;
}
};067: 在排序数组中查找元素的第一个和最后一个位置 34
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size()==0)return vector<int>{-1,-1};
int n = nums.size();
int l = lower_bound(nums.begin(),nums.end(),target)-nums.begin();
int r = upper_bound(nums.begin(),nums.end(),target)-nums.begin();
vector<int>ans;
ans.push_back((l<=n-1&&nums[l]==target ? l : -1));
ans.push_back((r>=1&&nums[r-1]==target ? r-1 : -1));
return ans;
}
};068: 寻找两个正序数组的中位数 4
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
//思路：首先不难想到合并两个序列后中位数就是a[len/2], 所以问题转为求两个序列中第k大的值，可以二分。
class Solution {
public:
int getKth(const vector<int>& nums1, vector<int>& nums2, int k){
int n = nums1.size(), m = nums2.size();
int i = 0, j = 0;
while(1){
if(i==n)return nums2[j+k-1];
if(j==m)return nums1[i+k-1];
if(k==1)return min(nums1[i], nums2[j]);
int ni = min(i+k/2-1, n-1), nj = min(j+k/2-1,m-1);//在有效序列中找第k/2+k/2大，加起来不会超过k个数
if(nums1[ni] <= nums2[nj]){
k -= ni-i+1; //a[i,ni]这些数都<b[nj],所以不要了,接着找剩下的k大
i = ni+1; //更新i的位置为当前有效序列的ni+1
}else{
k -= nj-j+1;
j = nj+1;
}
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len = nums1.size()+nums2.size();
if(len%2==1){
return getKth(nums1,nums2, (len+1)/2);
}else{
return (getKth(nums1,nums2,len/2)+getKth(nums1,nums2,len/2+1))/2.0;//WA
}
}
};069: 数组中的第K个最大元素 215
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
提示：
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
通过次数513,392提交次数793,865
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
sort(nums.begin(),nums.end());
return nums[n-k];
}
};070: 移动零 283
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
进阶：你能尽量减少完成的操作次数吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int l = 0, r = 0;
while(r < n){
if(nums[r]!=0){
swap(nums[r],nums[l]);
l++;
}
r++;
}
}
};071: 前 K 个高频元素 347
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements
class Solution {
public:
static bool cmp(pair<int, int> m, pair<int, int> n){
return m.second > n.second;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int>ma;
for(auto x : nums)ma[x]++;
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)>q(cmp);
for(auto& [num, count] : ma){
if(q.size()==k){
if(q.top().second<count){
q.pop();
q.push(make_pair(num,count));
}
}else{
q.push(make_pair(num,count));
}
}
vector<int>res;
while(q.size()){
res.push_back(q.top().first);
q.pop();
}
return res;
}
};072: 盛最多水的容器 11
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
示例 3：
输入：height = [4,3,2,1,4]
输出：16
示例 4：
输入：height = [1,2,1]
输出：2
提示：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = height.size()-1;
int ans = 0;
while(l < r){
int area = min(height[l],height[r])*(r-l);
ans = max(ans, area);
if(height[l] <= height[r]){//贪心，移动小的更优
l++;
}else{
r--;
}
}
return ans;
}
};073: 颜色分类 75
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
提示：
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
//统计0,1,2个数，扫两趟即可
class Solution {
public:
void sortColors(vector<int>& nums) {
int a = 0, b = 0, c = 0;
for(int x : nums){
if(x==0)a++;
if(x==1)b++;
if(x==2)c++;
}
for(int i = 0; i < a; i++){
nums[i] = 0;
}
for(int i = a; i < a+b; i++){
nums[i] = 1;
}
for(int i = a+b; i < a+b+c; i++){
nums[i] = 2;
}
}
};074: 最短无序连续子数组 581
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
示例 1：
输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
示例 2：
输入：nums = [1,2,3,4]
输出：0
示例 3：
输入：nums = [1]
输出：0
提示：
1 <= nums.length <= 104
-105 <= nums[i] <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
if(is_sorted(nums.begin(),nums.end()))return 0;
vector<int>a(nums);
sort(a.begin(),a.end());
int left = 0;
while(nums[left] == a[left])left++;
int right = nums.size()-1;
while(nums[right]==a[right])right--;
return right-left+1;
}
};075: 三数之和 15
给你一个包含 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(),nums.end());
vector<vector<int>>ans;
for(int l = 0; l < n; l++){
if(l>0 && nums[l]==nums[l-1])continue;//需要和上次的数不同
int ed = n-1;
int v = -nums[l];
for(int r = l+1; r < n; r++){
if(r>l+1 && nums[r]==nums[r-1])continue;
while(r<ed && nums[r]+nums[ed]>v)ed--;
if(r==ed)break;
if(nums[r]+nums[ed]==v){
ans.push_back({nums[l],nums[r],nums[ed]});
}
}
}
return ans;
}
};076: 根据身高重建队列 406
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 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 <= hi <= 106
0 <= ki < people.length
题目数据确保队列可以被重建
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height
class Solution {
public:
//按照身高降序，人数升序排。对于已经拍排好的i-1个人，放入第i个人结果不会改变。
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(),people.end(), [](const vector<int>&u, const vector<int>&v){
return u[0]>v[0] || (u[0]==v[0]&&u[1]<v[1]);
});
vector<vector<int>> ans;
for(const vector<int> human: people){
ans.insert(ans.begin()+human[1], human);
}
return ans;
}
};077: 除自身以外数组的乘积 238
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
提示：
2 <= nums.length <= 105
-30 <= nums[i] <= 30
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/product-of-array-except-self
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
vector<int>L(len,0), R(len,0);
vector<int>ans(len);
L[0] = 1;
for(int i = 1; i < len; i++){
L[i] = L[i-1]*nums[i-1];
}
R[len-1] = 1;
for(int i = len-2; i>= 0; i--){
R[i] = R[i+1]*nums[i+1];
}
for(int i = 0; i < len; i++){
ans[i] = L[i]*R[i];
}
return ans;
}
};078: 多数元素 169
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3]
输出：3
示例 2：
输入：[2,2,1,1,1,2,2]
输出：2
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element
class Solution {
public:
int majorityElement(vector<int>& nums) {
int x = -1, cc = 0;
for(int num : nums){
if(num==x)cc++;
else cc--;
if(cc < 0){
x = num;
cc = 1;
}
}
return x;
}
};079: 找到所有数组中消失的数字 448
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]
示例 2：
输入：nums = [1,1]
输出：[2]
提示：
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
unordered_set<int>se;
for(int x : nums)se.insert(x);
vector<int>res;
for(int i = 1; i <= nums.size(); i++){
if(!se.count(i)){
res.push_back(i);
}
}
return res;
}
};080: 任务调度器 621
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
示例 1：
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。 示例 2：
输入：tasks = ["A","A","A","B","B","B"], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
诸如此类
示例 3：
输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案是：
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A
提示：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/task-scheduler
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
unordered_map<char,int>ma;
for(char ch : tasks){
ma[ch]++;
}
int mxval = max_element(ma.begin(),ma.end(), [](const auto& u, const auto& v){
return u.second<v.second;
})->second;
int mxcc = accumulate(ma.begin(), ma.end(), 0, [=](int acc, const auto& u) {
return acc + (u.second == mxval);
});
return max((mxval - 1) * (n + 1) + mxcc, static_cast<int>(tasks.size()));
}
};081: 买卖股票的最佳时机 121
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
class Solution {
public:
int maxProfit(vector<int>& prices) {
int mi = 1e9, mx = 0;
for(int x : prices){
mx = max(mx, x-mi);
mi = min(mi, x);
}
return mx;
}
};082: 两数之和 1
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
if(nums[i]+nums[j]==target){
ans.push_back(i);
ans.push_back(j);
return ans;
}
}
}
return ans;
}
};083: 会议室 II 253
plus权限题084: 滑动窗口最大值 239
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
priority_queue<pair<int,int> >q;
for(int i = 0; i < k; i++){
q.push(make_pair(nums[i],i));
}
vector<int>ans = {q.top().first};
for(int i = k; i < n; i++){
q.push(make_pair(nums[i],i));
while(q.top().second<=i-k)q.pop();
ans.push_back(q.top().first);
}
return ans;
}
};085: 合并区间 56
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()==0)return {};
sort(intervals.begin(),intervals.end());
vector<vector<int>>ans;
for(int i = 0; i < intervals.size(); i++){
int l = intervals[i][0], r = intervals[i][1];
if(ans.size()==0 || ans.back()[1]<l){
ans.push_back({l,r});
}else{
ans.back()[1] = max(ans.back()[1],r);
}
}
return ans;
}
};086: 和为 K 的子数组 560
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
提示：
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int>mp;
mp[0] = 1;
int cnt = 0, pre = 0;
for(int x : nums){
pre += x;
if(mp.find(pre-k)!=mp.end()){
cnt += mp[pre-k];
}
mp[pre]++;
}
return cnt;
}
};087: 跳跃游戏 55
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int mxr = 0;
for(int i = 0; i < n; i++){
if(i<=mxr){
mxr = max(mxr, i+nums[i]);
}
if(mxr >= n-1)return true;
}
return false;
}
};088: 不同路径 62
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>>f(m, vector<int>(n));
for(int i = 0; i < m; i++)f[i][0] = 1;
for(int i = 0; i < n; i++)f[0][i] = 1;
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
f[i][j] = f[i-1][j]+f[i][j-1];//上面或左边的方案
}
}
return f[m-1][n-1];
}
};089: 完全平方数 279
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
提示：
1 <= n <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-squares
class Solution {
public:
int numSquares(int n) {
//f[i]: i最少需要多少个数的平方来表示
vector<int>f(n+1);
for(int i = 1; i <= n; i++){
int mi = INT_MAX;
for(int j = 1; j*j<=i; j++){
mi = min(mi, f[i-j*j]);
}
f[i] = mi+1;
}
return f[n];
}
};090: 爬楼梯 70
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
提示：
1 <= n <= 45
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
class Solution {
public:
int climbStairs(int n) {
if(n<=2)return n;
int f[n+1];
f[1] = 1; f[2] = 2;//到第一级的方案数为1
for(int i = 3; i <= n; i++){
f[i] = f[i-1]+f[i-2];//可以从前一级或者前两级爬上来
}
return f[n];
}
};091: 旋转图像 48
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
提示：
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrixi <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-image
//不难发现a[i][j]移动到了a[j][n-i-1]
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
auto res = matrix;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
res[j][n-i-1] = matrix[i][j];
matrix = res;
}
};092: 最小路径和 64
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= gridi <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
//从上面或者左边走过来，加上自己的：f[i][j] = min(f[i-1][j], f[i][j-1])+grid[i][j];
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.size()==0 || grid[0].size()==0)return 0;
int n = grid.size(), m = grid[0].size();
int f[n+1][m+1];
f[0][0] = grid[0][0];
for(int i = 1; i < n; i++)f[i][0]=f[i-1][0]+grid[i][0];//第一列
for(int i = 1; i < m; i++)f[0][i]=f[0][i-1]+grid[0][i];//第一行
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
f[i][j] = min(f[i-1][j], f[i][j-1])+grid[i][j];
}
}
return f[n-1][m-1];
}
};093: 搜索二维矩阵 II 240
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
提示：
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrixi <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for(const auto& row : matrix){
auto it = lower_bound(row.begin(),row.end(),target);
if(it!=row.end() && *it==target){
return true;
}
}
return false;
}
};094: 最大正方形 221
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
示例 2：
输入：matrix = [["0","1"],["1","0"]]
输出：1
示例 3：
输入：matrix = [["0"]]
输出：0
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrixi 为 '0' 或 '1'
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
//f[i][j]:以(i,j)为右下角只含1的最大正方形边长
int n = matrix.size(), m = matrix[0].size();
if(n==0 || m==0)return 0;
int res = 0;
vector<vector<int>>f(n,vector<int>(m));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(matrix[i][j] == '1'){
if(i==0||j==0)f[i][j] = 1;
else f[i][j] = min(min(f[i-1][j],f[i][j-1]), f[i-1][j-1])+1;
res = max(res, f[i][j]);
}else{
f[i][j] = 0;
}
}
}
return res*res;
}
};095: 单词搜索 79
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
提示：
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search
class Solution {
public:
//check(i,j,k)表示从(i,j)出发，能否搜索到单词word[k..n]
bool check(vector<vector<char>>&board, string& word, vector<vector<int>>&vis, int i, int j, int k){
int n = board.size(), m = board[0].size();
if(board[i][j] != word[k])return false;
else if(k==word.size()-1)return true;
vis[i][j] = true;
vector<pair<int,int> >d{{0,1},{0,-1},{1,0},{-1,0}};
bool ok = false;
for(auto dd : d){
int ni = i+dd.first, nj = j+dd.second;
if(ni>=0&&ni<n&&nj>=0&&nj<m&&!vis[ni][nj]){
if(check(board,word,vis,ni,nj,k+1)){
ok = true;
break;
}
}
}
vis[i][j] = false;
return ok;
}
bool exist(vector<vector<char>>& board, string word) {
int n = board.size(), m = board[0].size();
vector<vector<int>> vis(n, vector<int>(m));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(check(board,word,vis,i,j,0)){
return true;
}
}
}
return false;
}
};096: 汉明距离 461
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例 1：
输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑上面的箭头指出了对应二进制位不同的位置。
示例 2：
输入：x = 3, y = 1
输出：1
提示：
0 <= x, y <= 231 - 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hamming-distance
class Solution {
public:
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
};097: 子集 78
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets
//dfs每个数选或不选
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size();
vector<vector<int> > ans;
vector<int>tmp;
for(int i = 0; i < (1<<n); i++){
tmp.clear();
for(int j = 0; j < n; j++){
if(i&(1<<j)){
tmp.push_back(nums[j]);
}
}
ans.push_back(tmp);
}
return ans;
}
};098: 比特位计数 338
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 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 <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/counting-bits
class Solution {
public:
vector<int> countBits(int n) {
vector<int>ans;
for(int i = 0; i <= n; i++){
ans.push_back(__builtin_popcount(i));
}
return ans;
}
};099: 只出现一次的数字 136
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number
//相同的数异或为0，所有数异或一下即可
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(int x:nums)res ^= x;
return res;
}
};100: 寻找重复数 287
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
示例 3：
输入：nums = [1,1]
输出：1
示例 4：
输入：nums = [1,1,2]
输出：1
提示：
1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-duplicate-number
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size(), ans = 0;
for(int i = 0; i <= 31; i++){
int x = 0, y = 0;
for(int j = 0; j < n; j++){
if(nums[j]&(1<<i))x++;
if(j>=1&& (j&(1<<i)) )y++;
}
if(x > y)ans |= 1<<i;
}
return ans;
}
};