剑指offer-Java版（下）-叭楼楼市分享网

楼市新闻、行业动态叭楼，新房带看，二手房代办过户，望京二手房精选房源，您置业的小管家。

31.丑数

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

思路：动态规划的解法。一个丑数一定由另一个丑数乘以2或者乘以3或者乘以5得到，那么我们从1开始乘以2,3,5，就得到2,3,5三个丑数，在从这三个丑数出发乘以2,3,5就得到4,6,10; 6,9,15;10,15,25九个丑数，这种方法会得到重复且无序的丑数，而且我们题目要求第N个丑数，这样的方法得到的丑数也是无序的，我们可以维护三个索引。

代码：

import java.util.ArrayList;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index<=0)
            return 0;
        ArrayList<Integer> arr = new ArrayList<Integer>();
        arr.add(1);
        int a = 0;
        int b = 0;
        int c = 0;
        int nextMin = 1;
        for(int i=2;i<=index;i++){
            nextMin = Math.min(Math.min(arr.get(a)*2,arr.get(b)*3),arr.get(c)*5);
            arr.add(nextMin);
            if(nextMin>=arr.get(a)*2)
                a += 1;
            if(nextMin>=arr.get(b)*3)
                b += 1;
            if(nextMin>=arr.get(c)*5)
                c += 1;
        }
        return nextMin;
    }
}

32.第一个只出现一次的字符

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

思路：创建哈希表，下标为ACII值，值为出现次数。

代码

import java.util.*;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str.length()==0)
            return -1;
        HashMap<Character,Integer> map=new HashMap<Character,Integer>();
        for(int i=0;i<str.length();i++)
        {
            char c=str.charAt(i);
            if(map.containsKey(c))
            {
                int time=map.get(c);
                time++;
                map.put(c,time);
            }
            else
                map.put(c,1);
        }
       for(int i=0;i<str.length();i++)
       {
          char c=str.charAt(i);
          if(map.get(c)==1)
              return i;
       }
       return -1;
    }
}

33.数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。例如{7,5,6,4}，存在5个逆序对，分别是(7,5),(7,6),(7,4),(6,4),(5,4)。并将P对1000000007取模的结果输出。即输出P%1000000007

//使用归并排序的思路求解
public class Solution {
    public int InversePairs(int [] array) {
        if(array==null || array.length==0)
            return 0;
        int[] copy = new int[array.length];
        for(int i=0;i<array.length;i++){
            copy[i]=array[i];
        }
        int count = InversePairsCore(array, copy, 0, array.length-1);
        return count;
    }
    private  static int InversePairsCore(int[] array,int[] copy,int low,int high)
    {
        if(low==high)
        {
            return 0;
        }
        int mid = (low+high)>>1;
        int leftCount = InversePairsCore(array,copy,low,mid)%1000000007;
        int rightCount = InversePairsCore(array,copy,mid+1,high)%1000000007;
        int count = 0;
        int i=mid;
        int j=high;
        int locCopy = high;
        while(i>=low&&j>mid)
        {
            if(array[i]>array[j])
            {
                count += j-mid;
                copy[locCopy--] = array[i--];
                if(count>=1000000007)//数值过大求余
                {
                    count%=1000000007;
                }
            }
            else
            {
                copy[locCopy--] = array[j--];
            }
        }
        for(;i>=low;i--)
        {
            copy[locCopy--]=array[i];
        }
        for(;j>mid;j--)
        {
            copy[locCopy--]=array[j];
        }
        for(int s=low;s<=high;s++)
        {
            array[s] = copy[s];
        }
        return (leftCount+rightCount+count)%1000000007;
    }
}

34.两个链表的第一个公共结点

(leetcode160) 编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

分析

设置两个指针，一个从headA开始遍历，遍历完headA再遍历headB，另一个从headB开始遍历，遍历完headB再遍历headA，如果有交点，两个指针会同时遍历到交点处。

