剑指offer刷题总结(六)其他

1. 扑克牌顺子

题目描述：

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。

代码实现:

public class problem1 {

    /**
     * 先排序再遍历，记录0的数量和空的大小，最后比较
     * @param numbers
     * @return
     */
    public boolean isContinuous(int [] numbers) {
        if(numbers == null || numbers.length ==0)
            return false;
        int zero=0;
        int space=0;
        Arrays.sort(numbers);
        for(int i=0;i<numbers.length-1;i++){
            if(numbers[i]==0){
                zero++;
            }else if(numbers[i]!=numbers[i+1]){
                space+=numbers[i+1]-numbers[i]-1;
            }else
                return false;
        }
        if(space>zero)
            return false;
        return true;
    }
}

2. 孩子们的游戏（圆圈中剩下的数）

题目描述

有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友可拿到礼物。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

代码实现：

public class problem2 {
    /**
     * 使用链表循环删除
     * @param n
     * @param m
     * @return
     */
    public int LastRemaining_Solution(int n, int m) {
        if (n == 0 || m == 0)
            return 0;
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            linkedList.add(i);
        }
        int count = 0;
        while (linkedList.size() > 1) {
            //删除报数为m-1的人（从0开始）
            count = (count + m - 1) % linkedList.size();
            linkedList.remove(count);
        }
        return linkedList.poll();
    }
}

3. 替换空格

题目描述

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

代码实现：

public class problem3 {
    public String replaceSpace(StringBuffer str) {
        String result="";

        for(int i=0;i<str.length();i++){
            if(str.charAt(i)!=' ')
                result+=str.charAt(i);
            else
                result+="%20";
        }
        return result;
    }
}

4. 斐波那契数列

题目描述

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

代码实现：

public class problem4 {

    /**
     * 递归(效率低)
     * @param n
     * @return
     */
    public int Fibonacci(int n) {
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else{
            return Fibonacci(n-1)+Fibonacci(n-2);
        }
    }

    /**
     * 循环(效率高)
     * @param n
     * @return
     */
    public int Fibonacci2(int n) {
        if(n<2)
            return n;
        int[] fib=new int[n+1];
        fib[0]=0;
        fib[1]=1;
        for(int i=2;i<=n;i++){
            fib[i]=fib[i-1]+fib[i-2];
        }
        return fib[n];
    }
}

5. 跳台阶

题目描述

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

思路：
斐波拉契数序列，初始条件n=1:只能一种方法，n=2:两种 对于第n个台阶来说，只能从n-1或者n-2的台阶跳上来，所以
F(n) = F(n-1) + F(n-2)

代码实现：

public class problem5 {
    public int JumpFloor(int target) {
        if(target==0||target==1){
            return 1;
        }else{
            return JumpFloor(target-1)+JumpFloor(target-2);
        }
    }
}

6. 变态跳台阶

题目描述

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

思路：

记第n级台阶有f(n)种跳法，则有：
$$f(n)=f(n-1)+f(n-2)+…+f(2)+f(1) ①$$
$$f(n-1)=f(n-2)+f(n-3)+…+f(2)+f(1) ②$$

①-②得f(n)=2f(n-1) 可得递推公式： $$f(n) = \begin{cases} 2f(n-1), n>=2\\[2ex] 1, n=1 \end{cases}$$

代码实现：

public class Solution {
    public int JumpFloorII(int target) {
        int res = 1;
        for(int i =1;i <=target-1;i++){
            
            res = res * 2;
            
        }
        return res;
    }
}

7. 矩形覆盖

题目描述：

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

思路：

我们先把2x8的覆盖方法记为f(8)。用第一个1x2小矩形去覆盖大矩形的最左边时有两个选择，竖着放或者横着放。当竖着放的时候，右边还剩下2x7的区域,这种情形下的覆盖方法记为f(7).接下来考虑横着放的情况。当1x2的小矩形横着放在左上角的时候，左下角必须和横着放一个1x2的小矩形，而在右边还还剩下2x6的区域，这种情形下的覆盖方法记为f(6), .因此f(8)= f(7)+ f(6)。 此时我们可以看出，这仍然是斐波那契数列。

代码实现：

