主題難度：* *

（學(xué)習(xí)影片推薦：java課程）

1、排序序

【題目】

傳回一個(gè)數(shù)字?jǐn)?shù)組的排序值，例如資料[6,2,5,0] 的回傳是[4,2,3,1]

【代碼】

package swear2offer.array;

import java.util.Arrays;

public class SortSequence {
    /**
     * 返回一個(gè)數(shù)字?jǐn)?shù)組的排序值
     * 比如數(shù)據(jù) [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];

		//數(shù)組下標(biāo)從0開始，但是輸出的次序從1開始，所以需要初始化數(shù)組為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)));
    }

}

【思考】

正常的獲得次序的方式是每一個(gè)元素都與其他所有元素進(jìn)行比較，然後獲得大小次序，但是這裡採(cǎi)用的是梯形比較次序

6
6 2
6 2 5
6 2 5 0

比較的時(shí)候，不只判斷比較元素，同時(shí)也判斷被比較元素，也就是if else的程式碼，這樣可以減少比較次數(shù)。

2、陣列下標(biāo)輔助記錄

【題目】

給定一個(gè)陣列a, 長(zhǎng)度為N, 元素取值範(fàn)圍為[1, N]，統(tǒng)計(jì)各個(gè)元素出現(xiàn)的次數(shù)，要求時(shí)間複雜度為O (N), 空間複雜度為O (1)

#【程式碼】

/**
     * 這類要求空間O(1)時(shí)間復(fù)雜度為O(n)的問(wèn)題
     * 需要在一次遍歷并且不聲明新數(shù)組的情況下求解，這種題目通常要求元素大小跟下標(biāo)大小一致。
     * 所以通?？紤]是利用數(shù)組存儲(chǔ)的元素和數(shù)組下標(biāo)來(lái)求解
     * 在本題中，數(shù)組的元素變成了下標(biāo)，而數(shù)組內(nèi)元素則表示之前元素出現(xiàn)的次數(shù)，0則代表不出現(xiàn)。
     * 為了區(qū)分元素和次數(shù)，可以把次數(shù)設(shè)定為負(fù)值
     * */
    public void Solution(int[] a) {
        int i,n,temp;
        n = a.length;

        i = 0;
        /**
         * 只有在temp小于0的時(shí)候才會(huì)推進(jìn)循環(huán)
         * */
        while(i < n) {
            temp = a[i]-1;
            // 如果數(shù)組元素小于0，則代表該數(shù)已經(jīng)被替換到其他地方或者已經(jīng)被計(jì)數(shù)過(guò)從而被覆蓋
            if (temp < 0) {
                i ++;
                continue;
            }
            // 把未記錄的數(shù)保存在已經(jīng)記錄的位置上，并用負(fù)值保存數(shù)量
            if (a[temp]>0) {
                a[i] = a[temp];
                a[temp] = -1;
            } else {
                a[i] = 0; //該數(shù)據(jù)已經(jīng)使用過(guò)，且表示元素i+1出現(xiàn)0次
                a[temp]--;
            }
        }

    }

（圖文教學(xué)推薦：java面試題目及答案）

3、找出有序二維數(shù)組的元素

【題目】

在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長(zhǎng)度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組是否含有該整數(shù)。

【程式碼】

package swear2offer.array;

public class ArrayFind {

    /**
     * 在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長(zhǎng)度相同），
     * 每一行都按照從左到右遞增的順序排序，
     * 每一列都按照從上到下遞增的順序排序。
     * 請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，
     * 判斷數(shù)組中是否含有該整數(shù)。
     *
     * 思路：
     * 從左上出發(fā)，需要考慮的情況太多，因?yàn)橄蛴液拖蛳露际沁f增
     * 但是從右上出發(fā)，向左遞減，向下遞增，這樣就把情況限定在一種。
     * */
    public boolean Find(int target, int [][] array) {

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

        // 游標(biāo)的橫縱坐標(biāo)
        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));
    }

}

【思考】

從左上出發(fā)，需要考慮的情況太多，因?yàn)橄蛴液拖蛳露际沁f增，但是從右上出發(fā)，向左遞減，向下遞增，這樣就把情況限定在一種。特殊的數(shù)組，充分利用數(shù)組的特殊性，從不同的方向考慮方法。

4、跳臺(tái)階

【題目】

一隻青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上 2 級(jí)。求該青蛙跳上一個(gè) n 級(jí)的階梯總共有多少種跳法（先後次序不同算不同的結(jié)果）。

【程式碼】

package swear2offer.array;

public class Floors {

    /**
     * 一只青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上 2 級(jí)。
     * 求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法（先后次序不同算不同的結(jié)果）。
     *
     * 獲取跳法次數(shù)
     * */
    public int JumpFloor(int target) {

        if (target < 3) return target;

        // 大于等于3個(gè)臺(tái)階，次數(shù)是第一步調(diào)1下和跳2下的個(gè)數(shù)之和
        return JumpFloor(target-1) + JumpFloor(target-2);

    }
}

5、變態(tài)跳臺(tái)階

【題目】

#一隻青蛙一次可以跳上1 級(jí)臺(tái)階，也可以跳上2 級(jí)… 它也可以跳上n 級(jí)。求該青蛙跳上一個(gè) n 級(jí)的階梯總共有多少種跳法。

【程式碼】

package swear2offer.array;

import java.util.Arrays;

public class FloorsPlus {

    /**
     * 一只青蛙一次可以跳上 1 級(jí)臺(tái)階，
     * 也可以跳上 2 級(jí)…… 它也可以跳上 n 級(jí)。
     * 求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。
     *
     * 動(dòng)態(tài)規(guī)劃：數(shù)組代表含義、邊界、轉(zhuǎn)換公式
     * 動(dòng)態(tài)規(guī)劃最重要的是找出階段之間的變化公式，
     * 即，n-1和n之間的狀態(tài)是如何轉(zhuǎn)移的
     *
     * f[n]:n階臺(tái)階的跳法
     * 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步也算一種方法，
     * 所以需要初始化把數(shù)組初始化為1，或則單獨(dú)處理f[0].
     *
     * */
    public int JumpFloorII(int target) {
        if (target < 3) return target;
        int[] f = new int[target+1];
        //單獨(dú)處理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];

        //初始化把數(shù)組初始化為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];
    }
}

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

以上是java面試中常見的陣列題目總結(jié)（一）的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！