Summary of common array questions in Java interviews (1)

Difficulty of the question: * *

(Learning video recommendation: java course)

1. Sorting order

[Title]

Returns the sorted value of a numeric array. For example, the return value of data [6,2,5,0] is [4,2,3,1]

[ Code]

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

}

[Thinking]

The normal way to obtain the order is to compare each element with all other elements, and then obtain the size order, but here the ladder comparison order is used

6
6 2
6 2 5
6 2 5 0

When comparing, not only the comparison element is judged, but also the compared element, which is the if else code, can reduce the number of comparisons.

2. Array subscript auxiliary record

[Title]

Given an array a, the length is N, the element value range is [1, N], statistics The number of occurrences of each element requires a time complexity of O (N) and a space complexity of O (1)

[Code]

/**
     * 这类要求空间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]--;
            }
        }

    }

(Recommended graphic tutorial: java Interview questions and answers)

3. Find the elements of an ordered two-dimensional array

[Title]

In a two-dimensional array (each one-dimensional arrays are of the same length), each row is sorted in increasing order from left to right, and each column is sorted in increasing order from top to bottom. Please complete a function, input such a two-dimensional array and an integer, and determine whether the array contains the integer.

[Code]

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

}

[Thinking]

Starting from the upper left, there are too many situations to consider, because going right and downward both increase, but starting from the upper right , decreases to the left and increases downward, thus limiting the situation to one type. Special arrays, make full use of the particularity of arrays, and consider methods from different directions.

4. Jumping steps

[Title]

A frog can jump up to 1 level or 2 steps at a time. Find out how many ways the frog can jump up an n-level step (different results will be calculated in different orders).

[Code]

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. Abnormal Jumping Stairs

[Title]

A frog can jump up to 1 step at a time, and can also jump Go up level 2... It can also jump up level n. Find the total number of ways the frog can jump up an n-level staircase.

【Code】

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

Related recommendations: Getting Started with Java

The above is the detailed content of Summary of common array questions in Java interviews (1). For more information, please follow other related articles on the PHP Chinese website!