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;
        // 遍歷游標(biāo)
        x = 0;
        y = 0;
        count = 0;
        // 元素個數(shù)
        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 {

    /**
     * 數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。
     * 例如輸入一個長度為 9 的數(shù)組 {1,2,3,2,2,2,5,4,2}。
     * 由于數(shù)字 2 在數(shù)組中出現(xiàn)了 5 次，超過數(shù)組長度的一半，因此輸出 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];

        // 標(biāo)記數(shù)組
        int[] flag = new int[n];
        // 給數(shù)組排序
        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出現(xiàn)的次數(shù)（相減之后）
        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半數(shù)
        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]

	/**
     * 給一個數(shù)組，返回它的最大連續(xù)子序列的和
     *
     * 例如:{6,-3,-2,7,-15,1,2,2}, 連續(xù)子向量的最大和為 8 (從第 0 個開始，到第 3 個為止)
     *
     * 非常典型的dp
     *
     * 動規(guī)通常分為順推和逆推兩個不同的方向
     * 要素：邊界，狀態(tài)轉(zhuǎn)移公式，數(shù)組代表含義
     * array[]
     * dp[x],從各個正數(shù)開始連續(xù)到達(dá)x時，最大和，即連續(xù)子序列的最大和
     * 需要注意：1.從第一個正數(shù)開始，2.是連續(xù)序列
     * 通常情況下，連續(xù)序列的復(fù)雜度為O(n),非連續(xù)序列為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]

	/**
     * 把只包含質(zhì)因子 2、3 和 5 的數(shù)稱作丑數(shù)（Ugly Number）。
     * 例如 6、8 都是丑數(shù)，但 14 不是，因為它包含質(zhì)因子 7。
     * 習(xí)慣上我們把 1 當(dāng)做是第一個丑數(shù)。求按從小到大的順序的第 N 個丑數(shù)。
     *
     * 從已有的丑數(shù)中選取一個，分別*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!