力扣hot100刷题——11~20

news/2025/2/26 0:57:56

文章目录

  • 11.滑动窗口最大值
    • 题目描述
    • 思路：滑动窗口+单调队列
    • code
  • 12.最小覆盖子串
    • 题目描述
    • 思路：双指针/滑动窗口+哈希
    • code Ⅰ
    • code Ⅱ
  • 13.最大子数组和
    • 题目描述
    • 思路：dp/贪心
    • code
  • 14.合并区间
    • 题目描述
    • 思路：贪心
    • code
  • 15.轮转数组
    • 题目描述
    • 思路：反转法
    • code
  • 16.除自身以外数组的乘积
    • 题目描述
    • 思路：前缀积+后缀积
    • code
  • 17.缺失的第一个正数
    • 题目描述
    • 思路：哈希
    • code
  • 18.矩阵置零
    • 题目描述
    • 思路：哈希
    • code
    • code(优化)
  • 19.螺旋矩阵
    • 题目描述
    • 思路：模拟/螺旋矩阵
    • code
  • 20.旋转图像
    • 题目描述
    • 思路一：水平翻转+转置
    • code

11.滑动窗口最大值

题目描述

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

思路：滑动窗口+单调队列

  1. 单调队列：
    • 使用一个双端队列（Deque）来存储数组的索引。
    • 队列中的元素按从大到小的顺序排列，队头元素是当前窗口的最大值。
  2. 滑动窗口：
    • 遍历数组，维护一个大小为 k 的滑动窗口。
    • 在遍历过程中，动态更新队列，确保队列中的元素始终在窗口内，并且按从大到小的顺序排列。
  3. 队列更新规则：
    • 移除不在窗口内的元素：如果队头元素已经不在当前窗口内，则将其从队列中移除。
    • 移除小于当前元素的元素：从队尾开始，移除所有小于当前元素的元素，确保队列的单调性。
    • 将当前元素加入队列：将当前元素的索引加入队尾。
  4. 记录结果：
    • 当窗口形成时（i >= k - 1），将队头元素（当前窗口的最大值）加入结果数组。

我认为本题真的很难，第一次不懂的话可以过段时间再看。

code

#include <stdio.h>
#include <stdlib.h>

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
    if (nums == NULL || numsSize == 0 || k == 0) {
        *returnSize = 0;
        return NULL;
    }

    *returnSize = numsSize - k + 1; // 计算结果数组的大小
    int* result = (int*)malloc(sizeof(int) * (*returnSize)); // 分配结果数组

    int queue[numsSize]; // 使用数组模拟双端队列
    int head = 0, tail = -1; // 队列的头和尾

    for (int i = 0; i < numsSize; i++) {
        // 移除队列中不在当前窗口内的元素
        if (head <= tail && queue[head] < i - k + 1) {
            head++;
        }

        // 移除队列中所有小于当前元素的元素
        while (head <= tail && nums[queue[tail]] < nums[i]) {
            tail--;
        }

        // 将当前元素的索引加入队列
        queue[++tail] = i;

        // 如果窗口已经形成，将队列头部的元素加入结果数组
        if (i >= k - 1) {
            result[i - k + 1] = nums[queue[head]];
        }
    }

    return result; // 返回结果数组
}

12.最小覆盖子串

题目描述

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

思路：双指针/滑动窗口+哈希

题目中的4个提示已经给出了本题思路：

  • Use two pointers to create a window of letters in s, which would have all the characters from t.
    使用两个指针在 s 中创建一个字母窗口，该窗口将包含 t 中的所有字符。
  • Expand the right pointer until all the characters of t are covered.
    展开右指针，直到覆盖 t 的所有字符。
  • Once all the characters are covered, move the left pointer and ensure that all the characters are still covered to minimize the subarray size.
    覆盖所有字符后，移动左指针并确保仍覆盖所有字符，以最小化子数组大小。
  • Continue expanding the right and left pointers until you reach the end of s.
    继续展开左右指针，直到到达 s 的末尾。