代码

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null || pHead2==null)
            return null;
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while(p1 != p2){
            if(p1 != null)
                p1 = p1.next;
            else
                p1 = pHead2;
            if(p2 != null)
                p2 = p2.next;
            else
                p2 = pHead1;
        }
        return p1;
    }
}

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

思路：考虑数组为空的情况，直接返回0；用二分查找法，找到i和j的位置。

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array.length == 0)
            return 0;
        int i = 0;
        int j = array.length-1;
        while(i<j && array[i] != array[j]){
            if(array[i]<k)
                i++;
            if(array[j]>k)
                j--;
        }
        if(array[i] != k)
            return 0;
        return j-i+1;
    }
}

36.二叉树的深度

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

示例：
给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

思路

递归的方法，比较左边路径和右边路径哪边最长，选择最长的一边路径，加上root结点本身的长度。

public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
    }
}

37.平衡二叉树

（同leetcode110）输入一个二叉树，判断是否是平衡二叉树。

平衡二叉树：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 :

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

思路

利用104题中判断二叉树最大深度的函数，左子树和右子树的深度差小于等于1即为平衡二叉树。

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null)
            return true;
        if(Math.abs(height(root.left)-height(root.right))>1)
            return false;
        else
            return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    public int height(TreeNode root){
        if(root == null)
            return 0;
        return Math.max(height(root.left),height(root.right))+1;
    }
}

38.数组中只出现一次的数字

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

思路：如果数组中只有一个数字出现了一次，对数组所有数求一次异或，两个相同的数的异或是0。
那么如果数组中有两个数出现了一次，其他出现了两次，将这数组分成两个子数组，这两个数字分别出现在这两个子数组中，那么就转换成了前面所说的求异或的问题。那么怎么分呢，这里的思路是根据要求的这两个数的异或之后最右边不为1的这一位进行划分的。

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int res = 0;
        for(int x:array)
            res ^= x;
        int splitBit = 1;
        while((res & splitBit)==0)
            splitBit = splitBit << 1;
        int res1 = 0;
        int res2 = 0;
        for(int x:array){
            if((x & splitBit) != 0)
                res1 ^= x;
            else
                res2 ^= x;
        }
        num1[0] = res1;
        num2[0] = res2;
    }
}

39.和为S的连续正数序列

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。例如连续正数和为100的序列:18,19,20,21,22。

思路：判断每一个起始位置，然后往后遍历，如果和大于目标的话，就进行下一次循环，如果等于目标，将arraylist添加到返回结果。另外，连续的数肯定小于等于和的一半。

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> aList=new ArrayList<ArrayList<Integer>>();
        if(sum<2)
            return aList;
        for(int i=1;i<=sum/2;i++){
            ArrayList<Integer> aList2=new ArrayList<Integer>();
            int count=0;
            for(int j=i;j<sum;j++){
                count+=j;
                aList2.add(j);
                if(count>sum)
                    break;
                else if(count==sum){
                    aList.add(aList2);
                    break;
                }
            }
        }
        return aList; 
    }
}

40.和为S的两个数字

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

思路：由于是排好序的数组，因此对于和相等的两个数来说，相互之间的差别越大，那么乘积越小，因此我们使用两个指针，一个从前往后遍历，另一个从后往前遍历数组即可。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
                ArrayList<Integer> res = new ArrayList<Integer>();
        int i=0;
        int j = array.length-1;
        while(i<j){
            if(array[i]+array[j]>sum)
                j-=1;
            else if(array[i]+array[j]<sum)
                i+=1;
            else{
                res.add(array[i]);
                res.add(array[j]);
                return res;
            }
        }
        return res;
    }
}

41.左旋转字符串

对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。

思路：分割法。

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

42.翻转单词顺序列

例如，“student. a am I”翻转为“I am a student.”。

思路：按空格切分为数组，从尾到头遍历数组，依次拼接起来。

