牛客网

数组
字符串
动态规划
栈和队列
链表
树
二分查找
- 旋转数组的最小数字 √
搜索
- 矩阵中的路径 √
- 机器人的运动范围 √
栈和队列
- 用两个栈实现队列 √
位运算
其他

* //没有思路
? //有思路做不出来
- //差一点
√ //完美解决

数组

构建乘积数组 -√

public int[] multiply(int[] A) {
       int[] B = new int[A.length];
       for(int i=0,product=1;i<A.length;product*=A[i],i++){
           B[i]=product;
       }
       for(int i=A.length-1,product = 1; i >= 0;product *= A[i],i--){
           B[i]*=product;
       }
       return B;
   }

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        auto len = A.size();
        vector<int>v(len, 1);
        for (int i = 0, product = 1; i < len;  product *= A[i++]) {
            v[i] = product;
        }
        for (int i = len - 1, product = 1; i >= 0;  product *= A[i--]) {
            v[i] *= product;
        }
        return v;
    }
};

数组中重复的数字 √

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

public boolean duplicate(int[] nums, int length, int[] duplication) {
    if (nums == null || length <= 0)
        return false;
    for (int i = 0; i < length; i++) {
        while (nums[i] != i) {
            if (nums[i] == nums[nums[i]]) {
                duplication[0] = nums[i];
                return true;
            }
            swap(nums, i, nums[i]);
        }
    }
    return false;
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

二维数组的查找 √

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

public boolean Find(int target, int [][] array) {
        int col=array[0].length-1,row=0;
        while(col>=0&&row<=array.length-1){
            if(array[row][col]<target) row++;
            else if(array[row][col]==target) return true;
            else col--;
        }
        return false;
    }

表示数值的字符串 -

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

[]  ： 字符集合
()  ： 分组
?   ： 重复 0 ~ 1 次
+   ： 重复 1 ~ n 次
*   ： 重复 0 ~ n 次
.   ： 任意字符
\\. ： 转义后的 .
\\d ： 数字
public boolean isNumeric(char[] str) {
    if (str == null || str.length == 0)
        return false;
    return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
}

和为S的两个数字 √

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

public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> res = new ArrayList();
        if(array.length==0) return res;
        int lo=0,hi=array.length-1;
        while(hi>lo){
            if(array[lo]+array[hi]==sum){
                res.add(array[lo]);
                res.add(array[hi]);
                break;
            }else if(array[lo]+array[hi]>sum) hi--;
            else lo++;
        }
        return res;
    }

和为S的连续正数序列 √

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

public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
       int lo=1,hi=1;
        ArrayList<ArrayList<Integer> > res = new ArrayList();
        while(hi<sum&&hi>=lo){
            if(cal(lo,hi)<sum){
                hi++;
            }else if(cal(lo,hi)>sum){
                lo++;
            }else{
                res.add(rec(lo,hi));
                hi++;
            }
        }
        return res;
    }
    int cal(int lo, int hi){
        return (lo+hi)*(hi-lo+1)/2;
    }
    ArrayList<Integer> rec(int lo,int hi){
         ArrayList<Integer> res=new ArrayList();
        for(int i=lo;i<=hi;i++) res.add(i);
        return res;
    }
}

扑克牌顺子 √

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何，如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

public boolean isContinuous(int [] numbers) {
       if(numbers.length==0) return false;
       Arrays.sort(numbers);
       int cnt=0;
       for(int i=0;i<numbers.length;i++)
           if(numbers[i]==0) cnt++;
       for(int i=cnt;i<numbers.length-1;i++){
           if(numbers[i]==numbers[i+1]) return false;            
           cnt-=numbers[i+1]-numbers[i]-1;
       }
       return cnt>=0;
   }

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

public void reOrderArray(int [] array) {
       int j=0, i=0;
       for(;i<array.length;i++){
           if(array[i]%2==1) j++;
       }
       int[] copy = array.clone();
       i=0;
       for(int c:copy){
           if(c%2==0) array[j++]=c;
           else array[i++]=c;
       }
   }

数字在排序数组中出现的次数 √

public int GetNumberOfK(int [] array , int k) {
        if(array.length==0) return 0;
      int left=BS(array,k);
      if(array[left]!=k) return 0;
      int right=BS(array,k+1);
        return array[right]==k?right-left+1:right-left;
    }
    public int BS(int[] a,int k){
        int lo=0,hi=a.length-1;
        while(lo<hi){
            int mid=lo+(hi-lo)/2;
            if(a[mid]<k)lo=mid+1;
            else hi=mid;
        }
        return lo;
    }

