算法学习

算法(持续更新ing)

数组

二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

class Solution {
    private:
     int result;
public:
    int search(vector<int>& nums, int target) {
        result =-1;
        int front=0;
        int end=nums.size()-1;
        int mid=(front+end)/2;
        while(front<=end)
        {
            if(nums[mid]==target)
            {
                result=mid;
                return result;
            }
            if(target>nums[mid])
            {
                front=mid+1;
                mid=(front+end)/2;
            }
            if(target<nums[mid])
            {   
                end=mid-1;
                mid=(front+end)/2;
            }
        }
        return result;
    }
};

移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow =0;
        fast= 0;
        length=len(nums)
        while fast<length:
            if nums[fast]!=val:
                nums[slow]=nums[fast]
                slow+=1
            fast+=1;

        return slow

链表

移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

解法1:不使用虚拟头节点

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        
        //如果需要删除头节点
        while(head!=NULL&&head->val==val)
        {
            ListNode* temp=head;
            head=head->next;
            delete temp;
        }

        //如果删除非头节点
        ListNode * cur=head;
        while(cur!=NULL&&cur->next!=NULL)
        {
            if(cur->next->val==val)
            {
                ListNode* temp =cur->next;
                cur->next=cur->next->next;
                delete temp;
            }
            else 
            {
                cur=cur->next;
            }
        }
        return head;
    }
};

解法2：虚拟一个头节点

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        
       //虚拟一个头结点
        ListNode* ntrHead = new ListNode(0);
        ntrHead->next=head;
        ListNode* p=ntrHead;
        while(p->next!=NULL){
            if(p->next->val==val)
            {
                ListNode * temp=p->next;
                p->next=p->next->next;
                delete temp;
            }
            else
            {
                p=p->next;
            }
        }
        head=ntrHead->next;
        delete ntrHead;
        return head;
    }
};

二叉树

层序遍历（类似广搜）

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

思路

借助队列，类似广度优先搜索，如图中举例，先将根元素放入队列，并记录此时队列长度，（第一层只有一个元素，长度为1），故只需再遍历一次，将根节点pop出去，再将根节点的左右push到队列里，如果左右为空，则不push，并退出循环，当第二次记录队列长度，（第二层有二个元素，长度为2），故需遍历两次，继续pop，并判断左右节点，以此类推。

class Solution(object):
    def levelOrder(self, root):
        if (root==None):
           return []
        queue=[root]
        res=[]
        while queue:
            size=len(queue)
            temp=[]
            for i in range(size):
                r=queue.pop(0)
                temp.append(r.val)
                if r.left:
                    queue.append(r.left)
                if r.right:
                    queue.append(r.right)
            res.append(temp)
        return res

二叉树翻转

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

解题思路

利用前序或者后序进行遍历来交换每个结点的左右子树

前序（从上至下进行交换）

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL)
        {
            return root;
        }
        swap(root->left,root->right);
        invertTree(root->left);
        invertTree(root->right);

        return root;
    }
};

后序（从下至上进行交换）

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL)
        {
            return root;
        }
        invertTree(root->left);
        invertTree(root->right);
        swap(root->left,root->right);

        return root;
    }
};

前序（不使用递归，使用迭代，一般递归能做的栈也能做）

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL)
        {
            return root;
        }
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
            TreeNode* treeNode =st.top();
            st.pop();
            swap(treeNode->left,treeNode->right);
            if(treeNode->left) st.push(treeNode->left);
            if(treeNode->right) st.push(treeNode->right);
        }
        return root;
    }
};

为什么不能用中序：

如果使用中序，则为左中右，如果左子树交换，该交换右子树，但此时的右子树为交换过的左子树，具体可以画图判断。如果十分想用中序，则可以左中左进行交换，但没必要。

对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

解题思路

只能使用后序遍历，因为判断每个节点是否对称需要孩子节点的返回的结果去判断，故须左右根。

判断条件：

左空，右不空，false

左不空，右空，false

左空，右空，true

左不空，右不空，但值不相等，false

递归开始：

先比较外侧，故fun（左的左节点，右的右节点）

再比较内测，故fun（左的右节点，右的左节点）

class Solution {
public:

    bool compare(TreeNode*left,TreeNode*right)
    {
        if((left==NULL)&&(right!=NULL)) return false;
        else if((left!=NULL)&&(right==NULL))return false;
        else if((left==NULL)&&(right==NULL)) return true;
        else if(left->val!=right->val) return false;
        //符合条件
        else
        {
            bool outside=compare(left->left,right->right);
            bool inner=compare(left->right,right->left);
            return outside&&inner;
        }

    }

    bool isSymmetric(TreeNode* root) {
        if((root->left==NULL)&&(root->right==NULL))
        {
            return true;
        }
        bool result=compare(root->left,root->right);
        return result;   
    }
};