具体代码思路：

  1. 初始化哈希表：
    • hasht[128]：记录 t 中每个字符的出现次数。
    • hashs[128]：记录当前窗口内字符的出现次数。
  2. 滑动窗口双指针：
    • left 和 right 指针分别表示窗口的左右边界。
    • right 向右扩展窗口，直到窗口包含 t 的所有字符。
    • 当窗口有效时，left 向右收缩以寻找更小的窗口。
  3. 计数器 count 的作用：
    • 统计当前窗口中恰好满足 t 字符需求的字符数量。
    • 当 count == strlen(t) 时，说明窗口已覆盖 t 的所有字符。
  4. 更新最小窗口：
    • 每次窗口有效时，记录窗口的起始位置和长度。
    • 最终返回最小窗口对应的子串。

code Ⅰ

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

char* minWindow(char* s, char* t) {
    int m = strlen(s), n = strlen(t); // 获取 s 和 t 的长度
    char* ans = malloc(sizeof(char) * (m + 1)); // 分配结果数组
    if (m < n) return ""; // 如果 s 的长度小于 t，直接返回空字符串

    int hashs[130] = {0}; // 记录 s 中当前窗口的字符频率
    int hasht[130] = {0}; // 记录 t 中字符的频率

    // 统计 t 中字符的频率
    for (int i = 0; i < n; i++) {
        hasht[t[i]]++;
    }

    int l = 0, r = 0; // 滑动窗口的左右指针
    int indexl = 0, indexr = 0; // 最小窗口的左右索引
    int minlen = m + 1; // 最小窗口长度

    // 初始化窗口
    while (r < n) {
        hashs[s[r]]++; // 更新 s 中当前窗口的字符频率
        r++; // 右指针右移
    }

    // 滑动窗口
    while (r < m) {
        bool flag = true;
        // 检查当前窗口是否满足 t 中字符的频率要求
        for (int i = 0; i <= 128; i++) {
            if (hashs[i] < hasht[i]) {
                flag = false; // 如果不满足，设置 flag 为 false
                break;
            }
        }

        if (flag) {
            // 如果满足条件，更新最小窗口
            if (r - l < minlen) {
                minlen = r - l;
                indexl = l;
                indexr = r;
            }
            // 移动左指针，缩小窗口
            hashs[s[l]]--;
            l++;
        } else {
            // 如果不满足条件，移动右指针，扩展窗口
            hashs[s[r]]++;
            r++;
        }
    }

    // 最后检查一次窗口
    bool flag = true;
    while (flag) {
        for (int i = 0; i <= 128; i++) {
            if (hashs[i] < hasht[i]) {
                flag = false; // 如果不满足，设置 flag 为 false
                break;
            }
        }
        if (!flag) break; // 如果不满足条件，退出循环
        // 如果满足条件，更新最小窗口
        if (r - l < minlen) {
            minlen = r - l;
            indexl = l;
            indexr = m;
        }
        // 移动左指针，缩小窗口
        hashs[s[l]]--;
        l++;
    }

    // 如果最小窗口长度未更新，说明没有符合条件的子串
    if (minlen == m + 1) return "";

    // 将结果复制到 ans 中
    for (int i = indexl; i < indexr; i++) {
        ans[i - indexl] = s[i];
    }
    ans[minlen] = '\0'; // 添加字符串结束符

    return ans; // 返回结果
}

code Ⅱ

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

char* minWindow(char* s, char* t) {
    int m = strlen(s), n = strlen(t);
    if (m == 0 || n == 0 || m < n) return ""; // 如果 s 或 t 为空，或者 s 的长度小于 t，直接返回空字符串

    char* ans = malloc(sizeof(char) * (m + 1)); // 分配结果数组
    int hashs[128] = {0}; // 记录 s 中当前窗口的字符频率
    int hasht[128] = {0}; // 记录 t 中字符的频率

    // 统计 t 中字符的频率
    for (int i = 0; i < n; i++) {
        hasht[t[i]]++;
    }

    int l = 0, r = 0; // 滑动窗口的左右指针
    int minlen = m + 1; // 最小窗口长度
    int indexl = 0, indexr = 0; // 最小窗口的左右索引
    int count = 0; // 记录当前窗口中满足 t 中字符频率的字符数量

    while (r < m) {
        // 如果当前字符在 t 中出现过，则更新 hashs 和 count
        if (hasht[s[r]] > 0) {
            hashs[s[r]]++;
            if (hashs[s[r]] <= hasht[s[r]]) {
                count++;
            }
        }
        r++;

        // 如果当前窗口满足 t 中字符的频率要求
        while (count == n) {
            // 更新最小窗口
            if (r - l < minlen) {
                minlen = r - l;
                indexl = l;
                indexr = r;
            }

            // 移动左指针，缩小窗口
            if (hasht[s[l]] > 0) {
                hashs[s[l]]--;
                if (hashs[s[l]] < hasht[s[l]]) {
                    count--;
                }
            }
            l++;
        }
    }

    // 如果最小窗口长度未更新，说明没有符合条件的子串
    if (minlen == m + 1) return "";

    // 将结果复制到 ans 中
    strncpy(ans, s + indexl, minlen);
    ans[minlen] = '\0'; // 添加字符串结束符

    return ans; // 返回结果
}

