public class Solution {
    public boolean Find(int target, int [][] array) {

    	//先判断边界条件
    	if(array == null){
    		return false;
    	}
    	//进行for循环的二维数组遍历
    	for(int i = 0;i < array.length;i++){
    		for(int j = 0;j < array[i].length;j++){

    			if(array[i][j] == target){

    				return true;
    			}
    		}
    	}
    	//找不到返回false
    	return false;
        
    }
}

2、替换空格

2.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：1054858

本题知识点：字符串

2.2 题目描述

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

2.3 代码段

public class Solution {
    public String replaceSpace(StringBuffer str) {
        //直接字符串替换方法即可
        String s = new String(str);
        String replace = s.replace(" ", "%20");
        return replace;
    }
}

3、从尾到头打印链表

3.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：942090

本题知识点：链表

3.2 题目描述

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

3.3 代码段

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

        //判断边界
        if(listNode == null){
            return new ArrayList<Integer>();
        }

        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        //while循环判断链表是否为空，不断的增加到list中
        while (listNode != null){
            list1.add(listNode.val);
            listNode = listNode.next ;
        }
//        思考栈的存储形式，然后反向遍历加入到新的list2中
        for (int i = list1.size();i >=0 ;i--){

            list2.add(list1.get(i));

        }
        return (ArrayList<Integer>) list2;

    }
}

3.4 思路解析

首先题目中告诉了ListNode的链表，所以这里我们首先在方法中判断边界条件

其次定义两个list21和list2来分别加入最开始的listNode.val和最后反向的list2即可。

4、重建二叉树

4.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：691830

本题知识点：树

4.2 题目描述

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

4.3 代码段

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.HashMap;
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;
    }
}

4.4 思路解析

在这里首先是题目给出了二叉树的中序和先序遍历，一般我们创建二叉树都是先序遍历+递归进行创建的，反正记住这个套路就差不多了。这里是通过在题目的要求下重载一个构建二叉树的方法，进入首先还是进行边界判断。

然后我们根据先序遍历创建二叉树的话就是先遍历到根节点，这时候再递归的分别构造左子树和右边子树。

Tips:前序遍历的第一个结果为根节点，通过查找可确定中序遍历中根节点的位置，则可确定左子树和右子树中序遍历下的结果。确定左子树和右子树节点数量，则可确定左子树和右子树前序遍历下的结果。得到左右子树中序和前序遍历结果，则可递归的构造出二叉树。

5、用两个栈实现队列

5.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：453710

本题知识点：队列栈

5.2 题目描述

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

5.3 代码段

package com.yuanfeng.test;

/**
 * @ClassName Solution
 * @Description T0D0
 * @Author yuanfeng
 * @Date 2019/7/23 23:02
 * @Version 1.0
 **/
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

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

    public int pop() {
        //弹出第一个栈中的数
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        int first = stack2.pop();
        //一个栈后面再弹出来
        while(!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
        return first;
    }
}

5.4 思路分析

首先题目告诉我们需要使用一个已经不再使用的Stack类来进行，这个类中本身具有push()、pop()、peek()、isEmpty()等方法，所以我们可以利用起来。

先使用stack1进行入栈操作，后面在出栈的时候我们需要循环的加入的stack2中，这个时候顺序又正了，那么弹出栈顶元素一个，接着把剩余的stack2中元素归为重新加到stack1中这个时候顺序又反了，重复该操作，所以每次弹出的都是先插入的那个元素，先进先出嘛。

6、旋转数组的最小数字

6.1 知识点和限制条件

时间限制：3秒空间限制：32768K 热度指数：635692

本题知识点：查找数组

6.2 题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

6.3 代码段

package com.yuanfeng.test;

/**
 * @ClassName Solution
 * @Description T0D0
 * @Author yuanfeng
 * @Date 2019/7/23 23:02
 * @Version 1.0
 **/
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {

        if(array == null){
            return 0;
        }else{
            //选择排序，由小到大
            for(int i = 0;i<array.length-1;i++){
                for(int j = i+1;j<array.length;j++){
                    if(array[i] > array[j]){
                        int temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                    }
                }
            }
        }
        //直接返回第一个
        return array[0];

    }
}

6.4 思路解析

题目本身告诉我们是传入的一个已经是旋转数组了，所以我们只需要把这个数组排序取出最小值即可，所以别被坑了，哈哈哈，冒泡、选择、快速、归并、基数、堆随你选！

7、斐波那契数列

7.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：580435

本题知识点：递归

7.2 题目描述

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

n<=39

7.3 代码段

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

7.4 思路解析

斐波那契数列本身是某一项等于前面两项之和的，所以可以得到递推方程F(n) = F(n-1)+F(n-2);

8、跳台阶

8.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：443486

本题知识点：递归

8.2 题目描述

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

8.3 代码段

public class Solution {
    public int JumpFloor(int target) {
        if(target <= 2){
            return target;
        }

        return JumpFloor(target-1)+JumpFloor(target-2);
    }
}

8.4 思路解析

比较倾向于找规律的解法，f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5，可以总结出f(n) = f(n-1) + f(n-2)的规律，但是为什么会出现这样的规律呢？假设现在6个台阶，我们可以从第5跳一步到6，这样的话有多少种方案跳到5就有多少种方案跳到6，另外我们也可以从4跳两步跳到6，跳到4有多少种方案的话，就有多少种方案跳到6，其他的不能从3跳到6什么的啦，所以最后就是f(6) = f(5) + f(4)；这样子也很好理解变态跳台阶的问题了。

9、变态跳台阶

9.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：357257

本题知识点：贪心

9.2 题目描述

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

9.3 代码段

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

9.4 思路分析

因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
因为f(n-1)=f(n-2)+f(n-3)+...+f(1)

所以f(n)=2*f(n-1)

10、矩形覆盖

10.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：326218

本题知识点：递归

10.2 题目描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

10.3 代码段

public class Solution {
    public int RectCover(int target) {
        if(target==1){
            return 1;
        }
        else if(target == 0){
            return 0;
        }
        else if(target==2){
            return 2;
        }else{
            return RectCover(target-1)+RectCover(target-2);
        }
    }
}

10.4 思路解析

f(1) = 1;

f(2) = 2;

当n>2时，画图可知，第一块小矩形可横放和竖放。横放后剩余的长度为n-2，竖放后剩余的长度为n-1。

