牛客网 剑指OFFER 编程题记录1_list.add(0,tmp.val)

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

自己编的乱七八糟,用了40行java代码.记录下评论区大神们的思路和操作.

首选: JS做法,最简单最好记: return array.toString().split(',').includes(target.toString())    (注意,JS后面没有分号)

最精妙做法: 当成二维矩阵,从左下角往右上找,如果比左下角元素大,就往右边找;反之就往上找.然后又自己写了一遍.

public class Solution {
    public boolean Find(int target, int [][] array) {
        int row = array.length;
        int col = array[0].length;
        if(row!=0&&col!=0){
            //从左下角往上和右找
            int left = row-1;
            int down = 0;
            while(left>=0&&down<=(col-1)){
                if(target==array[left][down])return true;
                else {
                    if(target<array[left][down]){
                        left--;
                    }else{
                        down++;
                    }
                }
            }
            return false;
        }else{
            return false;
        }
    }
}

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

这个回顾复习了一下java里的String函数,

一个%20替换一个空格: return str.toString().replaceAll("\\s","%20");

如果是一个%20替换一个或多个空格: return str.toString().replaceAll("\\s+","%20");

这里要注意的是一个或多个空格的正则表达式: "\\s+", split也是这个用法.

然后看了一下评论区大家的做法,感觉自己有点投机取巧,所以又写了一遍.

public class Solution {
    public String replaceSpace(StringBuffer str) {
        String ss = str.toString();
        String result=""; //注意初始化,否则后面用不了
        for(int i=0;i<ss.length();i++){
            char c = ss.charAt(i);
            if(c == ' '){
                result += "%20";
            }else{
                result += c;
            }
        }
        return result;
    }
}

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

解法1.这里注意一个list的功能，add(index,element),直接将遍历的元素插到ArrayList的起始位置即可。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode tmp = listNode;
        while(tmp!=null){
            list.add(0,tmp.val);
            tmp=tmp.next;
        }
        return list;
    }
}

解法2. 用递归，这样就最先插链表的最后一个元素了。这里注意递归返回的那个list一定只有一个。

import java.util.ArrayList;
public class Solution {
    //成员变量
    ArrayList<Integer> list = new ArrayList<>(); 
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode tmp = listNode;
        if(tmp!=null){
            printListFromTailToHead(tmp.next);
            list.add(tmp.val);
        }
        return list;
    }
}

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

这道题就涉及树的算法了，全忘了，只能从头捡起。看完解法之后我就开始自己编程了，没想到调入了一个binarySearch的陷阱里。先上解法，我的思路完全正确，而且做法也是最简洁的，结果就是不知道为什么错，直到后来直接复制粘贴别人的代码，才发现这个binarySearch的错。

import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre,int[] in) {
        if(pre.length==0){
            return null;
        }
        int rootval = pre[0];
        TreeNode root = new TreeNode(rootval);
        if(pre.length==1){
            return root;
        }
        int rootIndex = 0;
//这一步，我之前用binarySearch,然后真的大错特错，怎么都没想到是这出了问题
        for(int i=0;i<in.length;i++){
            if(in[i]==rootval){
                rootIndex=i;
                break;
            }
        }
        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,rootIndex+1),
                                          Arrays.copyOfRange(in,0,rootIndex));
        root.right =reConstructBinaryTree(Arrays.copyOfRange(pre,rootIndex+1,pre.length),
                                         Arrays.copyOfRange(in,rootIndex+1,in.length));
        return root;
    }
    
}

注意：binarySearch是二分查找法，在对无序数组查找时，非常容易出现找不着的情况。使用二分搜索法来搜索指定的 int 型数组，以获得指定的值。必须在进行此调用之前对数组进行排序（通过 sort(int[]) 方法）。如果没有对数组进行排序，则结果是不确定的。以下为例：所以对于无序数组查找时，千万不要用这个方法。

5. 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。比较简单，属于考思路类型。push操作都push到一个栈中,只有在pop时,将栈1的所有元素弹出,再压入栈2,这样从栈2再弹出的就是队列顺序了.

