Zusammenfassung häufiger Array-Fragen in Java-Interviews (2)

1. Fibonacci-Folge

Jeder kennt die Fibonacci-Folge. Jetzt werden wir aufgefordert, das n-te Element der Fibonacci-Folge einzugeben (beginnend mit 0). ).

(Empfohlenes Video-Tutorial:

Java-Kurs

)[Code]

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. Rechteckige Abdeckung

[Thema]

Wir können ein kleines Rechteck von 21 verwenden, um ein größeres Rechteck horizontal oder vertikal abzudecken. Wie viele Möglichkeiten gibt es, ein großes 2*n-Rechteck ohne Überlappung mit n kleinen Rechtecken der Größe 21 zu überdecken?

Wenn beispielsweise n=3 ist, gibt es 3 Überdeckungsmethoden für 2*3 rechteckige Blöcke:

Code:

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

[Denken]

Der einfachste Weg, das Problem zu lösen, besteht darin, die Regeln zu finden Aus den zusammengefassten Regeln ist ersichtlich, dass dies der Weg ist, die Fibonacci-Folge zu realisieren. Der andere Weg besteht darin, die Frage entsprechend der Bedeutung der Frage zu beantworten und die Methode von n zu finden des Problems von n-1, und der erste Block ist horizontal (f[n-2]) und vertikal (f[n-1]), was verschiedenen Situationen entspricht

(Empfohlene weitere verwandte Interviewfragen:

Java-Interviewfragen und Antworten

)3. 1 in Binärzahl

[Titel]

Geben Sie eine Ganzzahl ein und geben Sie die Anzahl der Einsen in der Binärdarstellung der Zahl aus. Negative Zahlen werden im Zweierkomplement ausgedrückt.

【Code】

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

【Denken】

Das Einserkomplement einer negativen Zahl: Das Vorzeichenbit bleibt unverändert und die restlichen Bits werden invertiert. Das Komplement einer negativen Zahl: +1 auf der Basis ihres Einserkomplements

Wenn eine Ganzzahl nicht 0 ist, dann ist mindestens ein Bit dieser Ganzzahl 1. Wenn wir von dieser Ganzzahl 1 subtrahieren, wird die ursprüngliche 1 ganz rechts der Ganzzahl zu 0 und alle Nullen nach der ursprünglichen 1 werden zu 1 (sofern nach der Eins ganz rechts Nullen stehen). Alle übrigen Bits bleiben davon unberührt.

Zum Beispiel: eine Binärzahl 1100, die dritte Ziffer von rechts ist die 1 ganz rechts. Nach dem Subtrahieren von 1 wird die dritte Ziffer zu 0, die beiden folgenden Nullen werden zu 1 und die erste 1 bleibt unverändert, sodass das Ergebnis 1011 ist. Wir stellen fest, dass das Ergebnis der Subtraktion von 1 darin besteht, das ganz rechte Bit zu ändern. Alle Bits, die mit 1 beginnen, sind invertiert. Wenn wir zu diesem Zeitpunkt die UND-Operation zwischen der ursprünglichen Ganzzahl und dem Ergebnis nach der Subtraktion von 1 durchführen, werden alle Bits beginnend mit der 1 ganz rechts der ursprünglichen Ganzzahl zu 0. Beispiel: 1100&1011=1000. Mit anderen Worten: Wenn Sie 1 von einer Ganzzahl subtrahieren und dann eine UND-Operation mit der ursprünglichen Ganzzahl durchführen, wird die 1 auf der rechten Seite der Ganzzahl in 0 umgewandelt. Dann gibt es ebenso viele Einsen wie es im Binärsystem einer ganzen Zahl eine solche Operation gibt.

4. Die ganzzahlige Potenz eines Werts

[Titel]

Gegeben ist eine Gleitkommazahlbasis vom Typ Double und ein ganzzahliger Exponent vom Typ int. Ermitteln Sie die Basis hoch exponentiell.

Stellen Sie sicher, dass Basis und Exponent nicht gleichzeitig 0 sind

[Code]

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

}

[Denken]

Diese Frage ist nicht schwierig und der Algorithmus ist nicht sehr kompliziert, aber die Ecken sind leicht zu übersehen

Der erste Punkt ist Exponent. Es ist leicht, das Positive und Negative negativer Zahlen zu übersehen Die Basis wird immer größer.

5. Passen Sie die Reihenfolge des Arrays so an, dass ungerade Zahlen vor geraden Zahlen stehen.

[Titel] befinden sich in der ersten Hälfte des Arrays und alle geraden Zahlen befinden sich in der zweiten Hälfte des Arrays und stellen sicher, dass die relativen Positionen zwischen ungeraden Zahlen und ungeraden Zahlen, geraden Zahlen und geraden Zahlen unverändert bleiben.

[Code]

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

[Denken]

Offensichtlich ist die Methode zum Erstellen eines neuen Arrays eine schwierige Methode. Die zweite Methode besteht darin, Operationen für dieses Array auszuführen Array-Operation, und diese Dual-Cursor-Fortschrittsmethode kommt der Idee der schnellen Sortierung sehr nahe.

Verwandte Empfehlungen:

Erste Schritte mit Java

Das obige ist der detaillierte Inhalt vonZusammenfassung häufiger Array-Fragen in Java-Interviews (2). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!