[关闭]
@huangyichun 2018-04-04T11:54:20.000000Z 字数 39473 阅读 1249

剑指Offer试题

算法

1.题目描述：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

  1.     //建议画个图理解下
  2.     public class Solution {
  3.         public boolean Find(int target, int [][] array) {
  4.             if(array==null || array.length == 0){
  5.                 return false;
  6.             }
  7.             int row = 0;
  8.             int col = array[0].length-1;    //数组最后一列的下标
  10.             while(row <=array.length-1 && col >=0){
  11.                 if(array[row][col] > target){//当该列最小的一个值都大于target
  12.                     col --;                 //向左移一列
  13.                 }else if(array[row][col] < target){//当该最小的一个小于target
  14.                     row ++;                 //向下移一行
  15.                 }else{                      //如果该值等于target,返回true
  16.                     return true;
  17.                 }
  18.             }
  19.             return false;
  20.         }
  21.     }

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

  1.     public class Solution {
  2.         public String replaceSpace(StringBuffer str) {
  3.             if(str == null || str.length() <= 0){
  4.                 return "";
  5.             }
  6.             int spaceCount = 0;
  7.             for(int i=0; i<str.length(); i++){//计算空格个数
  8.                 if(str.charAt(i)==' '){
  9.                     spaceCount++;
  10.                 }
  11.             }
  12.             //设置初始下标
  13.             int index = str.length()-1;
  15.             int length = str.length()+spaceCount * 2;//设置新的StringBuilder大小
  17.             //新StringBuilder最后一个字符下标
  18.             int newIndex = length - 1;
  19.             str.setLength(length);
  21.             while(index >=0){
  22.                 //当前下标的字符
  23.                 char c = str.charAt(index);
  24.                 if(c != ' '){
  25.                    str.setCharAt(newIndex--, c);              
  26.                 }else{
  27.                     str.setCharAt(newIndex--,'0');
  28.                     str.setCharAt(newIndex--,'2');
  29.                     str.setCharAt(newIndex--,'%');             
  30.                 }
  31.                   index --;
  32.             }
  33.             return str.toString();
  34.         }
  35.     }

3.题目描述:输入一个链表，从尾到头打印链表每个节点的值

  1.     import java.util.ArrayList;
  2.     public class Solution {
  3.         private ArrayList<Integer> list = new ArrayList<>();
  4.         public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
  6.             if(listNode != null){
  7.                 printListFromTailToHead(listNode.next);//递归
  8.                 list.add(listNode.val);
  9.             }
  10.             return list;
  12.         }
  13.     }

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

  1.     import java.util.*;
  2.     public class Solution {
  3.         private Map<Integer,Integer> map = new HashMap<>();
  4.         public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
  6.             for(int i=0; i<pre.length; i++){
  7.                 map.put(in[i],i);//存放中序中值对应的下标
  8.             }
  9.             return rebuild(pre,0, pre.length-1, 0, pre.length-1);
  11.         }
  13.         public TreeNode rebuild(int[] pre, int pi, int pj, int ni, int nj){
  14.             if(pi>pj)
  15.                 return null;
  16.             int index = map.get(pre[pi]);//前序该值该中序中的位置
  17.             TreeNode root = new TreeNode(pre[pi]);//创建根节点
  18.             root.left = rebuild(pre, pi+1, pi+ index-ni, ni, index-1);//建立根节点的左子树
  19.             root.right = rebuild(pre,pi+index-ni+1,pj, index+1, nj);//建立根节点右子树
  20.             return root;//返回根节点
  21.         }
  22.     }

5.题目描述:用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

  1.     import java.util.Stack;
  2.     import java.util.*;
  3.     public class Solution {
  4.         Stack<Integer> stack1 = new Stack<Integer>();//保存插入
  5.         Stack<Integer> stack2 = new Stack<Integer>();//处理删除
  7.         public void push(int node) {
  8.             stack1.push(node);
  9.         }
  10.         //如果stack2不为空，直接从stack2删除
  11.         //如果stack2为空，将stack1的内容，删除放入stack2中
  12.         public int pop() {
  13.             if(stack2.size() == 0  && stack1.size() == 0){
  14.                 throw new EmptyStackException();
  15.             }
  16.             if(stack2.size() == 0){
  17.                 while(!stack1.isEmpty()){
  18.                     stack2.push(stack1.pop());
  19.                 }
  20.             }
  21.             return stack2.pop();
  22.         }
  23.     }

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

  1.     import java.util.ArrayList;
  2.    public class Solution_1 {
  3.     public static void main(String[] args) {
  4.         int[] array = {4,1,1, 2, 3};
  5.         int i = minNumberInRotateArray(array);
  6.         System.out.println(i);
  7.     }
  8.     //本题考查二分查找
  9.     public static int minNumberInRotateArray(int [] array) {
  10.         if(array == null || array.length == 0){
  11.             return 0;
  12.         }
  13.         if(array.length == 1){
  14.             return array[0];
  15.         }
  16.         int index1 = 0;
  17.         int index2 = array.length-1;
  18.         int mid = index1;
  19.         while(array[index1] >= array[index2]){
  20.              mid = (index2-index1) / 2;
  21.             if(index2-index1 == 1){ //当两个相邻时
  22.                 mid = index2;
  23.                 break;
  24.             }
  25.             if(array[index1] <= array[mid] && array[mid] > array[index2]){// 3 3 3 0 2情况
  26.                 index1 = mid;
  27.             }else if(array[index2] >= array[mid] && array[index1] > array[mid]){// 3 0 0 0 2情况
  28.                 index2 = mid;
  29.             }else{// 3 3 3 0 3,  3 0 0 0 3两种情况无法判断哪个属于旋转部分
  30.                 mid = getMin(array,index1, index2);//采用顺序查找
  31.                 break;
  32.             }
  34.         }
  35.         return array[mid];
  36.     }
  37.     public static int getMin(int[] array, int index1, int index2){
  38.         int min = index1;
  39.         for(int i=index1+1; i<= index2; i++){
  40.             if(array[min] > array[i]){
  41.                 min = i;
  42.             }
  43.         }
  44.         return min;
  45.     }
  46. }

7.题目描述:大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39

  1.     public class Solution {
  2.         public int Fibonacci(int n) {
  3.             if(n < 2){
  4.                 return n;
  5.             }
  6.             int f1 = 0;
  7.             int f2 = 1;
  8.             int f = f2;
  9.             for(int i=2; i<= n; i++){
  10.                 f = f1 + f2;
  11.                 f1 = f2;
  12.                 f2 = f;
  13.             }
  14.             return f2;  
  15.         }
  16.     }

8.题目描述:一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法

  1.     public class Solution {
  2.         public int JumpFloor(int target) {
  3.             if(target <= 2){
  4.                 return target;
  5.             }
  7.             int f1 = 1;
  8.             int f2 = 2;
  9.             int f = f2;
  10.             for(int i=3; i<=target; i++){
  11.                 f = f1 +f2;
  12.                 f1 = f2;
  13.                 f2 = f;
  14.             }
  15.             return f2;
  17.         }
  18.     }

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

  1.     import java.util.*;
  2.     public class Solution {
  3.         public int JumpFloorII(int target) {
  4.             //f(n) = f(n-1) + f(n-2) + ... + f(1); f(n) =  2 * f(n-1);
  5.             //f(1) = 1 f(2) = 2 , f(n-1) = 2 xy(n-1)
  6.             return (int)Math.pow(2,target-1);
  7.         }
  8.     }

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

  1.     public class Solution {
  2.         public int RectCover(int target) {
  3.            if(target <=2){
  4.                return target;
  5.            }
  6.             int f1 = 1;
  7.             int f2 = 2;
  8.             int sum = 0;
  9.             for(int i=3; i<= target; i++){
  10.                 sum = f1 + f2;
  11.                 f1 = f2;
  12.                 f2 = sum;
  13.             }
  14.             return sum;
  15.         }
  16.     }

