1. Le nombre de fois qu'un nombre appara?t dans le tableau trié

[Titre]

Comptez le nombre de fois qu'un nombre appara?t dans le tableau trié. tableau trié.

(Recommandation vidéo d'apprentissage?: Tutoriel vidéo Java)

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

[Pensée]

Puisque le tableau est un tableau trié, donc la recherche binaire peut être utilisée pour localiser la première et la dernière occurrence de k. La complexité temporelle est O(logN)O(logN)

Condition préalable à la recherche binaire?:?ordre (quand il s'agit d'ordre). , il faut immédiatement penser à deux points !)

Trouver 1+2+3+…+n

[Titre]

Trouver 1+2 +3+ …+n, il est nécessaire que les mots-clés tels que multiplication et division, for, while, if, else, switch, case et les déclarations de jugement conditionnel (A?B:C) ne puissent pas être utilisés.

[Code]

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

Pensée]

exige que les boucles et les jugements ne puissent pas être utilisés, donc la récursivité est utilisée à la place des boucles, et le principe de court-circuit est utilisé à la place de jugements

L'ordre de court-circuit et d'exécution est de gauche à droite. Après avoir déterminé que la valeur de la première expression est fausse, il n'est pas nécessaire d'exécuter la deuxième instruction conditionnelle. Car il est évident que peu importe si la deuxième condition est vraie ou fausse, la valeur booléenne de l’expression entière doit être fausse. Le court-circuit ignorera la deuxième condition et ne l'exécutera pas. Sur la base de ces principes, les résultats ci-dessus ont émergé. L'utilisation flexible du court-circuit et de la programmation est d'une grande importance.

Lorsque n=0, sum=0, ce qui suit && ne sera pas exécuté, et sum=0 est renvoyé directement

Coupez la corde

[Sujet]

Vous recevez une corde de longueur n. Veuillez couper la corde en m segments de longueur entière (m et n sont tous deux des nombres entiers, n>1 et m>1). enregistré comme k [0],k[1],…,k[m]. Quel est le produit maximum possible de k [0] xk [1] x...xk [m] ? Par exemple, lorsque la longueur de la corde est de 8, nous la coupons en trois morceaux de longueurs respectivement 2, 3 et 3. Le produit maximum obtenu à ce moment est de 18.

[Code]

    /**
     * 給你一根長度為 n 的繩子，請把繩子剪成整數(shù)長的 m 段（m、n 都是整數(shù)，n>1 并且 m>1），
     * 每段繩子的長度記為 k [0],k [1],...,k [m]。
     * 請問 k [0] xk [1] x...xk [m] 可能的最大乘積是多少？
     * 例如，當繩子的長度是 8 時，
     * 我們把它剪成長度分別為 2、3、3 的三段，此時得到的最大乘積是 18。
     *
     * 使用動態(tài)規(guī)劃
     * 要點：邊界和狀態(tài)轉移公式
     * 使用順推法：從小推到大
     * 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是劃分的乘積小于自身，對狀態(tài)轉移會產生額外判斷
        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];

    }

Penser

 *
 * 使用動態(tài)規(guī)劃
 * 要點：邊界和狀態(tài)轉移公式
 * 使用順推法：從小推到大
 * dp[x] 代表x的最大值
 * dp[x] = max{d[x-1]*1,dp[x-2]*2,dp[x-3]*3,,,,},不需要全遍歷，取半即可
 * 但是需要注意。2和3這兩個特殊情況，因為他們的分解乘積比自身要大，所以特殊處理

(Plus de questions d'entretien connexes à partager?: questions et réponses d'entretien Java)

4. La valeur maximale de la fenêtre coulissante

[Sujet]

étant donné un tableau et la taille de la fenêtre coulissante, trouver la valeur maximale de toutes les valeurs du fenêtre coulissante. Par exemple, si le tableau d'entrée est {2,3,4,2,6,2,5,1} et que la taille de la fenêtre glissante est 3, alors il y a un total de 6 fenêtres glissantes et leurs valeurs maximales ??sont {4,4,6, 6,6,5}?; Il existe les 6 fenêtres glissantes suivantes pour le tableau {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 {

    /**
     * 給定一個數(shù)組和滑動窗口的大小，找出所有滑動窗口里數(shù)值的最大值。
     * 例如，如果輸入數(shù)組 {2,3,4,2,6,2,5,1} 及滑動窗口的大小 3，
     * 那么一共存在 6 個滑動窗口，他們的最大值分別為 {4,4,6,6,6,5}
     *
     * 思路：
     * 先找出最開始size大小的最大值，以及這個最大值的下標
     * 然后每次增加一個值，先判斷滑動窗口的第一位下標是否超過保存最大值的下標
     * 如果超過就要重新計算size區(qū)域的最大值，
     * 如果未超過就使用最大值與新增的元素比較，獲取較大的
     * */
    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;

        // 當窗口大于數(shù)組長度
        if (num.length <= size) return list;

        // 把第一個滑動窗口最大值加入數(shù)組
        list.add(temp[0]);

        // 從新的窗口開始計算，上一個窗口的最大值和下標保存在temp中
        for (i=size; i<num.length; i++) {
            // 上一個最大值還在滑動窗口區(qū)域內
            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;
        // 當窗口大于數(shù)組長度
        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;
    }

}

