专题总结

【代码规范】

一、三种常见的命名规范：

1. 驼峰命名法：驼峰命名法就是当变量名或函数名是由一个或多个单词连结在一起时，第一个单词以小写字母开始；从第二个单**词开始以后的每个单词**的首字母都采用大写字母。（例如：myName，hisBoyfriend）

2. 帕斯卡命名法：帕斯卡命名法就是当变量名或函数名是由一个或多个单词连结在一起时，**每个单词**的首字母都采用大写字母。（例如：MyName，HisBoyfriend）

3. 下划线命名法：所有字母均小写，每个单词间以下划线分割。（例如：my_name,his_name）

在使用上，这样的命名规范都十分清晰明了。具体而言，我们一般给函数名、全局变量和结构体名等通用性强的采用帕斯卡命名法，局部变量、函数形参采用驼峰命名法或下划线命名法。

二、代码结构清晰：

/*------错误示范-------*/
#include<stdio.h>
 int main()
{double a,b;
scanf("%lf%lf",&a,&b);
if(a>b)
printf("%lf",a);
else printf("%lf",b);
return 0;}
/*------正确示范-------*/
#include <stdio.h>         ///空格最好加上
int main()                 ///nt前面不要加空格
{                          ///每出现一个'{'后代码要向后缩进直到遇到'}'，语句不要直接放在'{'后面
    double a,b;
    scanf("%lf%lf",&a,&b);
    if(a>b)
    {
        printf("%lf",a);
    }
    else                   ///像if，else这类后面要接语句的关键词，后面最好加复合语句，以方便以后修改
    {
        printf("%lf",b);
    }
    return 0;
}

三、注解清晰：

//单行注释
 
/*多行注释
巴拉巴拉
以这个结尾->*/

【树】

<序>

解决树的问题无非就两种方法：DFS（深度优先遍历）和BFS（广度优先遍历）。

DFS框架：

/* 基本的二叉树节点 */
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    //前序
    traverse(root.left)
    //中序
    traverse(root.right)
    //后序
}

BFS框架：

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路

    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

1 二叉树的前、中、后序遍历（递归）

**题目描述：**给定一个二叉树，返回它的前序遍历。原题链接：link.

**思路：**二叉树是最适合使用递归的数据结构，根据二叉树递归的模板即可写出。

代码：

    //**********递归的先序遍历**********
    public static void recursivePreOrder(TreeNode p) {
        if (p == null) return;
            visit(p);
            recursivePreOrder(p.left);
            recursivePreOrder(p.right);
    }


    //**********递归的中序遍历**********
    public static void recursiveInOrder(TreeNode p) {
        if (p == null) return;
        recursiveInOrder(p.left);
        visit(p);
        recursiveInOrder(p.right);
    }


    //**********递归的后序遍历**********
    public static void recursivePostOrder(TreeNode p) {
        if (p == null) return;
        recursivePostOrder(p.left);
        recursivePostOrder(p.right);
        visit(p);
    }

拓展：递归思路

1.先设置嵌套出口

当极端情况，没有节点的时候：root==null时，退出。

 if(root==null){
   return;
 }

2.再设置嵌套入口

 if(root.left!=null){//若root左节点存在，则进入左节点，这里可以不写，在进入下次循环是判断
     helper(root.left,list); //设置入口
 }
  if(root.right!=null){//若root右节点存在，则进入右节点
   helper(root.right,list);//设置入口
  }

3.问题处理

将结点root的值存入数组中。

 list.add(root.val);

2 二叉树的前、中、后序遍历（非递归）

题目：给定一个二叉树，返回它的中序 遍历。

**思路：**二叉树的前，中，后序遍历都可以使用栈进行，其中他们都可以使用手算的思想，其中前序遍历可以哦利用栈的特性，后序遍历可以利用前序遍历的特性。

**前序遍历顺序： 根结点，左结点，右结点。**创建一个栈s存储节点，利用栈先进后出的特点模拟二叉树的遍历过程，首先将根节点压入栈，当栈不为空的时候进行此循环,栈为空表示已经二叉树遍历完成。取出根节点，并访问。由于栈是先进后出的特点，所以先进右节点以先取出左节点。

中序遍历顺序：左结点 ，根结点，右结点。我们首先需要找到的二叉树的最左边节点，然后下一个结点是右节点的最左结点，直到右节点没有左节点，即遍历它。需增加一个循环实现继续出栈，在出栈过程中压入右节点，以模拟中序遍历。此循环成立条件为栈不为空或者结点不为空（因为在出栈过程中会出现栈空但树未遍历完的状态，而且更重要的是）。

后序遍历顺序：左结点，右结点，根结点。因为：前序遍历顺序： 根结点，左结点，右结点.，后序遍历顺序： 左结点，右结点，根结点.
对二叉树的前序遍历代码稍作改变，即可成为后序遍历代码。

如何改变？见下图：

故：
1.想要改变左右结点位置，便需要交换左右结点入栈的顺序，则交换程序中以下两行代码的位置即可：

s.push(node.right);

s.push(node.left);

2.最后反转数组，即得到所求结果。

Collections.reverse(l);

建议使用手算的思想，首先走到最左边结点，当它没有右节点，或者右节点被遍历过，则遍历它。否则使用prev用来标记已经visit过的这个节点。

代码：

//**********非递归的先序遍历**********
    //栈的思想，按层次倒着进栈，利用后进先出解决顺序问题
    public static void iterativePreOrder_2(TreeNode p) {
        if (p == null) return;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //根节点入栈
        stack.push(p);
        while (!stack.empty()) {
            //出栈
            p = stack.pop();
            //访问
            visit(p);
            //由于栈是先进后出的特点，所以先进右节点以先取出左节点。
            if (p.right != null) stack.push(p.right);
            if (p.left != null) stack.push(p.left);
        }
    }
/*-----------------全是细节的手算非递归中序遍历-------------------------------------*/
    public  static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list =new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        //当处理根节点时，stack会为空，但是此时root.right!=null，则需要继续      
        while(!stack.isEmpty()||root!=null){
     //如何解决重复搜索？root!=null是精髓，如果右结点为null，则不继续下面循环，可以防止重复遍历，也可以作为遍历条件
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            list.add(root.val);
            //此处判断右节点是否为null,全是细节啊！！！！！！ 
            root=root.right;
        }
        return  list;
    }
    //**********基于手算非递归的后序遍历**********
    //注意prev的作用
    public static void iterativePostOrder(TreeNode p) {
        if (p == null) return;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode prev = p;
        while (!stack.empty() || p != null) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            p = stack.peek().right;
            //当它没有右节点，或者右节点被遍历过，则遍历它
            if (p == null || p == prev) {
                p = stack.pop();
                visit(p);
                //prev用来标记已经visit过这个节点
                prev = p;
                //防止死循环，查找栈顶的右节点
                p = null;
            }
        }
    }