11.题目描述:输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

  1. ## 位运算 ##
  2. /**负数是用补码表示的，补码求法位原码取反加一(原码是数的绝对值的二进制)
  3.     补码转换成原码为：取反加一(符号位不变)
  4.     例如: -16 二进制8位的 (原码)0001 0000  反码:1110 1111  补码:1111 0000 
  5.     然后-16 / 2 = -8 相当于补码右移一位: 1111 1000 反码:1000 0111 原码: 1000 1000 = -8
  6.     移位运算:右移时，如果是负数，左边补1
  7. */
  8.     public class Solution {
  9.         public int NumberOf1(int n) {
  10.             //思路: 一个数减去1，然后与上这个数，这样这个数从右到左的第一个1变为0
  11.             int count = 0;
  12.             while(n != 0){
  13.                 ++ count;
  14.                 n = (n-1) & n;
  15.             }
  16.             return count;
  18.         }
  19.     }

12.题目描述：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

  1.     public class Solution {
  2.         public double Power(double base, int exponent) {
  3.             if(equal(base,0.0)){
  4.                 throw new IllegalArgumentException("底数不能为0");
  5.             }
  6.             int absExponent = exponent;
  7.             if(exponent < 0){//将指数先转换成正的
  8.                 absExponent = -exponent;
  9.             }
  10.             double result = PowerWithUnsignedExponent(base, absExponent);
  11.             if(exponent < 0){//如果指数为负
  12.                 result = 1.0 / result;
  13.             }
  14.             return result;
  16.         }
  17.         //非递归下的求法
  18.         public static double PowerWithUnsignedExponent(double base, int exponent){
  19.             double result = 1;
  20.             double temp = base;
  21.             while(exponent != 0){
  22.                 if((exponent & 0x1) == 1){
  23.                     result =result * temp;
  24.                 }
  25.                 exponent >>= 1;
  26.                 temp *= temp;
  27.             }
  28.             return result;
  29.         }
  31.         public boolean equal(double num1, double num2){
  32.             if(num1-num2 > -0.0000001 && num1-num2 < 0.0000001){
  33.                 return true;
  34.             }else{
  35.                 return false;
  36.             }
  37.         }
  38.     }

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

  1.     public class Solution {
  2.         public void reOrderArray(int [] array) {
  3.             if(array == null || array.length == 0){
  4.                 return ;
  5.             }
  7.             int begin = 0;
  8.             int end = begin+1;
  9.             while(end < array.length){
  10.                 while(begin < array.length-1 && (array[begin] & 0x1) != 0){//找到偶数
  11.                     begin ++;
  12.                 }
  13.                 end = begin +1;
  14.                 while(end <= array.length-1 && (array[end] & 0x1) == 0){//找到奇数
  15.                     end ++;
  16.                 }
  18.                 if(end == array.length)
  19.                     break;
  21.                int temp = array[end];
  22.                for(int i=end; i > begin; i--){//偶数后移
  23.                    array[i] = array[i-1];
  24.                }
  25.                array[begin] = temp;
  27.                begin ++;
  28.             }
  29.         }
  30.     }

14.题目描述：输入一个链表，输出该链表中倒数第k个结点

  1.     public class Solution {
  2.         public ListNode FindKthToTail(ListNode head,int k) {
  4.             if(head == null || k <= 0){
  5.                 return null;
  6.             }
  8.             ListNode pHead = head;
  9.             ListNode pBehind = null;
  10.             for(int i=0; i<k-1; i++){//先走k-1个节点
  11.                 if(pHead.next != null){
  12.                     pHead = pHead.next;
  13.                 }else{
  14.                     return null;
  15.                 }
  16.             }
  18.             pBehind = head;
  19.             while(pHead.next != null){
  20.                 pHead = pHead.next;
  21.                 pBehind = pBehind.next;
  22.             }
  23.             return pBehind;
  24.         }
  25.     }

15.题目描述:输入一个链表，反转链表后，输出链表的所有元素

  1.     /*
  2.     public class ListNode {
  3.         int val;
  4.         ListNode next = null;
  6.         ListNode(int val) {
  7.             this.val = val;
  8.         }
  9.     }*/
  10.     public class Solution {
  11.         public ListNode ReverseList(ListNode head) {
  13.             if(head == null){
  14.                 return null;
  15.             }
  16.             //手动画个链表，操作下就能理解了
  17.             ListNode preNode = null;
  18.             ListNode nextNode = null;
  20.             while(head != null){
  21.                 nextNode = head.next;
  22.                 head.next = preNode;
  23.                 preNode = head;
  24.                 head = nextNode;
  25.             }
  26.             return preNode;
  27.         }
  28.     }

16.题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则

  1.     public class Solution {
  2.         public ListNode Merge(ListNode list1,ListNode list2) {
  3.             if(list1 == null)
  4.                 return list2;
  5.             else if(list2 == null)
  6.                 return list1;
  8.             ListNode head = null;
  9.             //递归思想实现
  10.             if(list1.val < list2.val){
  11.                 head = list1;
  12.                 head.next = Merge(list1.next, list2);
  13.             }else{
  14.                 head = list2;
  15.                 head.next = Merge(list1, list2.next);
  16.             }
  17.             return head;
  18.         }
  19.     }

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

  1.     public class Solution {
  2.         public boolean HasSubtree(TreeNode root1,TreeNode root2) {
  3.             //使用先序遍历找到root1 == root2
  4.             //当root1 = root2时，采用先序遍历判断两个子树是否相同
  5.             boolean isChild = false;
  6.             if(root1 == null || root2 == null){
  7.                 return false;
  8.             }
  10.             if(root1.val == root2.val){
  11.                 isChild = isTheSame(root1, root2);
  12.             }
  13.             if(!isChild){
  14.                 isChild = HasSubtree(root1.left,root2);
  15.             }
  16.             if(!isChild){
  17.                 isChild = HasSubtree(root1.right,root2);
  18.             }
  19.             return isChild;
  20.         }
  22.         public boolean isTheSame(TreeNode root1, TreeNode root2){
  23.             if(root2 == null) //递归结束条件
  24.                 return true;
  25.             if(root1 == null)
  26.                 return false;
  28.             if(root1.val != root2.val)
  29.                 return false;
  31.             return isTheSame(root1.left,root2.left) && isTheSame(root1.right,root2.right);
  33.         }
  34.     }

18.题目描述:操作给定的二叉树，将其变换为源二叉树的镜像。

  1.     public class Solution {
  2.         public void Mirror(TreeNode root) {
  3.             if(root == null){//递归退出条件
  4.                 return;
  5.             }
  6.             if(root.left == null && root.right == null)//递归退出条件
  7.                 return;
  9.             //交换左右子树
  10.             TreeNode tmp = root.left;
  11.             root.left = root.right;
  12.             root.right = tmp;
  14.             if(root.left != null){
  15.                 Mirror(root.left);
  16.             }
  17.             if(root.right != null){
  18.                 Mirror(root.right);
  19.             }
  21.         }
  22.     }

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

  1.     //这题没有按照剑指Offer来
  2.     // 1  2  3  4
  3.     // 5  6  7  8
  4.     // 9  10 11 12
  5.     // 13 14 15 16
  6.     // 每先从上右下左各取3个数，刚好取完外圈
  7.     //当到达最后一圈时可能有如下几种情况:
  8.     // a b c   剩下一个长大于宽的矩形
  9.     //-----------------------------------
  10.     // a   剩下一个宽大于长的矩形
  11.     // b
  12.     // c
  13.     // ---------------------------------
  14.     // a   剩下一个值
  15.     import java.util.ArrayList;
  16.     public class Solution {
  17.         public ArrayList<Integer> printMatrix(int [][] matrix) {
  18.             ArrayList<Integer> list = new ArrayList<>();
  20.             if(matrix == null || (matrix.length <=0 && matrix[0].length == 0))
  21.                 return list;
  23.             int columns = matrix[0].length;
  24.             int rows = matrix.length;
  26.             int rowStart = 0;           //第一行
  27.             int rowEnd = rows-1;        //最后一行
  28.             int colStart = 0;           //第一列
  29.             int colEnd = columns -  1;  //最后一列
  31.             while(rowStart <= rowEnd && colStart <= colEnd){
  32.                 if(rowStart < rowEnd && colStart < colEnd){
  33.                     for(int i= colStart; i<= colEnd-1; i++){//左到右第一行
  34.                         list.add(matrix[rowStart][i]);
  35.                     }
  36.                     for(int i= rowStart; i<= rowEnd-1; i++){//上到下第一列
  37.                         list.add(matrix[i][colEnd]);
  38.                     }
  39.                     for(int i=colEnd; i >= colStart + 1; i--){//右到左第一行
  40.                         list.add(matrix[rowEnd][i]);
  41.                     }
  42.                      for(int i=rowEnd; i >= rowStart + 1; i--){//下到上第一列
  43.                         list.add(matrix[i][colStart]);
  44.                     }
  45.                 }else if(colStart < colEnd && rowStart == rowEnd){//剩下一个长大于宽的矩形
  46.                     for(int i= colStart; i<= colEnd; i++){
  47.                         list.add(matrix[rowStart][i]);
  48.                     }
  49.                 }else if(rowStart < rowEnd && colStart == colEnd){//剩下一个宽大于长的矩形
  50.                     for(int i = rowStart; i<= rowEnd; i++){
  51.                         list.add(matrix[i][colStart]);
  52.                     }
  53.                 }else{// 剩下一个值
  54.                     list.add(matrix[rowStart][colStart]);
  55.                 }
  56.                 rowStart ++;
  57.                 colStart ++;
  58.                 rowEnd --;
  59.                 colEnd --;
  60.             }
  61.             return list;
  63.         }
  64.     }

