剑指offer

1-10

1 二维数组中的查找

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

自己的解法

二维数组是有序的，横向来说当目标整数在第一个和第二个之间该行就有可能存在目标整数，这时就对这行做一个二分查找，找到了就返回，没找到continue。

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array[0].length == 0) return false;
        int n = array[0].length;
        for(int i = 0; i < array.length; i++){
            if(array[i][0] < target && array[i][n-1] < target){
                continue;
            }else{
                if(find2(target, array[i]))
                    return true;
            }
        }
        return false;
    }
    public boolean find2(int target, int [] a){
        int right = a.length;
        int left = 0;
        while(left <= right){
            int mid = left + (right-left)/2;
            if(target == a[mid])
                return true;
            if(target < a[mid])
                right = mid-1;
            if(target > a[mid])
                left = mid+1;

        }
        return false;

    }
}

评论区解法

@徘徊的路人: 从左下角开始, 对这个数来说往上数字递减, 往右数字递增, 从左下角开始查找, 当目标整数大于数组的数就上移, 小于就下移, 直到找到目标数组.

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array[0].length == 0) return false;
        int n = array.length-1;
        int m = array[0].length-1;
        int i = n, j = 0;
        while(i >= 0 && j <= m){
            if(array[i][j] == target)
                return true;
            if(array[i][j] < target){
                j++;
                continue;
            }
            if(array[i][j] > target)
                i--;
        }
        return false;
    }
}

2 替换空格

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

自己的解法

直接牺牲空间换时间了, 相当于新建了一个字符串不在原字符串上操作,很好理解.

public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            if (' '==str.charAt(i)){
                res.append("%20");
            }else{
                res.append(str.charAt(i));
            }
        }

        return res.toString();
    }
}

评论区解法

在原字符串上操作, 先从左到右遍历字符串, 得到共有多少个空格, 然后算出需要返回的字符串的长度. 更改原字符串长度, 从右往左遍历, 遇到空格就添加%20.

public class Solution {
    public String replaceSpace(StringBuffer str) {
        int count = 0;
        int length = str.length();
        for (int i = 0; i < length; i++) {
            if (' '==str.charAt(i))
                count++;
        }
        int newLength = length+count*2-1;
        str.setLength(newLength+1);
        for (int i = length-1; i >=0; i--){
            if(' '!=str.charAt(i)){
                str.setCharAt(newLength, str.charAt(i));
                newLength--;
            }else{
                str.setCharAt(newLength--, '0');
                str.setCharAt(newLength--, '2');
                str.setCharAt(newLength--, '%');
            }
        }

        return str.toString();
    }
}

这样做时间复杂度会稍微搞一些, 但是稍微节省一点空间.

3 从尾到头打印链表

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

自己的解法

直接用栈

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack <Integer> stack = new Stack <Integer>();
        while(listNode != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
         ArrayList <Integer> res = new ArrayList <Integer>();
         while(!stack.isEmpty()){
             res.add(stack.pop());
        }
        return res;
    }
}

评论区解法

评论区有用递归的, 但是递归本质还是使用堆栈.

public class Solution {
    ArrayList<Integer> arrayList=new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode!=null){
            this.printListFromTailToHead(listNode.next);
            arrayList.add(listNode.val);
        }
        return arrayList;
    }
}  

4 重建二叉树

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

自己的解法

二叉树一般就是递归了, 按照题目给的两个序列在纸上写一遍就能得出递归该怎么写参数了.

public class Solution {
    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        return a(pre, in, 0, pre.length - 1, 0, in.length - 1);
    }

    public static TreeNode a(int[] pre, int[] in, int leftPre, int rightPre, int leftIn, int rightIn) {
        if (rightIn < leftIn || rightPre < leftPre)
            return null;
        else {
            TreeNode res = new TreeNode(pre[leftPre]);
            int i = leftIn, count = 0;
            while (i <= rightIn) {
                if (in[i] == res.val)
                    break;
                i++;
                count++;
            }
            res.left = a(pre, in, leftPre + 1, leftPre + count, leftIn, leftIn+count-1);
            res.right = a(pre, in, leftPre+count+1, rightPre, leftIn+count+1, rightIn);

            return res;
        }
    }
}

5 两个栈实现队列

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

自己的解法