回溯算法

概述

虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案。

可以解决的问题

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

算法框架

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

解题思路

当k小的时候，便可使用for进行暴力解题，但当k过于大，该想法便不可实现。且注意组合是无序的。

从左往右，当取完1后，往右走便可省去1，且每次取数不可以重复取，随着继续往右走，范围进而收缩。此时我们发现，k为树的深度，n为树的宽度。

class Solution {

private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n,int k,int num)
    {
        if(path.size()==k)
        {
             result.push_back(path);
        }
        for(int i=num;i<=n;i++)
        {
            //处理结点
            path.push_back(i);
            //回溯
            backtracking(n,k,i+1);
            //更新
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combine(int n, int k) {
        result.clear();
        path.clear();
        backtracking(n,k,1);
        return result;
    }
};

剪枝优化

由于k=4，删除的这些枝干便是不可能达到4的情况，这些则为无效分支。

优化过程

1. 已经选择的元素个数：path.size();
2. 还需要的元素个数为: k - path.size();
3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，i=num，包括了这个num：

举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 优化的地方
       path.push_back(i); // 处理节点
       backtracking(n, k, i + 1);
       path.pop_back(); // 回溯，撤销处理的节点
   }

N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

解题思路：

可以把递归棋盘相信成递归一棵树，每次向下递归则搜索下一行，回溯则会搜索上一行的下一列

n皇后约束条件：

• 不能同行
• 不能同列
• 不能同斜线

从图中，可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度，当搜索到树的叶子节点，说明找到了皇后的合理位置。

回溯三部曲

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

class Solution {
    private: 

    vector<vector<string>> result; 

    void backTrack(int n,int row,vector<string> & classboard)
    {
        //已经确认为正确皇后位置
        if(row==n)
        {
            result.push_back(classboard);
        }
        //这里为宽度
        for(int i=0;i<n;i++)
        {
            if(isVaild(row,i,classboard,n))
            {
                classboard[row][i]='Q';
                backTrack(n,row+1,classboard);
                //回溯
                classboard[row][i]='.';
            }
        }
    }

