java面試中常見的陣列題目總結（三）
- 王林轉載
- 2020-11-11 15:18:322224瀏覽
星級：*****
1、順時針列印矩陣
（學習影片分享：java課程）
【題目】
輸入矩陣，依照從外向以順時針的順序依序列印出每一個數字，例如，若輸入如下4 X 4 矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依序印出數字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;
// 遍历游标
x = 0;
y = 0;
count = 0;
// 元素个数
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;
}【思考】
需要注意邊界是否越界以及，遊標（x,y）經過x 或y 之後，定位在什麼地方，需要進行手動的轉彎。
2、陣列中出現次數超過一半的數字
【題目】
陣列中有一個數字出現的次數超過陣列長度的一半，請找出這個數字。例如輸入長度為 9 的陣列 {1,2,3,2,2,2,5,4,2}。由於數字 2 在陣列中出現了 5 次，超過陣列長度的一半，因此輸出 2。如果不存在則輸出 0。
【程式碼】
package swear2offer.array;
import java.util.Arrays;
public class Half {
/**
* 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
* 例如输入一个长度为 9 的数组 {1,2,3,2,2,2,5,4,2}。
* 由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 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];
// 标记数组
int[] flag = new int[n];
// 给数组排序
Arrays.sort(array);
count = 1;
flag[0] = 1;
for (i=1; i<n; i++) {
// 因为是排序好的，如果存在相等的
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;
}
}（相關面試題推薦：java面試題及答案）
【程式碼2】
不必要的排序的巧妙方法：
用preValue 記錄上一次訪問的值，count 表明當前值出現的次數，如果下一個值和當前值相同那麼count ；如果不同count–，減到0的時候就要更換新的preValue 值了，因為如果存在超過陣列長度一半的值，那麼最後preValue 一定會是這個值。
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0)return 0;
int preValue = array[0];//用来记录上一次的记录
int count = 1;//preValue出现的次数（相减之后）
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半数
for(int i=0; i < array.length; i++)
if(array[i] == preValue)
num++;
return (num > array.length/2)?preValue:0;
}【思考】
當i從1而不是0開始的時候，通常需要特別考慮只有一個元素的情況
3、連續子數組的最大和
【題目】
給一個數組，傳回它的最大連續子序列的和，例如:{6,-3,-2,7,-15,1,2,2 }, 連續子向量的最大和為8 (從第0 個開始，到第3 個為止)
【程式碼】
/**
* 给一个数组，返回它的最大连续子序列的和
*
* 例如:{6,-3,-2,7,-15,1,2,2}, 连续子向量的最大和为 8 (从第 0 个开始，到第 3 个为止)
*
* 非常典型的dp
*
* 动规通常分为顺推和逆推两个不同的方向
* 要素：边界，状态转移公式，数组代表含义
* array[]
* dp[x],从各个正数开始连续到达x时，最大和，即连续子序列的最大和
* 需要注意：1.从第一个正数开始，2.是连续序列
* 通常情况下，连续序列的复杂度为O(n),非连续序列为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;
}【想法】
從前往後遍歷，最大的連續子序列的和是由當前元素和之前的最大連續子序列的和疊加在一起形成的。如果之前的最大連續子序列的和大於零，我們可以繼續累加，如果小於零，則需要捨去之前的子序列，重新從目前的數字開始累積。時間複雜度為O (n)
4、整數中1 出現的次數
【題目】
求出1~13 的整數中1 出現的次數，並算出100~1300 的整數中1 出現的次數？為此他特別數了一下 1~13 中包含 1 的數字有 1、10、11、12、13 因此共出現 6 次，但是對於後面問題他就沒轍了。 ACMer 希望你們幫他，並把問題更普遍化，可以很快的求出任意非負整數區間中 1 出現的次數（從 1 到 n 中 1 出現的次數）。
【程式碼】
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;
}【思考】
不要用遞歸寫，最簡單的迴圈即可
5、醜數
【題目】
把只包含質因子2、3 和5 的數稱作醜數（Ugly Number）。例如 6、8 都是醜數，但 14 不是，因為它包含質因子 7。習慣上我們把 1 當做是第一個醜數。求從小到大的順序的第 N 個醜數。
【程式碼】
/**
* 把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。
* 例如 6、8 都是丑数，但 14 不是，因为它包含质因子 7。
* 习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 N 个丑数。
*
* 从已有的丑数中选取一个，分别*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];
}【思考】
當特定某些性質的數列排序時，可以考慮這個方法。
相關推薦：java入門
以上是java面試中常見的陣列題目總結（三）的詳細內容。更多資訊請關注PHP中文網其他相關文章！