拓展：

  
   //前序遍历手算的思想，先变访问边找，找到最左下方的，然后向上再向访问右边的
    public static void iterativePreOrder_1(TreeNode p) {
        if (p == null) return;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (!stack.empty() || p != null) {
            while (p != null) {
                System.out.println(p.val);
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            p = p.right;
        }
    }
    //**********基于前序遍历的非递归的后序遍历**********
    //栈的思想，按层次倒着进栈，利用后进先出解决顺序问题
    Collections.reverse(l);
    public static void iterativePreOrder_2(TreeNode p) {
        if (p == null) return;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //根节点入栈
        stack.push(p);
        while (!stack.empty()) {
            //出栈
            p = stack.pop();
            //访问
             visit(p);
            if (p.right != null) stack.push(p.left);
            if (p.left != null) stack.push(p.right);
        }    
    }

   //**********非递归的后序遍历**********
    //双栈法，易于理解
    public static void iterativePostOrder_3(TreeNode p) {
        if (p == null) return;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        Stack<TreeNode> result = new Stack<TreeNode>();
        while (!stack.empty() || p != null) {
            while (p != null) {
                stack.push(p);
                result.push(p);
                p = p.right;
            }
            if (!stack.empty()) p = stack.pop().left;
        }3
        while (!result.empty()) {
            p = result.pop();
            visit(p);
        }
    }

3 二叉树的层次遍历（BFS）

题目：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。原题传送门：link.

**思路：**BFS的模板为：

1. 如果不需要确定当前遍历到了哪一层，模板如下：

   void bfs() {
    vis[] = {0}; // or set
    queue<int> pq(start_val);
   
    while (!pq.empty()) {
        int cur = pq.front(); pq.pop();
        for (遍历cur所有的相邻节点nex) {
            if (nex节点有效 && vis[nex]==0){
                vis[nex] = 1;
                pq.push(nex)
            }
        } // end for
    } // end while
   }
   

上述是伪代码，不仅可用于二叉树，可针对所有用BFS解题。

1. 如果需要确定遍历到哪一层，模板如下；

   void bfs() {
    int level = 0;
    vis[] = {0}; // or set
    queue<int> pq(original_val);
    while (!pq.empty()) {
        int sz = pq.size();
   
        while (sz--) {
                int cur = pq.front(); pq.pop();
            for (遍历cur所有的相邻节点nex) {
                if (nex节点有效 && vis[nex] == 0) {
                    vis[nex] = 1;
                    pq.push(nex)
                }
            } // end for
        } // end inner while
        level++;
   
    } // end outer while
   }
   

代码：

/*--------------------------二叉树打印多行------------------------------*/
public static ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
       ArrayList<Integer> list=new ArrayList<>();
        ArrayList<TreeNode> queue = new ArrayList<>();
        queue.add(root);
       while(queue.size() != 0){
           TreeNode node=queue.remove(0);
           if(node.left!=null) queue.add(node.left);
           if(node.right!=null) queue.add(node.right);
           list.add(node.val);
       }
        return  list ;
    }
/*--------------------------之字型打印二叉树------------------------------*/
//思路:用两个栈，s1存储奇数层序列，s2存偶数层节点；s1打印时正向在s2中存储左右节点。s2打印时反向在s1中存储左右节点。
   public static ArrayList<Integer> print (TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        Queue<TreeNode> queue=new LinkedList<>();
        ArrayList<Integer> list=new ArrayList<>();
        stack.push(root);
        //有一个不为空则继续
        while (!stack.isEmpty()||queue.size()!=0){
            //栈循环入队
            while (!stack.isEmpty()){
                TreeNode node=stack.pop();
                if(node.left!=null)queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
                list.add(node.val);
            }
            //队循环入栈
            while (queue.size()!=0){
                TreeNode node=queue.remove();
                if(node.left!=null)stack.add(node.left);
                if(node.right!=null)stack.add(node.right);
                list.add(node.val);
            }
        }
        return list;
    }
/*--------------------------之字型打印二叉树2------------------------------*/
 public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        LinkedList<TreeNode> q = new LinkedList<>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        boolean rev = true;
        q.add(pRoot);
        while(!q.isEmpty()){
            int size = q.size();
            ArrayList<Integer> list = new ArrayList<>();
            for(int i=0; i<size; i++){
                TreeNode node = q.poll();
                if(node == null){continue;}
                if(rev){
                    list.add(node.val);
                }else{
                    list.add(0, node.val);
                }
                q.offer(node.left);
                q.offer(node.right);
            }
            if(list.size()!=0){res.add(list);}
            rev=!rev;
        }
        return res;
    }
/*--------------------------之字型打印二叉树3------------------------------*/
public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        int layer = 1;//记录奇偶性
        //s1存奇数层节点，s2存偶数层节点
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        s1.push(pRoot);//预先存入一个节点
       //定义数组存储节点内的值
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
       //两个栈都不为空循环
        while (!s1.empty() || !s2.empty()) {
            if (layer%2 != 0) { //如果为奇
                ArrayList<Integer> temp = new ArrayList<Integer>();
                while (!s1.empty()) {
                    TreeNode node = s1.pop(); //出栈
                    if(node != null) {   //结点不为空
                        temp.add(node.val);  //栈不为空
                      //System.out.print(node.val + " ");
                        s2.push(node.left);  //结点不为空
                        s2.push(node.right);
                    }
                }
                if (!temp.isEmpty()) { //表不为空
                    list.add(temp);  //导入节点
                    layer++;   //记录为偶
                    //System.out.println();
                }
            } else {
                ArrayList<Integer> temp = new ArrayList<Integer>();
                while (!s2.empty()) {
                    TreeNode node = s2.pop();
                    if(node != null) {
                        temp.add(node.val);
                        //System.out.print(node.val + " ");
                        s1.push(node.right);
                        s1.push(node.left);
                    }
                }
                if (!temp.isEmpty()) {
                    list.add(temp);
                    layer++;
                    //System.out.println();
                }
            }
        }
        return list;
    }

4 合并二叉树

题目：给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

//递归写法
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        //关键点：如果某一个为空，则直接返回另外一个，另外一个不管为不为空都可以
        if (t1 == null)
            return t2;
         //关键点：如果某一个为空，则直接返回另外一个，另外一个不管为不为空都可以
        if (t2 == null)
            return t1;
        t1.val += t2.val;//精髓，两个相加，都不为空的话
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}
//关键点位置其实是简写
           if(t1==null){
            if(t2==null){
                return t2;
            }else{
                return t2;
            }
        }
        if(t2==null){
            if(t1==null){
                return t1;
            }else{
                return t1;
            }
        }
        if(t1!=null&&t2!=null){
            t1.val=t1.val+t2.val;
        }
//

    /*---------------------------迭代----------------------------*/
    public static  TreeNode mergeTrees2(TreeNode t1, TreeNode t2) {
        Stack<TreeNode[]> stack =new Stack<>();
        stack.push(new TreeNode[]{t1,t2});
        while(!stack.isEmpty()){
            TreeNode[] node =stack.pop();
            //关键点：如果此时t2为null，说明不会再相加了。
            if(node[0]==null||node[1]==null){
                continue;
            }
            node[0].val=node[0].val+node[1].val;
            //如果为空，则直接赋值t2对应结点
            if(node[0].left==null){
                node[0].left=node[1].left;
            //否则，要入栈继续迭代
            }else{
                stack.push(new TreeNode[]{node[0].left,node[1].left});
            }
            if(node[0].right==null){
                node[0].right=node[1].right;
            }else{
                stack.push(new TreeNode[]{node[0].right,node[1].right});
            }
        }
        return t1;
    }

5 翻转二叉树

    /*---------------------DFS-----------------------*/
    public static TreeNode invertTree(TreeNode root) {
        //寻找结束结点
        if(root==null){
            return null;
        }
        //遍历左右模板
        invertTree(root.left);
        invertTree(root.right);
        //后序进行交换
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        return root;
    }

