代碼隨想錄算法訓練營二刷第一天| 704. 二分查找，27. 移除元素

一、704. 二分查找

題目鏈接：
思路：維護好循環不變量。另外一個點注意別讓加和超出int類型的限制，可以變為加差。
解法一：左閉右閉

public int search(int[] nums, int target) {int left = 0, right = nums.length - 1, mid = 0;while (left <= right) {mid = left + ((right - left) >> 1);if (target > nums[mid]) {left = mid + 1;} else if (target < nums[mid]) {right = mid - 1;}else {return mid;}}return -1;}

解法二：左閉右開

public int search(int[] nums, int target) {int left = 0, right = nums.length, mid = 0;while (left < right) {mid = left + ((right - left) >> 1);if (target > nums[mid]) {left = mid + 1;} else if (target < nums[mid]) {right = mid;}else {return mid;}}return -1;}

二、35.搜索插入位置

題目鏈接：
思路：經典二分查找。

public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length - 1, mid = 0;while (left <= right) {mid = left + ((right - left) >> 1);if (target > nums[mid]) {left = mid + 1;} else if (target < nums[mid]) {right = mid - 1;} else {return mid;}}return left;}

三、34. 在排序數組中查找元素的第一個和最后一個位置

題目鏈接
思路：分別用二分查找查左邊界和右邊界，查找區間的左邊界，要在mid小于等于target時一直記錄從左邊逼近邊界，而右邊不做記錄，同理求右邊界也是如此。

class Solution {public int[] searchRange(int[] nums, int target) {if (nums.length == 0) {return new int[]{-1, -1};}int left = getLeftBorder(nums, target);int right = getRightBorder(nums, target);if (left == -2 || right == -2) {return new int[]{-1, -1};}if (right - left > 1) {return new int[]{left + 1, right - 1};}return new int[]{-1, -1};}int getLeftBorder(int[] nums, int target) {int left = 0, right = nums.length - 1, mid = 0, leftBorder = -2;while (left <= right) {mid = left + ((right - left) >> 1);if (target <= nums[mid]) {right = mid - 1;leftBorder = right;}else {left = mid + 1;}}return leftBorder;}int getRightBorder(int[] nums, int target) {int left = 0, right = nums.length - 1, mid = 0, rightBorder = -2;while (left <= right) {mid = left + ((right - left) >> 1);if (target >= nums[mid]) {left = mid + 1;rightBorder = left;}else {right = mid - 1;}}return rightBorder;}
}

四、69.x 的平方根

題目鏈接
思路：求平方根有小數的向下取整，這種情況下只要中值計算小于等于mid就一直搜集結果，和上面求邊界的思路類似，當然注意防止溢出，要用long

class Solution {public int mySqrt(int x) {int left = 0, right = x, result = 0;while (left <= right) {int mid = left + ((right - left) >> 1);if ((long) mid * mid <= x) {result = mid;left = mid + 1;} else {right = mid - 1;}}return result;}
}

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

題目鏈接
思路：二分查找搜索即可，但是同樣注意乘積使用long。

class Solution {public boolean isPerfectSquare(int num) {int left = 0, right = num, mid = 0;while (left <= right) {mid = left + ((right - left) >> 1);long temp = (long) mid * mid;if (temp == num) {return true;} else if (num < temp) {right = mid - 1;}else {left = mid + 1;}}return false;}
}

六、27. 移除元素

題目鏈接
思路：用一個變量k計數，記錄相等元素的個數，不等則向前移動k個位置，最后返回數組長度減去k，因為k是要刪除的元素。

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

雙指針解法：一個快指針，一個慢指針，快指針向前遍歷，快指針指向的元素不等于target，就將元素賦值給慢指針，慢指針再前進一步，這個思路和上面有一個變量記錄要移動的距離類似，有異曲同工之妙。

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

雙向指針法：一個關鍵點維護好循環不變量，然后從左尋找等于target的值（即要被覆蓋的值），從右尋找不等于target的值（即要保留的值），找到之后即覆蓋一次。

class Solution {public int removeElement(int[] nums, int val) {int left = 0, right = nums.length - 1;while (left <= right) {while (left <= right && nums[left] != val) {left++;}while (left <= right && nums[right] == val) {right--;}if (left <= right) {nums[left++] = nums[right--];}}return left;}
}

七、26. 刪除有序數組中的重復項

題目鏈接
思路：因為數組是有序的，所以相同的元素都是緊挨著的，只需要比較相鄰元素即可，只要當前元素與上一個元素相等就給元素k加1，當不相等時，就要往前移動k個位置，數組的長度即為刪除掉K個元素之后的長度。

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

八、283. 移動零

題目鏈接
思路：這個移動零和前面刪除元素類似，快慢指針然后交換元素即可。

class Solution {public void moveZeroes(int[] nums) {int slow = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] != 0) {int temp = nums[slow];nums[slow++] = nums[i];nums[i] = temp;}}}
}

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

題目鏈接
思路：從前往后要拼接字符串，從后往前就簡單了，有#就記錄，沒有就跳過#數量，數量沒了就比較是否相等，不等就返回false

class Solution {public boolean backspaceCompare(String s, String t) {int i = s.length() - 1, j = t.length() - 1;int skipS = 0, skipT = 0;while (i >= 0 || j >= 0) {while (i >= 0) {if (s.charAt(i) == '#') {skipS++;i--;} else if (skipS > 0) {skipS--;i--;}else {break;}}while (j >= 0) {if (t.charAt(j) == '#') {skipT++;j--;} else if (skipT > 0) {skipT--;j--;}else {break;}}if (i >= 0 && j >= 0) {if (s.charAt(i) != t.charAt(j)) {return false;}} else {if (i >= 0 || j >= 0) {return false;}}i--;j--;}return true;}
}

十、977.有序數組的平方

題目鏈接
思路：找到正數負數分界線，然后歸并算法

class Solution {public int[] sortedSquares(int[] nums) {int n = nums.length;int negative = -1;for (int i = 0; i < n; ++i) {if (nums[i] < 0) {negative = i;} else {break;}}int[] ans = new int[n];int index = 0, i = negative, j = negative + 1;while (i >= 0 || j < n) {if (i < 0) {ans[index] = nums[j] * nums[j];++j;} else if (j == n) {ans[index] = nums[i] * nums[i];--i;} else if (nums[i] * nums[i] < nums[j] * nums[j]) {ans[index] = nums[i] * nums[i];--i;} else {ans[index] = nums[j] * nums[j];++j;}++index;}return ans;}}