技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

CC蓝桥杯算法真题打卡Day1

 收录于 蓝桥杯
   约 1985 字   预计阅读 4 分钟 
https://bing.ee123.net/img/rand?artid=146026979

C/C++蓝桥杯算法真题打卡（Day1）

一、

https://i-blog.csdnimg.cn/direct/c0c65f25b7344d5b9e4fb510a8ee9027.png

算法代码：

class Solution {
public:
    bool isPalindrome(string s) {
        int n = s.size();
        // 处理一下s为空字符的情况
        if (n == 0) {
            return true; // 修正拼写错误
        }

        // 定义左右指针遍历字符串
        int left = 0;
        int right = n - 1; // 修正右指针初始化
        while (left < right) {
            // 左右对非字母数字字符的处理是直接跳过
            while (left < right && !isalnum(s[left])) {
                left++;
            }
            while (left < right && !isalnum(s[right])) {
                right--;
            }

            // 处理大小写的情况，统一转换为小写
            if (s[left] >= 'A' && s[left] <= 'Z') {
                s[left] += 32;
            }
            if (s[right] >= 'A' && s[right] <= 'Z') {
                s[right] += 32;
            }

            // 然后判断是不是相同的字符，若是则直接跳过
            if (s[left] == s[right]) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }
};

代码思路

  1. 处理空字符串 ：

    • 如果字符串 s 为空（ n == 0 ），直接返回 true ，因为题目定义空字符串为有效回文串。

  2. 初始化左右指针 ：

    • 定义左指针 left ，初始化为 0 ，指向字符串的开头。
    • 定义右指针 right ，初始化为 n - 1 ，指向字符串的末尾。

  3. 主循环：左右指针向中间移动 ：

    • 使用 while (left < right) 循环，确保左右指针没有相遇或交叉。
    • 在循环中，分别处理左指针和右指针指向的字符。

  4. 跳过非字母数字字符 ：

    • 使用 isalnum 函数检查当前字符是否为字母或数字。
    • 如果不是字母或数字，则移动指针（左指针向右移动，右指针向左移动），直到找到字母或数字字符。

  5. 统一字符大小写 ：

    • 如果字符是大写字母（ A-Z ），将其转换为小写字母（ a-z ），以便在比较时忽略大小写。

  6. 比较字符 ：

    • 如果左右指针指向的字符相等，则继续向中间移动指针（ left++ 和 right-- ）。
    • 如果字符不相等，则直接返回 false ，说明字符串不是回文串。

  7. 循环结束 ：

    • 如果循环正常结束（即左右指针相遇或交叉），说明所有字符都匹配，返回 true ，表示字符串是回文串。

代码优化建议

  1. 避免修改原始字符串 ：

    • 你的代码中直接修改了字符串 s 中的字符（如 s[left] += 32 ）。虽然这不会影响结果，但为了代码的健壮性，建议避免修改输入数据。
    • 可以使用 tolower 函数直接在比较时转换字符大小写，而不修改原始字符串。

  2. 使用 tolower 函数 ：

    • tolower 是 C++ 标准库函数，可以直接将字符转换为小写，避免手动计算 ASCII 值。

优化后的代码如下：

class Solution {
public:
    bool isPalindrome(string s) {
        int n = s.size();
        // 处理空字符串
        if (n == 0) {
            return true;
        }

        int left = 0;
        int right = n - 1;
        while (left < right) {
            // 跳过非字母数字字符
            while (left < right && !isalnum(s[left])) {
                left++;
            }
            while (left < right && !isalnum(s[right])) {
                right--;
            }

            // 统一转换为小写并比较
            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }

            // 移动指针
            left++;
            right--;
        }
        return true;
    }
};

代码思路总结

步骤操作说明
1处理空字符串如果字符串为空，直接返回 true 。
2初始化左右指针left 指向开头， right 指向末尾。
3主循环当 left < right 时，继续循环。
4跳过非字母数字字符使用 isalnum 检查并跳过非字母数字字符。
5统一字符大小写使用 tolower 将字符转换为小写。
6比较字符如果字符不相等，返回 false ；否则移动指针。
7循环结束如果所有字符都匹配，返回 true 。

时间复杂度分析

  • 时间复杂度 ： O(n) ，其中 n 是字符串的长度。每个字符最多被访问一次。
  • 空间复杂度 ： O(1) ，只使用了常数级别的额外空间。

二、

https://i-blog.csdnimg.cn/direct/a88d7c979014422c935dcb84eeb1e000.png