20.题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

  1.     import java.util.Stack;
  2.     public class Solution {
  4.         private Stack<Integer> minStack = new Stack();//存放最小的
  5.         private Stack<Integer> stack = new Stack();//存放添加的
  6.         public void push(int node) {
  7.             if(minStack.isEmpty() || node < minStack.peek())
  8.                 minStack.push(node);
  9.             stack.push(node);
  10.         }
  12.         public void pop() {
  13.             if(stack.isEmpty())
  14.                 return;
  15.             if(!minStack.isEmpty() && minStack.peek() == stack.peek()){
  16.                 minStack.pop();
  17.             }
  18.             stack.pop();
  19.         }
  21.         public int top() {
  22.             return stack.peek();
  23.         }
  25.         public int min() {
  26.             return minStack.peek();
  27.         }
  28.     }

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

  1.     import java.util.ArrayList;
  2.     import java.util.Stack;
  3.     public class Solution {
  4.         public boolean IsPopOrder(int [] pushA,int [] popA) {
  5.             Stack<Integer> stack = new Stack();
  6.             int index = 0;
  7.             for(int i=0; i<popA.length; i++){
  8.                 int num = popA[i];
  10.                 if(stack.isEmpty()){//栈为空时添加节点
  11.                     stack.push(pushA[index++]);
  12.                 }
  14.                 while(stack.peek()!= num && index < pushA.length){
  15.                     stack.push(pushA[index++]);
  16.                 }
  17.                 if(stack.peek()!=num && index >= pushA.length)//当栈顶元素不等于num且pushA元素已经都入栈
  18.                     return false;
  19.                 stack.pop();
  20.             }
  21.             return true;
  22.         }
  23.     }

22.题目描述:从上往下打印出二叉树的每个节点，同层节点从左至右打印。

  1.     /**
  2.     public class TreeNode {
  3.         int val = 0;
  4.         TreeNode left = null;
  5.         TreeNode right = null;
  7.         public TreeNode(int val) {
  8.             this.val = val;
  10.         }
  12.     }
  13.     */
  14.     public class Solution {
  16.         public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
  17.             ArrayList<Integer> list = new ArrayList();
  18.             LinkedList<TreeNode> queue = new LinkedList();
  19.             if(root == null)
  20.                 return list;
  21.             queue.offer(root);
  22.             while(!queue.isEmpty()){
  23.                 TreeNode node = queue.poll();
  24.                 list.add(node.val);
  25.                 if(node.left != null){
  26.                     queue.offer(node.left);
  27.                 }
  28.                 if(node.right != null){
  29.                     queue.offer(node.right);
  30.                 }
  31.             }
  32.             return list;
  33.         }
  34.     }

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

  1.     public class Solution {
  2.         public boolean VerifySquenceOfBST(int [] sequence) {
  3.             if(sequence == null || sequence.length <=0)
  4.                 return false;
  5.             return isPostBST(sequence, 0, sequence.length-1);
  7.         }
  8.         public boolean isPostBST(int[] array, int start, int end){
  9.               //根节点的值
  10.             int root = array[end];
  11.             //找到左子树是否满足后序遍历
  12.             int i=start;
  13.             for(; i<end; i++){
  14.                 if(array[i] > root){
  15.                     break;
  16.                 }
  17.             }
  18.             int j=i;
  19.             for(; j<end; j++){
  20.                 if(array[j] < root)
  21.                     return false;
  22.             }
  23.             boolean left = true;
  24.             //判断左子树是不是二叉搜索树
  25.             if(i > start){
  26.                left = isPostBST(array,start, start + i -1);
  27.             }
  28.             boolean right = true;
  29.             if(j < end){
  30.                 right = isPostBST(array, start+i, end-1);
  31.             }
  32.             return left && right;
  33.         }
  34.     }