*Idée :

*Trouver d'abord la valeur maximale de la taille initiale, et l'indice de cette valeur maximale

* Ensuite, à chaque fois qu'une valeur est ajoutée, déterminez d'abord si le premier indice de la fenêtre glissante dépasse l'indice qui enregistre la valeur maximale

* S'il dépasse, recalculez la valeur maximale de la zone de taille,

* Si elle n'est pas dépassée, utilisez la valeur maximale pour comparer avec le nouvel élément afin d'obtenir un

Supplément supplémentaire plus grand : Pour les exceptions levées, par exemple, dans cette question, le cas de size>num. la longueur est nulle, mais je pense que c'est le plus gros lancer, vous devriez communiquer avec l'intervieweur à ce moment-là.

5. Nombres répétés dans le tableau

[Titre]

Tous les nombres dans un tableau de longueur n sont compris entre 0 et n-1. Certains nombres du tableau sont répétés, mais je ne sais pas combien de nombres sont répétés. Je ne sais pas combien de fois chaque numéro est répété. Veuillez trouver tout numéro répété dans le tableau. Par exemple, si l'entrée est un tableau {2,3,1,0,2,5,3} de longueur 7, la sortie correspondante est le premier nombre répété 2.

[Code]

    /**
     * 在一個長度為 n 的數(shù)組里的所有數(shù)字都在 0 到 n-1 的范圍內。
     * 數(shù)組中某些數(shù)字是重復的，但不知道有幾個數(shù)字是重復的。
     * 也不知道每個數(shù)字重復幾次。請找出數(shù)組中任意一個重復的數(shù)字。
     * 例如，如果輸入長度為 7 的數(shù)組 {2,3,1,0,2,5,3}，
     * 那么對應的輸出是第一個重復的數(shù)字 2。
     *
     * 思路：
     * 看到 長度n，內容為0-n-1；瞬間就應該想到，元素和下標的轉換
     *
     * 下標存的是元素的值，對應的元素存儲出現(xiàn)的次數(shù)，
     * 為了避免弄混次數(shù)和存儲元素，把次數(shù)取反，出現(xiàn)一次則-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) {
            // 獲取到數(shù)組元素
            res = numbers[i];
            // 判斷對應位置的計數(shù)是否存在
            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;
    }

*Idée :

*Quand vous voyez la longueur n et que le contenu est 0-n-1 vous devez immédiatement penser à la conversion de ; éléments et indices

* L'indice stocke la valeur de l'élément, et l'élément correspondant stocke le nombre d'occurrences

* Afin d'éviter toute confusion entre le nombre et l'élément stocké, le. le nombre est inversé. S'il appara?t une fois, -1. Deux fois puis -2

* échangez la position calculée avec l'élément non calculé, vous pouvez utiliser n à la place

Recommandations associées?: Démarrez avec Java

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!