剑指Offer: 二叉树的镜像

1. 题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:二叉树的镜像定义：源二叉树

    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

原题传送门：link.

2. 关键词

二叉树的镜像

3. 思路

• 先前序遍历这棵树的每个结点，如果遍历到的结点有子结点，就交换它的两个子节点，
  当交换完所有的非叶子结点的左右子结点之后，就得到了树的镜像
• 递归方法的解题思路：
  1. 递归算法一定有一个结束条件，不然递归会一直进行下去
  2. 递归算法一定会实现一定的功能
  3. 递归算法一定有入口

4. 代码实现（Java）

/* 先前序遍历这棵树的每个结点，如果遍历到的结点有子结点，就交换它的两个子节点，
当交换完所有的非叶子结点的左右子结点之后，就得到了树的镜像 */
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
//递归方法1
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        TreeNode tmp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tmp);
        return root;
    }
}
//递归方法2
public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null){
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        Mirror(root.left);
        Mirror(root.right);
    }
}
//使用辅助栈
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node.left != null) stack.add(node.left);
            if(node.right != null) stack.add(node.right);
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
}

5. 时间复杂度

两种方式的：
时间复杂度 O(N)
空间复杂度 O(N)

6 二叉树的最大深度

   /*-------------------递归----------------------*/
    public static  int maxDepth(TreeNode root) {
         if(root==null){
             return 0;
         }
         //当需要携带值时候使用参数
         int left=maxDepth(root.left);
         int right=maxDepth(root.right);

         return Math.max(left,right)+1;
    }
    /*-------------------迭代----------------------*/
    public static  int maxDepth1(TreeNode root) {
        if(root==null) return 0;
        Queue<TreeNode> node=new LinkedList<>();
        node.add(root);
        int deep=0;
        int size=1;
        while(!node.isEmpty()){
            TreeNode temp=node.poll();
            size--;
            if(temp.right!=null) node.add(temp.right);
            if(temp.left!=null) node.add(temp.left);
            if(size==0){
                deep++;
                size=node.size();
            }
        }
        return deep;
    }

代码拓展（Java）

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
    public int TreeDepth(TreeNode root) {
        if(root==null){
        return 0;
        } 
        //统计左节点的数
        int LD=TreeDepth(root.left);
        //统计左节点的数
        int RD=TreeDepth(root.right);
        //到底端时h=1,每退出一层就返回对比左右子树最大深度并加1，最后返回的值就是最大的深度
        return (LD>RD?LD:RD)+1;
}
//非递归
import java.util.Queue;
import java.util.LinkedList;
 
public class Solution {
    public int TreeDepth(TreeNode pRoot)
    {
        if(pRoot == null){
            return 0;
        }
 //队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。
//LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(pRoot);
        //出栈时count记录出栈结点数，记录nextCount记录本层结点数
        int depth = 0, count = 0, nextCount = 1;
        //因为，在循环外队列中已经放入了一个节点，所以循环结束的条件为队列为空
        while(queue.size()!=0){
        //count记录出队的节点数
            TreeNode top = queue.poll();
            count++;
            if(top.left != null){
                queue.add(top.left);
            }
            if(top.right != null){
                queue.add(top.right);
            }
            //满足条件则表示，本层节点出队完成，深度加1
            if(count == nextCount){
                // nextCount记录本层节点数
                nextCount = queue.size();
                count = 0;
                depth++;
            }
        }
        return depth;
    }
}

package 树;

import java.util.Stack;

public class 二叉树的深度 {
    public  static  int  treeDeep1 (TreeNode root){
        if(root==null) return 0;
        int left=treeDeep1(root.left);
        int right=treeDeep1(root.right);
        return (left>right?left:right)+1;
    }
    public  static int treeDeep2(TreeNode root){
        Stack<TreeNode> stack1=new Stack<>();
        stack1.push(root);
        //记录本层的节点消耗
        int count=1;
        //记录深度
        int deep=0;
        //记录下层的节点数量
        int nextcount=0;
        while(!stack1.isEmpty()){
            TreeNode node=stack1.pop();
            count--;
            if(node.left!=null){
                stack1.push(node.left);
                nextcount++;
            }
            if(node.right!=null){
                stack1.push(node.right);
                nextcount++;
            }
            if(count==0){
                deep++;
                count=nextcount;
                nextcount=0;
            }
        }
        return deep;
    }
}

7 对称二叉树

题目描述

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

原题传送门：link.

2. 关键词

字符串

3. 思路

• 思路：首先根节点以及其左右子树，左子树的左子树和右子树的右子树相同
• 左子树的右子树和右子树的左子树相同即可，采用递归
• 非递归也可，采用栈或队列存取各级子树根节点

如图

根据上图可知：若满足对称二叉树，必须满足：

1. L->val == R->val
2. L->left->val == R->right->val
3. L->right->val == R->left->val

因此可以自顶向下，递归求解即可。

1. 设置一个递归函数isSame(r1, r2),表示如果对称，返回true，否则返回false

2. 递归终止条件：r1==nullptr && r2==nulllptr, 直接返回true，否则，如果只有一个为nullptr，返回false

3. 下一步递归：如果r1->val == r2->val, 则isSame(root1->left, root2->right) && isSame(root1->right, root2->left);

4. 代码（Java）

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

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot == null){
            return true;
        }
        return comRoot(pRoot.left, pRoot.right);
    }
    private boolean comRoot(TreeNode left, TreeNode right) {
        //必须到根节点所以必须这么写
        //如果左节点为null，那么右节点为null,则返回真,否则返回false
        if(left == null) return right==null;
        //如果左节点不为null，右节点为null，返回假
        if(right == null) return false;
        if(left.val != right.val) return false;
        return comRoot(left.right, right.left) && comRoot(left.left, right.right);
    }
}

代码拓展：

  //1. 它们的两个根结点具有相同的值
    //2. 每个树的右子树都与另一个树的左子树镜像对称
    /*---------------------DFS------------------------*/
    public static boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }
    public static boolean check(TreeNode p, TreeNode q) {
        //如果都没有结点，自然为true
        if(p==null&&q==null){
            return  true;
        }
        //如果有一个为null时，另一个一定不为null，则false
        if(p==null||q==null){
            return  false;
        }
        //否则判断值&&左结点的左结点值和右结点的右结点值&&左结点的右结点值和右结点的左结点值
        return  p.val==q.val&&check(p.left,q.right)&&check(p.right,q.left);
    }
//首先我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
    /*---------------------BFS------------------------*/
    public static boolean isSymmetric1(TreeNode root) {
        return check1(root,root);
    }
    public static boolean check1(TreeNode p, TreeNode q) {
        //先存入一个队列中
        Queue<TreeNode> queue=new LinkedList<>();
        //
        queue.add(p);
        queue.add(q);
        while(!queue.isEmpty()){
            //出队比较
            TreeNode left=queue.poll();
            TreeNode right=queue.poll();
            //此时为true，这里continue;
            if(left==null&&right==null){
                continue;
            }
            //这三种情况下为false
            if(left==null||right==null||left.val!=right.val){
                return  false;
            }
            //插入1
            queue.add(left.left);
            queue.add(right.right);
            //插入2
            queue.add(left.right);
            queue.add(right.left);
        }
        return  true;
    }

8 二叉树的直径

题目：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

思路

1. 首先我们知道一条路径的长度为该路径经过的节点数减一，所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。
2. 而任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。

