代码随想录二刷day01

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

使用左闭右闭区间的二分查找时， 最后low一定是被查找元素的插入位置，若查找的数带小数，low-1， 便是最终结果

一、704. 二分查找

1、左闭右闭

class Solution {public int search(int[] nums, int target) {int low = 0, high = nums.length-1, mid = 0;while(low <= high){mid = (low + high)/2;if(nums[mid] == target){return mid;}else if(nums[mid] < target){low = mid + 1;}else{high = mid - 1;}}return -1;}
}

2、左闭右开

class Solution {public int search(int[] nums, int target) {int low = 0, high = nums.length, mid = 0;while(low < high){mid = (low + high)/2;if(nums[mid] == target){return mid;}else if(nums[mid] < target){low = mid + 1;}else{high = mid;}}return -1;}
}

二、35. 搜索插入位置

class Solution {public int searchInsert(int[] nums, int target) {int low = 0, high = nums.length, mid;while(low < high){mid = (low + high)/2;if(nums[mid] == target){return mid;}else if(nums[mid] < target){low = mid + 1;}else{high = mid;}}return low;}
}

三、34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {public int[] searchRange(int[] nums, int target) {int low = 0, high = nums.length, mid; int[] res = {-1, -1};while(low < high){mid = (low + high)/2;if(nums[mid] == target){res[0] = res[1] = mid;while(res[0]-1 >= 0 && nums[res[0] - 1] == target){res[0] -= 1;}while(res[1] + 1 < nums.length && nums[res[1] + 1] == target){res[1] += 1;}return res;}else if(nums[mid] < target){low = mid + 1;}else{high = mid;}}return res;}
}

四、69. x 的平方根

class Solution {public int mySqrt(int x) {int low = 0, high = x, mid;if(x == 0 || x == 1){return x;}while(low <= high){mid = (low + high)/2;if(x / mid == mid){return mid;}else if(x / mid > mid){low = mid +1;}else{high = mid -1;}}return low - 1;}
}

五、367. 有效的完全平方数

lass Solution {public boolean isPerfectSquare(int num) {int x = 1;while(num > 0){num -= x;x += 2;}return num == 0;}
}

六、27. 移除元素

class Solution {public int removeElement(int[] nums, int val) {int i = 0, j = 0;for(;i < nums.length; ){if(nums[i] != val){nums[j] = nums[i];i ++; j ++;}else{i ++;}}return j;}
}

七、26. 删除有序数组中的重复项

class Solution {public int removeDuplicates(int[] nums) {if(nums.length == 1){return 1;}int i = 1, j = 0;for(; i < nums.length; ){if(nums[i] != nums[j]){nums[++j] = nums[i++];}else{i ++;}}return j + 1;}
}

八、283. 移动零

class Solution {public void moveZeroes(int[] nums) {int i = 0, j = 0, len = nums.length;if(len == 1)return;while(i < len){if(nums[i] != 0){nums[j] = nums[i];if(i == j){i ++;}else{nums[i++] = 0;}j ++;}else{i ++;}}}
}

九、844. 比较含退格的字符串

class Solution {public boolean backspaceCompare(String s, String t) {Deque<Character> deq1 = new ArrayDeque<>();Deque<Character> deq2 = new ArrayDeque<>();char[] ch1 = s.toCharArray();char[] ch2 = t.toCharArray();for(int i = 0; i < ch1.length; i ++){if(ch1[i] != '#'){deq1.offerFirst(ch1[i]);}else if(!deq1.isEmpty()){deq1.pollFirst();}}for(int j = 0; j < ch2.length; j ++){if(ch2[j] != '#'){deq2.offerFirst(ch2[j]);}else if(!deq2.isEmpty()){deq2.pollFirst();}}while(!deq1.isEmpty() && !deq2.isEmpty()){char c1 = deq1.pollFirst();char c2 = deq2.pollFirst();if(c1 != c2){return false;}}return deq1.isEmpty() && deq2.isEmpty();}
}

十、977. 有序数组的平方

class Solution {public int[] sortedSquares(int[] nums) {Deque<Integer> deq1 = new LinkedList<>();Deque<Integer> deq2 = new LinkedList<>();for(int i = 0; i < nums.length; i ++){if(nums[i] <= 0){deq1.offerLast(nums[i] * nums[i]);}else{deq2.offerLast(nums[i] * nums[i]);}}int k = 0;while(!deq1.isEmpty() && !deq2.isEmpty()){if(deq1.peekLast() <= deq2.peekFirst()){nums[k ++] = deq1.pollLast();}else{nums[k ++] = deq2.pollFirst();}}while(!deq1.isEmpty()){nums[k ++] = deq1.pollLast();}while(!deq2.isEmpty()){nums[k ++] = deq2.pollFirst();}return nums;}
}