java面試中常見的陣列題目總結（二）-Java面試題-PHP中文網

java面試中常見的陣列題目總結（二）

1、斐波那契數列

【題目】

大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n 項（從0 開始，第0 項為0）。

（影片教學推薦：java課程）

【程式碼】

package swear2offer.array;


public class FeiBoNaQi {

    /**
     * 大家都知道斐波那契数列，现在要求输入一个整数 n，
     * 请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）。
     * 0,1,1,2,3,5
     * n<=39
     * */
    public int Fibonacci(int n) {
        if (n == 0) return 0;

        if (n == 1 || n== 2) return 1;

        return Fibonacci(n-1) + Fibonacci(n-2);
    }

    /**
     * 非递归方式，递归的数据结构使用的栈，那就是使用栈的方式
     * */
    public int NoRecursive(int n) {
        if (n>2) {
            int[] a = new int[n+1];
            a[0] = 0;
            a[1] = 1;
            a[2] = 1;

            for (int i=3; i<=n; i++) {
                a[i] = a[i-1] + a[i-2];
            }

            return a[n];
        } else {
            if (n == 0) return 0;
            else return 1;
        }
    }

    public static void main(String[] args) {
        System.out.println(new FeiBoNaQi().Fibonacci(39));
        System.out.println(new FeiBoNaQi().Fibonacci(39));
    }
}

登入後複製

2、矩形覆蓋

【題目】

我們可以用21 的小矩形橫著或豎著去覆蓋更大的矩形。請問用 n 個 21 的小矩形無重疊地覆蓋一個 2*n 的大矩形，總共有多少種方法？

例如n=3 時，2*3 的矩形區塊有3 種覆寫方法：

java面試中常見的陣列題目總結（二）

#程式碼：

package swear2offer.array;

public class Rectangle {

    /**
     * f[0] = 0;
     * f[1] = 1;
     * f[2] = 2;
     * f[3] = 3;
     * f[4] = 5;
     * f[5] = 8;
     * f[n] = f[n-1] + f[n-2]
     * */

    public int RectCover(int target) {

        if (target < 4) return target;

        int[] f = new int[target + 1];
        int i;
        for (i=0; i<4; i++) f[i] = i;

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

        return f[target];
    }



    public static void main(String[] args) {
        System.out.println(new Rectangle().RectCover(5));
    }
}

登入後複製

【思考】

最直白的結題方式就是找規律，從總結的規律可以看出這是斐波那契數列的實現方式；另一種就是根據題意來解答，求n的方法，這類問題很容易想到是從n-1來求解，而第一個區塊是橫（f[n-2]）是豎(f[n-1])，分別對應不同的情況

（更多相關面試題推薦：java面試題目及答案）

3、二進位中1 的個數

【題目】

輸入一個整數，輸出該數二進位表示中1 的個數。其中負數用補碼表示。

【代碼】

package swear2offer.array;

public class Binary {

    /**
     * 输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示。
     * */
    public int NumberOf1(int n) {
        int count;
        count = 0;

        while(n != 0) {
            n = n & (n-1);// 与操作就是二进制的操作，适用原码和补码
            count ++;
        }

        return count;
    }
}

登入後複製

【思考】

負數的反碼：符號位不變,其餘各位按位取反負數的補碼：在其反碼的基礎上1

如果一個整數不是0，那麼這個整數至少有一位是1。如果我們把這個整數減 1，那麼原來處在整數最右邊的 1 就會變成 0，原來在 1 後面的所有的 0 都會變成 1 (如果最右邊的 1 後面還有 0 的話)。其餘所有位將不會受到影響。

舉例：一個二進制數 1100，從右邊數起第三位是處於最右邊的一個 1。減去1 後，第三位變成0，它後面的兩位0 變成了1，而前面的1 保持不變，因此得到的結果是1011. 我們發現減1 的結果是把最右邊的一個1 開始的所有位元都取反了。這時候如果我們再把原來的整數和減去 1 之後的結果做與運算，從原來整數最右邊一個 1 那一位開始所有位都會變成 0。如1100&1011=1000. 也就是說，把一個整數減去1，再和原整數做與運算，會把該整數最右邊一個1 變成0. 那麼一個整數的二進制有多少個1，就可以進行多少次這樣的操作。

