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

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;
        // 元素个数
        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;
    }

[Denken]

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 {

    /**
     * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * 例如输入一个长度为 9 的数组 {1,2,3,2,2,2,5,4,2}。
     * 由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 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];

        // 标记数组
        int[] flag = new int[n];
        // 给数组排序
        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:

Java-Interviewfragen und -antworten

)

【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出现的次数（相减之后）
        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半数
        for(int i=0; i < array.length; i++)
            if(array[i] == preValue)
                num++;
        return (num > array.length/2)?preValue:0;
 
    }

[Denken]

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]

	/**
     * 给一个数组，返回它的最大连续子序列的和
     *
     * 例如:{6,-3,-2,7,-15,1,2,2}, 连续子向量的最大和为 8 (从第 0 个开始，到第 3 个为止)
     *
     * 非常典型的dp
     *
     * 动规通常分为顺推和逆推两个不同的方向
     * 要素：边界，状态转移公式，数组代表含义
     * array[]
     * dp[x],从各个正数开始连续到达x时，最大和，即连续子序列的最大和
     * 需要注意：1.从第一个正数开始，2.是连续序列
     * 通常情况下，连续序列的复杂度为O(n),非连续序列为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 的数称作丑数（Ugly Number）。
     * 例如 6、8 都是丑数，但 14 不是，因为它包含质因子 7。
     * 习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 N 个丑数。
     *
     * 从已有的丑数中选取一个，分别*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:

Erste Schritte mit Java

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!