1.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 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.移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并「原地」修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 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.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
考点:滑动窗口
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
给定一个正整数 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)