13.最大子数组和

题目描述

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

思路：dp/贪心

  1. 定义状态：

    • 定义 dp[i] 表示以 nums[i] 结尾的最大子数组和。

  2. 状态转移方程：

    • 如果 dp[i-1] 是正数，则将其加入当前元素 nums[i]，形成更大的子数组和。

    • 如果 dp[i-1] 是负数，则以当前元素 nums[i] 作为新的子数组起点。

    • 状态转移方程为：

      dp[i] = max(nums[i], dp[i-1] + nums[i])

  3. 初始化：

    • dp[0] = nums[0]，因为以第一个元素结尾的最大子数组和就是它本身。

  4. 遍历数组：

    • 从第二个元素开始，依次计算 dp[i]，并更新全局最大值 ans。

  5. 返回结果：

    • 返回全局最大值 ans。

code

#include <stdio.h>
#include <stdlib.h>

int maxSubArray(int* nums, int numsSize) {
    if (nums == NULL || numsSize == 0) return 0; // 如果数组为空，直接返回 0

    int dp[numsSize]; // 定义 dp 数组，dp[i] 表示以 nums[i] 结尾的最大子数组和
    dp[0] = nums[0]; // 初始化 dp[0]
    int ans = dp[0]; // 初始化全局最大值

    for (int i = 1; i < numsSize; i++) {
        // 状态转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])
        dp[i] = fmax(nums[i], dp[i - 1] + nums[i]);
        // 更新全局最大值
        ans = fmax(ans, dp[i]);
    }

    return ans; // 返回全局最大值
}

14.合并区间

题目描述

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路：贪心

本题比较简单，直接拷贝之前的文章

代码随想录——贪心

  • 按区间的起始位置排序。
  • 遍历区间，如果当前区间与前一个区间重叠，则合并它们；否则，将前一个区间加入结果列表。

个人感觉比较简单~~

code

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

// 比较函数，用于按区间的起始位置从小到大排序
int cmp(const void* a, const void* b) {
    int* intervala = *(int**)a;
    int* intervalb = *(int**)b;
    // 按起始位置从小到大排序
    if (intervala[0] - intervalb[0] < 0) return -1;
    return 1;
}

int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
    // 按区间的起始位置排序
    qsort(intervals, intervalsSize, sizeof(int*), cmp);

    // 分配结果数组的内存
    int** res = malloc(sizeof(int*) * intervalsSize);
    // 初始化返回的区间数量为 0
    *returnSize = 0;

    // 初始化当前区间的起始和结束位置
    int start = intervals[0][0];
    int end = intervals[0][1];

    // 遍历所有区间
    for (int i = 1; i < intervalsSize; i++) {
        // 如果当前区间与前一个区间重叠
        if (intervals[i][0] <= end) {
            // 合并区间，更新结束位置
            end = fmax(end, intervals[i][1]);
        } else {
            // 如果不重叠，将前一个区间加入结果列表
            res[*returnSize] = malloc(sizeof(int) * 2);
            res[*returnSize][0] = start;
            res[*returnSize][1] = end;
            (*returnSize)++;
            // 更新当前区间的起始和结束位置
            start = intervals[i][0];
            end = intervals[i][1];
        }
    }

    // 将最后一个区间加入结果列表
    res[*returnSize] = malloc(sizeof(int) * 2);
    res[*returnSize][0] = start;
    res[*returnSize][1] = end;
    (*returnSize)++;

    // 分配列大小数组的内存
    *returnColumnSizes = malloc(sizeof(int) * (*returnSize));
    // 设置每个区间的列大小为 2
    for (int i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = 2;
    }

    // 返回结果数组
    return res;
}

