一、前言
每天都有刷算法但是确实缺少一个陪跑，借着这次卡哥的训练营来整体的完成一次算法学习和一刷，说起来也挺惭愧的，进卡哥的知识星球也半年多了，还没说过话。。
网络异常，图片无法展示
|
闲话少说， 今天是算法训练营的第一天，目标是【数组】模块 LeetCode的 704，二分查找和 27. 移除元素
二、LeetCode 704. 二分查找
题目描述
网络异常，图片无法展示
|
解题思路
- 首先题中有说这是一个有序且升序的数组，那么肯定是二分法了
- 直接设置一个左右下标 left和 right，把控好有左右边界来遍历获取中间值就可以了
- 这里需要注意的是左右边界的判定
- 同时，因为是有序的，所以当数组最小值 nums[0]都小于 target或者数组最大值 nums[nums.length - 1] 大于 target那么证明这个数组中不可能存在 target
代码展示
public int search(int[] nums, int target) { // 因为 nums是有序的， 那最小的如果大于 target或者最大的小于 target，则代表数组中不可能存在大小 target的元素 if (nums[0] > target || nums[nums.length - 1] < target){ return -1; } int left = 0, right = nums.length - 1; // 因为是二分法，所以当左右双指针相等的时候代表数组遍历完成 while(left <= right){ // 获取当前左右边界的中间下标 int temp = left + (right - left) / 2; if (nums[temp] > target){ // 如果中间的树都大于 target，那么右边界向左移动 right = temp - 1; }else if (nums[temp] < target){ // 如果中甲的树小于 target， 那么左边界移动 left = temp + 1; }else{ return temp; } } return -1; } 复制代码
提交结果
网络异常，图片无法展示
|
总结
不得不说，很多东西不去练习真的会忘记，万万没想到这道题在之前我刷过四遍，虽然这次重做本题有些游刃有余，但是在细节处理上还是有一些小瑕疵，后续代码通过看代码随想录进行了相应的改进
网络异常，图片无法展示
|
LeetCode 27. 移除元素
题目描述
网络异常，图片无法展示
|
思路分析
- 首先这道题需要注意的是既要修改数组，还要记录数组中元素值非 val的个数
这道题我们还是可以使用双指针来做， 一个指针去遍历数组， 另外一个指针去修改数组的同时记录长度，具体可看代码展示
代码展示
public int removeElement(int[] nums, int val) { // left一直向前走， right记录长度 int left = 0, right = 0; for (; left < nums.length; left++) { // 如果当前元素为 val则 left继续向前走 if (nums[left] != val){ // 如果当前元素不为 val则修改，right++ nums[right++] = nums[left]; } } return right; } 复制代码
提交结果
网络异常，图片无法展示
|
补充
在【代码随想录】网站中，本题还给了另外一种解法，相向双指针法，但是相对来讲更繁琐且不易理解， 具体如下
网络异常，图片无法展示
|
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
题目描述
网络异常，图片无法展示
|
思路分析
- 老规矩，认真审题
- 这道题题目写的是非递减数组
- 目标值的开始结束位置
- 时间复杂度为 0（log n）
三种情况：
- 不存在
- 存在两个 val
- 只有一个 val
依旧是双指针来做，不过这次是用两个双指针
代码展示
class Solution { public int[] searchRange(int[] nums, int target) { int left = 0, right = nums.length - 1; // 因为是二分法，所以当左右双指针相等的时候代表数组遍历完成 while(left <= right){ // 获取当前左右边界的中间下标 int temp = left + (right - left) / 2; if (nums[temp] > target){ // 如果中间的树都大于 target，那么右边界向左移动 right = temp - 1; }else if (nums[temp] < target){ // 如果中甲的树小于 target， 那么左边界移动 left = temp + 1; }else{ left = temp; right = temp; while(left > 0 && nums[left - 1 ] == target){ left--; } while(right <= nums.length - 2 && nums[right + 1] == target){ right++; } return new int[]{left, right}; } } return new int[]{-1,-1}; } } 复制代码
结果提交
网络异常，图片无法展示
|
总结
笑死了，因为偷懒直接 copy的 704的代码，然后缝缝补补，出了好几个 bug，是我自信了，一个小扒菜的自不量力, 但是好在结果是好的
网络异常，图片无法展示
|
在评论区 Carl哥给出了另外一种解法，使用两次二分法查找，分别去查找左边界和右边界，感兴趣的可以试一下
LeetCode 35. 搜索插入位置
题目描述
网络异常，图片无法展示
|
思路分析
- 依旧是二分法的思路
- 需要注意的是返回值要是left， 因为当前left > right了证明若存在 target元素就应该在当前的 left下标位置
代码展示
class Solution { public int searchInsert(int[] nums, int target) { if (nums[0] > target ){ return 0; } if (nums[nums.length - 1] < target){ return nums.length; } int left = 0, right = nums.length - 1, temp = 0; // 因为是二分法，所以当左右双指针相等的时候代表数组遍历完成 while(left <= right){ // 获取当前左右边界的中间下标 temp = left + (right - left) / 2; if (nums[temp] > target){ // 如果中间的树都大于 target，那么右边界向左移动 right = temp - 1; }else if (nums[temp] < target){ // 如果中甲的树小于 target， 那么左边界移动 left = temp + 1; }else{ return temp; } } return left ; } } 复制代码
提交结果
网络异常，图片无法展示
|
总结
万万没想到，这道题我竟然错了这么多次，我真的有这么菜的吗。。。
网络异常，图片无法展示
|
