剑指offer刷题记录

剑指offer刷题笔记—-JAVA版本

[toc]

树

题目解答中用到的TreeNode类，定义如下：

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

题目解答中用到的TreeLinkNode类，定义如下:

public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }

N叉树的定义

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

递归实现二叉树的前-中-后序遍历

//前序
public void preOrder(TreeNode node)
    {
        if (node != null)
        {
            System.out.print(node.element + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }
//中序
public void inOrder(TreeNode node)
    {
        if (node != null)
        {   
            preOrder(node.left);
            System.out.print(node.element + " ");
            preOrder(node.right);
        }
    }
//后序:
public void posOrder(TreeNode node)
    {
        if (node != null)
        {            
            preOrder(node.left);
            preOrder(node.right);
            System.out.print(node.element + " ");
        }
    }

非递归实现二叉树的前-中-后序遍历

//前序:借助一个栈
public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Stack<TreeNode> s = new Stack<>();
       s.push(root);
       while (!s.empty()){
           TreeNode node = s.pop();
           res.add(node.val);
           if (node.right != null){
               s.push(node.right);
           }
           if (node.left != null){
               s.push(node.left);
           }
       }
       return res;
    }
//=========================================
//前序遍历2
public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Stack<TreeNode> s = new Stack<>();
       while (root != null || !s.empty()){
           while(root != null){
               res.add(root.val);
               s.push(root);
               root = root.left;
           }
           if(!s.empty()){
               TreeNode t = s.pop();
               root = t.right;
           }
       }
       return res;
    }
//中序：借助一个栈
 public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Stack<TreeNode> s = new Stack<>();
     //循环1 2步骤直至栈为空且指针也为空
        while (root != null || !s.empty()){
            //1.不断往左子树深入并不断入栈，直到左叶子的空左孩子
            while (root != null){
                s.push(root);
                root = root.left;
            }
            //2.弹出栈顶元素，将值加入res，并将指针指向它的右孩子
            if (!s.empty()){
                root = s.pop();
                res.add(root.val);
                root = root.right;
            }
        }

        return res;
    }
//后序:后序遍历是 左右根，从右往左依次是根右左，先序遍历是根左右，考虑修改先序遍历之后再调整顺序。
public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null){
            return res;
        }
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        TreeNode node = null;
        while (!s.isEmpty()){
            node = s.pop();
            //注意使用的是头插法，这样的话实现逆序的过程
            res.addFirst(node.val);
            //根据栈 先进后出的特点，根右左，那么入栈的时候用先左再右
            if (node.left != null){
                s.push(node.left);
            }
            if (node.right != null){
                s.push(node.right);
            }
        }
        return res;
    }

N叉树前、后序遍历的递归实现

//前序
 public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        preOrderNT(root,res);
        return res;
    }

    private void preOrderNT(Node node, List<Integer> res) {
        if (node == null){
            return;
        }
        res.add(node.val);
        if (node.children.size() >0){
            for (Node _node:node.children) {
                preOrderNT(_node,res);
            }
        }
    }

//后序
 public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        postOrderNT(root,res);
        return res;
    }

    private void postOrderNT(Node node, List<Integer> res) {
        if (node == null){
            return;
        }
        if (node.children != null && node.children.size() > 0){
            for (Node _node:node.children) {
                postOrderNT(_node,res);
            }
        }
        res.add(node.val);
    }

N叉树前、后序遍历的非递归实现

//前序
public List<Integer> preorder(Node root) {
       List<Integer> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Stack<Node> s = new Stack<>();
        s.push(root);
        Node temp = null;
        while (!s.isEmpty()){
            temp = s.pop();
            res.add(temp.val);
            if (temp.children.size() >0){
                for (int i = temp.children.size() -1;i>=0;i--){
                    //从右往左依次入栈
                   if (temp.children != null){
                       s.push(temp.children.get(i));
                   }
                }
            }
        }
        return res; 
    }

//后序
List<Integer> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Stack<Node> s = new Stack<>();
        s.push(root);
        Node temp = null;
        while (!s.isEmpty()){
            temp = s.pop();
            res.add(temp.val);
            if (temp.children.size() >0){
                for (Node _node:temp.children) {
                    s.push(_node);
                }
            }
        }
        //将res求逆，得到最后的结果
        Collections.reverse(res);
        return res; 

二叉树的深度

题目描述：

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

题目解答：

• 求一棵二叉树的深度，首先写一个私有方法求以node为根节点的树的高度，采用递归的方式实现，关键在于找到递归的终止条件和

public int TreeDepth(TreeNode root) {
         return depth(root);
    }
//返回以node为根节点的树的高度
private int depth(TreeNode node){
    //递归的终止条件 node == null || node.left == null && node.right == null
        if (node == null){
            return 0;
        }else {
            int depth;
            if (node.left == null && node.right == null){
                depth = 1;
            }else{
                int leftDepth = depth(node.left);
                int rightDepth = depth(node.right);
                //以node为根节点的树的深度为左右子树深度的最大值+1
                depth = Math.max(leftDepth,rightDepth)+1;
            }
            return depth;
        }
    }

从上往下打印二叉树

题目描述：

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

题目解答：

• 由题目描述可以知道这里考察的是二叉树的层次遍历

• 利用队列：先进先出的特性，首先将根节点入队;

• 判断当队不为空的时候，队头元素出队，放入list集合，然后将其左孩子入队，然后将其右孩子入队;

