主題難度：* *
（學習影片推薦：java課程）
1、排序序
【題目】
傳回一個數字數組的排序值，例如資料[6,2,5,0] 的回傳是[4,2,3,1]
【代碼】
package swear2offer.array;
import java.util.Arrays;
public class SortSequence {
/**
* 返回一个数字数组的排序值
* 比如数据 [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];
//数组下标从0开始，但是输出的次序从1开始，所以需要初始化数组为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)));
}
}【思考】
正常的獲得次序的方式是每一個元素都與其他所有元素進行比較，然後獲得大小次序，但是這裡採用的是梯形比較次序
6 6 2 6 2 5 6 2 5 0
比較的時候，不只判斷比較元素，同時也判斷被比較元素，也就是if else的程式碼，這樣可以減少比較次數。
2、陣列下標輔助記錄
【題目】
給定一個陣列a, 長度為N, 元素取值範圍為[1, N]，統計各個元素出現的次數，要求時間複雜度為O (N), 空間複雜度為O (1)
#【程式碼】
/**
* 这类要求空间O(1)时间复杂度为O(n)的问题
* 需要在一次遍历并且不声明新数组的情况下求解，这种题目通常要求元素大小跟下标大小一致。
* 所以通常考虑是利用数组存储的元素和数组下标来求解
* 在本题中，数组的元素变成了下标，而数组内元素则表示之前元素出现的次数，0则代表不出现。
* 为了区分元素和次数，可以把次数设定为负值
* */
public void Solution(int[] a) {
int i,n,temp;
n = a.length;
i = 0;
/**
* 只有在temp小于0的时候才会推进循环
* */
while(i < n) {
temp = a[i]-1;
// 如果数组元素小于0，则代表该数已经被替换到其他地方或者已经被计数过从而被覆盖
if (temp < 0) {
i ++;
continue;
}
// 把未记录的数保存在已经记录的位置上，并用负值保存数量
if (a[temp]>0) {
a[i] = a[temp];
a[temp] = -1;
} else {
a[i] = 0; //该数据已经使用过，且表示元素i+1出现0次
a[temp]--;
}
}
}（圖文教學推薦：java面試題目及答案）
3、找出有序二維數組的元素
【題目】
在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組是否含有該整數。
【程式碼】
package swear2offer.array;
public class ArrayFind {
/**
* 在一个二维数组中（每个一维数组的长度相同），
* 每一行都按照从左到右递增的顺序排序，
* 每一列都按照从上到下递增的顺序排序。
* 请完成一个函数，输入这样的一个二维数组和一个整数，
* 判断数组中是否含有该整数。
*
* 思路：
* 从左上出发，需要考虑的情况太多，因为向右和向下都是递增
* 但是从右上出发，向左递减，向下递增，这样就把情况限定在一种。
* */
public boolean Find(int target, int [][] array) {
int l,h,x,y;
h = array.length;
l = array[0].length;
// 游标的横纵坐标
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));
}
}【思考】
從左上出發，需要考慮的情況太多，因為向右和向下都是遞增，但是從右上出發，向左遞減，向下遞增，這樣就把情況限定在一種。特殊的數組，充分利用數組的特殊性，從不同的方向考慮方法。
4、跳台階
【題目】
一隻青蛙一次可以跳上 1 級台階，也可以跳上 2 級。求該青蛙跳上一個 n 級的階梯總共有多少種跳法（先後次序不同算不同的結果）。
【程式碼】
package swear2offer.array;
public class Floors {
/**
* 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。
* 求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
*
* 获取跳法次数
* */
public int JumpFloor(int target) {
if (target < 3) return target;
// 大于等于3个台阶，次数是第一步调1下和跳2下的个数之和
return JumpFloor(target-1) + JumpFloor(target-2);
}
}5、變態跳台階
【題目】
#一隻青蛙一次可以跳上1 級台階，也可以跳上2 級… 它也可以跳上n 級。求該青蛙跳上一個 n 級的階梯總共有多少種跳法。
【程式碼】
package swear2offer.array;
import java.util.Arrays;
public class FloorsPlus {
/**
* 一只青蛙一次可以跳上 1 级台阶，
* 也可以跳上 2 级…… 它也可以跳上 n 级。
* 求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
*
* 动态规划：数组代表含义、边界、转换公式
* 动态规划最重要的是找出阶段之间的变化公式，
* 即，n-1和n之间的状态是如何转移的
*
* f[n]:n阶台阶的跳法
* 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步也算一种方法，
* 所以需要初始化把数组初始化为1，或则单独处理f[0].
*
* */
public int JumpFloorII(int target) {
if (target < 3) return target;
int[] f = new int[target+1];
//单独处理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];
//初始化把数组初始化为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];
}
}相關推薦：java入門
以上是java面試中常見的陣列題目總結（一）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
