算法肝道夫之路

五步刷题法：

第一遍：尝试解决问题，解决不了背诵默写其他人的题解

第二遍：快速将脑海中的题解写到leetcode上，尽量超过leetcode80%以上的人

第三遍: 24小时以后重新刷

第四遍: 一周以后重新刷题

第五遍:面试一周或一个月前，重刷并手写代码(模拟真实环境)

常见时间复杂度

O(1) 常数阶

O(logn) 对数阶

O(n) 线性阶

O(nlogn) 线性对数阶

O(n^2) 平方阶

O(n^3) 立方阶

O(2^n) 指数阶

O(n!) 阶乘阶

O(n^n) 

从上到下的时间复杂度递增，一般情况下时间复杂度到立方阶就不能要了，到平方阶就要考虑是否有必要。

1.一个问题可以分解为相同的几个子问题

2.存在终止条件

1.第一遍

import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map map = new HashMap();
    //递归实现
    public int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        //如果map中存在值，返回，不存在，重新计算
        if(null != map.get(n)){
            return map.get(n);
        }else{
            //放入map中
            int sum = climbStairs(n-1)+climbStairs(n-2);
            map.put(n,sum);
            return sum;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().climbStairs(4));
    }
}

import java.util.HashMap;
import java.util.Map;


class Solution {
    Map map = new HashMap();
    public int fib(int n) {
        if(n == 0 ){ return 0;}
        if(n == 1 ){ return 1;}
        if(null != map.get(n)){
            return map.get(n);
        }else{
            int sum = fib(n-1) + fib(n-2);
            map.put(n,sum);
            return sum;
        }
    }
}

1. 两数之和

import java.util.HashMap;
import java.util.Map;


class Solution {
    public int[] twoSum(int[] nums, int target) {
        //暴力穷举
//        for(int i=0;i map = new HashMap();
        for(int i=0;i map = new HashMap();
//        for (int i =0 ;i