1、數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)

【題目】

統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。

（學(xué)習(xí)視頻推薦：java視頻教程）

【代碼】

public int GetNumberOfK(int [] array , int k) {

        if (array.length==0 || array==null) return 0;

        int i,n,count;
        n = array.length;

        count = 0;
        for (i=0; i<n; i++) {
            if (array[i] == k) count++;
        }

        return count;
    }

    public int high(int[] a, int k) {
        int start,end,mid;

        start = 0;
        end = a.length-1;

        while (start <= end) {
            mid = (start + end) >> 1;
            if (a[mid] <= k) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return end;
    }

    public int low(int[] a, int k) {
        int start,end,mid;

        start = 0;
        end = a.length-1;

        while (start <= end) {
            mid = (start + end) >> 1;
            if (a[mid] >= k) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return start;
    }

【思考】

由于數(shù)組是一個(gè)排序過(guò)的數(shù)組，所以可以用二分查找法，定位 k 的第一次出現(xiàn)位置和最后一次出現(xiàn)位置，時(shí)間復(fù)雜度為O(logN)O(logN)

二分的前提：有序（一提到有序，必須立馬想到二分?。?/p>

2、求 1+2+3+…+n

【題目】

求 1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case 等關(guān)鍵字及條件判斷語(yǔ)句（A?B:C）。

【代碼】

	public int Sum_Solution(int n) {
        int sum = n;
        boolean flag = (sum > 0) && (sum += Sum_Solution(n-1))>0;
        return sum;
    }

思考】

要求不能使用循環(huán)，不能使用判斷，所以用遞歸代替循環(huán)，用短路原理代替判斷

短路與執(zhí)行的順序是從左到右，在確定第一個(gè)表達(dá)式值為假之后就沒(méi)有必要執(zhí)行第二個(gè)條件句的必要了。因?yàn)楹苊黠@，不管第二個(gè)條件的真假，整個(gè)式子的布爾值一定為假。短路與會(huì)跳掉第二個(gè)條件句，不去執(zhí)行它?；谶@些原理，便出現(xiàn)了上述結(jié)果。在編程中靈活運(yùn)用短路與，有很大的意義。

當(dāng) n=0 時(shí)，sum=0，&& 后面的就不會(huì)執(zhí)行了，直接返回 sum=0

3、剪繩子

【題目】

給你一根長(zhǎng)度為 n 的繩子，請(qǐng)把繩子剪成整數(shù)長(zhǎng)的 m 段（m、n 都是整數(shù)，n>1 并且 m>1），每段繩子的長(zhǎng)度記為 k [0],k [1],…,k [m]。請(qǐng)問(wèn) k [0] xk [1] x…xk [m] 可能的最大乘積是多少？例如，當(dāng)繩子的長(zhǎng)度是 8 時(shí)，我們把它剪成長(zhǎng)度分別為 2、3、3 的三段，此時(shí)得到的最大乘積是 18。

【代碼】

    /**
     * 給你一根長(zhǎng)度為 n 的繩子，請(qǐng)把繩子剪成整數(shù)長(zhǎng)的 m 段（m、n 都是整數(shù)，n>1 并且 m>1），
     * 每段繩子的長(zhǎng)度記為 k [0],k [1],...,k [m]。
     * 請(qǐng)問(wèn) k [0] xk [1] x...xk [m] 可能的最大乘積是多少？
     * 例如，當(dāng)繩子的長(zhǎng)度是 8 時(shí)，
     * 我們把它剪成長(zhǎng)度分別為 2、3、3 的三段，此時(shí)得到的最大乘積是 18。
     *
     * 使用動(dòng)態(tài)規(guī)劃
     * 要點(diǎn)：邊界和狀態(tài)轉(zhuǎn)移公式
     * 使用順推法：從小推到大
     * dp[x] 代表x的最大值
     * dp[x] = max{d[x-1]*1,dp[x-2]*2,dp[x-3]*3,,,,},不需要全遍歷，取半即可
     * */
    public int cutRope(int target) {

        // 由于2,3是劃分的乘積小于自身，對(duì)狀態(tài)轉(zhuǎn)移會(huì)產(chǎn)生額外判斷
        if (target <= 3) return target-1;
        int[] dp = new int[target+1];
        int mid,i,j,temp;

        // 設(shè)定邊界
        dp[2] = 2;
        dp[3] = 3;

        for (i=4; i<=target; i++) {
            // 遍歷到中間即可
            mid = i >> 1;
            // 暫存最大值
            temp = 0;
            for (j=1; j<=mid; j++) {
                if (temp < j*dp[i-j]) {
                    temp = j*dp[i-j];
                }
            }
            dp[i] = temp;
        }

        return dp[target];

    }

思考

 *
 * 使用動(dòng)態(tài)規(guī)劃
 * 要點(diǎn)：邊界和狀態(tài)轉(zhuǎn)移公式
 * 使用順推法：從小推到大
 * dp[x] 代表x的最大值
 * dp[x] = max{d[x-1]*1,dp[x-2]*2,dp[x-3]*3,,,,},不需要全遍歷，取半即可
 * 但是需要注意。2和3這兩個(gè)特殊情況，因?yàn)樗麄兊姆纸獬朔e比自身要大，所以特殊處理

