【LeetCode 热题 HOT 100】6-10题-正则表达式 盛最多水的容器 三数之和 回 ...

1. 正则表达式匹配

   给你一个字符串 s 和一个字符规律 p，请你来实现一个支持'.' 和 '*' 的正则表达式匹配。
  

• '.'匹配恣意单个字符
  
• '*'匹配零个或多个前面的那一个元素
  所谓匹配，是要涵盖 **整个 **字符串 s的，而不是部分字符串。
  
  
  
  

    即
  

• X* 可以没有X或者可以用来匹配多个 X
  例如 s="abbbc" p="ab*bc"
  如果*匹配0个字符 p=“abc”，dp[5][5]=dp[5][3]
  如果*匹配一个 p=“abbc”
  如果*匹配多个 p=“abb…c”
  

  

1. class Solution {
2. public:
3.     bool isMatch(string s, string p) {
4.         int m = s.size(), n = p.size();
5.         vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
6.         
7.         dp[0][0] = true;  // 空字符串和空模式匹配
8.         
9.         // 处理模式前缀是 '*' 的情况
10.         for (int j = 1; j<=n; j++) {
11.             if (p[j-1] == '*') {
12.                 dp[0][j] = dp[0][j-2];  // 这里一定是-2
13.             }
14.         }
16.         for (int i = 1 ; i<=m; i++) {
17.             for (int j = 1; j<=n; j++) {
18.                 if (s[i-1] == p[j-1] || p[j-1] == '.') {  // p为.时, 这一位可以忽略。dp[i][j] = d[i-1][j-1]
19.                     dp[i][j] = dp[i-1][j-1];
20.                 } else if (p[j-1] == '*') { // 如果p遇到*
21.                     dp[i][j] = dp[i][j-2]  ||   // '*'匹配0个前面的字符
22.                                 ( (s[i-1] == p[j-2] ||p[j-2] == '.' ) && dp[i-1][j] ); // '*'匹配1或多个字符
23.                 }
24.             }
25.         }
26.         return dp[m][n];
27.     }
28. };

复制代码

1.思绪

子串匹配，想到 创建二维布尔型向量 dp
分两步：

• 定义状态
  
• 定义状态转移方程
  

• 状态
  

d[j] 表示s[..(i-1)]与p[..(j-1)]是否匹配。终极的dp[m][n]为本题答案。（ m=s.size(), n=p.size() , i/j 表示第 i/j 个字符。dp[0][0]表示空字符串和空模式）

• 状态转移
  dp[j]由s[i-1] p[j-1]和dp[j]前面的状态决定
  
  
  • 如果第 i个字符 s[i-1] == p[j-1] 或者 p[j-1] == ‘.’
    此时 dp[j] = dp[i-1][j-1];
    
  • 如果 s[i-1] 与 p[j-1] 不匹配，且 p[j] != ‘*’
    返回匹配失败。
    
  • 如果 s[i-1] 与 p[j-1] 不匹配，但 p[j-1] == ‘*’
    这里又分两种情况，由于*代表可以看成前一个元素的0个或多个字符
    
    
    
    • 如果 s[i-1] 和 p[j-2] 不匹配，则 ‘*’ 只能把前面元素 p[j-2] 匹配为0个。就是同时去掉了 p[j-1] 和 p[j-2] 。
      此时意味着我们跳过 * 和它前面的字符，即我们不思量 p[j-1] 和 p[j-2] 的匹配，直接去看 dp[j-2]。所以dp[j] = dp[j-2]
      
    • 如果 s[i-1] 和 p[j-2] 匹配，则 ‘*’ 可以把前面元素p[j-2]变为1个或多个。
      此时可以让’ * '匹配一个 s[j-1] ，必要看dp[i-1][j]，即( (s[i-1] == p[j-2] ||p[j-2] == '.' ) && dp[i-1][j] )
      
    
    
  
  

官方的答案：

