Schwierigkeitsgrad der Frage: * *

(Lernvideo-Empfehlung: Java-Kurs)

1. Sortierreihenfolge

[Titel]

Gibt den sortierten Wert eines numerischen Arrays zurück, z. B. Daten [6,2 ,5 ,0] gibt [4,2,3,1]

[Code]

package swear2offer.array;

import java.util.Arrays;

public class SortSequence {
    /**
     * 返回一個(gè)數(shù)字?jǐn)?shù)組的排序值
     * 比如數(shù)據(jù) [6,2,5,0] 的返回是 [4,2,3,1]
     * */
    public int[] compare(int[] a) {
        int i,j,n;
        n = a.length;

        int [] c = new int[n];

		//數(shù)組下標(biāo)從0開始，但是輸出的次序從1開始，所以需要初始化數(shù)組為1
        for (i=0; i<n; i++) {
           c[i]++;
        }

        for (i=0; i<n; i++) {
            for (j=0; j<i; j++) {
                if (a[j]<a[i]) c[i]++;
                else c[j]++;
            }
        }

        return c;
    }

    public static void main(String[] args) {
        int[] a = {6,2,5,0};
        System.out.println(Arrays.toString(new SortSequence().compare(a)));
    }

}

[Denken]

Der normale Weg, die Reihenfolge zu erhalten, besteht darin, jedes Element mit allen anderen Elementen zu vergleichen und dann die Gr??e zu ermitteln order , aber hier wird die trapezf?rmige Vergleichsreihenfolge verwendet.

2. Array-Index-Hilfsdatensatz

[Titel]

Gegebenes Array a mit einer L?nge von N und einem Elementwertbereich von [1, N], z?hlen Sie die Anzahl der Vorkommen jedes Elements und die erforderliche Zeitkomplexit?t ist O (N), die Raumkomplexit?t ist O (1)

[Code]

6
6 2
6 2 5
6 2 5 0

(Empfohlenes grafisches Tutorial:

)3. Finden Sie die Elemente eines geordneten zweidimensionalen Arrays

[Titel 】

In einem zweidimensionalen Array (jedes eindimensionale Array hat die gleiche L?nge) wird jede Zeile in aufsteigender Reihenfolge von links nach rechts und jede Spalte in aufsteigender Reihenfolge von oben nach unten sortiert. Bitte vervollst?ndigen Sie eine Funktion, geben Sie ein solches zweidimensionales Array und eine Ganzzahl ein und bestimmen Sie, ob das Array die Ganzzahl enth?lt.

[Code]

/**
     * 這類要求空間O(1)時(shí)間復(fù)雜度為O(n)的問題
     * 需要在一次遍歷并且不聲明新數(shù)組的情況下求解，這種題目通常要求元素大小跟下標(biāo)大小一致。
     * 所以通?？紤]是利用數(shù)組存儲(chǔ)的元素和數(shù)組下標(biāo)來求解
     * 在本題中，數(shù)組的元素變成了下標(biāo)，而數(shù)組內(nèi)元素則表示之前元素出現(xiàn)的次數(shù)，0則代表不出現(xiàn)。
     * 為了區(qū)分元素和次數(shù)，可以把次數(shù)設(shè)定為負(fù)值
     * */
    public void Solution(int[] a) {
        int i,n,temp;
        n = a.length;

        i = 0;
        /**
         * 只有在temp小于0的時(shí)候才會(huì)推進(jìn)循環(huán)
         * */
        while(i < n) {
            temp = a[i]-1;
            // 如果數(shù)組元素小于0，則代表該數(shù)已經(jīng)被替換到其他地方或者已經(jīng)被計(jì)數(shù)過從而被覆蓋
            if (temp < 0) {
                i ++;
                continue;
            }
            // 把未記錄的數(shù)保存在已經(jīng)記錄的位置上，并用負(fù)值保存數(shù)量
            if (a[temp]>0) {
                a[i] = a[temp];
                a[temp] = -1;
            } else {
                a[i] = 0; //該數(shù)據(jù)已經(jīng)使用過，且表示元素i+1出現(xiàn)0次
                a[temp]--;
            }
        }

    }

[Denken]

Ausgehend von oben links gibt es zu viele Situationen, die berücksichtigt werden müssen, da sowohl nach rechts als auch nach unten zunimmt, aber von oben rechts aus nach links abnehmend und nach unten zunehmend, so dass die Situation auf eins beschr?nkt ist. Spezielle Arrays, nutzen Sie die Besonderheiten von Arrays voll aus und berücksichtigen Sie Methoden aus verschiedenen Richtungen.

4. Stufen hochspringen

[Thema]

Ein Frosch kann 1 Stufe oder 2 Stufen gleichzeitig hochspringen. Finden Sie heraus, auf wie viele Arten der Frosch eine n-stufige Stufe hochspringen kann (unterschiedliche Ergebnisse werden in unterschiedlicher Reihenfolge berechnet). 5. Abnormale Sprungtreppen Finden Sie die Gesamtzahl der M?glichkeiten, auf denen der Frosch eine Treppe mit n Ebenen hinaufspringen kann.

【Code】

package swear2offer.array;

public class ArrayFind {

    /**
     * 在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長度相同），
     * 每一行都按照從左到右遞增的順序排序，
     * 每一列都按照從上到下遞增的順序排序。
     * 請完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，
     * 判斷數(shù)組中是否含有該整數(shù)。
     *
     * 思路：
     * 從左上出發(fā)，需要考慮的情況太多，因?yàn)橄蛴液拖蛳露际沁f增
     * 但是從右上出發(fā)，向左遞減，向下遞增，這樣就把情況限定在一種。
     * */
    public boolean Find(int target, int [][] array) {

        int l,h,x,y;
        h = array.length;
        l = array[0].length;

        // 游標(biāo)的橫縱坐標(biāo)
        x = l-1;
        y = 0;

        while (x>=0 && y<h) {
            if(array[y][x] == target) {
                return true;
            }

            if (array[y][x]<target) {
                y++;
            } else {
                x--;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int[][] a = {{1,3,5,6},{2,4,7,8},{5,8,9,12}};
        System.out.println(new ArrayFind().Find(11,a));
    }

}

Verwandte Empfehlungen:

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