（更多相關(guān)面試題分享：java面試題及答案）

4、滑動(dòng)窗口的最大值

【題目】

給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，找出所有滑動(dòng)窗口里數(shù)值的最大值。例如，如果輸入數(shù)組 {2,3,4,2,6,2,5,1} 及滑動(dòng)窗口的大小 3，那么一共存在 6 個(gè)滑動(dòng)窗口，他們的最大值分別為 {4,4,6,6,6,5}； 針對(duì)數(shù)組 {2,3,4,2,6,2,5,1} 的滑動(dòng)窗口有以下 6 個(gè)： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

【代碼】

package swear2offer.array;

import java.util.ArrayList;

public class Windows {

    /**
     * 給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，找出所有滑動(dòng)窗口里數(shù)值的最大值。
     * 例如，如果輸入數(shù)組 {2,3,4,2,6,2,5,1} 及滑動(dòng)窗口的大小 3，
     * 那么一共存在 6 個(gè)滑動(dòng)窗口，他們的最大值分別為 {4,4,6,6,6,5}
     *
     * 思路：
     * 先找出最開(kāi)始size大小的最大值，以及這個(gè)最大值的下標(biāo)
     * 然后每次增加一個(gè)值，先判斷滑動(dòng)窗口的第一位下標(biāo)是否超過(guò)保存最大值的下標(biāo)
     * 如果超過(guò)就要重新計(jì)算size區(qū)域的最大值，
     * 如果未超過(guò)就使用最大值與新增的元素比較，獲取較大的
     * */
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        int i;
        int[] temp;
        temp = getMax(num,0,size);

        if (size<=0 || num==null || num.length==0) return list;

        // 當(dāng)窗口大于數(shù)組長(zhǎng)度
        if (num.length <= size) return list;

        // 把第一個(gè)滑動(dòng)窗口最大值加入數(shù)組
        list.add(temp[0]);

        // 從新的窗口開(kāi)始計(jì)算，上一個(gè)窗口的最大值和下標(biāo)保存在temp中
        for (i=size; i<num.length; i++) {
            // 上一個(gè)最大值還在滑動(dòng)窗口區(qū)域內(nèi)
            if (i-size < temp[1]) {
                if (temp[0] < num[i]) {
                    temp[0] = num[i];
                    temp[1] = i;
                }
            } else {
                temp = getMax(num,i-size+1,size);
            }
            list.add(temp[0]);
        }