24.题目描述:输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

  1.     import java.util.ArrayList;
  2.     /**
  3.     public class TreeNode {
  4.         int val = 0;
  5.         TreeNode left = null;
  6.         TreeNode right = null;
  8.         public TreeNode(int val) {
  9.             this.val = val;
  11.         }
  13.     }
  14.     */
  15.     public class Solution {
  16.         private ArrayList<ArrayList<Integer>> roads = new ArrayList();//存储所有路径
  17.         private ArrayList<Integer> road = new ArrayList();//存放当前路径
  18.         public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
  19.             if(root == null)
  20.                 return roads;
  21.             road.add(root.val);
  22.             if(root.left == null && root.right == null){//当到达叶节点时
  23.                 if(target == root.val)
  24.                     roads.add(new ArrayList<>(road));
  25.             }
  27.             if(root.left != null){//当左子树不为空
  28.                 FindPath(root.left, target-root.val);
  29.             }
  30.             if(root.right != null){//当右子树不为空
  31.                 FindPath(root.right, target-root.val);
  32.             }
  33.             road.remove(road.size()-1);
  34.             return roads;
  36.         }
  37.     }

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

  1.     /*
  2.     public class RandomListNode {
  3.         int label;
  4.         RandomListNode next = null;
  5.         RandomListNode random = null;
  7.         RandomListNode(int label) {
  8.             this.label = label;
  9.         }
  10.     }
  11.     */
  12.     public class Solution {
  13.          //分成三步1.复制每个节点放置在该节点的后面
  14.         //2.修改节点的random指针
  15.         //3.修改节点的next指针
  16.         public static RandomListNode Clone(RandomListNode pHead)
  17.         {
  18.             if(pHead == null)
  19.                 return null;
  20.             copy(pHead);
  21.             changeRandom(pHead);
  22.             return changeNext(pHead);
  24.         }
  25.         public static RandomListNode changeNext(RandomListNode pHead){//修改next指针
  26.             RandomListNode root = pHead;
  27.             RandomListNode head = pHead.next;
  28.             while(root != null){
  29.                 RandomListNode copy = root.next;
  30.                 root.next = copy.next;
  31.                 root = copy.next;
  32.                 if(root != null)
  33.                     copy.next = root.next;
  34.                 else
  35.                     copy.next = null;
  36.             }
  37.             return head;
  38.         }
  40.         public static void changeRandom(RandomListNode pHead){//修改随机指针
  41.             RandomListNode root = pHead;
  42.             while(root != null){
  43.                 if(root.random != null){
  44.                     root.next.random = root.random.next;
  45.                 }
  46.                 root = root.next.next;
  47.             }
  48.         }
  50.         public static void copy(RandomListNode pHead){//复制节点
  51.             RandomListNode root = pHead;
  52.             while(root != null){
  53.                 RandomListNode node = new RandomListNode(root.label);//复制节点
  54.                 node.next = root.next;
  55.                 node.random = root.random;
  56.                 root.next = node;//修改原节点吓一跳指针
  57.                 root = node.next;//root指向下一个节点  
  58.             }
  59.         }
  60.     }

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

  1.     /**
  2.     public class TreeNode {
  3.         int val = 0;
  4.         TreeNode left = null;
  5.         TreeNode right = null;
  7.         public TreeNode(int val) {
  8.             this.val = val;
  10.         }
  12.     }
  13.     */
  14.     public class Solution {
  15.         private TreeNode head = null;//记录链表起始节点
  16.         public TreeNode Convert(TreeNode pRootOfTree) {
  17.             if(pRootOfTree == null){
  18.                 return null;
  19.             }
  20.             if(pRootOfTree.left == null && pRootOfTree.right == null)
  21.                 return pRootOfTree;
  23.             if(head == null){//找到初始节点
  24.                 head = pRootOfTree;
  25.                 while(head.left != null){
  26.                     head = head.left;
  27.                 }
  28.             }
  30.             Convert(pRootOfTree.left);//左子树构成一个双向链表
  31.             Convert(pRootOfTree.right);//右子树构成一个双向链表
  33.             TreeNode leftLast = null;
  34.             if(pRootOfTree.left != null){//找到左子树最右边一个就节点
  35.                 leftLast = pRootOfTree.left;
  36.                 while(leftLast.right != null){
  37.                     leftLast = leftLast.right;
  38.                 }
  39.             }
  41.             TreeNode rightFirst = null;
  42.             if(pRootOfTree.right != null){//找到右子树最左边的一个点
  43.                 rightFirst = pRootOfTree.right;
  44.                 while(rightFirst.left != null){
  45.                     rightFirst = rightFirst.left;
  46.                 }
  47.             }
  48.             if(leftLast != null){//左子树最大的点不为空
  49.                 leftLast.right = pRootOfTree;
  50.                 pRootOfTree.left = leftLast;
  51.             }
  53.             if(rightFirst != null){//右子树最小的点不为空
  54.                 rightFirst.left = pRootOfTree;
  55.                 pRootOfTree.right = rightFirst;
  56.             }
  58.             return head;
  60.         }
  61.     }

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

  3. import java.util.*;
  5. public class Solution {
  6.     public static ArrayList<String> Permutation(String str) {
  7.         if(str == null)
  8.             return null;
  9.         ArrayList<String> list = new ArrayList<>();
  10.         char[] chars = str.toCharArray();
  11.         list = allSort(chars, 0, list);
  12.         Collections.sort(list);
  13.         return list;
  14.     }
  16.     public static ArrayList<String> allSort(char[] chars, int index, ArrayList<String> list){
  17.         if(index == chars.length-1){
  18.             list.add(String.valueOf(chars));
  19.             return list;
  20.         }
  21.         for(int i=index; i< chars.length; i++){
  22.             if(i != index && chars[i] == chars[index])//当要交换的值相同时
  23.                 continue;
  24.             exChangeChars(index, i, chars); //修改第一个与后面的位置
  25.             allSort(chars,index+1,list);
  26.             exChangeChars(index, i, chars);//修改成原来的数组
  27.         }
  29.         return list;
  30.     }
  31.     /**
  32.      * 交换两个字符数组的位置
  33.      * @param index1
  34.      * @param index2
  35.      * @param chars
  36.      */
  37.     public static void exChangeChars(int index1, int index2, char[] chars){
  38.         char tmp =chars[index1];
  39.         chars[index1] = chars[index2];
  40.         chars[index2] = tmp;
  41.     }
  42. }

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

  1.     public class Solution {
  2.         public int MoreThanHalfNum_Solution(int [] array) {
  3.             if(array == null || array.length == 0)
  4.                 return 0;
  6.             int num = 0;
  7.             int count = 0;
  9.             for(int i=0; i<array.length; i++){
  10.                 if(count == 0){
  11.                     num = array[i];
  12.                     count = 1;
  13.                 }else if(num == array[i]){
  14.                     count++;
  15.                 }else{
  16.                     count--;
  17.                 }
  18.             }
  19.             count = 0;
  20.             for(int i=0; i<array.length; i++){
  21.                 if(array[i] == num)
  22.                     count++;
  23.             }
  25.             if((count << 1) <= array.length){
  26.                 return 0;
  27.             }
  29.             return num;
  31.         }
  32.     }

29.题目描述:输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,

  1.     import java.util.*;
  2.     public class Solution {
  3.         public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
  4.             ArrayList<Integer> list = new ArrayList<>();
  5.             if(input == null || k <=0 || input.length < k)
  6.                 return list;
  7.             int start = 0;
  8.             int end = input.length -1;
  9.             int index = partition(input, start, end);
  11.             while(index != k-1){
  12.                 if(index > k-1){
  13.                     end = index-1;
  14.                     index = partition(input,start,end);
  15.                 }else{
  16.                     start = index + 1;
  17.                     index = partition(input,start,end);
  18.                 }
  19.             }
  21.             for(int i=0; i<k; i++)
  22.                 list.add(input[i]);
  23.             return list;
  25.         }
  28.         public static int partition(int[] array, int start, int end){
  29.             if(array == null || array.length <= 0 || start< 0 || end >= array.length)
  30.                 throw new RuntimeException("输入不正确");
  32.             int index = (int)(Math.random() *(end-start +1)) + start;//获取随机数
  33.             swap(array,index,start);
  35.             while(start < end){
  36.                 while(array[end] > array[start])
  37.                     end --;
  38.                 if(start < end){
  39.                     swap(array, start, end);
  40.                     start ++;
  41.                 }
  43.                 while(array[start] < array[end])
  44.                     start ++;
  45.                 if(start < end){
  46.                     swap(array,start, end);
  47.                     end--;
  48.                 }
  50.             }
  52.             return start;
  54.         }
  56.         public static void swap(int[] array, int index, int start){//交换数组位置
  57.             int tmp = array[index];
  58.             array[index] = array[start];
  59.             array[start] = tmp;
  60.         }
  61.     }

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

  1.     public class Solution {
  2.         public int FindGreatestSumOfSubArray(int[] array) {
  3.             if(array== null || array.length <=0)
  4.                 throw new RuntimeException("数组长度不正确");
  6.             int max = Integer.MIN_VALUE;
  7.             int curSum = Integer.MIN_VALUE;
  9.             for(int i=0; i<array.length; i++){
  10.                 if(curSum < 0)
  11.                     curSum = array[i];
  12.                 else 
  13.                     curSum = array[i] + curSum;
  15.                 if(curSum > max)
  16.                     max = curSum;
  17.             }
  18.             return max;
  19.         }
  20.     }

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

  1.     import java.util.*;
  2.     public class Solution {
  3.         public int NumberOf1Between1AndN_Solution(int n) {
  5.             if(n <= 0)
  6.                 return 0;
  8.             int high, low, cur, i = 1;
  9.             high = n;
  10.             int count = 0;
  11.             while(high != 0){
  12.                 high = n / (int)Math.pow(10, i);
  13.                 int tmp = n % (int)Math.pow(10,i);
  14.                 cur = tmp / (int)Math.pow(10,i-1);
  15.                 low = tmp % (int)Math.pow(10,i-1);
  16.                 if(cur > 1){
  17.                     count += (high+1) * (int)Math.pow(10, i-1);
  18.                 }else if(cur == 1){
  19.                     count += high * (int)Math.pow(10,i-1) + low +1;
  20.                 }else{
  21.                     count+= high * (int)Math.pow(10,i-1);
  22.                 }
  23.                 i++;
  24.             }
  25.             return count;
  26.         }
  27.     }

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

  1.     import java.util.ArrayList;
  2.     import java.util.*;
  3.     public class Solution {
  4.         public String PrintMinNumber(int [] numbers) {
  5.             ArrayList<String> list = new ArrayList<>();
  6.             for(int i=0; i<numbers.length; i++){
  7.                 list.add(Integer.toString(numbers[i]));
  8.             }
  9.             Collections.sort(list,new Comparator<String>(){
  10.                 public int compare(String o1, String o2){
  11.                     String s1 = o1 + o2;
  12.                     String s2 = o2 + o1;
  13.                     return s1.compareTo(s2);
  14.                 }
  15.             }
  16.            );
  17.             StringBuilder sb = new StringBuilder();
  18.             for(String s : list){
  19.                 sb.append(s);
  20.             }
  21.             return sb.toString();
  22.         }
  23.     }

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

  1.     import java.util.*;
  2.     public class Solution {
  3.         public int GetUglyNumber_Solution(int index) {
  4.             if(index <= 0){
  5.                 return 0;
  6.             }
  7.             List<Integer> list = new ArrayList();
  8.             list.add(1);
  9.             int num1, num2, num3;
  10.             int index1=0,index2=0,index3=0;
  11.             while(list.size() < index){
  13.                 num1 = list.get(index1) * 2;
  14.                 num2 = list.get(index2) * 3;
  15.                 num3 = list.get(index3) * 5;
  17.                 int min = Math.min(num1, Math.min(num2,num3));
  19.                 list.add(min);
  21.                 if(min == num1)
  22.                     index1 ++;
  23.                 if(min == num2)
  24.                     index2 ++;
  25.                 if(min == num3)
  26.                     index3 ++;
  27.             }
  29.             return list.get(index-1);
  30.         }
  31.     }

