12.1 剑指Offer 1-16

题目.png

1、

package Offer;

public class FindInMatrix_1 {

    /**
     * 第一题 ：
     *
     * 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
     * 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，
     * 判断数组中是否含有该整数。
     *
     * 思路 ：
     *
     * 左上角开始向下搜寻
     */
    public boolean Find(int target, int [][] array) {
        int i = 0;
        int j = array[i].length - 1;

        while(i < array.length && j >= 0){
            if (array[i][j] == target) {
                return true;
            }else if(array[i][j] < target){
                i++;
            }else{
                j--;
            }
        }

        return false;
    }
}

2、

package Offer;

public class ReplaceSpace_2 {
    /**
     * 第二题 ：
     *
     * 请实现一个函数，将一个字符串中的每个空格替换成“%20”。
     * 例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
     *
     * 思路：
     *         return str.toString().replaceAll(" ", "%20");
     *
     * 如果不用以上api ， 本题 从后往前复制和从前往后没啥区别
     */
    public String replaceSpace(StringBuffer str) {
        int spaceCount = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') spaceCount++;
        }

        if (spaceCount == 0) return str.toString();
        String old = new String(str);
        str.setLength(str.length() + 2*spaceCount);

        int indexOld = old.length() - 1;
        for (int i = str.length() - 1; i > 0 ; ) {
            if (old.charAt(indexOld) == ' '){
                str.setCharAt(i--,'0');
                str.setCharAt(i--,'2');
                str.setCharAt(i--,'%');
                indexOld--;
            }else {
                str.setCharAt( i--, old.charAt(indexOld--));
            }
        }

        return str.toString();
    }
}

3、

package Offer;

import Utils.ListNode;

import java.util.ArrayList;

public class PrintListFromTailToHead_3 {
    /**
     * 题目描述
     * 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
     *
     * 思路：
     *
     * 这是一个stack的考题，使用递归依然会有jvm压栈的空间浪费。
     * 给两个答案 ： 1、 反转链表 2、 递归
     */
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        ListNode head = reverse(listNode);
        while (head != null){
            res.add(head.val);
            head = head.next;
        }
        //process(listNode, res);//递归
        return res;
    }
    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode next ;

        while (head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    public void process(ListNode head, ArrayList<Integer> res){
        if (head == null) return;
        process(head.next,res);
        res.add(head.val);
    }
}

4、

package Offer;

import Utils.TreeNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ReConstructBinaryTree_4 {
    /**
     * 题目描述
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
     * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，
     * 则重建二叉树并返回。
     *
     *
     * 思路 ：
     *
     * 重构二叉树的经典题 ， 核心在于前序遍历确定了根节点的位置，
     * 中序遍历确定了左右子树的长度
     */

    public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }
        return process(pre,in,0,pre.length-1,0,in.length-1,map);
    }

    public TreeNode process(int[] pre, int[] in,int pleft, int pright, int ileft, int iright, Map<Integer,Integer> map){
        if (pleft > pright) return null;

        TreeNode res = new TreeNode(pre[pleft]);
        int index = map.get(pre[pleft]);
        res.left = process(pre,in,pleft+1,pleft+index-ileft,ileft,index-1,map);
        res.right = process(pre,in,pleft+index-ileft+1,pright,index+1,iright,map);

        return res;
    }
}

5、

package Offer;

import java.util.Stack;

public class TwoStackCreateQueue_5 {
    /**
     * 题目描述
     * 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
     *
     * 思路 ：
     *
     * 一个负责进， 一个负责出
     */

    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        while (!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
        stack1.push(node);
    }

    public int pop() {
        while (!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}

6、

package Offer;

public class MinNumberInRotateArray_6 {
    /**
     * 题目描述
     * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
     * 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
     * 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
     * NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
     *
     * 思路：
     *
     *  这是一道二分题， 转折点所在区间端点必然不能保证 大小顺序。
     *  而且 二分很复杂，
     *  情况1： [441111] mid 与 right 相等， 分界点在哪？
     *  情况2： [46]  mid-1 越界
     *  （这题笔试推荐直接遍历）
     *
     */

    public int minNumberInRotateArray(int [] array) {
        int left = 0;
        int 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-=1;//[441111]
            }else {
                right = mid;//[46]
            }
        }
        return array[left];
    }


}

7、

package Offer;

public class Fibonacci_7 {
    /**
     * 题目描述
     * 大家都知道斐波那契数列，现在要求输入一个整数n，
     * 请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
     * n<=39
     *
     * 0 1 1 2 3 5 8 13...
     *
     * 思路 ：
     *
     * 斐波那契数列 不多说了 ， 最简单的Dp 。
     * 注意 ： 优化空间复杂度
     */
    public int fibonacci(int n) {
        int[] dp = new int[2];
        dp[0] = 0;
        dp[1] = 1;
        if (n == 0) return 0;
        for (int i = 2; i < n+1 ; i++) {
            int temp = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = temp;
        }
        //未优化dp
//        int[] dp = new int[n+1];
//        dp[0] = 0;
//        dp[1] = 1;
//        for (int i = 2; i < n+1; i++) {
//            dp[i] = dp[i-1] + dp[i-2];
//        }
//        return dp[n];
        return dp[1];
    }
}

8、

package Offer;

public class JumpFloor_8 {
    /**
     * 题目描述
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。
     * 求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
     *
     * 思路 ：
     * dp 入门题 ， 本质跟斐波那契数列相同 ，不再赘述
     */