push全部往stack1里push, pop的话先把stack1的都add进stack2, 留下最后一个输出. 然后再把stack2里的add进stack1.

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    int flag = 1;
    public void push(int node) {
        stack1.add(node);
    }
    
    public int pop() {
        int s = stack1.size();
        for(int i = 0; i<s-1; i++){
            stack2.add(stack1.pop());
        }
        int res = stack1.pop();
        for(int i = 0; i < s-1;i++)
            stack1.add(stack2.pop());
        return res;
    }
}

评论区解法

在我自己的步骤中, 每次都要重新倒stack2里的进stack1, 实际上stack2里的已经是可以用的了, 再放进stack1是没有必要的, 只需要判断stack2里是否还有元素, 有的话就直接pop stack2, 没有的话再把stack1里的add进stack2.

6 旋转数组的最小数字

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

自己的解法

本质还是有序的序列, 这里要注意的是非递减的意思是a[i+1] >= a[i], 解法其实是二分查找的变形, 当a[mid] > a[right]的时候, 说明最小值在mid的右边或者就是mid, 否则最小值应该在mid的左边或者是mid.

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

评论区

上面自己的代码通过编译了, 但是看评论区指出了一个用例上的问题, 如果旋转数组是11101, 符合题目的条件, 但是最小值在右边我确判断到了左边, 原因是当a[mid] == a[right]的时候, 是判断不出在左边还是在右边的, 因此需要从右边一位一位的向左查找. 加上一个判断条件即可.

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

7 斐波那契数列

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

自己的解法

很简单的一题了, 可以用递归但是太占内存了, 用循环比较好.

public class Solution {
    public int Fibonacci(int n) {
        if(n == 0)
            return 0;
        int a = 0;
        int b = 1;
        for(int i = 2; i <= n; i++){
            b = a + b;
            a = b - a;
        }
        return b;
    }
}

8 跳台阶

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

自己的解法

当需要跳上n时, 因为只能跳1级或者2级, 实际上只能从n-1或者n-2级台阶上跳上来, 因此可以得出f(n)=f(n-1)+f(n-2), 就是上面的斐波那契数列了, 改一下就可以.

public class Solution {
    public int JumpFloor(int target) {
        if(target == 0)
            return 0;
        if(target == 1)
            return 1;
        int a = 1;
        int b = 2;
        for(int i = 2; i <= target-1; i++){
            b = a + b;
            a = b - a;
        }
        return b;
    }
}       

9 变态跳台阶

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

自己的解法

自己归纳了一下得出了f(n) = 2 * f(n-1)的结论, 但其实没有证明出来.

public class Solution {
    public int JumpFloorII(int target) {
        if (target == 0)
            return 0;
        int res = 1;
        while(--target != 0){
            res = res * 2;
        }
        return res;
    }
}

评论区

主要有两种证明法:

1. f(n) = f(n-1)+f(n-2)+...+f(1), f(n-1) = f(n-2)+f(n-3)+...+f(1), 带入进去就可以得出f(n) = 2f(n-1)了.
2. 因为可以任意的跳, 所以假设n个台阶状态1代表跳到那里, 0代表不跳到那里, 那么第n个台阶肯定是1, 其他n-1个台阶就有2^(n-1)种组合.

10 矩形覆盖

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

自己的解法

还是斐波那契数列, 当n=1时, 有0种方法, 当n=2时有两种, 当n=3时有三种. 继续往下, 假设第一个位置是竖着摆, 那么就有f(n-1)种摆法; 第一个位置横着摆, 就有f(n-2)种摆法.

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

11-20

11 二进制中1的个数

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

太菜了这题自己没有思路, 只想到了if else判断正负然后短除法慢慢的来. 看到评论区用位运算才想到, 然后自己用位运算实现了.

public class Solution {
    public int NumberOf1(int n) {
        int temp = 1;
        int res = 0;
        while(temp != 0){
            if((n & temp) != 0)
                res++;
            temp = temp << 1;
        }
        return res;
    }
}

评论区还看到了最高效的解法, 就直接用输入的数和自己对比, 判断是n&(n-1), n二进制的n-1之后, 右边第一个1就会变成0, 右边的0都会变成1, 再和n进行与运算, 这时n最右边的1就会变成0, 也就是1的数量减少了一个, 能进行多少次这样的运算, 就说明n有多少个1.

public class Solution {
    public int NumberOf1(int n) {
        int res = 0;
        while(n!= 0){
            res++;
            n = n & (n - 1);
         }
        return res;
    }
}

12 数值的整数次方

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

保证base和exponent不同时为0

自己的解法

用递归来减低复杂度