所以：f(n) = f(n-1) + f(n-2); (n > 2)

11、二进制中1的个数

11.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：440050

本题知识点：进制转化补码反码原码

11.2 题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

11.3 代码段

package com.yuanfeng.test;

/**
 * @ClassName Solution
 * @Description T0D0
 * @Author yuanfeng
 * @Date 2019/7/26 10:32
 * @Version 1.0
 **/
public class Solution {

    public int NumberOf1(int n) {

        //存储1的个数
        int count = 0;
        //Java封装好的方法直接转为二进制的数组
        char[] arr = Integer.toBinaryString(n).toCharArray();
        for(int i = 0;i < arr.length;i++){
            if(arr[i] == '1'){
                count++;
            }
        }
        return count;
    }
}

11.4 思路解析

本题目求的是二进制，由于Java的Integer提供了一个tobinary()的方法，所以不管正数负数都是可以求解出来的！不用被题目中的负数用补码表示所干扰！

12、数值的整数次方

12.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：455300

本题知识点：数学

12.2 题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

12.3 代码段

package com.yuanfeng.test;

import javax.swing.text.Caret;

/**
 * @ClassName Solution
 * @Description T0D0
 * @Author yuanfeng
 * @Date 2019/7/26 10:32
 * @Version 1.0
 **/
public class Solution {

    public double getResult(double base, int exponent){
        if(exponent < 1){
            exponent = -exponent;
        }
        double result = 1.0;
        for (int i = 1; i <= exponent; i++) {

            result = base * result;

    }
        return result;
 }
    public double Power(double base, int exponent) {

        //exponent == 0
        if (exponent == 0) {
            return 1;
        }
        //exponent>=1的时候
        else if (exponent >= 1) {

            return getResult(base, exponent);

        } else if (exponent < 1) {
            return 1 / getResult(base, exponent);
        }
        return 0d;
    }
}

12.4 思路分析

该题我们首先要考虑的问题就是通过while循环或者是for循环我们可以求到一个数的次方。其次就是传入的exponent的边界分析了，要么大于0，要么大于等于1，要么小于1。小于1的时候我们需要知道的就是结果应该是大于0的倒数！

13、调整数组顺序使得奇数位于偶数的前面

13.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：529380

本题知识点：数组

13.2 题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

13.3 代码段

 //类似于冒泡排序的思想，前边是偶数后边是奇数就交换
    public void reOrderArray(int [] array) {
        for(int i= 0;i<array.length-1;i++){
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]%2 == 0 && array[j+1]%2 == 1){
                    int t = array[j];
                    array[j]=array[j+1];
                    array[j+1]=t;
                }
            }
        }
    }

14、链表中倒数第k个结点

14.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：737403

本题知识点：链表

14.2 题目描述

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

14.3 代码段

package com.yuanfeng.test;

import javax.swing.text.Caret;

/**
 * @ClassName Solution
 * @Description T0D0
 * @Author yuanfeng
 * @Date 2019/7/26 10:32
 * @Version 1.0
 **/

 class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {

        ListNode listNode = head;

        //记录总的结点个数
        int count = 1;
        //边界值判断
        if(head == null){
            return null;
        }
        //统计总的结点数
        while (head.next != null){
            head = head.next;
            count++;
        }
        //输入的k小于总的结点个数
        if(k <= count) {
            //t就是代表的前面遍历到第t个的时候就是倒数的第k个
            int t = count - k;
            for (int i = 1; i <= t; i++) {
                listNode = listNode.next;
            }
        }
        //输入的k大于结点个数，返回空
        else
            return null;
        return listNode;

    }
}

14.4 思路解析

1、我们先判断结点总共有多少个，使用count来计数

2、判断是否输入的k小于本身结点的长度

3、最重要就是明白我们平常说的一个串数字1、2、3、4、5，比如倒数第2个数，那么是4，它是正数第4个数。一共5个数，所以5-2=3，所以链表listNode = listNode.next就是代表的2,3,4,移动3次就找到了4这个数，即为倒数第k个数。

15、反转链表

15.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：536724

本题知识点：链表

15.2 题目描述

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

15.3 代码段

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode pre = null;
        ListNode next = null;
        //当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点
        //需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
        //即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
        //所以需要用到pre和next两个节点
        //1->2->3->4->5
        //1<-2<-3 4->5
        while(head!=null){
            //做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
            //如此就可以做到反转链表的效果
            //先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
            next = head.next;
            //保存完next，就可以让head从指向next变成指向pre了，代码如下
            head.next = pre;
            //head指向pre后，就继续依次反转下一个节点
            //让pre，head，next依次向后移动一个节点，继续下一次的指针反转
            pre = head;
            head = next;
        }
        //如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
        //直接输出pre就是我们想要得到的反转后的链表
        return pre;
    }
}

注解比较详细就不写思路解析了

16、合并两个排序的链表

16.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：516806

本题知识点：链表

16.2 题目描述

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

16.3 代码段

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //该list3是作为最后返回的递增的list3
        ListNode list3 = null;
        if(list1 == null){
            return list2;
        }
        else if(list2 == null){
            return list1;
        }
            if(list1.val < list2.val){
                //如果list1是小的,递归的求出最小
                list3 = list1;
                list3.next = Merge(list1.next,list2);
            }else{

                list3 = list2;
                list3.next =  Merge(list1,list2.next);
            }
        return list3;
        
    }
}

16.4 思路解析

想要解决这个问题需要有算法和数据结构的知识，其中必须运用链表和算法中的递归思想和归并思想。

先判断哪个串小一些就继续在这个串中进行判断。最后把这个串返回。

17、树的子结构

17.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：503303

本题知识点：树

17.2 题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

17.3 代码段

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

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

    }

}
*/
//假设树A的根节点ra和树B的根节点rb值相同，那么接下来就以这两个节点开始依次比较ra.left和rb.left、ra.right和rb.right，
//过程中只要有一个不相同则返回；继续比较ra.left和rb是否相同、ra.right和rb是否相同，
//就这样依次进行下去，时间复杂度则为O(树A的节点数)*O(树B的节点数)
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        //判断两棵树是否为空
        if(root1==null||root2==null){
            return false;
        }
        return isSubtree(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
    }
    
    public boolean isSubtree(TreeNode root1,TreeNode root2){
        //如果第二个节点为空 true
        if(root2==null){
            return true;
        }
         //如果第一个节点为空 false
        if(root1==null){
            return false;
        }
        //如果不同
        if(root1.val==root2.val){
            //继续递归
            return isSubtree(root1.left,root2.left)&&isSubtree(root1.right,root2.right);
        }
        return false;
    }
}