代码

  //不一定经过根节点
    //首先我们知道一条路径的长度为该路径经过的节点数减一，所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。
    //而任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。
    /*-------------------------DFS-------------------------*/
    static int ans;
    public static int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans;
    }
    public static int depth(TreeNode node) {
        if (node == null) return 0; // 访问到空节点了，返回0
        int L = depth(node.left); // 左儿子为根的子树的深度
        int R = depth(node.right); // 右儿子为根的子树的深度
        //与求最大深度不同的是，这里要记录每个节点为起点的最大长度
        ans = Math.max(ans, L+R); // 计算d_node即L+R+1 并更新ans
        return Math.max(L, R)+1; // 返回该节点为根的子树的深度
    }

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 class Solution {
    int maxd=0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return maxd;
    }
    public int depth(TreeNode node){
        if(node==null){
            return 0;
        }
        int Left = depth(node.left); // 左儿子为根的子树的深度
        int Right = depth(node.right);// 右儿子为根的子树的深度
        maxd=Math.max(Left+Right,maxd);//将每个节点最大直径(左子树深度+右子树深度)当前最大值比较并取大者
        return Math.max(Left,Right)+1;//返回节点深度
    }
} 

9 二叉树展开为链表

**题目：**给定一个二叉树，原地将它展开为一个单链表。

**思路：**递归，递归思想原来是这样！

题解：

分为三步：

• 首先将根节点的左子树变成链表
• 其次将根节点的右子树变成链表
• 最后将变成链表的右子树放在变成链表的左子树的最右边

class Solution {
    public void flatten(TreeNode root) {
        if(root == null){
            return ;
        }
        //将根节点的左子树变成链表
        flatten(root.left);
        //将根节点的右子树变成链表
        flatten(root.right);
        TreeNode temp = root.right;
        //把树的右边换成左边的链表
        root.right = root.left;
        //记得要将左边置空
        root.left = null;
        //找到树的最右边的节点
        while(root.right != null) root = root.right;
        //把右边的链表接到刚才树的最右边的节点
        root.right = temp;
    }
}

10 二叉树的最近公共祖先

11 二叉树的右视图

public class 二叉树的右视图 {
    public static void main(String[] args) {
        //构造树1
        int[] nums1={1,2,5,3,4};
        int[] nums2={2,5,1,3,4};
        TreeNode node1=createTree.buildTree(nums1,nums2);
        TreeOperation.show(node1);
        List<Integer> list=rightSideView(node1);
        for(Integer n:list){
            System.out.println(n);
        }

    }
    /*-------------------------DFS----------------------------*/
    static  ArrayList<Integer> res = new ArrayList<>();
    public static  List<Integer> rightSideView(TreeNode root) {
          dfs(root, 0); // 从根节点开始访问，根节点深度是0
          return res;
     }
     private static void dfs(TreeNode root, int depth) {
          if (root == null) {
          return;
       }
        // 先访问 当前节点，再递归地访问 右子树 和 左子树。
      if (depth == res.size()) {   // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
      res.add(root.val);
       }
         depth++;
      //System.out.println(depth);
      dfs(root.right, depth);
      dfs(root.left, depth);
       }
  }

12 二叉树和为k的路径

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    private ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
    
    private ArrayList<Integer> list = new ArrayList<Integer>();
    
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null)    return lists;
        list.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null) {
            lists.add(new ArrayList<Integer>(list));
        } else {
            FindPath(root.left, target);
            FindPath(root.right, target);
        }
        list.remove(list.size()-1);
        return lists;
    }
}

13 二叉树的下一个结点

1. 题目描述

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

原题传送门：link.

2. 关键词

二叉树

3. 思路

   • 根据中序遍历的规则，当结点存在右子树的时候，中序遍历的下一个结点为右子树的最左节点。

   • 但是当节点不存在右子树的时候，中序遍历的下一个结点必定为该节点的父辈节点。但是究竟是哪一辈呢？

   • 根据中序遍历特性，左父结点一定已经被中序遍历访问过，所以下一个结点一定是在父节点路径上的第一个右父节点。代码如下

4. 代码（Java）

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

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

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        //如果它的右节点不为空，则为右节点的最左节点
        TreeLinkNode temp=null;
        if(pNode.right!=null){
            temp=pNode.right;
            while(temp.left!=null){
                temp=temp.left;
            }
            return temp;
        }
        temp=pNode;
        //如果它的右节点不为空
        //temp.next!=null非root节点,并且temp不是左节点
        while(temp.next!=null&&temp!=temp.next.left){
            temp=temp.next;
        }
        //如果是左节点，那么它的父节点就是
        return temp.next;
    }
}

14 树的子结构

题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）原题传送门：link.

思路

遍历A的每个根节点与B根节点对比，如果根节点相同进入另一个递归函数进行对比。

另一个函数，遍历A,B左(右)节点，如果b遍历到最后则匹配，如果a遍历到最后b还有节点，则不匹配，如果节点值不同则不匹配。

• 首先设置标志位result = false，因为一旦匹配成功result就设为true，剩下的代码不会执行，如果匹配不成功，默认返回false
• 递归思想，如果根节点相同则递归调用DoesTree1HaveTree2（），如果根节点不相同，则判断tree1的左子树和tree2是否相同，再判断右子树和tree2是否相同
• 注意null的条件，HasSubTree中，如果两棵树都不为空才进行判断，DoesTree1HasTree2中，如果Tree2为空，则说明第二棵树遍历完了，即匹配成功，tree1为空有两种情况
  （1）如果tree1为空&&tree2不为空说明不匹配，
  （2）如果tree1为空，tree2为空，说明匹配。
• 牛客网传送门：link.

代码实现（Java）

public class Solution {
    public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
        boolean result = false;
        //当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false
        if (root2 != null && root1 != null) {
            //如果找到了对应Tree2的根节点的点
            if(root1.val == root2.val){
                //以这个根节点为为起点判断是否包含Tree2
                result = doesTree1HaveTree2(root1,root2);
            }
            //如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2
            if (!result) {
                result = HasSubtree(root1.left,root2);
            }
             
            //如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2
            if (!result) {
                result = HasSubtree(root1.right,root2);
               }
            }
            //返回结果
        return result;
    }
 
    public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
        //如果Tree2已经遍历完了都能对应的上，返回true
        if (node2 == null) {
            return true;
        }
        //如果Tree2还没有遍历完，Tree1却遍历完了。返回false
        if (node1 == null) {
            return false;
        }
        //如果其中有一个点没有对应上，返回false
        if (node1.val != node2.val) {  
                return false;
        }
          //如果根节点对应的上，那么就分别去子节点里面匹配
       return
doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
    }

15 平衡二叉树

1. 题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。
原题传送门：link.

2. 关键词

二叉树深度

3. 思路

• 从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历
• 之前是因为自己对平衡二叉树对定义不是很清楚：平衡二叉树的左右子树也是平衡二叉树，那么所谓平衡就是左右子树的高度差不超过1.

4. 代码（Java）

public class Solution {
    boolean isBalanced=true;//用于判断的变量
    public boolean IsBalanced_Solution(TreeNode root) {
        TreeDepth(root);
        return isBalanced;
    }

