数组类算法【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++) { // 设置子序列起点为isum = 0;for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为jsum += nums[j];if (sum >= s) { // 一旦发现子序列和超过了s，更新resultsubLength = 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;elsereturn 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 - offsetfor(;i < n - offset;i++){res[i][j] = count++;}//第二个for循环完之后，i = n - offsetfor(;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;}
};

未完待续.......