数组类算法【leetcode】

704. 二分查找

2024.11.06

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

二分查找用于有序数组中，没有重复的数组。首先需要定义一个头（left）和尾(right)，最后通过mid和target对比不断修改头和尾指向的位置。

【需要注意区间问题，根据区间的开和闭决定边界条件】

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else if(nums[mid] == target)
            {
                return mid;
            }
            else if(nums[mid] < target)
            {
                left = mid + 1;
            }
        }
        return -1;

    }
};

推荐练习 leetcode35.

27.移除元素

2024.11.07

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

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

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

这里其实有序无序都可以，正常的调用内置函数的复杂度是O（n），是用的两个for循环进行暴力解。这里要求我们原地执行，所以用一个for循环解决。

【这里我们要知道数组的删除，其实和我们平时理解的删除并不一样，数组的删除前其实是将不需要的元素进行覆盖，内存中他还是存在的】

这里用到了快慢指针，一个fast和一个slow，fast用于遍历整个数组，所以for循环的执行条件就应该是当fast小于数组长度的时候就进行一次循环，而slow指针怎么变化呢？如果nums[fast]不是需要的val，那就令nums[fast] = nums[slow]，当nums[fast] = val的时候，slow指针的位置不需要变，这样可以把slow看作一个新的数组，用于装不包含val值的数组，当nums[fast]再次不等于val的时候将nums[fast]再次赋给nums[slow]，slow指针再次向后移动。

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

977.有序数组的平方

2024.11.07

题目：给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。力扣题目链接

思路和上一题类似，也是用双指针，这里两头的平方一定会大于中间的值的平方，所以新建立一个数组从后往前放置原数组的平方的值。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        int k = nums.size() - 1;   //因为数组的两头的数字的绝对值一定大于中间的，所以result数组从后往前放
        vector<int> result(nums.size(), 0);
        for(; left <= right;)
        {
            if(nums[left] * nums[left] < nums[right] * nums[right])
            {   
                result[k--] = nums[right] * nums[right];
                right --;
            }
            else
            {
                result[k--] = nums[left] * nums[left];
                left ++;
            }
        }
        return result;
    }
};

209.长度最小的子数组

2024.11.08

这是第一道中等题，但其实也挺简单的力扣题目链接

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

1.暴力解

这道题目暴力解法当然是两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O(n^2)。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX; // 最终的结果
        int sum = 0; // 子序列的数值之和
        int subLength = 0; // 子序列的长度
        for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
            sum = 0;
            for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                sum += nums[j];
                if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                    subLength = j - i + 1; // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

2.最优解

滑动窗口，有点类似之前的双指针的解法，不断更新子序列的两头指针，只要窗口中的sum大于target，就把左边的指针往右移一格，如果sum一直小于target就右边的指针持续后移。那么我们就可以通过记录每次得到的小于sum的子数组，并每次进行比较，及时更新最小值。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int length = 0;                     //滑动窗口的长度（子数组）

        //在算法中，当你需要找到一组数中的最小值时，可以将初始值设为 INT32_MAX，这样任何实际的数值都会比它小。
        int result = INT32_MAX;

        for(right=0;right < nums.size();right++)
        {
            sum += nums[right];
            while(sum >= target)
            {
                length = right - left + 1;  //截至sum 小于 target, 数组的长度（未必是最小的）
                if (result > length)
                {
                    result = length;        // 更新最小子数组长度
                }
                sum -= nums[left++];
            }
        }
        if(result == INT32_MAX)
            return 0;
        else
            return result;
    }
};

不要以为for里放一个while就以为是O(n^2)啊，主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。

59.螺旋矩阵II

2024.11.08

这是第一道中等题，思路很简单，只需要注意边界条件，按顺序赋值就完了

题目：给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

思路:

模拟顺时针画矩阵的过程:

填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上

由外向内一圈一圈这么画下去.......【我按照左闭右开的原则】统一填充方式可以很大程度避免自己写到后面乱掉了。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int x = 0;
        int y = 0;
        int loop = n / 2;       //  循环次数
        int offset = 1;         // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int mid = n / 2;        //  n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1;          //  用来给矩阵中每一个空格赋值
        int i, j;
        while(loop--)
        {
            i = x; 
            j = y;

            for(;j < n - offset;j++)
            {
                res[i][j] = count++;
            }
            //第一个for循环完之后，j = n - offset

            for(;i < n - offset;i++)
            {
                res[i][j] = count++;
            }
            //第二个for循环完之后，i = n - offset

            for(;j > y;j--)
            {
                res[i][j] = count++;
            }

            for(;i > x;i--)
            {
                res[i][j] = count++;
            }

 // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            x++;
            y++;

 // offset 控制每一圈里每一条边遍历的长度
            offset++;
        }
            if (n % 2) 
            {
                res[mid][mid] = count;
            }
        return res;
    }
};

未完待续.......