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

問題の難易度: * *

(学習ビデオの推奨: java コース)

1. 並べ替え順序

[タイトル]

数値配列のソートされた値を返します。たとえば、データ [6,2,5,0] の戻り値は [4,2,3,1] です。

[コード]

package swear2offer.array;

import java.util.Arrays;

public class SortSequence {
    /**
     * 返回一个数字数组的排序值
     * 比如数据 [6,2,5,0] 的返回是 [4,2,3,1]
     * */
    public int[] compare(int[] a) {
        int i,j,n;
        n = a.length;

        int [] c = new int[n];

		//数组下标从0开始，但是输出的次序从1开始，所以需要初始化数组为1
        for (i=0; i<n; i++) {
           c[i]++;
        }

        for (i=0; i<n; i++) {
            for (j=0; j<i; j++) {
                if (a[j]<a[i]) c[i]++;
                else c[j]++;
            }
        }

        return c;
    }

    public static void main(String[] args) {
        int[] a = {6,2,5,0};
        System.out.println(Arrays.toString(new SortSequence().compare(a)));
    }

}

[考え方]

順序を取得する通常の方法は、各要素を他のすべての要素と比較して、サイズの順序を取得することですが、ここではラダー比較順序を使用します

6
6 2
6 2 5
6 2 5 0

比較の際、比較要素だけでなく、比較要素であるif elseコードも判定することで比較回数を減らすことができます。

2. 配列添字補助レコード

[タイトル]

配列 a、長さは N、要素値の範囲は [1, N]、統計が与えられると、各要素の出現回数には、時間計算量 O (N) と空間計算量 O (1)

[コード]

/**
     * 这类要求空间O(1)时间复杂度为O(n)的问题
     * 需要在一次遍历并且不声明新数组的情况下求解，这种题目通常要求元素大小跟下标大小一致。
     * 所以通常考虑是利用数组存储的元素和数组下标来求解
     * 在本题中，数组的元素变成了下标，而数组内元素则表示之前元素出现的次数，0则代表不出现。
     * 为了区分元素和次数，可以把次数设定为负值
     * */
    public void Solution(int[] a) {
        int i,n,temp;
        n = a.length;

        i = 0;
        /**
         * 只有在temp小于0的时候才会推进循环
         * */
        while(i < n) {
            temp = a[i]-1;
            // 如果数组元素小于0，则代表该数已经被替换到其他地方或者已经被计数过从而被覆盖
            if (temp < 0) {
                i ++;
                continue;
            }
            // 把未记录的数保存在已经记录的位置上，并用负值保存数量
            if (a[temp]>0) {
                a[i] = a[temp];
                a[temp] = -1;
            } else {
                a[i] = 0; //该数据已经使用过，且表示元素i+1出现0次
                a[temp]--;
            }
        }

    }

(推奨グラフィック チュートリアル: java インタビュー)質問と回答)

3. 順序付けられた 2 次元配列の要素を検索します

[タイトル]

2 次元配列 (それぞれ 1 つずつ)次元配列は同じ長さです)、各行は左から右に昇順にソートされ、各列は上から下に昇順にソートされます。関数を完成させ、二次元配列と整数を入力し、配列に整数が含まれているかどうかを判定してください。

[コード]

package swear2offer.array;

public class ArrayFind {

    /**
     * 在一个二维数组中（每个一维数组的长度相同），
     * 每一行都按照从左到右递增的顺序排序，
     * 每一列都按照从上到下递增的顺序排序。
     * 请完成一个函数，输入这样的一个二维数组和一个整数，
     * 判断数组中是否含有该整数。
     *
     * 思路：
     * 从左上出发，需要考虑的情况太多，因为向右和向下都是递增
     * 但是从右上出发，向左递减，向下递增，这样就把情况限定在一种。
     * */
    public boolean Find(int target, int [][] array) {

        int l,h,x,y;
        h = array.length;
        l = array[0].length;

        // 游标的横纵坐标
        x = l-1;
        y = 0;

        while (x>=0 && y<h) {
            if(array[y][x] == target) {
                return true;
            }

            if (array[y][x]<target) {
                y++;
            } else {
                x--;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int[][] a = {{1,3,5,6},{2,4,7,8},{5,8,9,12}};
        System.out.println(new ArrayFind().Find(11,a));
    }

}

[考え方]

左上から右に行く、下に行くと増えていくので考えられない状況が多すぎますが、右上、左に行くほど減少し、下に行くほど増加するため、状況は 1 つのタイプに限定されます。特殊な配列、配列の特性を最大限に活かし、さまざまな方向からの手法を検討します。

4. ジャンプステップ

[タイトル]

カエルは一度に 1 段または 2 段までジャンプできます。カエルが n レベルのステップをジャンプできる方法が何通りあるかを調べてください (異なる順序で異なる結果が計算されます)。

[コード]

package swear2offer.array;

public class Floors {

    /**
     * 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。
     * 求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
     *
     * 获取跳法次数
     * */
    public int JumpFloor(int target) {

        if (target < 3) return target;

        // 大于等于3个台阶，次数是第一步调1下和跳2下的个数之和
        return JumpFloor(target-1) + JumpFloor(target-2);

    }
}

5. 異常な階段ジャンプ

[タイトル]

カエルは一度に 1 段までジャンプでき、また、レベル 2 にジャンプします...レベル n にジャンプすることもできます。カエルが n 段の階段を飛び上がることができる方法の合計を求めます。

【コード】

package swear2offer.array;

import java.util.Arrays;

public class FloorsPlus {

    /**
     * 一只青蛙一次可以跳上 1 级台阶，
     * 也可以跳上 2 级…… 它也可以跳上 n 级。
     * 求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
     *
     * 动态规划：数组代表含义、边界、转换公式
     * 动态规划最重要的是找出阶段之间的变化公式，
     * 即，n-1和n之间的状态是如何转移的
     *
     * f[n]:n阶台阶的跳法
     * f[n] = f[n-1]+f[n-2]+...+f[1]+f[0]
     * f[n-1]代表最后一步走了1步
     * f[n-2]代表最后一步走了2步
     * f[1]代表最后一步走了n-1步
     * f[0]代表最后一步走了n步
     *
     * 这里需要注意，f[0]=0,但是最后一步走了n步也算一种方法，
     * 所以需要初始化把数组初始化为1，或则单独处理f[0].
     *
     * */
    public int JumpFloorII(int target) {
        if (target < 3) return target;
        int[] f = new int[target+1];
        //单独处理f[0]
        f[0] = 1;
        f[1] = 1;//边界

        int i,j;
        for (i=2; i<=target; i++) {
            for (j=i-1; j>=0; j--) {
                f[i] += f[j];
            }
        }

        return f[target];
    }
    
    public int JumpFloorII2(int target) {
        if (target < 3) return target;
        int[] f = new int[target+1];

        //初始化把数组初始化为1
        Arrays.fill(f,1);
        f[0] = 0;
        f[1] = 1;//边界

        int i,j;
        for (i=2; i<=target; i++) {
            for (j=i-1; j>0; j--) {
                f[i] += f[j];
            }
        }

        return f[target];
    }
}

関連する推奨事項: Java 入門

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