坚持 练习 谨慎
梦想开始的地方
题解来源https://leetcode-cn.com https://leetcode.com算法书籍以及自己的思考和
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int>twos;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
if(nums[i]+nums[j]==target){
twos.push_back(i);
twos .push_back(j);
}
}
}
return twos;
}
};
树
遍历：安照某种次序吧所有结点都访问一遍
二叉树的遍历
二叉树的递归特性
先序遍历（先根遍历）根左右
中序遍历（中根遍历）左根右
后序遍历（后根遍历）左右根
/**
* 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:
void inorder(TreeNode* root ,vector<int>& res){
//递归终止条件 结点为空返回
if(!root){
return;
}
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root,res);
return res;
}
};非递归
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
//非递归写法 用栈
vector<int> res;
stack<TreeNode*> s;
TreeNode* p = root;
while(p||!s.empty()){
if(p){
s.push(p);//结点入栈
p=p->left;//访问结点的左孩子，直到左孩子为空
}
else{
res.push_back(s.top()->val);//在结点为空的时候开始访问栈顶元素
p = s.top()->right;//访问栈顶元素的右孩子
s.pop();//弹出栈顶元素
}
}
return res;
}
};二叉树的前序遍历
递归
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
class Solution {
public:
void preorder(TreeNode* root ,vector<int>& res){
//递归终止条件 结点为空 返回
if(!root){
return;
}
res.push_back(root->val);
preorder(root->left,res);
preorder(root->right,res);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preorder(root,res);
return res;
}
};非递归
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
//非递归写法 用栈
stack<TreeNode*> s;
vector<int> res;
TreeNode* p = root;
while(p||!s.empty()){
if(p){
res.push_back(p->val);//访问结点
s.push(p);//访问后结点入栈，为了访问结点的左右孩子
p = p->left;//先访问左孩子
}
else{//如果结点的左孩子为空，因为结点已经在栈中。
p = s.top()->right;//访问栈顶元素的右孩子
s.pop();//弹出栈顶元素
}
}
return res;
}
};二叉树的后序遍历
递归
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
class Solution {
public:
void postorder(TreeNode* root,vector<int>& res){
//递归终止条件 结点为空返回
if(!root){
return;
}
postorder(root->left,res);
postorder(root->right,res);
res.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
postorder(root,res);
return res;
}
};非递归
算法思想：
A
/ \
B C
/ \
D E
后序非递归遍历二叉树是先访问左子树，再访问右子树,最后访问根节点
结合上图分析
①沿着根的左孩子，依次入栈，直到左孩子为空。
此时栈内元素依次为ABD。
②读栈顶元素：若其右孩子不为空且未被访问过，将右子树子树转执行①；否则，栈顶元素出栈并访问。
栈顶D的右孩子为空，出栈并访问，它是后序序列的第一个结点；栈顶B的右孩子不为空且未被访问过，E入栈，栈顶E的左右孩子均为空，出栈并访问；栈顶B的右孩子不为空单以被访问，B出栈并访问；栈顶A的右孩子不为空且未被访问过，C入栈，栈顶C的左右孩子均为空，出栈并访问；栈顶A的右孩子不为空但已被访问，A出栈并访问。由此得到后序序列
DEBCA
在第②步中，必须分清楚返回时是从左子树返回还是右子树返回的，因此可以设定一个辅助指针r,指向最近访问过的结点。也可以在结点中增加一个标识域，记录是否已经被访问。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
//非递归写法 用栈和一个标记指针标记访问过的元素
stack<TreeNode*> s;
TreeNode* p = root;
TreeNode* r = nullptr;
vector<int> res;
while(p||!s.empty()){
if(p){//走到最左边
s.push(p);//结点入栈
p=p->left;//访问结点左孩子
}
else{//向右
//读栈顶元素的右孩子（非出栈）
//若右子树存在，且未被访问过
if(s.top()->right&& s.top()->right!=r)
p = s.top()->right;//转向右
else{//如果结点的右孩子不存在或者已经访问过了
res.push_back(s.top()->val);//访问结点
r=s.top();//记录最近访问过的结点
s.top()=nullptr // 避免重复访问左子树[设空节点] 也可以不写
s.pop();
}
}
}
return res;
}
};二叉树的层序遍历
class Solution {
private:
vector<vector<int>> res;
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;//使用队列存储结点 队列先进先出的特性满足了树层 从上到下 从左到右 的访问方式
if(root!=nullptr) q.push(root);
while(!q.empty()){
int n = q.size();//每一层循环次数
vector<int> leval;
for(int i=0;i<n;i++){
//q.front() 队列的头元素
leval.push_back(q.front()->val);
if(q.front()->left!=nullptr) q.push(q.front()->left);
if(q.front()->right!=nullptr) q.push(q.front()->right);
q.pop();
//访问完头元素以后，弹出头元素
}
res.push_back(leval);
}
return res;
}
};二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==nullptr)//递归的终止条件 结点为空
return 0;//返回0
//如果结点不为空
//返回结点左右子树中深度最大的子树的高度加1
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};* 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
深度优先搜索
class Solution {
public:
int minDepth(TreeNode* root) {
//如果结点为空
if(root==nullptr){
return 0;
}
//递归终止条件
if(root->left==nullptr&&root->right==nullptr){
return 1;
}
int min_depth = INT_MAX;//二叉树的最小深度
// 如果左子树不为空
if(root->left!=nullptr){
min_depth = min(min_depth,minDepth(root->left));
}
// 如果右子树不为空
if(root->right!=nullptr){
min_depth = min(min_depth,minDepth(root->right));
}
// 如果左右子树都为空
return min_depth+1;
}
};关键：
叶子节点的定义是没有子节点的节点，即左孩子和右孩子都为nullptr时叫做叶子节点，如果只有一个孩子节点为空节点的节点不是叶子节点。
当root节点左右孩子都为空时，返回1
当root节点左右孩子有一个为空，一个不为空时，返回不为空的孩子节点的深度
当root节点左右孩子都不为空时，返回左右孩子较小深度的节点值
class Solution {
public:
int minDepth(TreeNode* root) {
if(root==nullptr)
return 0;
//当root节点左右孩子都为空时，返回1
if(root->left==nullptr&&root->right==nullptr)
return 1;
//左孩子的最小深度
int ld=minDepth(root->left);
//右孩子的最小深度
int rd=minDepth(root->right);
//这里其中一个节点为空，说明ld、rd有一个然为0，所以可以返回 ld+rd+ 1;
if(root->left==nullptr||root->right==nullptr)
return ld+rd+1;
//左右孩子都不为空
return min(ld,rd)+1;
}
};* 二叉树的所有路径
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
class Solution {
public:
void findPath(TreeNode* root, string path,vector<string>& paths){
if(root == nullptr){
return;
}
path+=to_string(root->val);
if(root->left==nullptr&&root->right==nullptr){
paths.push_back(path);
}
else{
path+="->";
findPath(root->left,path,paths);
findPath(root->right,path,paths);
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> paths;
findPath(root,"",paths);
return paths;
}
};
二叉树的层平均值
在二叉树的层序遍历基础上加上求和取平均值
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> res;
queue<TreeNode*> q;
if(root!=nullptr) q.push(root);
while(!q.empty()){
int n=q.size();//循环次数
double levelSum = 0;
for(int i=0;i<n;i++){
TreeNode* cur = q.front();
q.pop();
levelSum+=cur->val;
if(cur->left!=nullptr) q.push(cur->left);
if(cur->right!=nullptr) q.push(cur->right);
}
res.push_back((double)levelSum/n);
}
return res;
}
};二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
思路：
任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到
class Solution {
public:
int ans =0;
int deeth(TreeNode* root){
if(root ==nullptr){
return 0;
}
int leftd = deeth(root->left);
int rightd = deeth(root->right);
ans = max(ans,leftd+rightd);
return max(leftd,rightd)+1;
}
int diameterOfBinaryTree(TreeNode* root) {
deeth(root);
return ans;
}
};二叉搜索树中的众数
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
暴力解法
class Solution {
public:
void inorder(TreeNode* root ,vector<int>& res){
if(!root){
return;
}
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
bool static cmp(const pair<int, int>& a, const pair<int, int>& b){
return a.second>b.second;
}
vector<int> findMode(TreeNode* root) {
vector<int>res;
inorder(root,res);
//用来记录每个数的出现次数
unordered_map <int,int> map;
for(int e:res){
map[e]++;
}
vector<int> result;
if (root == nullptr) return result;
vector<pair<int, int>> vec(map.begin(), map.end());
//排序
sort(vec.begin(), vec.end(), cmp);
//因为众数可能有多个
result.push_back(vec[0].first);
for (int i = 1; i < vec.size(); i++) {
if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
else break;
}
return result;
}
};利用二叉搜索树的性质
二叉搜索树的中序遍历为一个递增序列
class Solution {
public:
int count;
int maxcount;
int base;
void update(int e,vector<int>& re){
if(e==base){
count++;
}
else{
count = 1;
base = e;
}
//记录出现最多的书
if(count>maxcount){
maxcount=count;
re.clear();
re.push_back(e);
}
//如果出现多个众数的情况
else if(count == maxcount){
re.push_back(e);
}
}
void inorder(TreeNode* root ,vector<int>& re){
if(!root){
return;
}
inorder(root->left,re);
update(root->val,re);
inorder(root->right,re);
}
vector<int> findMode(TreeNode* root) {
vector<int> re;
if(root==nullptr) return re ;
inorder(root,re);
return re;
}
};二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
利用二叉搜索树中序遍历是一个递增序列的性质
class Solution {
public:
//注意pre传的是引用
void dfs(TreeNode* root,int& pre,int& ans){
if(root==nullptr){
return;
}
//将左子树一搜到底
dfs(root->left,pre,ans);
if(pre==-1){//第一个结点
pre=root->val;
}
else{
ans = min(ans,root->val-pre);
pre=root->val;
}
dfs(root->right,pre,ans);
}
int getMinimumDifference(TreeNode* root) {
int ans = INT_MAX;
int pre=-1;
dfs(root,pre,ans);
return ans;
}
};
二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
6
/ \
2 8
/ \ / \
0 4 7 9
/ \
3 5
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。利用好二叉搜索树的性质
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//递归终止条件
if(root==NULL)
return NULL;
//如果p q的值都小于根结点 则p q的最近公共祖先在根结点的左子树
//递归调用左子树
if(p->val<root->val&&q->val<root->val)
return lowestCommonAncestor(root->left,p,q);
//如果p q的值都大于根结点 则p q的最近公共祖先在根结点的右子树
//递归调用右子树
if(p->val>root->val&&q->val>root->val)
return lowestCommonAncestor(root->right,p,q);
//否则，一左一右 则是它们的最近公共祖先
return root;
}
};二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
class Solution {
public:
TreeNode *searchBST(TreeNode *root, int val) {
if (root == nullptr) {
return nullptr;
}
//如果找到 直接返回
if (val == root->val) {
return root;
}
//利用二叉搜索树的性质 进行递归
return searchBST(val < root->val ? root->left : root->right, val);
}
};将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
class Solution {
private:
TreeNode* helper(vector<int>&nums,int left,int right){
if(left>right)
return nullptr;
int mid = (left+right+1)/2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = helper(nums,left,mid-1);
root->right = helper(nums,mid+1,right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums,0,nums.size()-1);
}
};两数之和 IV - 输入 BST
给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
中序遍历
双指针
class Solution {
public:
void preorder(TreeNode* root,vector<int>& res){
if(!root)
return;
preorder(root->left,res);
res.push_back(root->val);
preorder(root->right,res);
}
bool findTarget(TreeNode* root, int k) {
vector<int> res;
preorder(root,res);
int left=0;
int right=res.size()-1;
while(left<right){
if((res[left]+res[right])==k){
return true;
}
if((res[left]+res[right])>k){
right--;
}
else{
left++;
}
}
return false;
}
};翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr)
return nullptr;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};合并二叉树
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
class Solution {
private:
TreeNode* merge(TreeNode* root1, TreeNode* root2) {
if(root1==nullptr) return root2;
if(root2==nullptr) return root1;
TreeNode* newmerge = new TreeNode(root1->val+root2->val);
newmerge->left = merge(root1->left,root2->left);
newmerge->right = merge(root1->right,root2->right);
return newmerge;
}
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
return merge(root1,root2);
}
};平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
class Solution {
public:
int height(TreeNode* root){
if(root==nullptr){
return 0;
}
else {
return max(height(root->left),height(root->right))+1;
}
}
bool isBalanced(TreeNode* root) {
if(root==nullptr){
return true;
}
else{
return abs(height(root->left)-height(root->right))<=1&&
isBalanced(root->left)&&isBalanced(root->right);
}
}
};对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
class Solution {
private:
bool ismirro(TreeNode*Rroot,TreeNode*Lroot){
if(Rroot==nullptr&&Lroot==nullptr)
return true;
if(Rroot==nullptr||Lroot==nullptr)
return false;
return Rroot->val ==Lroot->val &&ismirro(Rroot->left,Lroot->right)
&&ismirro(Rroot->right,Lroot->left);
}
public:
bool isSymmetric(TreeNode* root) {
return ismirro(root,root);
}
};另一棵树的子树
class Solution {
public:
bool check(TreeNode* rt,TreeNode* sub){
if(rt==nullptr&&sub==nullptr) return true;
if((rt==nullptr&&sub!=nullptr)||(rt!=nullptr&&sub==nullptr)||rt->val!=sub->val){
return false;
}
return check(rt->left,sub->left)&&check(rt->right,sub->right);
}
bool dfs(TreeNode* rt,TreeNode* sub){
if(rt==nullptr){
return false;
}
return check(rt,sub)||dfs(rt->left,sub)||dfs(rt->right,sub);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
return dfs(root,subRoot);
}
};根据二叉树创建字符串
class Solution {
public:
string tree2str(TreeNode* root) {
//递归终止条件
if(root==nullptr)
return "";
//左子树和右子树都为空
if(root->left==nullptr&&root->right==nullptr)
return to_string(root->val)+"";
//只有左子树，右子树为空
if(root->right==nullptr){
return to_string(root->val)+"("+tree2str(root->left)+")";
}
//左子树为空，只有右子树
//左右子树都有
return to_string(root->val)+
"("+tree2str(root->left)+")("+tree2str(root->right)
+")";
}
};左叶子之和
class Solution {
int leftLeavesSum=0;
void leftLeaves(TreeNode* root){
if(root==nullptr)
return ;
//判断是否是左叶子
if(root->left!=nullptr){
if((root->left)->left==nullptr&&(root->left)->right==nullptr){
leftLeavesSum+=(root->left)->val;
}
}
leftLeaves(root->left);
leftLeaves(root->right);
}
public:
int sumOfLeftLeaves(TreeNode* root) {
leftLeaves(root);
return leftLeavesSum;
}
};
路径总和
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root==nullptr)
return false;
if(root->left==nullptr&&root->right==nullptr)
return targetSum==root->val;
return hasPathSum(root->left,targetSum-root->val)||
hasPathSum(root->right,targetSum-root->val);
}
};
相同的树
class Solution {
private:
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==nullptr&&q==nullptr){
return true;
}
else if((p!=nullptr&&q==nullptr)||(p==nullptr&&q!=nullptr)){
return false;
}
else if(p->val!=q->val){
return false;
}
else{
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
}
};动态规划
最大子数组和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n= nums.size();
int maxn=nums[0],pre=0;
for(int i=0;i<n;i++){
pre = max(pre+nums[i],nums[i]);
maxn=max(maxn,pre);
}
return maxn;
}
};爬楼梯
class Solution {
public:
int climbStairs(int n) {
int one=1;
int two=2;
int resSum=0;
if(n==1) return one;
if(n==2) return two;
for(int i=3;i<=n;i++){
resSum = one+two;
one = two;
two = resSum;
}
return resSum;
}
};杨辉三角
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res;
if(numRows==1) return {{1}};
if(numRows==2) return {{1},{1,1}};
res.push_back(vector<int>{1});
vector<int>s;
s.push_back(1);
s.push_back(1);
res.push_back(s);
for(int i=3;i<=numRows;i++){
vector<int> t;
t.push_back(1);
vector<int> rt=res.back();
for(int j=0;j<rt.size()-1;j++){
t.push_back(rt[j]+rt[j+1]);
}
t.push_back(1);
res.push_back(t);
}
return res;
}
};class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>>res(numRows);
for(int i=0;i<numRows;i++){
res[i].resize(i+1);
res[i][0]=res[i][i]=1;
for(int j=1;j<i;j++){
res[i][j]=res[i-1][j]+res[i-1][j-1];
}
}
return res;
}
};杨辉三角 II
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<vector<int>> res;
if(rowIndex==0) return {1};
if(rowIndex==1) return {1,1};
res.push_back(vector<int>{1});
vector<int>s;
s.push_back(1);
s.push_back(1);
res.push_back(s);
for(int i=3;i<=rowIndex+1;i++){
vector<int> t;
t.push_back(1);
vector<int> rt=res.back();
for(int j=0;j<rt.size()-1;j++){
t.push_back(rt[j]+rt[j+1]);
}
t.push_back(1);
res.push_back(t);
}
return res[rowIndex];
}
};class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> res(rowIndex+1);
res[0]=1;
for(int i=1;i<=rowIndex;i++){
for(int j=i;j>0;j--){
res[j]+=res[j-1];
}
}
return res;
}
};买卖股票的最佳时机
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minprices = prices[0];
int maxprofit = 0;
for(int i=1;i<prices.size();i++){
minprices=min(minprices,prices[i]);
maxprofit = max(maxprofit,prices[i]-minprices);
}
return maxprofit;
}
};比特位计数
class Solution {
private:
int countOnes(int x){
int count=0;
while(x!=0){
x&=(x-1);
count++;
}
return count;
}
public:
vector<int> countBits(int n) {
vector<int> record(n+1);
for(int i=0;i<=n;i++){
record[i]=countOnes(i);
}
return record;
}
};判断子序列
万物皆可DP
双指针更加快，而且容易理解
class Solution {
public:
bool isSubsequence(string s, string t) {
int sl = s.size();
int tl = t.size();
int i=0,j=0;
while(i<sl&&j<tl){
if(s[i]==t[j]){
i++;
}
j++;
}
return i==sl;
}
};最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
//LIS(i)表示以第i个数字为结尾的最长上升子序列的长度
//LIS(i)表示[0...i]的范围内，选择数字nums[i]可以获得的最长上升子序列的长度
//LIS(i) = max(1+LIS(j) if(nums[i]>nums[j])
//j<i
namespace LIS1{
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> memo(nums.size(),1);
for(int i=0;i<nums.size();i++){
for(int j=0;j<i;j++){
if(nums[j]<nums[i])
memo[i] = max(memo[i],memo[j]+1);
}
}
int res = 0;
for(auto i: memo){
res = max(res,i);
}
return res;
}
};双指针
删除有序数组中的重复项
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
快慢指针
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()==0){
return 0;
}
int slow=1;
int fast=1;
while(fast<nums.size()){
if(nums[fast]!=nums[slow]){
nums[slow]=nums[fast];
slow++;
}
fast++;
}
return slow;
}
};删除有序数组中的重复项 II
你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明：
为什么返回数值是整数，但输出的答案是数组呢？
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}class Solution {
public:
int removeElement(vector<int>& nums, int val) {
if(nums.size()==0){
return 0;
}
int slow = 0;
int fast = 0;
while(fast<nums.size()){
if(nums[fast]!=val){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
};实现 strStr()
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
朴素模式匹配算法
class Solution {
public:
int strStr(string haystack, string needle) {
//haystack 中有haystack.size()-needle.size()+1个子串
//暴力解法，取出所有子串并比较
if(needle.size()==0) return 0;
int count = haystack.size()-needle.size()+1;
for(int i=0;i<count;i++){
//标记
bool flase = true;
for(int j=0;j<needle.size();j++){
if(haystack[i+j]!=needle[j]){
flase = false;
break;
}
}
if(flase) return i;
}
return -1;
}
};class Solution {
public:
int strStr(string haystack, string needle) {
int i =0;
int j =0;
if(needle.size()==0) return 0;
while(i<haystack.size()&&j<needle.size()){
if(haystack[i]==needle[j]){
++i;
++j;
}
else{
i=i-j+1;
j=0;
}
}
if(j==needle.size())
return i-needle.size();
else
return -1;
}
};KMP
class Solution {
//次数next数组为经典原始写法
private:
vector<int> next;
public:
void getNext(const string& pattern){
int index=0;
int i=1;
while(i<pattern.size()){
if(pattern[i]==pattern[index]){
next[i] = index+1;
index++;
i++;
}
else{
if(index!=0){
//最关键一步
//前一个字符在相应前缀字符串中的位置
index = next[index-1];
}
else{
next[i]=0;
i++;
}
}
}
}
int strStr(string haystack, string needle) {
next.resize(needle.size(),0);
getNext(needle);
int i=0;
int j=0;
if(needle.size()==0) return 0;
while(i<haystack.size()&&j<needle.size()){
if(haystack[i]==needle[j]){
i++;
j++;
}
else{
if(j!=0){
j = next[j-1];
}
else{
i++;
}
}
}
if(j==needle.size()){
return i-j;
}
else{
return -1;
}
}
};
盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
class Solution {
public:
int maxArea(vector<int>& height) {
int left =0;
int right = height.size()-1;
int ret=0;
while(left<right){
int area = min(height[left],height[right])*(right-left);
ret = max(area,ret);
if(height[left]>height[right]){
right--;
}
else{
left++;
}
}
return ret;
}
};移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int k=0;
for(int i=0;i<n;i++){
if(nums[i]!=0){
nums[k]=nums[i];
k++;
}
}
for(int j=k;j<n;j++){
nums[j]=0;
}
}
};三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n=nums.size();
sort(nums.begin(),nums.end());
vector<vector<int>>ans;//存放结果
if(n<3) return {};
for(int i=0;i<n;i++)
{
if(nums[i]>0) return ans;//排序后，如果第一个数大于零，后面相加就不可能等于零了
if(i!=0&&nums[i]==nums[i-1]) continue;//去重：如果此数已经选取过，跳过
int left=i+1,right=n-1;
while(right>left)
{
if(nums[left]+nums[right]>-nums[i])
{
right--;
}
else if(nums[left]+nums[right]<-nums[i])
{
left++;
}
else if(nums[left]+nums[right]==-nums[i])
{
ans.push_back(vector<int>{nums[i],nums[left],nums[right]});
left++;
right--;
//去重
while(left<right&&nums[left]==nums[left-1]) left++;
while(left<right&&nums[right]==nums[right+1]) right--;
}
}
}
return ans;
}
};删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
/**
* 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 getLength(ListNode* head)
{
int length = 0;
while(head)
{
++length;
head = head -> next;
}
return length;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
int length =getLength(head);
//dummy->next = head
ListNode * dummy = new ListNode(0,head);//哑结点
ListNode * cur = dummy;
for(int i=1;i<length-n+1;++i)
{
cur=cur->next;
}
cur->next=cur->next->next;
return dummy->next;
}
};最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
排序 双指针
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int n = nums.size();
int best = 1e7;
// 根据差值的绝对值来更新答案
auto update = [&](int cur) {
if (abs(cur - target) < abs(best - target)) {
best = cur;
}
};
// 枚举 a
for (int i = 0; i < n; ++i) {
// 保证和上一次枚举的元素不相等
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 使用双指针枚举 b 和 c
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
// 如果和为 target 直接返回答案
if (sum == target) {
return target;
}
update(sum);
if (sum > target) {
// 如果和大于 target，移动 c 对应的指针
int k0 = k - 1;
// 移动到下一个不相等的元素
while (j < k0 && nums[k0] == nums[k]) {
--k0;
}
k = k0;
} else {
// 如果和小于 target，移动 b 对应的指针
int j0 = j + 1;
// 移动到下一个不相等的元素
while (j0 < k && nums[j0] == nums[j]) {
++j0;
}
j = j0;
}
}
}
return best;
}
};颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
class Solution {
public:
void sortColors(vector<int>& nums) {
int zero=-1; // [0,zero] == 0
int two=nums.size(); // [two,nums.size()-1] == 2
// [zero+1,i) = 1;
for(int i=0;i<two;){
if(nums[i]==1){
i++;}
else if(nums[i]==2){
swap(nums[i],nums[--two]);}
else{//nums[i]==0
assert(nums[i]==0);
swap(nums[++zero],nums[i++]);
}
}
}
};比较版本号
给你两个版本号 version1 和 version2 ，请你比较它们。
版本号由一个或多个修订号组成，各修订号由一个 ‘.’ 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。
比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。
返回规则如下：
如果 version1 > version2 返回 1，
如果 version1 < version2 返回 -1，
除此之外返回 0。
class Solution {
public:
int compareVersion(string version1, string version2) {
int i=0,j=0;
while(i<version1.size()||j<version2.size()){
int x=0;
while(i<version1.size()&&version1[i]!='.'){
x =x*10+version1[i++]-'0';
}
++i;//跳过 .
int y=0;
while(j<version2.size()&&version2[j]!='.'){
y =y*10+version2[j++]-'0';
}
++j;//跳过 .
if(x!=y){
return x>y?1:-1;
}
}
return 0;
}
};滑动窗口
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int freq[256]={0};//存ACSII码
//注意这里的定义
int l = 0,r =-1;
int res = 0;
while(l<s.size()){
//如果没有重复的字符
if(r+1<s.size()&&freq[s[r+1]]==0){
++r;
freq[s[r]]++;
}
//遇到重复的字符 右指针不动
//左指针右移，并将其在ASCII字符集中的字符减一
else{
freq[s[l++]]--;
}
//
res = max(res,r-l+1);
}
return res;
}
};重复的DNA序列
DNA序列 由一系列核苷酸组成，缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’.。
例如，”ACGAATTCCG” 是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
示例 1：
输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
输出：[“AAAAACCCCC”,”CCCCCAAAAA”]
示例 2：
输入：s = “AAAAAAAAAAAAA”
输出：[“AAAAAAAAAA”]
提示：
0 <= s.length <= 105
s[i]==’A’、’C’、’G’ or ‘T’
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int n= s.size();
if(n<10) return {};
vector<string>res;
unordered_map<string,int> m;
for(int i=0;i<=n-10;i++){
string tstr = s.substr(i,10);
m[tstr]++;
}
unordered_map<string,int>::iterator it;
for(it=m.begin();it!=m.end();it++){
if(it->second>1)
res.push_back(it->first);
}
return res;
}
};长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
class Solution{
public:
int minSubArrayLen(int target, vector<int>& nums) {
int l = 0 , r = -1;
int sum = 0, res = nums.size()+1;
while(l<nums.size()){
if(r+1<nums.size()&&sum<target)
sum += nums[++r];
else
sum -= nums[l++];
if(sum>=target)
res = min(res,r-l+1);
}
if(res > nums.size()) return 0;
return res;
}
};存在重复元素 II
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,1], k = 3
输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1
输出：true
示例 3：
输入：nums = [1,2,3,1,2,3], k = 2
输出：false
提示：
1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> record;
for(int i=0;i<nums.size();i++){
if(record.find(nums[i])!=record.end())
return true;
record.insert(nums[i]);
if(record.size()==k+1){
record.erase(nums[i-k]);
}
}
return false;
}
};找到字符串中所有字母异位词
给定两个字符串 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 仅包含小写字母
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int>pc(26,0);
vector<int>sc(26,0);
for(int i=0;i<p.size();i++){
pc[p[i]-'a']++;
}
vector<int> res;
int l=0;
for(int i=0;i<s.size();i++){
sc[s[i]-'a']++;
if(i<p.size()-1) continue;
if(pc==sc) res.push_back(l);
sc[s[l]-'a']--;
l++;
}
return res;
}
};深度优先搜索
岛屿数量
给你一个由 ‘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：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
提示：
- `m == grid.length`
- `n == grid[i].length`
- `1 <= m, n <= 300`
- `grid[i][j]` 的值为 `'0'` 或 `'1'class Solution {
private:
int d[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
vector<vector<bool>> visited;
int m,n;
bool isArea(int x,int y){
return x>=0&&x<m && y>=0&&y<n;
}
// 从grid[x][y]的位置开始,进行floodfill
// 保证(x,y)合法,且grid[x][y]是没有被访问过的陆地
void dfs(vector<vector<char>>& grid,int x,int y){
visited[x][y] = true;
for(int i=0;i<4;i++){
int newx = x +d[i][0];
int newy = y+ d[i][1];
if(isArea(newx,newy)&&!visited[newx][newy]&&grid[newx][newy]=='1'){
dfs(grid,newx,newy);
}
}
return;
}
public:
int numIslands(vector<vector<char>>& grid) {
m =grid.size();
if(m==0)
return 0;
n= grid[0].size();
if(n==0)
return 0;
visited = vector<vector<bool>>(m,vector<bool>(n,false));
// for(int i = 0 ; i < m ; i ++)
// visited.push_back(vector<bool>(n, false));
int res = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='1'&&!visited[i][j]){
dfs(grid,i,j);
res++;
}
}
}
return res;
}
};课程表
你这个学期必须选修 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：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
提示：
1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同
class Solution {
private:
vector<vector<int>> edges;
vector<int> visited;
bool valid = true;
void dfs(int u){
visited[u]=1;//u点被访问过
for(int v:edges[u]){
if(visited[v]==0){
dfs(v);
if(!valid){
return;
}
}
else if(visited[v]==1){
valid = false;
return;
}
}
visited[u]=2;
}
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
edges.resize(numCourses);
visited.resize(numCourses);
for(const vector<int>& info:prerequisites){
edges[info[1]].push_back(info[0]);
}
for(int i=0;i<numCourses&&valid;i++){
if(!visited[i]){
dfs(i);
}
}
return valid;
}
};