day1 记录代码随想录第一天
第一题 力扣704 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
题目链接：. - 力扣（LeetCode）
本题思路为二分查找法。
定义两个边界left和right，取一个中间指针mid=(left+right)/2，如果考虑到数据越界，可以使用另一个公式：mid=left+(right-left)/2，结果都是一样的。
然后判断mid元素与target的大小，如果相等则直接输出，如果mid元素小于rarget，则left=mid+1，再次进循环。
考虑跳出循环的条件，主要考虑left=right的情况，如果存在这种情况，则left=right=mid，当mid=target时，直接输出mid，当不等时，则一定会在if以后出现left>right，则跳出循环，输出-1，由此，说明left=right是有意义的，需要在循环内加以讨论。
//二分查找
class Solution {
public:
int search(vector& nums, int target) {
int left = 0, mid = 0, right = 0;
right = nums.size() - 1;
while (left <= right) {
mid = (left + right) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else
return mid;
}
return -1;
}
}; 以上方法为闭区间方法，即定义target在[left,right]区间内，还有一种方法为左闭右开区间，即target在[left,right)区间内，此时需要考虑right 的初始值不需要再-1，且每次循环中right赋值也不需要再-1，代码如下：
//二分左闭右开
class Solution {
public:
int search(vector& nums, int target) {
int left = 0, mid = 0, right = 0;
right = nums.size();
while (left < right) {
mid = (left + right) / 2;
if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else
return 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。
你不需要考虑数组中超出新长度后面的元素
题目链接：. - 力扣（LeetCode）
本题有两种解法，暴力求解和双指针
首先尝试暴力求解：
所谓暴力求解，就是指遍历、枚举、穷举等等方法
第一次编写：
class Solution {
public:
int removeElement(vector& nums, int val) {
int length = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] = val) {
for (int j = i; j = nums.size() - 1; j++) {
nums[j] = nums[j + 1];
}
length++;
}
}
return nums.size() - length;
}
}; 编译出错，怀疑是内存溢出了。
于是修改代码，此处nums.size()重复使用了三次，考虑直接使用中间变量length来替代。
再思考使用length表示数组长度，于是每次循环只用遍历length长度的数组即可，当发现与val相同的元素时，将第i个元素后面的元素覆盖到前一位。此时后面所有的元素都前移一位，所以length应减一，同时由于第i个元素被覆盖了，相当于此刻的第i个元素没有遍历，但是循环还是在往下走，将i减一可以将循环重走这一步，至此应该可以达到效果。
代码如下：
//暴力求解
class Solution {
public:
int removeElement(vector& nums, int val) {
int length = nums.size();
for (int i = 0; i < length; i++) {
if (nums[i] == val) {
for (int j = i; j < length - 1; j++) {
nums[j] = nums[j + 1];
}
length--;
i--;
}
}
return length;
}
}; 提交通过！
同时有个很有意思的地方是用时0ms，超过100%用户，虽然知道这可能是系统内部计算有问题，但是还是挺激励自己的，开心！
双指针法：
双指针法是指在遍历对象的过程中，不仅仅使用一个指针遍历，而使用两个指针同时遍历访问，依两个指针访问方向相同和相反分为快慢指针和对撞指针。
快慢指针解法：
定义一个快指针fast，一个慢指针slow，使用快指针遍历整个数组，慢指针遍历不含val元素的数组，每当快指针遍历一个非val元素，就将慢指针所指元素对应此时快指针所指元素，由于循环条件中只有快指针++，所以应设置慢指针++语句，而当快指针遍历到val元素时，不需要做任何操作，直接快指针遍历过去，此时慢指针没变，慢指针所指元素没变，即慢指针所指元素对应的数组忽略了此元素，达成要求！
代码如下：
//双指针法（快慢指针）
class Solution {
public:
int removeElement(vector& nums, int val) {
int slowIndex = 0, fastIndex = 0;
for (fastIndex = 0; fastIndex < nums.size() ; fastIndex++) {
if (nums[fastIndex] != val) {
nums[slowIndex] = nums[fastIndex];
slowIndex++;
}
}
return slowIndex;
}
}; 对撞指针解法：
定义一个左指针和一个右指针，分别从两边遍历，每次遍历中，当左指针先找到一个val，在从右指针反方向找一个非val，并将两个指针对应的元素互换，之后左指针右移，右指针左移。需要注意的是，在整个过程中，需要保证左指针在右指针的左边，否则为越界。
代码如下：
//双指针法（对撞指针）
class Solution {
public:
int removeElement(vector& nums, int val) {
int leftIndex = 0, rightIndex = 0;
rightIndex = nums.size() - 1;
while(leftIndex <= rightIndex) {
//找左边等于val的元素
while (leftIndex <= rightIndex && nums[leftIndex] != val) {
++leftIndex;
}
//找右边不等于val的元素
while (leftIndex <= rightIndex && nums[rightIndex] == val) {
--rightIndex;
}
//互换元素
if (leftIndex <= rightIndex) {
nums[leftIndex] = nums[rightIndex];
leftIndex++;
rightIndex--;
}
}
return leftIndex;
}
}; 最后一个判断语句中，曾考虑过<= 和<是否有不一样的结果，然后发现永远不会出现left=right的情况，所以，这里及时使用<=，其效果也跟<是一样的。