17.4 思路解析

如何判断一个二叉树是否是另一个的子结构？
     比如：

        2
      /   \
     9    8
    / \    /
   2 3 5
/
6

   有个子结构是
   9
/ \
2 3

分析：

有关二叉树的算法问题，一般都可以通过递归来解决。那么写成一个正确的递归程序，首先一定要分析正确递归结束的条件。

拿这道题来讲，什么时候递归结束。

<1>第二个二叉树root2为空时，说明root2是第一棵二叉树的root1的子结构，返回true。

<2>当root1为空时，此时root2还没为空，说明root2不是root1的子结构，返回false。

<3>递归下面有两种思路：

    方法一：先在root1中找结点值与root2的值相等的结点，如果找到就判断root2是不是这个结点开头的子结构。所以，首先IsSubTree()判断。

    方法二：就是直接判断，相同就递归判断root2左右子树是不是也是相应的子结构。如果值不相同，就分别递归到root1的左右子树寻找。尤其要注意最后两句递归的逻辑判断。

18、二叉树的镜像

18.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：292134

本题知识点：树

18.2 题目描述

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

18.3 代码段

public class Solution {
    public void Mirror(TreeNode root) {
       TreeNode temp;
        //如果树的引用不为空的话
        if(root!=null)
        {
         //交换左右子树
        temp=root.left;
        root.left=root.right;
        root.right=temp;
        if(root.left!=null)
            Mirror(root.left);
        if(root.right!=null)
            Mirror(root.right);
        }
    }
}

18.4 思路解析

此题直观的解法是使用递归的方式，将根节点的每个左右子节点进行swap。

①代码的鲁棒性（极限条件的考虑，空树条件）

②每次弹出栈顶元素，并且判断该元素的左右孩子结点，做swap操作

③结束条件为栈空间为空

19、顺时针打印矩阵

19.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：533255

本题知识点：数组

19.2 题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

19.3 代码段

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
     int length = matrix.length;   //行长度：矩阵的长
        int width = matrix[0].length; //列长度：矩阵的宽
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        if(matrix == null || length==0 || width==0) return null;
        if(length==1){
            for(int a1 = 0;a1<width;a1++){
                arrayList.add(matrix[0][a1]);
            }
            return arrayList;
        }
        if(width==1){
            for(int a2 = 0;a2<length;a2++){
                arrayList.add(matrix[a2][0]);
            }
            return arrayList;
        }

        //一次循环是一圈
        for(int i =0;i<length-i;i++){
            int j=i;
            if(j<width-i) {
                //一圈的上边
                for (;j<width - i; j++) {
                    arrayList.add(matrix[i][j]);
                }
                //一圈的右边
                for (int k = i + 1; k < length - i; k++) {
                    arrayList.add(matrix[k][width - 1 - i]);
                }

                int f = length - 1 - i; //下边所在的行数
                if (f != i) {
                    //一圈的下边
                    for (int m = width - 1 - i - 1; m >= i; m--) {
                        arrayList.add(matrix[f][m]);
                    }
                    //一圈的左边
                    for (int n = f - 1; n > i; n--) {
                        arrayList.add(matrix[n][i]);
                    }
                }
            }
        }
        return arrayList;
    }
}

19.4 思路解析

最主要的问题是要考虑边界值，例如上图，4既在第一圈的上边也在第一圈的右边，我们输出时，要求只输出一个4即可。
例如，当输入的矩形不是正方形，要考虑到其他特殊情况的判断：
{{1,2,3,4},{5,6,7,8},{9,10,11,12}}
{{1},{2},{3}}，长或宽有一项长度为1时，直接遍历输出即可。
{1,2},{3,4},{5,6},{7,8},{9,10}，这种情况下，length远比width大，外层根据length来判断的for循环可以进行下去，但是内层已经没有可以访问的元素了，这时候需要根据width进行判断。
其实好多这些特殊情况在第一次写的时候都没哟考虑到，在本地运行并测试不同的测试样例的时候，就发现了这些情况，然后在原本代码的基础上进行修改和调整。
希望以后能考虑的更加全面，而不是在出现问题后再进行调整。

转自：作者：夏臻Rock
链接：链接
来源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。

20、包含min函数的栈

20.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：314795

本题知识点：栈

20.2 题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

20.1 代码段

package com.yuanfeng.test;

/**
 * @ClassName Solution
 * @Description T0D0
 * @Author yuanfeng
 * @Date 2019/7/23 23:02
 * @Version 1.0
 **/
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

public class Solution {

    private Stack<Integer> stack = new Stack<>();

    public void push(int node) {

        stack.push(node);
    }

    public void pop() {
        stack.pop();
    }

    public int top() {

        return stack.peek();
    }

    public int min() {
        //先弹出一个顶部的值当作最小值
        int mid = stack.peek();
        //使用迭代器进行stack的迭代
        Iterator<Integer> iterator = stack.iterator();
        //while循环遍历
        while (iterator.hasNext()){
            Integer next = iterator.next();
            if(next < mid){
                mid = next;
            }
        }
        return mid;
    }
}

20.4 思路解析

这个相当于就是在栈这个结构中找到最小值，知道Stack中的几个方法就足够了。如果你使用while循环遍历的时候控制不好是不能满足题目的限制运行时间复杂度的条件的。所以还是使用Iterator迭代器遍历比较好一点。

21、栈的压入和弹出

21.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：371997

本题知识点：栈

21.2 题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

21.3 代码段

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        //边界值判断是否为空
      if(pushA == null || popA == null || pushA.length == 0 || popA.length == 0 || pushA.length != popA.length)
          return false;
        Stack<Integer> st = new Stack<Integer>();
        int i = 0;
        int j = 0;
        st.push(pushA[i++]);
        while(j <= popA.length-1){
            //这里的st.peek()用的巧妙，因为只是弹出栈顶元素，但是该元素还是存在于栈中，和pop()有区别
            while(popA[j] != st.peek()){
                //i等于pushA的长度
                if(i == pushA.length) return false;
                //将psuhA中元素不断压入st中进行判断,i++
                st.push(pushA[i++]);
            }
            j++;
            //这里弹出是关键
            st.pop();
        }
        return true;
    }
}

