1.搜索插入位置
給定一個排序數(shù)組和一個目標值舆床，在數(shù)組中找到目標值棋蚌，并返回其索引。如果目標值不存在于數(shù)組中挨队，返回它將會被按順序插入的位置谷暮。
你可以假設數(shù)組中無重復元素。
示例 1:
輸入: [1,3,5,6], 5
輸出: 2
示例 2:
輸入: [1,3,5,6], 2
輸出: 1
考點:二分法查找
public int binarySearch(int[] numbers, int target) {
int start = 0;
int end = numbers.length - 1;
while (end >= start) {
int mid = (start + end) / 2;
if (target > numbers[mid]) {
start = mid + 1;
} else if (target < numbers[mid]) {
end = mid - 1;
} else {
return mid;
}
}
return end + 1;
}
2.移除元素
給你一個數(shù)組 nums 和一個值 val盛垦，你需要 原地 移除所有數(shù)值等于 val 的元素湿弦，并返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間腾夯，你必須僅使用 O(1) 額外空間并「原地」修改輸入數(shù)組颊埃。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素蝶俱。
示例 1:
給定 nums = [3,2,2,3], val = 3,
函數(shù)應該返回新的長度 2, 并且 nums 中的前兩個元素均為 2班利。
你不需要考慮數(shù)組中超出新長度后面的元素。
示例 2:
給定 nums = [0,1,2,2,3,0,4,2], val = 2,
函數(shù)應該返回新的長度 5, 并且 nums 中的前五個元素為 0, 1, 3, 0, 4榨呆。
考點：雙指針
public int[] removingElements(int[] numbers, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < numbers.length; fastIndex++) {
if (numbers[fastIndex] != val) {
numbers[slowIndex] = numbers[fastIndex];
slowIndex++;
}
}
return numbers;
}
3.長度最小的子數(shù)組
給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s 罗标，找出該數(shù)組中滿足其和 ≥ s 的長度最小的 連續(xù) 子數(shù)組，并返回其長度愕提。如果不存在符合條件的子數(shù)組馒稍，返回 0。
示例：
輸入：s = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組浅侨。
考點:滑動窗口
public int smallestArray(int[] numbers, int target) {
int i = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
int subLength;
for (int j = 0; j < numbers.length; j++) {
sum += numbers[j];
while (sum>target){
subLength = j - i + 1;
result = Math.min(subLength,result);
sum -= numbers[i++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
4.螺旋矩陣II
給定一個正整數(shù) n纽谒，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的正方形矩陣如输。
示例:
輸入: 3
輸出:
[ [ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ] ]
考點:還原能力
public int[][] generateMatrix(int n) {
int[][] arr = new int[n][n];
int c = 1, j = 0;
while (c <= n * n) {
for (int i = j; i < n - j; i++)
arr[j][i] = c++;
for (int i = j + 1; i < n - j; i++)
arr[i][n - j - 1] = c++;
for (int i = n - j - 2; i >= j; i--)
arr[n - j - 1][i] = c++;
for (int i = n -j - 2; i > j; i--)
arr[i][j] = c++;
j++;
}
return arr;
}
下集預告：程序員必須掌握的高頻算法題之鏈表(2)
