• 剑指offer—java版
  • 01-二维数组中的查找
    • 思路
    • 实现
  • 02-替换空格
    • 思路
    • 实现
  • 03-从尾到头打印链表
    • 思路
    • 实现
  • 04-旋转数组的最小数字
    • 思路
    • 05-斐波那契数列
    • 06-青蛙跳
    • 07-变态青蛙跳
    • 08-矩阵覆盖
    • 09-二进制中1的个数
      • 思路
      • 实现
    • 10-数值的整数次方
    • 11-调整数组顺序奇数在偶数前面
    • 二叉搜索树的后序遍历序列
      • 实现
    • 复杂链表的复制
      • 思路
    • #
    • 二叉搜索树与双向链表
    • 字符串的排列

    剑指offer—java版

    代码格式按牛客网在线答题格式编写

    01-二维数组中的查找

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

    思路

    坑：不要从中间去，采用二分查找。如果中间查找会有两个区域需要查找，增加复杂度。
    真确思路：从右上角开始遍历，有三种情况:

    1. 如果相等，则直接返回。
    2. 如果值大于目标值，列减小。(因为从坐到右增大，因此右边的值不可能存在目标值)
    3. 如果值小于目标值，增大行。（从上往下增大，该值在最右上角为当前行最大，因此当前行没有更大的，可以往下一行找）

    思考，是否可以从左上角开始、右下角、左下角开始？
    左上角不可以，右下角不可以。因为这这两个移动后还是会形成两个区域需要查找。
    左下角可以。

    实现

    1. public boolean Find(int [][] array,int target) {
    2.     if (array == null || array[0].length == 0 ) {
    3.         return false;
    4.     }
    5.     int row = 0;
    6.     int col = array.length - 1;
    7.     while ( row < array.length && col >=0 ) {
    8.         if ( target > array[row][col]) {
    9.             row ++;
    10.         } else if (target < array[row][col]) {
    11.             col --;
    12.         } else {
    13.             return true;
    14.         }
    16.     }
    17.     return false;
    18. }

    02-替换空格

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

    思路

    1. 先计算空格数目
    2. 计算新的字符串长度，并构建新字符数组
    3. 逐个遍历和copy, 遇到空格用户“%20”替换

    实现

    1. public String replaceSpace(StringBuffer str) {
    2.     // 第一件重要的事
    3.     if( str == null || str.length() == 0)
    4.         return str.toString();
    5.     // 长度计算
    6.     int newlength = newLength(str);
    7.     char[] newChar = new char[newlength];
    8.     int idx = 0;
    9.     for (int i = 0; i < str.length(); i++) {
    10.         if (str.charAt(i) == ' ') {
    11.             newChar[idx++] = '%';
    12.             newChar[idx++] = '2';
    13.             newChar[idx++] = '0';
    14.         } else {
    15.             newChar[idx++] = str.charAt(i);
    16.         }
    17.     }
    18.     return new String(newChar);
    19. }
    20. private int newLength(StringBuffer str) {
    21.     int spaceNum = 0; 
    22.     for (int i = 0; i < str.length(); i ++) {
    23.         if (str.charAt(i) == ' ') {
    24.             spaceNum++;
    25.         }
    26.     }
    28.     // 或者  str.length() + spaceNum * 2
    29.     return (str.length() - spaceNum) + spaceNum * 3;
    30. }

    03-从尾到头打印链表

    输入一个链表，从尾到头打印链表每个节点的值。

    思路

    利用栈，先进后出的思路。

    实现

    1. public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    2.     ArrayList<Integer> result = new ArrayList<Integer>();
    3.     if (null == listNode) {
    4.         return result;
    5.     }
    7.     Stack<ListNode> stack = new Stack<ListNode>();
    8.     ListNode next = listNode;
    9.     while(null != next) {
    10.         stack.push(next);
    11.         next = next.next;
    12.     }
    13.     while(!stack.isEmpty()) {
    14.         result.add(stack.pop().val);
    15.     }
    16.     return result;
    17. }

    04-旋转数组的最小数字

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

    思路

    二分查找，不断缩短查找范围。

    1. mid值与左右两端比较，如果小于右边，high=mid.
    2. mid大于左边，low=mid
    3. 如果左值=mid值=右值，顺序遍历
    1. public int minNumberInRotateArray(int [] array) {
    2.     if ( array == null || array.length == 0 ) {
    3.         return 0;
    4.     }
    5.     int low = 0, high = array.length - 1;
    6.     int mid;
    7.     while ( low < high && array[low] >= array[high]) {
    8.         // array[low] 需要大于等于 array[high] 在内部进行 遍历
    9.         if ( (low +1 )== high) { //这个很关键，说明只有两个元素
    10.             return array[high];
    11.         }
    12.         if (array[low] == array[high]) {
    13.             int min = array[low];
    14.             for ( int i = low +1; i <= high; i++) {
    15.                 if(array[i] < min){
    16.                     min = array[i];
    17.                 }
    18.             }
    19.             return min;
    20.         } else {
    21.             mid = (low + high) >> 1;
    22.             if (array[mid] < array[high]){
    23.                 high = mid;
    24.             } else {
    25.                 low = mid;
    26.             }
    27.         }
    28.     }
    30.     // 只有一个元素 或者 array[low] < array[high]
    31.     return array[low];
    32. }

    05-斐波那契数列

    1. public int Fibonacci(int n) {
    2.     if(n <= 0) {
    3.         return 0;
    4.     }
    5.     if (n == 1 || n == 2) {
    6.         return 1;
    7.     }
    8.     int preOne = 1;
    9.     int preTwo = 1;
    10.     int temp;
    11.     for ( int i = 3; i <= n; i++ ){
    12.         temp = preOne;
    13.         preOne = preOne + preTwo;
    14.         preTwo = temp;
    15.     }
    16.     return preOne;
    17. }

    06-青蛙跳

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

    1. public int JumpFloor(int target) {
    2.     if(target <= 0) return 0;
    3.     if(target == 1) return 1;
    4.     if(target == 2) return 2;
    5.     int preOne = 2, preTwo = 1;
    6.     for(int i = 3; i <= target; i++){
    7.         int temp = preOne + preTwo;
    8.         preTwo = preOne;
    9.         preOne = temp;
    10.     }
    11.     return preOne;
    12. }

    07-变态青蛙跳

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

    1. public int JumpFloorII(int target) {
    2.     if(target <= 0) return 0;
    3.     int result = 1;
    4.     target --;
    5.     while(target !=0){
    6.         result = result << 1;
    7.         target --;
    8.     }
    9.     return result;
    10. }

    08-矩阵覆盖

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

    1.  public int RectCover(int target) {
    2.     if (target <= 0) return 0;
    3.     if(target == 1) return 1;
    4.     if(target == 2) return 2;
    5.     int preOne = 2, preTwo =1;
    6.     for(int i = 3; i <= target; i++){
    7.         int temp = preOne + preTwo;
    8.         preTwo = preOne;
    9.         preOne = temp;
    10.     }
    11.     return preOne;
    12. }

    09-二进制中1的个数

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

    思路

    如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
    举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

    实现

    1. public int NumberOf1(int n) {
    2.     int count = 0;
    3.     while(n!= 0){
    4.         count++;
    5.         n = n & (n - 1);
    6.      }
    7.     return count;
    8. }

    10-数值的整数次方

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

    1. public double Power(double base, int exponent) {
    2.     if (base == 0) {
    3.         return 0;
    4.     }
    5.     boolean flag = false; // 是否exponent是负数
    6.     if (exponent <= 0) {
    7.         exponent =  -1 * exponent;
    8.         flag = true;
    9.     }
    11.     double result = 1.0;
    12.     while (exponent > 0) {
    13.         result = result * base;
    14.         exponent--;
    15.     }
    17.     if (flag) {
    18.         return 1.0 / result; 
    19.     } else {
    20.         return result;
    21.     }
    22. }

    11-调整数组顺序奇数在偶数前面

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

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

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

    实现

    1. public boolean VerifySquenceOfBST(int [] sequence) {
    2.    if (sequence == null || sequence.length ==0) {
    3.        return false;
    4.    }
    5.     return verifySequenceOfBST(sequence, 0, sequence.length-1);
    7. }
    8. private boolean verifySequenceOfBST(int[] sequence,int begin,int end){
    9.    if (begin == end) {
    10.        return true;
    11.    }
    12.     int rightBegin = begin;
    13.     int root = sequence[end];
    14.     for (;rightBegin < end; rightBegin++ ) {
    15.         if (sequence[rightBegin] > root ) {
    16.             break;
    17.         }
    18.     }
    19.     int i = rightBegin;
    20.     for (; i < end; i ++ ) {
    21.         if (sequence[i] < root) {
    22.             return false;
    23.         }
    24.     }
    25.     boolean left = (rightBegin == begin )? true : verifySequenceOfBST(sequence, begin, rightBegin -1);
    26.     boolean right = (rightBegin == end) ? true : verifySequenceOfBST(sequence, rightBegin+1, end);
    27.     return left & right;
    29. }

    复杂链表的复制

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

    思路

    三步走:

    1. 在原来链中插入克隆节点，是的克隆节点和源节点相间出现。
    2. 复制random指针
    3. 从原链从剥离clone链。

    #

    1. public RandomListNode Clone(RandomListNode pHead)
    2. {
    3.     cloneNodes(pHead);
    4.     connectRandomNodes(pHead); 
    5.     return reconnectNodes(pHead);
    6. }
    7. private void cloneNodes(RandomListNode pHead){
    8.     RandomListNode node = pHead;
    9.     while(node != null){
    10.         RandomListNode clone = new RandomListNode(node.label);
    11.         RandomListNode temp = node.next;
    12.         clone.next = temp;
    13.         node.next = clone;
    14.         node = temp;           
    15.     }
    16. }
    17. private void connectRandomNodes(RandomListNode pHead){
    18.     RandomListNode node = pHead;
    19.     while(node != null){
    20.          RandomListNode clone = node.next;
    21.          if(node.random != null)//这里一定要判断
    22.             clone.random = node.random.next;
    23.          node = clone.next;
    24.     }
    25. }
    27. private  RandomListNode reconnectNodes(RandomListNode pHead){
    28.     RandomListNode node = pHead;
    29.     RandomListNode cloneHead = null;
    30.     RandomListNode cloneNode = null;
    31.     if(node != null){
    32.         cloneHead = cloneNode = node.next;
    33.         node.next = cloneNode.next;
    34.         node = node.next;
    35.     }
    36.     while(node != null){
    37.         cloneNode.next = node.next;
    38.         cloneNode = cloneNode.next;
    39.         node.next = cloneNode.next;
    40.         node = cloneNode.next;
    41.     }
    42.     return cloneHead;
    43. }

    二叉搜索树与双向链表

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

    1. public class Solution {
    2.     public TreeNode Convert(TreeNode root){
    3.         TreeNode lastNode = null;
    4.         lastNode = doConvert(root, lastNode);
    5.         while(lastNode != null && lastNode.left != null) {
    6.             lastNode = lastNode.left;
    7.         }
    8.        return lastNode;
    10.     }
    11.     /* 转换并返回链表最后一个结点
    12.      */
    13.     private TreeNode doConvert(TreeNode root, TreeNode lastNode){
    14.          if (root == null) {
    15.              return lastNode;
    16.          }
    17.          if (root.left != null) {
    18.              lastNode = doConvert(root.left, lastNode);
    19.          }
    20.          if(lastNode != null) {
    21.              lastNode.right = root;
    22.          }
    23.          root.left = lastNode;
    24.          lastNode = root;
    25.          if (root.right != null) {
    26.              lastNode = doConvert(root.right, lastNode);
    27.          }
    28.         return lastNode;
    29.     }
    30. }

    字符串的排列

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

    1. import java.util.ArrayList;
    2. import java.util.Collections;
    3. public class Solution {
    4.     public ArrayList<String> Permutation(String str) {
    5.        ArrayList<String> result = new ArrayList<String>();
    6.         if(str == null || str.length() == 0)
    7.             return result;
    8.         doPermutation(str.toCharArray(),0,result);
    9.         // 实际中不需要排序
    10.         Collections.sort(result);
    11.         return result;
    13.     }
    14.     private void doPermutation(char[] array,int idx,ArrayList<String> result){
    15.         if(idx >= array.length){
    16.             String str = new String(array);
    17.             result.add(str);
    18.             return;
    19.         }
    20.         for(int i=idx; i < array.length; i++){ //i得从 idx开始
    21.             if(i != idx && array[i] == array[idx] )
    22.                 continue;
    24.             swap(array,idx,i);
    25.             doPermutation(array,idx+1,result);
    26.             swap(array,idx,i);
    27.         }
    28.     }
    29.     private void swap(char[] array,int i,int j){
    30.         char temp = array[i];
    31.         array[i] = array[j];
    32.         array[j] = temp;
    33.     }
    35. }