文章目录
1. 两数之和（用哈希表减少查找的时间复杂度）2. 两数相加（高精度加法）3.无重复字符的最长子串：（模板：经典的滑动窗口算法）5. 最长回文子串（枚举）6. Z 自形变换（找规律）7.整数反转8. 字符串转换整数（atoi）9. 回文数11.盛水最多的容器（贪心（基于双指针来实现））12. 整数转罗马数字13. 罗马数字转整数14. 最长公共前缀15. 三数之和（双指针 + 去重）16. 最接近的三数之和（双指针算法）17. 电话号码的字母组合（标准 DFS）18. 四数之和（双指针算法）19. 删除链表的倒数第 N 个结点（前后双指针寻找结点 + dummy 避免特判）20. 有效的括号（栈的简单应用）21. 合并两个有序链表（模拟归并排序中的二路归并操作）22. 括号生成（DFS）24. 两两交换链表中的节点（链表结点交换算法）26. 删除有序数组中的重复项（经典双指针算法）27. 移除元素（简单的双指针算法）31. 下一个排列：32. 最长有效括号33.搜索旋转排序数组：34.在排序数组中查找元素的第一个和最后一个位置：35.搜索插入位置：36.有效的数独：37.解数独：38.外观数列：39.组合总和：40.组合总和：41.缺失的第一个正数：42.接雨水：43.字符串相乘：44.通配符匹配：45.跳跃游戏 II：46.全排列：47.全排列 II：48.旋转图像：49.字母异位词分组：50.Pow(x, n)：51. N 皇后（DFS）52. N 皇后 II（DFS，和 51 题完全一样，只是不需要记录方案是什么）53. 最大子数组和（动态规划）54. 螺旋矩阵55.跳跃游戏：56. 区间合并（模板：区间合并）57. 插入区间58. 最后一个单词的长度（模拟题）59. 螺旋矩阵 II（方向数组的简单应用）
1. 两数之和（用哈希表减少查找的时间复杂度）
class Solution {
public:
vector
unordered_map
for (int i = 0; i < nums.size(); i++)
{
if (dict.count(target - nums[i]))
return {dict[target - nums[i]], i};
else
dict[nums[i]] = i;
}
return {};
}
};
（注：本题也可以用双指针算法。）
2. 两数相加（高精度加法）
/**
* 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) {
ListNode* dummy = new ListNode(-1);
ListNode* p = dummy;
int t = 0;
while (l1 || l2 || t)
{
if (l1) {
t += l1->val;
l1 = l1->next;
}
if (l2) {
t += l2->val;
l2 = l2->next;
}
p->next = new ListNode(t % 10);
p = p->next;
t /= 10;
}
return dummy->next;
}
};
3.无重复字符的最长子串：（模板：经典的滑动窗口算法）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0;
unordered_map
for (int l = 0, r = 0; r < s.size(); r++)
{
ht[s[r]]++;
while (ht[s[r]] > 1)
{
ht[s[l]]--;
l++;
}
res = max(res, r - l + 1);
}
return res;
}
};
5. 最长回文子串（枚举）
class Solution {
public:
string longestPalindrome(string s) {
string res = "";
for (int i = 0; i < s.size(); i++) {
// 看回文串的长度是否是奇数
int l = i - 1, r = i + 1;
while (l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;
if (res.size() < r - (l + 1)) res = s.substr(l + 1, r - (l + 1));
// 看回文串的长度是否是偶数
l = i, r = i + 1;
while (l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;
if (res.size() < r - (l + 1)) res = s.substr(l + 1, r - (l + 1));
}
return res;
}
};
6. Z 自形变换（找规律）
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s; // numRows = 1会导致base为0，需要特判
string res = "";
int base = 2 * numRows - 2;
for (int k = 0; k < numRows; k++)
for (int i = 0; i < s.size(); i++)
if ((i - k) % base == 0 || (i + k) % base == 0)
res += s[i];
return res;
}
};
// 每一趟会有 numRows + (nuRows - 2) = 2 * numRows - 2 = base 个数
// 故最终第0行应该是满足 (i + 0) % base == 0的数
// 第1行是 (i + 1) % base == 0的数
// 第 k 行是 (i + k) % base == 0的数
// k的范围是从 0 到 numRows - 1
7.整数反转
class Solution {
public:
int reverse(int x) {
int res = 0;
bool is_minus = (x < 0);
while (x)
{
if (is_minus && res < (INT_MIN - x % 10) / 10) return 0;
if (!is_minus && res > (INT_MAX - x % 10) / 10) return 0;
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
};
8. 字符串转换整数（atoi）
class Solution {
public:
int myAtoi(string s) {
int res = 0;
bool is_minus = false;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == ' ') continue;
else if (s[i] == '+' || s[i] == '-')
{
is_minus = (s[i] == '-');
if (i + 1 < s.size() && !isdigit(s[i + 1])) return res;
else continue;
}
else if (isdigit(s[i]))
{
while (i < s.size() && isdigit(s[i]))
{
int t = s[i] - '0';
if (is_minus && res > (INT_MAX - t) / 10) return INT_MIN;
if (!is_minus && res > (INT_MAX - t) / 10) return INT_MAX;
res = res * 10 + t;
i++;
}
if (is_minus) return -res;
else return res;
}
else return res;
}
return res;
}
};
9. 回文数
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) return false;
if (!x) return true;
long long res = 0; // 翻转后有可能会溢出
int tmp = x;
while (tmp)
{
res = res * 10 + tmp % 10;
tmp /= 10;
}
return res == x;
}
};
11.盛水最多的容器（贪心（基于双指针来实现））
class Solution {
public:
int maxArea(vector
int res = 0;
int i = 0, j = height.size() - 1;
while (i < j)
{
res = max(res, min(height[i], height[j]) * (j - i));
if (height[i] < height[j]) i++;
else j--;
}
return res;
}
};
12. 整数转罗马数字
class Solution {
public:
string intToRoman(int num) {
unordered_map
{1, "I"}, {4, "IV"}, {5, "V"}, {9, "IX"},
{10, "X"}, {40, "XL"}, {50, "L"}, {90, "XC"},
{100, "C"}, {400, "CD"}, {500, "D"}, {900, "CM"},
{1000, "M"}
};
vector
string res = "";
for (auto b : base)
{
if (!num) break;
int cnt = num / b;
num %= b;
if (cnt)
{
for (int i = 0; i < cnt; i++)
res += dict[b];
}
}
return res;
}
};
13. 罗马数字转整数
class Solution {
public:
int romanToInt(string s) {
// 从右往左遍历，定义一个哈希表表示大小关系，正常情况下右边小于等于左边；
// 如果右边大于左边，说明出现了特殊规则
// unordered_map
// {'C', 5}, {'D', 6}, {'M', 7}}; /* 后记：val表的功能可以替代pri，故可以不用专门定义pri */
unordered_map
{'C', 100}, {'D', 500}, {'M', 1000}};
int res = 0;
for (int i = s.size() - 1; i >= 0;)
{
if (i && val[s[i]] > val[s[i - 1]]) // e.g. IV
{
res += val[s[i]] - val[s[i - 1]];
i -= 2;
}
else
{
res += val[s[i]];
i--;
}
}
return res;
}
};
14. 最长公共前缀
class Solution {
public:
string longestCommonPrefix(vector
string cp = strs[0];
for (auto& s : strs)
for (int i = 0; i < cp.size(); i++)
if (cp[i] != s[i])
{
cp.erase(cp.begin() + i, cp.end());
break;
}
return cp;
}
};
15. 三数之和（双指针 + 去重）
本题双指针算法的判定依据：
对于每一个固定的 i，当 j 增大时，k 必减小。
class Solution {
public:
vector
sort(nums.begin(), nums.end()); // sort是双指针算法和去重的前提
vector
for (int i = 0; i < nums.size() - 2; i++)
{
if (i && nums[i] == nums[i - 1]) continue; // 对i去重
for (int j = i + 1, k = nums.size() - 1; j < nums.size() - 1; j++)
{
if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 对j去重
while (j < k && nums[i] + nums[j] + nums[k] > 0) k--;
if (j == k) break; // 注意：两指针不能重合！
if (nums[i] + nums[j] + nums[k] == 0)
res.push_back({nums[i], nums[j], nums[k]});
}
}
return res;
}
};
16. 最接近的三数之和（双指针算法）
class Solution {
public:
int threeSumClosest(vector
sort(nums.begin(), nums.end());
pair
for (int i = 0; i < nums.size() - 2; i++)
{
if (i && nums[i] == nums[i - 1]) continue;
for (int j = i + 1, k = nums.size() - 1; j < k; j++)
{
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= target) k--;
int sum = nums[i] + nums[j] + nums[k];
res = min(res, make_pair(abs(sum - target), sum));
if (j < k - 1)
{
sum = nums[i] + nums[j] + nums[k - 1];
res = min(res, make_pair(target - sum, sum));
}
}
}
return res.second;
}
};
17. 电话号码的字母组合（标准 DFS）
class Solution {
public:
string s;
unordered_map
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
vector
vector
if (digits.empty()) return {};
dfs(digits, 0);
return res;
}
void dfs(string digits, int idx)
{
if (idx == digits.size())
{
res.push_back(s);
return;
}
for (char c : dict[digits[idx]])
{
s += c;
dfs(digits, idx + 1);
s.pop_back();
}
}
};
18. 四数之和（双指针算法）
class Solution {
public:
vector
vector
if (nums.size() < 4) return res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 3; i++)
{
if (i && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size() - 2; j++)
{
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
for (int k = j + 1, m = nums.size() - 1; k < m; k++)
{
if (k > j + 1 && nums[k] == nums[k - 1]) continue;
while (k < m - 1 && (long)nums[i] + nums[j] + nums[k] + nums[m - 1] >= target)
m--; // 注意：不加long会有数据溢出问题，下同
if ((long)nums[i] + nums[j] + nums[k] + nums[m] == target)
res.push_back({nums[i], nums[j], nums[k], nums[m]});
}
}
}
return res;
}
};
19. 删除链表的倒数第 N 个结点（前后双指针寻找结点 + 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* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(-1, head);
ListNode* left = dummy;
ListNode* right = head;
for (int i = 0; i < n; i++)
right = right->next;
while (right != nullptr)
{
left = left->next;
right = right->next;
}
left->next = left->next->next;
ListNode* res = dummy->next;
delete dummy; // 删除哑节点，释放内存
return res;
}
};
20. 有效的括号（栈的简单应用）
class Solution {
public:
bool isValid(string s) {
stack
for (auto c : s)
{
if (c == '(' || c == '{' || c == '[')
stk.push(c);
else
{
// if (stk.empty() || (c == ')' && stk.top() != '(') || (c == '}' && stk.top() != '{') || (c == ']' && stk.top() != '['))
if (stk.empty() || abs(stk.top() - c) > 2) // (){}[] = 40 41 123 125 91 93
return false;
else
stk.pop();
}
}
return stk.empty();
}
};
21. 合并两个有序链表（模拟归并排序中的二路归并操作）
/**
* 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dummy = new ListNode(-1);
ListNode* p = dummy;
ListNode* p1 = list1;
ListNode* p2 = list2;
while (p1 && p2)
{
if (p1->val <= p2->val)
{
p->next = p1;
p1 = p1->next;
}
else
{
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if (p1) p->next = p1;
if (p2) p->next = p2;
return dummy->next;
}
};
22. 括号生成（DFS）
class Solution {
public:
string s;
vector
vector
// 左括号用了i个，右括号用了j个，当i == j == n时，即可
dfs(n, 0, 0);
return res;
}
void dfs(int n, int left, int right)
{
if (left == n && right == n)
{
res.push_back(s);
return;
}
// 左分支的条件如果满足，就转向左分支
if (left < n)
{
s += '(';
dfs(n, left + 1, right); // 在左分支里继续进行递归
s.pop_back(); // 和回溯
}
//如果右分支的条件满足，就转向右分支
if (right < left)
{
s += ')';
dfs(n, left, right + 1); // 在右分支里继续进行递归
s.pop_back(); // 和回溯
}
}
};
24. 两两交换链表中的节点（链表结点交换算法）
/**
* 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* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(-1, head);
ListNode* p = dummy;
while (p->next && p->next->next)
{
ListNode* left = p->next; // 必须要先用两个临时结点把p->next
ListNode* right = p->next->next; // 和p->next->next保存起来
p->next = right;
left->next = right->next;
right->next = left;
p = left; // <=> p = p->next->next;
}
return dummy->next;
}
};
26. 删除有序数组中的重复项（经典双指针算法）
class Solution {
public:
int removeDuplicates(vector
int k = 0;
for (int i = 0; i < nums.size(); i++)
{
if (!i || nums[i] != nums[i - 1])
nums[k++] = nums[i];
}
return k;
}
};
27. 移除元素（简单的双指针算法）
第一种实现方式：两个指针都从左往右走
class Solution {
public:
int removeElement(vector
int k = 0; // k是新数组的长度，初始时为0
for (int i = 0; i < nums.size(); i++)
if (nums[i] != val)
nums[k++] = nums[i];
return k;
}
};
第二种实现方式：两个指针从两头出发往中间走
class Solution {
public:
int removeElement(vector
int n = nums.size();
int i = -1, j = n;
while (i < j)
{
do i++; while (i < j && nums[i] != val);
do j--; while (i < j && nums[j] == val);
if (i < j) swap(nums[i], nums[j]);
}
return i;
}
};
// 注：这种实现方式可以应对以下两种边界情况：
// （1）nums为空；
// （2）nums仅含1个元素
31. 下一个排列：
class Solution {
public:
void nextPermutation(vector
int n = nums.size();
// 从后往前找到第一对升序的元素
int i = n - 1;
while (i >= 1 && nums[i - 1] >= nums[i]) i--;
if (i == 0) // 如果不存在升序元素对，
reverse(nums.begin(), nums.end()); // 直接将降序翻转为升序
else // 如果存在升序元素对，
{
int j = i; i--; // 此时nums[i - 1], nums[i]即为从后往前第一对升序元素
// 再次从后往前，寻找第一个大于nums[i]的元素
int k = n - 1;
while (k > i && nums[i] >= nums[k]) k--;
// 找到后将nums[i]和nums[k]交换
swap(nums[i], nums[k]);
// 此时[j, end)必降序，将其翻转为升序即可
reverse(nums.begin() + j, nums.end());
}
}
};
32. 最长有效括号
class Solution {
public:
int longestValidParentheses(string s) {
int res = 0;
stack
for (int i = 0, start = -1; i < s.size(); i++)
{
if (s[i] == '(') stk.push(i);
else // 来右括号
{
if (!stk.empty()) // 来右括号且栈不空，说明栈顶有左括号
{
stk.pop(); // 将左括号弹出，
if (!stk.empty()) // 如果弹出后栈顶仍有左括号，
res = max(res, i - stk.top()); // 则左括号的下一个位置到i的长度即为当前i对应的最大有效括号长度
else
res = max(res, i - start); // 如果将栈顶左括号弹出后栈空，则从start + 1到i皆为有效长度
}
else // 来右括号且栈空
{
start = i;
}
}
}
return res;
}
};
33.搜索旋转排序数组：
class Solution {
public:
int search(vector
int l = 0, r = nums.size() - 1;
while (l <= r)
{
int mid = l + r >> 1;
if (nums[mid] == target) return mid;
// 我们要做的就是确定每次的mid到底是在左半段还是右半段中
if (nums[l] <= nums[mid]) // 说明mid在左半段，则左半段可以二分
{
if (nums[l] <= target && target < nums[mid])
r = mid - 1;
else
l = mid + 1;
}
else // 说明mid在右半段，则右半段可以二分
{
if (nums[mid] < target && target <= nums[r])
l = mid + 1;
else
r = mid - 1;
}
}
return -1;
}
};
34.在排序数组中查找元素的第一个和最后一个位置：
class Solution {
public:
vector
vector
if (nums.empty()) return {-1, -1};
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (nums[l] != target) return {-1, -1};
else
{
res.push_back(l);
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (nums[mid] <= target) l = mid;
else r = mid - 1;
}
res.push_back(l);
}
return res;
}
};
35.搜索插入位置：
// 找到从前往后第一个大于等于target的位置
class Solution {
public:
int searchInsert(vector
int l = 0, r = nums.size(); // 注意：此处不再是nums.size() - 1
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
};
36.有效的数独：
class Solution {
public:
bool row[9][9], col[9][9], block[3][3][9];
bool isValidSudoku(vector
memset(row, 0, sizeof row);
memset(col, 0, sizeof col);
memset(block, 0, sizeof block);
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (board[i][j] != '.')
{
int t = board[i][j] - '1';
if (row[i][t] || col[j][t] || block[i / 3][j / 3][t])
return false;
else
row[i][t] = col[j][t] = block[i / 3][j / 3][t] = true;
}
return true;
}
};
37.解数独：
class Solution {
public:
bool row[9][9], col[9][9], block[3][3][9];
void solveSudoku(vector
memset(row, 0, sizeof row);
memset(col, 0, sizeof col);
memset(block, 0, sizeof block);
int n = board.size(), m = board[0].size();
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (board[i][j] != '.')
{
int t = board[i][j] - '1';
row[i][t] = col[j][t] = block[i / 3][j / 3][t] = true;
}
dfs(board, 0, 0);
}
bool dfs(vector
{
int n = board.size(), m = board[0].size();
if (y == m) { y = 0; x++; }
if (x == n) return true;
if (board[x][y] != '.') return dfs(board, x, y + 1);
for (int num = 0; num < 9; num++)
{
if (!row[x][num] && !col[y][num] && !block[x / 3][y / 3][num])
{
board[x][y] = num + '1';
row[x][num] = col[y][num] = block[x / 3][y / 3][num] = true;
if (dfs(board, x, y + 1)) return true;
board[x][y] = '.';
row[x][num] = col[y][num] = block[x / 3][y / 3][num] = false;
}
}
return false;
}
};
38.外观数列：
class Solution {
public:
string countAndSay(int n) {
string s = "1";
for (int i = 0; i < n - 1; i++)
{
string tmp = "";
for (int j = 0; j < s.size();)
{
int k = j + 1;
while (k < s.size() && s[j] == s[k]) k++;
tmp += to_string(k - j) + s[j];
j = k;
}
s = tmp;
}
return s;
}
};
39.组合总和：
第一种 DFS：逐数字枚举
class Solution {
public:
vector
vector
vector
dfs(candidates, 0, target);
return res;
}
void dfs(vector
{
if (target == 0)
{
res.push_back(path);
return;
} // 注意：此if与后面if的顺序不能颠倒！
if (u == candidates.size()) return;
// skip current position
dfs(candidates, u + 1, target);
// choose current position
if (target - candidates[u] >= 0)
{
path.push_back(candidates[u]);
dfs(candidates, u, target - candidates[u]);
path.pop_back();
}
}
};
第二种 DFS：按第 i 个数选多少个来搜索
class Solution {
public:
vector
vector
vector
dfs(candidates, 0, target);
return res;
}
void dfs(vector
{
if (target == 0)
{
res.push_back(path);
return;
} // 注意：此if与后面if的顺序不能颠倒！
if (u == candidates.size()) return;
for (int i = 0; i * candidates[u] <= target; i++)
{
dfs(candidates, u + 1, target - i * candidates[u]);
path.push_back(candidates[u]);
}
for (int i = 0; i * candidates[u] <= target; i++)
path.pop_back();
}
};
40.组合总和：
class Solution {
public:
vector
vector
vector
sort(candidates.begin(), candidates.end());
dfs(candidates, 0, target);
return res;
}
void dfs(vector
{
if (target == 0)
{
res.push_back(path);
return;
}
if (idx == candidates.size()) return;
int prev = -1;
for (int i = idx; i < candidates.size(); i++)
{
if (prev != candidates[i] && candidates[i] <= target)
{
prev = candidates[i];
path.push_back(candidates[i]);
dfs(candidates, i + 1, target - candidates[i]);
path.pop_back();
}
}
}
};
41.缺失的第一个正数：
class Solution {
public:
int firstMissingPositive(vector
int n = nums.size();
for (int i = 0; i < n; i++)
{
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
swap(nums[nums[i] - 1], nums[i]);
}
for (int i = 0; i < n; i++)
{
if (nums[i] != i + 1)
return i + 1;
}
return n + 1;
}
};
42.接雨水：
class Solution {
public:
int trap(vector
int ans = 0;
int l = 0, r = height.size() - 1;
int lmax = 0, rmax = 0;
while (l < r)
{
lmax = max(lmax, height[l]);
rmax = max(rmax, height[r]);
if (lmax <= rmax)
{
ans += lmax - height[l];
l++;
}
else
{
ans += rmax - height[r];
r--;
}
}
return ans;
}
};
43.字符串相乘：
class Solution {
public:
string multiply(string num1, string num2) {
int n = num1.size(), m = num2.size();
vector
for (int i = n - 1; i >= 0; i--) A.push_back(num1[i] - '0');
for (int i = m - 1; i >= 0; i--) B.push_back(num2[i] - '0');
vector
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
C[i + j] += A[i] * B[j];
// 集中处理进位
int t = 0;
for (int i = 0; i < C.size(); i++)
{
t += C[i];
C[i] = t % 10;
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
string res;
for (int i = C.size() - 1; i >= 0; i--) res += C[i] + '0';
return res;
}
};
44.通配符匹配：
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
s = ' ' + s, p = ' ' + p;
vector
f[0][0] = true;
for (int i = 0; i <= n; i++) // i必须从0开始，因为f[0][j]是有意义的
for (int j = 1; j <= m; j++) // j可以从1开始，因为f[i][0]必为false
if (p[j] == '*')
f[i][j] = f[i][j - 1] || (i && f[i - 1][j]);
else
f[i][j] = (s[i] == p[j] || p[j] == '?') && (i && f[i - 1][j - 1]);
return f[n][m];
}
};
45.跳跃游戏 II：
class Solution {
public:
int jump(vector
int n = nums.size();
vector
for (int i = 1, j = 0; i < n; i++)
{
while (j + nums[j] < i) j++;
f[i] = f[j] + 1;
}
return f[n - 1];
}
};
46.全排列：
class Solution {
public:
vector
vector
bool st[10];
vector
dfs(nums, 0);
return res;
}
void dfs(vector
{
if (u == nums.size())
{
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++)
{
if (!st[i])
{
path.push_back(nums[i]);
st[i] = true;
dfs(nums, u + 1);
path.pop_back();
st[i] = false;
}
}
}
};
47.全排列 II：
class Solution {
public:
vector
vector
bool st[10];
vector
vector
sort(tmp.begin(), tmp.end());
dfs(tmp, 0);
return res;
}
void dfs(vector
{
if (u == nums.size())
{
res.push_back(path);
return;
}
int prev = -11;
for (int i = 0; i < nums.size(); i++)
{
if (prev != nums[i] && !st[i])
{
prev = nums[i];
path.push_back(nums[i]);
st[i] = true;
dfs(nums, u + 1);
path.pop_back();
st[i] = false;
}
}
}
};
48.旋转图像：
class Solution {
public:
void rotate(vector
/* 两次对称即可：先沿反对角线对称，再沿中轴左右对称*/
int n = matrix.size();
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
swap(matrix[i][j], matrix[j][i]);
for (int i = 0; i < n; i++)
for (int j = 0; j < n / 2; j++)
swap(matrix[i][j], matrix[i][n - 1 - j]);
}
};
49.字母异位词分组：
class Solution {
public:
vector
unordered_map
for (auto& str : strs)
{
string tmp = str;
sort(tmp.begin(), tmp.end());
map[tmp].push_back(str);
}
vector
for (auto& item : map) res.push_back(item.second);
return res;
}
};
50.Pow(x, n)：
class Solution {
public:
double myPow(double x, int n) {
typedef long long LL;
bool is_minus = n < 0;
double res = 1;
for (LL k = abs(LL(n)); k; k >>= 1)
{
if (k & 1) res *= x;
x *= x;
}
if (is_minus) res = 1 / res;
return res;
}
};
51. N 皇后（DFS）
class Solution {
public:
bool col[10], dg[20], udg[20];
vector
vector
// 初始化棋盘
vector
for (int i = 0; i < n; i++)
g.push_back(string(n, '.'));
dfs(0, n, g);
return res;
}
void dfs(int u, int n, vector
{
if (u == n)
{
res.push_back(g);
return;
}
for (int i = 0; i < n; i++)
{
if (!col[i] && !dg[u - i + n] && !udg[u + i])
{
g[u][i] = 'Q';
col[i] = dg[u - i + n] = udg[u + i] = true;
dfs(u + 1, n, g);
g[u][i] = '.';
col[i] = dg[u - i + n] = udg[u + i] = false;
}
}
}
};
52. N 皇后 II（DFS，和 51 题完全一样，只是不需要记录方案是什么）
class Solution {
public:
bool col[10], dg[20], udg[20];
int res = 0;
int totalNQueens(int n) {
dfs(0, n);
return res;
}
void dfs(int u, int n)
{
if (u == n)
{
res++;
return;
}
for (int i = 0; i < n; i++)
{
if (!col[i] && !dg[u - i + n] && !udg[u + i])
{
col[i] = dg[u - i + n] = udg[u + i] = true;
dfs(u + 1, n);
col[i] = dg[u - i + n] = udg[u + i] = false;
}
}
}
};
53. 最大子数组和（动态规划）
从动态规划的角度去理解：（更推荐）
class Solution {
public:
int maxSubArray(vector
int res = INT_MIN;
for (int i = 0, last = 0; i < nums.size(); i++)
{
last = nums[i] + max(last, 0);
res = max(res, last);
}
return res;
}
};
// 动态规划：
// f[i] 表示所有以nums[i]结尾的连续子数组的最大和
// f[i] = max(nums[i], f[i - 1] + nums[i]) = nums[i] + max(f[i - 1], 0);
// 由于只用到了两个状态，因此可以用一个变量保存f[i - 1]，这样空间复杂度可以优化至O(1)
从贪心的角度去理解：
class Solution {
public:
int maxSubArray(vector
int res = -1e5, sum = 0;
for (int i = 0; i < nums.size(); i++)
{
sum += nums[i];
if (sum < nums[i]) sum = nums[i];
res = max(res, sum);
}
return res;
}
};
// 贪心：
// 从左到右扫描，
54. 螺旋矩阵
方法一：（迭代）利用方向数组（推荐）
class Solution {
public:
vector
vector
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int m = matrix.size(), n = matrix[0].size();
vector
for (int i = 0, x = 0, y = 0, d = 0; i < m * n; i++)
{
// 先判断上一步有没有走对，如果没有走对，就纠正上一步并让其走对
if (x < 0 || x >= m || y < 0 || y >= n || st[x][y])
{
x -= dx[d], y -= dy[d];
d = (d + 1) % 4;
x += dx[d], y += dy[d];
}
// 如果走对的话就记录
res.push_back(matrix[x][y]);
st[x][y] = true;
x += dx[d], y += dy[d]; // 并继续往前走
}
return res;
}
};
方法二：（DFS）模拟
class Solution {
public:
vector
vector
int m = matrix.size(), n = matrix[0].size();
dfs(matrix, 0, 0, m - 1, n - 1); // 传入的是左上角和右下角的坐标(x1, y1)和(x2, y2)
return res;
}
void dfs(vector
{
if (x1 > x2 || y1 > y2) return;
int i = x1, j = y1;
while (j <= y2)
{
res.push_back(matrix[i][j]);
j++;
}
j--,i++;
while (i <= x2)
{
res.push_back(matrix[i][j]);
i++;
}
i--, j--;
while (i > x1 && j >= y1) // i > x1的目的是防止出现回退，如第2个测试用例
{
res.push_back(matrix[i][j]);
j--;
}
j++, i--;
while (j < y2 && i > x1) // j < y2的目的也是防止出现回退，例如[[7], [9], [6]]
{
res.push_back(matrix[i][j]);
i--;
}
dfs(matrix, x1 + 1, y1 + 1, x2 - 1, y2 - 1);
}
};
55.跳跃游戏：
class Solution {
public:
bool canJump(vector
for (int i = 0, j = 0; i < nums.size(); i++)
{
if (j < i) return false;
j = max(j, i + nums[i]);
}
return true;
}
};
56. 区间合并（模板：区间合并）
class Solution {
public:
vector
vector
sort(intervals.begin(), intervals.end());
int st = -1, ed = -1;
for (auto seg : intervals)
{
if (ed < seg[0])
{
if (st != -1) res.push_back({st, ed});
st = seg[0], ed = seg[1];
}
else ed = max(ed, seg[1]);
}
if (st != -1) res.push_back({st, ed});
return res;
}
};
57. 插入区间
方法一：先用二分查找找到插入位置，将新区间插入，再调用标准的区间合并算法
class Solution {
public:
vector
// 先二分找到插入位置
int l = 0, r = intervals.size();
while (l < r)
{
int mid = l + r >> 1;
if (intervals[mid][0] >= newInterval[0]) r = mid;
else l = mid + 1;
}
intervals.insert(intervals.begin() + l, newInterval);
// 调用区间合并模板
int st = -1, ed = -1;
vector
for (int i = 0; i < intervals.size(); i++)
{
if (ed < intervals[i][0])
{
if (st != -1) res.push_back({st, ed});
st = intervals[i][0], ed = intervals[i][1];
}
else ed = max(ed, intervals[i][1]);
}
if (st != -1) res.push_back({st, ed});
return res;
}
};
方法二：（Y总做法）模拟
class Solution {
public:
vector
vector
// 首先寻找左侧没有交叠的区间
int k = 0;
while (k < intervals.size() && intervals[k][1] < newInterval[0])
{
res.push_back(intervals[k]);
k++;
}
// 对中间有交叠的区间进行合并
if (k < intervals.size()) // 这一条件可以处理intervals为空的情况
{
newInterval[0] = min(intervals[k][0], newInterval[0]);
while (k < intervals.size() && intervals[k][0] <= newInterval[1])
{
newInterval[1] = max(intervals[k][1], newInterval[1]);
k++;
}
}
res.push_back(newInterval);
// 右侧没有交叠的区间也照抄
while (k < intervals.size())
{
res.push_back(intervals[k]);
k++;
}
return res;
}
};
58. 最后一个单词的长度（模拟题）
class Solution {
public:
int lengthOfLastWord(string s) {
int k = s.size() - 1;
while (s[k] == ' ') k--;
int j = k;
while (j >= 0 && s[j] != ' ') j--;
return k - j;
}
};
59. 螺旋矩阵 II（方向数组的简单应用）
class Solution {
public:
vector
vector
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
for (int i = 1, x = 0, y = 0, d = 0; i <= n * n; i++)
{
if (x < 0 || x >= n || y < 0 || y >= n || res[x][y] != 0)
{
x -= dx[d], y -= dy[d];
d = (d + 1) % 4;
x += dx[d], y += dy[d];
}
res[x][y] = i;
x += dx[d], y += dy[d];
}
return res;
}
};
文章来源
发表评论