34.题目描述:在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置。如果字符串为空,返回-1

  1.     import java.util.*;
  2.     public class Solution {
  3.         public int FirstNotRepeatingChar(String str) {
  5.             char[] chars = str.toCharArray();//转换成字符数组
  6.             LinkedHashMap<Character,Integer> map = new LinkedHashMap<>();
  7.             for(int i=0; i<chars.length; i++){
  8.                 if(map.containsKey(chars[i])){
  9.                     int value = map.get(chars[i]);
  10.                     map.put(chars[i],value+1);
  11.                 }else{
  12.                     map.put(chars[i],1);
  13.                 }
  14.             }
  16.             for(int i=0; i<chars.length; i++){
  17.                 if(map.get(chars[i]) == 1)
  18.                     return i;
  19.             }
  20.             return -1;
  22.         }
  23.     }

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

  1.     public class Solution {
  2.         private int count = 0;
  3.         private int[] copy;
  4.         public int InversePairs(int [] array) {
  5.             if(array == null || array.length == 0)
  6.                 return 0;
  7.             copy = new int[array.length];
  8.             sort(array, 0, array.length-1);
  9.             return count;
  10.         }
  12.         public void sort(int[] array, int start, int end){
  13.             if(start >= end)
  14.                 return;
  16.             int mid = (start + end) / 2;
  17.             sort(array, start, mid);
  18.             sort(array,mid+1, end);
  19.             merger(array, start, mid, end);
  20.         }
  22.         public void merger(int[] array, int start, int mid, int end){
  24.             int i = start, j = mid+1;
  25.             for(int k=i; k <= end; k++){
  26.                 copy[k] = array[k]; //复制需要合并的数组
  27.             }
  29.             for(int k = start; k <= end; k++){
  30.                 if(i > mid) array[k] = copy[j++]; //最半边取尽
  31.                 else if(j > end) array[k] = copy[i++]; //右半边取尽
  32.                 else if(copy[i] <= copy[j]) array[k] = copy[i++]; //左边小于等于右边
  33.                 else {
  34.                     array[k] = copy[j++];
  35.                     count = (count + mid - i+1) % 1000000007;
  36.                 }
  37.             }
  38.         }
  39.     }

36.题目描述:输入两个链表，找出它们的第一个公共结点。

  1.     /*
  2.     public class ListNode {
  3.         int val;
  4.         ListNode next = null;
  6.         ListNode(int val) {
  7.             this.val = val;
  8.         }
  9.     }*/
  10.     public class Solution {
  11.         public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
  13.             if(pHead1 == null || pHead2 == null)
  14.                 return null;
  16.             int length1 = getLength(pHead1);
  17.             int length2 = getLength(pHead2);
  19.             int lengthDif = length1 - length2;
  21.             ListNode longNode = pHead1; 
  22.             ListNode shortNode = pHead2;
  23.             if(length2 > length1){
  24.                 lengthDif = length2 - length1;
  25.                 longNode = pHead2;
  26.                 shortNode = pHead1;
  27.             }
  29.             for(int i=0; i<lengthDif; i++){//长链表后移lengthDif位
  30.                 longNode = longNode.next;
  31.             }
  33.             while(longNode != null && shortNode != null && longNode != shortNode){
  34.                 longNode = longNode.next;
  35.                 shortNode = shortNode.next;
  36.             }
  37.             return longNode;
  38.         }
  40.         public int getLength(ListNode head){//获取链表长度
  41.             int length = 0;
  42.             ListNode pNode = head;
  43.             while(pNode != null){
  44.                 length ++;
  45.                 pNode = pNode.next;
  46.             }
  47.             return length;
  48.         }
  49.     }

37.题目描述:统计一个数字在排序数组中出现的次数。

  1.     public class Solution {
  2.            public int GetNumberOfK(int [] array , int k) {
  3.             if(array == null || array.length == 0)
  4.                 return 0;
  6.             int left = getLeftIndex(array,k);
  7.             int right = getRightIndex(array, k);
  9.             if(left == -1 || right == -1)
  10.                 return 0;
  12.             return right - left +1;
  13.         }
  15.         public int getLeftIndex(int[] array, int k){//获取左边第一个k下标
  16.             int low = 0, mid = 0, high = array.length-1;
  18.             while(low <= high){
  19.                 mid = (low + high) / 2;
  20.                 if(array[mid] > k){
  21.                     high = mid - 1;
  22.                 }else if(array[mid] < k){
  23.                     low = mid +1;
  24.                 }else{
  25.                     if(mid > 0 && array[mid-1] == k){
  26.                         high = mid-1;
  27.                     }else{
  28.                         return mid;
  29.                     }
  30.                 }
  31.             }
  32.             return -1;
  33.         }
  35.         public int getRightIndex(int[] array, int k){//获取左边第一个k下标
  36.             int low = 0, mid=0, high = array.length-1;
  37.             while(low <= high){
  38.                 mid = (low+high) / 2;
  39.                 if(array[mid] > k){
  40.                     high = mid -1;
  41.                 }else if(array[mid] < k){
  42.                     low = mid +1;
  43.                 }else{
  44.                     if(mid < array.length-1 && array[mid+1] == k){
  45.                         low = mid+1;
  46.                     }else{
  47.                         return mid;
  48.                     }
  49.                 }
  50.             }
  51.             return -1;
  52.         }
  54.     }

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

  1.     /**
  2.     public class TreeNode {
  3.         int val = 0;
  4.         TreeNode left = null;
  5.         TreeNode right = null;
  7.         public TreeNode(int val) {
  8.             this.val = val;
  10.         }
  12.     }
  13.     */
  14.     public class Solution {
  15.         public int TreeDepth(TreeNode root) {
  16.             if(root == null)
  17.                 return 0;
  18.             int left = TreeDepth(root.left);
  19.             int right = TreeDepth(root.right);
  21.             return left > right ? (left + 1) : (right + 1);
  22.         }
  23.     }