4、數值的整數次方

【題目】

給定一個 double 類型的浮點數 base 和 int 類型的整數 exponent。求 base 的 exponent 次方。
保證base 和exponent 不同時為0

【程式碼】

package swear2offer.array;

public class Power {

    public double Power(double base, int exponent) {

        if (base == 0) return 0;
        if (exponent == 0) return 1;

        int count;
        boolean flag;
        double temp;

        count = 1;
        temp = base;
        flag = true;// 标记正负

        if (exponent < 0){
            exponent = -exponent;
            flag = false;
        }

        while (count < exponent) {
            base *= temp;
            count ++;
        }

        if (flag) {
            return base;
        } else {
            return 1/base;
        }

    }

    public static void main(String[] args) {
        System.out.println(new Power().Power(2,-3));
    }

}

登入後複製

【思考】

本題難度並不大，演算法也不是很複雜，但邊邊角角很容易遺漏，

第一點就是exponent的正負，很容易就漏掉負數的情況

其次，base==0和exponent==0的情況是不一樣的

最後，base累乘的時候，是不能用本身的，因為base是不斷變大的。

5、調整數組順序使奇數位於偶數前面

【題目】

輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有的奇數位於數組的前半部分，所有的偶數位於數組的後半部分，並保證奇數和奇數，偶數和偶數之間的相對位置不變。

【程式碼】

package swear2offer.array;

import java.util.Arrays;

public class OddEven {

    /**
     * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
     * 使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
     * 并保证奇数和奇数，偶数和偶数之间的相对位置不变。
     *
     * 时空复杂度较高的算法：
     * 新建一个数组b，用来保存奇数，在重新变量一次，保存偶数
     * 时空复杂度0(n)
     * */
    public void reOrderArray1(int [] array) {
        int n,i,j;
        n = array.length;

        int[] b = new int[n];

        j = 0;// 用来保存数组B的下标
        for (i=0; i<n; i++) {
            if (array[i]%2 != 0) {
                b[j] = array[i];
                j ++;
            }
        }
        for (i=0; i<n; i++) {
            if (array[i]%2 == 0){
                b[j] = array[i];
                j++;
            }
        }

        for (i=0; i<n; i++) {
            array[i] = b[i];
        }
    }

    /**
     * 采用的冒泡交换以及快速排序的思想：
     * 设定两个游标，游标分别用来标记奇数和偶数的下标，然后交换二者
     * 注意交换二者是无法保证顺序的，交换的ij之间还有进行平移。
     * */
    public void reOrderArray(int [] array) {

        int n,i,j,temp,p;

        n = array.length;
        i = 0;
        j = 0;
        while (i<n && j<n) {
            // i标记偶数下标
            while (i<n) {
                if (array[i]%2 ==0){
                    break;
                } else {
                    i++;
                }
            }
            j = i;
            // j标记奇数下标
            while (j<n) {
                if (array[j]%2 !=0){
                    break;
                } else {
                    j++;
                }
            }
            if (i<n && j<n) {
                // 此时ij已经在遇到的第一个偶数和奇数停下，把ij之间的内容平移
                temp = array[j];
                for (p=j; p>i; p--) {
                    array[p] = array[p-1];
                }
                array[i] = temp;
                // 此时把i,j标记到 未交换前的偶数位置的下一个
                i ++;
                j = i;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {1,4,6,3,2,5,8};
        int[] b = {2,4,6,1,3,5,7};
        new OddEven().reOrderArray(b);
        System.out.println(Arrays.toString(b));
    }
}

登入後複製

【思考】

顯然，創建新數組的方式，是一種取巧的方式，題目要求是需要在本數組上進行操作，第二種方式就是採用在本數組上進行操作的，而這種雙遊標遞進的方式跟快速排序的思想很接近。