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)。