public class Solution {
    public String ReverseSentence(String str) {
        if(str.trim().length() <= 0){
            return str;
        }
        String[] strArr = str.split(" ");
        String res = "";
        for(int i=strArr.length-1;i>=0;i--){
            if(i != 0){
                res += strArr[i] + " ";
            }else{
                res += strArr[i];
            }
        }
        return res;
    }
}

43.扑克牌顺子

一副扑克牌,里面有2个大王，2个小王，从中随机抽出5张牌，如果牌能组成顺子就输出true，否则就输出false。为了方便起见，大小王是0，大小王可以当作任何数字。

思路：

1、将数组排序；2、统计数组中0的个数，即判断大小王的个数；3、统计数组中相邻数字之间的空缺总数，如果空缺数小于等于大小王的个数，可以组成顺子，否则不行。如果数组中出现了对子，那么一定是不可以组成顺子的。

代码：

import java.util.Arrays;
public class Solution {
    public boolean isContinuous(int [] numbers) {
        int m = numbers.length;
        if(m==0)
            return false;
        Arrays.sort(numbers);
        int count = 0;
        for(int i=0;i<m;i++){
            if(numbers[i]==0)
                count += 1;
        }
        for(int i=count;i<m-1;i++){
            if(numbers[i+1]==numbers[i])
                return false;
            else if((numbers[i+1]-numbers[i]-1)>count)
                return false;
            else
                count -= (numbers[i+1]-numbers[i]-1);
        }
        return true;
    }
}

44.孩子们的游戏（圆圈中最后剩下的数）

游戏是这样的：首先，让小朋友们围成一个大圈。然后，他随机指定一个数m，让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列，不再回到圈中，从他的下一个小朋友开始，继续0…m-1报数….这样下去….直到剩下最后一个小朋友获胜，获胜的小朋友编号多少？(注：小朋友的编号是从0到n-1)

分析：约瑟夫环问题，可以用数组模拟，但需要维护是否出列的状态。使用LinkedList模拟一个环cycle，出列时删除对应的位置。 1. 报数起点为start（初始为0），则出列的位置为out = (start + m – 1) % cycle.size()，删除out位置； 2. 更新起点start = out，重复1直到只剩下一个元素。时间复杂性、空间复杂度均为O(n)。

import java.util.LinkedList;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        LinkedList<Integer> cycle = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            cycle.add(i);
        }
        int start = 0;
        while (cycle.size() > 1) {
            int out = (start + m - 1) % cycle.size();
            cycle.remove(out);
            start = out;
        }
        return cycle.remove();
    }
}

45.求1+2+3+…+n

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

思路：将加法问题转化为递归进行求解即可。

代码：

public class Solution {
    public int sum = 0;
    public int Sum_Solution(int n) {
        getSum(n);
        return sum;
    }
    private void getSum(int n){
        if(n<=0)
            return;
        sum += n;
        getSum(n-1);
    }
}

46.不用加减乘除做加法

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

思路：

对数字做运算，除了加减乘除外，还有位运算，位运算是针对二进制的，二进制的运算有“三步走”策略：

例如5的二进制是101，17的二进制10001。
第一步：各位相加但不计进位，得到的结果是10100。
第二步：计算进位值，只在最后一位相加时产生一个进位，结果是二进制10。
第三步：把前两步的结果相加，得到的结果是10110。转换成十进制正好是22。

接着把二进制的加法用位运算替代：
（1）不考虑进位对每一位相加，0加0、1加1的结果都是0，1加0、0加1的结果都是1。这和异或运算相同。（2）考虑进位，只有1加1的时候产生进位。位与运算只有两个数都是1的时候结果为1。考虑成两个数都做位与运算，然后向左移一位。（3）相加的过程依然重复前面两步，直到不产生进位为止。

public class Solution {
    public int Add(int num1,int num2) {
         while (num2!=0) {
            int temp = num1num2;
            num2 = (num1&num2)<<1;
            num1 = temp;
        }
        return num1;
    }
}

