java面试中常见的数组题目汇总（五）
1、數字在排序數組中出現的次數
【題目】
統計一個數字在排序數組中出現的次數。
（學習視頻推薦：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;
}
【思考】
由于數組是一個排序過的數組，所以可以用二分查找法，定位 k 的第一次出現位置和最后一次出現位置，時間復雜度為O(logN)O(logN)
二分的前提：有序（一提到有序，必須立馬想到二分！）
2、求 1+2+3+…+n
【題目】
求 1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case 等關鍵字及條件判斷語句（A?B:C）。
【代碼】
public int Sum_Solution(int n) {
int sum = n;
boolean flag = (sum > 0) && (sum += Sum_Solution(n-1))>0;
return sum;
}
思考】
要求不能使用循環，不能使用判斷，所以用遞歸代替循環，用短路原理代替判斷
短路與執行的順序是從左到右，在確定第一個表達式值為假之后就沒有必要執行第二個條件句的必要了。因為很明顯，不管第二個條件的真假，整個式子的布爾值一定為假。短路與會跳掉第二個條件句，不去執行它。基于這些原理，便出現了上述結果。在編程中靈活運用短路與，有很大的意義。
當 n=0 時，sum=0，&& 后面的就不會執行了，直接返回 sum=0
3、剪繩子
【題目】
給你一根長度為 n 的繩子，請把繩子剪成整數長的 m 段（m、n 都是整數，n>1 并且 m>1），每段繩子的長度記為 k [0],k [1],…,k [m]。請問 k [0] xk [1] x…xk [m] 可能的最大乘積是多少？例如，當繩子的長度是 8 時，我們把它剪成長度分別為 2、3、3 的三段，此時得到的最大乘積是 18。
【代碼】
/**
* 給你一根長度為 n 的繩子，請把繩子剪成整數長的 m 段（m、n 都是整數，n>1 并且 m>1），
* 每段繩子的長度記為 k [0],k [1],...,k [m]。
* 請問 k [0] xk [1] x...xk [m] 可能的最大乘積是多少？
* 例如，當繩子的長度是 8 時，
* 我們把它剪成長度分別為 2、3、3 的三段，此時得到的最大乘積是 18。
*
* 使用動態規劃
* 要點：邊界和狀態轉移公式
* 使用順推法：從小推到大
* 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是劃分的乘積小于自身，對狀態轉移會產生額外判斷
if (target <= 3) return target-1;
int[] dp = new int[target+1];
int mid,i,j,temp;
// 設定邊界
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];
}
思考
*
* 使用動態規劃
* 要點：邊界和狀態轉移公式
* 使用順推法：從小推到大
* dp[x] 代表x的最大值
* dp[x] = max{d[x-1]*1,dp[x-2]*2,dp[x-3]*3,,,,},不需要全遍歷，取半即可
* 但是需要注意。2和3這兩個特殊情況，因為他們的分解乘積比自身要大，所以特殊處理
（更多相關面試題分享：java面試題及答案）
4、滑動窗口的最大值
【題目】
給定一個數組和滑動窗口的大小，找出所有滑動窗口里數值的最大值。例如，如果輸入數組 {2,3,4,2,6,2,5,1} 及滑動窗口的大小 3，那么一共存在 6 個滑動窗口，他們的最大值分別為 {4,4,6,6,6,5}； 針對數組 {2,3,4,2,6,2,5,1} 的滑動窗口有以下 6 個： {[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 {
/**
* 給定一個數組和滑動窗口的大小，找出所有滑動窗口里數值的最大值。
* 例如，如果輸入數組 {2,3,4,2,6,2,5,1} 及滑動窗口的大小 3，
* 那么一共存在 6 個滑動窗口，他們的最大值分別為 {4,4,6,6,6,5}
*
* 思路：
* 先找出最開始size大小的最大值，以及這個最大值的下標
* 然后每次增加一個值，先判斷滑動窗口的第一位下標是否超過保存最大值的下標
* 如果超過就要重新計算size區域的最大值，
* 如果未超過就使用最大值與新增的元素比較，獲取較大的
* */
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;
// 當窗口大于數組長度
if (num.length <= size) return list;
// 把第一個滑動窗口最大值加入數組
list.add(temp[0]);
// 從新的窗口開始計算，上一個窗口的最大值和下標保存在temp中
for (i=size; i<num.length; 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;
// 當窗口大于數組長度
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;
}
}
* 思路：
* 先找出最開始size大小的最大值，以及這個最大值的下標
* 然后每次增加一個值，先判斷滑動窗口的第一位下標是否超過保存最大值的下標
* 如果超過就要重新計算size區域的最大值，
* 如果未超過就使用最大值與新增的元素比較，獲取較大的
額外補充：對于異常情況的拋出，就比如這道題，size>num.length的情況是拋出null，而自己覺得還是拋出最大，這個時候應該跟面試官溝通。
5、數組中重復的數字
【題目】
在一個長度為 n 的數組里的所有數字都在 0 到 n-1 的范圍內。 數組中某些數字是重復的，但不知道有幾個數字是重復的。也不知道每個數字重復幾次。請找出數組中任意一個重復的數字。 例如，如果輸入長度為 7 的數組 {2,3,1,0,2,5,3}，那么對應的輸出是第一個重復的數字 2。
【代碼】
/**
* 在一個長度為 n 的數組里的所有數字都在 0 到 n-1 的范圍內。
* 數組中某些數字是重復的，但不知道有幾個數字是重復的。
* 也不知道每個數字重復幾次。請找出數組中任意一個重復的數字。
* 例如，如果輸入長度為 7 的數組 {2,3,1,0,2,5,3}，
* 那么對應的輸出是第一個重復的數字 2。
*
* 思路：
* 看到 長度n，內容為0-n-1；瞬間就應該想到，元素和下標的轉換
*
* 下標存的是元素的值，對應的元素存儲出現的次數，
* 為了避免弄混次數和存儲元素，把次數取反，出現一次則-1，兩次則-2
* 把計算過的位置和未計算的元素交換，當重復的時候，可以用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) {
// 獲取到數組元素
res = numbers[i];
// 判斷對應位置的計數是否存在
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;
}
* 思路：
* 看到 長度n，內容為0-n-1；瞬間就應該想到，元素和下標的轉換
* 下標存的是元素的值，對應的元素存儲出現的次數，
* 為了避免弄混次數和存儲元素，把次數取反，出現一次則-1，兩次則-2
* 把計算過的位置和未計算的元素交換，當重復的時候，可以用n代替
相關推薦：java入門
總結
以上是生活随笔為你收集整理的java面试中常见的数组题目汇总（五）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： css三个字如何和两个字对齐
- 下一篇： 用Telnet 来用smtp发邮件。。