难度困难
请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
示例 1:
1
2
3
4
5
| 输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
|
示例 2:
1
2
3
4
5
| 输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
|
示例 3:
1
2
3
4
5
| 输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
|
示例 4:
1
2
3
4
5
| 输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
|
示例 5:
1
2
3
4
| 输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
|
s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。
想不出来是动态规划。。看了一下题解才知道，然后把自己的理解写一下：
用dp[i][j] = true/false 来表示s[:i]和p[:j]是否匹配。所以最后只要返回右下角的元素就可以了。
且dp[i][j]对应添加的字符是s[i-1]和p[j-1]。
给出转移方程：
根据p[j-1]是否为*，分两种情况讨论：
p[j-1]是*时：
dp[i][j-2] dp[i][j-1],前两种是p[j-2]出现0次或者1次。dp[i-1][j]并且s[i-1] == p[j-2]dp[i-1][j]并且p[j-2]=='.',后两种情况都是p[j-2]多出现一次。
p[j-1]不是*:
dp[i-1][j-1]并且s[i-1] == p[j-1]dp[i-1][j-1]并且p[j-1] = '.'
还要注意矩阵的初始化：
dp[0][0]是true，空串匹配空串，特殊的还有矩阵的第一行，s串为空的情况，只看p的偶数位，全为*时才能匹配dp[0][j] = dp[0][j-2] && p[j-1] == *。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size() + 1;
int n = p.size() + 1;
vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
dp[0][0] = true;
for(int j = 2; j < n; j += 2)
{
dp[0][j] = dp[0][j-2] && p[j-1] == '*';
}
for(int i = 1; i < m; ++i)
{
for(int j = 1; j < n; ++j)
{
if(p[j - 1] == '*')
{
dp[i][j] = dp[i][j-2] || dp[i][j-1] || (dp[i-1][j] && s[i - 1] == p[j - 2]) || (dp[i-1][j] && p[j-2] == '.');
}
else
{
dp[i][j] = (dp[i-1][j-1] && s[i-1]==p[j-1]) || (dp[i-1][j-1] && p[j-1] == '.');
}
}
}
return dp[m-1][n-1];
}
};
|
难度中等
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123”都表示数值，但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。
确定有限状态自动机
难度简单64
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
1
2
3
| 输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
|
提示：
1 <= nums.length <= 500001 <= nums[i] <= 10000
双指针，一个指针指向头，一个指向尾，从前往后找偶数，从后往前找奇数，找到就交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int i = 0, n = nums.size() - 1, j = n;
while(i < j)
{
while(i < j && nums[i] & 1) ++i;
while(i < j && !(nums[j] & 1)) --j;
swap(nums[i], nums[j]);
}
return nums;
}
};
|
难度简单113
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
示例：
1
2
3
| 给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
|
快慢指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode* res = head;
ListNode* cur = head;
if(head == nullptr) return head;
while(k > 0)
{
if(cur == nullptr) return nullptr;
cur = cur->next;
--k;
}
while(cur != nullptr)
{
res = res->next;
cur = cur->next;
}
return res;
}
};
|
难度简单142
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
1
2
| 输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
|
我还在写头插。。原来直接改指针指向啊。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *cur = head, *pre = nullptr;
while(cur != nullptr) {
ListNode* tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};
|
难度简单66
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
1
2
| 输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
|
做过好多次了。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr) return l2;
if(l2 == nullptr) return l1;
ListNode* res;
if(l1->val < l2->val)
{
res = l1;
l1 = l1->next;
}
else
{
res = l2;
l2 = l2->next;
}
ListNode* cur = res;
while(l1 && l2)
{
if(l1->val < l2->val)
{
cur->next = l1;
l1 = l1->next;
}
else
{
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if(l1) cur->next = l1;
if(l2) cur->next = l2;
return res;
}
};
|
