1. 两数之和
用一个 unordered_map 来存储已经访问过的数字和它们的索引。对于每个数字，检查 target - nums[i] 是否在 unordered_map 中，如果存在，则返回对应的索引和当前索引；如果不存在，则将当前数字和索引存入 unordered_map 中。
时间复杂度： $O(n)$。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
for (size_t i = 0; i < nums.size(); i++)
{
if (mp.find(target - nums[i]) != mp.end())
return { mp[target - nums[i]], static_cast<int>(i) };
mp[nums[i]] = i;
}
return {};
}
};
2. 两数相加
创建一个新链表储存两个链表相加后的结果。相加的时候先不进行进位，在相加完成之后再去遍历链表统一处理进位。如果进位后链表末端的值大于 9，则在末端添加一个新的节点。
时间复杂度： $O(\max(m, n))$。
/**
* 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) {
if (l1 == nullptr)
return l2;
if (l2 == nullptr)
return l1;
ListNode *head = new ListNode(l1->val + l2->val);
head->next = addTwoNumbers(l1->next, l2->next);
ListNode *tail = head;
while (tail->next)
{
if (tail->val > 9)
tail->next->val++, tail->val -= 10;
tail = tail->next;
}
if (tail->val > 9)
tail->next = new ListNode(1), tail->val -= 10;
return head;
}
};
3. 无重复字符的最长子串
使用两个指针 l 和 r 来维护一个滑动窗口，初始时都指向字符串的开头。用 unordered_map 来记录当前窗口内的字符是否出现过。每次将 r 指向的字符加入窗口，如果该字符已经在窗口中出现过，则移动 l 指针直到该字符不再出现在窗口中。每次更新最长子串的长度。
时间复杂度： $O(n)$。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, bool> vis;
int l = 0, r = 0, n = s.size(), ans = 0;
while (r < n)
{
while (l < r && vis.find(s[r]) != vis.end() && vis[s[r]])
vis[s[l]] = false, l++;
vis[s[r]] = true;
r++;
ans = max(ans, r - l);
}
return ans;
}
};
4. 寻找两个正序数组的中位数
通过二分查找来找到第 $k$ 小的元素。每次比较两个数组中第 $k/2$ 个元素的大小，较小的那个数组中前 $k/2$ 个元素都不可能是第 $k$ 小的元素，因此可以将其排除掉，并更新 $k$ 的值。重复这个过程直到找到第 $k$ 小的元素。
时间复杂度： $O(\log(m + n))$。
class Solution {
public:
double binarySearch(vector<int>& nums1, vector<int>& nums2, int k)
{
int l1 = 0, r1 = nums1.size(), l2 = 0, r2 = nums2.size();
while (k)
{
if (l1 == r1)
return nums2[l2 + k - 1];
if (l2 == r2)
return nums1[l1 + k - 1];
if (k == 1)
return min(nums1[l1], nums2[l2]);
int mid1 = min(r1 - 1, l1 + k / 2 - 1);
int mid2 = min(r2 - 1, l2 + k / 2 - 1);
if (nums1[mid1] < nums2[mid2])
k -= (mid1 - l1 + 1), l1 = mid1 + 1;
else
k -= (mid2 - l2 + 1), l2 = mid2 + 1;
}
return 0;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if ((m + n) % 2 == 0)
return (binarySearch(nums1, nums2, (m + n) / 2) +
binarySearch(nums1, nums2, (m + n) / 2 + 1)) / 2;
else
return binarySearch(nums1, nums2, (m + n + 1) / 2);
}
};
5. 最长回文子串
设 $dp_{i, j}$ 为字符串 $s$ 的第 $i$ 个字符到第 $j$ 个字符是否为回文串。初始时，所有长度为 1 的子串都是回文串，因此 $dp_{i, i} = 1$。对于长度大于 $1$ 的子串，如果 $s[i]$ 和 $s[j]$ 相等，并且 $dp_{i + 1, j - 1}$ 为真，则 $dp_{i, j}$ 也为真。最后，从最长的子串开始检查，找到第一个满足条件的回文子串并返回。
时间复杂度： $O(n^2)$。
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
s = " " + s;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i][j] = 1;
}
}
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
dp[l][r] = dp[l + 1][r - 1] & (s[l] == s[r]);
}
}
for (int len = n; len; len--) {
for (int l = 1; l + len - 1 <= n; l++) {
if (dp[l][l + len - 1]) return s.substr(l, len);
}
}
return "";
}
};
6. Z 字形变换
按照题目要求将字符串 $s$ 重新排列成 Z 字形。首先计算出每个字符在 Z 字形中的位置，然后按照行的顺序将字符连接起来形成最终的字符串。
| 时间复杂度： $O( | s | )$。 |
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
string ans = "";
int n = s.size();
s = " " + s;
int t = 2 * numRows - 2;
for (int row = 1; row <= numRows; row++) {
for (int pos = row; pos <= n; pos += t) {
ans.push_back(s[pos]);
if (row > 1 && row < numRows && pos + 2 * (numRows - row) <= n)
ans.push_back(s[pos + 2 * (numRows - row)]);
}
}
return ans;
}
};
7. 整数反转
将整数先转换成字符串，然后反转字符串。对于正数，直接反转整个字符串；对于负数，反转除第一个字符以外的部分。最后检查反转后的字符串是否超过 32 位整数的范围，如果超过则返回 0，否则返回转换后的整数。
| 时间复杂度： $O(\log | x | )$。 |
class Solution {
public:
int reverse(int x) {
string maxm = to_string(INT_MAX), minm = to_string(INT_MIN);
string ans = to_string(x);
if (x > 0) std::reverse(ans.begin(), ans.end());
else std::reverse(ans.begin() + 1, ans.end());
if (x > 0 && ans.size() == maxm.size() && ans > maxm) return 0;
if (x < 0 && ans.size() == minm.size() && ans > minm) return 0;
return std:: stoi(ans);
return 0;
}
};
8. 字符串转换整数 (atoi)
按照题意模拟即可。首先去掉字符串开头的空格，然后检查第一个非空字符是否为正负号，如果是，则记录符号并继续处理后续字符。接下来逐个处理后续字符，如果遇到非数字字符则停止处理。最后根据记录的符号和处理得到的数字进行范围检查，确保结果在 32 位整数的范围内。
| 时间复杂度： $O( | s | )$。 |
class Solution {
public:
int myAtoi(string s) {
int pos = 0;
while (pos < s.size() && s[pos] == ' ') pos++;
s = s.substr(pos, s.size() - pos);
if (s.size() == 0 || ((s[0] < '0' || s[0] > '9') && s[0] != '-' && s[0] != '+'))
return 0;
int n = s.size();
s = " " + s;
int f = 1;
long long num = 0;
bool flag = false;
for (int i = 1; i <= n; i++) {
if (i == 1 && (s[i] == '-' || s[i] == '+')) {
f = s[i] == '-' ? -1 : 1;
continue;
}
if (flag && (s[i] < '0' || s[i] > '9')) break;
if (i > 1 && (s[i] < '0' || s[i] > '9')) break;
num = num * 10 + s[i] - '0';
flag = true;
if (f > 0) num = min(num, 1LL * INT_MAX);
if (f < 0) num = min(num, -1LL * INT_MIN);
}
return num * f;
}
};
9. 回文数
将整数转换成字符串，然后检查字符串是否是回文。可以通过比较字符串的前半部分和后半部分来判断是否是回文。
| 时间复杂度： $O(\log | x | )$。 |
class Solution {
public:
bool isPalindrome(int x) {
string str = to_string(x);
for (int i = 0; i < (int)str.size() / 2; i++)
if (str[i] != str[str.size() - i - 1]) return false;
return true;
}
};
10. 正则表达式匹配
设 $dp[i][j]$ 表示字符串 $s$ 的前 $i$ 个字符和模式 $p$ 的前 $j$ 个字符是否匹配。状态转移方程为：
\[f[i][j] = \begin{cases} \text{if } p[j] \ne '*'= \begin{cases} f[i-1][j-1], & \text{if } check(s[i], p[j]) \\ \text{false}, & \text{otherwise} \end{cases}\\ \text{otherwise}= \begin{cases} f[i-1][j] \ \text{or} \ f[i][j-2], & \text{if } check(s[i], p[j-1]) \\ f[i][j-2], & \text{otherwise} \end{cases} \end{cases}\]class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
s = " " + s, p = " " + p;
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
auto check = [&](int i, int j) {
if (i == 0) return false;
if (p[j] == '.') return true;
return s[i] == p[j];
};
dp[0][0] = 1;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j] == '*') {
dp[i][j] |= dp[i][j - 2];
if (check(i, j - 1)) dp[i][j] |= dp[i - 1][j];
} else {
if (check(i, j)) dp[i][j] |= dp[i - 1][j - 1];
}
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cout << dp[i][j] << ' ';
}
cout << endl;
}
return dp[m][n];
}
};