[数据结构与算法]算法套路学习笔记

前言

现在是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 <iostream>
#include <unordered_map>
using namespace std;

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

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

    for(auto& item: counter){
        int key=item.first;
        int val=item.second;
        cout<<key<<":"<<val<<endl;
    }
    return 0;
}

对于unordered_map有一点是需要注意的,用方括号[]访问其中的键值对,如果key不存在,那么就会自动创建key,对应的值为值类型的默认值

2.JAVA String

常用方法:
①toCharArray
该方法会将JAVA中的Strng类型转化为char[]类型,进行该方法的转化后即可使用[]运算符进行运算,操作完毕后再转换回String类型
②StringBuilder
如果需要对字符串进行频繁的拼接,则使用该方法较容易接受,示例代码

	public static void main(String[] args) {
		/*1.StringBuilder*/
		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<int> m(n+1,0);
        return helper(m,n);
    }
    
    int helper(vector<int>&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];
    }
    

};