        return list;
    }

    public int[] getMax (int[] num, int s, int size) {
        int [] res = new int[2];
        int e = s + size;
        // 當(dāng)窗口大于數(shù)組長(zhǎng)度
        if (e>num.length) e = num.length;

        int temp = Integer.MIN_VALUE;
        int k = 0;
        for (int i=s; i<e; i++) {
            if (temp < num[i]) {
                temp = num[i];
                k = i;
            }
        }

        res[0] = temp;
        res[1] = k;

        return res;
    }

}

* 思路：

* 先找出最開(kāi)始size大小的最大值，以及這個(gè)最大值的下標(biāo)

* 然后每次增加一個(gè)值，先判斷滑動(dòng)窗口的第一位下標(biāo)是否超過(guò)保存最大值的下標(biāo)

* 如果超過(guò)就要重新計(jì)算size區(qū)域的最大值，

* 如果未超過(guò)就使用最大值與新增的元素比較，獲取較大的

額外補(bǔ)充：對(duì)于異常情況的拋出，就比如這道題，size>num.length的情況是拋出null，而自己覺(jué)得還是拋出最大，這個(gè)時(shí)候應(yīng)該跟面試官溝通。

5、數(shù)組中重復(fù)的數(shù)字

【題目】

在一個(gè)長(zhǎng)度為 n 的數(shù)組里的所有數(shù)字都在 0 到 n-1 的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。 例如，如果輸入長(zhǎng)度為 7 的數(shù)組 {2,3,1,0,2,5,3}，那么對(duì)應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字 2。

【代碼】

    /**
     * 在一個(gè)長(zhǎng)度為 n 的數(shù)組里的所有數(shù)字都在 0 到 n-1 的范圍內(nèi)。
     * 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。
     * 也不知道每個(gè)數(shù)字重復(fù)幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。
     * 例如，如果輸入長(zhǎng)度為 7 的數(shù)組 {2,3,1,0,2,5,3}，
     * 那么對(duì)應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字 2。
     *
     * 思路：
     * 看到 長(zhǎng)度n，內(nèi)容為0-n-1；瞬間就應(yīng)該想到，元素和下標(biāo)的轉(zhuǎn)換
     *
     * 下標(biāo)存的是元素的值，對(duì)應(yīng)的元素存儲(chǔ)出現(xiàn)的次數(shù)，
     * 為了避免弄混次數(shù)和存儲(chǔ)元素，把次數(shù)取反，出現(xiàn)一次則-1，兩次則-2
     * 把計(jì)算過(guò)的位置和未計(jì)算的元素交換，當(dāng)重復(fù)的時(shí)候，可以用n代替
     * */
    public boolean duplicate(int numbers[],int length,int [] duplication) {

        if (length == 0 || numbers == null) {
            duplication[0] = -1;
            return false;
        }

        int i,res;
        i = 0;
        while (i < length) {
            // 獲取到數(shù)組元素
            res = numbers[i];
            // 判斷對(duì)應(yīng)位置的計(jì)數(shù)是否存在
            if (res < 0 || res == length) {
                i++;
                continue;
            }

            if (numbers[res] < 0) {
                numbers[res] --;
                numbers[i] = length;
                continue;
            }

            numbers[i] = numbers[res];
            numbers[res] = -1;
        }

        res = 0;
        for (i=0; i<length; i++) {
            if (numbers[i] < -1) {
                duplication[res] = i;
                return true;
            }
        }

        return false;
    }

?* 思路：

?* 看到 長(zhǎng)度n，內(nèi)容為0-n-1；瞬間就應(yīng)該想到，元素和下標(biāo)的轉(zhuǎn)換

?* 下標(biāo)存的是元素的值，對(duì)應(yīng)的元素存儲(chǔ)出現(xiàn)的次數(shù)，

?* 為了避免弄混次數(shù)和存儲(chǔ)元素，把次數(shù)取反，出現(xiàn)一次則-1，兩次則-2

?* 把計(jì)算過(guò)的位置和未計(jì)算的元素交換，當(dāng)重復(fù)的時(shí)候，可以用n代替

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

以上是java面試中常見(jiàn)的數(shù)組題目匯總（五）的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！