挑战一周刷完剑指offer

第一天

1. 二维数组中的查找

描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]]
给定 target = 7，返回 true。
给定 target = 3，返回 false。

解题思路：_解题的关键是以第一行的最后一个元素[其左边均小于它][其下面均大于它]

就可以进行二分查找了_

时间复杂度：o(m+n)

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

2.从尾到头打印链表

描述:
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
www.nowcoder.com/practice/d0…
1.使用递归 空间复杂度o(n),时间复杂度o(n)   有的面试官可能需要让使用递归的方法来处理
2.使用栈 空间复杂度o(2n),时间复杂度o(n)
3.反转链表 空间复杂度o(n),时间复杂度o(n)

/**
	递归的解法
*/
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> result = new ArrayList<>();
        return recursive(listNode, result);
    }

    public ArrayList<Integer> recursive(ListNode node, ArrayList<Integer> list) {
        if (node == null) {
            return list;
        }
        recursive(node.next,list);
        list.add(node.val);
        return list;
    }

/**
	反转链表的解法
*/
 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> result = new ArrayList<>();
        ListNode listNode1 = reverseList(listNode);
        if (listNode1 == null) {
            return result;
        }
        while (listNode1 != null) {
            result.add(listNode1.val);
            listNode1 = listNode1.next;
        }
        return  result;
        
    }
/**
反转链表
*/
    public ListNode reverseList(ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }
        ListNode pre = null;
        ListNode cur = node;
        ListNode next;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;

    }

/**
基于栈的解法不做赘述
*/
复制代码

3.重新构建二叉树

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

思路：递归调用，模拟

public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null) {
            return null;
        }
        int preLength = pre.length;
        int inLength = in.length;
        if (preLength == 0 || inLength == 0 || preLength != inLength) {
            return null;
        }
        return recursive(pre, in, 0, preLength - 1, 0, inLength - 1);
    }

    public TreeNode recursive(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart < 0 || preStart > preEnd || inStart < 0 || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(pre[preStart]);
        int leftCount = -1;
        int rightCount = -1;
        int inRootIndex = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if (in[i] == pre[preStart]) {
                inRootIndex = i;
            }
        }
        leftCount = inRootIndex - inStart;
        rightCount = inEnd - inRootIndex;
        if (leftCount > 0) {
            root.left = recursive(pre, in, preStart + 1, preStart + leftCount, inStart, inRootIndex - 1);
        }
        if (rightCount > 0) {
            root.right = recursive(pre, in, preEnd - rightCount + 1, preEnd, inEnd - rightCount + 1, inEnd);
        }
        return root;

    }
复制代码

4.用两个栈实现队列

描述
用两个栈来实现一个队列，分别完成在队列尾部插入整数(push)和在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

示例:
输入:
[“PSH1″,”PSH2″,”POP”,”POP”]

返回:
1,2
解析:
“PSH1”:代表将1插入队列尾部
“PSH2”:代表将2插入队列尾部
“POP“:代表删除一个元素，先进先出=>返回1

“POP“:代表删除一个元素，先进先出=>返回2

示例1
输入：
[“PSH1″,”PSH2″,”POP”,”POP”]
返回值：
1,2

public class Solution {
    private Stack<Integer> mInStack = new Stack<>();
    private Stack<Integer> mOutStack = new Stack<>();

    public int pop() {
        if (mOutStack.isEmpty()) {
            while (!mInStack.isEmpty()) {
                mOutStack.push(mInStack.pop());
            }
        }
        if (mOutStack.isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return mOutStack.pop();
    }

    public void push(int val) {
        mInStack.push(val);
    }
}
复制代码

5.旋转数组的最小元素

这种二分查找难就难在，arr[mid]跟谁比.

我们的目的是：当进行一次比较时，一定能够确定答案在mid的某一侧。一次比较为 arr[mid]跟谁比的问题。
一般的比较原则有：

• 如果有目标值target，那么直接让arr[mid] 和 target 比较即可。
• 如果没有目标值，一般可以考虑 端点

这里我们把target 看作是右端点，来进行分析，那就要分析以下三种情况，看是否可以达到上述的目标。

1. 情况1，arr[mid] > target：4 5 6 1 2 3
   • arr[mid] 为 6， target为右端点 3， arr[mid] > target, 说明[first … mid] 都是 >= target 的，因为原始数组是非递减，所以可以确定答案为 [mid+1…last]区间,所以 first = mid + 1
2. 情况2，arr[mid] < target:5 6 1 2 3 4
   • arr[mid] 为 1， target为右端点 4， arr[mid] < target, 说明答案肯定不在[mid+1…last]，但是arr[mid] 有可能是答案,所以答案在[first, mid]区间，所以last = mid;
3. 情况3，arr[mid] == target:
   • 如果是 1 0 1 1 1， arr[mid] = target = 1, 显然答案在左边
   • 如果是 1 1 1 0 1, arr[mid] = target = 1, 显然答案在右边

所以这种情况，不能确定答案在左边还是右边，那么就让last = last – 1;慢慢缩少区间，同时也不会错过答案。

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

6.斐波那契数列

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

n\leq 39_n_≤39
1.递归解法
2.动态规划
3.动态规划的优化（记住中间值）

//递归 时间复杂度 2的n次方
 public int Fibonacci(int n) {
        if(n<=1){
            return n;
        }
        return Fibonacci(n-1)+Fibonacci(n-2);
    }

//动态规划 时间复杂度o(n) 空间复杂度o(n)
public int Fibonacci(int n) {
        int[] dp = new int[n+1];

        if (n <= 1) {
            return n;
        }
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
//优化
public int Fibonacci(int n) {
        
        if (n <= 1) {
            return n;
        }
        int x = 0;
        int y = 1;
        for (int i = 2; i <= n; i++) {
            int t = y;
            y = x+y;
            x = t;
            //或者 
            //y += x;
            //x = y-x;
          
        }
        return y;
    }
复制代码

7.跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
f(n) = f(n-1)+f(n-2);
题解同第6道题

8.跳台阶扩展问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法.
解题思路：
f(n) = f(n-1)+f(n-2)+…….+1;
f(n-1) = f(n-2)+f(n-3)+….+1;
所以推导出
f(n) = 2f(n-1);

 public int JumpFloorII(int target) {
        if(target==1){return 1;}
        if(target==2){return 2;}
        int x = 2;
        for(int i=3;i<=target;i++){
            x=x<<1;
        }
        return x;
    }
复制代码

9.矩形覆盖

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

题解同 6和 7 
复制代码