    public int jumpFloor(int target) {
        int[] dp = new int[2];

        if (target < 3) return target;
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 3; i <= target; i++) {
            int temp = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = temp;
        }
        return dp[1];
    }
}

9、

package Offer;

public class JumpFloorII_9 {
    /**
     * 题目描述
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
     * 求该青蛙跳上一个n级的台阶总共有多少种跳法。
     *
     * 0 ....1 2 4 8 16 ...
     * 思路 ：
     *
     * 当前步数 = 之前所有步数加和 + 1 ，从零一步跳上
     *
     * 观察数字规律，这里成了一道贪心问题 ， 直接数学方法给出答案即可。
     */

    public int jumpFloorII(int target) {
        if (target == 0) return 0;
        return (int)Math.pow(2,target-1);
    }
}

10、

package Offer;

public class RectCover_10 {
    /**
     * 题目描述
     * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
     * 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
     *
     * 思路：
     * 0 1 2 3 5 ……
     *
     * 观察数字规律发现， 这题还是斐波那契dp ，尝试一下可以AC。
     * 分析原理， f(n-1)加一竖条 ， f(n-2)加俩横条，实现全部组合。
     *
     */
    public int rectCover(int target) {
        if (target <= 2) return target;
        int[] dp = new int[target];
        dp[0] = 1;
        dp[1] = 2;

        for(int i = 2; i < target; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[target - 1];
    }
}

11、

package Offer;

public class NumberOf1_11 {
    /**
     * 二进制中1的个数
     *
     * 题目描述
     * 输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。
     *
     * 思路：
     * 按位与 & (N-1) ,
     * n - 1 消掉末尾0 ，
     * & 消掉最后一位 1 ， n != 0 计数 。
     *
     * 1001 1010 +1
     * 1001 1001 -> 1001 1000 +1
     *              1001 0111 ->  1001 0000 +1
     *                            1000 1111 ->  1000 0000 +1
     *                                          0111 1111 break
     */
    public int NumberOf1(int n) {
        int count = 0;

        while (n != 0){
            count++;
            n = n&(n-1);
        }
        return count;
    }
}

12、

package Offer;

public class Power_12 {
    /**
     * 数值的整数次方
     *
     * 题目描述
     * 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
     * 保证base和exponent不同时为0
     *
     * 思路：
     *  考察 快速幂算法 和 边界指数为负数等情况。
     *
     *
     * 注 ： 牛客网，快速幂算法时间复杂度过高，令人迷惑 反而应该用普通算法。
     */

    public double power(double base, int exponent) {
        int flag = 1;
        if (exponent < 0) flag = -1;

        double ans = 1;

        while (exponent != 0){
            if ((exponent & 1) == 1) ans *= base;

            base *= base;
            exponent >>= 1;
        }

        return flag < 0? (1/ans):ans;
    }

    public double powerNormal(double base, int exponent){
        int flag = 1;
        if (exponent < 0) flag = -1;

        double ans = 1;
        exponent = Math.abs(exponent);
        for (int i = 0; i < exponent; i++) {
            ans *= base;
        }
        return flag < 0? (1/ans):ans;
    }
}

13、

package Offer;

public class ReOrderArray_13 {
    /**
     * 调整数组顺序奇数在前
     *
     * 题目描述
     * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
     * 使得所有的奇数位于数组的前半部分，
     * 所有的偶数位于数组的后半部分，
     * 并保证奇数和奇数，偶数和偶数之间的相对位置不变。
     *
     * 思路 ：
     *
     * 想办法将空间复杂度压倒最低。
     */
    public void reOrderArray(int [] array) {
        int board = -1;
        int cur = 0;

        while (cur < array.length){
            if ((array[cur] % 2) == 1){ // odd
                int temp = array[cur];
                for (int i = cur ; i > board+1 ; i--) {
                    array[i] = array[i-1];
                }
                array[++board] = temp;
            }
            cur++;
        }
    }
}

14、

package Offer;

import Utils.ListNode;

public class FindKthToTail_14 {
    /**
     * 链表的倒数第K个节点
     *
     *题目描述
     * 输入一个链表，输出该链表中倒数第k个结点。
     *
     * 思路：
     * 双指针间隔为K，末指针到尾即可返回头指针。
     */
    public ListNode FindKthToTail(ListNode head, int k) {
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            if (tail == null) return null;
            tail = tail.next;
        }
        while (tail != null){
            head = head.next;
            tail = tail.next;
        }
        return head;
    }
}

15、

package Offer;

import Utils.ListNode;

public class ReverseList_15 {
    /**
     * 反转单链表
     *
     * 题目描述
     * 输入一个链表，反转链表后，输出新链表的表头。
     *
     * 思路：
     * 必会题背下来。三个指针 pre next head 。
     */
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;

        while (head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

16、

package Offer;

import Utils.ListNode;

public class MergeSortedList_16 {
    /**
     * 合并两个排序链表
     *
     * 题目描述
     * 输入两个单调递增的链表，输出两个链表合成后的链表，
     * 当然我们需要合成后的链表满足单调不减规则。
     *
     * 思路：
     *
     * 谁小cur next指向谁。 注意dummy节点的使用。
     *
     *
     */
    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                cur.next = list1;
                cur = cur.next;
                list1 = list1.next;
            } else {
                cur.next = list2;
                cur = cur.next;
                list2 = list2.next;
            }
        }

        if (list1 == null) cur.next = list2;
        if (list2 == null) cur.next = list1;

        return dummy.next;
    }
}