Résumé des questions courantes dans les entretiens Java (5)

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 的绳子，请把绳子剪成整数长的 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];

    }

Penser

 *
 * 使用动态规划
 * 要点：边界和状态转移公式
 * 使用顺推法：从小推到大
 * 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 {

    /**
     * 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
     * 例如，如果输入数组 {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;
    }

}

*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 的数组里的所有数字都在 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;
    }

*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!