21.4 思路分析

　解决这个问题很直观的想法就是建立一个辅助栈，把输入的第一个序列中的数字依次压入该辅助栈Stack，并按照第二个序列的顺序依次从该栈

中弹出数字。以弹出序列4、5、3、2、1为例分析压栈和弹出的过程。第一个希望被弹出的数字是4,因此4需要先压入到辅助栈里面。压入栈的

顺序由压栈序***定了，也就是在把4压入进栈之前，数字1、2、3都需要先压入到栈里面。此时栈里包含4个数字，分别是1、2、3、4,其中4位

于栈顶。把4 弹出栈后，剩下的三个数字是1、2和3。接下来希望被弹出的数字是5，由于它不是栈顶数字，因此我们接着在第一个序列中把4以

后数字压入辅助栈中，直到压入了数字5。这个时候5位于栈顶，就可以被弹出来了。接下来希望被弹出的三个数字依次是3、2和1。由于每次操

作前它们都位于栈顶，因此直接弹出即可。好好理解一下！

22、从上往下打印二叉树

22.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：388426

本题知识点：队列树

22.2 题目描述

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

22.3 代码段

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 {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        //保存返回的Integer
         ArrayList<Integer> list1 = new ArrayList<>();
        //保存TreeNode
        ArrayList<TreeNode> list2 = new ArrayList<>();
        if (root == null) {
            return list1;
        }
        //将root增加到里面
        list2.add(root);
        while(list2.size() != 0) {
            //得到根节点.最后删除了下一个子树也会的到对应的根节点
            TreeNode temp = list2.remove(0);
            //判断左子树
            if (temp.left != null){
                list2.add(temp.left);
            }
               //判断右子树
            if (temp.right != null) {
                list2.add(temp.right);
            }
            list1.add(temp.val);
        }
        return list1;
    }
}

22.4 思路解析

相当于说这个题目的意思就是二叉树从上到下从左到右层次遍历，所以我们要知道层次遍历的规则，首先是先得到根节点的值，其次是左子树根节点、右子树的根节点，一层层递归下去。

23、二叉搜索树的后序遍历序列

23.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：449402

本题知识点：栈树

23.2 题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

23.3 代码段

public class Solution {
//思路：找住二叉查找树的特点：左子树<根<=右子树  使用分治思想
    public boolean VerifySquenceOfBST(int [] sequence) {
        //边界值判断
        if(sequence.length == 0){
            return false;
        }
        return judge(sequence,0,sequence.length-1);
    }
     
   public boolean judge(int [] a,int start,int last){
        if(start>=last){
            return true;
        }
        //后序遍历，最后的一个位置元素即是根节点
        int i = last;
        //找到的i即是分割左子树与右子树的位置。i-1的位置到start为左子树，i到last-1位置为右子树
        //因为二叉树的左子树的所有元素小于根节点的值，右子树的所有元素的值大于根节点的值
        while(i>start && a[i-1]>a[last]){
            --i;
        }
        //左子树的元素都需要小于根节点
        for(int j=i-1;j>=start;--j){
            if(a[j]>a[last]){
                return false;
            }
        }
        //在递归判断左子树与右子树是否满足后序遍历
        return (judge(a,start,i-1)) && (judge(a,i,last-1));
    }
}

23.4 思路解析

递归思路：

确定跟节点的值，即后序遍历序列最后的值；

遍历序列，记录第一个比根节点大的值的位置，继续遍历，如果之后序列的所有值

存在比根节点小的值，直接返回false，如果不存在则判断其子树是否为二叉搜索树。

第一个比根节点大的值之前的子序列为左子树，之后（包括该值）为右子树，根据递归思想，重复步骤1，2.直到子树根节点的左右子节点均为空。

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

24.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：402558

本题知识点：树

24.2 题目描述

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

24.3 代码段

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 {
    //定义一个list返回最后的结果
    private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
   //定义一个list把当前遍历到的结点加入到其中
    private ArrayList<Integer> list = new ArrayList<Integer>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        //边界判断
        if(root == null) return listAll;
        //加入当前结点
        list.add(root.val);
        //遍历一个就减去这个数
        target -= root.val;
        //最后遍历完的时候
        if(target == 0 && root.left == null && root.right == null)
            listAll.add(new ArrayList<Integer>(list));
        //递归左子树
        FindPath(root.left, target);
        //递归右子树
        FindPath(root.right, target);
        list.remove(list.size()-1);
        return listAll;
    }
}

24.4 思路解析

这个题就是判断的这个target是否是所有经历的路径上面结点的值之和，所以我们首先遍历到根节点，然后依次减去遍历到的结点值，就是target剩下的值，最后遍历完了target也是只剩下为0，这个路径也就是最终的路径了，需要不断的递归左右子树。

25、复杂链表的复制

25.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：413283

本题知识点：链表

25.2 题目描述

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

25.3 代码段