    public int TreeDepth(TreeNode root) {
        if(root==null)
            return 0;
        int left=TreeDepth(root.left);
        int right=TreeDepth(root.right);
        //相对于求树的深度只多了这一步
        if(left-right>1 || right-left>1)
            isBalanced=false;
        return left>right?left+1:right+1;
    }
}

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return getDepth(root) != -1;
    }
    //这里与求二叉树高度类似
    private int getDepth(TreeNode root) {
        if (root == null) return 0;
         //左子树和右子树有可能不平衡，不平衡就返回-1
        int left = getDepth(root.left);
        if (left == -1) return -1;
        int right = getDepth(root.right);
        if (right == -1) return -1;
        //Math.abs(x) 函数返回指定数字 “x“ 的绝对值
        //如果left - right，绝对值大于1则不是ASL树，返回值；若绝对值小于等于1，返回left，right中最大值。
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }
}

5.复杂度

• 暂无

6. 知识积累

• 什么是二叉排序（BST）树？
  二叉树是空树或者满足一下条件：

1. 若它的左子树不为空，则左子树上的左节点的关键字的值均小于根节点关键字的值。
2. 若它的右子树不为空，则右子树上的左节点的关键字的值均大于根节点关键字的值。
3. 左右子树又分别是一颗二叉排序树

• 什么是平衡二叉（AVL）树？
  平衡二叉树首先是二叉查找树，由于树越矮查找效率越高，就有了二叉查找树。二叉平衡树中所有平衡因子只能是-1，0，1三个值
• 什么是平衡因子？
  一个结点的平衡因子为其左子树的高度减去右子树高度的差。
• 什么是红黑树？
  红黑树是一颗二叉搜索树，它相对二叉搜索树增加了一个存储位来标识结点颜色，可以使 Red 或 Black。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，确保没有一条路径会比其他路径长出两倍。

16 从前序与中序遍历序列构造二叉树

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

17 二叉树中的最大路径和

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

18 验证二叉搜索树

https://leetcode-cn.com/problems/validate-binary-search-tree

19 不同的二叉搜索树

https://leetcode-cn.com/problems/unique-binary-search-trees

20 二叉搜索树与双向链表

1. 题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向

原题传送门：link.

2. 关键词

二叉搜索树

3. 思路

用一个全局变量pre去保存前一个节点，然后再去创建节点之间的关系

//https://blog.nowcoder.net/n/17c95de2427e49abb207a6a9d37c602d?f=comment

4. 代码（Java）

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    TreeNode pre=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null)
            return null;
        Convert(pRootOfTree.right);
        //当当前节点（中序遍历节点的顺序）依次与之前节点构成双向链表。
        if (pre!= null){
            pRootOfTree.right=pre;
            pre.left=pRootOfTree;
        }
        pre=pRootOfTree;
        Convert(pRootOfTree.left);
        return pre;
    }
}

5. 知识积累

暂无

21 把二叉搜索树转换为累加树

**题目：**给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

代码：

    /*----------------------DFS------------------------*/
    static int num=0;
    public static TreeNode convertBST(TreeNode root) {
        if(root==null) return null;

        convertBST(root.right);
        //中序遍历是有序的，如果想要倒序，则反转左右节点的遍历顺顺序
        //左中右->右中左
        //注意，这里遍历的都是根节点
        root.val=num+root.val;
        num=root.val;

        convertBST(root.left);
        return root;
    }
    /*----------------------BFS------------------------*/
    public static TreeNode convertBST1(TreeNode root) {
        Stack<TreeNode> stack=new Stack<>();
        int num1=0;
        TreeNode temp=root;
        while(!stack.isEmpty()||root!=null){
            //将中序遍历的代码改为右中左的顺序
            while(root!=null){
                stack.push(root);
                root=root.right;
            }
            root=stack.pop();
            //这里进行累加
            root.val=root.val+num1;
            num1=root.val;
            
            root=root.left;
        }
        return temp;
    }

22 二叉搜索树的第k个结点

1. 题目描述

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

原题传送门：link.

2. 关键词

二叉树的中序遍历

3. 思路

• 思路：二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。

  所以，按照中序遍历顺序找到第k个结点就是结果。

4. 代码（Java）

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
 
    }
 
}
*/
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null || k <= 0){
            return null;
        }
        TreeNode[] result = new TreeNode[1];
        KthNode(pRoot,k,new int[1],result);
        return result[0];
    }
     void KthNode(TreeNode pRoot, int k,int[] count,TreeNode[] result){
         if(result[0] != null || pRoot == null){
             return;
         }
         KthNode(pRoot.left,k,count,result);
         count[0]++;
         if(count[0] == k){
             result[0] = pRoot;
         }
         KthNode(pRoot.right,k,count,result);
     }
 
}

23 实现 Trie (前缀树)

24 二叉树的序列化与反序列化

25 重建二叉树

1. 题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

原题传送门：link.

2. 关键词

重建二叉树，前序遍历，后序遍历

3. 思路

因为是树的结构，一般都是用递归来实现。

• 用数学归纳法的思想就是，假设最后一步，就是root的左右子树都已经重建好了，那么我只要考虑将root的左右子树安上去即可。

• 根据前序遍历的性质，第一个元素必然就是root，那么下面的工作就是如何确定root的左右子树的范围。

• 根据中序遍历的性质，root元素前面都是root的左子树，后面都是root的右子树。那么我们只要找到中序遍历中root的位置，就可以确定好左右子树的范围。

• 正如上面所说，只需要将确定的左右子树安到root上即可。递归要注意出口，假设最后只有一个元素了，那么就要返回。

4. 代码

import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        //数组长度为0的时候要处理
        if(pre.length == 0){
            return null;
        }
 
        int rootVal = pre[0];
 
        //数组长度仅为1的时候就要处理
        if(pre.length == 1){
            return new TreeNode(rootVal);
        }
 
        //我们先找到root所在的位置，确定好前序和中序中左子树和右子树序列的范围
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = 0;
        for(int i=0;i<in.length;i++){
            if(rootVal == in[i]){
                rootIndex = i;
                break;
            }
        }
 
        //递归，假设root的左右子树都已经构建完毕，那么只要将左右子树安到root左右即可
        //这里注意Arrays.copyOfRange(int[],start,end)是[)的区间
        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,rootIndex+1),Arrays.copyOfRange(in,0,rootIndex));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,rootIndex+1,pre.length),Arrays.copyOfRange(in,rootIndex+1,in.length));
 
 
        return root;
    }
}

//链接：https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6?f=discussion
//来源：牛客网

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
        return root;
    }
    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
    private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
         
        if(startPre>endPre||startIn>endIn)
            return null;
        TreeNode root=new TreeNode(pre[startPre]);
         
        for(int i=startIn;i<=endIn;i++)
            if(in[i]==pre[startPre]){
root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
                      break;
            }
                 
        return root;
    }
}

5. 知识积累

// 树结点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) { }
};
// 建树的伪代码
TreeNode* build(1...) {
    if (2...) return nullptr;
    TreeNode *root = new TreeNode(3...);
    root->left = build(4...); // 递归建立左子树
    root->right = build(5...); // 递归建立右子树
    return root;
}

如果大家知道了上述建树的伪代码后，那么括号应该填什么呢？
假设 1.是一个数组vector，是需要建树的元素
那么 2.数组为空，然后 return nullptr.

3. 根结点的值
4. 左子树的数组元素
5. 右子树的数组元素

【链表】

1 反转链表

题目描述 输入一个链表，反转链表后，输出新链表的表头 原题传送门：link.

思路

• 头插法
• 返回头节点应该为newhead.next
• newhead应该被定义为链表
• 递归方法传送门：link.