最小的k个数 -√

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
         ArrayList<Integer> res=new ArrayList();
        if(input==null||input.length==0||k<=0||k>input.length) return res;
        qs(input,k-1);
        for(int i=0;i<k;i++) res.add(input[i]);
        return res;
    }
    public void qs(int[] a,int k){
        int lo=0,hi=a.length-1;
        while(lo<hi){
            int mid = judge(a,lo,hi);
            if(mid==k) break;
            else if(mid<k)lo=mid+1;
            else hi=mid-1;
        }        
    }
    public int judge(int a[],int lo,int hi){
        int i=lo,j=hi,x=a[lo];        
        while(i<j){
            while(i<j&&a[j]>=x)j--;
            if(i<j) a[i]=a[j];
            while(i<j&&a[i]<x)i++;
            if(i<j) a[j]=a[i];
        }
        a[i]=x;
        return i;
    }
}

#include<vector>
#include <iostream>
using namespace std;
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if (k > input.size()||k<0) return vector<int>();
        return qs(input, k - 1);
    }
    vector<int> qs(vector<int> &input, int k) {
        int lo = 0, hi = input.size() - 1;
        while (lo < hi) {
            int mid = select(input, lo, hi);
            if (k == mid) break;
            else if (input[mid] > k)hi = mid - 1;
            else lo = mid + 1;
        }
        return  vector<int>(begin(input), begin(input)+k+1);
    }
    int select(vector<int>& a, int lo, int hi) {
        int i = lo, j = hi, x = a[lo];
        while (i < j) {
            while (i < j && x <= a[j])j--;
            if (i < j)a[i] = a[j];
            while (i < j && x > a[i])i++;
            if (i < j)a[j] = a[i];
        }
        a[i] = x;
        return i;
    }
};
int main() {
    Solution s;
    vector<int> A{ 7,1,4,3,2,5,6 };
    for(int i:s.GetLeastNumbers_Solution(A,6))
    cout << i <<",";
  
}

数组中的逆序对 -

public class Solution {
    long cnt;
    public int InversePairs(int[] array) {
        cnt = 0;
        if (array == null||array.length==0) return  0;
        mergeSort(array, 0, array.length - 1,new int[array.length]);
        return (int)(cnt%1000000007);
    }

    /*
     * 归并排序(从上往下)
     */
    public void mergeSort(int[] a, int start, int end,int[] tmp) {
        if (start >= end)
            return;
        int mid = (start + end) >> 1;
        mergeSort(a, start, mid,tmp);
        mergeSort(a, mid + 1, end,tmp);
        merge(a, start, mid, end,tmp);
    }

    /*
     * 将一个数组中的两个相邻有序区间合并成一个
     */
    public void merge(int[] a, int start, int mid, int end,int[] tmp) {

        int i = start, j = mid + 1, k = 0;
        while (i <= mid && j <= end) {
            if (a[i] <= a[j])
                tmp[k++] = a[i++];
            else {
                tmp[k++] = a[j++];
                cnt += mid - i + 1;  // core code, calculate InversePairs............
            }
        }

        while (i <= mid)
            tmp[k++] = a[i++];
        while (j <= end)
            tmp[k++] = a[j++];
        for (i = 0; i <k; i++)
            a[start + i] = tmp[i];
    }
}

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

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

public int MoreThanHalfNum_Solution(int[] nums) {
    int majority = nums[0];
    for (int i = 1, cnt = 1; i < nums.length; i++) {
        cnt = nums[i] == majority ? cnt + 1 : cnt - 1;
        if (cnt == 0) {
            majority = nums[i];
            cnt = 1;
        }
    }
    int cnt = 0;
    for (int val : nums)
        if (val == majority)
            cnt++;
    return cnt > nums.length / 2 ? majority : 0;
}

顺时针打印矩阵 ×

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.

public ArrayList<Integer> printMatrix(int[][] matrix) {
    ArrayList<Integer> ret = new ArrayList<>();
    int r1 = 0, r2 = matrix.length - 1, c1 = 0, c2 = matrix[0].length - 1;
    while (r1 <= r2 && c1 <= c2) {
        for (int i = c1; i <= c2; i++)
            ret.add(matrix[r1][i]);
        for (int i = r1 + 1; i <= r2; i++)
            ret.add(matrix[i][c2]);
        if (r1 != r2)
            for (int i = c2 - 1; i >= c1; i--)
                ret.add(matrix[r2][i]);
        if (c1 != c2)
            for (int i = r2 - 1; i > r1; i--)
                ret.add(matrix[i][c1]);
        r1++; r2--; c1++; c2--;
    }
    return ret;
}

