力扣刷题笔记

好记性不如烂笔头

刷题trick

27. 移除元素

题目描述

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

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

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

题解

暴力解法：

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:
    int removeElement(vector<int>& 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--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;
    }
};

双指针：

//时间复杂度：O(n^2)
//空间复杂度：O(1)
//元素的相对位置没有发生改变
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;  //慢指针指向
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            //当fastIndex指向val时，慢指针不动
            if (nums[fastIndex] != val) {  //当没找到val时，将快指针所指向的值nums[fastIndex]赋值给此时慢指针所指向的值nums[slowIndex]，因此此时慢指针指向的值一定是val。赋值即使移除值为val的元素。
                nums[slowIndex++] = nums[fastIndex];  //slowIndex++是为了保证当赋值发生时，慢指针也得往下走，因为当前slowIndex被赋值后肯定不是val了，slowIndex总是指向val所在的位置
            }
        }
        return slowIndex;
    }
};

例如：nums：2 3 3 4 8 3 9 1 val：3

快排式双指针法：

/**
* 相向双指针方法，基于元素顺序可以改变的题目描述改变了元素相对位置，确保了移动最少元素
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int leftIndex = 0;
        int rightIndex = nums.size() - 1;
        while (leftIndex <= rightIndex) {
            // 找左边等于val的元素
            while (leftIndex <= rightIndex && nums[leftIndex] != val){
                ++leftIndex;
            }
            // 找右边不等于val的元素
            while (leftIndex <= rightIndex && nums[rightIndex] == val) {
                -- rightIndex;
            }
            // 将右边不等于val的元素覆盖左边等于val的元素
            if (leftIndex < rightIndex) {
                nums[leftIndex++] = nums[rightIndex--];    //自加表示在新的元素区间(去除刚才检查过的)重新执行判断
            }
        }
        //循环执行结束的时候，leftIndex右边不为val的元素全部都赋值到leftIndex左边，因此leftIndex即为移除后数组长度
        return leftIndex;   // leftIndex一定指向了最终数组末尾的下一个元素
    }
};

注意：左指针用来找到元素值为val的元素，因此再循环里需要用nums[leftIndex]!=val，这样停止循环的时候就找到了值为val的元素

右指针用来找到元素值不是val的元素，因此循环里判断需要写nums[rightIndex]==val，同上原理

977. 有序数组的平方

题目描述

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

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

题解

暴力解法：先平方再排序

//时间复杂度O(n+nlogn)，快速排序
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        //先对元素都平方
        for (int i = 0; i < nums.size(); i++) {
            nums[i] *= nums[i];
        }
        //对nums进行快速排序
        quickSort(nums, 0, nums.size() - 1);
    }
    //划分函数
    int Partition(vector<int>& nums, int low, int high) {
        int pivot = nums[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (nums[j] <= pivot) {
                i++;
                int temp1 = nums[i];
                nums[i] = nums[j];
                nums[j] = temp1;
            }
        }
        int temp2 = nums[i + 1];
        nums[i + 1] = nums[high];
        nums[high] = temp2;
    }

    //快速排序算法
    void quickSort(vector<int>& nums, int low, int high) {
        if (low < high) {
            int partitionIndex = Partition(nums, low, high);
            quickSort(nums, low, partitionIndex - 1);
            quickSort(nums, partitionIndex + 1, high);
        }
    }
};

双指针解法

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;  //指向result数组末尾的指针
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};

209. 长度最小的子数组【经典】

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

题解

暴力解法

// 时间复杂度O(n^2)
// 存在一些测试用例超出时长限制
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        // 暴力解法
        int result = INT32_MAX;
        int sum = 0;  // 子序列总和
        int subLength = 0;  //计算子序列长度
        for (int i = 0; i < nums.size(); i++) {
            sum = 0;
            for (int j = i; j < nums.size(); j++) {
                sum += nums[j];        // 先累加在进行判断
                subLength = j - i + 1; //关键，计算子序列的长度
                if (sum >= target) {
                    result = result < subLength ? result : subLength;  // 条件运算符来判断是否更新result
                }
            }
        }
        return result == INT32_MAX ? 0 : result;
    }
};