39.题目描述:输入一棵二叉树，判断该二叉树是否是平衡二叉树。

  1.     public class Solution {
  2.         boolean isBalanced = true;
  3.         public boolean IsBalanced_Solution(TreeNode root) {
  5.             getDeep(root);
  6.             return isBalanced;
  7.         }
  9.         public int getDeep(TreeNode root){
  10.             if(root == null)
  11.                 return 0;
  13.             int left = getDeep(root.left);
  14.             int right = getDeep(root.right);
  16.             if(left - right > 1 || left - right < -1){
  17.                 isBalanced = false;
  18.             }
  20.             return left > right ? left + 1 : right + 1;
  21.         }
  22.     }

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

  1.     //num1,num2分别为长度为1的数组。传出参数
  2.     //将num1[0],num2[0]设置为返回结果
  3.     public class Solution {
  4.         public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
  5.             if(array.length == 2){
  6.                 num1[0] = array[0];
  7.                 num2[1] = array[1];
  8.             }
  10.             int result = 0;
  11.             for(int i=0; i<array.length; i++){
  12.                 result ^= array[i];
  13.             }
  14.             int index = findFirstBitIs1(result);
  15.             num1[0] = 0;
  16.             num2[0] = 0;
  18.             for(int i=0; i<array.length; i++){
  19.                 if(isBit1(array[i], index)){
  20.                     num1[0] ^= array[i];
  21.                 }else{
  22.                     num2[0] ^= array[i];
  23.                 }
  24.             }
  26.         }
  28.         public boolean isBit1(int num, int indexBit){
  29.             num = num >> indexBit;
  30.             return (num & 1) == 1;
  31.         }
  33.         public int findFirstBitIs1(int num){//求两个出现一次数字的下标
  34.             int index = 0;
  36.             while((num & 1) == 0){
  37.                 num = num >> 1;
  38.                 ++index;
  39.             }
  40.             return index;
  41.         }
  42.     }

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

  1.     import java.util.ArrayList;
  2.     public class Solution {
  3.         public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
  4.            ArrayList<ArrayList<Integer>> list = new ArrayList<>();
  5.            if(sum < 3)
  6.                return list;
  8.            int small = 1;
  9.            int big = 2;
  10.            int mid = (sum + 1) / 2;
  11.            int curSum = big + small;
  13.            while(small < mid){
  15.                if(curSum == sum){
  16.                    list.add(countinueSequence(small, big));
  17.                    curSum -= small;
  18.                    ++ small;
  19.                }else if(curSum < sum){
  20.                    ++big;
  21.                    curSum += big;
  22.                }else{ 
  23.                    curSum -= small;
  24.                     ++small;
  25.                }
  26.            }
  27.            return list;
  28.         }
  30.         public ArrayList<Integer> countinueSequence(int small, int big){
  31.             ArrayList<Integer> list = new ArrayList<>();
  32.             for(int i=small; i<= big; i++){
  33.                 list.add(i);
  34.             }
  35.             return list;
  36.         }
  37.     }

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

  1.     import java.util.ArrayList;
  2.     public class Solution {
  3.         public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
  5.             int first = 0, last = array.length-1;
  7.             int mulSum = Integer.MAX_VALUE;
  8.             ArrayList<Integer> list = new ArrayList<>();
  9.             while(first < last){
  10.                 int numFirst = array[first];
  11.                 int numLast = array[last];
  13.                 if(numFirst + numLast < sum)
  14.                     ++first;
  15.                 else if(numFirst + numLast > sum)
  16.                     --last;
  17.                 else{
  18.                     if(numFirst * numLast < mulSum){
  19.                         mulSum = numFirst *  numLast;
  20.                         list.clear();
  21.                         list.add(numFirst);
  22.                         list.add(numLast);
  23.                     }
  24.                     ++first;
  25.                 }
  26.             }
  27.             return list;
  28.         }
  29.     }

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

  1.     public class Solution {
  2.         public String LeftRotateString(String str,int n) {
  3.             if(str == null || str.length() == 0){
  4.                 return "";
  5.             }
  7.             char[] chars = str.toCharArray();
  8.             int length = chars.length;
  9.             reverse(chars, 0, length-1);
  11.             n = n % length;
  13.             reverse(chars, 0, length - n -1);
  14.             reverse(chars, length -n, length-1);
  16.             return new String(chars);
  17.         }
  19.         public void reverse(char[] chars, int start, int end){//翻转
  20.             while(start < end){
  21.                 char tmp = chars[start];
  22.                 chars[start] = chars[end];
  23.                 chars[end] = tmp;
  24.                 ++ start;
  25.                 --end;
  26.             }
  27.         }
  28.     }

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

  1.     public class Solution {
  2.         public String ReverseSentence(String str) {
  4.             if(str == null || str.length() == 1)
  5.                 return str;
  7.             char[] chars = str.toCharArray();
  8.             reverse(chars, 0, str.length()-1);
  10.             int start = 0;
  11.             for(int i=0; i<chars.length; ++i){
  12.                 if(chars[i] == ' '){
  13.                     reverse(chars, start, i-1);
  14.                     start = i + 1;
  15.                 }else if(i == chars.length-1){
  16.                     reverse(chars, start, i);
  17.                 }
  18.             }
  19.             return String.valueOf(chars);
  20.         }
  22.         public void reverse(char[] chars, int start, int end){//翻转
  23.             while(start < end){
  24.                 char tmp = chars[start];
  25.                 chars[start] = chars[end];
  26.                 chars[end] = tmp;
  27.                 ++ start;
  28.                 --end;
  29.             }
  30.         }
  31.     }

45.题目描述: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的运气如何。为了方便起见,你可以认为大小王是0。

  1.     import java.util.*;
  2.     public class Solution {
  3.         public boolean isContinuous(int [] numbers) {
  5.             if(numbers == null || numbers.length < 1)
  6.                 return false;
  8.             Arrays.sort(numbers);
  10.             int numberZero = 0;
  11.             int numberGap = 0;
  13.             for(int i=0; i<numbers.length && numbers[i] == 0; i++){
  14.                ++numberZero ;
  15.             }
  17.             int small = numberZero;
  18.             int big = small + 1;
  20.             while(big < numbers.length){
  21.                 if(numbers[small] == numbers[big])//对子
  22.                     return false;
  24.                 numberGap += numbers[big] - numbers[small] - 1;
  25.                 small = big;
  26.                 ++big;
  27.             }
  29.             if(numberGap <= numberZero)
  30.                 return true;
  31.             return false;
  32.         }
  33.     }

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

  1.     public class Solution {
  2.         public int LastRemaining_Solution(int n, int m) {
  3.             if(n < 1 || m < 1)
  4.                 return -1;
  5.             int last = 0;
  6.             for(int i=2; i<=n; i++){
  7.                 last = (last + m) % i;
  8.             }
  9.             return last;
  10.         }
  11.     }

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

  1.     public class Solution {
  2.         public int Sum_Solution(int n) {
  3.             int sum = n;
  4.             boolean bool = (sum>0)  && (sum += Sum_Solution(n-1))>0;
  5.             return sum;
  6.         }
  7.     }

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

  1.     public class Solution {
  2.         public int Add(int num1,int num2) {
  4.             int sum = num1 ^ num2;
  5.             int carry = (num1 & num2) << 1;
  7.             sum += carry;
  8.             return sum;
  9.         }
  10.     }

49.题目描述:将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

  1.     public class Solution {
  2.         public int StrToInt(String str) {
  4.             if(str == null)
  5.                 return 0;
  6.             boolean negative = false;//判断符号
  7.             int result = 0;
  8.             int i =0, len = str.length();
  10.             if(len > 0){
  11.                 char firstChar = str.charAt(0);
  12.                 if(firstChar < '0'){
  13.                     if(firstChar == '-'){
  14.                         negative = true;
  15.                     }else if(firstChar != '+')
  16.                         return 0;
  18.                     if(len == 1)
  19.                         return 0;
  20.                     i++;
  21.                 }
  23.                 while(i < len){
  24.                     char c = str.charAt(i++);
  25.                     if(c < '0' || c > '9')
  26.                         return 0;
  27.                     if((negative && -result < Integer.MIN_VALUE) || (!negative && result > Integer.MAX_VALUE))
  28.                         return 0;
  29.                     result  = result * 10 + (c - '0');
  31.                 }
  32.             }else{
  33.                 return 0;
  34.             }
  35.             return negative ? -result : result;
  36.         }
  37.     }

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

  1.     public class Solution {
  2.         // Parameters:
  3.         //    numbers:     an array of integers
  4.         //    length:      the length of array numbers
  5.         //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
  6.         //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
  7.         //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
  8.         // Return value:       true if the input is valid, and there are some duplications in the array number
  9.         //                     otherwise false
  10.         public boolean duplicate(int numbers[],int length,int [] duplication) {
  12.             if(numbers == null || numbers.length < 1)
  13.                 return false;
  15.             for(int i=0; i<numbers.length; ++i){
  16.                 if(numbers[i] < 0 || numbers[i] > length-1)
  17.                     return false;
  18.             }
  20.             for(int i=0; i< length; ++i){
  22.                 while(numbers[i] != i){
  23.                     if(numbers[i] == numbers[numbers[i]]){
  24.                         duplication[0] = numbers[i];
  25.                         return true;
  26.                     }
  27.                     int temp = numbers[i];
  28.                     numbers[i] = numbers[temp];
  29.                     numbers[temp] = temp;
  31.                 }
  32.             }
  33.             return false;
  34.         }
  35.     }