• 注意root为空的情况

  public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<Integer>();
          if (root == null){
              return list;
          }
         Queue<TreeNode> queue = new LinkedList<TreeNode>();
         queue.add(root);
          TreeNode topNode;
          while (!queue.isEmpty()){
              topNode = queue.remove();
              list.add(topNode.val);
              if (topNode.left != null){
                queue.add(topNode.left);
              }
              if (topNode.right != null){
                 queue.add(topNode.right);
              }
          }
          return list;
      }

把二叉树打印成多行

题目描述:

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

题目解答：

• 相对于层次遍历的区别在于：每层输出一行；

• 即需要知道每一层的节点个数，将遍历的节点放入list，该行遍历结束之后，将list放入res

• 问题在于如何知道每一层的节点个数？首先知道当前所在层的个数，在遍历当前所在层的时候，计算出下一层的节点个数，当前层遍历结束，更新当前层的节点个数为下一层的节点个数。

  ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
          ArrayList<ArrayList<Integer>> res = new ArrayList<>();
          if (pRoot == null ){
              return res;
          }
          Queue<TreeNode> q = new LinkedList<>();
          q.offer(pRoot);
          //记录每一层的节点个数
          int sum = 1;
          while (!q.isEmpty()){
              ArrayList<Integer> list = new ArrayList<>();
              //当前所在层下一层节点的个数
              int temp = 0;
            while (sum>0){
                TreeNode node = q.remove();
                    list.add(node.val);
                    if (node.left != null){
                        q.offer(node.left);
                        temp++;
                    }
                    if (node.right != null){
                        q.offer(node.right);
                        temp ++;
                    }
                sum --;
            }
            //当前所在层节点操作完成之后，更新sum的值，进行下一层
            sum = temp;
             res.add(list);
          }
          return res;
      }

按之字形顺序打印二叉树

题目描述：

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

题目解答：

• 与把二叉树打印成多行相比，区别在于相邻行的打印顺序不同

• 需要知道当前所在行是第几行，若当前行是偶数行需要对list集合进行顺序调整

  public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
          ArrayList<ArrayList<Integer>> res = new ArrayList<>();
  
          if (pRoot == null){
              return res;
          }
          Queue<TreeNode> q = new LinkedList<>();
          q.offer(pRoot);
          //当前所操作的行数
          int row = 1;
          //每层的节点数
          int sum = 1;
          while (!q.isEmpty()){
              ArrayList<Integer> list = new ArrayList<>();
              //当前所在层的下一层节点的个数
              int temp = 0;
              //遍历当前层的所有节点
              while (sum>0){
                  //将队首元素出队
                  TreeNode node = q.remove();
                  list.add(node.val);
  
                  if (node.left != null){
                      q.offer(node.left);
                      temp++;
                  }
  
                  if (node.right != null){
                      q.offer(node.right);
                      temp ++;
                  }
                  sum--;
              }
              sum = temp;
              if (row % 2 ==0){
                  //当前行是偶数行的的话，需要将获得的list数组调整
                  for (int i = 0,j = list.size()-1;i<j;i++,j--){
                      int t = list.get(i);
                      list.set(i,list.get(j));
                      list.set(j,t);
                  }
              }
              row++;
              res.add(list);
          }
          return res;
  
      }

求给定二叉树的最小深度（LeetCode）

题目描述：

求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量 。

题目解答：

分析：题目中说最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量 。那么什么是最近叶子节点？第一次出现左右子节点都为空的节点为所需要找的节点，此节点为最近叶子节点。如何能最快地找到该节点呢？考虑层次遍历，采用数据结构队列+层次遍历；

//递归
public int run(TreeNode root) {
        return getDepth(root);
    }
private int getDepth(TreeNode node){
    if(node == null){
        return 0;
    }
    if(node.left == null && node.right == null){
        return 1;
    }
    if (node.left == null){
        return getDepth(node.right)+1;
    }
    if (node.right == null){
        return getDepth(node.left)+1;
    }
    return Math.min(getDepth(node.left),getDepth(node.right))+1;
}

//非递归
public int run_1(TreeNode root) {
      if (root == null){
          return 0;
      }
      if (root.left == null && root.right == null){
          return 1;
      }
      Queue<TreeNode> q = new LinkedList<TreeNode>();
      q.offer(root);
      //当前层的深度
      int depth = 1;
      //当前层的个数
        int sum =1;
      while (!q.isEmpty()){
          //下一层的个数
          int temp = 0;
          //遍历当前层的所有节点
          while (sum >0){
              TreeNode node = q.remove();
              sum--;
              if (node.left != null){
                  q.offer(node.left);
                  temp++;
              }
              if (node.right != null){
                  q.offer(node.right);
                  temp++;
              }
              if (node.left == null && node.right ==null){
                  return depth;
              }
          }
          depth++;
          sum = temp;
      }
      return depth;
    }

平衡二叉树

题目描述:

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

题目解答:

• 平衡二叉树的定义：又称AVL树，指的是左子树上的所有节点的值都比根节点的值小，而右子树上的所有节点的值都比根节点的值大（二叉搜索树BST），且左子树与右子树的高度差最大为1。
• 由定义可以知道：需要求出二叉树每个节点的高度，计算每个节点的平衡因子，平衡因子大于1的，此二叉树就不是平衡二叉树，要保证该节点的左右子树都是平衡二叉树，以该节点为根的二叉树才是平衡二叉树。

public boolean IsBalanced_Solution(TreeNode root) {
        return isBalanced_node(root);
     }