代码

/*------------------------头插法---------------------*/
public static ListNode reverseList(ListNode head) {
    //这里需要一个新节点
    ListNode newhead=new ListNode(-1);
    newhead.next=null;
    while(head!=null){
        //标记
        ListNode next=head.next;
        //头插法
        head.next=newhead.next;
        newhead.next=head;
        //后退
        head=next;
    }
    return newhead.next;
}
/*------------------------递归---------------------*/
public static ListNode reverseList2(ListNode head) {
    //假设链表没有结点或者只有1个节点
    if(head==null||head.next==null){
        return head;
    }
    //假设链表有2个以上结点
    ListNode newhead=reverseList2(head.next);
    // //必须使用head.next.next，而非newhead.next,因为只有第一次时head.next=newhead;
    head.next.next=head;
    //释放指针，否则会在链表尾部生成环：7 6 5 4 3 2 1 2 1 2  ...
    head.next=null;
    //newhead不能动
    return newhead;
}

2 相交链表

题目：编写一个程序，找到两个单链表相交的起始节点。

**类型：**双指针法

思路：当它

最终两个指针分别走过的路径为：
指针A :a+c+b
指针B :b+c+a

    public  static  ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //这是高手！！！！
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            //思想就是当一个链表到达null时，就从另一条链表的开头走
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

3 链表中环的入口结点

题目描述：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。原题传送门：link.

思路

如何找到环的交点：

用快慢指针，慢指针每次走一步，快指针每次走两步，快指针与慢指针第一次相遇的的位置慢指针走了t步，快指针走了2t步，如果不相遇则没有环。

t=x+a， 2t=x+a+kc (c为环的结点数，k=1,2,3…)

可得到 2x+2a=x+a+kc， x=kc-a， x=(k-1)c+ c-a

这里的k-1无论是多少也不影响。环上的指针可能走了很多圈，但最后一定会在节点部分可另外一个指针相遇。

可以得到，当两个指针相遇时，把一个指针的指向链表开头，两指针都以每次一步的速度走，两指针再次相遇时就是环的入口结点。

**为什么用快慢指针可以判断是否有环：**https://blog.csdn.net/mucaoyx/article/details/81395782

代码（Java）

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        //设置快慢指针起始位置
        ListNode slow= head;
        ListNode fast=head;
        //结束条件
        while(fast!=null){
            slow=slow.next;
            //防止空指针异常
            if(fast.next==null){
                return null;
            }
            fast=fast.next.next;
            //有环条件
            if(slow==fast){
                break;
            }
        }
        //判断是否有环
        if(fast==null){
            return null;
        }else {
            //无环则找出他们的交点
            slow=head;
            while(slow!=fast){
                slow=slow.next;
                fast=fast.next;
            }
        }
        return slow;
    }
}

4 链表中倒数第k个结点

题目描述：输入一个链表，输出该链表中倒数第k个结点。原题传送门：link.

思路：三指针

代码实现（Java）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public  ListNode removeNthFromEnd(ListNode head, int n) {
      //假设要删除第一个结点，如何处理，此时需要一个空的头结点
       ListNode newhead=new ListNode(0);
       newhead.next=head;
       ListNode slow= newhead;
       ListNode fast= newhead;
        //需要两次遍历
       for(int i=1;i<=n+1;i++){
         fast=fast.next;
       }
       while(fast!=null){
           slow=slow.next;
           fast=fast.next;
       }
       slow.next=slow.next.next;
       return newhead.next;
    }
}

5 合并两个排序的链表

1. 题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

2. 关键词

反转链表

3. 思路

• 非递归
• 尾插法
• 递归传送门：link.

4. 代码实现（Java）

