- LeetCode 热题 HOT 100
- 前言
- 六、正则表达式匹配
- 七、盛最多水的容器
- 八、三数之和
- 九、 电话号码的字母组合
- 十、删除链表的倒数第 N 个结点
- 总结
前言
备战秋招，每天坚持，注意这不是题解，有的题我觉得简单的都没有注释，这相当于自己记录，督促自己的一个渠道。
题目顺序：前后交替
回顾：每一天回顾前一天没刷出来的题目，依次累加进行
提示：以下是本篇文章正文内容，下面案例可供参考
六、正则表达式匹配10. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。
比较难，动态规划，主要在于细节
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
s.insert(s.begin(), '0');
p.insert(p.begin(), '0');
vector> dp(n + 1, vector (m + 1, false));
//dp[i][j]表示s的前i个字符与p串的前j个字符是否匹配
dp[0][0] = true;
for (int j = 1; j <= m; j++) {
if (p[j] == '*') {//一定和前一个字符绑定在一起，p[j - 1]，p[j]
dp[0][j] = dp[0][j - 1];//s[0]和p[j]是否相同根据前一个判断
} else if (j + 1 > m || p[j + 1] != '*') {//没下一个字符，或下一个字符不为**
break;
} else {
dp[0][j] = true;
}
}
for (int i = 1; i <= n; i++) {//s
for (int j = 1; j <= m; j++) {//p
if (p[j] == '*') {
//p[j - 1]
dp[i][j] = dp[i][j - 1];
continue;
}
if (j + 1 <= m && p[j + 1] == '*') {
//空串 或 一个p[j] 或若干个p[j]
dp[i][j] = dp[i][j - 1] ||
(dp[i - 1][j - 1] && (p[j] == '.' || s[i] == p[j])) ||
(dp[i - 1][j] && (p[j] == '.' || s[i] == p[j]));
} else {
dp[i][j] = dp[i - 1][j - 1] && (p[j] == '.' || s[i] == p[j]);
}
}
}
return dp[n][m];
}
};
七、盛最多水的容器
11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
class Solution {
public:
int maxArea(vector& height) {
int left = 0;
int right = height.size() - 1;
int res = 0;
while (left < right) {
int cap = min(height[left], height[right]) * (right - left);
res = max(cap, res);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return res;
}
};
八、三数之和
15.三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
简要来说，三根指针，主要去重，以及先排序
class Solution {
public:
vector> threeSum(vector& nums) {
vector> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0) return res;
//去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1, right = nums.size() - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] > 0) {
right--;
} else if(nums[i] + nums[left] + nums[right] < 0) {
left++;
} else {
res.push_back(vector {nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
return res;
}
};
九、 电话号码的字母组合
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
class Solution {
public:
vector letterCombinations(string digits) {
if (digits.size() == 0) return res;
backtracking(digits, 0);
return res;
}
void backtracking(const string& digits, int index) {
if (digits.size() == index) {
res.push_back(s);
return ;
}
int digit = digits[index] - '0';
string letters = letterMap[digit];
for (int i = 0; i < letters.size(); i++) {
s.push_back(letters[i]);
backtracking(digits, index + 1);
s.pop_back();
}
}
private:
vector res;
string s;
const string letterMap[10] = {
"",//0
"",//1
"abc",//2
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
};
};
十、删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
快慢指针
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy -> next = head;
ListNode* fast = head;
ListNode* slow = dummy;
for (int i = 0; i < n; i++) {
fast = fast -> next;
}
while (fast != nullptr) {
fast = fast -> next;
slow = slow -> next;
}
slow -> next = slow -> next -> next;
ListNode* ans = dummy -> next;
delete dummy;
return ans;
}
};
总结
总之，加油