public class Solution {
    public double Power(double base, int exponent) {
        if (base == 0)
            return 0.0;
        if (exponent == 0)
            return 1.0;
        if (exponent < 0){
            base = 1 / base;
            exponent = - exponent;
        }
            
        if (exponent % 2 == 1)
            return base * Power(base * base, exponent/2);
        else
            return Power(base * base, exponent/2);
  }
}

评论区解法

https://blog.csdn.net/hkdgjqr/article/details/5381028

快速幂的算法, 看了一遍不理解, 有时间再看吧.

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

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

自己的解法

先找到一个偶数, 从这个偶数继续向右, 当遇到奇数时就把奇数前面的偶数向右移, 奇数填到第一个偶数的地方.

public class Solution {
    public void reOrderArray(int [] array) {
        int a = -1; // 偶
        int b;
        for(int i = 0; i < array.length; i++){
            if(a== -1 && (array[i] & 1) == 0){
                a = i;
            }
            if(a != -1 && (array[i] & 1) == 1){
                b = i;
                int t = array[b];
                while (b > a){
                    array[b] = array[b-1];
                    b--;
                }
                array[b] = t;
                a++;
            }
        }
    }
}

评论区解法

用的类似冒泡排序的方法

public class Solution {
    public void reOrderArray(int [] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = array.length - 1; j > i; j--) {
                if (array[j] % 2 == 1 && array[j - 1] % 2 == 0){
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                }
            }
        }
    }
}

14 链表中倒数第k个结点

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

自己的解法

快慢指针.

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

15 翻转链表

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

评论区解法

数据结构课实验明明写过, 又忘了, 要记住啊...

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null)
            return null;
        ListNode cur = null;
        ListNode next = null;
        while(head != null){
            next = head.next;
            head.next = cur;
            cur = head;
            head = next;
        }
        return cur;
    }
}

16 合并两个排序的链表

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

自己的解法

也是之前写过的, 链表操作看代码吧.

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode res = null;
        ListNode cur = null;
        while(list1!=null && list2!=null){
            if(list1.val <= list2.val){
                if(res == null){
                   res = cur = list1;
                }else{
                   cur.next = list1;
                   cur = cur.next;
                }
                list1 = list1.next;
            }else{
                if(res == null){
                   res = cur = list2;
                }else{
                   cur.next = list2;
                   cur = cur.next;
                }
                list2 = list2.next;
            }
        }
        if(list1 == null){
            cur.next = list2;
        }else{
            cur.next = list1;
        }
        return res;
    }
}

17 树的子结构

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

自己的解法

a方法同样也是判断root2是不是root1的子结构, 不同的是只从当前root1节点开始, 直接返回结果而不会再继续向下查找. 在HasSubtree方法中, 当节点值相同时就使用a方法判断, 如果返回了false, 则再从左右两个节点依次向下查找.

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean res = false;
        if(root2 == null || root1 == null)
            return false;
        if(root1.val == root2.val)
            res = a(root1, root2);
        if(!res)
            res = HasSubtree(root1.left, root2);
        if(!res)
            res = HasSubtree(root1.right, root2);
        return res;
    }
    private boolean a(TreeNode root1,TreeNode root2){
        if(root2 == null)
            return true;
        if(root1 == null)
            return false;
        if(root1.val == root2.val)
            return a(root1.left, root2.left) && a(root1.right, root2.right);
        else
            return false;
    }
}

18 二叉树的镜像

这个太简单了....

19 顺时针打印矩阵

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

分成按照方向分成四种情况, 分别的把数字add进结果里.

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        int i = 0, j = 0, k = 0;
        int w = matrix[0].length, h = matrix.length;
        ArrayList<Integer> res = new ArrayList<>();
        while(w != 0 && h != 0){
            switch(k){
                case 0:
                    for(int m = 0; m < w; m++, j++)
                        res.add(matrix[i][j]);
                    h--;
                    i++;
                    j--;
                    break;
                case 1:
                    for(int m = 0;m < h; m++, i++)
                        res.add(matrix[i][j]);
                    w--;
                    j--;
                    i--;
                    break;
                case 2:
                    for(int m =0;m < w; m++, j--)
                        res.add(matrix[i][j]);
                    h--;
                    i--;
                    j++;
                    break;
                case 3:
                    for(int m =0;m < h; m++,i--)
                        res.add(matrix[i][j]);
                    w--;
                    j++;
                    i++;
            }
            if (k == 3)
                k = 0;
            else
                k++;
        }
        return res;
    }
}