1、斐波那契數(shù)列

【題目】

大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù) n，請(qǐng)你輸出斐波那契數(shù)列的第 n 項(xiàng)（從 0 開始，第 0 項(xiàng)為 0）。

（視頻教程推薦：java課程）

【代碼】

package swear2offer.array;


public class FeiBoNaQi {

    /**
     * 大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù) n，
     * 請(qǐng)你輸出斐波那契數(shù)列的第 n 項(xiàng)（從 0 開始，第 0 項(xiàng)為 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);
    }

    /**
     * 非遞歸方式，遞歸的數(shù)據(jù)結(jié)構(gòu)使用的棧，那就是使用棧的方式
     * */
    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 的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用 n 個(gè) 21 的小矩形無(wú)重疊地覆蓋一個(gè) 2*n 的大矩形，總共有多少種方法？

比如 n=3 時(shí)，2*3 的矩形塊有 3 種覆蓋方法：

代碼：

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));
    }
}

【思考】

最直白的結(jié)題方式就是找規(guī)律，從總結(jié)的規(guī)律可以看出這是斐波那契數(shù)列的實(shí)現(xiàn)方式；另一種就是根據(jù)題意來(lái)解答，求n的方法，這類問(wèn)題很容易想到是從n-1來(lái)求解，而第一個(gè)塊是橫（f[n-2]）是豎(f[n-1])，分別對(duì)應(yīng)不同的情況

（更多相關(guān)面試題推薦：java面試題及答案）

3、二進(jìn)制中 1 的個(gè)數(shù)

【題目】

輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中 1 的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。

【代碼】

package swear2offer.array;

public class Binary {

    /**
     * 輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中 1 的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。
     * */
    public int NumberOf1(int n) {
        int count;
        count = 0;

        while(n != 0) {
            n = n & (n-1);// 與操作就是二進(jìn)制的操作，適用原碼和補(bǔ)碼
            count ++;
        }

        return count;
    }
}

【思考】

負(fù)數(shù)的反碼： 符號(hào)位不變,其余各位按位取反負(fù)數(shù)的補(bǔ)碼：在其反碼的基礎(chǔ)上+1

如果一個(gè)整數(shù)不為 0，那么這個(gè)整數(shù)至少有一位是 1。如果我們把這個(gè)整數(shù)減 1，那么原來(lái)處在整數(shù)最右邊的 1 就會(huì)變?yōu)?0，原來(lái)在 1 后面的所有的 0 都會(huì)變成 1 (如果最右邊的 1 后面還有 0 的話)。其余所有位將不會(huì)受到影響。

舉個(gè)例子：一個(gè)二進(jìn)制數(shù) 1100，從右邊數(shù)起第三位是處于最右邊的一個(gè) 1。減去 1 后，第三位變成 0，它后面的兩位 0 變成了 1，而前面的 1 保持不變，因此得到的結(jié)果是 1011. 我們發(fā)現(xiàn)減 1 的結(jié)果是把最右邊的一個(gè) 1 開始的所有位都取反了。這個(gè)時(shí)候如果我們?cè)侔言瓉?lái)的整數(shù)和減去 1 之后的結(jié)果做與運(yùn)算，從原來(lái)整數(shù)最右邊一個(gè) 1 那一位開始所有位都會(huì)變成 0。如 1100&1011=1000. 也就是說(shuō)，把一個(gè)整數(shù)減去 1，再和原整數(shù)做與運(yùn)算，會(huì)把該整數(shù)最右邊一個(gè) 1 變成 0. 那么一個(gè)整數(shù)的二進(jìn)制有多少個(gè) 1，就可以進(jìn)行多少次這樣的操作。

4、數(shù)值的整數(shù)次方

【題目】

給定一個(gè) double 類型的浮點(diǎn)數(shù) base 和 int 類型的整數(shù) exponent。求 base 的 exponent 次方。
保證 base 和 exponent 不同時(shí)為 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;// 標(biāo)記正負(fù)

        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));
    }

}

【思考】

本題難度并不大，算法也不是很復(fù)雜，但是邊邊角角很容易遺漏，

第一點(diǎn)就是exponent的正負(fù)，很容易就漏掉負(fù)數(shù)的情況

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

最后，base累乘的時(shí)候，是不能用本身的，因?yàn)閎ase是不斷變大的。

5、調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

【題目】

輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。

【代碼】

package swear2offer.array;

import java.util.Arrays;

public class OddEven {

    /**
     * 輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序，
     * 使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分，
     * 并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。
     *
     * 時(shí)空復(fù)雜度較高的算法：
     * 新建一個(gè)數(shù)組b，用來(lái)保存奇數(shù)，在重新變量一次，保存偶數(shù)
     * 時(shí)空復(fù)雜度0(n)
     * */
    public void reOrderArray1(int [] array) {
        int n,i,j;
        n = array.length;

        int[] b = new int[n];

        j = 0;// 用來(lái)保存數(shù)組B的下標(biāo)
        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];
        }
    }

    /**
     * 采用的冒泡交換以及快速排序的思想：
     * 設(shè)定兩個(gè)游標(biāo)，游標(biāo)分別用來(lái)標(biāo)記奇數(shù)和偶數(shù)的下標(biāo)，然后交換二者
     * 注意交換二者是無(wú)法保證順序的，交換的ij之間還有進(jìn)行平移。
     * */
    public void reOrderArray(int [] array) {

        int n,i,j,temp,p;

        n = array.length;
        i = 0;
        j = 0;
        while (i<n && j<n) {
            // i標(biāo)記偶數(shù)下標(biāo)
            while (i<n) {
                if (array[i]%2 ==0){
                    break;
                } else {
                    i++;
                }
            }
            j = i;
            // j標(biāo)記奇數(shù)下標(biāo)
            while (j<n) {
                if (array[j]%2 !=0){
                    break;
                } else {
                    j++;
                }
            }
            if (i<n && j<n) {
                // 此時(shí)ij已經(jīng)在遇到的第一個(gè)偶數(shù)和奇數(shù)停下，把ij之間的內(nèi)容平移
                temp = array[j];
                for (p=j; p>i; p--) {
                    array[p] = array[p-1];
                }
                array[i] = temp;
                // 此時(shí)把i,j標(biāo)記到 未交換前的偶數(shù)位置的下一個(gè)
                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));
    }
}

【思考】

顯然，創(chuàng)建新數(shù)組的方式，是一種取巧的方式，題目要求是需要在本數(shù)組上進(jìn)行操作，第二種方式就是采用在本數(shù)組上進(jìn)行操作的，而這種雙游標(biāo)遞進(jìn)的方式跟快速排序的思想很接近。

相關(guān)推薦：java入門

以上是java面試中常見的數(shù)組題目匯總（二）的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！