备战蓝桥第一天 验证回文串 杨辉三角
LCR 018. 验证回文串 - 力扣（LeetCode）
涉及的函数：
int isalnum ( int c );
检查字符是否为字母数字
int tolower ( int c );
将大写字母转换为小写
void reverse (BidirectionalIterator first, BidirectionalIterator last);
反转区域中元素的顺序 [first,last).
方法一：筛选 + 判断
对字符串s进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串t中
这样我们只需要判断t是否是一个普通的回文串即可
判断的方法有两种。第一种是使用reverse翻转得到t的逆序字符串
如果这两个字符串相同，那么t就是回文串
代码1：
class Solution {
public:
bool isPalindrome(string s) {
string t;
for(auto ch : s)
{
if (isalnum(ch))
t += tolower(ch);
}
string t1(t);
reverse(t1.begin(), t1.end());
return t1 == t;
}
};
//时间复杂度：O(|n|)
//空间复杂度：O(|n|)
第二种是使用双指针
初始时，左右指针分别指向t的两侧，随后我们不断地将这两个指针相向移动
每次移动一步，并判断这两个指针指向的字符是否相同
当这两个指针相遇时，就说明是回文串
代码2：
class Solution {
public:
bool isPalindrome(string s) {
string t;
for (char ch: s) {
if (isalnum(ch)) {
t += tolower(ch);
}
}
int l = 0, r = t.size() - 1;
while (l < r) {
if (t[l] != t[r]) {
return false;
}
++l;
--r;
}
return true;
}
};
//时间复杂度：O(|n|)
//空间复杂度：O(|n|)方法二：在原字符串上直接判断
直接在原字符串s上使用双指针。在移动任意一个指针时，需要不断地向另一指针的方向移动
直到遇到一个字母或数字字符，或者两指针重合为止，再判断这两个指针指向的字符是否相同
代码3：
class Solution {
public:
bool isPalindrome(string s) {
int l = 0, r = s.size() - 1;
while (l < r) {
//注意要再次判断l<r，防止死循环
//遇不到字母或数字就一直向后走
while (l < r && !isalnum(s[l])) {
++l;
}
//遇不到字母或数字就一直向前走
while (l < r && !isalnum(s[r])) {
--r;
}
if (l < r) {
if (tolower(s[l]) != tolower(s[r])) {
return false;
}
++l;
--r;
}
}
return true;
}
};
//时间复杂度：O(|n|)
//空间复杂度：O(|1|) 118. 杨辉三角 - 力扣（LeetCode）
代码1：
//void resize (size_type n, value_type val = value_type());
//调整容器大小
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv(numRows);
for (int i = 0; i < numRows; ++i) {
vv[i].resize(i + 1);
vv[i][0] = vv[i][i] = 1;
for (int j = 1; j < i; ++j) {
//下标等于上面加左上
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
return vv;
}
};
时间复杂度：O(numRowsD平方)。
空间复杂度：O(1)。原文地址：https://blog.csdn.net/weixin_73266891/article/details/144404970
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！