/*
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode list3 = new ListNode (-1);
        ListNode root=list3;
        while(list1!=null&&list2!=null){
            if(list2.val>list1.val)
            {
                root.next=list1;
                list1=list1.next;
                root=root.next;                
            }else{
                root.next=list2;
                list2=list2.next;
                root=root.next;
            }
        }
        root.next=list1!=null?list1:list2;
        return list3.next;
    }
}
/**
 * 递归做法
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1==null) return l2;
    if(l2==null) return l1;
    
    if(l1.val>l2.val)
    {
        l2.next=mergeTwoLists(l1,l2.next);//这是嵌套入口，
        return l2;
    }else{
        l1.next=mergeTwoLists(l1.next,l2);
        return l1;
    }
    }
}

递归思路

1.先设置嵌套出口

当极端情况下：l1为空，返回l2；l2为空，返回l1。

 if(l1==null) return l2;
 if(l2==null) return l1;

2.再设置嵌套入口

若l1.val>l2.val，那么l2是所需要的结点，故,
l2.next=mergeTwoLists(l1,l2.next)。

if(l1.val>l2.val){
        l2.next=mergeTwoLists(l1,l2.next);
        //return l2;
    }else{
        l1.next=mergeTwoLists(l1.next,l2);
        //return l1;
    }

3.大问题化小问题

若l1.val>l2.val，那么l2是所需要的结点。故, return l2。
若l2.val>l1.val，那么l1是所需要的结点，故, return l1。

if(l1.val>l2.val){
        l2.next=mergeTwoLists(l1,l2.next);
        return l2;
    }else{
        l1.next=mergeTwoLists(l1.next,l2);
        return l1;
    }

6 孩子们的游戏

1. 题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

原题传送门：link.

2. 关键词

用线性表模拟环，取余

3. 思路

• 用线性表模拟环，为什么不用数组？因为数组增删不方便

4. 代码（Java）

import java.util.LinkedList; 
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n ==0 ) {
        return -1;}
        //加入第一个线性表
        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 0; i < n; i ++) {
            list.add(i);
        }
        //模拟环的操作，bt是从0开始的，bt= 0为第一个学生
        int bt = 0;
        while (list.size() > 1) {
            bt = (bt + m - 1) % list.size();//由于下标是从0开始的，所以这里要减去1
            list.remove(bt);
        }
         //当剩下一个小朋友，返回他的编号
        return list.get(0);
    }
}

5. 复杂度

• 暂无

6. 知识积累

• 暂无

简单选择

7 删除链表中重复的结点

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

三指针法

3. 思路

4. 首先添加一个头节点，以方便碰到第一个，第二个节点就相同的情况

5. 设置 pre ，last 指针， pre指针指向当前确定不重复的那个节点，所以使用一个空节点，而last指针相当于工作指针，一直往后面搜索。

6. 代码（Java）

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public static ListNode delete(ListNode listNode) {
       ListNode  newhead=new ListNode(0);
       newhead.next=listNode;
       ListNode pre=newhead;
       ListNode last=listNode.next;
        //遍历
       while (last!=null){
           //如果相等
           if(last.val==listNode.val){
               //一直循环到不相等那个值
               while(last.val==listNode.val){
                   last=last.next;
               }
               //链接归位
               pre.next=last;
               listNode=last;
               last=last.next;
               pre=pre.next;
           }
           else{
               //全部后退
               listNode=listNode.next;
               last=last.next;
               pre=pre.next;
           }

       }
       return newhead.next;
    }

}

8 两两交换链表中的节点

给定 1->2->3->4, 你应该返回 2->1->4->3.

package 数据结构与算法.链表;

import java.util.List;

//# 链表的两两翻转 # 给定链表:  1->2->3->4->5->6->7 # 返回结果：  2->1->4->3->6->5->7
public class 链表两两反转 {
    public static void main(String[] args) {
        ListNode headNode =new ListNode(1);
        ListNode node=new ListNode(2);
        ListNode node1=new ListNode(3);
        ListNode node2=new ListNode(4);
        ListNode node3=new ListNode(5);
        ListNode node4=new ListNode(6);
        ListNode node5=new ListNode(7);
        headNode.next=node;
        node.next=node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        ListNode next=headNode;
        System.out.print("正序打印结果:");
        while(next!=null){
            System.out.print(next.val+" ");
            next=next.next;
        }
        ListNode next1=swapPairs1(headNode);
        System.out.print("两两反转结果:");
        while(next1!=null){
            System.out.print(next1.val+" ");
            next1=next1.next;
        }
    }
    public static ListNode swapPairs(ListNode head) {
        // 1. 终止条件：当前没有节点或者只有一个节点，肯定就不需要交换了
        if (head == null || head.next == null) return head;

        // 2. 调用单元
        // 需要交换的两个节点是 head 和 head.next
        ListNode firstNode = head;
        ListNode secondNode = head.next;
        // firstNode 连接后面交换完成的子链表
        firstNode.next = swapPairs(secondNode.next);
        // secondNode 连接 firstNode
        secondNode.next = firstNode;

        // 3. 返回值：返回交换完成的子链表
        // secondNode 变成了头结点
        return secondNode;
    }
    //三指针法，并且用一个新建一个空结点指向头结点。
    public static ListNode swapPairs1(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode temp = pre;
        while(temp.next != null && temp.next.next != null) {
            ListNode start = temp.next;
            ListNode end = temp.next.next;
            temp.next = end;
            start.next = end.next;
            end.next = start;
            temp = start;
        }
        return pre.next;
    }
}

9 合并K个排序链表

**类型：**分治，类似于归并排序

class Solution {
    //主函数
   public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
       //归并排序中的分值策略
        return merge(lists, 0, lists.length - 1);
    }
    private ListNode merge(ListNode[] lists, int left, int right) {
        //
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        //左边
        ListNode l1 = merge(lists, left, mid);
        //右边
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

10 从尾到头打印链表

1. 题目描述

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

原题传送门：link.

2. 关键词

链表的头插法

3. 思路

• 首先使用头插法逆置链表
• 然后将链表导入到数组里

4. 代码实现（Java）

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
      ListNode newhead= new ListNode(-1);
        while(listNode!=null){
            ListNode next=listNode.next;
            listNode.next=newhead.next;
            newhead.next=listNode;
            listNode=next;
        }
        next=newhead.next;//newhead的下一个结点才是要导出的第一个结点
        ArrayList<Integer> list = new ArrayList<Integer>(-1);
        while(next!=null){
            list.add[next.val];
            next=next.next;
        }   
        return list;
    }
}  

5. 知识积累

需掌握数组，链表的基本操作和内部结构。

11 复杂链表的复制

1. 题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

原题传送门：link.

2. 关键词

复杂链表的复制

3. 思路

• 在每一个结点后面插入复制的结点
• 对复制结点的random的链接进行赋值
• 拆分出复制的链表

4. 代码（Java）

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
       RandomListNode p=pHead;
        RandomListNode t=pHead;
        //在每个节点后面插入一个节点并赋值
        while(p!=null){
            RandomListNode q=new RandomListNode(p.label);
            q.next=p.next;
            p.next=q;
            p=q.next;
        }
        //赋值random
        while(t!=null){
            RandomListNode q=t.next;
            if(t.random!=null)
            q.random=t.random.next;
            t=q.next;
             
        }
        //删除
        RandomListNode s=new RandomListNode(0);
        RandomListNode s1=s;
       while(pHead!=null){
           //定位，防止删除后找不到
           RandomListNode  q=pHead.next;
           //删除
           pHead.next=q.next;
           q.next=s.next;
           //插入
           s.next=q;
           s=s.next;
           //定位移动
           pHead=pHead.next;       
       }
        return s1.next;
    }
}

12 LRU缓存机制

代码：

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

13 排序链表

**题目：**在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

**类型：**归并排序，先递归分割，然后归并

【字符串】

<序>

String的用法：
//java中String是只读的，没有办法进行变换，因此需要使用StringBuilder。
String.length() //获取字符串的长度
String.charAt(i) //获取第i个字符的内容
String.subString(start) //获取[start,）的字符串
String.subString(start,end) //获取[start,end）中的字符串
char[] c = iniString.toCharArray() //将字符串转为char数组来进行改变字符内容
String.equal() //判断两个字符串是否相等

StringBuilder的用法：
除了String中支持的方法外，StringBuilder支持字符的增、删、改。
stringBuilder.append(“we”); //添加we在词尾
stringBuilder.insert(0,“we”);//在0的位置加入后面的内容
stringBuilder.delete(0,1); //删除[0,1)的数据
stringBuilder.deleteCharAt(0);
stringBuilder.setCharAt(0,‘p’); //在某一个独特位置设置字符
char c = stringBuilder.charAt(i);//查询某个位置上的字符
System.out.println(stringBuilder);
new String(stringBuilder);//用stringBuilder来初始化String

1 替换空格

题目描述：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。原题传送门：link.

思路

问题1：替换字符串，是在原来的字符串上做替换，还是新开辟一个字符串做替换
问题2：在当前字符串替换，怎么替换才更有效率（不考虑java里现有的replace方法）。
从前往后替换，后面的字符要不断往后移动，要多次移动，所以效率低下
从后往前，先计算需要多少空间，然后从后往前移动，则每个字符只为移动一次，这样效率更高一点

分析：由于函数返回为void，说明此题不能另外开辟数组，需要in-place操作。我们知道字符串的遍历无非是从左到右和从右到左两种。
1）如果从左到右，会发现如果遇到空格，会将原来的字符覆盖。于是，此方法不行。
2）那么就考虑从右向左，遇到空格，就填充“20%“，否则将原字符移动应该呆的位置。

代码实现（Java）

public class Solution {
    public String replaceSpace(StringBuffer str) {
        if(str==null){
            renturn null;
        }
        StringBuilder newStr=new StringBuilder();
        for(int i=0,i<str.length(),i++){
            if(Str.charAt(i)==''){
                newStr.append(%);
                newStr.append(2);
                newStr.append(0);
            }else{
                newStr.append(Str.charAt(i));
            }
        }
        return newStr.toString();
    }
}

5. 知识积累

• 考察String基本操作方法
  1、 获取字符串长度方法length()
  int length = str.length();
  2、获取字符串中的第i个字符方法charAt(i)
  char ch = str.charAt(i);

  3、向字符串中添加字符
  newStr.append(0);

  4、获取指定位置的字符方法

  getChars(indexBegin,indexEnd,array,arrayBegin)

  1. indexBegin：需要复制的字符串的开始索引

  2. indexEnd: 需要复制的字符串的结束索引，indexEnd-1

  3. array: 前面定义的char型数组的数组名

  4. arrayBegin:数组array开始存储的位置索引号

• String，StringBuffer，StringBuilder区别：
  1、String类是不可变类，即一旦一个String对象被创建以后，包含在这个对象中的字符序列是不可改变的，直至这个对象被销毁。
  2、StringBuffer对象则代表一个字符序列可变的字符串，当一个StringBuffer被创建以后，通过StringBuffer提供的append()、insert()、reverse()、setCharAt()、setLength()等方法可以改变这个字符串对象的字符序列。一旦通过StringBuffer生成了最终想要的字符串，就可以调用它的toString()方法将其转换为一个String对象。
  3、StringBuilder类也代表可变字符串对象。实际上，StringBuilder和StringBuffer基本相似，两个类的构造器和方法也基本相同。不同的是：StringBuffer是线程安全的，而StringBuilder则没有实现线程安全功能，所以性能略高。
  注：StringBuilder类也代表可变字符串对象。实际上，StringBuilder和StringBuffer基本相似，两个类的构造器和方法也基本相同。不同的是：StringBuffer是线程安全的，而StringBuilder则没有实现线程安全功能，所以性能略高。

原文传送门：link.

2 字符串的排列

题目描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

原题传送门：link.

思路：

• 所在网站//https://blog.csdn.net/qq_33575542/article/details/80825221

代码（Java）

/**
     * 1、递归算法
     *
     * 解析：http://www.cnblogs.com/cxjchen/p/3932949.html  (感谢该文作者！)
     *
     * 对于无重复值的情况
     *
     * 固定第一个字符，递归取得首位后面的各种字符串组合；
     * 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合； *递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
     *
     * 假如有重复值呢？
     * *由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。
     * 例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。
     * 但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。
     * 由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。
     *
     * 换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，
     * 所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！
     *
     *
     * @param str
     * @return
     */
