Summary of common array questions in Java interviews (3)

Star rating: *****

1. Print the matrix clockwise

(Learning video sharing: java course）

[Title]

Enter a matrix and print out each number in clockwise order from outside to inside. For example, if you enter the following 4 X 4 matrix: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 then print out the numbers 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10 in sequence.

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

[Thinking]

You need to pay attention to whether the boundary is out of bounds and where the cursor (x, y) is positioned after passing x or y. Make manual turns.

2. A number that appears more than half the time in the array

[Title]

There is a number in the array that appears more than half the time of the array. Please find this number. . For example, enter an array {1,2,3,2,2,2,5,4,2} with a length of 9. Since the number 2 appears 5 times in the array, which is more than half the length of the array, 2 is output. If not present, output 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;

    }
}

(Recommended related interview questions: java interview questions and answers)

【Code 2】

Clever method of unnecessary sorting:

Use preValue to record the value of the last visit, count indicates the number of times the current value appears, if the next value is the same as the current value then count; if different count–, reduce to 0 It is necessary to replace the new preValue value, because if there is a value that exceeds half the length of the array, then the final preValue will definitely be this value.

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

[Thinking]

When i starts from 1 instead of 0, special consideration is usually needed when there is only one element

3. The maximum sum of consecutive subarrays

[Title]

Given an array, return the sum of its largest continuous subsequence, for example: {6,-3,-2,7,-15,1,2,2 }, the maximum sum of consecutive subvectors is 8 (starting from the 0th and ending with the 3rd)

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

[Ideas]

Go from After traversal, the sum of the largest continuous subsequence is formed by superimposing the current element and the sum of the previous largest continuous subsequence. If the sum of the previous largest continuous subsequence is greater than zero, we can continue to accumulate. If it is less than zero, we need to discard the previous subsequence and start accumulating again from the current number. The time complexity is O (n)

4. The number of occurrences of 1 in integers

[Title]

Find the number of occurrences of 1 in integers from 1 to 13, And count the number of times 1 appears in the integers from 100 to 1300? For this reason, he specially counted the numbers containing 1 from 1 to 13. They were 1, 10, 11, 12, and 13, so they appeared 6 times in total, but he was at a loss for the next question. ACMer hopes that you can help him and make the problem more general, so that he can quickly find the number of occurrences of 1 in any non-negative integer interval (the number of occurrences of 1 from 1 to 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;

    }

[Thinking]

Don’t use recursion to write, the simplest loop will do

5, ugly numbers

[Title]

The numbers containing only prime factors 2, 3 and 5 are called ugly numbers. For example, 6 and 8 are both ugly numbers, but 14 is not because it contains the prime factor 7. It is customary for us to regard 1 as the first ugly number. Find the Nth ugly number in ascending order.

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

[Thinking]

This method can be considered when sorting sequences with certain properties.

Related recommendations:Getting started with java

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