15.轮转数组

题目描述

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

思路：反转法

  1. 反转整个数组。
  2. 反转前 k 个元素。
  3. 反转剩余 n - k 个元素。

证明：

  1. 初始数组：

    • 数组 nums 可以表示为：
      n u m s = [ a 0 , a 1 , . . . , a n − k − 1 , a n − k , a n − k + 1 , . . . , a n − 1 ] nums = [a_{0}, a_{1}, ..., a_{n-k-1}, a_{n-k}, a_{n-k+1}, ..., a_{n-1}] nums=[a0​,a1​,...,an−k−1​,an−k​,an−k+1​,...,an−1​]

  2. 第一次反转（反转整个数组）：

    • 反转后，数组变为：
      n u m s = [ a n − 1 , . . . , a n − k + 1 , a n − k , a n − k − 1 , . . . , a 0 ] nums = [a_{n-1}, ..., a_{n-k+1}, a_{n-k}, a_{n-k-1}, ..., a_{0}] nums=[an−1​,...,an−k+1​,an−k​,an−k−1​,...,a0​]

  3. 第二次反转（反转前 k 个元素）：

    • 反转前 k 个元素后，数组变为：
      n u m s = [ a n − k , . . . , a n − 1 , a n − k − 1 , . . . , a 0 ] nums = [a_{n-k}, ..., a_{n-1}, a_{n-k-1}, ..., a_{0}] nums=[an−k​,...,an−1​,an−k−1​,...,a0​]

  4. 第三次反转（反转剩下的 n - k 个元素）：

    • 反转剩下的 n - k 个元素后，数组变为：
      n u m s = [ a n − k , . . . , a n − 1 , a 0 , . . . , a n − k − 1 ] nums = [a_{n-k}, ..., a_{n-1}, a_{0}, ..., a_{n-k-1}] nums=[an−k​,...,an−1​,a0​,...,an−k−1​]

网上有很多种证明，我觉得这样是最直观的

code

#include <stdio.h>

// 反转数组的辅助函数
void reverse(int* nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

void rotate(int* nums, int numsSize, int k) {
    k = k % numsSize; // 处理 k 大于数组长度的情况
    if (k == 0) return; // 如果 k 为 0，直接返回

    // 反转整个数组
    reverse(nums, 0, numsSize - 1);
    // 反转前 k 个元素
    reverse(nums, 0, k - 1);
    // 反转剩下的 n - k 个元素
    reverse(nums, k, numsSize - 1);
}

16.除自身以外数组的乘积

题目描述

238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

思路：前缀积+后缀积

  1. 前缀积：
    • 从左到右遍历数组，计算每个位置左侧所有元素的乘积。
  2. 后缀积：
    • 从右到左遍历数组，计算每个位置右侧所有元素的乘积。
  3. 结果计算：
    • 对于每个位置 i，结果 ans[i] 等于前缀积 left[i] 乘以后缀积 right[i]。

code

#include <stdio.h>
#include <stdlib.h>

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    // 分配结果数组的内存
    int* ans = malloc(sizeof(int) * numsSize);
    *returnSize = numsSize; // 设置返回数组的大小

    // 定义前缀积数组 left 和后缀积数组 right
    int left[numsSize];  // 存储每个位置左侧所有元素的乘积
    int right[numsSize]; // 存储每个位置右侧所有元素的乘积

    // 计算前缀积
    left[0] = 1; // 第一个元素左侧没有元素，前缀积为 1
    for (int i = 1; i < numsSize; i++) {
        left[i] = left[i - 1] * nums[i - 1]; // 前缀积 = 前一个前缀积 * 前一个元素
    }

    // 计算后缀积
    right[numsSize - 1] = 1; // 最后一个元素右侧没有元素，后缀积为 1
    for (int i = numsSize - 2; i >= 0; i--) {
        right[i] = right[i + 1] * nums[i + 1]; // 后缀积 = 后一个后缀积 * 后一个元素
    }

    // 计算结果数组
    for (int i = 0; i < numsSize; i++) {
        ans[i] = left[i] * right[i]; // 结果 = 前缀积 * 后缀积
    }

    return ans; // 返回结果数组
}

