leetcode刷题–数组
此篇为leetcode刷题笔记。跟随代码随想录的顺序去刷题。这里的学习方法为:先借助代码随想录的资料入门算法，最后再去leetcode上完整刷题。下面为数组专题的学习笔记
二分查找
前提
- 元素不重复
- 有序序列
思路
不断将区间从中间分为两份，将中间值与目标值相比较，决定下一次搜索区间。
注意
边界条件的处理。理清除思路，区间为左闭右闭还是左闭右开。
如果是左闭右闭区间：
while循环条件:left <= right。- 边界如何重新赋值:以右边界为例
right = middle - 1.middle位置元素已经完成比较。而且区间可取右边界。
如何判断是否取等: 在于取等后区间是否为合法的左闭右闭区间。是不是我们需要搜索的区间。
如果是左闭右开区间：
while循环条件为left < right。- 边界如何重新赋值:以右边界为例
right = middle.middle位置元素完成比较。但区间取不到右边界。
代码
左闭右闭区间写法:
int search(int* nums, int numsSize, int target) {
int left = 0;
int right = numsSize - 1;
int middle = 0;
while (left <= right) {
middle = left + (right - left) / 2;
if (nums[middle] < target) {
left = middle + 1;
}
else if (nums[middle] > target) {
right = middle - 1;
}
else {
return middle;
}
}
return -1;
}
左闭右开区间写法:
int search(int* nums, int numsSize, int target) {
int left = 0;
int right = numsSize;
int middle = 0;
while (left < right)
{
middle = left + ((right - left) / 2);
if (nums[middle] < target)
{
left = middle + 1;
}
else if (nums[middle] > target)
{
right = middle;
}
else
{
return middle;
}
}
return -1;
}
移除元素
思路
这里提供两种解决思路:
- 一种为暴力解法：利用两层循环；外层循环找目标元素，内层移动后面元素。
- 双指针法：快指针遍历所有元素，找非目标元素。找到一个元素，赋值给慢指针，慢指针再向前移动。
代码
- 暴力解法
int removeElement(int *nums, int numsSize, int val)
{
int i,j;
int count = 0;
for (i=0; i<numsSize; i++)
{
if (nums[i] != val)
{
continue;
}
for (j=i+1; j<numsSize; j++)
{
nums[j-1] = nums[j];
}
count++;
i--; //由于后面的所有元素向前移动一个,i不需要再加
}
return count;
}
- 双指针法
int removeElement(int* nums, int numsSize, int val)
{
int* fastPtr = nums;
int* slowPtr = nums;
int count = 0;
for (int i=0; i<numsSize; i++)
{
if (fastPtr[i] != val)
{
*slowPtr = fastPtr[i];
slowPtr++;
count++;
}
}
return count;
}
长度最小的子数组
题目
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
- 输入：s = 7, nums = [2,3,1,2,4,3]
- 输出：2
- 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
提示：
- $1 <= target <= 10^9$
- $1 <= nums.length <= 10^5$
- $1 <= nums[i] <= 10^5$
思路
暴力解法
思路: 使用两次循环，外层循环表示子序列开始位置；内层循环找满足和为 target 的子序列。
#define MAX_INT32 0x7fffffff
int minSubArrayLen(int target, int* nums, int numsSize)
{
int result = MAX_INT32; // 最终的结果
int sum = 0; // 子序列的数值之和
int subLength = 0; // 子序列的长度
for (int i = 0; i < numsSize; i++) { // 设置子序列起点为i
sum = 0;
for (int j = i; j < numsSize; 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 == MAX_INT32) ? 0 : result;
}
滑动窗口
此题采用滑动窗口的方法。所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置。起始位置与终止位置类似于双指针。
思路: 区别于暴力解法，外层循环表示子序列终止位置 j 的循环。j 向后移动去找到满足 target 的子序列，i 再由内循环向后移动，去寻找满足 target 且长度最短的子序列。
简单来说：先移动子序列的结束位置。找到满足 target 的子序列后，开始向后移动起始位置，直到不满足 target 后再向后移动子序列的结束位置。不断循环该过程。
#define MAX_INT32 0x7fffffff
int minSubArrayLen(int target, int* nums, int numsSize) {
int subStart = 0;
int subEnd = 0;
int sum = 0;
int len = MAX_INT32;
for (subEnd=0; subEnd<numsSize; subEnd++) {
sum += nums[subEnd];
while(sum >= target) {
len = (len > (subEnd - subStart + 1)) ? (subEnd - subStart + 1) : len;
sum -= nums[subStart];
subStart++;
}
}
return (len == MAX_INT32) ? 0 : len;
}
有序数组的平方
题目
给你一个按非递减顺序排序的整数数组 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 <= 10^4$
- $-10^4 <= nums[i] <= 10^4$
- nums 已按 非递减顺序 排序
思路
规律：有序数组平方后，较大的数位于数组两端，中间的数较小。
方法：使用双指针的方法，指定两个指针 left 和 right 指向数组两端。比较两个位置大小。新数组使用非递减顺序排序，则将较大的数据放到新数组尾部。再将两个指针向中间移动。直到 left > right. 表示遍历完数组。
代码
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
int left = 0;
int right = numsSize - 1;
int *ret = (int *)malloc(sizeof(int) * numsSize);
//while(left <= right)
for (int i=0; i<numsSize; i++) {
if ((nums[left] * nums[left]) >= (nums[right] * nums[right])) {
ret[numsSize-i-1] = nums[left] * nums[left];
left++;
}
else {
ret[numsSize-i-1] = nums[right] * nums[right];
right--;
}
}
*returnSize = numsSize;
return ret;
}
螺旋矩阵
题目
给你一个正整数n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix。
- 示例1
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
-
示例 2：
输入：n = 1
输出：[[1]]
提示： 1 \leq n \leq 20
思路
此题不涉及算法，关键在于模拟过程，总结不同n，螺旋矩阵排列方式。遵循循环不变量的原则(左闭右闭/左闭右开)。
模拟顺时针填充过程。为了统一处理边界问题，采用左闭右开的原则。
当n=3时，第一层顶部取 [1,3) 右边取 [3,5) 下面取 [5,7) 右边取 [7,9)。最后中间填充9
当n=4时，第一层顶部取 [1,4) 右边取 [4,7) 下面取 [7,10) 右边取 [10,13)；第二层顶部取 [13,14) 右边取 [14,15) 下面取 [15,16) 右边取 [16,17)
总结：螺旋矩阵层数为 n / 2 , 每层数字个数: n – 1 – 2 * i。i 为层数 – 1。 n为奇数时，最后在正中间位置(n/2, n/2)放 n^2
代码
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes) {
int i,j;
int loop = 0;
int layer = 1;
int num = 1;
int offset = 0;
*returnSize = n;
int **result = (int **)malloc(n * sizeof(int *));
*returnColumnSizes = (int *)malloc(n * sizeof(int));
for (i=0; i<n; i++)
{
result[i] = (int *)malloc(n * sizeof(int));
(*returnColumnSizes)[i] = n;
}
loop = n / 2;
for (i=0; i<loop; i++)
{
offset = (n - 1) - (2 * i);
if (offset <= 0)
{
break;
}
//填充顶边
for (j=layer-1; j<layer+offset-1; j++)
{
result[layer-1][j] = num++;
}
//填充右边
for (j=layer-1; j<layer+offset-1; j++)
{
result[j][n-layer] = num++;
}
//填充底边
for (j=n-layer; j>n-layer-offset; j--)
{
result[n-layer][j] = num++;
}
//填充左边
for (j=n-layer; j>n-layer-offset; j--)
{
result[j][layer-1] = num++;
}
layer++;
}
if (n % 2)
{
result[n / 2][n / 2] = n * n;
}
return result;
}
注意
二维数组申请方式
int **array = (int **)malloc(RowNums * sizeof(int *)); //每行数组起始指针
for (int i=0; i<RowNums; i++)
{
array[i] = (int *)malloc(ColumnNums * sizeof(int));
}