/*
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){
    if (pHead == null) {
            return null;
        }
        //复制并且插入
        RandomListNode p = pHead;
        while (p != null) {
            RandomListNode tmp = new RandomListNode(p.label);
            tmp.next = p.next;
            p.next = tmp;

            p = tmp.next;
        }
        //复制random指针
        p = pHead;
        while (p != null) {
            if (p.random != null) {
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        //拆分链表

        RandomListNode head = pHead.next;
        RandomListNode q = head;
        p = pHead;
        //这个部分需要注意一下
        while (q.next != null) {
            p.next = q.next;
            p = p.next;

            q.next = p.next;
            q = q.next;
        }
        p.next = null;  //最后将原来链表的尾部设置为null
        return head;
    }
}

25.4 结果分析

26、二叉搜索树与双向链表

26.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：289219

本题知识点：链表树

26.2 题目描述

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

26.3 代码段

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

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

    }

}
*/
public class Solution
{
//1、将左子树构成双链表，并返回该链表的头节点(左子树最左边的节点)
//2、定位到左链表的最后一个节点(左子树最右边的节点)
//3、如果左子树链表不为空，则将当前root追加到左子树链表后
//4、将右子树构造成双向链表，并返回链表头结点(右子树最左边的节点)
//5、如果右子树链表不为空，将右子树链表追加到当前root后
//6，根据左子树链表是否为空返回的整体双向链表的头节点
 
//Convert函数把一个二叉搜索树变成一个有序的双向链表，返回双向链表的头结点，参数root为二叉搜索树的根节点
public TreeNode Convert(TreeNode root){
    if(root==null){//假如根节点为空，返回空
        return null;
    }
    if(root.left==null&&root.right==null){//假如只有一个根节点，则返回根节点
        return root;
    }
    //1、将左子树构造成双链表，并返回该链表头结点left
    TreeNode left=Convert(root.left);
 
    //2、定位到左子树链表的最后一个节点（左子树最右边的节点）
    TreeNode p=left;//创建一个临时节点P,用来遍历找到左链表的最后一个节点(左子树最右边的节点)，p初始化指向做左子树的根节点，
    while(p!=null&&p.right!=null){
        p=p.right;//最终p为左子树最右边的节点
    }
    //3、如果左子树链表不为空，将当前root追加到左子树链表后
    if(left!=null){//左子树链表不为空
        p.right=root;//左子树链表的最后一个节点p（左子树最右边节点）的右指针指向当前root节点
        root.left=p;//当前root节点的左指针指向左子树链表的最后一个节点p（左子树最右边节点）
    }
    //4、将右子树构造成双链表，并返回该链表的头结点right
    TreeNode right=Convert(root.right);
 
    //5、如果右子树链表不为空，将右子树链表追加到当前root后
    if(right!=null){//右子树链表不为空
        right.left=root;//右子树链表的头结点right的左指针指向当前root
        root.right=right;//当前root的右指针指向右子树链表的头结点right
    }
    return left!=null?left:root;//根据左子树链表是否为空返回整个双向链表的头指针。
}
}

26.4 结果解析

该题最重要就是明白二叉搜索树的左子树是<根节点<右子树的，所以最后求出来的两边子树的双向链表必须按照顺序进行连接起来。因为要求是一个排序的双向链表。

27、字符串的排列（重要）

27.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：440552

本题知识点：字符串动态规划递归

27.2 题目描述

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

27.3 输入描述

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

27.4 代码段

import java.util.*;
 
public class Solution {
     
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<String>() ;
        if(str==null || str.length()==0) { return result ; }
         //转化为字符数组
        char[] chars = str.toCharArray() ;
        //TreeSet排序
        TreeSet<String> temp = new TreeSet<>() ;
        Permutation(chars, 0, temp);
        result.addAll(temp) ;
        return result ;
    }
 
    public void Permutation(char[] chars, int begin, TreeSet<String> result) {
        if(chars==null || chars.length==0 || begin<0 || begin>chars.length-1) { return ; }
 
        if(begin == chars.length-1) {
            result.add(String.valueOf(chars)) ;
        }else {
            for(int i=begin ; i<=chars.length-1 ; i++) {
                swap(chars, begin, i) ;
 
                Permutation(chars, begin+1, result);
 
                swap(chars, begin, i) ;
            }
        }
    }
 
    public void swap(char[] x, int a, int b) {
        char t = x[a];
        x[a] = x[b];
        x[b] = t;
    }
     
}

27.5 结果分析

我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a，求后面两个字符bc的排列。当两个字符bc的排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍然是和原先处在第一位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处在第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列。

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

28.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：379292

本题知识点：数组

28.2 题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

28.3 代码段

public class Solution {
    public static int MoreThanHalfNum_Solution(int[] array) {

        //边界判断
        if (array == null || array.length == 0) {
            return 0;
        }
        int half = array.length / 2;
        int count = 0;
        int flag = 0;
        for (int i = 0; i < array.length; i++) {

            for (int j = 0; j < array.length; j++) {
                //相等时
                if (array[i] == array[j]) {
                    count++;
                }
                //如果得到的次数是超过一般长度的
                //记录下标索引并跳出循环
                if (count >half) {
                    flag = i;
                    break;
                //当判断到了j等于长度的时候依旧不满足次数大于一半长度
                }else if(j ==array.length-1 && count <= half){
                    
                    count = 0;
                }

            }
            //满足条件直接跳出
            if (count > half) {
                break;
            }
        }
        return count > half?array[flag]:0;

    }

    public static void main(String[] args) {
        int[] array = new int[]{1,2,3,2,4,2,5,2,3};
        System.out.println(MoreThanHalfNum_Solution(array));
    }
}

28.4 结果解析

这个题目我这边暂时是使用的两个for循环进行判断的，定义flag为得到最后的次数大于一半的那个索引，最重要的是需要知道最后第一轮比较完了的时候，还是没有超过一半长度的时候，需要将count置为0，防止重复计算了次数。

29、最小的k个数

29.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：307857

本题知识点：穷举

29.2 题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

29.3 代码段


import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName Solution
 * @Description T0D0
 * @Author yuanfeng
 * @Date 2019/7/23 23:02
 * @Version 1.0
 **/

public class Solution {
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

            List<Integer> list = new ArrayList<>();
                if(input == null || input.length == 0 || k > input.length){
                return  (ArrayList<Integer>) list;
                }
            for(int i = 0;i < input.length-1;i++){

                for(int j = 0;j < input.length-i-1;j++){

                    if(input[j] > input[j+1]){
                        int temp = input[j];
                        input[j] = input[j+1];
                        input[j+1] = temp;
                    }
                }

            }
            //得到最小的k个数加入集合中
            for (int l = 0;l <=k-1;l++){
                list.add(input[l]);
            }

            return  (ArrayList<Integer>) list;
    }


    public static void main(String[] args) {
        int[] input = new int[]{4,5,1,6,2,7,3,8};
        Solution solution = new Solution();
        ArrayList<Integer> list = solution.GetLeastNumbers_Solution(input, 4);
        System.out.println(list);
    }
}

29.4 结果解析

直接使用冒牌排序由小大到的排序即可。

30、连续子数组的最大和

30.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：268889

本题知识点：数组

30.2 题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

30.3 代码段

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class Solution {
   public int FindGreatestSumOfSubArray(int[] array)
    {
    	if(array == null || array.length == 0)
    	{
    		return 0;
    	}
    	int sumMax = array[0];
    	int currentMax = array[0];//保存子数组相加之和
    	//从头开始遍历相加数组中的元素
    	for (int i = 1; i < array.length; i++)
		{
    		//若是相加之和一旦小于零，子数组从新开始，否则相加
			if(currentMax < 0)
			{
				currentMax = array[i];
			}
			else
			{
				currentMax = currentMax + array[i];
			}
			//sumMax保存最大的子数组的和
			if(currentMax > sumMax)
			{
				sumMax = currentMax;
			}
		}
    	return sumMax;
    }
}