字符串

替换空格 √

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

public String replaceSpace(StringBuffer str) {
        int p1=str.length()-1;
        for(int i=0;i<=p1;i++){
            if(str.charAt(i)==' ')
                str.append("  ");
        }
        int p2=str.length()-1;
        while(p1>=0&&p1<p2){
            if(str.charAt(p1)!=' '){
                str.setCharAt(p2--,str.charAt(p1--));
            }else{
                p1--;
                str.setCharAt(p2--,'0');
                str.setCharAt(p2--,'2');
                str.setCharAt(p2--,'%');
            }
        }
        return str.toString();
    }

左旋转字符串 √

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

public String LeftRotateString(String str,int n) {
        if(str==null||str.length()==0) return str;
        int len = str.length();
        n=n%len;      
        char[] c=str.toCharArray();
        rotate(c,0,n-1);
        rotate(c,n,len-1);
        rotate(c,0,len-1);
        return String.valueOf(c);
    }
    public void rotate(char[] c,int lo,int hi){
        while(hi>lo){
             char tmp=c[lo];
            c[lo]=c[hi];
            c[hi]=tmp;
            hi--;
            lo++;
        }            
    }

翻转单词顺序列 √

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

public String ReverseSentence(String str) {
        if(str.trim().equals("")||str.length()<=1)return str;
        String[] s=str.split(" ");
        String res="";
        for(int i=s.length-1;i>=0;i--){
            res+=s[i]+" ";
        }
        return res.substring(0,res.length()-1);
    }

public String ReverseSentence(String str) {
    int n = str.length();
    char[] chars = str.toCharArray();
    int i = 0, j = 0;
    while (j <= n) {
        if (j == n || chars[j] == ' ') {
            reverse(chars, i, j - 1);
            i = j + 1;
        }
        j++;
    }
    reverse(chars, 0, n - 1);
    return new String(chars);
}

private void reverse(char[] c, int i, int j) {
    while (i < j)
        swap(c, i++, j--);
}

private void swap(char[] c, int i, int j) {
    char t = c[i];
    c[i] = c[j];
    c[j] = t;
}

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

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

public int FirstNotRepeatingChar(String str) {
       int[] map=new int[52];
       Arrays.fill(map,-2);
       char c[]=str.toCharArray();
       for(int i=0;i<c.length;i++){
           int index=0;
           if(c[i]>'Z'){
               index=c[i]-'a'+26;                
           }else{
              index =c[i]-'A';                
           }
           if(map[index]==-2) map[index]=i;
           else map[index]=-1;
       }
       int res=Integer.MAX_VALUE;
       for(int i=0;i<52;i++){
           if(map[i]!=-2&&map[i]!=-1){
               res=Math.min(res,map[i]);
           }
       }
       return res==Integer.MAX_VALUE?-1:res;
   }

把字符串转化成整数 √

public int StrToInt(String str) {
    if (str == null || str.length() == 0)
        return 0;
    boolean isNegative = str.charAt(0) == '-';
    long ret = 0;
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (i == 0 && (c == '+' || c == '-'))  /* 符号判定 */
            continue;
        if (c < '0' || c > '9')                /* 非法输入 */
            return 0;
        ret = ret * 10 + (c - '0');
    }
    ret = isNegative? -ret:ret;
    if(ret<=Integer.MAX_VALUE&&ret>=Integer.MIN_VALUE) return (int)ret;
    return 0;
}

把数组排成最小的数 -

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

public String PrintMinNumber(int [] numbers) {
          if (numbers == null || numbers.length == 0)
                return "";
            int n = numbers.length;
            String[] nums = new String[n];
            for (int i = 0; i < n; i++)
                nums[i] = numbers[i] + "";
            Arrays.sort(nums, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));
            String ret = "";
            for (String str : nums)
                ret += str;
            return ret;
    }

动态规划

正则表达式匹配 -

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