51.题目描述:给定一个数组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]。不能使用除法。

  1.     import java.util.ArrayList;
  2.     public class Solution {
  3.         public int[] multiply(int[] A) {
  4.             if(A == null || A.length < 1){
  5.                 return null;
  6.             }
  8.             int[] array1 = new int[A.length];//保存前半部分矩阵
  9.             array1[0] = 1;
  10.             for(int i=1; i< A.length; i++){
  11.                 array1[i] = array1[i-1] * A[i-1];
  12.             }
  14.             int[] array2 = new int[A.length];
  15.             array2[A.length-1] = array1[A.length-1]; // 设置最后一个值
  17.             int temp = 1;
  18.             for(int i=A.length-2; i>=0; i--){
  19.                 temp *= A[i+1];
  20.                 array2[i] = temp * array1[i];
  21.             }
  22.             return array2;
  23.         }
  24.     }

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

  1.     public class Solution {
  2.           public boolean match(char[] str, char[] pattern) {
  4.             if(str == null || pattern == null)
  5.                 return false;
  6.             int strIndex = 0;
  7.             int patternIndex = 0;
  8.             return  isMatchCode(str,pattern,strIndex, patternIndex);
  9.         }
  11.         /**
  13.          当模式中的第二个字符不是“*”时：
  14.          1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
  15.          2、如果
  16.          字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
  18.          而当模式中的第二个字符是“*”时：
  19.          如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
  20.          1、模式后移2字符，相当于x*被忽略；
  21.          2、字符串后移1字符，模式后移2字符；
  22.          3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；
  23.      */
  25.         public boolean isMatchCode(char[] str, char[] pattern, int strIndex, int patIndex){
  27.             if(strIndex == str.length && patIndex == pattern.length)
  28.                 return true;
  30.             if(strIndex != str.length && patIndex == pattern.length)
  31.                 return false;
  33.             if(patIndex+1<pattern.length && pattern[patIndex+1] == '*'){
  34.                 if(strIndex != str.length &&(pattern[patIndex] ==str[strIndex] || pattern[patIndex] == '.')){
  36.                     return isMatchCode(str,pattern,strIndex, patIndex+2)  || isMatchCode(str,pattern,strIndex+1,patIndex+1)|| isMatchCode(str,pattern, strIndex+1, patIndex);
  37.                 }else {
  38.                     return isMatchCode(str, pattern, strIndex, patIndex+2);
  39.                 }
  40.             }
  42.             if(strIndex != str.length && (pattern[patIndex] == str[strIndex] || pattern[patIndex] == '.')){
  43.                 return isMatchCode(str,pattern, strIndex+1, patIndex+1);
  44.             }
  45.             return false;
  46.         }
  47.     }

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

  1.     public class Solution {
  2.         public boolean isNumeric(char[] str) {
  3.             String s = String.valueOf(str);
  4.             // * 匹配前一个字符0次或多次
  5.             // ? 匹配前面的0次或者1次
  6.             // . 配除换行符 \n 之外的任何单字符。要匹配 . ，请使用 \.
  7.             // + 匹配前面字符1次或多次
  8.             return s.matches("[\\+-]?[0-9]*(\\.[0-9]+)?([eE][\\+-]?[0-9]+)?");
  9.         }
  10.     }

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

  1.     import java.util.*;
  2.     public class Solution {
  3.         //Insert one char from stringstream
  4.         private LinkedHashMap<Character,Integer> map = new LinkedHashMap<>();
  5.         public void Insert(char ch)
  6.         {
  7.             if(map.containsKey(ch)){
  8.                 int value = map.get(ch);
  9.                 map.put(ch, value+1);
  10.             }else{
  11.                 map.put(ch, 1);
  12.             }
  13.         }
  14.       //return the first appearence once char in current stringstream
  15.         public char FirstAppearingOnce()
  16.         {
  17.             for(Map.Entry<Character,Integer> entry : map.entrySet()){
  18.                 if(entry.getValue() == 1)
  19.                     return entry.getKey();
  20.             }
  21.             return '#';
  22.         }
  23.     }

55.题目描述：一个链表中包含环，请找出该链表的环的入口结点。

  1.     /*
  2.      public class ListNode {
  3.         int val;
  4.         ListNode next = null;
  6.         ListNode(int val) {
  7.             this.val = val;
  8.         }
  9.     }
  10.     */
  11.     public class Solution {
  13.         public ListNode EntryNodeOfLoop(ListNode pHead)
  14.         {
  15.             if(pHead == null)
  16.                 return null;
  17.             ListNode p1 = pHead;
  18.             ListNode p2 = pHead;
  19.             while(p1 != null && p2.next != null){
  20.                 p1 = p1.next;
  21.                 p2 = p2.next.next;
  22.                 if(p1 == p2){
  23.                     p1 = pHead;
  24.                     while(p1 != p2){
  25.                         p1 = p1.next;
  26.                         p2 = p2.next;
  27.                     }
  28.                     return p1;
  29.                 }
  30.             }
  31.             return null;
  32.         }
  33.     }

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

  1.     /*
  2.      public class ListNode {
  3.         int val;
  4.         ListNode next = null;
  6.         ListNode(int val) {
  7.             this.val = val;
  8.         }
  9.     }
  10.     */
  11.     public class Solution {
  12.       public static ListNode deleteDuplication(ListNode pHead) {
  14.            if(pHead == null)
  15.                 return null;
  17.             ListNode head = new ListNode(-1);
  18.             head.next = pHead;
  19.             ListNode preNode = head;
  20.             ListNode pNode = head.next;
  21.             while(pNode != null && pNode.next != null){
  22.                 if(pNode.val == pNode.next.val){
  23.                     int value = pNode.val;
  24.                     while(pNode != null && pNode.val == value)
  25.                         pNode = pNode.next;
  26.                     preNode.next = pNode;
  27.                 }else{
  28.                     preNode = pNode;
  29.                     pNode = pNode.next;
  30.                 }
  31.             }
  32.             return head.next;
  33.         }
  34.     }

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

  1.     /*
  2.     public class TreeLinkNode {
  3.         int val;
  4.         TreeLinkNode left = null;
  5.         TreeLinkNode right = null;
  6.         TreeLinkNode next = null;
  8.         TreeLinkNode(int val) {
  9.             this.val = val;
  10.         }
  11.     }
  12.     */
  13.     public class Solution {
  14.         public TreeLinkNode GetNext(TreeLinkNode pNode)
  15.         {
  16.             if(pNode == null)
  17.                 return null;
  19.             if(pNode.right != null){
  20.                 pNode = pNode.right;
  21.                 while(pNode.left != null)
  22.                     pNode = pNode.left;
  23.                 return pNode;
  24.             }else{
  25.                 TreeLinkNode node = pNode.next;
  26.                 while(node != null && node.right == pNode){
  27.                     pNode = node;
  28.                     node = node.next;
  29.                 }
  30.                 return node;
  31.             }
  33.         }
  34.     }

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

  1.     /*
  2.     public class TreeNode {
  3.         int val = 0;
  4.         TreeNode left = null;
  5.         TreeNode right = null;
  7.         public TreeNode(int val) {
  8.             this.val = val;
  10.         }
  12.     }
  13.     */
  14.     public class Solution {
  15.         boolean isSymmetrical(TreeNode pRoot)
  16.         {
  17.             return isSymmetrical(pRoot, pRoot);
  18.         }
  20.         boolean isSymmetrical(TreeNode root1, TreeNode root2){
  21.             if(root1 == null && root2 == null)
  22.                 return true;
  24.             if(root1 == null || root2 == null)
  25.                 return false;
  27.             if(root1.val != root2.val)
  28.                 return false;
  30.             return isSymmetrical(root1.left,root2.right) && isSymmetrical(root1.right, root2.left);
  31.         }
  32.     }

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

  1.     import java.util.ArrayList;
  2.     import java.util.*;
  3.     /*
  4.     public class TreeNode {
  5.         int val = 0;
  6.         TreeNode left = null;
  7.         TreeNode right = null;
  9.         public TreeNode(int val) {
  10.             this.val = val;
  12.         }
  14.     }
  15.     */
  16.     public class Solution {
  17.         public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
  19.             ArrayList<ArrayList<Integer>> list = new ArrayList<>();
  20.             if(pRoot == null)
  21.                 return list;
  23.             LinkedList<TreeNode> stack1 = new LinkedList<>();
  24.             LinkedList<TreeNode> stack2 = new LinkedList<>();
  26.             stack1.push(pRoot);
  27.             int index = 1;
  29.             while(!stack1.isEmpty() || !stack2.isEmpty()){
  30.                 ArrayList<Integer> arrayList = new ArrayList<>();
  31.                 if(index == 1){
  32.                     while(!stack1.isEmpty()){
  33.                         TreeNode node = stack1.pop();
  34.                         if(node.left != null){
  35.                             stack2.push(node.left);
  36.                         }
  37.                         if(node.right != null){
  38.                             stack2.push(node.right);
  39.                         }
  40.                         arrayList.add(node.val);
  41.                     }
  42.                     index = 2;
  43.                 }else{
  44.                     while(!stack2.isEmpty()){
  45.                         TreeNode node = stack2.pop();
  46.                         if(node.right != null){
  47.                             stack1.push(node.right);
  48.                         }
  49.                         if(node.left != null){
  50.                             stack1.push(node.left);
  51.                         }
  52.                         arrayList.add(node.val);
  53.                     }
  54.                     index = 1;
  55.                 }
  56.                 if(arrayList.size()>0)
  57.                     list.add(arrayList);
  58.             }
  59.             return list;
  61.         }
  62.     }

