Bewertung: *****

1. Drucken Sie die Matrix im Uhrzeigersinn aus Wenn Sie beispielsweise die folgenden 4 eingeben: 12,16,15,14,13,9,5,6,7,11,10.

[Code]

public ArrayList<Integer> printMatrix(int [][] matrix) {

        int width,height,x,y,count,n;
        height = matrix.length;
        width = matrix[0].length;
        // 遍歷游標
        x = 0;
        y = 0;
        count = 0;
        // 元素個數(shù)
        n = height * width;

        boolean[][] flag = new boolean[height][width];
        ArrayList<Integer> list = new ArrayList<>();

        while (count < n) {
            // x不變，y增加
            while (y<width && !flag[x][y]) {
                list.add(matrix[x][y]);
                flag[x][y] = true;
                count ++;
                y ++;
            }
            y--;
            x++;
            // x增加，y不變
            while (x<height && !flag[x][y]) {
                list.add(matrix[x][y]);
                flag[x][y] = true;
                count ++;
                x ++;
            }
            x--;
            y--;
            // x不變，y減少
            while (y>=0 && !flag[x][y]) {
                list.add(matrix[x][y]);
                flag[x][y] = true;
                count ++;
                y--;
            }
            y++;
            x--;
            // x變少，y不變
            while (x>=0 && !flag[x][y]) {
                list.add(matrix[x][y]);
                flag[x][y] = true;
                count ++;
                x--;
            }
            x++;
            y++;
        }


        return list;
    }

Sie ben?tigen Achten Sie darauf, ob die Grenze überschritten wird und der Cursor (x, y) durch x++ verl?uft. Oder nach y++, wo sich die Positionierung befindet, ist eine manuelle Drehung erforderlich.

2. Eine Zahl, die mehr als die H?lfte der Zeit im Array vorkommt

[Titel]

Es gibt eine Zahl im Array, die mehr als die H?lfte der L?nge des Arrays vorkommt. Geben Sie beispielsweise ein Array {1,2,3,2,2,2,5,4,2} mit einer L?nge von 9 ein. Da die Zahl 2 fünfmal im Array vorkommt, was mehr als der halben L?nge des Arrays entspricht, wird 2 ausgegeben. Wenn nicht vorhanden, wird 0 ausgegeben.

【Code】

package swear2offer.array;

import java.util.Arrays;

public class Half {

    /**
     * 數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。
     * 例如輸入一個長度為 9 的數(shù)組 {1,2,3,2,2,2,5,4,2}。
     * 由于數(shù)字 2 在數(shù)組中出現(xiàn)了 5 次，超過數(shù)組長度的一半，因此輸出 2。如果不存在則輸出 0。
     * */
    public int MoreThanHalfNum_Solution(int [] array) {

        int n,count,i,k;

        n = array.length;

        if (n == 0) return 0;

        if (n == 1) return array[0];

        // 標記數(shù)組
        int[] flag = new int[n];
        // 給數(shù)組排序
        Arrays.sort(array);

        count = 1;
        flag[0] = 1;
        for (i=1; i<n; i++) {
            // 因為是排序好的，如果存在相等的
            if (array[i-1] == array[i]) {
                count ++;
            } else {
                count = 1;
            }
            flag[i] = count;
        }

        count = 0;
        k = 0;
        for (i=1; i<n; i++) {
            if (count < flag[i]) {
                count = flag[i];
                k = i;
            }
        }

        return count > n/2 ? array[k] : 0;

    }
}

(Empfohlene verwandte Interviewfragen:

)

【Code 2】

Geniale Methode für unn?tiges Sortieren:

Verwenden Sie preValue, um den Wert des letzten Besuchs aufzuzeichnen, z?hlen Gibt an, wie oft der aktuelle Wert mit dem aktuellen Wert übereinstimmt. Wenn er sich von count– unterscheidet, muss der neue Wert preValue ersetzt werden, wenn er auf 0 sinkt ein Wert, der die halbe L?nge des Arrays überschreitet, dann der letzte preValue Es muss dieser Wert sein.

	public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0)return 0;
        int preValue = array[0];//用來記錄上一次的記錄
        int count = 1;//preValue出現(xiàn)的次數(shù)（相減之后）
        for(int i = 1; i < array.length; i++){
            if(array[i] == preValue)
                count++;
            else{
                count--;
                if(count == 0){
                    preValue = array[i];
                    count = 1;
                }
            }
        }
        int num = 0;//需要判斷是否真的是大于1半數(shù)
        for(int i=0; i < array.length; i++)
            if(array[i] == preValue)
                num++;
        return (num > array.length/2)?preValue:0;
 
    }

Wenn ich bei 1 statt bei 0 beginne, ist normalerweise besondere überlegung erforderlich, wenn nur ein Element vorhanden ist.

3 Die maximale Summe aufeinanderfolgender Unterarrays Die Summe seiner maximal aufeinanderfolgenden Teilsequenzen, zum Beispiel: {6,-3,-2,7,-15,1,2,2}, die maximale Summe aufeinanderfolgender Teilvektoren betr?gt 8 (beginnend vom 0. bis zum 3.)

