「剑指Offer系列题解」

剑指Offer_解题记录

• 📝分享和记录做题的思路
• 🧑🏻‍💻本篇包含部分数据结构的基础笔记
• 🦾希望我的代码可以帮到看这篇题解的人　

Commonly Used Class

//Definition of a single-linked list node
public class ListNode {
 int val;
 ListNode next;
 ListNode(int x) { val = x; }
}

public class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

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

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}

Commonly Used Data Structures

HashSet

// HashSet最重要的特性就是：不接受重复的元素，两个元素的比较不是用==而是用equals方法，也就是说Set不接受两个对象
// HashSet的实战例子：找到一个数组中第一个重复的元素	

// 构造方法
HashSet( )//构造一个空的Set，其实HashSet的实例的默认大小是16，加载因子是0.75
HashSet(Collection<? extends E> c)//包含一个Collection中的元素的新set
HashSet(int initialCapacity)//构造一个设定好大小的set
HashSet(int initialCapacity, float loadFactor)//构造一个设定好大小和加载因子的set
  
// HashSet中添加元素
hashset.add("abc");//向hashset中添加一个整数
hashset.add(1);//向hashset中添加一个字符
hashset.add('a');//向hashset中添加一个数组
int[] abc={10,11,12};
hashset.add(abc);//向hashset中添加一个自定义对象
Cat cat1=new Cat("asd", 2);
hashset.add(cat1);//向hashset中添加一个对象

//遍历HashSet
Iterator it = hashset.iterator();
while(it.hasNext())
{
  Object obj = it.next();
  if(obj instanceof Integer)
  {
    System.out.println("Integer:"+obj);
  }
  if(obj instanceof String)
  {
    System.out.println("String:"+obj);
  }
  if(obj instanceof Character)
  {
    System.out.println("Character:"+obj);
  }
  if(obj instanceof int[])
  {
    System.out.print("int[]:");
    for(int i=0;i<abc.length;i++)
    {
      System.out.print(abc[i]+" ");
    }
  }
}

// HashSet常用方法
hashset.add(E e)：//返回boolean型，如果此 set 中尚未包含指定元素，则添加指定元素；如果此 set 已包含该元素，则该调用不更改 set 并返回 false。
//删除元素：
hashset.clear()//从此 set 中移除所有元素。
hashset.remove(Object o)//如果指定元素存在于此 set 中，则将其移除。
hashset.isEmpty()//如果此 set 不包含任何元素，则返回 true。
hashset.contains(Object o)//如果此 set 包含指定元素，则返回 true。
hashset.size()//返回此 set 中的元素的数量（set 的容量）。

String

// 总结String常用的方法

// 常用方法
StringBuilder sb = new StringBuilder();//charAt()方法经常跟StringBuilder一起用
sb.append(String s.charAt(0));
sb.toString();

//1.获取
 1.1：字符串中包含的字符数，也就是字符串的长度。
  int length():获取长度
 1.2：根据位置获取位置上某个字符。
  char charAt(int index)
 1.3：根据字符获取该字符在字符串中的位置。
  int indexOf(int ch):返回的是ch在字符串中第一次出现的位置。
  int indexOf(int ch,int fromIndex):从fromIndex指定位置开始，获取ch在字符串中出现的位置。
  int indexOf(String str):返回的是str在字符串中第一次出现的位置。
  int indexOf(String str，int fromIndex):从fromIndex指定位置开始，获取str在字符串中出现的位置。
 1.4：int lastIndexOf(String str):反向索引。
   
//2.判断
 2.1：字符串中是否包含某一个子串。
      boolean contains(str);
   特殊之处：indexOf(str):可以索引str第一次出现为止，如果返回-1，表示该str不在字符串中存在。
             所以，也可以用于对指定判断是否包含。
       if(str.indexOf("a")!=1)

       而且该方法既可以判断，也可以获取出现的位置。

 2.2：字符串中是否有内容。
      boolean isEmpty():原理就是判断长度是否为0。
 2.3：字符串是否以指定内容开头。
   		boolean startsWith(str);
 2.4：字符串是否以指定内容结尾。
   		boolean endsWith(str);
 2.5：判断字符内容是否相同，复写了object类中的equals方法。
   		boolean equals(str);
 2.6:判断内容是否相同，并忽略大小写。
  		boolean.equalsIgnorecase();

//3.转换
 3.1：将字符数组转成字符串。
  构造函数：String(char[])
      String(char[],offset,count):将字符数组中的一部分转成字符串
 
  静态方法：
     static String copyValueOf(char[]);
     static String copyValueOf(char[] data,int offset,int count);

     static String valueOf(char[]); //也将其他类型的参数转换成string
 
 3.2：将字符串转成字符组
  char[] tocharArray();

 3.3：将字节数组转成字符串。
      String(byte[])
      String(byte[],offset,count):将字节数组中的一部分转成字符串
 
 3.4：将字符串转成字节数组。
  byte[] getBytes()

 3.5:将基本数据类型转成字符串，
 static String valueOf(int)
 static String valueOf(double)

 // 3+"" 与 String.valueOf(3)的值是一样的
 
 特殊：字符串和字节数组在转换过程中，是可以指定编码的。

//4.替换
 String replace(oldchar,newchar);

//5.切割
 String[] split(regex);

//6.子串。获取字符串中的而一部分
 String subString(begin);
 String subString(begin,end);

//7.转换，去除空格，比较。
 7.1：将字符串转成大写或小写
   String toUpperCsae() 大转小
   String toLowerCsae() 小转大

 7.2：将字符串两端的多个空格去除
   String trim();

 7.3：对两个字符串进行自然顺序的比较
   int compareTo(string);

Tree

介绍

树🌲是一种数据结构，用来模拟具有树状结构性质的数据合集。树的每一个节点都有一个值和一个包含所有子节点的列表,树也可以视为一个拥有N个节点和N-1条边的有向无环图。

二叉树是一种更为典型的树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

树有4⃣️种遍历方法：

• 前序遍历特点： 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序
• 中序遍历特点： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序
• 后序遍历特点： 节点按照 [ 左子树 | 右子树 | 跟节点 ] 排序
• 层序遍历

• 先序遍历
  • 判空
  • 访问节点
  • 左孩子入栈（再次从 1 开始执行）
  • 右孩子入栈（再次从 1 开始执行）
• 中序遍历
  • 判空
  • 左孩子入栈
  • 访问节点
  • 右孩子入栈
• 后序遍历
  • 判空
  • 左孩子入栈
  • 右孩子入栈
  • 访问节点
• 遍历分为两种解法 - 递归和迭代

前序遍历

class Solution_144_0{
    //递归解法
    ArrayList<Integer> res = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root!=null){
            res.add(root.val);
            if (root.left!=null) preorderTraversal(root.left); //前序遍历：根左右
            if (root.right!=null) preorderTraversal(root.right);
        }
        return res;
    }
}

class Solution_144_1{
    //迭代解法
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root==null) return new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>(); // 用队列来保存节点，顺序是根左右
        ArrayList<Integer> res = new ArrayList<>(); // 保存节点值

        stack.push(root); // 添加根
        while (!stack.isEmpty()){
            TreeNode node = stack.pop(); //弹出栈顶元素
            res.add(node.val); // 添加值
            if (node.right!=null) stack.push(node.right); // 因为是前序遍历，所以添加完根之后去添加左子树
            if (node.left!=null) stack.push(node.left); // 因为是stack结构，所以右子树先add，放在栈下，左子树放在栈顶
        }
        return res;
    }
}

中序遍历

class Solution_94_0{
    // 中序遍历 迭代做法
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root==null) return new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> res = new ArrayList<>();

        TreeNode cur = root; // 当前节点为root
        while (!stack.isEmpty() || cur!=null){
            while (cur!=null){
                stack.push(cur); // 如果当前节点不为null，则押入栈中
                cur = cur.left; // 并且更新cur节点为当前节点的左子节点
            }
            cur = stack.pop(); // 到达树的最左叶子时，弹出叶子，res添加当前节点的值
            res.add(cur.val);
            cur = cur.right; // 检查当前节点是否有右节点，如果没有则下次循环弹出当前节点的父节点
        }
        return res;
    }
}

class Solution_94_1{
    // 中序遍历 递归做法
    ArrayList<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root!=null){
            if (root.left!=null) inorderTraversal(root.left); // 中序遍历：左根右 先将左子树全部遍历
            res.add(root.val);
            if (root.right!=null) inorderTraversal(root.right);
        }
        return res;
    }
}

后序遍历

class Solution_145_0{
    // 后序遍历 迭代做法
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode last = null;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode temp = stack.peek();
                //是否变到右子树
                if (temp.right != null && temp.right != last) {
                    cur = temp.right;
                } else {
                    list.add(temp.val);
                    last = temp;
                    stack.pop();
                }
            }
        }
        return list;
    }
}