//判断以node为根节点的子树是否是平衡的
private boolean isBalanced_node(TreeNode node) {
        if (node == null){
            return true;
        }
        //计算平衡因子
        int balanceFactor = getBalanceFactor(node);
        //如果某节点的平衡因子绝对值>1，该树就不是平衡二叉树
        if (Math.abs(balanceFactor) >1){
            return false;
        }
        return isBalanced_node(node.left) && isBalanced_node(node.right);
    }
//计算二叉树中某个节点的平衡因子：定义为该节点左子树的高度-该节点右子树的高度
private int getBalanceFactor(TreeNode node) {
        return node == null ? 0 : getHeight(node.left) - getHeight(node.right);
    }
//计算二叉树中某个节点的高度：
private int getHeight(TreeNode node) {
        if (node == null){
            return 0;
        }else {
            int height ;
            //若该节点无左右孩子，该节点高度为1
            if (node.left == null && node.right == null){
                height = 1;
            }else {
                //分别递归计算该节点左右孩子的高度
            int leftHeight = getHeight(node.left);
            int rightHeight = getHeight(node.right);
                //该节点的高度为左右孩子中高度最大值+1
            height = Math.max(leftHeight,rightHeight)+1;
            }
            return height;
        }
    }

重建二叉树

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

题目解答：

前序遍历：根左右

中序遍历：左右根

前序遍历序列的第一个字符就是二叉树的根，在中序遍历序列中，找到该字符所对应的位置，该字符左侧所有字符为该二叉树的左子树字符，右侧所有字符为该二叉树的右子树字符；在前序遍历序列中找到对应的左右子树，递归重建左右子树

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre == null || pre.length ==0|| in==null || in.length == 0){
            return null;
        }
    //以前序遍历序列pre的第一个字符创建根节点
        TreeNode root = new TreeNode(pre[0]);
        for (int i = 0;i<in.length;i++){
            //在中序遍历序列中找到根节点所在的位置
            if (in[i] == pre[0]){
//Arrays.copyOfRange(被copy的数组，开始的下标，结束的下标)==>一个新的数组：前闭后开[)底层使用System.arraycopy()
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
                break;
            }
        }
        return root;
    }

二叉树的下一个结点

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

题目解答

分析：

注意给定的结点并不是根节点，故需要先找到根节点，还原整颗二叉树；再进行中序遍历；在中序遍历序列中找到该结点，如果该结点是序列中最后一个，则返回null，否则将其下一个结点返回。

//注意list的位置，若将list写在方法内，则在inOrder方法中也需要传入此参数
static ArrayList<TreeLinkNode> list = new ArrayList<>(); 
public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        TreeLinkNode par = pNode;
        //根据给定的节点还原二叉树
        while (par.next != null){
            par = par.next;
        }
        //对最后的root节点进行中序遍历，放到list数组中
        inOrder(par);
        for (int i = 0;i<list.size();i++){
            if (list.get(i) == pNode){
                return  i ==list.size() -1 ? null:list.get(i+1);
            }
        }
        return null;
    }
    private void inOrder(TreeLinkNode node){
//        左根右
        if (node != null){
            inOrder(node.left);
            list.add(node);
            inOrder(node.right);
        }
    }

二叉树的镜像

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

二叉树的镜像定义：
    源二叉树 
            8
           /  \
          6   10
         / \  / \
        5  7 9 11
    镜像二叉树
            8
           /  \
          10   6
         / \  / \
        11 9 7  5

题目解答

分析：从所给的定义中可以看出，根节点的左右子树互换，其中细化到每个父节点，其左右孩子也要互换。

//非递归写法，借助栈这一数据结构
import java.util.Stack;
public class Solution {
    public void Mirror(TreeNode root) {
         if (root == null){
            return;
        }
        if (root.left == null && root.right == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            //交换给节点的左右孩子
            TreeNode temp =node.left;
            node.left = node.right;
            node.right = temp;

            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }

        }
    }
}
//递归写法
public void Mirror(TreeNode root) {
        root = mirror(root);
    }
private TreeNode mirror(TreeNode node){
    if (node == null){
        return node;
    }
    if (node.left == null && node.right == null){
        return node;
    }
    TreeNode tempNode = node.left;
    node.left = node.right;
    node.right = tempNode;
    if (node.left != null){
        node.left = mirror(node.left);
    }
    if (node.right != null){
        node.right = mirror(node.right);
    }
    return node;
}

对称的二叉树

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

题目解答

分析：判断二叉树是不是对称的，根据定义可知，就是要判断该二叉树除了根节点之外的其他节点是镜像的且对应结点的值还要相等。

boolean isSymmetrical(TreeNode pRoot)
    {
        if (pRoot == null){
            return true;
        }
        return isMirror(pRoot.left,pRoot.right);
    }
//判断两个节点是否是镜像的且值要相等
private boolean isMirror(TreeNode node1,TreeNode node2){
        if (node1 == null || node2 == null){
            if (node1 == null && node2 == null){
                return true;
            }else {
                return false;
            }
        }
        return node1.val == node2.val &&(isMirror(node1.left,node2.right))&&(isMirror(node1.right,node2.left));
    }

序列化二叉树

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为”1,”，然后通过自己的函数来解析回这个二叉树

题目解答

String Serialize(TreeNode root) {
        if (root == null){
            return "#";
        }else {
            return root.val +","+Serialize(root.left)+","+Serialize(root.right);
        }
    }
int index = -1;
TreeNode Deserialize(String str) {
    //将序列化之后的序列用，分割转化成数组
    String[] s = str.split(",");
    index ++;
    int len = s.length;
    if (index > len){
        return null;
    }
    TreeNode node = null;
    if (!s[index].equals("#")){
        node = new TreeNode(Integer.parseInt(s[index]));
           node.left = Deserialize(str);
        node.right = Deserialize(str);
    }
    return node;
}