1. class Solution {
2. public:
3.     bool isMatch(string s, string p) {
4.         int m = s.size();
5.         int n = p.size();
7.         auto matches = [&](int i, int j) {
8.             if (i == 0) {
9.                 return false;
10.             }
11.             if (p[j - 1] == '.') {
12.                 return true;
13.             }
14.             return s[i - 1] == p[j - 1];
15.         };
17.         vector<vector<int>> f(m + 1, vector<int>(n + 1));
18.         f[0][0] = true;
19.         for (int i = 0; i <= m; ++i) {
20.             for (int j = 1; j <= n; ++j) {
21.                 if (p[j - 1] == '*') {
22.                     f[i][j] |= f[i][j - 2];
23.                     if (matches(i, j - 1)) {
24.                         f[i][j] |= f[i - 1][j];
25.                     }
26.                 }
27.                 else {
28.                     if (matches(i, j)) {
29.                         f[i][j] |= f[i - 1][j - 1];
30.                     }
31.                 }
32.             }
33.         }
34.         return f[m][n];
35.     }
36. };

复制代码

2. 盛最多水的容器

   给定一个长度为n的整数数组 height 。有 n 条垂线，第i条线的两个端点是 (i, 0) 和 (i, height) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
阐明： 你不能倾斜容器。
  

1. class Solution {
2. public:
3.     int maxArea(vector<int>& height) {
4.         int left = 0, right = height.size() - 1;
5.         int maxArea = 0;
7.         while (left < right) {
8.             int tempmax = min(height[left], height[right]) * (right - left);
9.             maxArea = max(maxArea, tempmax);
11.             if (height[left]<height[right]) {
12.                 left++;
13.             } else {
14.                 --right;
15.             }
16.         }
17.         return maxArea;
18.     }
19. };

复制代码

2. 思绪

