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

Note par étoiles : *****

1. Imprimer la matrice dans le sens des aiguilles d'une montre

(Partage de vidéos d'apprentissage : cours Java )

[Titre]

Saisissez une matrice et imprimez chaque nombre dans le sens des aiguilles d'une montre de l'extérieur vers l'intérieur. Par exemple, si vous saisissez la matrice 4 X 4 suivante : 1 2 3. 4 5 6 7 8 9 10 11 12 13 14 15 16 puis imprimez les nombres 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10 dans séquence.

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

[Pensée]

Vous devez faire attention à savoir si la limite est hors limites et où se trouve le curseur (x, y). positionné après avoir passé x++ ou y++. Effectuer des virages manuels.

2. Un nombre qui apparaît plus de la moitié du temps dans le tableau

[Titre]

Il y a un nombre dans le tableau qui apparaît plus de la moitié de la longueur de le tableau. Veuillez trouver ce numéro. Par exemple, saisissez un tableau {1,2,3,2,2,2,5,4,2} d'une longueur de 9. Étant donné que le nombre 2 apparaît 5 fois dans le tableau, qui fait plus de la moitié de la longueur du tableau, 2 est affiché. S’il n’est pas présent, sortie 0.

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

    }
}

(questions d'entretien connexes recommandées : questions et réponses d'entretien Java)

[Code 2]

Méthode intelligente pour un tri inutile :

Utilisez preValue pour enregistrer la valeur de la dernière visite, le nombre indique le nombre de fois où la valeur actuelle apparaît, si la valeur suivante est la même que la valeur actuelle alors comptez++ si elle est différente ; count–, réduire à 0 Il est nécessaire de remplacer la nouvelle valeur preValue, car s'il y a une valeur qui dépasse la moitié de la longueur du tableau, alors la preValue finale sera définitivement cette valeur.

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

[Pensée]

Quand je part de 1 au lieu de 0, une attention particulière est généralement nécessaire lorsqu'il n'y a qu'un seul élément

3 La somme maximale des sous-tableaux consécutifs.

[Titre]

Étant donné un tableau, renvoie la somme de ses sous-séquences consécutives maximales, par exemple : {6,-3,-2,7,-15,1,2,2 }, la somme maximale des sous-vecteurs consécutifs est de 8 (du 0 au 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;
    }

[Idée]

Partir d'Après parcours , la somme de la plus grande sous-séquence continue est formée en superposant l'élément actuel et la somme de la plus grande sous-séquence continue précédente. Si la somme de la plus grande sous-séquence continue précédente est supérieure à zéro, nous pouvons continuer à accumuler. Si elle est inférieure à zéro, nous devons éliminer la sous-séquence précédente et recommencer à accumuler à partir du nombre actuel. La complexité temporelle est O (n)

4 Le nombre d'occurrences de 1 en entiers

[Titre]

Trouver le nombre d'occurrences de 1 en entiers à partir de 1. à 13, et compter le nombre de fois où 1 apparaît dans les nombres entiers de 100 à 1300 ? Pour cette raison, il a spécialement compté les nombres contenant 1 de 1 à 13. Ils étaient 1, 10, 11, 12 et 13, ils sont donc apparus 6 fois au total, mais il ne pouvait pas répondre à la question suivante. ACMer espère que vous pourrez l'aider et rendre le problème plus général, afin qu'il puisse trouver rapidement le nombre d'occurrences de 1 dans tout intervalle entier non négatif (le nombre d'occurrences de 1 de 1 à 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;

    }

[Pensée]

N'écrivez pas de manière récursive, la boucle la plus simple suffit

5 Nombres laids

【Titre】

Les nombres contenant uniquement les facteurs premiers 2, 3 et 5 sont appelés nombres laids. Par exemple, 6 et 8 sont tous deux des nombres laids, mais 14 ne l’est pas car il contient le facteur premier 7. Il est d’usage pour nous de considérer 1 comme le premier nombre laid. Trouvez le Nième nombre laid par ordre croissant.

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

[Pensée]

Cette méthode peut être envisagée lors du tri de séquences avec certaines propriétés.

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!