1. フィボナッチ數(shù)列

[トピック]

誰もが知っているフィボナッチ數(shù)列です。ここで、整數(shù) n を入力するように求められます。出力してください。フィボナッチ數(shù)列の n 番目の項 (0 から始まり、0 番目の項は 0)。

(ビデオチュートリアルの推奨: java コース)

[コード]

package swear2offer.array;


public class FeiBoNaQi {

    /**
     * 大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù) n，
     * 請你輸出斐波那契數(shù)列的第 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);
    }

    /**
     * 非遞歸方式，遞歸的數(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 という小さな長方形を使用して、大きな長方形を水平または垂直に覆うことができます。 2*n の大きな長方形をサイズ 21 の n 個の小さな長方形で重なり合わずに覆う方法は何通りありますか?

たとえば、n=3 の場合、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));
    }
}

[思考 ]

問題を解決する最も簡単な方法は、ルールを見つけることです。要約されたルールから、これがフィボナッチ數(shù)列を?qū)g現(xiàn)する方法であることがわかります。もう 1 つは質(zhì)問に答えることです。質(zhì)問の意味に従って n の方法を見つけます。この種の問題を n-1 から解くことを考えるのは簡単で、最初のブロックは水平 (f[n-2]) または垂直 (f[ n-1])、さまざまな狀況に対応

(さらに関連する面接の質(zhì)問に関する推奨事項: java 面接の質(zhì)問と回答)

3. 2 進數(shù)の 1 の數(shù)

##[トピック]

整數(shù)を入力し、その數(shù)値を 2 進數(shù)で表現(xiàn)した 1 の數(shù)を出力します。負の數(shù)は 2 の補數(shù)で表現(xiàn)されます。

[コード]

package swear2offer.array;

public class Binary {

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

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

        return count;
    }
}

[考え方]

負の數(shù)の 1 の補數(shù): 符號ビットは変更されず、殘りのビットはビットごとに反転されます。負の數(shù)の補數(shù): 1 の補數(shù)で 1

に基づく 整數(shù)が 0 でない場合、この整數(shù)の少なくとも 1 ビットは 1 です。この整數(shù)から 1 を引くと、整數(shù)の右端にある元の 1 は 0 になり、元の 1 の後の 0 はすべて 1 になります (右端の 1 の後に 0 がある場合)。殘りのビットはすべて影響を受けません。

例: 2 進數(shù) 1100、右から 3 桁目は右端の 1 です。 1 を減算すると、3 番目の桁が 0 になり、続く 2 つの 0 が 1 になり、前の 1 は変更されないため、結(jié)果は 1011 になります。 1 を減算した結(jié)果は、右端の 1 つが変更されることがわかります。 1 で始まるすべてのビットは次のとおりです。反転した。このとき、元の整數(shù)と1を引いた結(jié)果とのAND演算を行うと、元の整數(shù)の右端の1から始まるすべてのビットが0になります。たとえば、1100&1011=1000。つまり、整數(shù)から 1 を引いて、元の整數(shù)と AND 演算を?qū)g行すると、整數(shù)の右端の 1 が 0 になります。整數(shù)の 2 進數(shù)システムにそのような演算があるのと同様です。

4. 値の整數(shù)べき乗

[タイトル]

double 型の浮動小數(shù)點數(shù)の基數(shù)と int 型の整數(shù)指數(shù)が與えられます。底の指數(shù)乗を求めます。

基數(shù)と指數(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;// 標記正負

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

}

[考え方]

この質(zhì)問は難しくありません。アルゴリズムは次のとおりです。それほど複雑ではありませんが、エッジ 角や角を見逃しやすいです。 Base==0 と exponent==0 の場合は次のとおりです。 何が異なりますか。

最後に、base を累積的に乗算する場合、base は常に大きくなるため、単獨で使用することはできません。

5. 奇數(shù)が偶數(shù)の前になるように配列の順序を調(diào)整します

[トピック]

整數(shù)の配列を入力し、調(diào)整する関數(shù)を?qū)g裝しますすべての奇數(shù)が配列の前半に配置され、すべての偶數(shù)が配列の後半に配置されるように、配列內(nèi)の數(shù)値の順序を決定し、奇數(shù)と奇數(shù)の間の相対位置を確保します。そして偶數(shù)と偶數(shù)は変化しません。

[コード]

package swear2offer.array;

import java.util.Arrays;

public class OddEven {

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

        int[] b = new int[n];

        j = 0;// 用來保存數(shù)組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];
        }
    }

    /**
     * 采用的冒泡交換以及快速排序的思想：
     * 設定兩個游標，游標分別用來標記奇數(shù)和偶數(shù)的下標，然后交換二者
     * 注意交換二者是無法保證順序的，交換的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標記偶數(shù)下標
            while (i<n) {
                if (array[i]%2 ==0){
                    break;
                } else {
                    i++;
                }
            }
            j = i;
            // j標記奇數(shù)下標
            while (j<n) {
                if (array[j]%2 !=0){
                    break;
                } else {
                    j++;
                }
            }
            if (i<n && j<n) {
                // 此時ij已經(jīng)在遇到的第一個偶數(shù)和奇數(shù)停下，把ij之間的內(nèi)容平移
                temp = array[j];
                for (p=j; p>i; p--) {
                    array[p] = array[p-1];
                }
                array[i] = temp;
                // 此時把i,j標記到 未交換前的偶數(shù)位置的下一個
                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));
    }
}

[思考]

明らかに、新しい配列を作成する方法は難しい方法であり、質(zhì)問ではこの配列に対して操作を?qū)g行する必要があります。 、2 番目の方法は、この配列を操作することであり、このデュアル カーソル プログレッシブ方法は、クイック ソートのアイデアに非常に近いです。

関連する推奨事項:

Java の使用を開始する

以上がJava 面接でよくある配列に関する質(zhì)問のまとめ (2)の詳細內(nèi)容です。詳細については、PHP 中國語 Web サイトの他の関連記事を參照してください。