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;
        // 元素個數(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;
    }

[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 {

    /**
     * 數(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];

        // 標記數(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;

    }
}

(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出現(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;
 
    }

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

	/**
     * 給一個數(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ù)到達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;
    }

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

	/**
     * 把只包含質(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];
    }

[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!