package 字符串;

import java.nio.charset.Charset;
import java.util.*;

/**
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 * 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 * */
public class 字符串的排列 {
    public static void main(String[] args) {
        String str="abb";
        HashSet<String> charset=new HashSet<>();
        if(str!=null&&str.length()>0){
            helper(str.toCharArray(),charset,0);
        }

        Iterator<String> iterator = charset.iterator();//遍历器
        while(iterator.hasNext())System.out.print(iterator.next()+" ");//判断是否有，有就输出
    }
    private static void helper (char []chars,HashSet<String> charset, int i){
      //递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
        // for循环和swap的含义：对于“ABC”，
        // 第一次'A' 与 'A'交换，字符串为"ABC", pos为0， 相当于固定'A'
        // 第二次'A' 与 'B'交换，字符串为"BAC", pos为0， 相当于固定'B'
        // 第三次'A' 与 'C'交换，字符串为"CBA", pos为0， 相当于固定'C'
        if(i==chars.length-1){
          charset.add(String.valueOf(chars));
      }else{
            for(int j=i;j<chars.length;j++){
                    swap(chars,i,j);
                    helper(chars,charset,i+1);
                    swap(chars,j,i);
                }
            }
        }
    private static void  swap(char[] cs,int i,int j){
        char temp=cs[i];
        cs[i]=cs[j];
        cs[j]=temp;
    }
}

3. 整数中1出现的次数

**题目描述：**求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。原题传送门：link.

思路

• 链接：https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6?answerType=1&f=discussion

  。统计某个位置上 1出现的次数。如34，1在十位上出现的次数是10次
  （10到19），1在个位上出现的次数是4次（1，11，21，31），因此34中1出现了14次。

  对于整数n，将这个整数分为三部分：当前位数字cur，更高位数字high，更低位数字low，如：对于n=21034，当位数是十位时，cur=3，high=210，low=4。
  我们从个位到最高位 依次计算每个位置出现1的次数：
  在计算时，会出现三种情况
  1）当前位的数字等于0时，例如n=21034，在百位上的数字cur=0，百位上是1的情况有：00100-00199，01100-01199，……，20100-20199。一共有21100种情况，即high100;
  2）当前位的数字等于1时，例如n=21034，在千位上的数字cur=1，千位上是1的情况有：01000-01999，11000-11999，21000-21034。一共有21000+（34+1）种情况，即high1000+(low+1)。
  3）当前位的数字大于1时，例如n=21034，在十位上的数字cur=3，十位上是1的情况有：00010-00019，……，21010-21019。一共有(210+1)*10种情况，即(high+1)*10。

代码（Java）

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count=0;
        for(int i=1;i<=n;i*=10){  //i代表位数
            int high=n/(i*10); //更高位数字
            int low=(n%i);  //更低位数字
            int cur=(n/i)%10;  //当前位数字
            if(cur==0){
                count+=high*i;
            }else if(cur==1){
                count+=high*i+(low+1);
            }else{
                count+=(high+1)*i;
            }
        }
        return count;
    }
}

4 把数组排成最小的数

题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。原题传送门：link.

思路

• 自定义一个比较大小的函数，比较两个字符串s1, s2大小的时候，
• 先将它们拼接起来，比较s1+s2,和s2+s1那个小,
• 由于求能排成的最小数字，所以如果s1+s2小，那说明s2应该放前面
• compareTo()是用来比较大小的，a.compareTo(b)，a>b 的情况返回1，a<b 的情况返回-1， a=b的情况返回0

代码（Java）

public String PrintMinNumber(int [] numbers) {
        if(numbers == null || numbers.length == 0) return "";
        int len = numbers.length;
        String[] str = new String[len];
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < len; i++){
// String.valueOf(numbers[i]) numbers[i] 转换成字符串 
            str[i] = String.valueOf(numbers[i]);
        }
    //实现了Arrays接口的sort方法，将集合元素按照compare方法的规则进行排序
        Arrays.sort(str,new Comparator<String>(){
            @Override
            public int compare(String s1, String s2) {
                String c1 = s1 + s2;
                String c2 = s2 + s1;
                return c1.compareTo(c2);
            }
        });
        for(int i = 0; i < len; i++){
            sb.append(str[i]);
        }
        return sb.toString();
    }

5 第一个只出现一次的字符

题目描述

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
原题传送门：link.

思路

• 建立一个key为字符，val为次数（整数类型）的哈希map；
• 遍历字符串，将字符和次数插入到哈希map中；
• 规则为：定义time就是字符出现的次数，每出现一次加1；
• 再次从头到尾遍历字符串，配合hash表找出符合条件的字符。

代码（Java）

import java.util.HashMap;
public class Solution
{
    public int FirstNotRepeatingChar(String str)
    {
        //新建hashmap
        HashMap<Character,Integer> map=new HashMap<Character,Integer>();
        //遍历字符串
        for(int i=0;i<str.length();i++)
        {
            char c=str.charAt(i);
             //如果存在相同的key，覆盖
            if(map.containsKey(c))
            {
                int time=map.get(c);
                time++;
                map.put(c,time);
                 
            }
            //如果不存在相同的key,插入
            else
            {
                map.put(c,1);
            }
        }
        //再次从头遍历字符串，输出第一个为1的字符
       for(int i=0;i<str.length();i++)
       {
           char c=str.charAt(i);
          if(map.get(c)==1)
           return i;
       }
       return -1;
    }
}

package 字符串;
/**
 * 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置,
 * 如果没有则返回 -1（需要区分大小写）.
 *
 * 遍历一次字符串，使用一个数组来保存他们的状态
 *
 * */
public class 第一个只出现一次的字符 {

    public static void main(String[] args) {
        String str ="ssadcasdassdad";
        System.out.println(helper(str));
    }
    private  static char helper(String str){
        int [] count =new int ['z'-'A'];

        for(int i=0;i<str.length();i++){
            count[str.charAt(i)-'A']++;
        }
        for(int i=0;i<str.length();i++){
            if(count[str.charAt(i)-'A']==1){
                return str.charAt(i);
            }
        }
        return 0;
    }
}