1. 两数之和
哈希表：O(n)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hs;
int n = nums.size();
for(int i = 0; i < n; i++) {
int x = target - nums[i];
if(hs.count(x)) {
return {hs[x], i};
}
hs[nums[i]] = i;
}
return {};
}
};
2. 两数相加
为了方便定义一个虚拟头节点dummy，这样就不用特判第一个节点了
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
auto dummy = new ListNode(-1), cur = dummy;
int t = 0;
while(l1 || l2 || t) {
if(l1) t += l1->val, l1 = l1->next;
if(l2) t += l2->val, l2 = l2->next;
cur->next = new ListNode(t % 10);
t /= 10;
cur = cur->next;
}
return dummy->next;
}
};
3. 无重复字符的最长子串
双指针算法
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
int res = 0;
unordered_map<int, int> hs;
for(int i = 0, j = 0; i < n; i++) {
int x = s[i] - 'a';
hs[x] ++;
while(hs[x] > 1) {
hs[s[j] - 'a']--;
j++;
}
res = max(res, i - j + 1);
}
return res;
}
};
4. 寻找两个正序数组的中位数
这道题"困难"标签是对特定做法来说的，像我这种菜鸡只能想到暴力合并然后排序 O((m+n)log(m+n))
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
vector<int> nums(n + m);
for(int i = 0; i < n; i++){
nums[i] = nums1[i];
}
for(int i = 0;i < m;i++){
nums[i + n] = nums2[i];
}
sort(nums.begin(), nums.end());
int x = n + m;
double res = 0.0;
if(x % 2 == 0) {
res = (nums[x / 2] + nums[x / 2 - 1]) * 1.0 / 2;
}else {
res = 1.0 * nums[x / 2];
}
return res;
}
};
5. 最长回文子串
方法一：马拉车算法
O(n), 很长时间不写了...
方法二：字符串哈希+二分：
O(nlog(n))
首先在每两个字符之间加上一个#，保证字符串的长度为奇数，方便后面的判断
枚举中心点，二分求左右两边的长度r（回文子串的半径），如果左边字符串逆序的哈希值和右边的哈希值一样，那么这个回文子串的长度为2 * r + 1，注意这个是包含#号的
typedef unsigned long long ull;
const int P = 131, N = 2010;
class Solution {
public:
ull hl[N], hr[N], p[N];
ull get(ull h[], int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
string longestPalindrome(string str) {
int n = str.size();
if(n == 1) {
return str;
}
string s = "";
for(int i = 0; i < n; i++) {
s += '#';
s += str[i];
}
n = 2 * n - 1;
memset(hl, 0, sizeof(hl));
memset(hr, 0, sizeof(hr));
memset(p, 0, sizeof(p));
p[0] = 1;
for(int i = 1, j = n; i <= n; i++, j--) {
hl[i] = hl[i - 1] * P + s[i] - 'a' + 1;
hr[i] = hr[i - 1] * P + s[j] - 'a' + 1;
p[i] = p[i - 1] * P;
}
string res = "";
int len = 0;
for(int i = 1; i <= n; i++) {
int l = 0, r = min(i - 1, n - i);
while(l < r) {
int mid = (l + r + 1) >> 1;
if(get(hl, i - mid, i - 1) != get(hr, n - i - mid + 1, n - i)) {
r = mid - 1;
}else {
l = mid;
}
}
if (s[i - r] != '#') {
if((r + 1) > len) {
res = s.substr(i - r, 2 * r + 1);
len = r + 1;
}
}
else {
if(r > len) {
res = s.substr(i - r, 2 * r + 1);
len = r;
}
}
}
string t = "";
for(int i = 0; i < res.size(); i++) {
if(res[i] != '#') t += res[i];
}
return t;
}
};
方法三：双指针
O(n^2)
枚举中点，然后用两个指针往两边走
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
string res = "";
for(int i = 0; i < n; i++) {
int l = i - 1, r = i + 1;
while(l >= 0 && r < n && s[l] == s[r]) l--, r++;
int t = r - l - 1;
if(t > res.size()) res = s.substr(l + 1, t);
l = i, r = i + 1;
while(l >= 0 && r < n && s[l] == s[r]) l--, r++;
t = r - l - 1;
if(t > res.size()) res = s.substr(l + 1, t);
}
return res;
}
};
方法四：区间DP
O(n^2)
const int N = 1010;
class Solution {
public:
bool dp[N][N];
string longestPalindrome(string s) {
int n = s.size();
s = '#' + s;
for(int i = 1; i <= n; i++) dp[i][i] = 1;
for(int len = 2; len <= n; len++) {
for(int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
if(len == 2) {
dp[i][j] = (s[i] == s[j]);
continue;
}
if(s[i] == s[j]) dp[i][j] |= dp[i + 1][j - 1];
else dp[i][j] = 0;
}
}
string res = "";
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
if(dp[i][j] && (j - i + 1) > res.size()) {
res = s.substr(i, j - i + 1);
}
}
}
return res;
}
};
6. N 字形变换
方法一：找规律：
class Solution {
public:
string convert(string s, int n) {
string res = "";
if(n == 1) return s; //注意这里要特判
for(int i = 0;i < n;i++){
if(i == 0 || i == n-1) {
for(int j = i;j < s.size();j += 2*n-2) {
res += s[j];
}
}else {
for(int j = i,k = 2*n-2-i;j < s.size() || k < s.size();j += 2*n-2, k+=2*n-2) {
if(j < s.size()) res += s[j];
if(k < s.size()) res += s[k];
}
}
}
return res;
}
};
方法二：模拟：
class Solution {
public:
string convert(string s, int numRows) {
int n = s.length(), r = numRows;
if (r == 1 || r >= n) {
return s;
}
int t = r * 2 - 2;
int c = (n + t - 1) / t * (r - 1);
vector<string> mat(r, string(c, 0));
for (int i = 0, x = 0, y = 0; i < n; ++i) {
mat[x][y] = s[i];
if (i % t < r - 1) {
++x; // 向下移动
} else {
--x;
++y; // 向右上移动
}
}
string ans;
for (auto &row : mat) {
for (char ch : row) {
if (ch) {
ans += ch;
}
}
}
return ans;
}
};
7. 整数反转
方法一：字符串翻转：
class Solution {
public:
int reverse(int x) {
int t = x > 0 ? 1 : -1;
x = abs(x);
string s = to_string(x);
for(int i = 0, j = s.size() - 1; i <= j; i++, j--) {
swap(s[i], s[j]);
}
x = 0;
try{
x = t * stoi(s);//变回数字
}catch(exception ex){}
return x;
}
};
方法二：整数各位拆分，在循环过程中判断是否溢出：
class Solution {
public:
int reverse(int x) {
int res = 0;
while(x) {
if(x > 0 && res > (INT_MAX - x % 10) / 10) return 0;
if(x < 0 && res < (INT_MIN - x % 10) / 10) return 0;
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
};
8. 字符串转换整数 (atoi)
模拟题：
find_first_not_of(' ') 找到字符串中第一个不是空格的位置，如果没有返回-1
class Solution {
public:
int myAtoi(string s) {
int n = s.size(), idx = s.find_first_not_of(' ');
if(idx == -1) {
// 表示字符串全为空格
return 0;
}
int minus = 1;
if(s[idx] == '-') {
// 为负数
minus = -1;
idx++;
}else if(s[idx] == '+') {
idx++;
}
long long res = 0;
while(idx < n && isdigit(s[idx])) {
res = res * 10 + (s[idx] - '0');
idx++;
if(res > INT_MAX) break;
}
res *= minus;
if(res > INT_MAX) res = INT_MAX;
if(res < INT_MIN) res = INT_MIN;
return res;
}
};
9. 回文数
方法一：变成字符串
class Solution {
public:
bool isPalindrome(int x) {
string s = to_string(x);
string t = string(s.rbegin(), s.rend());
return s == t;
}
};
方法二：直接做：
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0) return false;
int t = x;
long long res = 0;
while(t) {
res = res * 10 + t % 10;
t /= 10;
}
return res == x;
}
};
10. 正则表达式匹配
经验之谈，两个字符串，dp两维
dp[i][j] 表示s[1~i]和p[1~j]是否能够匹配(下标从1开始)
如果p[j] ≠ '*', 则dp[i][j] = (s[i] == p[j] || p[j] == '.') && dp[i-1][j-1] ,也就是只有当s[i]和p[j]成功匹配的时候（当p[j]=='.'的时候一定能匹配）并且s[1~i-1]和p[1~j-1]成功匹配的时候dp[i][j]才为1
如果p[j] == '*'， 需要枚举*代表多少个p[j-1], 这和完全背包问题很像，可以借鉴完全背包问题的优化方法，所以dp[i][j] = (dp[i][j-2] || (dp[i-1][j] && s[i] == p[j-1]
注意dp[0][j] 也是有可能匹配的，所以i要从0开始循环
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
s = ' ' + s, p = ' ' + p;
vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));
dp[0][0] = 1;
for(int i = 0; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(j + 1 <= m && p[j + 1] == '*') continue;
if(i && p[j] != '*') {
dp[i][j] = (s[i] == p[j] || p[j] == '.') && dp[i - 1][j - 1];
}else if(p[j] == '*') {
dp[i][j] = (dp[i][j-2] || (i && dp[i-1][j] && (s[i] == p[j-1] || p[j - 1] == '.')));
}
}
}
return dp[n][m];
}
};