二叉搜索树的第k个结点

题目描述：

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

题目解答：

分析：

题目中给定的是一棵二叉搜索树：所有节点的左孩子<根<右孩子；再想二叉搜索树的中序遍历（左根右）所得的序列是从小到大排序的，故可得第k小的结点的值。

TreeNode KthNode(TreeNode pRoot, int k)
    {
        if (pRoot == null){
            return null;
        }
        ArrayList<TreeNode> ans = new ArrayList<>();
        inOrder(pRoot,ans);
        //如果中序遍历序列所得个数小于k，则得不到第k小的值
         if (ans.size()<k||k==0){
            return null;
        }else {
           return ans.get(k-1);
        }
    }
    //中序遍历，注意参数
    private void inOrder(TreeNode node,ArrayList<TreeNode> list){
        if (node != null){
        inOrder(node.left,list);
        list.add(node);
        inOrder(node.right,list);
        }
    }

数据流中的中位数

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

题目解答

    //中位数的左区间，大顶堆
    private PriorityQueue<Integer> queue1 = new PriorityQueue<>(((o1,o2)->(o2-o1)));
    //中位数的右区间。默认是小顶堆
    private PriorityQueue<Integer> queue2 = new PriorityQueue<>();
    //数据流中的个数
    private  int sum = 0;
    public void Insert(Integer num) {
        if (sum % 2 == 0){
            //如果两个堆元素个数一样的时候，此时新增一个元素，放入大顶推（左区间）
            queue1.add(num);
        }else {
            queue2.add(num);
        }
        //sum初始值为0，那么queue1中肯定有值
        if (!queue2.isEmpty() && queue1.peek() > queue2.peek()){
            //如果大顶堆的堆顶>小顶堆的堆顶，需要交换
            int temp1 = queue1.poll();
            int temp2 = queue2.poll();
            //取出queue1、queue2的堆顶值，将大（小）顶堆的堆顶添加入小（大）顶堆，
            queue1.add(temp2);
            queue2.add(temp1);
        }
        sum++;
    }

    public Double GetMedian() {
        if (sum % 2 == 1){
            return (double)queue1.peek();
        }else {
            return (queue1.peek() + queue2.peek())/2.0;
        }
    }

二叉树中和为某一值的路径

题目描述：

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

题目解答：

分析：

题目中关于路径的定义—从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。树的前中后序遍历，只有前序遍历是从根结点开始遍历的，故借助二叉树的前序遍历；

• 前序遍历访问某一结点，把该结点添加到路径上，并用目标值减去该结点的值

• 如果该结点为叶节点并且目标值减去该节点的值为0，则把该路径添加进res数组

• 若该节点是非叶子节点，继续访问子节点，访问结束后，递归函数将自动回到它的父结点

• 在函数退出之前要在路径上删除当前节点，以确保返回父结点时路径刚好是从根节点到父结点的的路径

    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> temp = new ArrayList<Integer>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
         if (root == null){
            return res;
        }
        target -= root.val;
        temp.add(root.val);

        if (target == 0 && root.left == null && root.right ==null){
            ////必须重新生成一个对象实例，并使用temp对其初始化赋值，不可以直接使用temp：list本质是 引用，在每次遍历中，会直接改变它的值，最后的路径会被后面的覆盖
            res.add(new ArrayList<Integer>(temp));
        }else {
            FindPath(root.left,target);
            FindPath(root.right,target);
        }
        //当前节点为叶子节点或者已经访问过的情况下，回溯到父结点
        temp.remove(temp.size()-1);
        return res;
    }

链表

链表中倒数第K个结点

题目描述：

输入一个链表，输出该链表中倒数第k个结点。

题目解答：

分析：1.先遍历一遍链表，计算链表的长度n，这样就可以计算出要找的第n-k个元素，再遍历一遍链表即可；

2.使用快慢指针减少一次遍历，两个指针间隔一定的距离，移动速度相同 ，快指针先前进k个元素，然后两个指针同样速度前进，当快指针到达链表尾部时，慢指针正好到达链表的倒数第K个结点；

public ListNode FindKthToTail(ListNode head,int k) {
        if (head == null || k<=0){
            return null;
        }
        ListNode first = head;
        ListNode second = head;
        for (int i =0;i<k;i++){
             if (first == null){
                return null;
            }
            first = first.next;
        }
        while (first != null){
            first = first.next;
            second = second.next;
        }
        return second;
    }

leetCode 19 Remove Nth Node From End of List

题目描述：

Given a linked list, remove the n-th node from the end of list and return its head.

题目解答：

分析：1.这个题目是要求找到倒数第n个结点还需要将其删除；删除某一结点，需要找到待删除结点的前一个结点，通常情况下遇到要找带操作结点的前一个结点，需要借助虚拟头结dummyHead，同样适用快慢指针，经过while循环结束之后，second之前了待删除结点的前一个结点，改变其next的指向即可。

2.若不借助虚拟头结点，可尝试将慢指针变成prev=null和curr=head两个指针。

注意：题目表明n的取值一定是合法的，那么就不需要合法性检测，但是在面试中遇到的话，就要考虑n的不合法的情况