    bool isVaild(int row,int col,vector<string> & classboard,int n)
    {
        // 检查列
        for (int i = 0; i < row; i++) { 
            if (classboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查45度角是否有皇后
        for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
            if (classboard[i][j] == 'Q') {
                return false;
            }
        }
        // 检查 135度角是否有皇后
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (classboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

public:
    vector<vector<string>> solveNQueens(int n) {
        //初始化棋盘
        result.clear();
        std::vector<std::string> classboard(n,std::string(n,'.')); 
        backTrack(n,0,classboard);
        return result;
    }
};

注意两点：

为什么不判断行，应为每次递归只会选择同行中的一个元素，故可不判断，同时递归为向下递归，对角线判断也只需判断改行以上的元素，以下的元素无需判断。

动态规划

硬币问题

若有若干硬币，面值分别为1，5，11，凑出w，至少需要多少？

解决方案：

• 1.贪心
• 2.暴力枚举(3个for)
• 3.DP

f（n）	最优解	1	5	11
f（0）	0	x	x	x
f（1）	1	1+f (0)	x	x
f（2）	2	1+f (1)	x	x
f（3）	3	1+f (2)	x	x
f（4）	4	1+f (3)	x	x
f（5）	1	1+f (4)	1+f (0)	x
f（6）	2	1+f (5)	1+f (1)	x
f（7）	3	1+f (6)	1+f (2)	x
f（8）	4	1+f (7)	1+f (3)	x
f（9）	5	1+f (8)	1+f (4)	x
f（10）	2	1+f (9)	1+f (5)	x
f（11）	1	1+f (10)	1+f (6)	1+f (0)
f（12）	2	依次类推	依次类推	依次类推
f（13）	3	依次类推	依次类推	依次类推
f（14）	4	依次类推	依次类推	依次类推
f（15）	3	依次类推	依次类推	依次类推

由图可知，该递推公式与前min[f(n-1)|f(n-5)|f(n-11)]有关

代码：

#include <iostream>
using namespace std;

int min(int a,int b)
{
    return a<b?a:b;
}

int main() {

    int dp[100];
    //f(0)=0
    dp[0]=0;
    //每次遍历的最优解
    int value;
    for(int i=1;i<=15;i++)
    {
        value=999999;
        if(i-1>=0){value= min(value,dp[i-1]+1);}
        if(i-5>=0){value= min(value,dp[i-5]+1);}
        if(i-11>=0){value= min(value,dp[i-11]+1);}
        dp[i]=value;
        cout<<value<<endl;
    }
    return 0;
}

总结

动态规划特点：

最优子结构：大问题可由小问题最优解推出

无后效性：一旦最优解确定，之后可以随便调用，无需关心已经确认的最优解

背包问题

现有四个物品，背包总数8，怎么拿价值最多的物品

如：

物品编号：1，2，3，4

物品重量：2，3，4，5

物品价值：3，4，5，8

记f(k,w)：背包容量w，现有k件物品可以偷，所偷到的最大价值

例如：f(2,5) 当前背包容量5，有2件物品可以偷，现在如果选择投，则为f(1,2)+4=7,如果不偷则为f(1,5)=3，故f(2,5)=7

int f[5][9]={0};
int w[5]={0,2,3,4,5};
int v[5]={0,3,4,5,8};
int main()
{
    //清零
    memset(f,0,sizeof(f));
    for(int i=1;i<5;i++)
    {
        for(int j=1;j<9;j++)
        {
            if(w[i]<=j)
            f[i][j]= max(f[i-1][j-w[i]]+v[i],f[i-1][j]);
            else
            f[i][j]=f[i-1][j];
        }
    }

    for(int i=0;i<5;i++)
        for(int j=0;j<9;j++)
        {
            cout<<i<<j<<f[i][j]<<endl;
        }

    return  0;
}

LCS最长公共子序列

给定两个序列S1 S2,求二者最长公共子序列长度

例如：

S1=”algorithms”

S2=”alchemist”

S1,S2最长公共子序列为：alhms

解法：

设计状态

f [i] [j] 表示是序列Si和序列Sj的最长公共子序列。

状态转移方程

f [i] [j]=0 ，i=0或者j=0

f [i] [j]=1+f [i-1] [j-1]，Xi=Yj（此处相同，故1+前面最长子序列个数）

f [i] [j]=max{f [i-1] [j]，f [i] [j-1]}，Xi ！=Yj

f [i] [j]		0	1	2	3	4	5	6	7	8	9
			A	L	C	H	E	M	I	S	T
0(空字符)		0	0	0	0	0	0	0	0	0	0
1	A	0	1+f [0] [0]=1	max{f [1] [1]，f [0] [2}=1	1	1	1	1	1	1	1
2	L	0	1	1+f [1] [1]=2	2	2	2	2	2	2	2
3	G	0	1	2	2	2	2	2	2	2	2
4	O	0	1	2	2	2	2	2	2	2	2
5	R	0	1	2	2	2	2	2	2	2	2
6	I	0	1	2	2	2	2	2	1+2=3	3	3
7	T	0	1	2	2	2	2	2	3	3	4
8	H	0	1	2	2	3	3	3	3	3	4
9	M	0	1	2	2	3	3	4	4	4	4
10	S	0	1	2	2	3	3	4	4	5	5

/**
 * 最长公共子序列
 */
int dp[11][10]={0};
char * s1="algorithms";
char * s2="alchemist";

int main()
{
    memset(dp,0,sizeof (dp));
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=9;j++)
        {
            if(s1[i-1]==s2[j-1])
            {
                dp[i][j]=1+dp[i-1][j-1];
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    for(int i=0;i<=10;i++)
        for(int j=0;j<=9;j++)
        {
            cout<<i<<j<<dp[i][j]<<endl;
        }
    return 0;
}

若想输出最长序列，则可以从最后向前递归寻找。

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解题思路：

设计dp数组，由于要选择偷第i家，则前一家不能偷，则为dp[i]+dp[i-2]，选择不偷，则为dp[i-1],最后得出状态方程：

dp[i]=max(dp[i-1],dp[i-2]+物品value[i])

由于状态方程需要确定dp[i-2],则需初始化前两个数组。

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int length = nums.length;
    if (length == 1) {
        return nums[0];
    }
    int[] dp = new int[length];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (int i = 2; i < length; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[length - 1];
}

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

思路：

背包问题：

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。

“apple”, “pen” 是物品，那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。

“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的，那么我们就是强调物品之间顺序。

所以说，本题一定是 先遍历 背包，再遍历物品。

以输入: s = “leetcode”, wordDict = [“leet”, “code”]为例，dp状态如图：

递推公式：

if([j,i]&&dp[j]==true) dp[i]=true;

dp[i]往前走j，如果j到i为worddict里的一个单词，且dp[j]为true（意味这j之前的那段也是worddict里的一个单词），则dp[i]为true

class Solution {
public:
   bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {   // 遍历背包
            for (int j = 0; j < i; j++) {       // 遍历物品
                string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

贪心

贪心策略：局部最优推出全局最优，例如取钞票，每次取出最大的面额，最后一次去完，则得到最大面额。

分发饼干

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

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

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

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

解题思路

尽量用最大的饼干满足胃口最大的孩子。

先排序两个数组，再遍历胃口数组，其两个数组指针指向最后，并相比较，如果胃口大于饼干大小，则饼干数组不移动，胃口指针向前，反之可以喂饱，都向前移动。

其余思路：尽量用一个小饼干满足胃口小的孩子。

int cmp(int* a, int* b) {
    return *a - *b;
}
int findContentChildren(int* g, int gSize, int* s, int sSize) {
    if(sSize<=0)
    {
        return 0; 
    }
    qsort(g,gSize,sizeof(int),cmp);
    qsort(s,sSize,sizeof(int),cmp);
    int index = sSize -1;
    int result = 0;
    /**
    保证饼干数组是动态移动，胃口数组是静态移动
    */
    for(int i =gSize-1;i>=0;i--)
    {
        if(s[index]>=g[i])
        {
            result++;
            index--;
        }
        if(index<0)
        {
            break;
        }
    }
    return result;
}

摆动序列（也有动态规划的思路）

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

• 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
• 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

解题思路：

主题思路：不记录局部单调的数，只记录峰值，最后的峰值总数则为摆动序列最长子序列长度

判断数组出现的峰值

• 例如当前为i，前一个坡度为high[i]-high[i-1]，下一个坡度为high[i+1]-high[i]，当前一个坡度和下一个坡度一正一负，则为一个峰值，返回结果加1
• 如果出现上下平坡，例如1，2，2，2，1，则摆动序列最长为1，2，1，本题选择删除左面，当前一个坡度<=0,后一个坡度>0||当前一个坡度>=0,后一个坡度<0
• 如果出现两个元素，由于默认最后一个元素有一个坡度，可以延长第一个元素造成一个平坡，符合情况二的判断
• 如果出现单调中有平坡，1，2，2，2，3，4，则摆动序列最长为1，4，在判断前两种情况时，前一个坡度与后一个坡度是一起变化，如果出现单调中有平坡则会出现问题，此时，我们可以将前一个坡度保持不变，直到出现正负变换，前一个坡度才会更新，即可解决该问题。

int wiggleMaxLength(int* nums, int numsSize){
    //前一个坡度
    int prediff=0;
    //后一个坡度
    int crediff=0;
    //默认最后一个元素有坡度
    int result=1;
    if(numsSize==1)
    {
        return result;
    }
    for(int i=0;i<numsSize-1;i++)
    {
        crediff=nums[i+1]-nums[i];
        if((prediff<=0&&crediff>0)||(prediff>=0&&crediff<0))
        {
            result++;
            //防止出现单调中有平坡
            prediff=crediff;
        }
    }
    return result;
}

柠檬水找零（简单题）

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false

示例 1：

输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

解题思路：

优先用10元进行找零，如果10元没有，则再选择用5元找零（局部最优）。

bool lemonadeChange(int* bills, int billsSize) {
    int fiveNum=0;
    int tenNum=0;
    for(int i;i<billsSize;i++)
    {
        if(bills[i]==5)
        {
            fiveNum++;
        }
        if(bills[i]==10)
        {
            if(fiveNum!=0)
            {
                fiveNum--;
                tenNum++;
            }
            else
            {
                return false;
            }
        }
        if(bills[i]==20)
        {
            if(fiveNum>=1&&tenNum>=1)
            {
                fiveNum-=1;
                tenNum--;
            }
            else if(fiveNum>=3)
            {
                fiveNum-=3;
            }
            else
            {
                return false;
            }
        }
    }
    return true;
}

图论

基础

BFS

for (选择：本节点所连接的其他节点) {
    处理节点;
    dfs(图，选择的节点); // 递归
    回溯，撤销处理结果
}

DFS

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

所有可能路径

给定一个有 n 个节点的有向无环图，用二维数组 graph 表示，请找到所有从 0 到 n-1 的路径并输出（不要求按顺序）。

graph 的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些结点（译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a ），若为空，就是没有下一个节点了。

示例 1：

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例 2：

输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

示例 3：

输入：graph = [[1],[]]
输出：[[0,1]]

示例 4：

输入：graph = [[1,2,3],[2],[3],[]]
输出：[[0,1,2,3],[0,2,3],[0,3]]

示例 5：

输入：graph = [[1,3],[2],[3],[]]
输出：[[0,1,2,3],[0,3]]

解题思路：

使用传统dfs进行遍历，如果当前节点为最后一个节点，直接返回，如果不是，进行路径处理，向下一个节点遍历，本体图的存储结构为邻接表存储。

class Solution {

private:
    vector<int> path;
    vector<vector<int>> result;

public:
    // x 为当前节点   n为最后一个节点
    void dfs(vector<vector<int>>& graph,int x,int n)
    {
        if(x==n)
        {
            result.push_back(path);
            return ;
        }

        for(auto & y : graph[x])
        {
            path.push_back(y);
            dfs(graph,y,n);
            path.pop_back();
        }
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        path.clear();
        result.clear();
        int n =graph.size()-1;
        int x =path.size();
        path.push_back(0);
        dfs(graph,x,n);
        return result;
    }
};