public boolean match(char[] str, char[] pattern)
    {
        int m=str.length,n=pattern.length;
        boolean[][] dp=new boolean[m+1][n+1];
        dp[0][0]=true;
        for(int i=2;i<=n;i++){
            if(pattern[i-1]=='*'&&dp[0][i-2])dp[0][i]=true;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(pattern[j-1]=='.'||pattern[j-1]==str[i-1])
                    dp[i][j]=dp[i-1][j-1];
                else if(pattern[j-1]=='*'){
                    if(pattern[j-2]==str[i-1]||pattern[j-2]=='.'){
                        dp[i][j]|=dp[i][j-2]|dp[i][j-1]|dp[i-1][j];
                    }else{
                        dp[i][j]|=dp[i][j-2];
                    }
                }
            }
        }
        return dp[m][n];
    }

跳台阶 √

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

变态跳台阶 √

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

public int JumpFloorII(int target) {
        int dp[]=new int[target+1];
        Arrays.fill(dp,1);
        for(int i=2;i<=target;i++){
            for(int j=1;j<i;j++)
                dp[i]+=dp[j];
        }
        return dp[target];
    }

剪绳子 √

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
            dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));
    return dp[n];
}

斐波那契 √

public int fib(int N) {
    int dp[] = new int[3];
    dp[1]=1;
    for(int i = 2; i <= N ; i++){
        dp[i%3] = dp[(i-1)%3] + dp[(i-2)%3];
    }
    return dp[N%3];
}

矩形覆盖 √

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

比如n=3时，2*3的矩形块有3种覆盖方法：

public int RectCover(int n) {
      int dp[] = new int[4];
      dp[1]=1;
      dp[2]=2;
      for (int i=3;i<=n;i++){
          dp[i%4]=dp[(i-1)%4]+dp[(i-2)%4];
      }
      return dp[n%4];
   }

连续数组的最大和 √

public int FindGreatestSumOfSubArray(int[] array) {
       if(array==null||array.length==0) return 0;  
       int res=array[0];
       int dp[]=new int[array.length];
        dp[0]=res;
        for(int i=1;i<array.length;i++){
            if(dp[i-1]+array[i]>array[i])
                dp[i]=dp[i-1]+array[i];
            else
                dp[i]=array[i];
            res=Math.max(dp[i],res);
        }
        return res;
    }

丑数 ×

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

 public int GetUglyNumber_Solution(int N) {
    if (N <= 6)
        return N;
    int i2 = 0, i3 = 0, i5 = 0;
    int[] dp = new int[N];
    dp[0] = 1;
    for (int i = 1; i < N; i++) {
        int next2 = dp[i2] * 2, next3 = dp[i3] * 3, next5 = dp[i5] * 5;
        dp[i] = Math.min(next2, Math.min(next3, next5));
        if (dp[i] == next2)
            i2++;
        if (dp[i] == next3)
            i3++;
        if (dp[i] == next5)
            i5++;
    }
    return dp[N - 1];
}

字符串的排列 -

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

public ArrayList<String> Permutation(String str) {
       ArrayList<String> res = new ArrayList();
        if(str==null||str.length()==0) return res;
        return back(str,res,new StringBuilder(),new boolean[str.length()]);
    }
    public ArrayList<String> back(String str,ArrayList<String> res,StringBuilder sb,boolean[] memo){
        if(sb.length()==str.length()){
            res.add(sb.toString());
            return res;
        }
        for(int i=0;i<str.length();i++){
            if(i!=0&&!memo[i-1]&&str.charAt(i)==str.charAt(i-1)) continue;
            if(memo[i]==false){
                memo[i]=true;
                sb.append(str.charAt(i));
                back(str,res,sb,memo);
                sb.deleteCharAt(sb.length()-1);
                memo[i]=false;
            }
            
        }
        return res;
    }

记住deleteCharAt

栈和队列

字符流中第一个不重复的字符 √

public class Solution {
    //Insert one char from stringstream
    Map<Character,Integer> map = new HashMap();
    Queue<Character> q = new LinkedList();
    public void Insert(char ch)
    {
        if(map.containsKey(ch)) map.put(ch,2);
        else{
            map.put(ch,1);
            q.offer(ch);
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        while(!q.isEmpty()){
            char c=q.peek();
            if(map.get(c)==1)return c;
            else q.poll();
        }
        return '#';
    }
}

从尾到头打印链表 √

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

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    Stack<Integer> stack = new Stack<>();
    while (listNode != null) {
        stack.add(listNode.val);
        listNode = listNode.next;
    }
    ArrayList<Integer> ret = new ArrayList<>();
    while (!stack.isEmpty())
        ret.add(stack.pop());
    return ret;
}

包含min函数的栈 √

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

注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

public class Solution {

    Stack<Integer> ele=new Stack();
    Stack<Integer> min=new Stack();
    public void push(int node) {
        if(min.size()==0||node<=min.peek()) min.push(node);
        ele.push(node);
    }
    