31、整数中1出现的次数

31.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：207626

本题知识点：查找数学

31.2 题目描述

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

31.3 代码段

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        //定义计数器来计数1出现的次数
        int count = 0;
        int arr[] = new int[5];
       //首先判断条件初始的条件是否满足
        if(n <= 1 && n >0){
            return 1;
        }
        //分别看是几位数
        //一位数
        for(int i = 1;i<=n;i++){
            arr[0] = i%10;
            arr[1] = i/10%10;
            arr[2] = i/100%10;
            arr[3] = i/1000%10;
            arr[4] = i/10000%10;
           for(int j = 0;j<arr.length;j++){
               if(arr[j] == 1){
                   count++;
               }
           } 
        }
       return count; 
    }
}

32、把数组排成最小的数

32.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：276561

本题知识点：数组

32.2 题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323

32.3 代码段

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
 
public class Solution {
    public String PrintMinNumber(int [] numbers) {
        StringBuilder sb = new StringBuilder();
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i = 0; i <numbers.length; i++) {
            list.add(numbers[i]);
        }
 
        //集合工具排序
        Collections.sort(list, new Comparator<Integer>() {
            public int compare(Integer str1, Integer str2) {
                //两个方向进行比较大小
                String s1 = str1 + "" + str2;
                String s2 = str2 + "" + str1;
                return s1.compareTo(s2);
            }
        });
 
        for(int j : list) {
            sb.append(j);
        }
 
        return sb.toString();
    }
}

33、丑数

33.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：307857

本题知识点：穷举

33.2 题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

33.3 代码段

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        
           
   if(index<=0)
       return 0;
       
        //定义result数组存最后的丑数
        int[] result = new int[index];
        int count = 0;
        int i2 = 0;
        int i3 = 0;
        int i5 = 0;
        
        //因为1是第一个丑数嘛
        result[0] = 1;
        int tmp = 0;
        while (count < index-1) {
            //得到最小的丑数
            tmp = min(result[i2] * 2, min(result[i3] * 3, result[i5] * 5));
            //三条if防止值是一样的，不能改成else的
            if(tmp==result[i2] * 2)
                i2++;
            if(tmp==result[i3] * 3)
                i3++;
            if(tmp==result[i5]*5)
                i5++;
            result[++count]=tmp;
        }
        return result[index - 1];
    }
 
    private int min(int a, int b) {
        return (a > b) ? b : a;
    }
        
    }

33.4 结果分析

丑数规律是前面的数*2||*3||*5都会得到一个丑数，为了避免重复我们就想了一个办法，取当前最小的丑数然后加入丑数数组。

34、第一个只出现一次的字符

34.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：297013

本题知识点：字符串

34.2 题目描述

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

34.3 代码段

package com.yuanfeng.test;

public class Solution {


    public int FirstNotRepeatingChar(String str) {
        char[] a = str.toCharArray();
        for (int i = 0; i < a.length; i++) {
            //我们只要判断在这个字符之前的字符和之后字符是否存在就可以判断字符是否唯一
            if (!str.substring(0, i).contains(a[i] + "") && !str.substring(i + 1).contains(a[i] + ""))
                return i;
        }
        return -1;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        int i = solution.FirstNotRepeatingChar("aabfdfhsjk");
        System.out.println(i);
    }

}

34.4 结果分析

求解该题目本身我们可以换一种角度去思考问题，要求的是某个字符第一个只出现一次的字符，那么我们可以考虑判断这个字符串中某个字符中前面的所有和后面的所有是否包含该字符，只要不包含的位置就是要求解的位置了！

35、数组中的逆序对

35.1 知识点和限制条件

时间限制：2秒空间限制：32768K 热度指数：372992

本题知识点：数组

35.2 题目描述

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

35.3 输入描述

题目保证输入的数组中没有的相同的数字
数据范围：

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2*10^5

35.4 输入示例

输入

复制
1,2,3,4,5,6,7,0
输出

复制
7

35.5 代码段


public class Solution {
    //统计逆序对的个数
    int cnt;
    public int InversePairs(int [] array) {
        if(array.length != 0){
            divide(array,0,array.length-1);
        }
        return cnt;
    }
 
    //归并排序的分治---分
    private void divide(int[] arr,int start,int end){
        //递归的终止条件
        if(start >= end)
            return;
        //计算中间值，注意溢出
        int mid = start + (end - start)/2;
 
        //递归分
        divide(arr,start,mid);
        divide(arr,mid+1,end);
 
        //治
        merge(arr,start,mid,end);
    }
 
    private void merge(int[] arr,int start,int mid,int end){
        int[] temp = new int[end-start+1];
 
        //存一下变量
        int i=start,j=mid+1,k=0;
        //下面就开始两两进行比较，若前面的数大于后面的数，就构成逆序对
        while(i<=mid && j<=end){
            //若前面小于后面，直接存进去，并且移动前面数所在的数组的指针即可
            if(arr[i] <= arr[j]){
                temp[k++] = arr[i++];
            }else{
                temp[k++] = arr[j++];
                //a[i]>a[j]了，那么这一次，从a[i]开始到a[mid]必定都是大于这个a[j]的，因为此时分治的两边已经是各自有序了
                cnt = (cnt+mid-i+1)%1000000007;
            }
        }
        //各自还有剩余的没比完，直接赋值即可
        while(i<=mid)
            temp[k++] = arr[i++];
        while(j<=end)
            temp[k++] = arr[j++];
        //覆盖原数组
        for (k = 0; k < temp.length; k++)
            arr[start + k] = temp[k];
    }
}

35.6 结果分析

本题其实对于熟悉归并排序的朋友来说再2熟悉不过了。。。。。（归并+分治法）

36、两个链表的第一个公共结点

36.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：245042

本题知识点：链表

36.2 题目描述

输入两个链表，找出它们的第一个公共结点。

36.3 代码段


