代码随想录算法训练营第一天 | 704-二分查找、27-移除元素、977-有序数组的平方
LeetCode704 二分查找
题目链接：https://leetcode.cn/problems/binary-search/submissions/679153988/
卡哥文章讲解：https://programmercarl.com/0704.二分查找.html
卡哥视频讲解：https://www.bilibili.com/video/BV1fA4y1o715
第一遍 自己独立完成
一上来先自己做一遍，初看题目，分了三种情况画图：nums[mid] < target、nums[mid] > target、nums[mid] = target，再在外面套个while循环，自信满满点了提交hh，然后报错：
看了错误详情，恍然大悟，发现我的while循环条件有误：
如果循环判断条件只是left<right的话，遇到‘’nums={5},target=5‘’的情况就不会进入循环，mid都求不到就返回-1了，这显然不对
把这个条件改成left<=right，再遇到上述情况，就能够成功进入循环，改变result，返回正确结果了：
class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;int result = -1;while(left <= right){int mid = (left + right)/2;if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{result = mid;break;}}return result;}
}
第二遍 看讲解、深入刨析、做小结
二分法，把握好区间边界问题，分清楚题目区间到底是左闭右闭还是左闭右开
左闭右闭[left, right]
- 初始赋值 left = 0，right = nums.length - 1
- [1,1]是合法区间，所以while(left <= right)
- 当nums[mid] != target时，mid对应下标应排除出搜索区间，相应left = mid+1，right = mid-1
左闭右开[left, right)
- 初始赋值 left = 0，right = nums.length
- [1,1)是非法区间，所以while(left < right)
- 当nums[mid] != target时，mid对应下标应排除出搜索区间，相应left = mid+1，right = mid
LeetCode27 移除元素
题目链接：https://leetcode.cn/problems/remove-element/
文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP
第一遍 自己独立完成
初看题目，思路还算比较清晰：首先先建立一个nums2数组用于存放nums数组中不等于val的元素，再用k来计数。
第一次for循环，得到nums2数组和k的值
第二次for循环，再将nums2数组覆盖到nums数组上，这样nums数组前k个元素就能符合题目要求
class Solution {public int removeElement(int[] nums, int val) {int k = 0;int length = nums.length;int[] nums2 = new int[length];for(int i = 0;i < length;i++){if(nums[i] != val){nums2[k] = nums[i];k++;}}for(int i = 0;i < k;i++){nums[i] = nums2[i];}return k;}
}
第二遍 看讲解、深入刨析、做小结
看了讲解之后，发现还能使用双指针的思路解这道题目
快指针用来获取新数组中的元素，慢指针用来获取新数组中需要更新的位置
因为slow从0开始，所以它最后指向的下标，就是新数组中元素的个数
class Solution {public int removeElement(int[] nums, int val) {int slow = 0;int fast = 0;for(;fast < nums.length;fast++){if(nums[fast] != val){nums[slow] = nums[fast];slow++;}}return slow;}
}
LeetCode977 有序数组的平方
题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep
第一遍 自己独立完成
第一眼看到题目，首先想到的思路是先用一次for循环把nums数组所有元素平方，然后再用排序算法升序排序
这里挑了比较好实现的冒泡排序，虽然题目AC，但很显然，这代码并不优雅，还有很多可改进的空间
class Solution {public int[] sortedSquares(int[] nums) {int length = nums.length;for(int i = 0;i < length;i++){nums[i] = nums[i]*nums[i];}for(int i = 0;i < length;i++){for(int j = 0;j < length-i-1;j++){if(nums[j] > nums[j+1]){int temp = nums[j];nums[j] = nums[j+1];nums[j+1] = temp;}}}return nums;}
}
第二遍 看讲解、深入刨析、做小结
看了讲解以后，发现这题还能用双指针的思路求解，时间复杂度来到O(n)
一左一右两个指针逐渐向中间靠拢，由大到小生成一个新数组
最后用双指针的思路写了一遍，代码十分优雅呀hh：
class Solution {public int[] sortedSquares(int[] nums) {int length = nums.length;for(int i = 0;i < length;i++){nums[i] = nums[i] * nums[i];}int left = 0;int right = length - 1;int[] result = new int[length];int cnt = length - 1;while(left <= right){if(nums[left] <= nums[right]){result[cnt] = nums[right];cnt--;right--;}else{result[cnt] = nums[left];cnt--;left++;}}return result;}
}