17.缺失的第一个正数

题目描述

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

思路：哈希

本题如果抛弃时间和空间的限制是蛮简单的。

有两种思路：

1.开辟额外空间建立哈希表，记录1~numSize的数是否出现。空间复杂度O(N)

2.先对原数组排序，再寻找没有出现的最小正整整。时间复杂度O(NlogN)。

虽然上面两种方法都可以解决，但是不能满足题目的要求。这里的思路是：原地哈希。

具体步骤：

  1. 原地哈希：
    • 将数组中的每个正整数放到它应该在的位置
    • 如果当前数在 1 到 numsSize之间，并且它不在正确的位置上，将它交换到正确的位置。
  2. 查找缺失的正整数：
    • 最后遍历数组，找到第一个正数的位置 i，i + 1 就是缺失的最小正整数。
    • 如果所有位置都是负数，则缺失的最小正整数是 n + 1。

code

#include <stdio.h>

// 交换两个整数的值
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int firstMissingPositive(int* nums, int numsSize) {
    // 第一步：将数组中的每个正整数放到它应该在的位置
    for (int i = 0; i < numsSize; i++) {
        // 如果当前数在 1 到 numsSize 之间，并且它不在正确的位置上
        while (nums[i] > 0 && nums[i] <= numsSize && nums[nums[i] - 1] != nums[i]) {
            // 将它交换到正确的位置
            swap(&nums[i], &nums[nums[i] - 1]);
        }
    }

    // 第二步：遍历数组，找到第一个不满足 nums[i] == i + 1 的位置
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }

    // 如果所有位置都满足条件，返回 numsSize + 1
    return numsSize + 1;
}

18.矩阵置零

题目描述

73. 矩阵置零

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法**。**

示例 1：

img

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

img

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

思路：哈希

1.问题分析：

  • 我们需要将矩阵中所有 0 所在的行和列都置为 0。
  • 直接修改矩阵会导致后续的 0 被误判，因此需要先记录哪些行和列需要置零。

2.核心思想：

  • 使用两个辅助数组 row 和 col，分别记录哪些行和列需要置零。
  • 遍历矩阵，如果发现 matrix[i][j] == 0，则标记 row[i] 和 col[j] 为 true。
  • 再次遍历矩阵，根据 row 和 col 的标记，将对应的行和列置零。

3.优化：

  • 可以使用矩阵的第一行和第一列来替代辅助数组，从而将空间复杂度优化为 O(1)。

code

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    // 定义两个辅助数组，用于记录哪些行和列需要置零
    bool col[200]; // 记录列是否需要置零
    bool row[200]; // 记录行是否需要置零
    memset(col, false, sizeof(col)); // 初始化 col 数组为 false
    memset(row, false, sizeof(row)); // 初始化 row 数组为 false

    // 遍历矩阵，标记需要置零的行和列
    for (int i = 0; i < matrixSize; i++) {
        for (int j = 0; j < matrixColSize[i]; j++) {
            if (matrix[i][j] == 0) { // 如果当前元素为 0
                if (!col[j]) col[j] = true; // 标记列 j 需要置零
                if (!row[i]) row[i] = true; // 标记行 i 需要置零
            }
        }
    }

    // 遍历矩阵，将标记的行置零
    for (int i = 0; i < matrixSize; i++) {
        if (row[i]) { // 如果行 i 需要置零
            for (int j = 0; j < matrixColSize[i]; j++) {
                matrix[i][j] = 0; // 将行 i 的所有元素置零
            }
        }
    }

    // 遍历矩阵，将标记的列置零
    for (int j = 0; j < matrixColSize[0]; j++) {
        if (col[j]) { // 如果列 j 需要置零
            for (int i = 0; i < matrixSize; i++) {
                matrix[i][j] = 0; // 将列 j 的所有元素置零
            }
        }
    }
}