public class Solution {
    public int RectCover(int target) {
	        int res = 0;
            if(target == 0)
                return 0;
	        else if(target == 2)
	            return 2;
            else if(target ==1)
                return 1;
	      	else
	            res = RectCover(target - 1) + RectCover(target-2);
	        return res;
         /*int result = 0;  
            if (target > 0) {  
                if (target <= 2)  
                    return target;  
                else  
                    return result = RectCover(target - 1) + RectCover(target - 2);  
            }  
            return result;  */
    }

8. 数值的整数次方

题目描述：

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

代码实现：

public class problem8 {

    /**
     * 讨论exponent大于0、小于0和等于0的情况
     * @param base
     * @param exponent
     * @return
     */
    public double Power(double base, int exponent) {
        double result = 1.0;
        if (exponent > 0) {
            for (; exponent > 0; exponent--) {
                result *= base;
            }

        } else if (exponent == 0) {
            result = 1;
        } else {
            base=1/base;
            exponent=-exponent;
            for (; exponent > 0; exponent--) {
                result *= base;
            }
        }
        return result;
    }
}

9. 顺时针打印矩阵

题目描述：

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

代码实现：

public class problem9 {
    private static ArrayList<Integer> list=new ArrayList<>();
    /**
     * 基本思路：
     * 1.左上角的坐标和右下角的坐标固定了一圈矩阵，先打印这一圈矩阵。其中，对矩阵只有一行或者一列分别打印。
     * 2.打印完了这一圈，左上角坐标都+1 ，右下角的都减一，到更内一圈。
     *比如：4*4的矩阵，(0,0)--(3,3)然后，(1,1)--(2,2)
     * 3.当左上角跑到右下角下面就结束了。
     * @param matrix
     * @return
     */
    public static ArrayList<Integer> printMatrix(int[][] matrix) {
        int downRow=matrix.length-1;
        int downCol=matrix[0].length-1;
        int topRow=0;
        int topCol=0;
        while(downCol>=topCol&&downRow>=topCol){
            printM(matrix,topRow++,topCol++,  downRow--, downCol--);
        }
        return list;
    }

    private static void printM(int[][] matrix, int topRow, int topCol, int downRow, int downCol){
        if (topRow == downRow) { //子矩阵只有一行的时候
            for (int i = topCol; i <= downCol; i++) {//注意循环开始的条件，是从这一列开始，不是从零
                list.add(matrix[topRow][i]);
            }
        }
        else if (topCol == downCol) {//子矩阵只有一列的时候
            for (int i = topRow; i <= downRow; i++) {//
                list.add(matrix[i][topCol]);
            }
        }else{
            int currntRow=topRow;
            int currntCol=topCol;
            while(currntCol<downCol){
                list.add(matrix[topRow][currntCol]);
                currntCol++;
            }
            while (currntRow<downRow){
                list.add(matrix[currntRow][downCol]);
                currntRow++;
            }
            while(currntCol>topCol){
                list.add(matrix[downRow][currntCol]);
                currntCol--;
            }
            while (currntRow>topRow){
                list.add(matrix[currntRow][topCol]);
                currntRow--;
            }
        }
    }
}

10. 最小的k个数

题目描述:

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

代码实现;

public class problem10 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> resultlist=new ArrayList<>();
        if(input.length<k)
            return  resultlist;
        Arrays.sort(input);
        for(int i=0;i<k;i++){
            resultlist.add(input[i]);
        }
        return resultlist;
    }
    /**
     * 大顶堆实现
     * @param input
     * @param k
     * @return
     */
    public  ArrayList<Integer> GetLeastNumbers_Solution2(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input == null || k <= 0 || k > input.length) {
            return list;
        }
        int[] kArray = Arrays.copyOfRange(input, 0, k);
        //1.构建大顶堆
        for(int i=kArray.length / 2 - 1;i>=0;i--){
            //从第一个非叶子节点开始，下次第二个，依次调整构建大根堆
            adjustHeap(kArray,i,kArray.length);
        }
        //2.依次来判断，有小于堆顶的那就替换掉继续调整一个堆
        for (int i = k; i < input.length; i++) {
            if (input[i] < kArray[0]) {
                kArray[0] = input[i];
                adjustHeap(kArray, 0, kArray.length);
            }
        }
        //最后把堆里的元素读出来
        for (int i = kArray.length - 1; i >= 0; i--) {
            list.add(kArray[i]);
        }
        return list;
    }
    public static void adjustHeap(int []arr,int i,int length){ //从i节点开始调整，
        int temp = arr[i];//先取出当前元素i
        for(int k = i*2+1;k<length;k = k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }
}