public ListNode removeNthFromEnd(ListNode head, int n) {
      ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode first = dummyHead;
        ListNode second = dummyHead;
        //the gap betwwen first and second is n nodes apart; n+1
        for (int i = 0;i<=n;i++){
            first = first.next;
        }
        while (first != null){
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummyHead.next;
}

反转链表

题目描述：

输入一个链表，反转链表后，输出新链表的表头。

题目解答：

分析：通常会要求不能创建新的链表结点，只能在原有结点上修改链表指针，具体思路就是将链表第一个结点的next置为null，将其他结点的next指向前一个结点，那么需要用到pre这个指针，cur遍历链表中的结点，注意其初始值应为null。

 public ListNode ReverseList(ListNode head) {
         if (head == null){
             return null;
         }
         ListNode pre = null;
         ListNode cur = head;

         while (cur != null){
             ListNode p = cur.next;
             cur.next = pre;
             pre = cur;
             cur = p;
         }
         return pre;
    }

从尾到头打印链表

题目描述：

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

题目解答：

分析：1.可以将链表逆序之后，再遍历整个链表；

2.借助栈这一数据结构，利用其先进后出的特性；

//将链表逆序
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode reverseNode = reverse(listNode);
        while (reverseNode != null){
            list.add(reverseNode.val);
            reverseNode = reverseNode.next;
        }
        return list;
    }
    private ListNode reverse(ListNode listNode){
        if (listNode == null){
            return null;
        }
        ListNode pre = null;
        ListNode cur = listNode;
        while (cur != null){
            ListNode p = cur.next;
            cur.next = pre;
            pre = cur;
            cur = p;
        }
        return pre;
    }

LeetCode 141. Linked List Cycle

题目描述：

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

题目解答：1.借助Set、HashMap等数据结构，判断结点出现过的次数；

2.使用快慢指针，不适用额外空间；让快指针一次前进两个结点（为什么快指针不一次性前进是三个呢？是为了最快追上慢指针），慢指针一次前进一个节点。当快慢指针都进入环路时，快指针会将慢指针”套圈“，追上慢指针。

public boolean hasCycle(ListNode head) {
       if (head == null || head.next == null){
            return false;
        }

        ListNode first = head;
        ListNode seconed = head;
       while (first != null && first.next != null){
           first = first.next.next;
           seconed = seconed.next;
           if (first == seconed){
               return true;
           }
       }
       return false;
    }

链表中环的入口结点

题目描述：

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

题目解答：

分析：1.借助HashMap这一数据结构，若链表中环的入口结点是HashMap中第一个出现2次的结点；

public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        HashMap<ListNode,Integer> map = new HashMap<>();
        while (pHead != null){
            map.put(pHead,map.getOrDefault(pHead,0)+1);
            if (map.get(pHead) == 2){
                return pHead;
            }
            pHead = pHead.next;
        }
        return null; 
    }

删除链表中重复的结点

题目描述：

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

题目解答：

分析：注意题目中给的是排序的链表；

public ListNode deleteDuplication(ListNode pHead)
    {
        ListNode ans = pHead;
        //1.确定最终链表的头节点(2->2->3->4，这种的话头结点就不是所给的头节点)
        while (ans != null){
            //如果ans.next节点不为空，且ans 与ans.next的节点值相等
            if (ans.next != null && ans.val == ans.next.val){

                int temp = ans.val;
                //寻找重复之后 第一个不重复的结点
                while (ans != null && ans.val == temp){
                    ans = ans.next;
                }
            }else {
                //当前ans所指的结点就是我们最终链表的头结点
                break;
            }
        }
        //1 -> 1 -> 1 -> 1这种情况下，ans会出现为null的情况
        if (ans == null){
            return null;
        }
        //判断从ans到链表的尾部，判断每一个节点是否为重复节点
        ListNode lastNode = ans;
        //遍历剩余结点的变量
        ListNode removeNode = lastNode.next;
        while (removeNode != null){
           if (removeNode.next != null && removeNode.val == removeNode.next.val){
               int temp = removeNode.val;
               while (removeNode != null && removeNode.val == temp){
                   removeNode = removeNode.next;
               }
           }else {
               lastNode.next = removeNode;
               lastNode = removeNode;
               removeNode = removeNode.next;
           }
        }
        lastNode.next = null;
        return ans;
    }

合并两个排序的链表

题目描述：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

题目解答：

分析：新建一个新的结果链表result，并定义一个cur变量遍历该链表；while循环先判断list1与list2是否都不为空，若都不为空进入while循环，比较list1与list2链表各个结点值的大小，放到result链表中，如果不满足while循环，说明list1和list2里有一个是空的，那么直接将不为空的结点挂在result链表上即可。

public ListNode Merge(ListNode list1,ListNode list2) {
//       以下是list1和list2均不为空
       ListNode result = new ListNode(-1);
       ListNode cur = result;
       while (list1 != null && list2 != null){
           if (list1.val < list2.val){
//               先将list1与之后的结点断开
               ListNode temp1 = list1.next;
//               将list1放到result里面
               cur.next = list1;
//               将list1指向原list1的next结点
               list1 = temp1;
           }else {
               ListNode temp2 = list2.next;
               cur.next = list2;
               list2 = temp2;
           }
           //               移动cur结点
               cur = cur.next;
       }
//       while循环 当list1/list2还有元素，此时不能进入循环中了，直接将剩下的挂在cur的next上
       if (list1 != null ){
           cur.next = list1;
       }
       if (list2!= null){
           cur.next = list2;
       }
       return result.next;

    }

LeetCode 146. LRU Cache

题目描述：

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

题目解答：

分析：LRU 算法-一种缓存淘汰策略；认为最近使用过的数据应该是有用的，很久没有使用过的数据应该是无用的，内存满了就优先删除那些很久没用过的数据；