[Code]

	/**
     * 給一個數(shù)組，返回它的最大連續(xù)子序列的和
     *
     * 例如:{6,-3,-2,7,-15,1,2,2}, 連續(xù)子向量的最大和為 8 (從第 0 個開始，到第 3 個為止)
     *
     * 非常典型的dp
     *
     * 動規(guī)通常分為順推和逆推兩個不同的方向
     * 要素：邊界，狀態(tài)轉移公式，數(shù)組代表含義
     * array[]
     * dp[x],從各個正數(shù)開始連續(xù)到達x時，最大和，即連續(xù)子序列的最大和
     * 需要注意：1.從第一個正數(shù)開始，2.是連續(xù)序列
     * 通常情況下，連續(xù)序列的復雜度為O(n),非連續(xù)序列為O(n*n)
     * */
    public int FindGreatestSumOfSubArray(int[] array) {
        int n,i,len,res;
        int[] dp;

        n = array.length;

        if (n == 0 || array == null) return 0;
        if (n == 1) return array[0];

        dp = new int[n];
        dp[0] = array[0];
        len = 0;
        res = array[0];
        for (i=1; i<n; i++) {
            len = dp[i-1] + array[i];

            if (dp[i-1] < 0) {
                dp[i] = array[i];
            } else {
                dp[i] = len;
            }

            if (res < dp[i]) res = dp[i];
        }

        return res;
    }

[Idee]

Durchlauf von vorne nach hinten Die Summe der gr??ten kontinuierlichen Teilfolge wird durch überlagerung des aktuellen Elements und der Summe der vorherigen gr??ten kontinuierlichen Teilfolge gebildet. Wenn die Summe der vorherigen gr??ten kontinuierlichen Teilfolge gr??er als Null ist, k?nnen wir mit der Akkumulation fortfahren. Wenn sie kleiner als Null ist, müssen wir die vorherige Teilfolge verwerfen und erneut mit der Akkumulation beginnen. Die Zeitkomplexit?t betr?gt O (n)

4. Die Anzahl der Vorkommen von 1 in ganzen Zahlen

[Titel]

Finden Sie die Anzahl der Vorkommen von 1 in ganzen Zahlen von 1 bis 13 und berechnen Sie die Anzahl der Vorkommen von 1 in ganze Zahlen von 100 bis 1300 ? Aus diesem Grund z?hlte er speziell die Zahlen, die 1 enthielten, von 1 bis 13. Es waren 1, 10, 11, 12 und 13, also kamen sie insgesamt sechsmal vor, aber er war ratlos für die n?chste Frage. ACMer hofft, dass Sie ihm helfen und das Problem allgemeiner gestalten k?nnen, sodass er schnell die H?ufigkeit des Vorkommens von 1 in jedem nichtnegativen ganzzahligen Intervall ermitteln kann (die H?ufigkeit des Auftretens von 1 von 1 bis n).

[Code]

public int NumberOf1Between1AndN_Solution(int n) {
        if (n == 1) return 1;

        int nCount,i,j;
        nCount = 0;

        for (i=1; i<=n; i++) {
            j = i;
            while (j > 0) {
                if (j%10 == 1) nCount++;
                j = j/10;
            }
        }

        return nCount;

    }

[Denken]

Verwenden Sie zum Schreiben keine Rekursion, die einfachste Schleife reicht aus

5. H?ssliche Zahlen

[Titel]

Nennen Sie die Zahlen, die nur die Primfaktoren 2, 3 enthalten und 5 H?ssliche Zahl. Zum Beispiel sind 6 und 8 beide h?ssliche Zahlen, 14 jedoch nicht, weil sie den Primfaktor 7 enth?lt. Es ist üblich, dass wir 1 als die erste h?ssliche Zahl betrachten. Finden Sie die N-te h?ssliche Zahl in aufsteigender Reihenfolge.

【Code】

	/**
     * 把只包含質因子 2、3 和 5 的數(shù)稱作丑數(shù)（Ugly Number）。
     * 例如 6、8 都是丑數(shù)，但 14 不是，因為它包含質因子 7。
     * 習慣上我們把 1 當做是第一個丑數(shù)。求按從小到大的順序的第 N 個丑數(shù)。
     *
     * 從已有的丑數(shù)中選取一個，分別*2，*3，*5，再取最小的
     * 最小的索引++，并賦值
     * */
    public int GetUglyNumber_Solution(int index) {
        if (index == 0) return 0;

        int p2,p3,p5,i,temp;

        p2 = p3 = p5 = 0;

        int[] res = new int[index];
        res[0] = 1;

        for (i=1; i<index; i++) {

            res[i] = Math.min(res[p2]*2,Math.min(res[p3]*3,res[p5]*5));

            if (res[i] == res[p2]*2) p2++;
            if (res[i] == res[p3]*3) p3++;
            if (res[i] == res[p5]*5) p5++;
        }

        return res[index-1];
    }

【Denken】

Beim Sortieren einer Sequenz mit bestimmten Eigenschaften k?nnen Sie diese Methode in Betracht ziehen.

Verwandte Empfehlungen:

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