算法套路学习笔记

算法套路学习笔记 前言

现在是2021-11-21,开始使用东哥的算法小抄进行算法的学习,这篇文章就算是我的读书笔记吧,侵权删。

1.1 基础语法使用备份 1.哈希表 unordered_map

常用方法:
①size_type count(const key_type& key);
返回哈希表中key出现的次数,因为哈希表不会出现重复的键,所以该函数只可能返回0或者1
可以用来判断键key是否存在于哈希表中
②size_type erase(const key_type& key)
通过key来清除哈希表中的键值对, 如果删除成功则返回1,失败则返回0
③常用代码

#include 
#include 
using namespace std;

int main()
{
    vector nums{1,1,3,4,5,3,6};
    unordered_map counter;

    for(int num:nums){
        counter[num]++;
    }

    for(auto& item: counter){
        int key=item.first;
        int val=item.second;
        cout< 
对于unordered_map有一点是需要注意的,用方括号[]访问其中的键值对,如果key不存在,那么就会自动创建key,对应的值为值类型的默认值
 
2.JAVA String 
常用方法:
 ①toCharArray
 该方法会将JAVA中的Strng类型转化为char[]类型,进行该方法的转化后即可使用[]运算符进行运算, *** 作完毕后再转换回String类型
 ②StringBuilder
 如果需要对字符串进行频繁的拼接,则使用该方法较容易接受,示例代码
 
	public static void main(String[] args) {
		
		StringBuilder sBuilder = new StringBuilder();
		for(char c='a';c<='f';c++) {
			sBuilder.append(c);
		}
		//append支持拼接字符、字符串、数字等类型
		sBuilder.append('g').append("hij").append(123);
		String reString=sBuilder.toString();
		System.out.println(reString);
	}
 
③equal
 老生常谈的话题了,要比较两个字符串是否相同,就必须采用equal的方法来进行 而不是 ==
 
1.2 动态规划解题套路 
解释:首先,动态规划问题的一般形式就是求最值,而求最值,我们需要穷举所有可能的结果,但是动态规划的穷举存在“重叠子问题”,如果暴力穷举,效率会及其低下,因此需要备忘录或者"DP Table"来优化穷举过程，避免不必要的计算。
 动态规划一定具备有“最优子结构”，这样才能通过子问题的最值来得到原问题的最值,而只有列出正确的“状态方程”才能正确的穷举。
 核心步骤:
 ①这个问题的base case(最简单情况)是什么?
 ②这个问题有什么“状态”?
 ③对于每个“状态”，可以做出什么“选择”使得“状态”发生改变？
 ④如何定义dp数组/函数的含义来表现“状态”和“选择”?
 伪代码示例
 
    dp[0][0][...]=baseCase;
    //进行状态转移
    for(状态1 in 状态1的所有取值){
        for(状态2 in 状态2的所有取值){
            for(状态n....){
                dp[状态1][状态2]  = 求最值 (选择1,选择2,...);
            }
        }
    }
 
1.2.1斐波那契数列求解(记忆化搜索+动态规划) 
原始递归代码求解
 
class Solution {
public:
    int fib(int n) {
        if(n==0){
            return 0;
        }else if(n==1 || n==2){
            return 1;
        }
        return fib(n-1)+fib(n-2);
    }
};
 
交上去发现超时了,实际上是递归过程太过于低效,实际上每次递归都需要计算一个值,但实际上在之前的递归就可以把这个值求出来了,那么如果有这样的特性的话(重叠子问题),就可以采用动态规划的思路来做了,记忆化计算(搜索)。
 递归算法的时间复杂度如何计算？就是用子问题个数乘以解决一个子问题所需要的时间
 首先计算子问题的个数,即递归树中节点的总数。显然二叉树节点总数为指数级别的,所以求解子问题个数的时间复杂度为O(2^n),然后解决一个子问题的时间,只有加法 *** 作,因此是常数级别的复杂度O(1)
 记忆化计算改进算法:
 
class Solution {
public:
    int MOD = 1000000007;
    int fib(int n) {
        if(n==0){
            return 0;
        }
        vector m(n+1,0);
        return helper(m,n);
    }
    
    int helper(vector&m,int n){
        if(n==1||n==2){
            return 1;
        }
        if(m[n]!=0){
            return m[n];
        }
        //进行计算m[n]==0
        m[n]=(helper(m,n-1)+helper(m,n-2))%MOD;
        return m[n];
    }

};
 
上面改进算法的最大特点就是建立了一个m数组来存储计算结果,通过画出递归树可以知道,有大量的重复计算,那么这个m数组就可以将这些冗余的计算给优化掉,从而对程序进行优化。
 自顶向下:从一个规模比较大的原问题,向下逐渐分解规模,直到f(1)和f(2)这两个basecase为止,然后逐层返回答案。
 自底向上:从最下面最简单问题规模最小的f(1)和f(2)向上推,直到推到答案,这就是动态规划的思路。
 
动态规划改进算法
 
class Solution {
public:
    int MOD = 1000000007;
    int fib(int n) {
        if(n==0){
            return 0;
        }
        if(n==1 || n==2){
            return 1;
        }
        int *dp=new int[n+1];
        dp[1]=dp[2]=1;//初始状态
        for(int i=3;i<=n;i++){
            dp[i]=(dp[i-1]+dp[i-2])%MOD;
        }
        return dp[n];
    }
    

};
 
提交后发现空间复杂度仍然很高,但是实际上是不是真的需要这个数组呢?实际上题目单case的输入方式,决定了不需要多次计算,因此每次计算只需要前两个数作为计算支撑,因此不需要额外开拓新的数组,只需要把之前的计算结果用两个变量存起来进行迭代即可。
 
class Solution {
public:
    int MOD = 1000000007;
    int fib(int n) {
        if(n==0){
            return 0;
        }
        if(n==1 || n==2){
            return 1;
        }
        int pre=1,cur=1;
        for(int i=3;i<=n;i++){
            int sum=(pre+cur)%MOD;
            pre=cur%MOD;
            cur=sum%MOD;
        }
        return cur;
    }
    

};
 
这个技巧就是所谓的状态压缩,如果我们发现每次状态转移只需要DPTable中的一部分,那么可以尝试用状态压缩来缩小DPTable的大小,只记录必要的数据。
 总结:斐波那契数列的例子主要学到的是如何来消除重叠子问题的问题。
 
1.2.2凑零钱问题(暴力递归以及dp迭代求解) 
题目描述:给你k种面值的硬币,面值分别为c1,c2,…ck,每种硬币的总量无限,再给一个金额amount,问你最少需要几枚硬币来凑出这个金额,如果不可能凑出,那么就返回-1.
 解题思路:
 ①这个问题的base case(最简单情况)是什么?
 就是给出的目标金额为0的时候,那么算法就返回0
 ②这个问题有什么“状态”?
 目标金额amount
 ③对于每个“状态”，可以做出什么“选择”使得“状态”发生改变？
 选择硬币的面值会减少目标金额的量,因此所有硬币的面值就是选择
 ④如何定义dp数组/函数的含义来表现“状态”和“选择”?
 dp(n)的定义:输入一个目标金额n,返回凑出目标金额n最少的硬币数量
 
暴力解:采用递归的思路,穷举出所有的硬币组合,通过每次选择而逼近目标金额的baseCase的方式来进行计算,在计算过程中,由于要求一个最值,因此需要做一个最佳选择,用min来控制是选还是不选,如果选,那么能否使得选了之后的结果比当前的解决方案有更少的硬币数,交上去发现超时了,然后分析递归树,发现仍然存在重复计算的问题,因此可以从这里入手进行优化
 
class Solution {
public:
    const int INF=0x3f3f3f3f;
    int coinChange(vector& coins, int amount) {
        return dp(coins,amount);
    }

    int dp(vector& coins,int n){
        if(n==0){
            return 0;
        }
        if(n<0){
            return -1;
        }
        int res=INF;
        for(int i=0;i 
记忆化搜索优化之后的暴力解
 
class Solution {
public:
    const int INF=0x3f3f3f3f;
    vectorm;
    int coinChange(vector& coins, int amount) {
        for(int i=0;i& coins,int n){
        if(n==0){
            return 0;
        }
        if(n<0){
            return -1;
        }
        if(m[n]!=0){
            return m[n];
        }
        int res=INF;
        for(int i=0;i 
交上去仍然发现超时,但是通过的样例多了15个,证明该算法思路本身没问题,但是需要进一步优化.
 接下来考虑动态规划
 
class Solution {
public:
    const int INF=0x3f3f3f3f;
    int coinChange(vector& coins, int amount) {
        vector dp(amount+1,amount+1);
        //别忘了初始化状态,0的面值当然是0枚硬币了
        dp[0]=0;
        for(int i=0;i 
通过这一节可以了解到求解这一类问题主要是通过记忆化搜索来优化递归树还有优化状态转移方程来进行求解的
 
1.3 回溯算法解题套路框架 
解决一个回溯问题,实际上就是一个决策树的遍历过程。通常情况下需要三个要素
 1.路径：也就是已经做出的选择
 2.选择列表:你当前可以做出的选择
 3.结束条件:到达决策树的底层,无法再做选择的条件
 这三点在dfs中体现得非常具体,就不详细讲了,可以简单地理解为递归调用之前做选择,在递归调用之后撤销选择,转而去尝试别的选择
 回溯问题的解题的关键是backtrack函数的编写,该函数其实就像一个指针,在这棵树上遍历,同时要正确维护每个节点的属性,每当走到树的底层,其路径就是一个解。
 做选择其实就是从选择列表中拿出一个选择,并将它放入路径,撤销选择其实就是路径中拿出一个选择,并将其恢复到选择列表中。
 在递归之前做出选择,在递归之后撤销刚才的选择
 
1.3.1 全排列问题 
采用模板写的
 
class Solution {
public:
    vector >ans;
    vector> permute(vector& nums) {
        vector track;
        backTrack(nums,track);
        return ans;
    }

    void backTrack(vector& nums,vector& track){
        //参数说明:nums是选择列表,如何体现其被选择和未被选择的状态
        //我们通过判断track内的元素数量来判断是否选择了足够的函数
        //结束条件,当选择状态为空
        if((int)track.size() == (int)nums.size() ){
            ans.push_back(track);
            return ;
        }
        for(int i=0;i track,int num){
        for(int i=0;i 
用dfs写的
 
class Solution {
public:
    vector >ans;
    vector select;//选择列表,放在全局变量
    map book;//标记数组
    vector> permute(vector& nums) {
        //先将选择列表复制一份
        for(int i=0;itrack;
        dfs(track);
        return ans;
    }

    void dfs(vector& track){
        if(track.size()==select.size()){
            ans.push_back(track);
            return;//返回上一次搜索
        }
        for(int i=0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5580111.html