网站维护 内容,网站突然掉排名,西安公司招聘,公司做网站怎么赚钱目录
数组基础知识补充
704. 二分查找
题目
左闭右闭方法
思路
代码
左闭右开方法
思路
代码
27. 移除元素
题目
暴力解法
思路
代码
双指针法
思路
代码 数组基础知识补充
1. 在leecode中#xff0c;数组一般是以vector容器的形式出现的#xff0c;虽然ve…目录
数组基础知识补充
704. 二分查找
题目
左闭右闭方法
思路
代码
左闭右开方法
思路
代码
27. 移除元素
题目
暴力解法
思路
代码
双指针法
思路
代码 数组基础知识补充
1. 在leecode中数组一般是以vector容器的形式出现的虽然vector的底层实现是array但严格来讲vector是容器不是数组
2. 数组元素的删除和增添都需要移动后续元素而且在实现的角度上看数组元素是不能删的只能用后一个元素将其覆盖掉然后再逐个覆盖就相当于向前移动后续元素了
3. C二维数组的存储空间是连续的但Java的不是Java中每一个外层数组都会有指针指向内层数组的地址。
704. 二分查找
题目 左闭右闭方法
左闭右闭意味着搜索区间是闭合的比如 [ 1 , 5 ]在这种区间搜索元素两个指针指向同一个元素时一定是有意义的因为区间涉及到的元素都在区间内
但如果搜索区间是半开半闭的那么就要考虑指针不能指向开的那个元素需要对代码进行一定的改动。
思路
用二分查找来做这道题是高效且简单的因为元素递增不重复
闭合区间二分的思路是分别给数组的最左边和最右边一个指针每次通过求两个指针指向地址的中间处那个元素的值来判断是否和目标值相等相等的话就返回中间处的值的下标不相等的话则分为两种情况
如果中间处的值小于目标值以为这中间处以及它的左边的元素都太小所以接下来我们就把搜索区间的左边界缩到中间处右边一个的元素那里
如果中间处的值大于目标值同理就把搜索区间的右边界缩小到中间处左边一个的元素那里。
因为这里是一个闭区间所以二分的终止条件就是两个指针指向相同这时候如果指向的元素不等于目标值那就返回 -1 。
代码
class Solution {
public:int search(vectorint nums, int target) {int l 0, r nums.size() - 1; int mid 0;while (l r) {mid l (r - l) / 2; // 防止l和r过大直接相加越界if (nums[mid] target)return mid;if (nums[mid] target)l mid 1;elser mid - 1;}// 带入一个有两个元素的数组测试样例就知道如果我们的目标是后者第一次的mid指向前面那个后面的l加一以后就指向目标了这时候l和r相等mid也和它们相等了可以得到结论//如果没有在while条件中写那么l和r指向相同时就直接跳出循环了这时候mid还未赋新值就会出错return -1;}
};
左闭右开方法
思路
大体上和上面的方法一样主要注意的是while的终止条件这时候就不能是指针指向相同了要把等于号去掉因为区间边界一开一闭两者显然是不能混为一谈的
另外开区间的那一边的搜索边界需要注意如果mid指向的元素大于目标值那么这时候将有边界缩小到mid即可不用减一具体见代码。
代码
class Solution {
public:int search(vectorint nums, int target) {int l 0, r nums.size();while (l r) {int mid l (r - l) / 2;if (nums[mid] target)l mid 1;else if (nums[mid] target)r mid; // 这时候不能再写mid-1了因为这是开区间mid肯定不可能是目标值了但是mid-1可能是如果把mid-1赋值给r那就意味着排除掉了mid-1elsereturn mid;}return -1;}
};
27. 移除元素
题目
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums [3,2,2,3], val 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums [0,1,2,2,3,0,4,2], val 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素。
暴力解法
思路
用内外两层指针外层指针遍历数组并寻找和目标值相等的元素找到以后使用内层指针遍历该元素之后的所有元素将所有元素往前移动一位其实就是用后一个元素将前一个元素覆盖掉
其中有一些细节需要注意首先是数组长度要实时记录最后返回的就是数组长度而且每次覆盖一轮后数组长度就减一了所以外层指针相应地也要减一。
代码
class Solution {
public:int removeElement(vectorint nums, int val) {int size nums.size();for (int i 0; i size; i) {if (nums[i] val) {for (int j i 1; j size; j)nums[j - 1] nums[j];i--;size--;} }return size;}
};
双指针法
思路
使用一快一慢两个指针用一个for循环完成两个for循环的任务。
首先定义一个慢指针在此基础上再定义一个快指针在数组里从头扫到尾如果遇见不等于目标值的数就把这个数赋值给慢指针相当于用慢指针创造了一个不包含目标值的新数组但是这个新数组使用的就是原数组的空间。
代码
class Solution {
public:int removeElement(vectorint nums, int val) {int slow 0;for (int fast 0; fast nums.size(); fast) {if (nums[fast] ! val)nums[slow] nums[fast];}return slow; // 因为最后slow还有一个所以这里直接返回不用1}
};