public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
       if (pHead1 == null||pHead2 == null) {
            return null;
        }
        //求链表的长度
        int count1 = 0;
        ListNode p1 = pHead1;
        while (p1!=null){
            p1 = p1.next;
            count1++;
        }
        int count2 = 0;
        ListNode p2 = pHead2;
        while (p2!=null){
            p2 = p2.next;
            count2++;
        }
        
        //求链表长度之差
        int flag = count1 - count2;
        if (flag > 0){
            while (flag>0){
                pHead1 = pHead1.next;
                flag --;
            }
        while (pHead1!=pHead2){
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return pHead1;
    }
        if (flag <= 0){
            while (flag<0){
                pHead2 = pHead2.next;
                flag ++;
            }
            while (pHead1 != pHead2){
                pHead2 = pHead2.next;
                pHead1 = pHead1.next;
            }
            return pHead1;
        }
        return null;
    }
}

36.4 结果分析

首先需要明确一点，如果两个链表有公共节点，那么从第一个公共节点开始，直到链表结束，这段链表的长度N对两个链表来说长度是一致的，且公共链表必定是从距离两个链表尾向前N（公共部分的节点个数）个节点的位置的下一位置开始的。

37、数字在排序数组中出现的次数

37.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：276802

本题知识点：数组

37.2 题目描述

统计一个数字在排序数组中出现的次数。

37.3 代码段

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       
        
       int count = 0;
       
        if(array == null || array.length == 0){
            return 0;
        }
        for(int i = 0;i<array.length;i++ ){
            if(k == array[i]){
                count++;
            }
        }
        return count;
    }
}

38、二叉树的深度

38.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：180483

本题知识点：树

38.2 题目描述

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

38.3 代码段

public class Solution {
    public int TreeDepth(TreeNode root) {
        
        int depth = 0;
        if(root == null){
            return 0;
        }
        
        int leftLen=TreeDepth(root.left);
        int rightLen=TreeDepth(root.right);
        
        //比较过后还需要加上一个根节点
        return leftLen>rightLen?(leftLen+1):(rightLen+1);
    }
}

38.4 结果分析

求二叉树的深度，这个概念就不多说了，想要求解这个问题我觉得除了递归可能找不到其他更好更容易理解的方法了，首先我们直接对左子树和右子树进行递归，然后直接判断谁的深度更长即可，最后别忘了是还要加上一个根节点的长度的！

39、平衡二叉树

39.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：222622

本题知识点：树

39.2 题目描述

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

39.3 代码段

public class Solution {
      //后续遍历时，遍历到一个节点，其左右子树已经遍历  依次自底向上判断，每个节点只需要遍历一次
     
    private boolean isBalanced=true;
    public boolean IsBalanced_Solution(TreeNode root) {
        //得到树的深度
         getDepth(root);
         return isBalanced;
    }
      public int getDepth(TreeNode root){
        if(root==null)
            return 0;
          //左子树
        int left=getDepth(root.left);
          //右子树
        int right=getDepth(root.right);
         //高度差超过一了，不满足条件
        if(Math.abs(left-right)>1){
            isBalanced=false;
        }
           
          return right>left ?right+1:left+1;
}
}

39.4结果分析

平衡二叉树的概念：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

解决本题目的一个方向就是得到深度，比较左子树和右子树的长度之差，绝对值是否大于1。

40、数组中只出现一次的数字

40.1 知识点和限制条件


import java.util.ArrayList;
public class Solution {
        public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
            //使用list集合
                List<Integer>list=new ArrayList<Integer>();
                for(int i=0;i<array.length;i++)
                    {
                    //看集合是否包含来判断是否有重复数字
                        if(!list.contains(array[i]))
                            list.add(array[i]);
                        else//因为这里集合存的只有两个数
                            list.remove(new Integer(array[i]));
                    }
                if(list.size()>1)
                    {
                        num1[0]=list.get(0);
                        num2[0]=list.get(1);
                    }
        }
}

40.2 题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

40.3 代码段


import java.util.ArrayList;
public class Solution {
        public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
            //使用list集合
                List<Integer>list=new ArrayList<Integer>();
                for(int i=0;i<array.length;i++)
                    {
                    //看集合是否包含来判断是否有重复数字
                        if(!list.contains(array[i]))
                            list.add(array[i]);
                        else//因为这里集合存的只有两个数
                            list.remove(new Integer(array[i]));
                    }
                if(list.size()>1)
                    {
                        num1[0]=list.get(0);
                        num2[0]=list.get(1);
                    }
        }
}

40.4 结果分析

首先我们想要解决这个问题需要考虑到最后我们的结果只需要把找到的两个数字分别赋值给num1和num2即可，所以我们使用List中的contains来解决。

41、和为S的连续正数序列

41.1知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：263609

本题知识点：穷举

41.2 题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

41.3输出描述

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

41.4 代码段

import java.util.ArrayList;
 //双层循环，找出所有和为S的连续正数序列。
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
       ArrayList<ArrayList<Integer>> arrs = new ArrayList<ArrayList<Integer>>();
        for(int i=1; i<sum; i++){
            int s = 0;
            ArrayList<Integer> arr = new ArrayList<Integer>();
            for(int j=i; j<sum; j++){
                if(s < sum){
                    s += j;
                    arr.add(j);//加到序列集合中
                    if(s == sum){
                        arrs.add(arr);//加到总的大集合中
                        break;
                    }
                }else{
                    break;
                }
            }
        }
        return arrs;
    }
}

42、和为S的两个数字

42.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：242376

本题知识点：数学

42.2 题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

42.3 输出描述

对应每个测试案例，输出两个数，小的先输出。

42.4 代码段

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (array == null || array.length < 2) {
            return list;
        }
        int i=0；
        int j=array.length-1;
        
        //数组是递增排序的，后面肯定大于前面
        while(i<j){
            if(array[i]+array[j]==sum){
            list.add(array[i]);
            list.add(array[j]);
                return list;
           }else if(array[i]+array[j]>sum){//大于肯定是数过大，所以j--
                j--;
            }else{//小于的情况肯定是数不够大
                i++;
            }
             
        }
        return list;
    }
}

42.5 结果分析

直接使用最直观容易理解的蛮力暴力解法，首先我们可以在while循环中判断两个数之和相等于sum,大于小于sum相等的时候，说明这两个数是应该加入到list中，因为本身是递增的数组，所以首先加入的肯定是乘积最小的。同理可知其他两种情况！

46、左旋转字符串

46.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：227535

本题知识点：字符串

46.2 题目描述

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

46.3 代码段

public class Solution {
    public String LeftRotateString(String str,int n) {
        int length = str.length();
          if(str == null || length < n){
            return "";
        }
        String head = str.substring(0,n);
        String rear = str.substring(0+n);
        String resultStr = rear + head;
        return resultStr;


    }
}