    public void pop() {
        if(ele.peek()==min.peek()) min.pop();
        ele.pop();
    }
    
    public int top() {
        return ele.peek();
    }
    
    public int min() {
        return min.peek();
    }
}

栈的压入弹出序列 √

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

public boolean IsPopOrder(int [] pushA,int [] popA) {
    Stack<Integer> s = new Stack();
    int i=0,j=0;
    while(i<pushA.length){
        if(pushA[i]!=popA[j]){
            s.push(pushA[i]);
            i++;
        }
        else{
            i++;
            j++;
        }
    }
    while(!s.isEmpty()){
        if(s.pop()==popA[j]) j++;
    }
    return j==popA.length;
}

链表

链表中环的入口结点 √

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

public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        int flag=0;
        if(pHead==null||pHead.next==null) return null;
        ListNode fast=pHead;
        ListNode slow=pHead;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                flag=1;
                break;
            }           
        }
        if(flag==0) return null;
        else{
             while(pHead!=fast){                    
                    pHead=pHead.next;
                    fast=fast.next;
                    if(fast==pHead)
                        break;
                }
                return pHead;
        }
    }

删除链表中重复的结点 -

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

public ListNode deleteDuplication(ListNode pHead)
   {
       ListNode head = new ListNode(0);
       head.next=pHead;
       ListNode pre=head,now=pHead;
       while(now!=null&&now.next!=null){
           if(now.next.val==now.val){
               while(now.next!=null&&now.next.val==now.val){
                   now=now.next;
               }
              now=now.next;
               pre.next=now;
           }else{
               pre=pre.next;
               now=now.next;
           }
       }
       return head.next;
   }

如果是不删除重复节点的话，将now=now.next注释就可以了。

合并两个排序的链表 √

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

public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode root = new ListNode(0);
        ListNode now=root;
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                now.next=list1;
                list1=list1.next;
            }else{
                now.next=list2;
                list2=list2.next;
            }
            now=now.next;
        }
        now.next= list1==null?list2:list1;
        return root.next;
    }

链表中倒数第k个结点 √

public ListNode FindKthToTail(ListNode head,int k) {
        ListNode root=head;      
        while(k-->0&&root!=null){
            root=root.next;
        }
        if(k>=0)return null;
        while(root!=null){
            root=root.next;
            head=head.next;
        }
        return head;
    }

反转链表 √

public ListNode ReverseList(ListNode head) {
        ListNode root=new ListNode(0);
        while(head!=null){
            ListNode tmp = head.next;
            head.next=root.next;
            root.next=head;
            head=tmp;
        }
        return root.next;
    }

复杂链表的复制 √

public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead == null)
        return null;
        RandomListNode head=pHead;
        while(head!=null){          
            RandomListNode tmp=new RandomListNode(head.label);            
            tmp.next=head.next;
            head.next=tmp;
            head=tmp.next;
        }
        head=pHead;
        while(head!=null){
            if(head.random!=null){
                RandomListNode ran=head.random;
                head.next.random=ran.next;
            }
            head=head.next.next;
        }
        head=pHead;
        RandomListNode res=head.next;
        while(head.next!=null){
            RandomListNode next=head.next;
            head.next=head.next.next;
            head=next;
        }
        return res;
    }

树

重建二叉树 √

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

public TreeNode buildTree(int[] preorder, int[] inorder) {
    return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}

private TreeNode build(int[] preorder, int preS, int preE, int[] inorder, int inS, int inE) {
    if(preE>preS||inE>inS) return null;
    TreeNode root=new TreeNode(preorder[preS]);
    for (int i = inS; i <=inE; i++) {
        if(inorder[i]==preorder[preS]){
            root.left=build(preorder,preS+1,preS+i-inS,inorder,inS,i-1);
            root.right=build(preorder,preS+i-inS+1,preE,inorder,i+1,inE);
        }
    }
    return root;
}

二叉树的镜象 √

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

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

public void Mirror(TreeNode root) {
    if (root == null)
        return;
    swap(root);
    Mirror(root.left);
    Mirror(root.right);
}
 
private void swap(TreeNode root) {
    TreeNode t = root.left;
    root.left = root.right;
    root.right = t;
}

从上到下打印二叉树 √

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

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer> res = new ArrayList();
    if(root==null) return res;
    Queue<TreeNode> q = new LinkedList();
    q.offer(root);
    while(!q.isEmpty()){
        TreeNode tmp=q.poll();
        res.add(tmp.val);
        if(tmp.left!=null) q.offer(tmp.left);
        if(tmp.right!=null) q.offer(tmp.right);
    }
    return res;
}