47.把字符串转换成整数

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

示例1：

输入：+2147483647 ，输出：2147483647；输入：1a33，输出：0。

思路：考虑溢出。

public class Solution {
    public int StrToInt(String str) {
        if (str == null)
            return 0;
        int result = 0;
        boolean negative = false;//是否负数
        int i = 0, len = str.length();
        /**
         * limit 默认初始化为 负的 最大正整数 ，假如字符串表示的是正数
         * 那么result(在返回之前一直是负数形式)就必须和这个最大正数的负数来比较，
         * 判断是否溢出
         */
        int limit = -Integer.MAX_VALUE;
        int multmin;
        int digit;
        if (len > 0) {
            char firstChar = str.charAt(0);//首先看第一位
            if (firstChar < '0') { // Possible leading "+" or "-"
                if (firstChar == '-') {
                    negative = true;
                    limit = Integer.MIN_VALUE;//在负号的情况下，判断溢出的值就变成了 整数的 最小负数了
                } else if (firstChar != '+')//第一位不是数字和-只能是+
                    return 0;
                if (len == 1) // Cannot have lone "+" or "-"
                    return 0;
                i++;
            }
            multmin = limit / 10;
            while (i < len) {
                // Accumulating negatively avoids surprises near MAX_VALUE
                digit = str.charAt(i++)-'0';//char转int
                if (digit < 0 || digit > 9)//0到9以外的数字
                    return 0;
                //判断溢出
                if (result < multmin) {
                    return 0;
                }
                result *= 10;
                if (result < limit + digit) {
                    return 0;
                }
                result -= digit;
            }
        } else {
            return 0;
        }
        //如果是正数就返回-result（result一直是负数）
        return negative ? result : -result;
    }
}

48.数组中重复的数字

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

思路：一个简单的方法是先排序再查找，时间复杂度是O(nlogn)。还可以用哈希表来解决，遍历每个数字，每扫描到一个数字可以用O(1)的时间来判断哈希表中是否包含了这个数字，如果没有包含，则加到哈希表，如果包含了，就找到了一个重复的数字。时间复杂度O(n)。

我们注意到数组中的数字都在0~n-1范围内，如果这个数组中没有重复的数字，那么当数组排序后数字i在下标i的位置，由于数组中有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有数字。遍历数组，当扫描到下标为i 的数字m时，首先看这个数字是否等于i，如果是，继续扫描，如果不是，拿它和第m个数字进行比较。如果它和第m个数字相等，就找到了一个重复的数字，如果不相等，就交换两个数字。继续比较。

 // 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
 // 函数返回true/false
public class Solution {
    public boolean duplicate(int numbers[],int length,int[] duplication) {
        for(int i=0;i<length;i++){
            while(numbers[i]!=i){
                int m=numbers[i];
                if(numbers[m]==numbers[i]){
                    duplication[0]=m;
                    return true;
                }
                else{
                    numbers[i]=numbers[m];
                    numbers[m]=m;
                }
            }
        }
        return false;
    }
}

49.构建乘积数组

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]*A[1]*…*A[i-1]*A[i+1]*…*A[n-1]。不能使用除法。

思路：如果没有不能使用除法的限制，可以直接用累乘的结果除以A[i]。由于题目有限制，一种直观的解法是连乘n-1个数字，但时间复杂度是O(n^2)。可以把B[i]=A[0]*A[1]*…*A[i-1]*A[i+1]*…*A[n-1]分成A[0]*A[1]*…*A[i-1]和A[i+1]*…*A[n-1]两部分的乘积。

public class Solution {
    public int[] multiply(int[] A) {
        int length = A.length;
        int[] B = new int[length];
        if(length != 0 ){
            B[0] = 1;
            //计算下三角连乘
            for(int i = 1; i < length; i++){
                B[i] = B[i-1] * A[i-1];
            }
            int temp = 1;
            //计算上三角
            for(int j = length-2; j >= 0; j--){
                temp *= A[j+1];
                B[j] *= temp;
            }
        }
        return B;
    }
}