import java.util.Stack;
 
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    //队列先进先出，栈先进后出，把推进栈1的倒到栈2，再从栈2倒出来即可。
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        int node = stack2.pop();
        return node;
    }
}

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

难点在于,数组中的非递减顺序.

二分查找的做法: 为了避免出现a[mid]=a[left]=a[right]的情况,先将left和light值不断后移和前移使a[left],a[right]不相等. 然后再不断缩小查找范围,直到出现a[left]<a[right],就可以返回最小值a[left]了.(因为在旋转数组中,最左边小于最右边时,那么一定有最左边为最小值).缩小查找范围时,a[mid]如果>=a[left],那么说明a[mid]是左半边非递减数组的,则最小值在mid的右边.反之,a[mid]是右边非递减数组的,则最小值在mid及其mid的左边.

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length==0){
            return 0;
        }
        int left = 0;
        int right = array.length - 1;
        //避免出现[1,1,1,0,1]的情况,先让left和right做个比较
        while((right>left)&&array[left] == array[right]){
            left++;
            right--;
        }
//二分查找        
        while(array[left]>array[right]){
            //mid属于中间值,根据中间值的大小判断最小值在哪半边
            int mid = left + (right - left)/2;
            //中间值大于left时,说明mid在左半边递增数组,那么最小值在mid右边
            if(array[mid]>=array[left]){
                left = mid+1;
            }else{
                //小于left说明mid在右半边递增数组,则最小值在mid及其左边
                right = mid;
            }
        }
 
        return array[left];
    }
}

7. 斐波那契: 从0开始的斐波那契数列.虽然递归是最简单的,但内存占用过大,所以还是稳妥一点选循环吧.

public class Solution {
    public int Fibonacci(int n) {
        int a0 = 0;
        int a1 = 1;
        if(n==0)return a0;
        if(n==1)return a1;
        int result =0;
        for(int i=2;i<=n;i++){
            result = a0+a1;
            a0 = a1;
            a1 = result;
        }
        return result;
    }
}

8. 递归: 跳台阶: 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。核心思路: JumpFloor(n) = JumpFloor(n-1) + JumpFloor(n-2), 因此又变成了斐波契那问题.

public class Solution {
    public int JumpFloor(int target) {
        int n=target;
        if(n<=0)return 0;
        if(n==1)return 1;
        if(n==2)return 2;
        int f1 = 1;
        int f2 = 2;
        int result=0;
        for(int i=3;i<=n;i++){
            result = f1+f2;
            f1 = f2;
            f2 = result;
        }
        return result;
    }
}

9. 变态跳台阶(递归).一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

两个思路: 1. 青蛙跳台阶数f(n) = f(n-1)+f(n-2)+...+f(1)+1; 然后根据这个迭代着算一下

2. f(n) = f(n-1)+f(n-2)+...+f(1)+1;

 f(n-1) =            f(n-2)+...+f(1)+1;

f(n)-f(n-1)=f(n-1), 所以,f(n)=2*f(n-1),这样计算出来就很快了.首选2做法.不过1做法比较容易想.

public class Solution {
    public int JumpFloorII(int target) {
        int n = target;
        if(n<=0)return 0;
        if(n==1)return 1;
        if(n==2)return 2;
        int[] a= new int[n+1];
        a[0] = 1;
        a[1] = 1;
        a[2] = 2;
        for(int i=3;i<=n;i++){
            a[i] = 2*a[i-1];
        }
        return a[n];
        
    }
}

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

f(1)=1;f(2)=2;f(3)=3;f(4)=5;...;f(n) = f(n-1)+f(n-2)

public class Solution {
    public int RectCover(int target) {
        int n = target;
        int a1 = 1;
        int a2 = 2;
        if(n<=0)return 0;
        if(n==1)return a1;
        if(n==2)return a2;
        int result = 0;
        for(int i=3;i<=n;i++){
            result = a1+a2;
            a1 = a2;
            a2 = result;
        }
        return result;
    }
}