按之字形顺序打印二叉树 √

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

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> res = new ArrayList();
    if(pRoot==null) return res;
    Queue<TreeNode> q = new LinkedList();
    q.add(pRoot);
    int flag=1;
    while(!q.isEmpty()){
        int len = q.size();
        ArrayList<Integer> memo = new ArrayList();
        for(int i=0;i<len;i++){
            TreeNode tmp = q.poll();
            if(flag==1) memo.add(tmp.val);
            else memo.add(0,tmp.val);
            if(tmp.left!=null) q.offer(tmp.left);
            if(tmp.right!=null) q.offer(tmp.right);
        }
        flag=flag*-1;
        res.add(memo);
    }
    return res;
}

对称的二叉树 √

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

boolean isSymmetrical(TreeNode pRoot)
{
    if(pRoot==null) return true;
    return isSymmetrical(pRoot.left,pRoot.right);
}
boolean isSymmetrical(TreeNode p,TreeNode q){
    if(q==null&&p==null) return true;
    if(q==null||p==null) return false;
    return q.val==p.val&&isSymmetrical(q.left,p.right)&&isSymmetrical(q.right,p.left);
}

二叉树的深度 √

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

序列化二叉树 -

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

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

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

public class Solution {
    String Serialize(TreeNode root) {
        return serial(root,new StringBuilder());
  }
    String serial(TreeNode root,StringBuilder sb ){        
        if(root==null){
            sb.append("#,");
            return sb.toString();
        }
        sb.append(root.val+",");
        serial(root.left,sb);
        serial(root.right,sb);
        return sb.toString();
    }
    TreeNode Deserialize(String str) {
        String[] s=str.split(",");
       return deserial(new LinkedList(Arrays.asList(s)));
  }
    TreeNode deserial(LinkedList<String> l){
       String tmp = l.poll();
        if(tmp.equals("#")) return null;
        TreeNode root=new TreeNode(Integer.valueOf(tmp));
        root.left=deserial(l);
        root.right=deserial(l);
        return root;
    }
}

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

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

private TreeNode ret;
private int cnt = 0;

public TreeNode KthNode(TreeNode pRoot, int k) {
    inOrder(pRoot, k);
    return ret;
}

private void inOrder(TreeNode root, int k) {
    if (root == null || cnt >= k)
        return;
    inOrder(root.left, k);
    cnt++;
    if (cnt == k)
        ret = root;
    inOrder(root.right, k);
}

二叉树的下一个结点 -

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

public TreeLinkNode GetNext(TreeLinkNode pNode)
   {
       if(pNode.right!=null){
            TreeLinkNode tmp=pNode.right;
           while(tmp.left!=null){              
               tmp=tmp.left;
           }
           return tmp;
       }else{
           TreeLinkNode parent=pNode.next;
           while(parent!=null){
              if(parent.left==pNode) return parent;
               pNode=parent;
               parent=parent.next;
           }
           return null;
       }
   }

树的子结构 √

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

public boolean HasSubtree(TreeNode root1,TreeNode root2) {
       if(root1==null||root2==null) return false;
       return check(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
   }
   public boolean check(TreeNode root1,TreeNode root2) {
       if(root2==null) return true;
       if(root1==null) return false;
       return root1.val==root2.val&&check(root1.left,root2.left)&&check(root1.right,root2.right);
   }

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

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

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        return find(root,target,new ArrayList<Integer>(),new ArrayList<ArrayList<Integer>>());
    }
    public ArrayList<ArrayList<Integer>> find(TreeNode root,int target,ArrayList<Integer> tmp,ArrayList<ArrayList<Integer>> res){
        if(root==null) return res;
        if(target==root.val&&root.left==root.right){
            tmp.add(root.val);
            res.add(new ArrayList(tmp));
            tmp.remove(tmp.size()-1);
            return res;
        }
        tmp.add(root.val);
        if(root.left!=null)
        find(root.left,target-root.val,tmp,res);
        find(root.right,target-root.val,tmp,res);
        tmp.remove(tmp.size()-1);
        return res;
    }

二叉搜索树和双向链表 -

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

private TreeNode pre = null;
private TreeNode head = null;

public TreeNode Convert(TreeNode root) {
    inOrder(root);
    return head;
}

