一、LCR 018. 验证回文串 - 力扣（LeetCode）

算法代码： 

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)，只使用了常数级别的额外空间。

二、118. 杨辉三角 - 力扣（LeetCode） 

算法代码： 

class Solution {
public:vector<vector<int>> generate(int numRows) {// 初始化 DP 表vector<vector<int>> dp(numRows);// 生成每一行for (int i = 0; i < numRows; i++) {// 调整当前行的大小为 i+1dp[i].resize(i + 1);// 设置边界值：第一个和最后一个元素为 1dp[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 是行号。

   • 总时间复杂度为：

     

   • 其中 n=numRows。

2. 空间复杂度：

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

---

总结

• 代码通过动态规划（DP）表的方式生成杨辉三角，思路清晰且高效。

• 使用 resize 为每一行分配空间，并通过状态转移方程计算中间元素。

• 代码的时间复杂度和空间复杂度均为 O(n2)，是生成杨辉三角的经典实现。