Java 面接でよくある配列に関する質問のまとめ (3)

星評価: *****

1. マトリックスを時計回りに印刷します

(学習ビデオ共有: Java コース）

[タイトル]

行列を入力し、外側から内側へ時計回りに各数値を出力します。たとえば、次の 4 X 4 行列を入力したとします。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 次に、数字 1、2、3、4、8、12、16、15、14、13、9、5、6、7、11、10 を順番に出力します。 .

[コード]

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

[考え方]

境界線が範囲外かどうかと、カーソル(x,y)がどこに位置するかに注意する必要があります。 x または y を通過した後、手動で回転します。

2. 配列内に半分以上出現する数値

[トピック]

配列内に、長さの半分以上出現する数値があります。配列。この番号を見つけてください。たとえば、長さが 9 の配列 {1,2,3,2,2,2,5,4,2} を入力します。数値 2 が配列内に 5 回出現し、これは配列の長さの半分を超えるため、2 が出力されます。存在しない場合は 0 を出力します。

【コード】

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;

    }
}

(推奨される関連する面接の質問: Java 面接の質問と回答)

【コード 2】

不要な並べ替えの賢い方法:

preValue を使用して最後の訪問の値を記録します。count は現在の値が表示された回数を示します。次の値が現在の値と同じ場合はカウントし、異なる場合はカウントします。 count–、0 に減らす 新しい preValue 値を置き換える必要があります。配列の長さの半分を超える値がある場合、最終的な preValue は間違いなくこの値になるためです。

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

[考え方]

i が 0 ではなく 1 から始まる場合、要素が 1 つしかない場合は通常、特別な考慮が必要です

3. 連続する部分配列の最大合計

[タイトル]

配列を指定すると、その最大の連続サブシーケンスの合計を返します。例: {6,-3,-2,7,-15,1,2,2 }、連続するサブベクトルの最大合計は 8 です (0 番目から始まり 3 番目で終わります)

[コード]

	/**
     * 给一个数组，返回它的最大连续子序列的和
     *
     * 例如:{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;
    }

[アイデア]

Go fromトラバース後、現在の要素と前の最大の連続サブシーケンスの合計を重ね合わせることで、最大の連続サブシーケンスの合計が形成されます。以前の最大の連続部分列の合計がゼロより大きい場合は、累積を続けることができますが、ゼロ未満の場合は、前の部分列を破棄し、現在の数値から再度累積を開始する必要があります。時間計算量は O (n)

4 整数中の 1 の出現数

[タイトル]

整数中の 1 の出現数を 1 から求めますから 13 まで、そして 100 から 1300 までの整数の中に 1 が現れる回数を数えてください。そこで、特別に1を含む数字を1から13まで数えました。1、10、11、12、13と合計6回出てきましたが、次の質問に困っていました。 ACMer は、あなたが彼を助け、問題をより一般的にして、負でない整数区間における 1 の出現数 (1 から n までの 1 の出現数) をすぐに見つけられるようにしてほしいと考えています。

[コード]

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;

    }

[考え方]

再帰を使用して記述しないでください。最も単純なループで実行できます。

5、醜い数字です

[タイトル]

素因数 2、3、5 のみを含む数値を醜い数値と呼びます。たとえば、6 と 8 はどちらも醜い数字ですが、14 には素因数 7 が含まれているため、醜い数字ではありません。私たちは 1 を最初の醜い数字とみなすのが通例です。 N 番目の醜い数値を昇順で見つけます。

[コード]

	/**
     * 把只包含质因子 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];
    }

[考え方]

この方法は、特定のプロパティを持つシーケンスをソートするときに考慮できます。

関連する推奨事項:Java の使用を開始する

以上がJava 面接でよくある配列に関する質問のまとめ (3)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。