private void inOrder(TreeNode node) {
    if (node == null)
        return;
    inOrder(node.left);
    node.left = pre;
    if (pre != null)
        pre.right = node;
    pre = node;
    if (head == null)
        head = node;
    inOrder(node.right);
}

二叉搜索树的后序遍历序列 √

public boolean VerifySquenceOfBST(int [] sequence) {
    if(sequence.length==0) return false;
    int lo=0,hi=sequence.length-1;
    return find(sequence,lo,hi);
}
public boolean find(int[] sequence,int lo,int hi){
    if(lo>=hi) return true;
    int pivot=sequence[hi];
    int index=lo;
    for(;index<hi;index++){
        if(sequence[index]>pivot) break;
    }
    for(int i=index;i<hi;i++){
        if(sequence[i]<pivot) return false;
    }
    return find(sequence,lo,index-1)&&find(sequence,index,hi-1);
}

二分查找

旋转数组的最小数字 √

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

public class Solution {
    public int minNumberInRotateArray(int [] array) {        
        int lo=0,hi=array.length-1;
        if(array[lo]<array[hi]) return array[lo];
        while(lo<hi){
            int mid = lo+(hi-lo)/2;
            if(array[mid]>array[array.length-1]) lo=mid+1;
            else hi=mid;
        }
        return array[lo];
    }
}

搜索

矩阵中的路径 √

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如

矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

public class Solution {
      int dir[][] = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        int len = matrix.length;
        boolean visited[] = new boolean[len];
        for (int i=0;i<rows;i++){
            for (int j=0;j<cols;j++){
                if (matrix[i*cols+j]==str[0]){
                    visited[i*cols+j]=true;
                    if(dfs(matrix,rows,cols,i,j,str,visited,0))
                        return true;
                    visited[i*cols+j]=false;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[] matrix, int rows, int cols, int i, int j, char[] str, boolean[] visited, int k) {
        int index = i*cols+j;
        if(k==str.length-1&&str[k]==matrix[index]) return true;
        for (int[] direct:dir){
            int x=i+direct[0];
            int y=j+direct[1];
            if(x<rows&&x>=0&&y<cols&&y>=0&&visited[x*cols+y]==false&&str[k]==matrix[index]){
                visited[x*cols+y]=true;
                if(dfs(matrix,rows,cols,x,y,str,visited,k+1)) return true;
                visited[x*cols+y]=false;
            }
        }
        return false;
    }

}

机器人的运动范围 √

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

public class Solution {
        int[][] direction = {{1,0},{0,1},{-1,0},{0,-1}};
    public int movingCount(int threshold, int rows, int cols){
        if(threshold<=0) return 0;
        HashSet<Integer> set = new HashSet<>();
        set.add(0);
        dfs(0,0,rows,cols,threshold,set);
        return set.size();
    }

    private void dfs(int i, int j, int rows, int cols, int threshold, HashSet<Integer> set) {
        for (int[] dir : direction) {
            int x = i+dir[0];
            int y=j+dir[1];
            int index = x*cols+y;
            if (x>=0&&x<rows&&y>=0&&y<cols&&!set.contains(index)&&judge(x,y,threshold)){
                set.add(index);
                dfs(x,y,rows,cols,threshold,set);
            }
        }
    }

    private boolean judge(int x, int y,int threshold) {
        int xVal=0,yVal=0;
        while(x!=0){
            xVal+=x%10;
            x=x/10;
        }
        while(y!=0){
            yVal+=y%10;
            y=y/10;
        }
        //System.out.println(xVal+yVal);
        return xVal+yVal<=threshold;
    }
}

栈和队列

用两个栈实现队列 √

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

Stack<Integer> in = new Stack<Integer>();
Stack<Integer> out = new Stack<Integer>();
 
public void push(int node) {
    in.push(node);
}
 
public int pop() throws Exception {
    if (out.isEmpty())
        while (!in.isEmpty())
            out.push(in.pop());
 
    if (out.isEmpty())
        throw new Exception("queue is empty");
 
    return out.pop();
}

位运算

不用加减乘除做加法 ×

1
2
3

public int Add(int a, int b) {
    return b == 0 ? a : Add(a ^ b, (a & b) << 1);
}

二进制中1的个数 ×

public int NumberOf1(int n) {
       int count = 0;
       while (n != 0) {
           /*
           * 用1和n进行位与运算，
           * 结果要是为1则n的2进制形式
           * 最右边那位肯定是1，否则为0
           */
           if ((n & 1) == 1) {
               count++;
           }
           //把n的2进制形式往右推一位
           n = n >>> 1;
       }
       return count;
   }

数组中只出现一次的数字 ×

public void FindNumsAppearOnce(int [] nums,int num1[] , int num2[]) {
    int diff = 0;
	for (int num : nums)
    	diff ^= num;
	diff &= -diff;
	for (int num : nums) {
      if ((num & diff) == 0)
         num1[0] ^= num;
      else
         num2[0] ^= num;
	}
}

其他

求1+2+3+…+n ×

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

public int Sum_Solution(int n) {
        int sum = n;
        boolean ans = (n>0)&&((sum+=Sum_Solution(n-1))>0);
        return sum;
    }

数据流的中位数 -

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

public class Solution {
    PriorityQueue<Integer> left=new PriorityQueue<>((o1,o2) ->o2 - o1);
    PriorityQueue<Integer> right=new PriorityQueue<>();
    int N=0;
    public void Insert(Integer num) {
        N++;
        if(N%2==1){
            right.add(num);
            left.add(right.poll());
        }else{
            left.add(num);
            right.add(left.poll());
        }
        
    }

    public Double GetMedian() {
        if(N%2==0){
            return (right.peek()+left.peek())/2.0;
        }
        return (double)left.peek();
    }
}

滑动窗口的最大值 -

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。

public ArrayList<Integer> maxInWindows(int[] num, int size) {
    ArrayList<Integer> ret = new ArrayList<>();
    if (size > num.length || size < 1)
        return ret;
    PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);  /* 大顶堆 */
    for (int i = 0; i < size; i++)
        heap.add(num[i]);
    ret.add(heap.peek());
    for (int i = 0, j = i + size; j < num.length; i++, j++) {            /* 维护一个大小为 size 的大顶堆 */
        heap.remove(num[i]);
        heap.add(num[j]);
        ret.add(heap.peek());
    }
    return ret;
}

孩子们的游戏 ×

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

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

public int LastRemaining_Solution(int n, int m) {
      
        if(n==0) return -1;
        if(n==1) return 0;
        return (m+LastRemaining_Solution(n-1,m))%n;
    }

数值的整数次方 √

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

保证base和exponent不同时为0

public double Power(double base, int exponent) {
        if(exponent==0) return 1;
        if(exponent==1) return base;
        if(exponent<0){
            base=1/base;
            exponent=-exponent;
        } 
        return exponent%2==0?Power(base*base,exponent/2):base*Power(base*base,exponent/2);
  }

整数中1出现的次数 ×

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
    int ones = 0;
    for (long m = 1; m <= n; m *= 10)
        ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0);
    return ones;
    }
}

