1.如何高效的刷算法题？

五步刷题法：

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

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

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

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

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

2. 1-002-算法时间复杂度分析

常见时间复杂度

O(1) 常数阶

O(logn) 对数阶

O(n) 线性阶

O(nlogn) 线性对数阶

O(n^2) 平方阶

O(n^3) 立方阶

O(2^n) 指数阶

O(n!) 阶乘阶

O(n^n)?

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

3. 什么是递归

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

2.存在终止条件

4.1-004-(LeetCode-70) 爬楼梯?

1.第一遍

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

class Solution {
    private Map<Integer, Integer> map = new HashMap<Integer,Integer>();
    //递归实现
    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));
    }
}

5.?斐波那契数

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

/**
 * 509. 斐波那契数
 * 使用递归+hashMap解决问题
 */
class Solution {
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    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;

/**
 * 1. 两数之和
 * 第一种方法：暴力穷举 时间复杂度O（N^2）
 * 第二种方法：遍历+hashMap 时间复杂度O（N）
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        //暴力穷举
//        for(int i=0;i<nums.length;i++){
//            for(int j=0;j<nums.length;j++){
//                if(nums[i]+nums[j] == target && i!=j){
//                    return new int[]{i,j};
//                }
//            }
//        }

        //遍历+hashMap 时间复杂度O（N）
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            int value = target-nums[i];
            if(map.containsKey(value)){
                return new int[]{value,i};
            }else{
                map.put(nums[i],i);
            }
        }
        return new int[2];

//        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//        for (int i =0 ;i<nums.length; i++){
//            if(map.containsKey(target-nums[i])){
//                return new int[]{map.get(target-nums[i]),i};
//            }
//            map.put(nums[i],i);
//        }
//
//        return new int[0];
    }

    public static void main(String[] args) {
        System.out.println(new Solution().twoSum(new int[]{3,2,4},6));
    }
}

88. 合并两个有序数组?

解法有三：

1. 第二个数组给第一个数组，第一个数组排序

2. 引入temp数组，将数组1和数组2比较放入temp数组，最后将temp数组放入nums1 （todo）

3. 倒序排列将数组比较放入nums1（todo）

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
            for(int i = 0;i < nums2.length;i++){
                nums1[m+i] = nums2[i];
            }
            Arrays.sort(nums1);
    }
}