二分查找
==总结：二分查找的结果：如果能查到则返回值一定是mid，如果查找不到，最后的状态是(eg: 1,2,3,right,left,4,5,6)，最后一定是right指针在left指针左边且相邻，此时left指针的位置就是找不到target是需要插入的位置，mid指针应该等于left指针==
注意点
mid=left+(right-left)/2 放置left+right溢出
while(left<right) OR while(left<=right)
边界重新赋值时应为mid或者mid+1
按照自己所定义的区间来判断 [left, right] [left, rigth)
两种写法
[left, right]
此时当left=right时也是有意义的，因此while条件为left<=right
当nums[mid] != target时，需要重新确定区间
显然mid下标的数已经参与过比较，因此确定新的区间时不需要包含mid下标，left=mid+1，right=mid-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target < nums[mid]) {
right = mid - 1;
} else if (target > nums[mid]) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
|
[left, right)
注意，由于右边界是开区间，因此 right = nums.length 而不需要减 1
因为right为开区间，所以left不可能等于right ，因此while的条件为while(left < right)
当nums[mid] != target时，需要重新确定区间
确定新的区间时不需要包含mid下标，而由于区间是右开，因此右边界可以是mid
故确定新区间时 [left, mid) [mid+1, right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int search(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (target < nums[mid]) {
right = mid;
} else if (target > nums[mid]) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
|
35.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(target < nums[mid]){
right = mid - 1;
}else if (target > nums[mid]){
left = mid + 1;
}else {
return mid;
}
}
return left;
}
|
34.在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
思路：一次二分法搜索出左边界，再用一次二分法搜索出右边界(或者得到左边界后顺序遍历)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public int[] searchRange(int[] nums, int target) {
int resLeft = -1, resRight = -1;
int lLeft = 0, rLeft = 0;
int lRight = nums.length - 1, rRight = nums.length - 1;
while (lLeft <= lRight) {
int mid = lLeft + (lRight - lLeft) / 2;
if (target <= nums[mid]) {
lRight = mid - 1;
if (target == nums[mid]) {
resLeft = mid;
}
} else {
lLeft = mid + 1;
}
}
while (rLeft <= rRight) {
int mid = rLeft + (rRight - rLeft) / 2;
if (target < nums[mid]) {
rRight = mid - 1;
} else {
rLeft = mid + 1;
if (target == nums[mid]) {
resRight = mid;
}
}
}
return new int[]{resLeft, resRight};
}
|
确定左边界后遍历计数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public int[] searchRange(int[] nums, int target) {
int resLeft = -1, resRight = -1;
int lLeft = 0, rLeft = 0;
int lRight = nums.length - 1, rRight = nums.length - 1;
while (lLeft <= lRight) {
int mid = lLeft + (lRight - lLeft) / 2;
if (target <= nums[mid]) {
lRight = mid - 1;
if (target == nums[mid]) {
resLeft = lRight + 1;
}
} else {
lLeft = mid + 1;
}
}
int res = 0;
int i = resLeft;
while (i >= 0 && i< nums.length && nums[i] == target) {
res++;
i++;
}
if(res!=0){
res-=1;
}
return new int[]{resLeft, resLeft + res};
}
|
69.x的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
示例 2：
1
2
3
| 输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public int mySqrt(int x) {
if (x == 0) {
return 0;
}
if (x <= 3) {
return 1;
}
int left = 2;
int right = x / 2;
while (left <= right) {
int mid = left + (right - left) / 2;
if ((long) mid * mid < x) {
left = mid + 1;
} else if ((long) mid * mid > x) {
right = mid - 1;
} else {
return mid;
}
}
return right;
}
|
367.有效的完全平方数
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
示例 2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public boolean isPerfectSquare(int num) {
if (num == 1) {
return true;
}
int left = 2;
int right = num / 2;
while (left <= right) {
int mid = left + (right - left) / 2;
if ((long) mid * mid > num) {
right = mid - 1;
} else if ((long) mid * mid < num) {
left = mid + 1;
} else {
return true;
}
}
return false;
}
|
移除元素
==总结：使用快慢双指针==
27. 移除元素
快慢双指针：初始时快慢指针都指向第一个元素，每循环一次，如果快指针不等于val，则赋值给慢指针，如果快指针等于val，则慢指针不需要动，快指针加1
给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int removeElement(int[] nums, int val) {
if (nums == null || nums.length == 0) {
return 0;
}
int fastIndex = 0;
int slowIndex = 0;
while(fastIndex < nums.length){
if(nums[fastIndex] != val){
nums[slowIndex] = nums[fastIndex];
slowIndex++;
}
fastIndex++;
}
return slowIndex;
}
|
26.删除排序数组中的重复项
给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
1
2
3
4
5
6
7
8
9
10
11
12
| public int removeDuplicates(int[] nums) {
int fastIndex=1;
int slowIndex=0;
while(fastIndex < nums.length){
if (nums[fastIndex] != nums[slowIndex]) {
slowIndex++;
nums[slowIndex] = nums[fastIndex];
}
fastIndex++;
}
return slowIndex+1;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int removeDuplicates(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int fast = 1, slow = 1;
while (fast < n) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast]; ++slow;
} ++fast;
}
return slow;
}
|
283.移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
1
2
| 输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
|
示例 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public void moveZeroes(int[] nums) {
int fastIndex = 0;
int slowIndex = 0;
while (fastIndex < nums.length) {
if (nums[fastIndex] != 0) {
swap(nums, fastIndex, slowIndex);
slowIndex++;
}
fastIndex++;
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
|
滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
|
for () {
while (窗口数据不满要求 && left < arrSize) {
left++;
}
right++;
}
|
209.长度最小的子数组