60.题目描述:从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

  1.     import java.util.ArrayList;
  2.     import java.util.*;
  4.     /*
  5.     public class TreeNode {
  6.         int val = 0;
  7.         TreeNode left = null;
  8.         TreeNode right = null;
  10.         public TreeNode(int val) {
  11.             this.val = val;
  13.         }
  15.     }
  16.     */
  17.     public class Solution {
  18.         ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
  20.             ArrayList<ArrayList<Integer>> list = new ArrayList<>();
  21.             if(pRoot == null)
  22.                 return list;
  24.             LinkedList<TreeNode> queue = new LinkedList<>();
  25.             queue.offer(pRoot);
  27.             while(!queue.isEmpty()){
  28.                 int num = queue.size();
  29.                 ArrayList<Integer> array = new ArrayList<>();
  30.                 while(num > 0){
  31.                     TreeNode node = queue.poll();
  32.                     if(node.left != null)
  33.                         queue.offer(node.left);
  34.                     if(node.right != null)
  35.                         queue.offer(node.right);
  37.                     array.add(node.val);
  38.                     -- num;
  39.                 }
  40.                 if(array.size() > 0){
  41.                     list.add(array);
  42.                 }
  43.             }
  45.             return list;
  46.         }
  48.     }

61.题目描述:请实现两个函数，分别用来序列化和反序列化二叉树

  1.     /*
  2.     public class TreeNode {
  3.         int val = 0;
  4.         TreeNode left = null;
  5.         TreeNode right = null;
  7.         public TreeNode(int val) {
  8.             this.val = val;
  10.         }
  12.     }
  13.     */
  14.     public class Solution {
  15.         int index = 0;
  16.         String Serialize(TreeNode root) {
  17.             if(root == null)
  18.                 return "#,";
  19.             String res = root.val +",";
  20.             res += Serialize(root.left);
  21.             res += Serialize(root.right);
  22.             return res;
  23.       }
  24.         TreeNode Deserialize(String str) {
  25.            String[] s = str.split(",");
  26.            return Deserialize(s);
  27.       }
  28.         TreeNode Deserialize(String[] s){
  29.             if(s[index].equals("#")){
  30.                 ++index;
  31.                 return null;
  32.             }
  34.             TreeNode root = new TreeNode(Integer.parseInt(s[index++])); 
  35.             root.left = Deserialize(s);
  36.             root.right = Deserialize(s);
  37.             return root;
  38.         }
  39.     }

62.题目描述:给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

  1.     /*
  2.     public class TreeNode {
  3.         int val = 0;
  4.         TreeNode left = null;
  5.         TreeNode right = null;
  7.         public TreeNode(int val) {
  8.             this.val = val;
  10.         }
  12.     }
  13.     */
  14.     public class Solution {
  15.         int index = 0;
  16.         TreeNode KthNode(TreeNode pRoot, int k)
  17.         {
  18.             if(pRoot != null){
  19.                 TreeNode node = KthNode(pRoot.left,k);//找到中序第一个节点
  21.                 if(node != null)
  22.                     return node;
  23.                 ++index;
  24.                 if(index == k )
  25.                     return pRoot;
  27.                 node = KthNode(pRoot.right,k);
  28.                 if(node != null)
  29.                     return node;
  31.             }
  32.             return null;
  33.         }
  34.     }

63.题目描述:如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

  1.     import java.util.*;
  2.     public class Solution {
  3.         int count = 0;
  4.         private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  5.         private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(15,new Comparator<Integer>() {
  6.             @Override
  7.             public int compare(Integer o1, Integer o2) {
  8.                 return o2 - o1;
  9.             }
  10.         });
  12.         public void Insert(Integer num) {
  13.             if((count & 1) == 0){
  14.                 if(!maxHeap.isEmpty() && maxHeap.peek() > num) {
  15.                     maxHeap.offer(num);
  16.                     num = maxHeap.poll();
  17.                 }
  18.                 minHeap.offer(num);
  20.             }else {
  21.                 if(!minHeap.isEmpty() && minHeap.peek() < num){
  22.                     minHeap.offer(num);
  23.                     num = minHeap.poll();
  24.                 }
  25.                 maxHeap.offer(num);
  27.             }
  28.             ++count;
  29.         }
  31.         public Double GetMedian() {
  33.             if((count & 1) == 1)
  34.                 return Double.valueOf(minHeap.peek());
  35.             else 
  36.                 return Double.valueOf(minHeap.peek() + maxHeap.peek())/ 2;
  37.         }
  38.     }

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

  1.     import java.util.*;
  2.     public class Solution {
  3.      public static ArrayList<Integer> maxInWindows(int [] num, int size)
  4.         {
  5.             ArrayList<Integer> list = new ArrayList<>();
  6.             if(num == null ||size == 0 || num.length < size)
  7.                 return list;
  9.             LinkedList<Integer> queue = new LinkedList<>();
  10.             for(int i=0; i<num.length; i++){
  13.                 while(!queue.isEmpty()&& num[i] > num[queue.getLast()])
  14.                     queue.pollLast();
  16.                 queue.offerLast(i);
  18.                  if(i - queue.getFirst() >= size)
  19.                      queue.pollFirst();
  21.                 if(i >= size-1)
  22.                     list.add(num[queue.peek()]);
  23.             }
  24.             return list;
  25.         }
  26.     }

65.题目描述:请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如[a b c e s f c s a d e e]是3*4矩阵，其包含字符串"bcced"的路径，但是矩阵中不包含“abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

  1.     public class Solution {
  2.         public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
  3.         {
  4.             int[] flag = new int[matrix.length];
  5.             for(int i=0; i<rows; i++){
  6.                 for(int j=0; j<cols; j++){
  8.                     if(help(matrix,i,j, rows,cols,str,flag,0))
  9.                         return true;
  10.                 }
  11.             }
  13.             return false;
  14.         }
  16.         public boolean help(char[] matrix, int i, int j, int rows, int cols, char[] str, int[] flag, int k){
  17.             int index = i * cols + j;
  18.             if(i<0 || i>=rows || j<0 || j >= cols || flag[index] == 1 || str[k] != matrix[index])
  19.                 return false;
  20.             if(k == str.length-1)
  21.                 return true;
  23.             flag[index] = 1;
  24.             if(help(matrix,i-1,j,rows,cols,str,flag,k+1) || help(matrix,i+1,j,rows,cols,str,flag,k+1)
  25.                     || help(matrix,i,j-1,rows,cols,str,flag,k+1) ||help(matrix,i,j+1,rows,cols,str,flag,k+1))
  26.                 return true;
  27.             flag[index] = 0;
  28.             return false;
  29.         }
  30.     }

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

  1.     public class Solution {
  2.       public int movingCount(int threshold, int rows, int cols)
  3.         {
  4.             int[][] move = new int[rows][cols];
  5.             return moveing(threshold, 0, 0, rows, cols, move);
  6.         }
  8.         public int moveing(int threshold, int i, int j,int rows, int cols, int[][] move){
  9.             if(i < 0 || j <0 || i>=rows || j >= cols || !isCanMove(i,j, threshold) || move[i][j] == 1)
  10.                 return 0;
  11.             move[i][j] = 1;
  12.             return moveing(threshold, i+1, j, rows, cols, move)
  13.             +moveing(threshold, i-1, j, rows, cols, move)+
  14.             moveing(threshold, i, j-1, rows, cols, move)+
  15.             moveing(threshold, i, j+1, rows, cols, move)+1;
  16.         }
  18.         public boolean isCanMove(int rows, int cols, int threshold){
  19.             int sum = 0;
  20.             while(rows > 0){
  21.                 sum += rows % 10;
  22.                 rows = rows/ 10;
  23.             }
  24.             while(cols >0){
  25.                 sum += cols % 10;
  26.                 cols = cols /10;
  27.             }
  28.             if(sum <= threshold)
  29.                 return true;
  30.             return false;
  31.         }
  32.     }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注