class Solution_145_1{
    // 后序遍历 递归做法
    ArrayList<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root!=null){
            if (root.left!=null) inorderTraversal(root.left);
            if (root.right!=null) inorderTraversal(root.right);
            res.add(root.val);
        }
        return res;
    }
}

class Solution_145_2{
    // 后序遍历 抖机灵做法
    // 利用LinkedList的addFirts方法，每次添加到在队首添加，最后顺序是：左右根
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root==null) return new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        LinkedList<Integer> res = new LinkedList<>()<>();

        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.addFirst(node.val); // 每次添加到队首，所以根被排到最后
            if (root.left!=null) stack.push(node.left); // 左节点押入栈底
            if (root.right!=null) stack.push(node.right); // 右节点先弹出
        }
        return res;
    }
}

层序遍历

public List<List<Integer>> levelOrder(TreeNode root) {
        /*
        整体思路和上一题差不多，不同点在于把每一层的node.val都集中在一个List中
        用for loop来把同一层的node全添加到list中并且把每次循环中
        当前的node的left和right child node全添加到queue中
        结束for loop后用res添加list
         */
        if (root==null) return new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<List<Integer>> res = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            for (int i=queue.size(); i>0;i--){
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left!=null) queue.add(node.left);
                if (node.right!=null) queue.add(node.right);
            }
            res.add(list);
        }
        return res;
}

//前序遍历特点： 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序
//中序遍历特点： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序
//后序遍历特点： 节点按照 [ 左子树 | 右子树 | 跟节点 ] 排序

二叉搜索树（Binary Search Tree）它或者是一棵空树，或者是具有下列性质的二叉树：左子树上所有结点的值均小于它的根结点的值；右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
  
树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）；
  常见的 DFS ： 先序遍历、中序遍历、后序遍历；// 树的DFS通常用 递归 或 栈 来实现
  常见的 BFS ： 层序遍历（即按层遍历）。

Tree

07-重建二叉树

//根据给出的树的前序遍历和中序遍历重构树结构
class Solution_07_0{
    // 解题的原理是：pre order遍历的第一个元素是root 利用这个root到in order遍历分为左子树和右子树，然后左右子树向下递归
    HashMap<Integer, Integer> map = new HashMap<>(); //记录in order遍历
    int[] preorder; // 记录pre order 的数组，递归方法中需要用到

    /**
     * @param preorder 前序遍历数组
     * @param inorder 中序遍历数组
     * @return TreeNode数组
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder; //存入preOrder
        for (int i=0; i<inorder.length;i++)
            // inOrdre元素:index
            map.put(inorder[i],i); //记录中序遍历中每一个元素的index
        return recur(0,0,inorder.length-1); //preRootIndex为0是因为要从preorder的第一个也就是整个树的root开始
    }

    /**
     * @param preRoot 前序遍历中root的索引(index)
     * @param inLeft 中序遍历的左边界
     * @param inRight 中序边界汇总的右边界
     */
    TreeNode recur(int preRoot, int inLeft, int inRight){
        if (inLeft > inRight) return null; //如果左边界大于右边界说明inOrder数组中越界了 直接返回null
        TreeNode root = new TreeNode(preorder[preRoot]); //new一个root的TreeNode对象
        int inRoot = map.get(preorder[preRoot]); //通过前序遍历的index来得到中序遍历中当前元素的index
        //因为已经知道该元素在中序遍历中的index，我们就可以区分出左右子树
        root.left = recur(preRoot+1,inLeft,inRoot-1); //左子树
        // 右子树root在前序遍历中的index = 当前root在前序遍历的index + (当前root在中序遍历中的index-中序遍历左边界)(这个是左子树的长度) +1(再加一)
        root.right = recur(preRoot+(inRoot-inLeft)+1,inRoot+1,inRight); //右子树
        return root;
    }
}

26-树的子结构

class Solution_26_0{
    /**
     * @param A
     * @param B
     * @return 因为给出的AB都是root，所以每一层只需要判断两个root本身的val和左右两个子树
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A==null || B==null) return false; //AB只要有一方是null则
        //先看root是否匹配，在看root的左右子树是否匹配
        return isRootSubStructure(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

    boolean isRootSubStructure(TreeNode A, TreeNode B){
        if (B==null) return true; // 如果B这边往下找都找到null也没有找出不同，则说明是子树
        if (A==null) return false; // 如果A找到null但是B还没有找到null，说明B不是A的子树
        if (A.val!=B.val) return false; //AB的val都不一样 B肯定不是子树
        //如果当前AB相同则往左右子树递归
        return isRootSubStructure(A.left,B.left) && isRootSubStructure(A.right,B.right);
    }
}

27-二叉树的镜像

class Solution_27_0{
    public TreeNode mirrorTree(TreeNode root) {
        if (root==null) return null;
        //将当前root上的左右子树的root互换
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
}

32-1 -从上往下打印二叉树

class Solution_32_1_0{
    public int[] levelOrder(TreeNode root) {
        if (root==null) return new int[]{};
        // 从上到下遍历二叉树，用BFS
        // BFS需要用到queue队列的FIFO先入先出特性
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();
        queue.add(root); // 先把root添加到queue中
        while (!queue.isEmpty()){
            // 在循环中，先把root拿出来，把值存到ArrayList中
            // 如果左右子树不为null，则添加到queue中，继续循环
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left!=null) queue.add(node.left);
            if (node.right!=null) queue.add(node.right);
        }
        int[] res = new int[list.size()];
        // 把List中的值拿出来存到数组中
        for (int i=0;i<res.length;i++)
            res[i] = list.get(i);
        return res;
    }
}

32-2 -从上往下打印二叉树 2

public List<List<Integer>> levelOrder(TreeNode root) {
        /*
        整体思路和上一题差不多，不同点在于把每一层的node.val都集中在一个List中
        用for loop来把同一层的node全添加到list中并且把每次循环中
        当前的node的left和right child node全添加到queue中
        结束for loop后用res添加list
         */
        if (root==null) return new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<List<Integer>> res = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            for (int i=queue.size(); i>0;i--){
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left!=null) queue.add(node.left);
                if (node.right!=null) queue.add(node.right);
            }
            res.add(list);
        }
        return res;
    }

32-3 -从上往下打印二叉树 3

class Solution_32_3_0{
    /*
    请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，
    第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root==null) return new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<List<Integer>> res = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            LinkedList<Integer> list = new LinkedList<>();
            for (int i=queue.size();i>0;i--) {
                TreeNode node = queue.poll();
                if (res.size()%2!=0) {
                    list.addFirst(node.val);
                } else {
                    list.addLast(node.val);
                }
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            res.add(list);
        }
        return res;
    }
}

33-二叉搜索树的后序遍历序列

class Solution_33_0{
    public boolean verifyPostorder(int[] postorder){
        if (postorder.length<=0) return true; // 题目要求如果是空数组 返回true而不是false
        recur(postorder,-,postorder.length-1);
    }

    boolean recur(int[] postorder, int i, int j){
        // j=postorder.length-1 根据后序遍历得知j是根节点

        if (i>=j) return true; // 设置递归终止条件

        int p = i; // 设置一个来找到区分左右子树的index 的 counter
        while (postorder[p]<postorder[j]) p++; // 因为左子树的值小于根节点

        int m = p; // m是区分左右子树的index, (1,m-1)左子树, (m,j-1)右子树
        while(postorder[p]>postorder[j]) p++; // 右子树的节点值大于根节点

        boolean verified = p==j; // 判断当前这个树是否符合二叉搜索树，如果符合，p经历两个while loop就应该到达根节点处
        return verified && recur(postorder,i,m-1) && recur(postorder,m,j-1); // 递归左右子树是否符合二叉搜索树
    }
}

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

class Solution_34_0{
    LinkedList<List<Integer>> res = new LinkedList<>();// 记录每一条path
    LinkedList<Integer> path = new LinkedList<>(); // 记录当前path

    public List<List<Integer>> pathSum(TreeNode root, int sum){
        recur(root,sum);
        return res;
    }

    void recur(TreeNode node,int target){
        // 设置递归条件：如果当前node为null，则递归方法结束
        if (node==null) return;

        target -= node.val; // target减去当前节点上的值来更新target
        path.add(node.val); // path添加当前节点

        if (target==0 && node.left==null && node.right==null){
            res.add(new LinkedList<>(path)); // 如果到达叶子处且target为0说明这条path满足条件，添加到res中
        }

        recur(node.left,target); // 递归左右子树
        recur(node.right,target);

        // 路径恢复：向上回溯，如果当前path加上node.left时target不为0，则删掉node.left回到上一层，并之后尝试node.right
        path.removeLast();
    }
}

36-二叉搜索树与双向链表

class Solution_36_0{
    /*
    将 二叉搜索树 转换成一个 “排序的循环双向链表” ，其中包含三个要素：
    排序链表： 节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点；
    双向链表： 在构建相邻节点（设前驱节点 pre ，当前节点 cur ）关系时，不仅应 pre.right=cur，也应 cur.left=pre
    循环链表： 设链表头节点 head 和尾节点 tail ，则应构建 head.left=tail 和 tail.right=head
     */
    Node pre,head;

