LeetCode【代码随想录】刷题（数组篇）
704.二分查找
题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
思路：简单的二分法即可，注意等号边界
通过代码：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while(left <= right)
{
int mid = (left + right) / 2;
if(nums[mid] == target)
return mid;
else if(target < nums[mid])
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
};
27.移除元素
题目：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
- 更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。 - 返回
k。
思路一：直接按照题目意思来，查到一个删一个。需要掌握vector的erase函数用法。注意：erase会返回删除元素后的下一个迭代器，如果要删除的元素是最后一个元素会返回end迭代器。
通过代码：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
for(vector<int>::iterator it = nums.begin(); it != nums.end();)
{
if(*it == val)
it = nums.erase(it);
else
it++;
}
return nums.size();
}
};
思路二：双指针，一个指针遍历数组，另一个指针直接从头开始写在输入的数组上。
通过代码：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0;
for(int i = 0; i < nums.size(); i++)
{
if(nums[i] != val)
nums[left++] = nums[i];
}
return left;
}
};
977.有序数组的平方
题目：给你一个按 非递减顺序 排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按 非递减顺序 排序。
思路：简单粗暴的方法，平方完之后用sort排个序即可。但是时间复杂度为nlogn，追求进阶考虑使用双指针。观察示例可知，平方最大的一定在两端。于是我们的双指针从两边往中间找最大的平方添加进数组，最后逆序一下即可。
通过代码：
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> res;
int left = 0, right = nums.size() - 1;
while(left <= right)
{
int num1 = pow(nums[left], 2);
int num2 = pow(nums[right], 2);
if(num1 > num2)
{
res.push_back(num1);
left++;
}
else
{
res.push_back(num2);
right--;
}
}
reverse(res.begin(), res.end());
return res;
}
};
209.长度最小的子数组
题目：给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [nums[l], nums[l+1], ..., nums[r-1], nums[r]] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
思路一：前缀和+二分查找，暴力是过不了的，由于数组都是正数，所以前缀和一定是递增的，于是可以用二分。得到前缀和数组后，分别以每个元素为起点，用二分找到子数组并计算结果，更新最小长度。
通过代码：
class Solution
{
public:
int minSubArrayLen(int target, vector<int> &nums)
{
vector<int> presum{0};
for (int i = 0; i < nums.size(); i++)
presum.push_back(presum[i] + nums[i]);
if (presum.back() < target) //排除无解情况
return 0;
int res = INT_MAX;
for (int i = 0; i < presum.size() - 1; i++)
{
// 往后就可能满足不了条件，可提前退出
if(presum[i] + target > presum.back())
break;
int left = i + 1, right = presum.size() - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (presum[mid] - presum[i] >= target)
right = mid - 1;
else
left = mid + 1;
}
res = min(res, left - i);
}
return res;
}
};
思路二：滑动窗口，初始两个指针都在最左边，首先右指针先向右滑，直到窗口刚好大于target，然后左指针慢慢向右滑，试图缩小窗口的大小。一旦窗口小于target了，右指针继续向右滑，重复上述过程并更新最小的区间长度。
通过代码：
class Solution
{
public:
int minSubArrayLen(int target, vector<int> &nums)
{
int sum = 0;
int res = INT_MAX;
int left = 0, right = 0;
while(right < nums.size())
{
sum += nums[right];
while(sum >= target)
{
res = min(res, right - left + 1);
sum -= nums[left];
left++;
}
right++;
}
return res == INT_MAX ? 0 : res;
}
};
59.螺旋矩阵II
题目：给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
思路：模拟即可。一圈一圈的往里填数，每一圈又可分解为四条等长的边，确定好每条边的起点和长度即可。
通过代码：
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int cnt = 1;
vector<vector<int>> matrix(n, vector<int>(n));
for (int i = 0; i < ceil(n / 2.0); i++)
{
int len = n - i * 2 - 1;
if (len == 0)
matrix[i][i] = cnt;
for (int j = 0; j < len; j++)
matrix[i][i + j] = cnt++;
for (int j = 0; j < len; j++)
matrix[i + j][n - 1 - i] = cnt++;
for (int j = 0; j < len; j++)
matrix[n - 1 - i][n - 1 - i - j] = cnt++;
for (int j = 0; j < len; j++)
matrix[n - 1 - i - j][i] = cnt++;
}
return matrix;
}
};
原文地址：https://blog.csdn.net/m0_51507437/article/details/144096793
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！