剑指Offer

剑指Offer

数组

构建乘积数组 -√

数组中重复的数字 √

二维数组的查找 √

表示数值的字符串 -

和为S的两个数字 √

和为S的连续正数序列 √

扑克牌顺子 √

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

数字在排序数组中出现的次数 √

最小的k个数 -√

数组中的逆序对 -

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

顺时针打印矩阵 ×

字符串

替换空格 √

左旋转字符串 √

翻转单词顺序列 √

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

把字符串转化成整数 √

把数组排成最小的数 -

动态规划

正则表达式匹配 -

跳台阶 √

变态跳台阶 √

剪绳子 √

斐波那契 √

矩形覆盖 √

连续数组的最大和 √

丑数 ×

字符串的排列 -

栈和队列

字符流中第一个不重复的字符 √

从尾到头打印链表 √

包含min函数的栈 √

栈的压入弹出序列 √

链表

链表中环的入口结点 √

删除链表中重复的结点 -

合并两个排序的链表 √

链表中倒数第k个结点 √

反转链表 √

复杂链表的复制 √

树

重建二叉树 √

二叉树的镜象 √

从上到下打印二叉树 √

按之字形顺序打印二叉树 √

对称的二叉树 √

二叉树的深度 √

序列化二叉树 -

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

二叉树的下一个结点 -

树的子结构 √

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

二叉搜索树和双向链表 -

二叉搜索树的后序遍历序列 √

二分查找

旋转数组的最小数字 √

搜索

矩阵中的路径 √

机器人的运动范围 √

栈和队列

用两个栈实现队列 √

位运算

不用加减乘除做加法 ×

二进制中1的个数 ×

数组中只出现一次的数字 ×

其他

求1+2+3+…+n ×

数据流的中位数 -

滑动窗口的最大值 -

孩子们的游戏 ×

数值的整数次方 √

整数中1出现的次数 ×