50.正则表达式匹配

请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。

思路：如果 s和pattern都为空，匹配成功。

当模式中的第二个字符不是“*”时：

1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。

2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。

而当模式中的第二个字符是“*”时：

如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：

1、模式后移2字符，相当于x*被忽略；

2、字符串后移1字符，模式后移2字符；

3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；

public class Solution {
    public boolean match(char[] str, char[] pattern) {
    if (str == null || pattern == null)
        return false;
    return matchCore(str, 0, pattern, 0);
}
    public  boolean matchCore(char[] str,int i,char[] pattern,int j) {
        //str到尾，pattern到尾，匹配成功
        if(str.length == i && j == pattern.length)
            return true;
        //pattern先到尾，匹配失败
        if(str.length != i && j == pattern.length)
            return false;
       //注意数组越界问题，一下情况都保证数组不越界
       if(j < pattern.length-1 && pattern[j+1] == '*') {//下一个是*
           if(str.length != i && (str[i] == pattern[j] || pattern[j] == '.')) //匹配
               return matchCore(str,i,pattern,j+2)|| matchCore(str,i+1,pattern,j);
           else//当前不匹配
               return matchCore(str,i,pattern,j + 2);
       }
       //下一个不是“*”，当前匹配
       if(str.length != i && (str[i] == pattern[j] || pattern[j] == '.'))
           return matchCore(str,i + 1,pattern,j + 1);
        return false;
    }
}

51.表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

思路：数字的格式可以用A[.[B]][E|eC]或者.B[E|eC]表示，其中A和C都是整数（可以有符号也可以没有），B是一个无符号数。

如果遍历到e或E，那么之前不能有e或E，并且e或E不能在末尾；

如果遍历到小数点,那么之前不能有小数点，并且之前不能有e或E；

如果遍历到正负号，那么如果之前有正负号，只能够出现在e或E的后面，如果之前没符号，那么符号只能出现在第一位，或者出现在e或E的后面；

如果遍历到不是上面所有的符号和0~9，返回False。

代码：

public class Solution {
    public boolean isNumeric(char[] str) {
        boolean hasE = false;
        boolean hasDot = false;
        boolean hasSign = false;
        for(int i=0;i<str.length;i++){
            if(str[i]=='E' || str[i]=='e'){
                if(hasE || i==str.length-1)
                    return false;
                hasE = true;
            }
            else if(str[i]=='.'){
                if(hasE || hasDot)
                    return false;
                hasDot = true;
            }
            else if(str[i]=='+' || str[i]=='-'){
                if(hasSign && (str[i-1]!='E' || str[i-1]!='e'))
                    return false;
                if(!hasSign && i!=0 && str[i-1]!='E' && str[i-1]!='e')
                    return false;
            }
            else{
                if(str[i]<'0' || str[i]>'9')
                    return false;
            }
        }
        return true;
    }
}

52.字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

如果当前字符流没有存在出现一次的字符，返回#字符。

思路：用一个字典保存下出现过的字符，以及字符出现的次数。

除保存出现的字符之外，我们用一个字符数组保存出现过程字符顺序，如果不保存插入的char的话，我们可以遍历ascii码中的字符。

代码：

import java.util.*;
public class Solution {
    public ArrayList<Character> charlist = new ArrayList<Character>();
    public HashMap<Character,Integer> map = new HashMap<Character,Integer>();
    public void Insert(char ch)
    {
        if(map.containsKey(ch))
            map.put(ch,map.get(ch)+1);
        else
            map.put(ch,1);
        charlist.add(ch);
    }
    public char FirstAppearingOnce()
    {
        char c='#';
        for(char key : charlist){
            if(map.get(key)==1){
                c=key;
                break;
            }
        }
        return c;
    }
}

