代码随想录算法训练营day1 | 704.二分查找 27.移动元素

数组理论基础

• （一维）数组是存放在连续内存空间上的相同类型数据的集合。
• 数组下标从0开始。
• 数组内存地址连续。

正因如此，删除数据的时候难免要移动其他元素的位置。

注意array和vector区别：array不能删除元素，只能覆盖。

拓展
C++中二维数组的地址也是连续的。
但是在java中却是无规则的。

刷题笔记day1

704.二分查找

文章讲解：代码随想录
视频讲解：哔哩哔哩
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

• while (nums[midIndex] != target)，导致找不到数据的时候陷入死循环。
• int midIndex = leftIndex + (rightIndex - leftIndex) >> 1
  注意>>优先级较低要加()。

自己的代码

用的是左闭右闭的方法来实现：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int leftIndex = 0;
        int rightIndex = nums.size() - 1;
        
        while (leftIndex <= rightIndex) {
            int midIndex = leftIndex + ((rightIndex - leftIndex) >> 1);
            if (nums[midIndex] > target) {
                rightIndex = midIndex - 1;
            }
            else if (nums[midIndex] < target) {
                leftIndex = midIndex + 1;
            }
            else {
                return midIndex;
            }
        }
        return -1;
    }
};

看了题解后的收获

学习了左闭右开的思想。重点在while (left < right)以及right = middle与左闭右闭不同;

27.移除元素

文章讲解：代码随想录
视频讲解：哔哩哔哩
是否自己做出来通过全部用例：是

自己的代码

用的是iter迭代器的方法来实现，类似于题解的版本一：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int sametovalue = 0;
        int count = 0;
        auto iter = nums.begin();

        while (count != nums.size()) {
            ++count;
            if (*iter == val) {
                for (auto it = iter; it != nums.end() - sametovalue - 1; ++it) {
                    *it = *(it + 1) ;
                }
                ++sametovalue;
            }
            else {
                ++iter;
            }
        }
        return (nums.size() - sametovalue);
    }
};

看了题解后的收获

学习和掌握了双指针法的基本思想，学会了使用快慢指针。