_1LeetCode代码随想录算法训练营第一天-C++

LeetCode 题目列表：

• 704.二分查找
• 35.搜索插入位置
• 34.在排序数组中查找元素的第一个和最后一个位置
• 27 移除元素

704. 二分查找

根本原则：遍历到每个区间，并且不重复遍历任何一个元素。

易错点

while(left < right)
还是
while(left <= right)

if(nums[middle]>target)  //此时更新右区间
{right = middle;还是right = middle - 1;
}

循环不变量

左闭右闭区间：[left, right]

左闭右开区间：[left, right)

一般实际应用中不会使用左开右闭区间(left, right]

自己选择一个区间原则，然后写代码的时候严格遵守这个原则。

左闭右闭写法

/** @lc app=leetcode.cn id=704 lang=cpp** [704] 二分查找*/// @lc code=start
class Solution {
public:int search(vector& nums, int target) {int left = 0;int right = nums.size() - 1;//左闭右闭区间选择nums.size() - 1，左闭右开区间选择nums.size()while(left <= right)//左闭右闭区间选择<=，左闭右开区间选择<{int middle = left + ((right - left)/2);//等同于(left+right)/2，此句是为了防止溢出，因为left+right可能会超出int的取值范围if(nums[middle] > target)right = middle - 1;//左闭右闭区间选择middle-1，左闭右开区间选择middleelse if(nums[middle] < target)left = middle + 1;elsereturn middle;}return -1;}
};
// @lc code=end

左闭右开写法

/** @lc app=leetcode.cn id=704 lang=cpp** [704] 二分查找*/// @lc code=start
class Solution {
public:int search(vector& nums, int target) {int left = 0;int right = nums.size();//左闭右闭区间选择nums.size() - 1，左闭右开区间选择nums.size()while(left < right)//左闭右闭区间选择<=，左闭右开区间选择<{int middle = left + ((right - left)/2);//等同于(left+right)/2，此句是为了防止溢出，因为left+right可能会超出int的取值范围if(nums[middle] > target)right = middle;//左闭右闭区间选择middle-1，左闭右开区间选择middleelse if(nums[middle] < target)left = middle + 1;elsereturn middle;}return -1;}
};
// @lc code=end

27. 移除元素

数组理论基础

数组是连续存储的，删除一个元素，要将其后面的所有元素往前移动一位。

库函数的使用

如果一个问题直接使用库函数就可以解决，那么建议不要使用库函数；如果一个库函数只是解决问题的一小部分问题，并且在了解该库函数的实现机制以及其复杂度的情况下可以使用库函数。(我个人认为，如果自己能写出比库函数时间复杂度更低的代码，自己写代码会比较好。)

双指针的思路

fast：快指针指向新数组所需要的元素。

slow：慢指针指向需要更新元素的下标。

代码实现

使用暴力方法(即两个for循环)的复杂度为O(n^2)，使用双指针的方法的时间复杂度为O(n)。

/** @lc app=leetcode.cn id=27 lang=cpp** [27] 移除元素*/// @lc code=start
class Solution {
public:int removeElement(vector& nums, int val) {int slow = 0;for(int fast = 0;fast < nums.size();fast++){if(nums[fast] != val){nums[slow] = nums[fast];slow++;//当执行了移动操作时，将slow++}}return slow;//当循环结束时，slow正好表示数组大小}
};
// @lc code=end

练习

35. 搜索插入位置

/** @lc app=leetcode.cn id=35 lang=cpp** [35] 搜索插入位置*/// @lc code=start
class Solution {
public:int searchInsert(vector& nums, int target) {//如果元素存在于数组中，则就是题目704的问题int left = 0;int right = nums.size() - 1;int rightBorder = 0;//赋初值，此题对于初值是不在乎的while(left <= right){int middle = left + ((right - left)/2);//等同于(left+right)/2，此句是为了防止溢出，因为left+right可能会超出int的取值范围if(nums[middle] > target)//就是说target在middle的左边right = middle - 1;//此时更新右索引的值else if(nums[middle] < target)//就是说target在middle的右边{left = middle + 1;//此时更新左索引的值rightBorder = left;//此处记录右边界，是为了返回 按顺序插入的位置所作的工作}    elsereturn middle;//相等的话就返回当前的位置}//不相等的话要返回按顺序插入的位置return rightBorder;}
};
// @lc code=end

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

三种情况

• 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
• 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
• 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}

/** @lc app=leetcode.cn id=34 lang=cpp** [34] 在排序数组中查找元素的第一个和最后一个位置*/// @lc code=start
class Solution {
public:vector searchRange(vector& nums, int target) {int leftBorder = getLeftBorder(nums,target);int rightBorder = getRightBorder(nums,target);//情况1if(leftBorder == -2 || rightBorder == -2)return {-1, -1};//此处不能返回[]数组的原因是，vector没有这样的构造函数//情况3if(rightBorder - leftBorder > 1)return {leftBorder + 1, rightBorder - 1};//情况2return {-1, -1};}
private:int getLeftBorder(vector& nums, int target){int left = 0;int right = nums.size() - 1;int leftBorder = -2;//对于题目35的rightBorder，初值是不重要的，但此处的初值是重要的，是为了后面的区分while(left <= right){int middle = left + ((right - left)/2);//防止溢出if(nums[middle] >= target)//要将等于放在这里{right = middle - 1;leftBorder = right;}elseleft = middle + 1;}return leftBorder;}int getRightBorder(vector& nums, int target){int left = 0;int right = nums.size() - 1;int rightBorder = -2;//对于题目35的rightBorder，初值是不重要的，但此处的初值是重要的，是为了后面的区分while(left <= right){int middle = left + ((right - left)/2);//防止溢出if(nums[middle] > target)right = middle - 1;else//要将等于放在这里{left = middle + 1;rightBorder = left;}                }return rightBorder;}
};
// @lc code=end