53.链表中环的入口节点

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

思路：快慢指针，快指针一次走两步，慢指针一次走一步。如果链表中存在环，且环中假设有n个节点，那么当两个指针相遇时，快的指针刚好比慢的指针多走了环中节点的个数，即n步。从另一个角度想，快的指针比慢的指针多走了慢的指针走过的步数，也是n步。相遇后，快指针再从头开始走，快慢指针再次相遇时，所指位置就是入口。

代码：

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead==null || pHead.next==null || pHead.next.next==null)
            return null;
        ListNode fast=pHead.next.next;
        ListNode slow = pHead.next;
        while(fast != slow){
            if(fast.next==null || fast.next.next==null)
                return null;
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = pHead;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

54.删除链表中重复的结点

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

思路

1.设置一个虚拟头结点，设置两个指针，pre指向虚拟头结点，cur指向头结点。

2.判断下一个节点的值和cur的值是否相等，若相等cur后移，直到下个节点的值和cur的值不同。

3.此时执行pre.next= cur.next。

4.继续走直到结尾.

代码

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        ListNode dummy = new ListNode(0);
        dummy.next = pHead;
        ListNode pre = dummy;
        ListNode cur = pHead;
        while(cur != null){
            while(cur.next != null && cur.next.val==cur.val)
                cur = cur.next;
            if(pre.next==cur)
                pre=pre.next;
            else
                pre.next = cur.next;
            cur = cur.next;
        }
        return dummy.next;
    }
}

55.二叉树的下一个结点

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

思路：如下图所示，二叉树的中序遍历序列是{d,b,h,e,i,a,f,c,g}。

1、如果该节点有右子树，那么它的下一个节点就是它的右子树的最左侧子节点；

2、如果该节点没有右子树且是父节点的左子树，那么下一节点就是父节点；

3、如果该节点没有右子树且是父节点的右子树，比如i节点，那么我们往上找父节点，找到一个节点满足：它是它的父节点的左子树的节点。

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null)
            return pNode;
        if (pNode.right != null) { // 节点有右子树
            pNode = pNode.right;
            while (pNode.left != null) {
                pNode = pNode.left;
            }
            return pNode;
        } 
        // 节点无右子树且该节点为父节点的左子节点
        else if ( pNode.next != null && pNode.next.left == pNode) { 
            return pNode.next;
        } 
        // 节点无右子树且该节点为父节点的右子点
        else if (pNode.next != null && pNode.next .right == pNode) {
            while(pNode.next != null && pNode .next .left != pNode){
                pNode = pNode.next ;
            }
            return pNode.next ;
        }
        else
            return pNode.next ;//节点无父节点 ，即节点为根节点
    }
}

56.对称的二叉树

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

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

思路

递归的思想，首先判断头结点是否为空。然后将根节点的左右两个节点假设成两个独立的树，如果左右两个树都为空，返回True。然后看左子树的左结点和右子树的右结点、左子树的右结点和右子树的左结点是否相同，都相同返回True.

代码

public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot==null)
            return true;
        return isSymmetricalTree(pRoot.left,pRoot.right);
    }
    private boolean isSymmetricalTree(TreeNode left,TreeNode right){
        if(left==null && right==null)
            return true;
        else if(left==null || right==null)
            return false;
        else if(left.val != right.val)
            return false;
        else{
            return isSymmetricalTree(left.left,right.right)
                 && isSymmetricalTree(left.right,right.left);
        }
    }
}

57.把二叉树打印成多行

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

给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

思路

用队列实现，root为空，返回空；队列不为空，记下此时队列中的节点个数end，end个节点出队列的同时，记录节点值，并把节点的左右子节点加入队列中。