题目的意思是：要接收一个 capacity 参数作为缓存的最大容量，然后实现两个方法，一个是 put(key, val) 方法存入键值对，另一个是 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1。注意，题目要求get和put的时间复杂度均为O(1)，这样的话对于查找、插入、删除都要快，且存储的内容要有顺序[判断是否最近使用过]；

充分考虑链表及HashMap的优缺点，选择使用双向链表+HashMap实现

class LRUCache {
    //双向链表中每个结点的结构
     class ListNode{
        int key;
        int value;
        ListNode prev;
        ListNode next;
        public ListNode(int key,int value){
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }
    //构建双向链表，并实现在双向链表头部插入元素以及删除链表的最后一个元素
    class DoubleList{
        //虚拟头尾结点
        private ListNode head,tail;
        private int size;
        public DoubleList(){
            head = new ListNode(0,0);
            tail = new ListNode(0,0);
            head.next = tail;
            tail.prev = head;
            size = 0;
        }

        /**
         * 从链表头部添加节点node
         */
        public void addFirst(ListNode node){
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
            size++;
        }

        /**
         * 删除链表中的node结点
         * @param node
         */
        public void remove(ListNode node){
            node.prev.next = node.next;
            node.next.prev = node.prev;
            size --;
        }

        /**
         * 删除链表中最后一个结点，并返回该结点
         */
        public ListNode removeLast(){
            //此时双向链表为null
           if (tail.prev == head){
               return null;
           }
           ListNode removeNode = tail.prev;
           remove(removeNode);
           return removeNode;

        }

        public int getSize(){
            return size;
        }
    }

    private HashMap<Integer,ListNode> map ;
    private DoubleList cache;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    /**
     * 先去map中查，如有，需要将cache中将数据提前，直接返回
     * @param key
     * @return
     */
    public int get(int key) {
        if (!map.containsKey(key)){
            return -1;
        }
        int val = map.get(key).value;
        put(key,val);
        return val;
    }

