1. 栈和队列(简单）（√）

1.1：剑指 Offer 09. 用两个栈实现队列

1. 题目说明
   
2. 求解思路
   1）通过两个栈来实现队列
   2）首先新建两个成员变量栈，在构造函数处进行初始化
   3）队头插入：直接在入栈中插入即可
   4）队头删除：分为三种情况
   （1）：如果两个栈均为空，返回-1；
   （2）：如果出栈为空，那么把入栈元素都存入出栈中，再弹出出栈的首元素
   （3）：如果出栈不为空，那么直接弹出出栈中的首元素。
3. 代码展示

class CQueue {
    
    //类的成员变量（两个栈）
    Stack<Integer> stackin;
    Stack<Integer> stackout;

    public CQueue() {
    
        //初始化两个栈
        stackin=new Stack<>();
        stackout=new Stack<>();
    }
    
    public void appendTail(int value) {
    
        //入栈操作不影响，直接放入入栈中
        stackin.push(value);
    }
    
    public int deleteHead() {
    
        //出栈操作受影响，分为三种情况
        //1)入栈和出栈均为空
        if(stackin.isEmpty() && stackout.isEmpty() ){
    
            return -1;

        //2)入栈不空，出栈为空 
        }else if(!stackin.isEmpty() && stackout.isEmpty() ){
    
            //先把入栈中的元素都放到出栈来，再弹出
            while(!stackin.isEmpty()){
    
                stackout.push(stackin.pop());
            }
            return stackout.pop();

        //3)出栈不为空,直接弹出
        }else{
    
            return stackout.pop();
        }
    }
}

/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */

6. 注意事项：
   1）栈的新建和初始化学会。
   2）主要是对弹出元素进行分类讨论。
   3）栈的弹出和查看，都需要事先判断是否存在。

1.2：剑指 Offer 30. 包含min函数的栈

1. 题目说明
   
2. 求解思路
   1）使用一个栈存放原始栈
   2）再使用一个栈存放最小值信息：如果压入的时候是当前最小值，那么就压入；如果弹出的时候，是当前最小值，那么就弹出；

3. 原始栈的操作和以前一样即可

3. 代码解析

class MinStack {
    

    /** initialize your data structure here. */
    //核心思路：用两个栈实现,其中一个栈存储数据，另一个栈存最小值
    //1）定义新栈的数据结构
    ArrayDeque<Integer> stack;
    ArrayDeque<Integer> min;
    public MinStack() {
    
        stack=new ArrayDeque<>();
        min=new ArrayDeque<>();
    }

     //2）把数据压入栈中
    public void push(int x) {
    
        if(min.isEmpty() || x<=min.peek())   min.push(x);  //针对最小栈操作 //易错点：等于的情况也还是要压入栈中，不然只有一个，弹出去就没有了
        stack.push(x);
    }
    
    public void pop() {
    
        int x=stack.pop();
        if(x ==min.peek())   min.pop();     //针对最小栈操作 //迷惑操作，这两个东西搞不懂区别在哪里
        
    }
    
    public int top() {
    
        return stack.peek();
    }
    
    public int min() {
    
       return  min.peek();

    }
}

/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.min(); */

4. 注意事项：
   1）栈和队列，都可以用ArrayDeque(基于数组+链表）来实现：
   (1) 如果作为栈，其操作有：stack.push(),stack.pop(),stack.peek();
   (2) 如果作为栈，其操作有：stack.offer(),stack.poll(),stack.peek();
   2）栈和队列，都可以用双向链表LinkedList(基于双向链表）来实现：
   (1) 如果是栈：在尾部添加stack.addLast()，尾部弹出stack.removeLast();尾部查看：stack.getLast();
   (2) 如果是队列：在尾部添加stack.addLast()，头部弹出stack.removeLast();头部查看：stack.getFirst();

2. 链表（简单）（√）

2.1 剑指 Offer 06. 从尾到头打印链表

1. 题目说明
   

//自定义一个链表的class类
public class ListNode{
    
     int val;
     ListNode next;
     ListNode(int val){
    
         this.val=val;
     }
 }
 //核心思路：使用一个集合来装数据，然后再逆序 
class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        List<Integer> data=new ArrayList<>();
        while(head!=null){
    
            data.add(head.val);
            head=head.next;
        }
        int[] result=new int[data.size()];
        int m=data.size()-1;
        for(int i:data){
    
            result[m--]=i;
        }
        return result;

    }
}

2.2 剑指 Offer 24. 反转链表

1.问题描述

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        //特殊情况
        if(head==null) return head;

        //一般情况
        ListNode pre=null;
        ListNode post=head;
        while(post!=null){
    
            //保存下一个post
            ListNode temp=post.next;
            post.next=pre;

            //进行交换
            pre=post;
            post=temp;
        }
        return pre;

    }
}