46.4 结果分析

这个题目我们直接把要左边移动的几位取出来，右边的取出来，然后后面的放在前面，前面的放在后面连接起来即可！

47、翻转单词顺序列

47.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：364632

本题知识点：字符串

47.2 题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

47.3 代码段

public class Solution {
    public String ReverseSentence(String str) {
        if(str == null){ return null;}
         if(str.trim().equals("")){
            return str;
        }
        String string = str;
        //切割出来
        String[] strings = string.split(" ");
        //使用一个StringBuffer来进行连接
        StringBuilder sBuilder = new StringBuilder();
        for (int i = strings.length-1 ; i>=0;i--) {
            if(i == 0){
                sBuilder.append(strings[i]);
            }else {
                sBuilder.append(strings[i]);
                sBuilder.append(" ");
            }  
        }
     
        String string2 = sBuilder.toString();
        return string2;
    }
}

48、孩子们的游戏(圆圈中最后剩下的数)

48.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：211420

本题知识点：链表数学

48.2 题目描述

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

48.3 代码段

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        //约瑟夫环问题
        if(n==0||m==0)return -1;
        int s=0;
        for(int i=2;i<=n;i++)
        {
            s=(s+m)%i;
        }   
       return s ;
    }
}

48.4 结果分析

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 [1] 结果+1即为原问题的解。

49、求1+2+3+...n

49.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：196934

本题知识点：进制转化

49.2 题目描述

求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

49.3 代码段

public class Solution {

    public int Sum_Solution(int n) {

        int sum = 0;
        return (1+n)*n/2;
    }
}
不说了，高中等差数列求和公式n*(n+1)/2;

50、不用加减乘除做加法

50.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：133682

本题知识点：进制转化

50.2 题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

50.3 代码段

import java.math.BigInteger;
public class Solution {
    public static int Add(int num1,int num2) {
        BigInteger bi1=new BigInteger(String.valueOf(num1));
        BigInteger bi2=new BigInteger(String.valueOf(num2));
        return bi1.add(bi2).intValue();

    }

    public static void main(String[] args) {
        System.out.println(Add(22,4));
    }
}

直接使用math包中的BigInteger中的add方法实现加法运算！

51、把字符串转换成整数

51.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：221102

本题知识点：字符串进制转化

51.2 题目描述

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0。

51.3 输入描述

输入一个字符串,包括数字字母符号,可以为空

51.4 输出描述

如果是合法的数值表达则返回该数字，否则返回0

51.5 示例

输入: +2147483647
1a33

输出 : 2147483647
0

51.6 代码段

public class Solution {
    public int StrToInt(String str) {
         if (str.equals("") || str.length() == 0)
            return 0;
        //转换成字符数组
        char[] a = str.toCharArray();
        //符号标记
        int flag = 0;
        //如果第一个字符为负数
        if (a[0] == '-')
            flag = 1;
        int sum = 0;
        for (int i = flag; i < a.length; i++)
        {
            if (a[i] == '+')
                continue;
            if (a[i] < 48 || a[i] > 57)
                return 0;
            //字符变为整数减去48
            sum = sum * 10 + a[i] - 48;
        }
        //判断是否带符号整数返回sum,负数返回sum*(-1)
        return flag == 0 ? sum : sum * -1;
    }
        
}

52、数组中重复的数字

52.1 知识点和限制条件

时间限制：1秒空间限制：32768K 热度指数：280288

本题知识点：数组

52.2 题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

52.3 代码段

import java.util.Arrays;
public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null || length == 0){
            return false;
        }
        //排序
        Arrays.sort(numbers);
        for(int i=0;i<length-1;i++){
            //判断相邻元素是否相等
            if(numbers[i] == numbers[i+1]){
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }
}

52.4 结果分析

将输入数组排序，再判断相邻位置是否存在相同数字，如果存在，对 duplication 赋值返回，否则继续比较。

牛客网《剑指offer》题解--Java版

1、二维数组中的查找

1.1 知识点和限制条件

1.2 题目描述

1.3 代码段

2、替换空格

2.1 知识点和限制条件

2.2 题目描述

2.3 代码段

3、从尾到头打印链表

3.1 知识点和限制条件

3.2 题目描述

3.3 代码段

3.4 思路解析

4、重建二叉树

4.1 知识点和限制条件

4.2 题目描述

4.3 代码段

4.4 思路解析

5、用两个栈实现队列

5.1 知识点和限制条件

5.2 题目描述

5.3 代码段

5.4 思路分析

6、旋转数组的最小数字

6.1 知识点和限制条件

6.2 题目描述

6.3 代码段

6.4 思路解析

7、斐波那契数列

7.1 知识点和限制条件

7.2 题目描述

7.3 代码段

7.4 思路解析

8、跳台阶

8.1 知识点和限制条件

8.2 题目描述

8.3 代码段

8.4 思路解析

9、 变态跳台阶

9.1 知识点和限制条件

9.2 题目描述

9.3 代码段

9.4 思路分析

10、矩形覆盖

10.1 知识点和限制条件

10.2 题目描述

10.3 代码段

10.4 思路解析

11、二进制中1的个数

11.1 知识点和限制条件

11.2 题目描述

11.3 代码段

11.4 思路解析

12、 数值的整数次方

12.1 知识点和限制条件

12.2 题目描述

12.3 代码段

12.4 思路分析

13、 调整数组顺序使得奇数位于偶数的前面

13.1 知识点和限制条件

13.2 题目描述

13.3 代码段

14、 链表中倒数第k个结点

14.1 知识点和限制条件

14.2 题目描述

14.3 代码段

14.4 思路解析

15、反转链表

15.1 知识点和限制条件

15.2 题目描述

15.3 代码段

16、合并两个排序的链表

16.1 知识点和限制条件

16.2 题目描述

16.3 代码段

16.4 思路解析

17、树的子结构

17.1 知识点和限制条件

17.2 题目描述

9、变态跳台阶

12、数值的整数次方

13、调整数组顺序使得奇数位于偶数的前面

14、链表中倒数第k个结点

22、从上往下打印二叉树

23、二叉搜索树的后序遍历序列

25、复杂链表的复制

27、字符串的排列（重要）

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

30、连续子数组的最大和

31、整数中1出现的次数