通过双指针办理该问题。
left 和 right 分别指向数组的两端，maxArea 用于记载最大水量。
在while循环中不断计算当前容器水位水量并更新maxArea。每次 根据最短的线去移动指针。 末了返回maxArea。
3. 三数之和

   给你一个整数数组nums，判断是否存在三元组[nums, nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。
**注意：**答案中不可以包罗重复的三元组。

1. class Solution {
2. public:
3.     vector<vector<int>> threeSum(vector<int>& nums) {
4.         vector<vector<int>> result;
5.         int n = nums.size();
6.         if (n < 3) return result;
8.         sort(nums.begin(), nums.end());
10.         for (int i=0; i<n-2; i++) {
11.             // 跳过重复的元素
12.             if (i > 0 && nums[i] == nums[i - 1]) continue;
14.             int left = i+1, right = n-1;
15.             while (left < right) {
16.                 int sum = nums[i] + nums[left] + nums[right];
17.                 if (sum == 0) {
18.                     result.push_back({nums[i], nums[left], nums[right]});
19.                     // 跳过重复元素
20.                     // while (nums[left+1]==nums[left] && left<right) left++;
21.                     // while (nums[right-1]==nums[right] && left<right) right--;
22.                     while (left < right && nums[left] == nums[left + 1]) left++;
23.                     while (left < right && nums[right] == nums[right - 1]) right--;
24.                     left++;
25.                     right--;
26.                 } else if (sum > 0) { // 和>0，缩小right
27.                     right--;
28.                 } else {
29.                     left++; // 和<0，增大left
30.                 }
32.             }
34.         }
35.         return result;
37.     }
38. };

复制代码

3. 思绪

排序+双指针来实现
先对数组进行排序sort。排序后，三数之和问题会更容易处置处罚，由于如果我们遇到一个元素大于0，背面的元素就不大概和前面的元素加起来为0，所以可以提前停止一些不须要的计算。
再利用双指针，进行遍历。具体做法是，固定一个数 num ，作为三元组的一个元素，然后在剩下的数组中使用双指针遍历剩下部分。left 是指向当前 i 之后的第一个元素，即 left = i + 1。right 是指向数组的末了一个元素，即 right = n - 1。
4. 电话号码的字母组合 【回溯法】

   给定一个仅包罗数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按恣意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

1. class Solution {
2.     unordered_map<char, string> NumsToLetters = {   // 键值对
3.         {'2', "abc"},
4.         {'2', "abc"},
5.         {'3', "def"},
6.         {'4', "ghi"},
7.         {'5', "jkl"},
8.         {'6', "mno"},
9.         {'7', "pqrs"},
10.         {'8', "tuv"},
11.         {'9', "wxyz"},
12.     };
13. public:
14.     vector<string> letterCombinations(string digits) {
15.         vector<string> result;
16.         if (digits.empty()) return result;
18.         string current; // 储存当前
19.         backtrack(NumsToLetters, digits, current, 0, result);
20.         return result;
21.     }
23. private:
24.     void backtrack( unordered_map<char, string> NumsToLetters, string &digits, string &current , int index, vector<string>& result) {
25.         if (index == digits.size()) {   // 递归结束条件
26.             result.push_back(current);
27.             return;
28.         }
30.         char num = digits[index];
31.         const string letters = NumsToLetters.at(num);   // 获取键值
32.         for (char letter : letters) {
33.             current.push_back(letter);
34.             backtrack(NumsToLetters, digits, current, index + 1, result);
35.             current.pop_back();
36.         }
37.         
38.     }
39. };

复制代码

4. 思绪

首先要根据电话按键，将数组和对应的字符储存起来。
回溯函数

• 递归过程：从输入的数字 digits 的第1个数字 digits[0] 开始，遍历数字对应的每一个字符，添加到当前组合 current 中，并递归处置处罚下一个数字(index+1)。
  
• 返回条件：当当前的组合长度便是字符串长度，将当前符合要求的一个组合 current 并添加到结果 result 中。
  
• 回溯：在 for 循环中，末了调用pop_back()撤销当前选择，使用 current 去尝试其他大概。
  

例如在输入 “23” 时，for循环执行如下：

1. Start
2. for (char letter : letters) {
3.     current.push_back(letter);
4.     backtrack(NumsToLetters, digits, current, index + 1, result);
5.     current.pop_back();
6. }
8. ├─ Choose 'a' → "a" current = a
9. │  ├─ Choose 'd' → "ad" current = ad; ✅回溯 pop_back(d) -> current = "a"
10. │  ├─ Choose 'e' → "ae" current = ae; ✅回溯 pop_back(e) -> current = "a"
11. │  └─ Choose 'f' → "af"  current = af;  ✅回溯 pop_back(f) -> current = "a"
12. |   回溯 pop_back(a) -> current = "", 进行下一个循环
13. ├─ Choose 'b' → "b"
14. │  ├─ Choose 'd' → "bd"
15. │  ├─ Choose 'e' → "be"
16. │  └─ Choose 'f' → "bf"
17. └─ Choose 'c' → "c"
18.    ├─ Choose 'd' → "cd"
19.    ├─ Choose 'e' → "ce"
20.    └─ Choose 'f' → "cf"

复制代码

5. 删除链表的倒数第N个结点

   给你一个链表，删除链表的倒数第 n个结点，并且返回链表的头结点。

  方法一：计算链表长度

1. class Solution {
2.     public:
3.         int getLength(ListNode* head) {
4.             int length = 0;
5.             while (head) {
6.                 ++length;
7.                 head = head->next;
8.             }
9.             return length;
10.         }
11.    
12.         ListNode* removeNthFromEnd(ListNode* head, int n) {
13.             ListNode* dummy = new ListNode(0, head);
14.             int length = getLength(head);
15.             ListNode* cur = dummy;
16.             for (int i = 1; i < length - n + 1; ++i) {
17.                 cur = cur->next;
18.             }
19.             cur->next = cur->next->next;
20.             ListNode* ans = dummy->next;
21.             delete dummy;
22.             return ans;
23.         }
24. };

复制代码

方法二：双指针

1. class Solution {
2.     public:
3.    
4.         ListNode* removeNthFromEnd(ListNode* head, int n) {
5.             // 创建一个虚拟头节点，为方便删除头节点的情况
6.             ListNode* dummy = new ListNode(0, head);   
7.             ListNode* first = head;
8.             ListNode* second = dummy;
9.             // 移动first指针，让first与second相距n
10.             for (int i = 0; i<n; ++i) {
11.                 first = first->next;
12.             }
13.             while (first) {
14.                 first = first->next;
15.                 second = second->next;
16.             }
17.             // 删除second的下一个节点
18.             second->next = second->next->next;
19.             // ListNode* ret = dummy->next;
20.             // delete dummy;
21.             return dummy->next;
22.         }
23. };

复制代码

使用两个指针 first 和 second 同时对链表进行遍历。我们让 first 先走 n 步，然后 first 和 second 一起进步。直到 first 指向 nullptr。此时 second 就指向了倒数第 n 个节点的前一个节点。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。