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> 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è)排序過的數(shù)組，所以可以用二分查找法，定位 k 的第一次出現(xiàn)位置和最后一次出現(xiàn)位置，時(shí)間復(fù)雜度為O(logN)O(logN)
二分的前提：有序（一提到有序，必須立馬想到二分！）
2、求 1+2+3+…+n
【題目】
求 1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case 等關(guān)鍵字及條件判斷語句（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á)式值為假之后就沒有必要執(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、剪繩子
【題目】
給你一根長度為 n 的繩子，請把繩子剪成整數(shù)長的 m 段（m、n 都是整數(shù)，n>1 并且 m>1），每段繩子的長度記為 k [0],k [1],…,k [m]。請問 k [0] xk [1] x…xk [m] 可能的乘積是多少？例如，當(dāng)繩子的長度是 8 時(shí)，我們把它剪成長度分別為 2、3、3 的三段，此時(shí)得到的乘積是 18。
【代碼】
/**
* 給你一根長度為 n 的繩子，請把繩子剪成整數(shù)長的 m 段（m、n 都是整數(shù)，n>1 并且 m>1），
* 每段繩子的長度記為 k [0],k [1],...,k [m]。
* 請問 k [0] xk [1] x...xk [m] 可能的乘積是多少？
* 例如，當(dāng)繩子的長度是 8 時(shí)，
* 我們把它剪成長度分別為 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是劃分的乘積小于自身，對狀態(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}； 針對數(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}
*
* 思路：
* 先找出最開始size大小的值，以及這個(gè)值的下標(biāo)
* 然后每次增加一個(gè)值，先判斷滑動(dòng)窗口的第一位下標(biāo)是否超過保存值的下標(biāo)
* 如果超過就要重新計(jì)算size區(qū)域的值，
* 如果未超過就使用值與新增的元素比較，獲取較大的
* */
public ArrayList maxInWindows(int [] num, int size) {
ArrayList 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ù)組長度
if (num.length <= size) return list;
// 把第一個(gè)滑動(dòng)窗口值加入數(shù)組
list.add(temp[0]);
// 從新的窗口開始計(jì)算，上一個(gè)窗口的值和下標(biāo)保存在temp中
for (i=size; inum.length) e = num.length;
int temp = Integer.MIN_VALUE;
int k = 0;
for (int i=s; i* 思路：
* 先找出最開始size大小的值，以及這個(gè)值的下標(biāo)
* 然后每次增加一個(gè)值，先判斷滑動(dòng)窗口的第一位下標(biāo)是否超過保存值的下標(biāo)
* 如果超過就要重新計(jì)算size區(qū)域的值，
* 如果未超過就使用值與新增的元素比較，獲取較大的
額外補(bǔ)充：對于異常情況的拋出，就比如這道題，size>num.length的情況是拋出null，而自己覺得還是拋出，這個(gè)時(shí)候應(yīng)該跟面試官溝通。
5、數(shù)組中重復(fù)的數(shù)字
【題目】
在一個(gè)長度為 n 的數(shù)組里的所有數(shù)字都在 0 到 n-1 的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次。請找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。 例如，如果輸入長度為 7 的數(shù)組 {2,3,1,0,2,5,3}，那么對應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字 2。
【代碼】
/**
* 在一個(gè)長度為 n 的數(shù)組里的所有數(shù)字都在 0 到 n-1 的范圍內(nèi)。
* 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。
* 也不知道每個(gè)數(shù)字重復(fù)幾次。請找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。
* 例如，如果輸入長度為 7 的數(shù)組 {2,3,1,0,2,5,3}，
* 那么對應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字 2。
*
* 思路：
* 看到 長度n，內(nèi)容為0-n-1；瞬間就應(yīng)該想到，元素和下標(biāo)的轉(zhuǎn)換
*
* 下標(biāo)存的是元素的值，對應(yīng)的元素存儲(chǔ)出現(xiàn)的次數(shù)，
* 為了避免弄混次數(shù)和存儲(chǔ)元素，把次數(shù)取反，出現(xiàn)一次則-1，兩次則-2
* 把計(jì)算過的位置和未計(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];
// 判斷對應(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* 思路：
* 看到 長度n，內(nèi)容為0-n-1；瞬間就應(yīng)該想到，元素和下標(biāo)的轉(zhuǎn)換
* 下標(biāo)存的是元素的值，對應(yīng)的元素存儲(chǔ)出現(xiàn)的次數(shù)，
* 為了避免弄混次數(shù)和存儲(chǔ)元素，把次數(shù)取反，出現(xiàn)一次則-1，兩次則-2
* 把計(jì)算過的位置和未計(jì)算的元素交換，當(dāng)重復(fù)的時(shí)候，可以用n代替
相關(guān)推薦：java入門
文章名稱：java面試中常見的數(shù)組題目匯總（五）
URL標(biāo)題：http://weahome.cn/article/cjgsgs.html