    public Node treeToDoublyList(Node root){
        if (root==null) return null;
        dfs(root);
        pre.right = head;
        head.left = pre;
        return head;
    }

    void dfs(Node cur){
        // 设置递归终止条件
        if (cur==null) return;

        dfs(cur.left); //向下递归，已知二叉搜索树的最左下角的node的值是最小，所以用作head

        if (pre==null){
            head = cur; //已知二叉搜索树的最左下角的node的值是最小，所以用作head
        }else {
            pre.right = cur; // 不为null说明不是head，那就正常连接pre和cur
        }
        cur.left = pre; // 双向连接

        pre = cur; //最后更新pre
        dfs(cur.right); // 递归右子树
    }
}

55-1-二叉树的深度

class Solution_55_1_0{
    public int maxDepth(TreeNode root) {
        if (root==null) return 0;
        int depth = 0;
        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(root);
        while (!queue.isEmpty()){
            for (int i=queue.size();i>0;i--){ // for loop将每一层中的节点都弹出 并且加上这些节点的子节点
                TreeNode node = queue.poll();
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
            }
            depth++; // 结束一个for loop代表结束一层 那么深度+1
        }

        return depth;
    }
}

class Solution_55_1_1{
    // DFS 深度优先搜索
    public int maxDepth(TreeNode root) {
        // 设置递归终止条件：到达叶子处的时候（也就是null的时候）返回0
        if (root==null) return 0;
        // 对比左右子树的深度并且加一
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

55-2-平衡二叉树

class Solution_55_2_0{
    // BFS 层序遍历判断是否平衡
    public boolean isBalanced(TreeNode root) {
        if (root==null) return true; // 特殊案例
        // 如果左子树的深度减去右子树的深度的绝对值大于1说明不是平衡则返回false
        boolean balanced = Math.abs(recur(root.left)-recur(root.right))>1 ? false : true;
        return balanced &&  isBalanced(root.left) && isBalanced(root.right); // return 根的判断结果并且递归左子树根和右子树根
    }

    int recur(TreeNode node){
        //设置递归终止条件
        if (node==null) return 0;
        return Math.max(recur(node.left),recur(node.right)) + 1;
    }
}

class Solution_55_2_1{
    // DFS 后序遍历 + 剪枝
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    int recur(TreeNode node){
        if (node==null) return 0; // 递归终止条件
        int left = recur(node.left); // 先从左子树开始递归 如果左子树中任意节点的深度差不超过1则left等于不是-1的int
        if (left==-1) return -1; // left等于-1代表左子树某一节点的深度差超过1，所以不平衡
        int right = recur(node.right); // 同理，递归完左子树就开始递归右子树
        if (right==-1) return -1;
        return Math.abs(left-right) < 2 ? Math.max(left,right)+1 : -1;
    }
}

28-对称的二叉树

class Solution_28_0{
    public boolean isSymmetric(TreeNode root) {
        //如果root根节点为null 直接返回true
        if(root==null) return true;
        return recur(root.left,root.right);
    }

    boolean recur(TreeNode left, TreeNode right){
        //如果左右节点都为null则是对称二叉树
        if(left==null && right==null) return true;
        //如果左右节点中有一个不为null而另一个为null则返回false,或者左右节点的值不同也返回false
        if(left==null || right==null || right.val!= left.val) return false;
        //递归左节点的左右子节点和右节点的左右自节点 用&&连接 来判断是否是对称二叉树
        return recur(left.left, right.right) && recur(left.right, right.left);
    }
}

(困难)37-序列化二叉树

class Solution_37_0{
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(!vals[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
            if(!vals[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

54-二叉搜索树的第k大节点

class Solution_54_0{
    public int kthLargest(TreeNode root, int k) {
        if (root==null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();

        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left!=null) queue.add(node.left);
            if (node.right!=null) queue.add(node.right);
        }
        int[] res = new int[list.size()];
        for (int i=0;i<res.length;i++){
            res[i] = list.get(i);
        }
        Arrays.sort(res);
        return res[res.length-k];
    }
}

LinkedList

06-从尾到头打印链表

import java.util.ArrayList;

public class HeadTailLinkedNode_06 {
    /**
     * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
     * 示例 1：
     *
     * 输入：head = [1,3,2]
     * 输出：[2,3,1]
     */
}

class Solution_06_0{
    //创建一个arraylist来储存从尾到头的element
    ArrayList<Integer> list = new ArrayList<>();

    public int[] reversePrint(ListNode head) {
        recur(head);
        //创建一个list大小的数组
        int[] res = new int[list.size()];
        for (int i=0; i<list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }

    void recur(ListNode node){
        /**
         * 这是一个递归方法
         * 终止条件：当node为null的时候说明已经到尾巴了
         * 当终止递归的时候开始回朔
         * 回朔会从尾巴到头一个一个的通过list.add(node.val)把值加到list中
         */
        if(node == null) return;
        recur(node.next);
        list.add(node.val);
    }
}

22-链表中倒数第k个结点

import java.util.ArrayList;

public class getKthFromEnd_22 {
/**
 * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
 *
 *
 *
 * 示例：
 *
 * 给定一个链表: 1->2->3->4->5, 和 k = 2.
 *
 * 返回链表 4->5.
 */
}

class Solution_22_0{
    /**
     * 这个是递归的解法
     * 通过递归得到一个储存从尾到头的元素的list
     * 然后直接通过index k 来得到答案
     */

    ArrayList<ListNode> list = new ArrayList<>();
    boolean FindOrNot = true;
    int count=0;

    public ListNode getKthFromEnd(ListNode head, int k) {
        //先递归，把element从尾巴到头储存到list中
        recur(head);
        return list.get(k-1);
    }

    void recur(ListNode node){
        /**
         * 递归解决
         * 从尾巴到头依次把element加到list中
         */
        if (node==null) return;
        recur(node.next);
        list.add(node);
    }
}

class solution_22_1{
    /**
     * 这题用双指针
     * 算法流程：
     *
     * 初始化： 前指针 former 、后指针 latter ，双指针都指向头节点 head​ 。
     * 构建双指针距离： 前指针 former 先向前走 kkk 步（结束后，双指针 former 和 latter 间相距 kkk 步）。
     * 双指针共同移动： 循环中，双指针 former 和 latter 每轮都向前走一步，直至 former 走过链表 尾节点 时跳出（跳出后， latter 与尾节点距离为 k−1k-1k−1，即 latter 指向倒数第 kkk 个节点）。
     * 返回值： 返回 latter 即可。
     */

    public ListNode getKthFromEnd(ListNode head, int k) {
        //两个指针最初都指向head
        ListNode former=head, latter=head;
        //先让former指针移动k个位置
        for (int i=0;i<k;i++){
            //如果只有一个node就是head，则直接返回latter
            if (former==null) return null;
            former = former.next;
        }
        //当former移动到头，也就是当former等于null的时候，latter就到达倒数第k个element，这时再返回latter
        while(former!=null){
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}

24-反转链表

import java.util.ArrayList;

public class reverseList_24 {
    /**
     * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
     *
     *
     *
     * 示例:
     *
     * 输入: 1->2->3->4->5->NULL
     * 输出: 5->4->3->2->1->NULL
     */
}

class Solution_24_0{
    /**
     * 这是一个土办法
     * 先用list从尾到头来储存node的值
     * 然后利用递归把每一个node的val更换为list中已经反转的值
     */
    ArrayList<Integer> list = new ArrayList<>();
    int i = 0;

    public ListNode reverseList(ListNode head) {
        recur(head);
        recur1(head);
        return head;
    }
    void recur(ListNode node){
        //先用递归把所有的node存起来
        if (node==null) return;
        recur(node.next);
        list.add(node.val);
    }
    void recur1(ListNode node){
        if (node==null) return;
        node.val=list.get(i++);
        recur1(node.next);
    }
}

25-合并两个排序的链表

public class mergeTwoLists_25 {
    /**
     * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
     *
     * 示例1：
     *
     * 输入：1->2->4, 1->3->4
     * 输出：1->1->2->3->4->4
     */
}

class Solution_25_0{
    //伪头点
    ListNode dum = new ListNode(0);
    //cur先指向dum
    ListNode cur = dum;
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        while (l1 != null && l2 != null){
            if (l1.val<l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else {
                cur.next = l2;
                l2 = l2.next;
            }
            //cur往前更新一步
            cur = cur.next;
        }
        if (l1!=null){
            cur.next=l1;
        }else {
            cur.next=l2;
        }
        return dum.next;
    }
}

35-复杂链表的复制

import java.util.HashMap;

public class copyRandomList_35 {
    /**
     * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，
     * 每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
     */
}

class Solution_35_0{
    /**
     * 使用HashMap来解题
     */
    public Node copyRandomList(Node head) {
        if (head==null) return null;
        //创建map
        HashMap<Node,Node> map = new HashMap<>();
        //指向head
        Node cur = head;
        //复制Node
        while (cur!=null){
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        //再次指向head
        cur = head;
        //复制Node的random和next
        while (cur!=null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

52-两个链表的第一个公共节点

public class getIntersectionNode_52 {
    /**
     * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
     * 输出：Reference of the node with value = 8
     * 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
     */
}

class Solution_52_0{
    /**
     * 如果两个无环链表相交,那么从相交节点开始,一直到两个链表终止的这一段,是两个链表共享的。
     *
     * 因此解决该问题的具体过程如下:
     *
     *     链表1从头节点开始，走到最后一个节点(不是结束)，统计链表1的长度记为len1，同时记录链表1的最后一个节点记为end1
     *
     *     链表2从头节点开始，走到最后一个节点(不是结束)，统计链表2的长度记为len2，同时记录链表2的最后一个节点记为end2。
     *
     *     如果end1!=end2，说明两个链表不相交，返回nul即可。如果end=end2，说明两个链表相交，进入步骤4来找寻第一个相交节点。
     *
     *     如果链表1比较长，链表1就先走len1-len2步。如果链表2比较长，链表2就先走len2-len1步。然后两个链表一起走，一起走的过程中，两个链表第一次走到一起的那个节点，就是第一个相交的节点。
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null || headB==null) return null;
        int lenA=0, lenB=0;
        ListNode curA = headA, curB = headB;
        //计算lenA
        while(curA!=null){
            lenA++;
            curA = curA.next;
        }
        //计算lenB
        while (curB!=null){
            lenB++;
            curB = curB.next;
        }
        //如果end1!=end2，说明两个链表不相交，返回nul即可。如果end=end2，说明两个链表相交，进入步骤4来找寻第一个相交节点。
        int dif = (lenA-lenB);
        curA = dif>0 ? headA : headB;
        curB = curA==headA ? headB : headA;
        dif = Math.abs(dif);
        if (dif>0){
            while (dif > 0){
                curA = curA.next;
                dif--;
            }
        }
        //现在两个链表一起走，等两个node相等的时候就返回，因为找到了intersect point
        while(curA!=curB){
            curA = curA.next;
            curB = curB.next;
        }
        //返回curA curB都行，因为相同
        return curA;
    }
}

18-删除链表的节点

public class deleteNode_18 {
    /**
     * 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
     *
     * 返回删除后的链表的头节点。
     *
     * 注意：此题对比原题有改动
     *
     * 示例 1:
     *
     * 输入: head = [4,5,1,9], val = 5
     * 输出: [4,1,9]
     * 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
     *
     * 示例 2:
     *
     * 输入: head = [4,5,1,9], val = 1
     * 输出: [4,5,9]
     * 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
     */
}

class Solution_18_0{
    public ListNode deleteNode(ListNode head, int val) {
        /**
         *     删除值为 val 的节点可分为两步：定位节点、修改引用。
         *
         *     定位节点： 遍历链表，直到 head.val == val 时跳出，即可定位目标节点。
         *     修改引用： 设节点 cur 的前驱节点为 pre ，后继节点为 cur.next ；则执行 pre.next = cur.next ，即可实现删除 cur 节点。
         */
        if (head.val==val) return head.next;
        //创建指针
        ListNode cur = head, pre = head;
        int count = 0;
        //找到目标节点
        while (cur.val!=val){
            cur = cur.next;
            count++;
        }
        //找到目标节点前面的一个节点
        for (int i=0;i<(count-1);i++){
            pre = pre.next;
        }
        //删除目标节点
        pre.next = cur.next;
        return head;
    }
}

Stack & Queue

09-用两个栈实现队列

import java.util.LinkedList;

/**
 * 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
 *
 *
 *
 * 示例 1：
 *
 * 输入：
 * ["CQueue","appendTail","deleteHead","deleteHead"]
 * [[],[3],[],[]]
 * 输出：[null,null,3,-1]
 *
 * 示例 2：
 *
 * 输入：
 * ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
 * [[],[],[5],[2],[],[]]
 * 输出：[null,-1,null,null,5,2]
 */

public class CQueue_09 {
    LinkedList<Integer> A,B;
    public CQueue_09() {
        /**
         * 题目只要求实现 加入队尾appendTail() 和 删除队首deleteHead() 两个函数的正常工作，
         * 因此我们可以设计栈 A 用于加入队尾操作，
         * 栈 B 用于将元素倒序，从而实现删除队首元素。
         */
        A = new LinkedList<>();
        B = new LinkedList<>();
    }

    public void appendTail(int value) {
        //A用于加入队尾
        //63
        A.addLast(value);
    }

    public int deleteHead() {
        /**
         * 删除队首deleteHead()函数： 有以下三种情况。
         *
         *     当栈 B 不为空： B中仍有已完成倒序的元素，因此直接返回 B 的栈顶元素。
         *     否则，当 A 为空： 即两个栈都为空，无元素，因此返回 −1 。
         *     否则： 将栈 A 元素全部转移至栈 B 中，实现元素倒序，并返回栈 B 的栈顶元素。
         */
        if (A.isEmpty() && B.isEmpty()) return -1;
        if (B.isEmpty()){
            while (!A.isEmpty()){
                //这里用addFirst来实现倒序
                //36
                B.addLast(A.removeLast());
            }
            //6
            return B.removeLast();
        }else return B.removeLast();
    }
}

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

30-包含min函数的栈

import java.util.Stack;

public class MinStack_30 {
    Stack<Integer> A,B;

    /** initialize your data structure here. */
    public MinStack_30() {
        A = new Stack<>();
        B = new Stack<>();
        /**
         * 函数设计：
         *
         *     push(x) 函数： 重点为保持栈 B 的元素是 非严格降序 的。
         *         将 xxx 压入栈 AAA （即 A.add(x) ）；
         *         若 ① 栈 BBB 为空 或 ② xxx 小于等于 栈 BBB 的栈顶元素，则将 xxx 压入栈 BBB （即 B.add(x) ）。
         *
         *     pop() 函数： 重点为保持栈 A,B 的 元素一致性 。
         *         执行栈 AAA 出栈（即 A.pop() ），将出栈元素记为 yyy ；
         *         若 yyy 等于栈 BBB 的栈顶元素，则执行栈 B 出栈（即 B.pop() ）。
         *
         *     top() 函数： 直接返回栈 AAA 的栈顶元素即可，即返回 A.peek() 。
         *
         *     min() 函数： 直接返回栈 BBB 的栈顶元素即可，即返回 B.peek() 。
         */
    }

    public void push(int x) {
      	//把x push到A
      	A.add(x);
        //需要保持 B栈 是非严格降序
      	//Stack类一定要用empty()别用错，用错成isEmpty()会报错
        if (B.Empty() || x<=B.peek()){
            //如果B是空 则把x push到B
            B.add(x);
        }
    }

    public void pop() {
        Integer popedInt = A.pop();
        if (popedInt.equals(B.peek())) B.pop();
    }

    public int top() {
        return A.peek();
    }

    public int min() {
        return B.peek();
    }
}

31-栈的压入、弹出序列

import java.util.Stack;

public class validateStackSequences_31 {
/**
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
 * 输出：true
 * 解释：我们可以按以下顺序执行：
 * push(1), push(2), push(3), push(4), pop() -> 4,
 * push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
 *
 * 示例 2：
 *
 * 输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
 * 输出：false
 * 解释：1 不能在 2 之前弹出。
 */
}

class Solution_31_0{
    /**
     * 考虑借用一个辅助栈 stack ，模拟 压入 / 弹出操作的排列。根据是否模拟成功，即可得到结果。
     *
     *     入栈操作： 按照压栈序列的顺序执行。
     *     出栈操作： 每次入栈后，循环判断 “栈顶元素 === 弹出序列的当前元素” 是否成立，将符合弹出序列顺序的栈顶元素全部弹出。
     *
     *     由于题目规定 栈的所有数字均不相等 ，因此在循环入栈中，每个元素出栈的位置的可能性是唯一的（若有重复数字，则具有多个可出栈的位置）。
     *     因而，在遇到 “栈顶元素 === 弹出序列的当前元素” 就应立即执行出栈。
     *
     * 算法流程：
     *
     *     初始化： 辅助栈 stackstackstack ，弹出序列的索引 iii ；
     *     遍历压栈序列： 各元素记为 numnumnum ；
     *         元素 numnumnum 入栈；
     *         循环出栈：若 stackstackstack 的栈顶元素 === 弹出序列元素 popped[i]popped[i]popped[i] ，则执行出栈与 i++i++i++ ；
     *     返回值： 若 stackstackstack 为空，则此弹出序列合法。
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int n = 0;
        //按照顺序依次push element
        for(int num : pushed){
            stack.push(num);
            while(!stack.empty() && stack.peek().equals(popped[n])){
                stack.pop();
                n++;
            }
        }
        return stack.empty();
    }
}

58-1-翻转单词顺序

public class reverseWords_58_1 {
    /**
     * 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
     *
     *
     *
     * 示例 1：
     *
     * 输入: "the sky is blue"
     * 输出: "blue is sky the"
     *
     * 示例 2：
     *
     * 输入: "  hello world!  "
     * 输出: "world! hello"
     * 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
     *
     * 示例 3：
     *
     * 输入: "a good   example"
     * 输出: "example good a"
     * 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
}

class Solution_58_1_0{
    public String reverseWords(String s) {
        //trim()删除首尾空格 split(" ")用空格分割字符串
        String[] strings = s.trim().split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i=strings.length-1;i>=0;i--){
            //如果stringbuilder里的string是空单词 就跳过进入下一次循环
            if (strings[i].equals("")) continue;
            stringBuilder.append(strings[i]);
        }
        return stringBuilder.toString();
    }
}

59 - I. 滑动窗口的最大值

import java.util.Deque;
import java.util.LinkedList;

public class maxSlidingWindow_59_1 {

}

class Solution_59_1_0{
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length==0 || k==0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        //初始化返回的结果
        int[] res = new int[nums.length-k+1];
        for (int i=1-k,j=0;j<nums.length; i++,j++){
            //通过removefirst来删除deque中和nums对应的element
            if (i>0 && deque.peekFirst()==nums[i-1]) deque.removeFirst();
            //while递减deque
            while (!deque.isEmpty() && deque.peekLast()<nums[j]) deque.removeLast();
            deque.addLast(nums[j]);
            //记录最大值
            if (i>=0) res[i]=deque.peekFirst();
        }
        return res;
    }
}

Heap

40-最小的K个数

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class getLeastNumbers_40 {
    public int[] getLeastNumbers(int[] nums, int k) {
        if (nums.length==0 || k==0) return new int[0];
        // 使用一个最大堆（大顶堆）
        // Java 的 PriorityQueue 默认是小顶堆，添加 comparator 参数使其变成最大堆
        Queue<Integer> heap = new PriorityQueue<>(k,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                /**
                 * This method returns the value zero if (x==y),
                 * if (x < y) then it returns a value less than zero
                 * and if (x > y) then it returns a value greater than zero.
                 */
                return Integer.compare(o2,o1);
            }
        });
        for (int e : nums){
            //如果e小于当前heap中栈顶的最大的元素才添加e
            if (heap.isEmpty() || heap.size()<k || heap.peek()>e) heap.offer(e);
            //如果当前heap的size大于k则把栈顶元素弹出去
            if (heap.size()>k) heap.poll();
        }
        //将heap中最小的k个数加入到res数组里并return
        int[] res = new int[heap.size()];
        int i = 0;
        for (int e : heap){
            res[i++] = e;
        }
        return res;
    }
}

Hash Table

50-第一个只出现一次的字符

public char firstUniqChar(String s) {
  HashMap<Character, Boolean> dic = new HashMap<>();
  char[] sc = s.toCharArray();
  for (char c:sc){
    //!dic.containsKey(c)导致第一次添加key的时候，value是true，但是再次添加的时候就是false
    //跟本题符合，因为只需要出现依次的char，也就是说如果value为false则不是只出现一次的char
    dic.put(c,!dic.containsKey(c));
  }
  for (char c:sc)
    //只出现一次的key的value是true，如果dic,get()返回true，说明是我们要找的char
    if (dic.get(c)) return c;
  return ' ';
}

Graph (DFS & BFS)

12-矩阵中的路径(DFS)

class Solution_12_0{
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i=0;i<board.length;i++){
            for (int j=0;j<board[0].length;j++){
                if (dfs(board,words,i,j,0)) return true;
            }
        }
        return false;
    }

    boolean dfs(char[][] board, char[] word, int i, int j, int k){
        //① 行或列索引越界 或 ② 当前矩阵元素与目标字符不同 或 ③ 当前矩阵元素已访问过 （③ 可合并至 ②
        if (i>=board.length || i<0 || j>=board[0].length || j<0 || board[i][j]!=word[k]) return false;
        //字符串 word 已全部匹配，即 k = len(word) - 1 。
        if (k==word.length-1) return true;
        //将当前char存起来
        char tmp = board[i][j];
        //将当前char的位置标记为/，防治再次遍历当前的char，走回头路
        board[i][j] = '/';
        //可以上下左右移动，只要有一个方向符合要求就可以
        boolean res = dfs(board,word,i,j+1,k+1) || dfs(board, word, i, j-1, k+1) || dfs(board, word, i-1, j, k+1)
                || dfs(board, word, i+1, j, k+1);
        //恢复char，因为其他递归里还需要走过这个char
        board[i][j] = tmp;
        return res;
    }
}

13-机器人的运动范围(DFS)

class Solution_13_0{
    int m,n,k;
    //辅助矩阵
    boolean[][] visited;

    public int movingCount(int m, int n, int k) {
        this.m=m;
        this.n=n;
        this.k=k;
        this.visited = new boolean[m][n];
        return dfs(0,0,0,0);
    }

    int dfs(int i, int j, int si, int sj){
        //当 ① 行列索引越界 或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过 时，返回 0 ，代表不计入可达解。
        if (i>=m || j>=n || si+sj>k || visited[i][j]) return 0;
        visited[i][j] = true;
        /**
         * 递推工作：
         *
         *     标记当前单元格 ：将索引 (i, j) 存入 Set visited 中，代表此单元格已被访问过。
         *     搜索下一单元格： 计算当前元素的 下、右 两个方向元素的数位和，并开启下层递归 。
         *
         * 回溯返回值： 返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数。
         */
      	//注意数位和的增量公式
        //(x + 1) % 10 != 0 ? s_x + 1 : s_x - 8
        //s_x为x的数位和
        return 1+dfs(i+1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj)+dfs(i,j+1,si,(j+1)%10!=0?sj+1:sj-8);
    }
}

Fibonacci (Dynamic Programming)

10-1-斐波拉契数列

public class Fib_10_1 {
    /**
     * 如果仅仅是用简单递归，在时间复杂度闪就会WA，然后就需要用动态规划的想法去简化计算量。
     * 对于这个问题，我的思路是从小到大算回去，把沿途的结果进行记录，推到n。
     * 关于题目描述中的取模这里提一句，要在计算中就取，不要等到结果再取，在计算过程中就已经达到取模要求了，如果没有取，可能会溢出。
     */
    /**
     * 动态规划解析：
     *
     *     状态定义： 设 dp 为一维数组，其中 dp[i]dp[i]dp[i] 的值代表 斐波那契数列第 i 个数字 。
     *     转移方程： dp[i]=dp[i-1]+dp[i−2]，即对应数列定义 F(N) = F(N - 1) + F(N - 2)
     *     初始状态： dp[0]=1 dp[1]=1 ，即初始化前两个数字；
     *     返回值： dp[n]] ，即斐波那契数列的第 n 个数字。
     */
}

class Solution_10_1_0{
    public int fib(int n) {
        if(n==0 || n==1) return n;
        long[] dp = new long[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            dp[i] = dp[i-1] + dp[i-2];
            //在计算中就曲摸，不然会溢出
            dp[i] = dp[i]%1000000007;
        }
        return (int)dp[n];
    }
}

10-2-青蛙跳台阶问题

public class numWays_10_2 {
    /**
     * 动态规划解析：
     *
     *     状态定义： 设 dp 为一维数组，其中 dp[i]dp[i]dp[i] 的值代表 斐波那契数列第 i 个数字 。
     *     转移方程： dp[i]=dp[i-1]+dp[i−2]，即对应数列定义 F(N) = F(N - 1) + F(N - 2)
     *     初始状态： dp[0]=1 dp[1]=1 dp[2]=2 ，即初始化前三个数字；
     *     返回值： dp[n]] ，即斐波那契数列的第 n 个数字。
     */
}

class Solution_10_2_0{
    public int numWays(int n) {
        if(n==0 || n==1) return 1;
        if (n==2) return 2;
        long[] dp = new long[n+1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i=3;i<=n;i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
        }
        return (int)dp[n];
    }
}

Searching Algorithms (Binary Search)

04-二维数组中的查找

import java.util.Arrays;

public class findNumberIn2DArray_04 {
}

class Solution_04_0{
    //线性查找 Linear Search
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        //行数
        int i = matrix.length-1;
        //列数
        int j = 0;
        /**
         * 则 int flag = matrix[i][j] 代表左下角元素（标志数）
         * 左下角元素： 为所在列最大元素，所在行最小元素
         * 如果flag大于target，就到上一行找，也就是i--，因为已知flag是所在行最小的元素
         * 如果flag小于target，就到下一列，j++，因为flag是这一列最大的元素
         * 如果flag ==  target，则return true
         */
        while (i>=0 && j<matrix[0].length){
            if (matrix[i][j]>target) i--;
            else if (matrix[i][j]<target) j++;
            else return true;
        }
        return false;
    }
}

class Solution_04_1{
    //二分查找  Binary Search
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        /**
         * 思路分析：
         *
         * 要查找矩阵中是否存在某个元素，并且表示矩阵每一行的数组都是有序的，可以对每一行进行二分查找，如果每一行都没有查找到结果，就返回false。
         *     使用java库函数Arrays.binarySearch(matrix[i], target)，返回值非负说明查找到target。
         * 还需要处理一些特殊情况：
         *     给定的矩阵为null或者给定的矩阵不存在任何元素matrix.length == 0 || matrix[0].length == 0，肯定找不到目标元素，直接返回。
         *     矩阵的每一列也是从小到达排列的，所以在对每一行进行二分查找的循环是，如果matrix[i][0] > target，
         *     这一行肯定没有指定元素，更下面的每一行的所有元素都大于matrix[i][0]也一定找不到指定元素，所以可以直接返回false。
         */
        if (matrix==null || matrix.length==0 || matrix[0].length==0) return false;
        for (int i=0;i<matrix.length;i++){
            //如果Arrays.binarySearch(matrix[i],target)是非零数则表示该行含有target
            if (Arrays.binarySearch(matrix[i],target)>=0) return true;
            //如果matrix[i][0]>target这一行就不包括target，因为matrix[i][0]是该行第一个元素，每一列和每一行都是递增的，如果第一个元素
            //都比target大，那说明该行不包含该元素，且因为递增，下一行的第一个元素一定比target大，所以return false结束循环
            if (matrix[i][0]>target) return false;
        }
        return false;
    }
}

11-旋转数组的最小数字（二分查找）

import java.util.Arrays;

public class minArray_11 {
}

class Solution_11_0{
    //沙雕做法
    //笔试的时候可以用，面试别用
    public int minArray(int[] numbers) {
        Arrays.sort(numbers);
        return numbers[0];
    }
}

class Solution_11_1{
    //二分搜索 Binary Search
    public int minArray(int[] numbers){
        /**
         * 设计两个指针i和j分别指向0和numbers.length-1
         * m = (i+j)/2 是中间数，那么会有三种情况
         * 1：numbers[m]<numbers[j] 说明m在右边数组[m+1,j]，旋转点在[i,m], 所以更新j=m，m=(i+j)/2
         * 2：number[m]>numbers[j] 说明m在左边数组,旋转点在[m+1,j]，所以更新i=m+1,m=(i+j)/2
         * 3：number[m]==numbers[j] 无法判断 mmm 在哪个排序数组中，即无法判断旋转点在 [i,m] 还是 [m+1,j] 区间中。
         * 解决方案： 执行 j=j−1 缩小判断范围
         */
        int i=0, j= numbers.length-1;
        while (i<j){
            int m = (i+j)/2;
            if (numbers[m]<numbers[j]){
                j=m;
            }else if (numbers[m]>numbers[j]){
                i=m+1;
            }else if (numbers[m]==numbers[j]){
                j--;
            }
        }
        return numbers[i];
    }
}

class Solution_11_2{
    //暴力法 居然是这三种办法里最快的QAQ
    public int minArray(int[] numbers){
        for (int i=0;i<numbers.length;i++){
            if (numbers[i]<numbers[0]){
                return numbers[i];
            }
        }
        return numbers[0];
    }
}

56-1-数组中数字出现的次数

public class singleNumbers_56_1 {
    /**
     * 难点主要在于对mask的理解。mask是一个二进制数，且其中只有一位是1，其他位全是0，
     * 比如000010，表示我们用倒数第二位作为分组标准，倒数第二位是0的数字分到一组，倒数第二位是1的分到另一组。
     *
     * 那么如何得到这个mask?因为我们分组的目的就是将两个不重复数字分开，
     * 这两个不重复数字的二进制表示肯定是不同的，但是我们没必要一位一位地比较，我们可以从右到左，找到第一个不相同的位，将mask当中这一位变成1,就得到了mask。
     *
     * 比如[2,2,3,3,4,6]中，不重复的两个数字是4，6，4和6的异或结果（也是整个数组的异或结果）是010，
     * 表示从右到左，第一次出现不同是在倒数第二位，那么可以确定，mask的倒数第二位是1，其他位是0，即
     */
}

class Solution_56_1_0{
    public int[] singleNumbers(int[] nums) {
        //xor用来计算nums的异或和
        int xor = 0;

        // 计算异或和 并存到xor
        // e.g. [2,4,2,3,3,6] 异或和：(2^2)^(3^3)^(4^6)=2=010
        for(int num : nums) xor ^= num;

        //设置mask为1，则二进制为0001
        // mask是一个二进制数，且其中只有一位是1，其他位全是0，比如000010，
        // 表示我们用倒数第二位作为分组标准，倒数第二位是0的数字分到一组，倒数第二位是1的分到另一组
        int mask = 1;

        // & operator只有1&1时等于1 其余等于0
        // 用上面的e.g. 4和6的二进制是不同的 我们从右到左找到第一个不同的位就可以分组 4=0100 6=0110
        // 根据e.g. 010 & 001 = 000 = 0则 mask=010
        // 010 & 010 != 0 所以mask=010
        // 之后就可以用mask来将数组里的两个数分区分开
        while((xor & mask)==0){
            mask <<= 1;
        }

        //两个只出现一次的数字
        int a=0, b=0;

        for(int num : nums){
            //根据&是否为0区分将两个数字分区，并分别求异或和
            if((num & mask)==0) a ^= num;
            else{
                b ^= num;
            }
        }
        return new int[]{a,b};
    }
}

Permutation

38-字符串的排列

class Solution {
    //把参数string换为char数组
    char[] c;
    //记录每一种可能，最后转换成数组return
    List<String> res = new LinkedList<>();
    public String[] permutation(String s) {
        c = s.toCharArray();
        //从c的第一位字符开始
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x){
        //终止条件
        if(x==c.length-1){
            res.add(String.valueOf(c));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i=x;i<c.length;i++){
            //HashSet用来剪枝，避免重复
            //例如 c=[a,b,b], 如果没有剪枝，就会有四个abb
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            //e.g. c=[a,b,c]
            //这是第一层，也就是第一位上的字符的选择，通过调换来更换位置
            swap(i,x);
            //进入第二层，在e.g.第二层里会有两种选择，然后第二层里再递归第三层
            //第三层会出发终止条件 res会加上当前的可能
            dfs(x+1);
            //回溯，把调换的位置再换回来
            swap(i,x);
        }
    }
    void swap(int a,int b){
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}

Dynamic Programming

42-连续子数组的最大和

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        //初始化
        dp[0] = nums[0];
        int res = nums[0];
        for (int i=1;i<dp.length;i++){
            if(dp[i-1]>0){
                dp[i] = dp[i-1]+nums[i];
            }else if(dp[i-1]<=0){
                //说明dp[i-1]对dp[i]是负贡献
                //dp[i-1]+nums[i]小于nums[i]
                //所以我们直接从当前nums[i]为开头的连续子数组来数就行
                dp[i] = nums[i];
            }
        }
      //不要用 Arrays.sort() 或者Arrays.stream().min().getAsInt()
        for(int i=0;i<dp.length;i++){
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

19-正则表达式匹配

Bitwise Operation

15-二进制中1的个数

class Solution_15_0{
    public int hammingWeight(int n) {
        int res = 0;
        // n-1 代表 二进制n的最右边的1变成0，然后这个1右边的0变成1
        // n = n & (n-1) 代表 二进制n最右边的1变成0，其余不变
        // e.g. n = 110001000 n-1=110000111
        // n &= (n-1) -> n = 110000000
        //在每一次循环中都消去n的最右边的1 并且res++ 当n中不含有1的时候终止循环
        while(n!=0){
            res++;
            n &= (n-1);
        }
        return res;
    }
}

class Solution_15_1{
    public int hammingWeight(int n) {
        int res = 0;
        while(n!=0){
            //n&1只有两种可能分别是0和1
            res += n&1;
            //本题要求把数字 nnn 看作无符号数，因此使用 无符号右移 操作
            // java中是>>>=
            n >>>= 1;
        }
        return res;
    }
}

class Solution_15_2{
    public int hammingWeight(int n) {
        /**
         * 这个是土方法做的 虽然能做出来但是时间空间复杂度高 性能差
         */
        int mask = 1;
        int res = 0;
        // 用Integer.toBinaryString().length来计算转换为二进制的数的长度
        // 也就是从二进制的一位一位的算
        // mask = 00000001
        // 如果 n&mask !=0 说明 对应mask的1的位置的n的位置是1 则res++
        // 每次循环都将mask往左边移动 才检测n的左边一位是否是1
        for(int i=0;i<Integer.toBinaryString(n).length();i++){
            if((n & mask)!=0){
                res++;
            }
            mask <<= 1;
        }
        return res;
    }
}

class Solution_15_3{
    public int hammingWeight(int n) {
        /**
         * 这个是土方法做的 虽然能做出来但是时间空间复杂度高 性能差
         */
        int res = 0;
        int len = Integer.toBinaryString(n).length();
        for(int i=0;i<len;i++){
            if((n & 1)!=0){
                res++;
            }
            n >>>= 1;
        }
        return res;
    }
}

class Solution_15_4{
    //最简洁 = 性能最差哈哈哈
    public int hammingWeight(int n) {
        return Integer.toBinaryString(n).replaceAll("0", "").length();
    }
}

16-数值的整数次方

class Solution_16_0{
    //e.g. 2^10 x=2.0 n=9=1001
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        //Java 代码中 int32 变量 n∈[−2147483648,2147483647],
        // 因此当 n=−2147483648n 时执行 n=−n 会因越界而赋值出错。解决方法是先将 n 存入 long 变量 b ，后面用 b 操作即可。
        long b = n;
        double res = 1.0;
        if(b < 0) {
        //如果是n是负数就换成正数 x换成x^-1就行 也就是1/x
            x = 1 / x;
            b = -b;
        }
        while(b > 0) {
            // res = 1*2 = 2
            if((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
}

Other Algorithms

05-替换空格

class Solution_05_0{
    //脑瘫做法哈哈 但是时间空间复杂度跟下面一样哈哈 笔试的时候真的可以用哈哈
    public String replaceSpace(String s) {
        return s.replace(" ","%20");
    }
}

class Solution_05_1{
    //脑瘫做法哈哈
    public String replaceSpace(String s) {
        //在 Python 和 Java 等语言中，字符串都被设计成不可变的类型，即无法直接修改字符串的某一位字符，需要新建一个字符串实现。
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        for (char c : chars){
            if (c == ' ') sb.append("%20");
            else{
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

21-调整数组顺序使奇数位于偶数前面

class Soulution_21_0{
    // 不是同一时间 但是同一种土方法
    // 6%+95%
    // 性能感人 泪目了
    public int[] exchange(int[] nums) {
        List<Integer> list_1 = new ArrayList<>();
        List<Integer> list_2 = new ArrayList<>();
        for (int n : nums){
            //==0就是偶数
            if ((n&1)==0) list_1.add(n);
            // ==1是奇数
            if ((n&1)==1) list_2.add(n);
        }
        int[] res = new int[list_1.size()+list_2.size()];
        for (int i=0;i<list_2.size();i++){
            res[i] = list_2.get(i);
        }
        int j = 0;
        for (int i=list_2.size();i<res.length;i++){
            res[i] = list_1.get(j);
            j++;
        }
        return res;
    }
}

class Soulution_21_1{
    //双指针
    public int[] exchange(int[] nums) {
        //定义左右指针 和 tmp用来转换位置
        int left = 0;
        int right = nums.length-1;
        int tmp;
        while(left<right){
            //思路就是
            //左指针找到左边第一个偶数
            //右指针找到右边第一个奇数
            //左右指针指向的数互换位置
            //这样的话 所有的操作都是基于参数nums 最后直接返回nums
            while(left<right && (nums[left]&1)!=0) left++;
            while(left<right && (nums[right]&1)!=1) right--;
            tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
        return nums;
    }
}

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

class Solution_39_0{
    // for each 版本的 HashMap做法
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums){
            if (map.containsKey(n)){
                map.put(n,map.get(n)+1);
            }else {
                map.put(n,1);
            }
        }
        int resValue = 0;
        int resKey = 0;
        Collection<Integer> c = map.values();
        Object[] obj = c.toArray();
        Arrays.sort(obj);
        resValue = (int)obj[obj.length-1];
        for (int key : map.keySet()){
            if (map.get(key).equals(resValue)){
                resKey = key;
            }
        }
        return resKey;
    }
}

class Soulution_39_1{
    public int majorityElement(int[] nums) {
        //出现次数大于nums的长度的一般
        int len = nums.length/2;
        //定义hashmap来统计每次数字出现次数
        Map<Integer, Integer> map = new HashMap<>();
        //题目给出nums.length>=1所以要考虑等于1的情况
        if (nums.length==1) return nums[0];
        for (int i=0;i<nums.length;i++){
            if (map.containsKey(nums[i])){
                //如果map包含当前的数字，则更新该数字的出现次数
                map.put(nums[i],map.get(nums[i])+1);
                //如果当前数字的value也就是出现次数大于nums的长度的一半就赋值给res
                if (map.get(nums[i])>len){
                    return nums[i];
                }
            } else {
                map.put(nums[i],1);
            }
        }
        return 0;
    }
}

class Solution_39_2{
    //排序法
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

class Solution_39_3{
    //摩尔投票法 最优解
    /**
     * 算法原理：
     *
     *     为构建正负抵消，假设数组首个元素 n1​ 为众数，遍历统计票数，当发生正负抵消时，剩余数组的众数一定不变 ，这是因为（设真正的众数为 x ）：
     *         当 n1=x： 抵消的所有数字中，有一半是众数 x 。
     *         当 n1≠x ： 抵消的所有数字中，少于或等于一半是众数 x 。
     *     利用此特性，每轮假设都可以 缩小剩余数组区间 。当遍历完成时，最后一轮假设的数字即为众数（由于众数超过一半，最后一轮的票数和必为正数
     */
    public int majorityElement(int[] nums) {
        /**
         * 算法流程:
         *
         *     初始化： 票数统计 votes=0， 众数 x；
         *     循环抵消： 遍历数组 nums 中的每个数字 num ；
         *         当 票数 votes 等于 0 ，则假设 当前数字 numn 为 众数 x ；
         *         当 num=x时，票数 votes 自增 1 ；否则，票数 voteses 自减 1 。
         *     返回值： 返回 众数 x 即可
         */
        int vote = 0;
        int x=0;
        for (int num : nums){
            if (vote==0) x = num;
            if (num==x){
                vote++;
            }else {
                vote--;
            }
        }
        return x;
    }
}

43-1～n整数中1出现的次数(妖魔算法题)

public class countDigitOne_43 {
    public static void main(String[] args) {
        String s = String.valueOf(2345);
        // char类型的s.chartAt(0)是2
        System.out.println(s.charAt(0));
        //但是把s.chartAt(0)强制转换为int是不行的
        int test = (int) s.charAt(0);
        System.out.println(test);
        // 有两种办法
        //第一种 用char的封装累的静态方法
        int high_0 = Character.getNumericValue(s.charAt(0));
        System.out.println(high_0);
        //第二种 直接 -'0' 就可以得到准确的int
        int high_1 = s.charAt(0) - '0';
        System.out.println(high_1);
        System.out.println(s);
    }
}

class Solution_43_0{
    public int countDigitOne(int n) {
        return d(n);
    }
    int d(int n){
        //递归终止条件
        if (n<=0) return 0;
        // 把int转为string
        String s = String.valueOf(n);
        int high = s.charAt(0) - '0';
        int pow = (int)Math.pow(10,s.length()-1);
        int last = n-high*pow;
        if (high == 1){
            return d(pow-1)+d(last)+(last+1);
        }else {
            return pow + high*d(pow-1) + d(last);
        }
    }
}

45-把数组排成最小的数(妖魔算法题)

class Solution_45_0{
    /**
     * 排序判断规则： 设 nums 任意两数字的字符串格式 x 和 y ，则
     *
     *     若拼接字符串 x+y>y+x，则 m>n；
     *     反之，若 x+y<y+xx，则 n<m；
     */
    public String minNumber(int[] nums) {
        // 字符串列表 strs ，保存各数字的字符串格式
        String[] strs = new String[nums.length];
        for (int i=0;i<nums.length;i++){
            strs[i] = String.valueOf(nums[i]);
        }
        //应用以上 “排序判断规则” ，对 strs 执行排序；
        Arrays.sort(strs, (x,y) -> (x+y).compareTo(y+x));
        //拼接 strs 中的所有字符串，并返回
        StringBuilder sb = new StringBuilder();
        for (String s : strs){
            sb.append(s);
        }
        return sb.toString();
    }
}

49-丑数 (妖魔算法题)

class Solution_49_0{
    /**
     * 定义三个指针p2,p3,p5，p2指向的数字永远乘2，p3指向的数字永远乘3，p5指向的数字永远乘5
     * 初始化所有指针都指向第一个丑数，即1
     * 我们从2*dp[p2], 3*dp[p3], 5*dp[p5]选取最小的一个数字，作为新的丑数。这边新的丑数就是2*dp[p2]=2*1=2，然后p2++
     * 此时p3和p5指向第1个丑数，p2指向第2个丑数。然后重复上一步
     * 这里基于的一个事实是，丑数数列是递增的，当p5指针在当前位置时，
     * 后面的数乘以5必然比前面的数乘以5大，所以下一个丑数必然是先考虑前面的数乘以5。p2,p3同理，所以才可以使用指针
     */
    public int nthUglyNumber(int n) {
        int p2=0, p3=0, p5=0;
        int[] dp = new int[n];
        dp[0]=1;
        for (int i=1;i<n;i++){
            dp[i] = Math.min(dp[p2]*2,Math.min(dp[p3]*3,dp[p5]*5));
            if (dp[i]==dp[p2]*2) p2++;
            if (dp[i]==dp[p3]*3) p3++;
            if (dp[i]==dp[p5]*5) p5++;
        }
        return dp[n-1];
    }
}

57-2-和为S的连续正数序列(滑动窗口思想)

public class findContinuousSequence_57_2 {
}

/**
 * 滑动窗口是数组中框起来的一部分，我们可以用滑动窗口观察所有可能的结果，当窗口从数组左边滑到数组右边，我们可以从中找出最优解
 * 对于这道题来说，数组就是正整数序列 [1,2,3,...n] 。我们设滑动窗口的左边界为 i，右边界为 j，
 * 则滑动窗口框起来的是一个左闭右开区间 [i,j)。注意，为了编程的方便，滑动窗口一般表示成一个左闭右开区间。
 * 在一开始，i=1,j=1，滑动窗口位于序列的最左侧，窗口大小为零。
 * 滑动窗口的重要性质是：窗口的左边界和右边界永远只能向右移动，而不能向左移动。这是为了保证滑动窗口的时间复杂度是 O(n)
 *
 * 在这道题中，我们关注的是滑动窗口中所有数的和。当滑动窗口的右边界向右移动时，也就是 j = j + 1，窗口中多了一个数字 j，
 * 窗口的和也就要加上 j。当滑动窗口的左边界向右移动时，也就是 i = i + 1，窗口中少了一个数字 i，窗口的和也就要减去 i。
 * 滑动窗口只有 右边界向右移动（扩大窗口） 和 左边界向右移动（缩小窗口） 两个操作，所以实际上非常简单。
 */

class Solution_57_2_0{
    public int[][] findContinuousSequence(int target) {
        //左右边界必须从1开始，不能为0，否则会出现[0,1,2,3,...,n]的非法集合
        int i = 1; // 滑动窗口左边界
        int j = 1; // 滑动窗口右边界
        int sum = 0; // 窗口中的和
        List<int[]> list = new ArrayList<>(); // 储存可能的数组
        //因为序列是连续的 当i=target/2时下一个比i大1，加起来就超过target了，题目要求最少两个整数
        //拿target=9举例，当i=5的时候没有必要接着遍历下去了，题目说数组递增，所以下一个数比5大，加起来也肯定大于9
        while(i<=target/2){
            if (sum<target){
                sum += j;
                j++;
            }else if (sum>target){
                sum -= i;
                i++;
            }else {
                int[] res = new int[j-i];
                for (int k=i;k<j;k++){
                    res[k-i] = k;
                }
                list.add(res);
                //左边边界向右移动1位
                sum -= i;
                i++;
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

57-和为S的两个数字(双指针思想)

public class twoSum_57 {

}

class Soulution_57_0{
    //憨憨做法哈哈
    public int[] twoSum(int[] nums, int target){
        //HashSet做法
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums){
            //将每一个nums中的数字添加到set中
            set.add(num);
        }
        for (int num : nums){
            //对于nums中的每一个数字，求出与target的差，如果set包含这个差的数字则返回
            int dif = target - num;
            if (set.contains(dif)){
                return new int[]{dif,num};
            }
        }
        return new int[]{};
    }
}

class Solution_57_1{
    //个人双指针
    public int[] twoSum(int[] nums, int target){
        //左右指针分别指向0和1
        int left = 0;
        int right = nums.length-1;
        while(left<right){
            if (nums[left]+nums[right]==target){
                return new int[]{nums[left],nums[right]};
            }else if (nums[left]+nums[right]<target){
                //因为nums是递增的，所以left++
                left++;
            }else if (nums[left]+nums[right]>target){
                //同理
                right--;
            }
        }
        return new int[]{};
    }
}

58-2-左旋转字符串(矩阵翻转)

class Solution_58_2_0{
    // 字符串切片 substring()方法
    public String reverseLeftWords(String s, int n) {
        //翻转之后前面的字符串
        String first = s.substring(n,s.length());
        //翻转之后后面的字符串
        String second = s.substring(0,n);
        return first+second;
    }
}

class Solution_58_2_1{
    // 列表遍历拼接 利用charAt()方法找到每一个string中的char 然后依次添加到StringBuilder对象中去
    public String reverseLeftWords(String s, int n) {
        StringBuilder sb = new StringBuilder();
        //先把从n到尾的char添加到sb
        for (int i=n;i<s.length();i++){
            sb.append(s.charAt(i));
        }
        //再把0到n添加到sb
        for (int i=0;i<n;i++){
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

class Solution_58_2_2{
    // 字符串遍历拼接
    public String reverseLeftWords(String s, int n) {
        String res = "";
        //先把从n到尾的char添加到res
        for (int i=n;i<s.length();i++){
            res += (s.charAt(i));
        }
        //再把0到n添加到res
        for (int i=0;i<n;i++){
            res += (s.charAt(i));
        }
        return res;
    }
}

62-圆圈中最后剩下的数(约瑟夫环)

class Solution_62_0{
    //Arraylist做法
    public int lastRemaining(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i=0;i<n;i++){
            list.add(i);
        }
        //当前删除位
        int x = 0;
        while (n>1){
            x = (x+m-1)%n;
            //删除x位置上的元素
            list.remove(x);
            n--;
        }
        return list.get(0);
    }
}

class Solution_62_1{
    //约瑟夫环的数学做法

    /**
     * n = 5, m = 3
     * 第一轮是 [0, 1, 2, 3, 4] ，所以是 [0, 1, 2, 3, 4] 这个数组的多个复制。这一轮 2 删除了。
     *
     * 第二轮开始时，从 3 开始，所以是 [3, 4, 0, 1] 这个数组的多个复制。这一轮 0 删除了。
     *
     * 第三轮开始时，从 1 开始，所以是 [1, 3, 4] 这个数组的多个复制。这一轮 4 删除了。
     *
     * 第四轮开始时，还是从 1 开始，所以是 [1, 3] 这个数组的多个复制。这一轮 1 删除了。
     *
     * 最后剩下的数字是 3。
     *
     * 图中的绿色的线指的是新的一轮的开头是怎么指定的，每次都是固定地向前移位 mmm 个位置。
     *
     * 然后我们从最后剩下的 3 倒着看，我们可以反向推出这个数字在之前每个轮次的位置。
     *
     * 最后剩下的 3 的下标是 0。
     *
     * 第四轮反推，补上 mmm 个位置，然后模上当时的数组大小 2，位置是(0 + 3) % 2 = 1。
     *
     * 第三轮反推，补上 mmm 个位置，然后模上当时的数组大小 3，位置是(1 + 3) % 3 = 1。
     *
     * 第二轮反推，补上 mmm 个位置，然后模上当时的数组大小 4，位置是(1 + 3) % 4 = 0。
     *
     * 第一轮反推，补上 mmm 个位置，然后模上当时的数组大小 5，位置是(0 + 3) % 5 = 3。
     *
     * 所以最终剩下的数字的下标就是3。因为数组是从0开始的，所以最终的答案就是3。
     *
     * 总结一下反推的过程，就是 (当前index + m) % 上一轮剩余数字的个数。
     */
    public int lastRemaining(int n, int m) {
        int res = 0;
        //最后一轮剩俩人 所以从2开始
        for (int i=2;i<=n;i++){
            res = (res+m)%i;
        }
        return res;
    }
}

66-构建乘积数组

class Solution_66_0{
    public int[] constructArr(int[] a) {
        /*
        这道题的思路就是：
        求出当前元素的左右乘积并分别存到不同的数组里
        最后用左右乘积的数组相乘得到答案
         */
        if (a.length==0){
            return new int[]{};
        }
        int[] leftRes = new int[a.length];
        int left=1;
        for (int i=0;i<a.length;i++){
            //第一位总是0，因为第一位的左边没有元素
            leftRes[i] = left;
            //更新left
            left *= a[i];
        }
        //右边同理
        int[] rightRes = new int[a.length];
        int right = 1;
        for (int i =a.length-1;i>=0;i--){
            rightRes[i] = right;
            right*=a[i];
        }
        int[] res = new int[a.length];
        for(int i=0;i<res.length;i++){
            res[i] = leftRes[i]*rightRes[i];
        }
        return res;
    }
}