星級：*****

1、順時針打印矩陣

（學(xué)習(xí)視頻分享：java課程）

【題目】

輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數(shù)字，例如，如果輸入如下 4 X 4 矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字 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;
        // 遍歷游標(biāo)
        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;
    }

【思考】

需要注意邊界是否越界以及，游標(biāo)（x,y）經(jīng)過x++或者y++之后，定位在什么地方，需要進(jìn)行手動的轉(zhuǎn)彎。

2、數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

【題目】

數(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。

【代碼】

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

        // 標(biāo)記數(shù)組
        int[] flag = new int[n];
        // 給數(shù)組排序
        Arrays.sort(array);

        count = 1;
        flag[0] = 1;
        for (i=1; i<n; i++) {
            // 因?yàn)槭桥判蚝玫模绻嬖谙嗟鹊?            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;

    }
}

（相關(guān)面試題推薦：java面試題及答案）

【代碼2】

不需要的排序的巧妙方法：

用 preValue 記錄上一次訪問的值，count 表明當(dāng)前值出現(xiàn)的次數(shù)，如果下一個值和當(dāng)前值相同那么 count++；如果不同 count–，減到 0 的時候就要更換新的 preValue 值了，因?yàn)槿绻嬖诔^數(shù)組長度一半的值，那么最后 preValue 一定會是該值。

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

【思考】

當(dāng)i從1而不是0開始的時候，通常需要特殊考慮只有一個元素的情況

3、連續(xù)子數(shù)組的最大和

【題目】

給一個數(shù)組，返回它的最大連續(xù)子序列的和，例如:{6,-3,-2,7,-15,1,2,2}, 連續(xù)子向量的最大和為 8 (從第 0 個開始，到第 3 個為止)

【代碼】

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

【思路】

從前往后遍歷，最大的連續(xù)子序列的和是由當(dāng)前元素和之前的最大連續(xù)子序列的和疊加在一起形成的。如果之前的最大連續(xù)子序列的和大于零，我們可以繼續(xù)累加，如果小于零，則需要舍去之前的子序列，重新從當(dāng)前的數(shù)字開始累加。時間復(fù)雜度為 O (n)

4、整數(shù)中 1 出現(xiàn)的次數(shù)

【題目】

求出 1~13 的整數(shù)中 1 出現(xiàn)的次數(shù)，并算出 100~1300 的整數(shù)中 1 出現(xiàn)的次數(shù)？為此他特別數(shù)了一下 1~13 中包含 1 的數(shù)字有 1、10、11、12、13 因此共出現(xiàn) 6 次，但是對于后面問題他就沒轍了。ACMer 希望你們幫幫他，并把問題更加普遍化，可以很快的求出任意非負(fù)整數(shù)區(qū)間中 1 出現(xiàn)的次數(shù)（從 1 到 n 中 1 出現(xiàn)的次數(shù)）。

【代碼】

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;

    }

【思考】

不要用遞歸寫，最簡單的循環(huán)即可

5、丑數(shù)

【題目】

把只包含質(zhì)因子 2、3 和 5 的數(shù)稱作丑數(shù)（Ugly Number）。例如 6、8 都是丑數(shù)，但 14 不是，因?yàn)樗|(zhì)因子 7。 習(xí)慣上我們把 1 當(dāng)做是第一個丑數(shù)。求按從小到大的順序的第 N 個丑數(shù)。

【代碼】

	/**
     * 把只包含質(zhì)因子 2、3 和 5 的數(shù)稱作丑數(shù)（Ugly Number）。
     * 例如 6、8 都是丑數(shù)，但 14 不是，因?yàn)樗|(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];
    }

【思考】

當(dāng)特定某些性質(zhì)的數(shù)列排序時，可以考慮這種方法。

相關(guān)推薦：java入門

Atas ialah kandungan terperinci java面試中常見的數(shù)組題目匯總（三）. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!