day1-526互联

数组理论知识

对于C++而言，C++在二维数组的地址是连续的。

void test_arr() {
    int array[2][3] = {
        {0, 1, 2},
        {3, 4, 5}
    };
    cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;
    cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
}

int main() {
    test_arr();
}

测试结果为

704 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

使用二分法前提：数组为有序数组，数组中无重复元素

方法一：左闭右闭

 1 class Solution {
 2 public:
 3     int search(vector<int>& nums, int target) {
 4         int left=0;
 5         int right=nums.size()-1;
 6         while(left<=right)
 7         {
 8             int mid=(left+right)/2;
 9             if (nums[mid]<target)
10             {
11                 left=mid+1;
12             }else if(nums[mid]>target)
13             {
14                 right=mid-1;
15             }else{
16                 return mid;
17             }
18         }
19         return -1;
20 
21     }
22 };

方法二：左闭右开

 1 class Solution {
 2 public:
 3     int search(vector<int>& nums, int target) {
 4         int left=0;
 5         int right=nums.size();//从开始定义起就要遵守左闭右开
 6         while(left<right)
 7         {
 8             int mid=(left+right)/2;
 9             if (nums[mid]<target)
10             {
11                 left=mid+1;//左端点要取一个有效值，此时已知mid无效，故加一
12             }else if(nums[mid]>target)
13             {
14                 right=mid;//右端点实际上取不到，故可取已知无效mid值，实际有效值为mid-1
15             }else{
16                 return mid;
17             }
18         }
19         return -1;
20 
21     }
22 };

27.移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

方法一：暴力法

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len=nums.size();
        for (int i=0;i<len;i++)
        {
            if(nums[i]==val)
            {
                for(int j=i;j<len-1;j++)
                {
                    nums[j]=nums[j+1];
                }
                i--;
                len--;
            }
        }
        return len;
    }
};

方法二：双指针

个人感觉快指针用于浏览整个数组，慢指针是实际要留下来的值。如果快指针所浏览到的数不符合要求则不装入慢指针为首的数组。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int fast=0,slow=0;
        for(int fast=0;fast<nums.size();fast++)
        {
            if(nums[fast]!=val)
            {
                nums[slow]=nums[fast];
                slow++;
            }
        }
        return slow;
    }
};