代码

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(pRoot == null){
            return result;
        }
        Queue<TreeNode> layer = new LinkedList<TreeNode>();
        ArrayList<Integer> layerList = new ArrayList<Integer>();
        layer.add(pRoot);
        int start = 0, end = 1;
        while(!layer.isEmpty()){
            TreeNode cur = layer.remove();
            layerList.add(cur.val);
            start++;
            if(cur.left!=null){
                layer.add(cur.left);           
            }
            if(cur.right!=null){
                layer.add(cur.right);
            }
            if(start == end){
                end = layer.size();
                start = 0;
                result.add(layerList);
                layerList = new ArrayList<Integer>();
            }
        }
        return result;
    }
}

58.按之字形顺序打印二叉树

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

例如：
给定二叉树 [3,9,20,null,null,15,7],

返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

思路

用两个栈实现，栈s1与栈s2交替入栈出栈。reverse方法时间复杂度比较高，两个栈以空间换时间。

代码

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > listAll = new ArrayList<>();
        if(pRoot==null)return listAll;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        int level = 1;
        s1.push(pRoot);
        while(!s1.isEmpty()||!s2.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            if(level++%2!=0){
                while(!s1.isEmpty()){
                    TreeNode node = s1.pop();
                    list.add(node.val);
                    if(node.left!=null)s2.push(node.left);
                    if(node.right!=null)s2.push(node.right);
                }
            }
            else{
                while(!s2.isEmpty()){
                    TreeNode node = s2.pop();
                    list.add(node.val);
                    if(node.right!=null)s1.push(node.right);
                    if(node.left!=null)s1.push(node.left);
                }
            }
            listAll.add(list);
        }
        return listAll;
   }
}

59.二叉搜索树的第K个节点

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

思路：如果是按中序遍历二叉搜索树的话，遍历的结果是递增排序的。所以只需要中序遍历就很容易找到第K个节点。

public class Solution {
    int count=0;
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot==null || k<=0)
            return null;
        TreeNode res = KthNode(pRoot.left, k);
        if(res!=null)
            return res;
        count++;
        if(count==k)
            return pRoot;
        res = KthNode(pRoot.right, k);
        return res;
    }
}

60.滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个：{[2,3,4],2,6,2,5,1}，{2,[3,4,2],6,2,5,1}，{2,3,[4,2,6],2,5,1}，{2,3,4,[2,6,2],5,1}，{2,3,4,2,[6,2,5],1}，{2,3,4,2,6,[2,5,1]}。

思路：双向队列，queue存入num的位置，时间复杂度O(n)

我们用双向队列可以在O(N)时间内解决这题。当我们遇到新的数时，将新的数和双向队列的末尾比较，如果末尾比新数小，则把末尾扔掉，直到该队列的末尾比新数大或者队列为空的时候才住手。这样，我们可以保证队列里的元素是从头到尾降序的，由于队列里只有窗口内的数.因此一个新数进来：1、判断队列头部的数的下标是否还在窗口中；2、将新数加入到队列；3、如果index已经达到窗口的大小了，则将队列头部的值加入到返回结果中

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(size <= 0)
            return res;
        Deque<Integer> queue = new ArrayDeque<Integer>();
        for(int i=0;i<num.length;i++){
            if(queue.size()>0 && (i - queue.getFirst()) >= size)
                queue.removeFirst();
            while(queue.size()>0 && num[i] > num[queue.getLast()])
                queue.removeLast();
            queue.addLast(i);
            if(i+1>=size)
                res.add(num[queue.getFirst()]);
        }
        return res;
    }
}

声明：本站内容来源于网络或叭楼会员发布，叭楼只作为信息发布平台，版权归原作者所有，本站不承担任何图片、内容、观点等内容版权问题，如对内容有歧义，可第一时间联系本站管理员发送邮件8309272@qq.com或者扫码微信沟通，经核实后我们会第一时间删除。北京二手房、楼市分析 31.丑数把只包含质因子2、3和5的数称作丑数。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。思路：动态规划的解法。一个丑数一定由另一个丑数乘以2或者乘以3或者乘以5得到，那么我们从…