抱佛脚一时爽，一直抱佛脚一直爽！这篇文章总结常见的链表问题~
参考链接：leetcode 剑指offer
题目们
把int当作字符串反转（lc7）
int reverseInt(int x) {
int y = 0;
while (x) {
if (abs(y) > INT_MAX / 10) return 0;
y = y * 10 + x % 10;
x /= 10;
}
return y;
}
正则表达式匹配（jz52）
bool isMatch(string s, string p) {
if (p.empty()) return s.empty();
if (p.size() > 1 && p[1] == '*') {
return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p));
} else {
return !s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
}
}
- 法二：动态规划；f[i][j]表示s的前i个和p的前j个能否匹配
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (j > 1 && p[j - 1] == '*') {
dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
} else {
dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
}
}
}
return dp[m][n];
}
无重复字符的最大子串（lc3）
int lengthOfLongestSubstring(string s) {
int n = s.size();
unordered_set<int> mySet;
int j = 0, res = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) mySet.erase(s[i - 1]);
for (; j < n; ++j) {
if (mySet.count(s[j])) {
break;
} else {
mySet.insert(s[j]);
res = max(res, j - i + 1);
}
}
}
return res;
}
最大回文子串（lc5）
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() < 2) return s;
int n = s.size(), maxLen = 0, start = 0;
for (int i = 0; i < n - 1; ++i) {
searchPalindrome(s, i, i, start, maxLen); // 回文子串长度为奇数时
searchPalindrome(s, i, i + 1, start, maxLen); // 回文子串长度为偶数时
}
return s.substr(start, maxLen);
}
void searchPalindrome(string s, int left, int right, int& start, int& maxLen) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
--left; ++right;
}
if (maxLen < right - left - 1) {
start = left + 1;
maxLen = right - left - 1;
}
}
};
回文子串个数（lc647）
class Solution {
public:
int countSubstrings(string s) {
int n = s.size(), res = 0;
for (int i = 0; i < n; ++i) {
res += count(s, i, i);
if (i < n - 1 && s[i] == s[i + 1]) res += count(s, i, i + 1);
}
return res;
}
int count(string s, int left, int right) {
int cnt = 0;
while (left >= 0 && right < s.size() && s[left] == s[right]) {
++cnt;
--left;
++right;
}
return cnt;
}
};
int countSubstrings(string s) {
int n = s.size(), res = 0;
vector<vector<bool>> dp(n, vector<bool>(n));
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]);
if (dp[i][j]) ++res;
}
}
return res;
}
最长有效括号（lc32）
int longestValidParentheses(string s) {
int left = 0, right = 0, n = s.size(), res = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '(') ++left;
else ++right;
if (right == left) res = max(res, 2 * left);
else if (right > left) {
left = 0;
right = 0;
}
}
left = 0, right = 0;
for (int i = n - 1; i >= 0; --i) {
if (s[i] == '(') ++left;
else ++right;
if (right == left) res = max(res, 2 * left);
else if (left > right) {
left = 0;
right = 0;
}
}
return res;
}
int longestValidParentheses(string s) {
int res = 0, start = 0, n = s.size();
stack<int> st;
for (int i = 0; i < n; ++i) {
if (s[i] == '(') st.push(i);
else if (s[i] == ')') {
if (st.empty()) start = i + 1;
else {
st.pop();
res = st.empty() ? max(res, i - start + 1) : max(res, i - st.top());
}
}
}
return res;
}
int longestValidParentheses(string s) {
int res = 0, n = s.size();
vector<int> dp(n + 1);
for (int i = 1; i <= n; ++i) {
int j = i - 2 - dp[i - 1];
if (s[i - 1] == '(' || j < 0 || s[j] == ')') {
dp[i] = 0;
} else {
dp[i] = dp[i - 1] + 2 + dp[j];
res = max(res, dp[i]);
}
}
return res;
}
最长公共前缀（lc14）
string longestCommonPrefix(vector<string>& strs) {
int n = strs.size();
if (!n) return "";
string result = "";
for (int i = 0; i < strs[0].size(); ++i) { // 第i位的字符
char c = strs[0][i];
for (int j = 1; j < strs.size(); ++j) {
if (strs[j].size() <= i || strs[j][i] != c) return result;
}
result += c;
}
return result;
}
简化路径（lc71）
- 思路：把路径看做是由一个或多个"/"分割开的众多子字符串，把它们分别提取出来一一处理即可
- 注意：用vector而不是stack！
string simplifyPath(string path) {
vector<string> v;
int i = 0;
while (i < path.size()) {
while (path[i] == '/' && i < path.size()) ++i;
if (i == path.size()) break;
int start = i;
while (path[i] != '/' && i < path.size()) ++i;
int end = i - 1;
string s = path.substr(start, end - start + 1);
if (s == "..") { // 处理/..的情况
if (!v.empty()) v.pop_back();
} else if (s != ".") {
v.push_back(s);
}
}
if (v.empty()) return "/";
string res;
for (int i = 0; i < v.size(); ++i) {
res += '/' + v[i];
}
return res;
}
字符串表示的两数相加（lc415）
string addStrings(string num1, string num2) {
int p1 = num1.size() - 1, p2 = num2.size() - 1;
int incre = 0;
string res = "";
while (p1 >= 0 || p2 >= 0) {
int val1 = p1 >= 0 ? num1[p1] - '0' : 0;
if (p1 >= 0) --p1;
int val2 = p2 >= 0 ? num2[p2] - '0' : 0;
if (p2 >= 0) --p2;
int sum = val1 + val2 + incre;
res.insert(res.begin(), sum % 10 + '0');
incre = sum / 10;
}
if (incre) res.insert(res.begin(), incre + '0');
return res;
}
替换空格（jz2）
- 思路：不要忘记最后的'\0'，所以char* pre = str + length而不是char* pre = str + length - 1
Z字形变换（lc6）
string convert(string s, int numRows) {
if (numRows <= 1) return s;
string res;
int size = 2 * numRows - 2, n = s.size();
for (int i = 0; i < numRows; ++i) {
for (int j = i; j < n; j += size) {
res += s[j];
int pos = j + size - 2 * i;
if (i != 0 && i != numRows - 1 && pos < n) res += s[pos];
}
}
return res;
}
