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

1. Die Häufigkeit, mit der eine Zahl im sortierten Array erscheint.

[Titel]

Zählt, wie oft eine Zahl im sortierten Array erscheint.

(Lernvideo-Empfehlung: Java-Video-Tutorial)

[Code]

public int GetNumberOfK(int [] array , int k) {

        if (array.length==0 || array==null) return 0;

        int i,n,count;
        n = array.length;

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

        return count;
    }

    public int high(int[] a, int k) {
        int start,end,mid;

        start = 0;
        end = a.length-1;

        while (start <= end) {
            mid = (start + end) >> 1;
            if (a[mid] <= k) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return end;
    }

    public int low(int[] a, int k) {
        int start,end,mid;

        start = 0;
        end = a.length-1;

        while (start <= end) {
            mid = (start + end) >> 1;
            if (a[mid] >= k) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return start;
    }

[Denken]

Da es sich bei dem Array um ein sortiertes Array handelt, können Sie die binäre Suchmethode verwenden, um das erste Vorkommen von k und the zu finden Die letzte Position des Vorkommens beträgt O(logN)O(logN)

Die Prämisse von zwei Punkten: Ordnung (wenn es um Ordnung geht, müssen Sie sofort an zwei Punkte denken!)

2 3+ …+n

[Titel]

Finde 1+2+3+…+n Es ist erforderlich, dass Sie keine Multiplikation und Division, für while, if, else, switch, case und andere Schlüsselwörter und Bedingungen verwenden können Urteilsaussagen (A?B:C).

【Code】

	public int Sum_Solution(int n) {
        int sum = n;
        boolean flag = (sum > 0) && (sum += Sum_Solution(n-1))>0;
        return sum;
    }

Denken】

erfordert, dass Schleifen und Urteile nicht verwendet werden können, daher wird Rekursion anstelle von Schleifen verwendet und das Kurzschlussprinzip wird anstelle von Urteilen verwendet.

Die Reihenfolge von Kurzschluss und Ausführung ist von links nach rechts, nachdem die erste Bedingungsanweisung ermittelt wurde. Nachdem der Ausdruck als falsch ausgewertet wurde, muss die zweite bedingte Anweisung nicht ausgeführt werden. Denn es ist offensichtlich, dass unabhängig davon, ob die zweite Bedingung wahr oder falsch ist, der boolesche Wert des gesamten Ausdrucks falsch sein muss. Durch einen Kurzschluss wird die zweite Bedingung übersprungen und nicht ausgeführt. Basierend auf diesen Prinzipien entstanden die oben genannten Ergebnisse. Der flexible Einsatz von Kurzschlüssen und in der Programmierung ist von großer Bedeutung.

Wenn n = 0, Summe = 0, wird das Folgende && nicht ausgeführt und Summe = 0 wird direkt zurückgegeben

3 Schneiden Sie das Seil ab

[Titel]

Ich gebe Ihnen ein Seil der Länge n, Bitte schneiden Sie das Seil in m Abschnitte ganzzahliger Länge (m und n sind beide ganze Zahlen, n>1 und m>1), und die Länge jedes Seilabschnitts wird als k [0], k [1], ... aufgezeichnet. ., k [m]. Was ist das maximal mögliche Produkt von k [0] xk [1] x...xk [m]? Wenn die Länge des Seils beispielsweise 8 beträgt, schneiden wir es in drei Stücke mit den Längen 2, 3 und 3. Das maximal erhaltene Produkt beträgt zu diesem Zeitpunkt 18.

[Code]

    /**
     * 给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（m、n 都是整数，n>1 并且 m>1），
     * 每段绳子的长度记为 k [0],k [1],...,k [m]。
     * 请问 k [0] xk [1] x...xk [m] 可能的最大乘积是多少？
     * 例如，当绳子的长度是 8 时，
     * 我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18。
     *
     * 使用动态规划
     * 要点：边界和状态转移公式
     * 使用顺推法：从小推到大
     * dp[x] 代表x的最大值
     * dp[x] = max{d[x-1]*1,dp[x-2]*2,dp[x-3]*3,,,,},不需要全遍历，取半即可
     * */
    public int cutRope(int target) {

        // 由于2,3是划分的乘积小于自身，对状态转移会产生额外判断
        if (target <= 3) return target-1;
        int[] dp = new int[target+1];
        int mid,i,j,temp;

        // 设定边界
        dp[2] = 2;
        dp[3] = 3;

        for (i=4; i<=target; i++) {
            // 遍历到中间即可
            mid = i >> 1;
            // 暂存最大值
            temp = 0;
            for (j=1; j<=mid; j++) {
                if (temp < j*dp[i-j]) {
                    temp = j*dp[i-j];
                }
            }
            dp[i] = temp;
        }

        return dp[target];

    }

Denken

 *
 * 使用动态规划
 * 要点：边界和状态转移公式
 * 使用顺推法：从小推到大
 * dp[x] 代表x的最大值
 * dp[x] = max{d[x-1]*1,dp[x-2]*2,dp[x-3]*3,,,,},不需要全遍历，取半即可
 * 但是需要注意。2和3这两个特殊情况，因为他们的分解乘积比自身要大，所以特殊处理

(Weitere verwandte Interviewfragen zum Teilen: Java-Interviewfragen und -antworten)

4. Der maximale Wert des Schiebefensters

[Frage]

Angesichts eines Arrays und Die Größe des Schiebefensters und den Maximalwert aller Werte im Schiebefenster ermitteln. Wenn das Eingabearray beispielsweise {2,3,4,2,6,2,5,1} ist und die Größe des Schiebefensters 3 beträgt, gibt es insgesamt 6 Schiebefenster und deren Maximalwerte ​are {4,4,6, 6,6,5} Es gibt die folgenden 6 Schiebefenster für das Array {2,3,4,2,6,2,5,1}: {[2,3, 4],2,6,2,5 ,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5 ,1}, {2,3,4 ,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4 ,2,6,[2,5, 1]}.

【Code】

package swear2offer.array;

import java.util.ArrayList;

public class Windows {

    /**
     * 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
     * 例如，如果输入数组 {2,3,4,2,6,2,5,1} 及滑动窗口的大小 3，
     * 那么一共存在 6 个滑动窗口，他们的最大值分别为 {4,4,6,6,6,5}
     *
     * 思路：
     * 先找出最开始size大小的最大值，以及这个最大值的下标
     * 然后每次增加一个值，先判断滑动窗口的第一位下标是否超过保存最大值的下标
     * 如果超过就要重新计算size区域的最大值，
     * 如果未超过就使用最大值与新增的元素比较，获取较大的
     * */
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        int i;
        int[] temp;
        temp = getMax(num,0,size);

        if (size<=0 || num==null || num.length==0) return list;

        // 当窗口大于数组长度
        if (num.length <= size) return list;

        // 把第一个滑动窗口最大值加入数组
        list.add(temp[0]);

        // 从新的窗口开始计算，上一个窗口的最大值和下标保存在temp中
        for (i=size; i<num.length; i++) {
            // 上一个最大值还在滑动窗口区域内
            if (i-size < temp[1]) {
                if (temp[0] < num[i]) {
                    temp[0] = num[i];
                    temp[1] = i;
                }
            } else {
                temp = getMax(num,i-size+1,size);
            }
            list.add(temp[0]);
        }

        return list;
    }

    public int[] getMax (int[] num, int s, int size) {
        int [] res = new int[2];
        int e = s + size;
        // 当窗口大于数组长度
        if (e>num.length) e = num.length;

        int temp = Integer.MIN_VALUE;
        int k = 0;
        for (int i=s; i<e; i++) {
            if (temp < num[i]) {
                temp = num[i];
                k = i;
            }
        }

        res[0] = temp;
        res[1] = k;

        return res;
    }

}

* Idee:

* Zuerst den Maximalwert der Anfangsgröße und den Index dieses Maximalwerts ermitteln

* Dann jedes Mal, wenn Sie einen Wert hinzufügen, zuerst die erste Position des Schiebefensters bestimmen Ob der Index den Index überschreitet, der den Maximalwert speichert

* Wenn er überschritten wird, berechnen Sie den Maximalwert des Größenbereichs neu.

* Wenn er nicht überschritten wird, verwenden Sie den Maximalwert, um ihn mit dem neuen Element zu vergleichen, um einen größeren Wert zu erhalten

Zusätzliche Ergänzung: Bei ausgelösten Ausnahmen wie dieser Frage wird null geworfen, wenn size> num.length geworfen wird. Ich denke jedoch, dass dies der größte Wurf ist. Sie sollten zu diesem Zeitpunkt mit dem Interviewer kommunizieren.

5. Wiederholte Zahlen im Array

[Titel]

Alle Zahlen in einem Array der Länge n liegen im Bereich von 0 bis n-1. Einige Zahlen im Array werden wiederholt, aber ich weiß nicht, wie viele Zahlen wiederholt werden. Ich weiß nicht, wie oft jede Zahl wiederholt wird. Suchen Sie nach wiederholten Zahlen im Array. Wenn die Eingabe beispielsweise ein Array {2,3,1,0,2,5,3} der Länge 7 ist, ist die entsprechende Ausgabe die erste wiederholte Zahl 2.

【Code】

    /**
     * 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。
     * 数组中某些数字是重复的，但不知道有几个数字是重复的。
     * 也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
     * 例如，如果输入长度为 7 的数组 {2,3,1,0,2,5,3}，
     * 那么对应的输出是第一个重复的数字 2。
     *
     * 思路：
     * 看到 长度n，内容为0-n-1；瞬间就应该想到，元素和下标的转换
     *
     * 下标存的是元素的值，对应的元素存储出现的次数，
     * 为了避免弄混次数和存储元素，把次数取反，出现一次则-1，两次则-2
     * 把计算过的位置和未计算的元素交换，当重复的时候，可以用n代替
     * */
    public boolean duplicate(int numbers[],int length,int [] duplication) {

        if (length == 0 || numbers == null) {
            duplication[0] = -1;
            return false;
        }

        int i,res;
        i = 0;
        while (i < length) {
            // 获取到数组元素
            res = numbers[i];
            // 判断对应位置的计数是否存在
            if (res < 0 || res == length) {
                i++;
                continue;
            }

            if (numbers[res] < 0) {
                numbers[res] --;
                numbers[i] = length;
                continue;
            }

            numbers[i] = numbers[res];
            numbers[res] = -1;
        }

        res = 0;
        for (i=0; i<length; i++) {
            if (numbers[i] < -1) {
                duplication[res] = i;
                return true;
            }
        }

        return false;
    }

* Idee:

* Wenn Sie die Länge n sehen und der Inhalt 0-n-1 ist, sollten Sie sofort an die Konvertierung von Elementen und Indizes denken

* Der Index speichert den Wert von Das entsprechende Element speichert die Anzahl der Vorkommen.

* Um eine Verwechslung der Häufigkeit und der gespeicherten Elemente zu vermeiden, invertieren Sie die Zahl. Wenn sie einmal vorkommt, ist sie -1, und wenn sie zweimal vorkommt, es wird -2

* Tauschen Sie die berechnete Position mit dem nicht berechneten Element aus. Beim Wiederholen können Sie stattdessen n verwenden

Verwandte Empfehlungen: Erste Schritte mit Java

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