算法代码：

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        // 初始化 DP 表
        vector<vector<int>> dp(numRows);

        // 生成每一行
        for (int i = 0; i < numRows; i++) {
            // 调整当前行的大小为 i+1
            dp[i].resize(i + 1);

            // 设置边界值：第一个和最后一个元素为 1
            dp[i][0] = dp[i][i] = 1;

            // 计算中间元素
            for (int j = 1; j < i; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }

        // 返回生成的杨辉三角
        return dp;
    }
};

代码思路

  1. 初始化 DP 表 ：

    • 创建一个二维向量 dp ，用于存储杨辉三角的每一行。
    • dp 的大小为 numRows ，表示杨辉三角的行数。

  2. 生成每一行 ：

    • 使用一个外层循环遍历每一行（从 0 到 numRows - 1 ）。
    • 对于每一行 i ，调整其大小为 i + 1 （因为第 i 行有 i + 1 个元素）。

  3. 设置边界值 ：

    • 每一行的第一个元素和最后一个元素总是 1 ，即：

      dp[i][0] = dp[i][i] = 1;

  4. 计算中间元素 ：

    • 使用一个内层循环计算每一行的中间元素（从第 2 个元素到倒数第 2 个元素）。

    • 每个中间元素等于它左上方和右上方元素的和，即：

      dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

  5. 返回结果 ：

    • 最终返回 dp 表，即生成的杨辉三角。

代码执行流程

  1. 初始化 ：

    • dp 表被创建，大小为 numRows ，每一行是一个空的 vector<int> 。

  2. 生成每一行 ：

    • 对于第 i 行：

      • 调整大小为 i + 1 。
      • 设置第一个和最后一个元素为 1 。
      • 计算中间元素（如果存在）。

  3. 返回结果 ：

    • 返回完整的 dp 表。

示例

假设 numRows = 5 ，代码的执行过程如下：

  1. 第 0 行 ：

    • 调整大小为 1 。
    • 设置 dp[0][0] = 1 。
    • 行内容： [1] 。

  2. 第 1 行 ：

    • 调整大小为 2 。
    • 设置 dp[1][0] = 1 和 dp[1][1] = 1 。
    • 行内容： [1, 1] 。

  3. 第 2 行 ：

    • 调整大小为 3 。
    • 设置 dp[2][0] = 1 和 dp[2][2] = 1 。
    • 计算中间元素： dp[2][1] = dp[1][0] + dp[1][1] = 1 + 1 = 2 。
    • 行内容： [1, 2, 1] 。

  4. 第 3 行 ：

    • 调整大小为 4 。

    • 设置 dp[3][0] = 1 和 dp[3][3] = 1 。

    • 计算中间元素：

      • dp[3][1] = dp[2][0] + dp[2][1] = 1 + 2 = 3 。
      • dp[3][2] = dp[2][1] + dp[2][2] = 2 + 1 = 3 。

    • 行内容： [1, 3, 3, 1] 。

  5. 第 4 行 ：

    • 调整大小为 5 。

    • 设置 dp[4][0] = 1 和 dp[4][4] = 1 。

    • 计算中间元素：

      • dp[4][1] = dp[3][0] + dp[3][1] = 1 + 3 = 4 。
      • dp[4][2] = dp[3][1] + dp[3][2] = 3 + 3 = 6 。
      • dp[4][3] = dp[3][2] + dp[3][3] = 3 + 1 = 4 。

    • 行内容： [1, 4, 6, 4, 1] 。

最终结果

[
    [1],
    [1, 1],
    [1, 2, 1],
    [1, 3, 3, 1],
    [1, 4, 6, 4, 1]
]

复杂度分析

  1. 时间复杂度 ：

    • 生成每一行需要 O(i) 的时间，其中 i 是行号。

    • 总时间复杂度为：

      https://i-blog.csdnimg.cn/direct/dcda5a4473204558bf44ae0b3bf39d84.png

    • 其中 n=numRows。

  2. 空间复杂度 ：

    • 需要存储整个杨辉三角，空间复杂度为 O(n2)。

总结

  • 代码通过动态规划（DP）表的方式生成杨辉三角，思路清晰且高效。
  • 使用 resize 为每一行分配空间，并通过状态转移方程计算中间元素。
  • 代码的时间复杂度和空间复杂度均为 O(n2)，是生成杨辉三角的经典实现。
更新于 2025-03-07
 蓝桥杯, 算法, 数据结构, 动态规划, C
返回 | 主页