code(优化)

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    bool firstRowHasZero = false; // 记录第一行是否需要置零
    bool firstColHasZero = false; // 记录第一列是否需要置零

    // 检查第一行是否有 0
    for (int j = 0; j < matrixColSize[0]; j++) {
        if (matrix[0][j] == 0) {
            firstRowHasZero = true;
            break;
        }
    }

    // 检查第一列是否有 0
    for (int i = 0; i < matrixSize; i++) {
        if (matrix[i][0] == 0) {
            firstColHasZero = true;
            break;
        }
    }

    // 遍历矩阵，标记需要置零的行和列
    for (int i = 1; i < matrixSize; i++) {
        for (int j = 1; j < matrixColSize[i]; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0; // 标记第 i 行需要置零
                matrix[0][j] = 0; // 标记第 j 列需要置零
            }
        }
    }

    // 根据标记置零
    for (int i = 1; i < matrixSize; i++) {
        for (int j = 1; j < matrixColSize[i]; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }

    // 处理第一行
    if (firstRowHasZero) {
        for (int j = 0; j < matrixColSize[0]; j++) {
            matrix[0][j] = 0;
        }
    }

    // 处理第一列
    if (firstColHasZero) {
        for (int i = 0; i < matrixSize; i++) {
            matrix[i][0] = 0;
        }
    }
}

19.螺旋矩阵

题目描述

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

img

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

img

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

思路：模拟/螺旋矩阵

  1. 边界初始化：

    • top 和 bottom 分别表示当前遍历的上下边界。
    • left 和 right 分别表示当前遍历的左右边界。

  2. 螺旋遍历核心逻辑：

    • 从左到右遍历上边界：将上边界的元素加入结果数组，然后上边界下移。
    • 从上到下遍历右边界：将右边界的元素加入结果数组，然后右边界左移。
    • 从右到左遍历下边界：将下边界的元素加入结果数组，然后下边界上移。
    • 从下到上遍历左边界：将左边界的元素加入结果数组，然后左边界右移。

    注：每次遍历完一个边界后修改边界值

  3. 终止条件：

    • 当上边界超过下边界或左边界超过右边界时，遍历结束。

  4. 边界条件处理：

    • 如果矩阵为空，直接返回 NULL 并设置 returnSize 为 0。

code

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    if (matrixSize == 0 || matrixColSize[0] == 0) {
        *returnSize = 0;
        return NULL;
    }

    int m = matrixSize;          // 矩阵的行数
    int n = matrixColSize[0];    // 矩阵的列数
    int* ans = malloc(sizeof(int) * m * n); // 结果数组
    *returnSize = 0;             // 初始化返回数组的大小

    int top = 0, bottom = m - 1; // 定义上下边界
    int left = 0, right = n - 1; // 定义左右边界

    while (top <= bottom && left <= right) {
        // 从左到右遍历上边界
        for (int j = left; j <= right; j++) {
            ans[(*returnSize)++] = matrix[top][j];
        }
        top++; // 上边界下移

        // 从上到下遍历右边界
        for (int i = top; i <= bottom; i++) {
            ans[(*returnSize)++] = matrix[i][right];
        }
        right--; // 右边界左移

        // 如果上边界超过下边界，说明已经遍历完
        if (top > bottom) break;

        // 从右到左遍历下边界
        for (int j = right; j >= left; j--) {
            ans[(*returnSize)++] = matrix[bottom][j];
        }
        bottom--; // 下边界上移

        // 如果左边界超过右边界，说明已经遍历完
        if (left > right) break;

        // 从下到上遍历左边界
        for (int i = bottom; i >= top; i--) {
            ans[(*returnSize)++] = matrix[i][left];
        }
        left++; // 左边界右移
    }

    return ans;
}

20.旋转图像

题目描述

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

img

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

img

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

思路一：水平翻转+转置

证明略。。。(后面再补)

code

//主对角线翻转+水平翻转
void swap(int *a,int *b){
    int temp=*a;
    *a=*b;
    *b=temp;
}
void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    //水平翻转
    for(int i=0;i<matrixSize/2;i++){
        for(int j=0;j<matrixSize;j++){
            swap(&matrix[i][j],&matrix[matrixSize-1-i][j]);
        }
    }
    //主对角线翻转
    for(int i=0;i<matrixSize;i++){
        for(int j=i+1;j<matrixSize;j++){
            swap(&matrix[i][j],&matrix[j][i]);
        }
    }
    
}