    public void put(int key, int value) {
        ListNode node = new ListNode(key, value);
        if (map.containsKey(key)){
            //删除该结点，并将该结点提到链表头部
            cache.remove(map.get(key));
            cache.addFirst(node);
            map.put(key,node);
        }else {
            //map中没有的话，就要加入cache中
            if (capacity == cache.size){
                //如果cache满了，就要删除链表最后一个结点，
                ListNode last = cache.removeLast();
                //还需要将map中映射该该结点的key同时删除
                map.remove(last.key);
            }
            //如果没满就要加入链表头部
            cache.addFirst(node);
            map.put(key,node);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

数组

第一次只出现一次的字符

哈希表O(1)时间内查找到某一元素

数组中出现次数超过一半的数字

旋转数组的最小数字

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

题目解答：

分析：

根据题目把递增排序数组最开始的若干个元素搬到数组的末尾，因此第一个数字总是大于或者等于最后一个数字；特例：如果把排序数组的前面的0个元素搬到后面，即排序数组本身，这仍然是数组的一个旋转;因此若第一个数字小于最后一个数字，直接返回第一个数字即可。

1.由于输入的是一个非递减排序的数组的一个旋转，那么找到第一个arr[i-1]>arr[i]，返回arr[i]即可，arr[i]即为最小值；若无，则返回arr[0];

2.二分查找O（logn）

用两个指针分别指向数组的第一个元素和最后一个元素，查找中间元素，将中间位置元素与第一个元素和最后一个元素比较，确定该元素位于哪一个递增序列；若三个元素大小相等，无法判断中间的数字是位于前面的子数组还是后面的子数组，也就无法移动两个指针来缩小查找的范围，此时不得不采用顺序查找。

要求在排序的数组（或部分排序的数组）中查找一个数字或者同级某个数字出现的次数尝试使用二分查找算法[前提是有序]。

public int minNumberInRotateArray(int [] array) {
        if (array == null || array.length == 0){
            return 0;
        }
        for (int i = 1;i<array.length;i++){
            if (array[i] < array[i-1]){
                return array[i];
            }
        }
        return array[0];
    }

二维数组中的查找

题目描述：

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

题目解答：每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序选择从二维数组arr[M][N]的右上角arr[0][N-1]开始遍历，若arr[i][j]=target,返回true；若arr[i][j]<target，跳出内层循环，往下遍历，进行i++；若arr[i][j]>target，往左遍历，进行j–;

public boolean Find(int target, int [][] array) {
        for (int i = 0;i<array.length;i++){
            for (int j = array[i].length-1;j>=0;j--){
                if (target == array[i][j]) {
                    return true;
                }else if (target > array[i][j]){
                    break;
                }
            }
        }
        return false;
    }

数组中的逆序对

题目描述：

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

题目保证输入的数组中没有的相同的数字数据范围：    对于%50的数据,size<=10^4    对于%75的数据,size<=10^5    对于%100的数据,size<=2*10^5

题目解答：

 private long sum;
    public int InversePairs(int [] array) {
        sum = 0;
        if (array.length == 0){
            return 0;
        }
        int l = 0;
        int r = array.length-1;
        divide(array,l,r);
        return (int)(sum%1000000007);
    }

    private void divide(int[] array, int l, int r) {
        if (l != r) {
            int mid = l + (r - l) / 2;
            divide(array, l,mid);
            divide(array, mid+1,r);
            merge(array,l,r,mid);
        }
    }

    private void merge(int[] array, int l, int r, int mid) {
        //左区间的起点
        int i = l;
        //右区间的起点
        int j = mid+1;
        int[] temp = new int[r-l+1];
        int index = 0;
        //如果见到这种条件，一定要考虑循环结束之后，其中一个还符合自己的条件
        while (i<=mid && j<= r){
            if (array[i] > array[j]){
                temp[index++] = array[j++];
                //左区间的i位置上的值大于右区间j位置上的值，那么左区间的所有值与右区间j位置上的值都构成逆序对
                sum += mid-i+1;
            }else {
                temp[index++] = array[i++];
            }
        }
        while (i<=mid){
            temp[index++] = array[i++];
        }
        while (j<=r){
            temp[index++] = array[j++];
        }
        index = 0;
        for (int k =l;k<=r;k++){
            array[k] = temp[index++];
        }

    }

栈和队列

用两个栈实现队列

题目描述：

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

题目解答：

• 使用栈1完成队列的入队操作
• 队列（先进先出），使用栈2入栈栈1出栈的序列，从而栈2出栈即可完成队列的出队操作

    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
          stack1.push(node);
    }

    public int pop() {
     if (stack2.isEmpty()){
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

堆

最小的k个数

题目描述：

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

题目解答：

分析：1.适合大数据量：题目需求为找出n个整数中最小的k个数，考虑使用小顶堆，选k个元素组成一个小顶堆，那么遍历剩下的n-k个元素的时候，如果当前遍历元素大于堆顶元素，该元素还需要继续与小顶堆内的其他元素比较，最差的情况是最初的k个元素就是n个整数中最小的k个数，那么该元素与小顶堆内最后一个元素比较完，该元素大于小顶堆内所有的元素，那么这次比较就是徒劳的，这样性能非常差；考虑使用大顶堆，如果当前遍历的元素大于堆顶元素，直接进行下一个遍历，如果当前遍历元素小于堆顶元素，用该元素替换堆顶元素，再进行大顶堆的调整。

2.考虑使用快速排序的分区函数，分区函数返回基准数的下标index，分区之后，左边的数字均小于或等于基准数，右边的均大于基准数，判断index和k的关系，当index!=k-1的时候，判断若index>k，则需要缩小范围；若index<k，则需要扩大范围；

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //如果k>n or k==0，那么就无法找出最小的k个数，根据方法所需的返回类型返回即可
        if (k > input.length || k==0){
            return new ArrayList<>();
        }
        //用数组去模拟k个节点的堆结构
        int[] maxHeap = new int[k];
        //初始化堆中元素
        //public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)：其中src-原数组，srcPos-从原数组的该位置开始，dest-目标数组，destPos-从目标数组的该位置开始，length-要copy的长度
        System.arraycopy(input,0,maxHeap,0,k);
        //从非叶子节点开始，调整堆
        for (int i = k/2-1;i>=0;i--){
            initiate(i,maxHeap,k);
        }
        //遍历len-k个元素
        for (int i = k;i<input.length;i++){
            if (input[i] < maxHeap[0]){
                //当前位置的值小于大顶堆堆顶位置的值
                //将当前值更新大顶堆堆顶，从堆顶元素开始调整堆
                maxHeap[0] = input[i];
                initiate(0,maxHeap,k);
            }
        }
        //将大顶堆的节点元素进行升序操作
        //将堆顶元素和最后一个元素交换，将除最后一个元素外的大顶堆进行堆维护，重复进行
        for (int i = maxHeap.length-1;i>0;i--){
            int temp = maxHeap[i];
            maxHeap[i] = maxHeap[0];
            maxHeap[0] = temp;
            initiate(0,maxHeap,i);
        }
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0;i<maxHeap.length;i++) {
            ans.add(maxHeap[i]);
        }
        return ans;
    }
    //从index位置开始，将maxHeap数组内的元素调整为大顶堆
    private void initiate(int index, int[] maxHeap, int length) {
        int temp = maxHeap[index];
        //k的初始值是从index的左孩子开始的，k=k*2+1:是找左孩子
        for (int k = index * 2 +1;k<length;k=k*2+1){
            //这里体现如果右孩子大于左孩子的话，k++找到右孩子
            if ((k+1) <length && maxHeap[k+1]>maxHeap[k]){
                k++;
            }
            if (maxHeap[k] > temp){
                //如果当前k即（左右孩子中的一个）>根节点，
                maxHeap[index] = maxHeap[k];
                //更新index的值，代表temp数字最终在堆中的位置，temp的值始终不变
                index=k;
            }else {//此时对应根节点大于左右孩子，就没有必要进行调整
                break;
            }
        }
        //找到最终位置，才进行值的更新
        maxHeap[index] = temp;
    }

动态规划

知识点

• 动态规划问题的一般形式就是求最值——比如：最长递增子序列，最小编辑距离；

• 求解动态规划的核心问题就是穷举；

  动态规划的穷举是有特点的，因为这类问题存在重叠子问题，如果暴力穷举的话效率会很低，所以需要备忘录/dp table来优化穷举过程，避免不必要的计算；

• 动态规划问题一定具备最优子结构，才能通过子问题的最值得到原问题的最值；

  最优子结构要求子问题间必须相互独立

• 列出正确的状态转移方程进行正确地穷举；

  • 先确定状态

  比如斐波那契数列中；把f(n)想做一个状态n，这个状态n是由状态n-1和状态n-2相加转移而来的

  • 确定dp函数的定义
  • 确定选择并择优
  • 明确base case

重叠子问题、最优子结构、状态转移方程是动态规划的三要素；

• 动态规划是自底向上，从最底下、最简单、问题规模最小的开始往上推

• 常用方法：

  • 暴力递归：递归算法的时间复杂度=子问题个数乘以一个子问题需要的时间；

  • 带备忘录的递归解法[自顶向下]：

  每次算出某个子问题的答案后，先记录到备忘录中，每次遇到子问题先去备忘录里查一查，若之前已经解决过了，直接把答案拿出来用，不需要耗时计算；

  • dp数组的迭代解法[自底向上]：

    优化——根据斐波那切数列状态转移方程，当前状态只有之前的两个状态有关系，所以可以不需要很大的DP数组存储所有的状态，只需要存储之前的两个状态就行了；将空间复杂度降低为O(1)。

分糖果

题目描述：

有N个小朋友站在一排，每个小朋友都有一个评分

你现在要按以下的规则给孩子们分糖果：

• 每个小朋友至少要分得一颗糖果
• 分数高的小朋友要他比旁边得分低的小朋友分得的糖果多

你最少要分发多少颗糖果？

题目解答：

分析：每个小朋友至少要分得一颗糖果，则candy[i]初始化为1

先从左向右遍历：如果当前位置的分数比前一个位置的分数高，则当前位置糖果数比前一个位置的糖果数多1；

再从右向左遍历：如果当前位置的分数比后一个位置的分数高，并且当前位置的糖果数小于等于后一个位置的糖果数，则当前位置的糖果数比后一个位置的糖果数多1。

public int candy(int[] ratings) {
         if (ratings == null){
            return 0;
        }
        if (ratings.length<2){
            return ratings.length;
        }
        int res = 0;
        //每个小朋友分得至少一颗糖果
        int[] candy = new int[ratings.length];
        for (int i =0;i<candy.length;i++){
            candy[i] = 1;
        }
        //从左向右遍历，ratings[j]>ratings[j-1]则candy[j] = candy[j-1]+1
        for (int j = 0;j<ratings.length-1;j++){
            if (ratings[j] < ratings[j+1]){
              candy[j+1] = candy[j] + 1;
            }
        }
        //从右向左遍历，ratings[k-1] > ratings[k] && candy[k-1] <= candy[k],candy[k-1] = candy[k]+1
        for (int k = ratings.length - 1;k>0;k--){
            if (ratings[k] < ratings[k-1] && candy[k-1] <= candy[k]){
                candy[k-1] = candy[k]+1;
            }
        }
       for (int i = 0;i<candy.length;i++){
            res += candy[i];
       }
       return res;
    }

斐波那契数列

题目描述：

现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

n<=39

题目解答：

public int Fibonacci(int n) {
         if (n<=1){
            return n;
        }
        return Fibonacci(n-1)+Fibonacci(n-2); 
    }

跳台阶

题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）

题目解答：

public int JumpFloor(int target) {
        if (target == 1){
            return 1;
        }
        if (target == 2){
            return 2;
        }
        int[] dp = new int[target+1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3;i< target+1;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[target];
    }
=========================================
public int JumpFloor(int target) {
        int dp = 0;
        if (target <= 2){
            return target;
        }

        int dp1 = 1;
        int dp2 = 2;
        for (int i = 3;i< target+1;i++){
             dp = dp1+dp2;
             dp1 = dp2;
             dp2 = dp;
        }
        return dp;
    }

变态跳台阶

题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题目解答：

public int JumpFloorII(int target) {
        if (target <=0){
            return 0;
        }
        if (target == 1){
            return 1;
        }
        return 2*JumpFloorII(target-1);
    }

贪心

知识点

贪心算法是动态规划算法的一个特列，相对于动态规划，使用贪心算法需要满足更多的条件；

题目描述：

环形路上有n个加油站，第i个加油站的汽油量是gas[i].

你有一辆车，车的油箱可以无限装汽油。从加油站i走到下一个加油站（i+1）花费的油量是cost[i]，你从一个加油站出发，刚开始的时候油箱里面没有汽油。

求从哪个加油站出发可以在环形路上走一圈。返回加油站的下标，如果没有答案的话返回-1。

注意：

答案保证唯一。

回溯

知识点

解决一个回溯问题，实际上就是一个决策树的遍历过程：只需要考虑三个问题：

• 路径：已经做出的选择；

• 选择列表：也就是你当前可以做的选择；

• 结束条件：也就是到达决策树底层，无法再做选择的条件。

• 回溯算法的框架：

  核心在for循环里面的递归，在递归调用之前做选择，在递归调用之后撤销选择。

  result = []
  def backtrack(路径，选择列表):
      if 满足结束条件:
          result.add(路径)
          return
       for 选择 in 选择列表:
          做选择
          backtrack(路径，选择列表)
          撤销选择

  关于backtrack函数，需要维护走过的路径和当前可以做的选择列表，当触发结束条件时，将路径记入结果集。

• 回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作。

全排列

N皇后问题

字符串

题目描述：

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

题目解答：使用countSpace记录源字符的空格数，计算新字符需要的长度，注意”%20”占两个空格的位置

 public String replaceSpace(StringBuffer str) {
       int lenStr = str.length();
       int countSpace = 0;
       for (int i = 0;i<lenStr;i++){
           if (str.charAt(i) ==' '){
               countSpace ++;
           }
       }
       int len = lenStr + 2*countSpace;
       str.setLength(len);
       int i = lenStr -1;
       int j = len - 1;
       int k = 0;
       while (k < countSpace){
           char ch = str.charAt(i);
           if (ch ==' '){
               str.setCharAt(j--,'0');
               str.setCharAt(j--,'2');
               str.setCharAt(j--,'%');
               k++;
           }else {
               str.setCharAt(j--,ch);
           }
           i--;
       }
       return str.toString();
    }