4. 注意事项：
   1）主要考察对链表的使用

2.3 剑指 Offer 35. 复杂链表的复制

1.问题描述

class Solution {
    
    public Node copyRandomList(Node head) {
    
        //1)使用HashMap进行拷贝
        if(head==null)  return head;

        //2)使用HashMap进行存取：HashMap<原来节点，新节点>(查找时O(1)的时间复杂度)
        HashMap<Node,Node> hashmap=new HashMap<>();
        for(Node cur=head; cur!=null; cur=cur.next){
    
            hashmap.put(cur,new Node(cur.val));
        }

        //3)将拷贝的节点穿成一个新链表
        for(Node cur=head; cur!=null; cur=cur.next){
    
            hashmap.get(cur).next=hashmap.get(cur.next);
            hashmap.get(cur).random=hashmap.get(cur.random);
        }
        return hashmap.get(head);
    }
}

2. 注意事项：
   1）主要考察对链表的复制，使用HashMap集合。

3. 字符串（简单）（√）

3.1 剑指 Offer 05. 替换空格

1.问题描述

```java
public String replaceSpace(String s) {
    
        //核心考察：字符串的使用
        //如果要对字符串频繁进行修改，需要使用StringBuilder
        StringBuilder builder=new StringBuilder();
        for(int i=0;i<s.length();i++){
    
            if(s.charAt(i)!=' '){
    
                builder.append(s.charAt(i));
            }else{
    
                builder.append("%20");
            }
        }
        return builder.toString();

    }
}

2. 注意事项：
   1）主要考察对字符串的修改，需要使用StringBuilder
   2）新建：StringBuilder builder=new StringBuilder（）；
   3）添加：builder.append(“字符串”) ;builder.insert(“字符串”,索引值）
   4）删除：builder.delete(2,3) 包前不包后，索引值
   5）截取：builder.substring(2,4) :截取字符串，包前不包后

3.2 剑指 Offer 58 - II. 左旋转字符串

1. 问题描述
   

2. 代码展示

class Solution {
    
    public String reverseLeftWords(String s, int n) {
    

        StringBuilder builder1=new StringBuilder(s);
        StringBuilder builder2=new StringBuilder();
        builder2.append(builder1.substring(0,n));  //先截取前n个 易错点：builder1.substring(0,n)得到的是字符串
        builder1=builder1.delete(0,n);             //删除前n个
        builder1=builder1.append( builder2);       //把截取的前n补充到后面
        return builder1.toString();
    }
}

3. 问题总结
   1）主要考验一个StringBuilder的使用：append, insert, delete, substring

4. 查找算法（简单）（二分查找思路重点）（√）

4.1 剑指 Offer 03. 数组中重复的数字

1. 问题描述
   

2. 代码展示

class Solution {
    
    public int findRepeatNumber(int[] nums) {
    
        //通过使用一个哈希表，然后如果已经再里面，就输出(哈希表查找元素最快O(1)时间复杂度)
        HashSet<Integer> hashset=new HashSet<>();
        for(int i=0;i<nums.length;i++){
    
            if(hashset.contains(nums[i])){
    
                return nums[i];
            }else{
    
                hashset.add(nums[i]);
            }
        }
        return 0;
    }
}

3. 注意事项
   1）哈希表查找元素是最快的。
   2）哈希表使用的结构是：HashSet，常用方法如下：
   3）add（） ； size(); remove(); contains(); 和list集合非常像

4.2 剑指 Offer 53 - I. 在排序数组中查找数字

1. 问题描述
   

class Solution {
    
    public int search(int[] nums, int target) {
    
        int result=0;
        int left=0;
        int end=nums.length-1;
        int mid=(end+left)/2;  //索引值
        //1）找到第一次出现target的索引
        while(left<end){
    
            if(target<nums[mid]  ){
    
                end=mid;
            }else if( target>nums[mid]) {
    
                left=mid+1;       //易错点：左边的可以加一
            }else{
                    //易错点：这一句纯粹是为了找到起始的第一个值，方便后面的查找
                while(mid>0 &&nums[mid]==nums[mid-1]) mid--;
                break;  
            }
            mid=(end+left)/2;   //易错点：判断完之后，一定是之后，需要更新该值。
        }
        //2）遍历出现target出现的次数
        while(mid<nums.length && target==nums[mid++]) result++;
        return result;
    }
}

2. 核心问题：二分查找问题
   1）首先mid的选取
   2）进行while循环（left<end）

3. 三个判断 ：target>nums[mid] left=mid+1; target<nums[mid] end=mid; target=nums[mid] ,要进行while，找到初始的。
   4）while判断之后，对mid进行更新。

4.3 剑指 Offer 53 - II. 0～n-1中缺失的数字

1. 问题描述
   
2. 代码展示
   思路说明：
   1）缺少的是开头值：直接输出0
   2）缺少的是最后一个值：直接数组最后值加一
   3）缺少的是中间的值：二分进行查找，找到值应该满足条件：nums[i]

class Solution {
    
    public int missingNumber(int[] nums) {
    
        //二分进行查找
        //1)特殊情况，缺少0
        if(nums[0]!=0) return 0;
        //1)特殊情况，缺少最后一个值
        if(nums[nums.length-1]==nums.length-1) return nums.length;
        
        //一般情况：确实中间某个数
        int left=0;
        int right=nums.length-1;
        int mid=(left+right)/2;
        //如何定位缺少值：缺少值后面的数，索引和值不一样
        while(left<right){
    
            if(nums[mid]==mid){
    
                left=mid+1;
            }else if(nums[mid]!=mid && mid>0 && nums[mid]-nums[mid-1]!=2){
    
                right=mid;
            }else{
    
                break;
            }
            mid=(left+right)/2;
        }
        return mid;

    }
}

4. 总结
   1）如果出现排列好的数组，那么就默认需要使用二分查找
   2）二分查找的注意事项和通向公式可以在题目Offer 53 中有详解。

5. 查找算法（中等）（√）

5.1 剑指 Offer 04. 二维数组中的查找

1. 题目说明
   
2. 代码展示

class Solution {
    
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
    
        //从右上角看，这其实就是个二叉搜索树
        //0)特殊情况
        if(matrix.length==0 || matrix[0].length==0) return false;
        
        //1）起始位置
        int hang=matrix.length;
        int lie=matrix[0].length;
        int start=matrix[0][lie-1];
        int i=0;
        int j=lie-1;
        while(i>=0 &&i<hang && j>=0 &&j<lie){
    
            if(matrix[i][j]==target){
    
                return true;
            }else if(matrix[i][j]<target){
    
                i++;
            }else{
    
                j--;
            }
        }
        return false;
    }
}

3. 注意事项
   1）有序的数组，那么就需要使用二分搜索，这里从右上角看，是一个二叉搜索树的样子。

5.2 剑指 Offer 11. 旋转数组的最小数字（没写出来）

3. 注意事项
   1）有序的数组，那么就需要使用二分搜索。

5.3 剑指 Offer 50. 第一个只出现一次的字符

1. 题目说明
   
2. 代码详解
   1）如果元素有限，可以直接使用数组进行存放数据，然后再根据顺序查找

class Solution {
    
    public char firstUniqChar(String s) {
    
        //只包含小写字母，故只有26个字母
        //0)特殊情况
        if(s.length()==0) return ' ';
        
        //1.) 每一个空格对应一个字符的计数器
        int[] data=new int[26];
        for(int i=0;i<s.length();i++){
    
            int temp= s.charAt(i)-'a'+0;
            data[temp]++;
        }

        //2)遍历的方式：从s开始遍历
        for(int i=0;i<s.length();i++){
    
            int temp= s.charAt(i)-'a'+0;
            if(data[temp]==1) return s.charAt(i);
        }
        return ' ';

    }
}

4. 如果需要查找的元素个数有限， 尽量使用数组，因为更方便。

6. 搜索与回溯算法（简单）

6.1 剑指 Offer 32 - I. 从上到下打印二叉树

6.2 剑指 Offer 32 - II. 从上到下打印二叉树 II

6.3 剑指 Offer 32 - III. 从上到下打印二叉树 III

7. 搜索与回溯算法（简单）

7.1 剑指 Offer 26. 树的子结构

7.2 剑指 Offer 27. 二叉树的镜像

7.3 剑指 Offer 28. 对称的二叉树

8. 动态规划（简单）（√）

8.1 剑指 Offer 10- I. 斐波那契数列

2. 代码展示

class Solution {
    
    //采用动态规划：使用一个矩阵
    public int fib(int n) {
    
        if(n<=1) return n;
        //确定dp数组的含义
        int[] dp=new int[n+1];
        //初始化
        dp[0]=0;
        dp[1]=1;
        //遍历顺序+递推公式
        for(int i=2;i<=n;i++){
    
            dp[i]=dp[i-1]+dp[i-2];
        }
        System.out.println("dp[n]="+Arrays.toString(dp));
        return dp[n];
    }
}

3. 注意事项
   1）对特殊的情况，需要先考虑，因为不满足迭代表达式。

8.2 剑指 Offer 10- II. 青蛙跳台阶问题

2. 代码展示

class Solution {
    
    public int numWays(int n) {
    
        //这个问题和爬楼梯问题是一样的。
        //迭代表达式：dp[n]=dp[n-1]+dp[n-2];
        //斐波那契数列的另一种表达式
        //一定要考虑边界情况
        //1)特殊情况
        if(n <=1) return 1;
        //2)一般情况
        int dp[] =new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
    
            dp[i]=(dp[i-1]+dp[i-2])%1000000007;
        }
        return dp[n];

    }
}

3. 注意事项
   1）取模要乘早。

8.3 剑指 Offer 63. 股票的最大利润

class Solution {
    
    public int maxProfit(int[] prices) {
    
        //把动规的迭代式想清楚：可以自己举一个例子的
        //特殊情况：
        if(prices.length==0) return 0;
        int n=prices.length-1;
        int[] dp=new int[n+1];
        int min=prices[0];
        dp[0]=0;

        //遍历循环
        for(int i=1;i<=n;i++){
    
            dp[i]=Math.max(dp[i-1],prices[i]-min);
            //更新最小值
            if(prices[i]<min) min=prices[i];
        }
        //输出
        return dp[n];
    }
}

9. 动态规划（简单）（√）

9.1 剑指 Offer 42. 连续子数组的最大和

2. 代码展示

class Solution {
    
    public int maxSubArray(int[] nums) {
    
        //先记录开始位置，如果之和存在负数情况，那么就重新选择开始位置
        int sum=0;
        int max=nums[0];
        for(int i=0;i<nums.length;i++){
    
            sum+=nums[i];
            //1)更新最大值
            max=sum>max?sum:max;
            //2)如果小于0，那么就重置
            if(sum<0) sum=0;
        }
        return max;
    }
}

3. 注意事项
   1）主要思想掌握：就是如果之前的和为负数，那么就重置开始位置。

9.2 剑指 Offer 47. 礼物的最大价值（√）

2. 代码展示

class Solution {
    
    public int maxValue(int[][] grid) {
    
        //这其实就是一个二维dp问题
        int hang=grid.length;
        int lie=grid[0].length;
        int[][] dp=new int[hang][lie];
        //初始化
        dp[0][0]=grid[0][0];
        for(int i=0;i<hang;i++){
    
            for(int j=0;j<lie;j++){
    
                if(i==0 && j!=0) dp[i][j]=grid[i][j]+dp[i][j-1];
                if(i!=0 && j==0) dp[i][j]=grid[i][j]+dp[i-1][j];
                if(i!=0 && j!=0) dp[i][j]=grid[i][j]+Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[hang-1][lie-1];
    }
}

4. 注意事项
   1）找好步骤与步骤之间的关联就好

10. 动态规划（中等）

10.1 剑指 Offer 46. 把数字翻译成字符串

10.2 剑指 Offer 48. 最长不含重复字符的子字符