http://www.niftyadmin.cn/n/5867007.html

相关文章

SpringSecurity处理器：登录成功处理器、登录失败处理器、无权限处理器、注销成功处理器

SpringSecurity处理器：登录成功处理器、登录失败处理器、无权限处理器、注销成功处理器

在 Spring Security 中，你可以通过实现特定的接口或扩展某些类来自定义各种处理器，例如登录成功处理器、登录失败处理器、无权限处理器和登出成功处理器。 以下是每种处理器的具体实现方法： 【示例】首先创建统一的响应结果类和响应结果编码枚举，方便后续示例中使用。 （…
阅读更多...
2025-skywalking组件

2025-skywalking组件

历史版本下载地址&#xff1a;Apache Archive Distribution Directory 官网&#xff1a;Apache SkyWalking 目录 . webapp: UI前端(web 监控页面)的jar包和配置文件; . oap-libs:后台应用的jar包&#xff0c;以及它的依赖jar包&#xff0c;里边有一个server-starter-*.jar就是…
阅读更多...
API返回的数据结构包含哪些字段？

API返回的数据结构包含哪些字段？

淘宝商品详情API返回的数据结构较为复杂&#xff0c;具体字段会根据API的版本和请求参数有所不同。以下是基于最新搜索结果的API返回值字段说明&#xff1a; 基础字段 num_iid&#xff1a;商品的唯一标识ID。 title&#xff1a;商品标题&#xff0c;用于描述商品名称或特点。…
阅读更多...
C++：pthread线程分离和线程属性

C++：pthread线程分离和线程属性

在 C 的多线程编程中&#xff0c;pthread 库提供了强大的功能来管理线程。其中&#xff0c;线程分离和线程属性是两个重要的概念&#xff0c;它们对于优化线程的行为和资源管理有着关键作用。 线程分离 1.1 什么是线程分离 在 pthread 库中&#xff0c;线程有两种状态&#…
阅读更多...
从零开始的网站搭建（以照片/文本/视频信息通信网站为例）

从零开始的网站搭建（以照片/文本/视频信息通信网站为例）

本文面向已经有一些编程基础&#xff08;会至少一门编程语言&#xff0c;比如python&#xff09;&#xff0c;但是没有搭建过web应用的人群&#xff0c;会写得尽量细致。重点介绍流程和部署云端的步骤&#xff0c;具体javascript代码怎么写之类的&#xff0c;这里不会涉及。 搭…
阅读更多...
【Qt之QQuickWidget】QML嵌入QWidget中

【Qt之QQuickWidget】QML嵌入QWidget中

由于我项目开始使用Widgets,换公司后直接使用QML开发&#xff0c;没有了解过如何实现widget到qml过渡&#xff0c;恰逢面试时遇到一家公司希望从widget迁移到qml开发&#xff0c;询问相关实现&#xff0c;一时语塞&#xff0c;很尴尬&#xff0c;粗略研究并总结下。 对qwidget嵌…
阅读更多...
Html 5简介(学习笔记)

Html 5简介(学习笔记)

基本标签 1. 换行标签 <br> <br>2. 链接标签 <a> <a href"https://www.example.com" target"_blank">网站</a>href&#xff1a;指定链接地址。 target&#xff1a; _blank&#xff1a;在新标签页打开。_self&#xff08…
阅读更多...
取消票证会把指定的票证从数据库中删除，同时也会把票证和航班 等相关表中的关联关系一起删除。但在删除之前，它会先检查当前用户是否拥有这张票

取消票证会把指定的票证从数据库中删除，同时也会把票证和航班 等相关表中的关联关系一起删除。但在删除之前，它会先检查当前用户是否拥有这张票

在做航班智能客服问答系统时会遇到取消票证的场景&#xff0c;这里涉及数据库的操作时会把指定的票证从数据库中删除&#xff0c;同时也会把票证和航班等相关表中的关联关系一起删除。但在删除之前&#xff0c;需要先检查当前用户是否拥有这张票&#xff0c;只有票主才有权限取…
阅读更多...
最新文章

Copyright @ 2022~2023