Apri 14, 2024
C++语法复习
- string s
- 属性: s.size() = s.length()
- 索引: s[i]
- 遍历: for(int i=0;i<s.size();i++) or for(char ch: s) or for(auto ch: s)
- stack< char > stk
- 属性: stk.empty(), stk.top(), stk.pop(), stk.push(x)
- 方法: stk.pop() 不返回任何值
- 遍历: while(!stk.empty())
- unordered_map<char, char> pairs
- 定义: 哈希表存储快速查找
1
2
3
4
5
| unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
|
- 方法: pairs.count(ch) 检测是否存在给定键的元素
- 索引: pairs[ch]
- Reference
C++语法复习
解题思路
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
| class MinStack {
stack<int> x_stack;
stack<int> min_stack;
public:
MinStack() {
min_stack.push(INT_MAX);
}
void push(int x) {
x_stack.push(x);
min_stack.push(min(min_stack.top(), x));
}
void pop() {
x_stack.pop();
min_stack.pop();
}
int top() {
return x_stack.top();
}
int getMin() {
return min_stack.top();
}
};
|
C++语法复习
- string s
- 属性: string.size()
- 方法: s.substr(start, length) 提取子串
- 常用函数
- isdigit(x) 判断是否为数字
- isalpha(x) 判断是否为字母
- to_string(x) 转换为字符串
- stoi(x) 转换为整数
解题思路
压栈时记录当前字符串的长度，出栈计算当前字符串长度，两个长度相减就是需要拼接的子串长度。
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
| class Solution {
public:
string decodeString(string s) {
string ans;
stack<pair<int, int>> stk;
int count = 0;
for (auto x : s) {
if (isdigit(x))
count = 10 * count + (x - '0');
else if (x == '[') {
stk.push({count, ans.size()});
count = 0;
}
else if (isalpha(x))
ans += x;
else if (x == ']') {
int n = stk.top().first;
string str = ans.substr(stk.top().second, ans.size() - stk.top().second);
for (int i = 0; i < n - 1; i++) {
ans += str;
}
stk.pop();
}
}
return ans;
}
};
|
Apri 16, 2024
C++语法复习
- vector< int > t
- 属性: t.size()
- 函数：vector< int > next_day(n); 创建一个大小为 n 的 vector< int > 数组
解题思路
- 单调栈
- 栈中存储元素的下标，维持一个每日温度单调递减的栈
- 遍历数组，当遇到比栈顶元素大的元素时，栈顶元素出栈，并计算出当前元素与栈顶元素之间的距离
- 遍历完成后，栈中剩余的元素即为无法找到对应元素的下标，其对应的下一天位置为初始化的 0
- 参考 栈进阶数据结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> next_day(temperatures.size());
stack<int> stk;
stk.push(0);
for(int i=1;i<temperatures.size();i++){
while(!stk.empty() && temperatures[stk.top()] < temperatures[i]){
next_day[stk.top()] = i-stk.top();
stk.pop();
}
stk.push(i);
}
return next_day;
}
};
|
Apri 22, 2024
C++语法复习
- vector< int > t
- pair< int, int >
- make_pair(x, y)
解题思路
- 单调栈
- 栈中存储矩形<宽, 高>，维持一个高度递增的栈
- 遍历每一个矩形，若栈空或当前矩形高度高于栈顶矩形，直接进栈
- 若当前矩形高度小于栈顶矩形，则弹出栈顶矩形，累计其当前矩形厚度乘以其高度即为完全涵盖该矩形的最大矩形面积，直至栈空或当前矩形高度高于栈顶矩形；
- 参考 栈进阶数据结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int max_size = 0;
heights.push_back(0);
stack<pair<int, int>> rang;
for(int i=0;i<heights.size();i++){
int cnt = 0;
while(!rang.empty() && rang.top().second > heights[i]){
cnt += rang.top().first;
max_size = max(max_size, cnt * rang.top().second);
rang.pop();
}
max_size = max(max_size, (cnt + 1) * heights[i]);
rang.push(make_pair(cnt + 1, heights[i]));
}
return max_size;
}
};
|
Apri 23, 2024
C++语法复习
- 结构体获取元素：Ta = Ta->next;
- unordered_set<ListNode *> visited; 创建无序集合，哈希数组（学会运用）
- make_pair(x, y)
解题思路
- 暴力解法
- 遍历两个链表，计算出各自长度，然后再对其链表指针，同时遍历
- 哈希解法
- headA, headB地址为键值建立哈希数组，接下来检测是否存在该键值即可
- 双指针
- 利用两个指针分别遍历headA + headB，保证总遍历长度一致，将会找到最开始的公共节点
- 我的写法 —— 暴力解法
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
|
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *Ta = headA;
ListNode *Tb = headB;
int cnta = 0, cntb = 0;
while(Ta){
Ta = Ta->next;
cnta += 1;
}
while(Tb){
Tb = Tb->next;
cntb += 1;
}
if(cnta > cntb){
int temp = cnta-cntb;
while(temp--){
headA = headA->next;
}
}else if(cntb > cnta){
int temp = cntb-cnta;
while(temp--){
headB = headB->next;
}
}
while(headA && headB){
if(headA == headB) return headA;
headA = headA->next;
headB = headB->next;
}
return headA;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set<ListNode *> visited;
ListNode *temp = headA;
while (temp != nullptr) {
visited.insert(temp);
temp = temp->next;
}
temp = headB;
while (temp != nullptr) {
if (visited.count(temp)) {
return temp;
}
temp = temp->next;
}
return nullptr;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode *pA = headA, *pB = headB;
while (pA != pB) {
pA = pA == nullptr ? headB : pA->next;
pB = pB == nullptr ? headA : pB->next;
}
return pA;
}
};
|
Apri 30, 2024
解题思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* nhead = NULL;
while(head){
ListNode* temp = head->next;
head->next = nhead;
nhead = head;
head = temp;
}
return nhead;
}
};
|
解题思路
- 反转链表
- 先遍历链表获取链表长度 length
- 将前半部分链表进行反转，再与后半部分链表进行比对
- 复杂度分析
- 时间复杂度：O(2n) = O(n)
- 空间复杂度：O(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
29
30
31
32
33
34
35
36
37
38
|
class Solution {
public:
bool isPalindrome(ListNode* head) {
int length = 0;
ListNode* temp = head;
while(temp){
length++;
temp = temp->next;
}
int mid = length / 2, cnt = 0;
ListNode* nhead = NULL;
while(cnt < mid){
ListNode* temp = head->next;
head->next = nhead;
nhead = head;
head = temp;
cnt++;
}
if(length % 2) head = head->next;
while(nhead){
if(nhead->val != head->val) return false;
nhead = nhead->next;
head = head->next;
}
return true;
}
};
|
解题思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode *> visited;
while(head != NULL){
if(visited.count(head))
return true;
else{
visited.insert(head);
head = head->next;
}
}
return false;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
bool hasCycle(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return false;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (fast == nullptr || fast->next == nullptr) {
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};
|
解题思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode *> visited;
while(head != NULL){
if(visited.count(head))
return head;
else{
visited.insert(head);
head = head->next;
}
}
return NULL;
}
};
|
解题思路
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* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = nullptr, *tail = nullptr;
int carry = 0;
while (l1 || l2) {
int n1 = l1 ? l1->val: 0;
int n2 = l2 ? l2->val: 0;
int sum = n1 + n2 + carry;
if (!head) {
head = tail = new ListNode(sum % 10);
} else {
tail->next = new ListNode(sum % 10);
tail = tail->next;
}
carry = sum / 10;
if (l1) {
l1 = l1->next;
}
if (l2) {
l2 = l2->next;
}
}
if (carry > 0) {
tail->next = new ListNode(carry);
}
return head;
}
};
|
解题思路
- 模拟
- 获取链表长度，得到倒数第 n 个节点的前驱节点；
- 创建一个虚拟头节点，避免单个元素和两个元素的特异性；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* nhead = new ListNode(-1);
nhead->next = head;
ListNode* ptr = nhead;
int length = -1;
while(ptr != NULL){
ptr = ptr->next;
length++;
}
int pos = length - n;
ptr = nhead;
for(int i=0;i<pos;i++){
ptr = ptr->next;
}
ptr->next = ptr->next->next;
return nhead->next;
}
};
|
May 5, 2024
解题思路
- 维护三个指针，pprev 用于更新前一翻转过的小节的 next 指针指向下一小节翻转后的首个节点；
- prev 用于当前小节的首指针，after 用于当前小节的尾指针
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
|
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* pprev=NULL;
ListNode* prev=head;
if(head == NULL) return head;
ListNode* after=head->next;
while(after != NULL){
prev->next = after->next;
after->next = prev;
if(pprev == NULL){
head = pprev = after;
pprev = pprev->next;
}
else{
pprev->next = after;
pprev = pprev->next->next;
}
prev = prev->next;
if(prev == NULL) after = NULL;
else after = after->next->next->next;
}
return head;
}
};
|
May 8, 2024
解题思路
- 单组处理：每一组都是翻转链表，只需要获取子链表的头节点合尾节点即可；
- 组间连接：保留上一组的尾节点，然后进行串接；
- 辅助头节点：引入辅助头节点用于模拟前面以及处理完毕的子链表；
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
45
46
|
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if(head == NULL) return head;
ListNode* after=(ListNode*)malloc(sizeof(ListNode));
after->next = head;
head = after;
ListNode* first = after->next;
ListNode* second = after->next;
while(after != NULL){
ListNode* subhead = NULL;
second = first;
for(int i=0;i<k-1;i++){
if(second == NULL) break;
second = second->next;
}
if(second){
ListNode* nafter = first;
ListNode* tag = second->next;
do{
ListNode* temp = first->next;
first->next = subhead;
subhead = first;
first = temp;
}while(first != tag);
after->next = subhead;
after = nafter;
}else{
after->next = first;
break;
}
}
return head->next;
}
};
|
C++复习
- 字典：unordered_map< Node*, Node*>;
- 创建：new Node(val);
解题思路
- 哈希法：将原节点和新节点映射起来，然后根据原节点的random域获取新节点地址，进行串接；
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
|
class Solution {
public:
unordered_map<Node*, Node*> RanMap;
Node* copyRandomList(Node* head) {
if(head == NULL) return NULL;
Node* newhead = new Node(head->val);
Node* newptr = newhead;
Node* ptr = head;
while(ptr->next){
RanMap[ptr] = newptr;
newptr->next = new Node(0);
newptr = newptr->next;
ptr = ptr->next;
newptr->val = ptr->val;
}
RanMap[ptr] = newptr;
ptr = head, newptr = newhead;
while(ptr){
newptr->random = RanMap[ptr->random];
ptr = ptr->next;
newptr = newptr->next;
}
return newhead;
}
};
|
May 20, 2024
C++ 复习
- unordered_map< int, int > dmap;
- 寻找元素: dmap.find(key) 如果找到返回元素迭代器否则返回末尾迭代器
解题思路
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> dset;
for(int i=0;i<nums.size();i++){
if(dset.find(target-nums[i]) != dset.end()){
return {dset[target-nums[i]], i};
}
dset[nums[i]] = i;
}
return {};
}
};
|
C++复习
- for(string &s:strs) 创建迭代器
解题思路
解题思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.empty()) return 0;
vector<int> temp(nums.begin(), nums.end());
sort(temp.begin(), temp.end());
int ans = 0, last_val = temp[0], temp_len = 1;
for(int i=1;i<temp.size();i++){
if(temp[i] == last_val) continue;
else if(temp[i] == (last_val + 1)){
temp_len++;
last_val = temp[i];
}
else{
ans = max(ans, temp_len);
last_val = temp[i];
temp_len = 1;
}
}
return max(ans, temp_len);
}
};
|
May 22, 2024
解题思路
- 双指针
- Solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
void moveZeroes(vector<int>& nums) {
int pos1 = 0, pos2 = 0;
while(pos1 <= pos2 && pos2 != nums.size()){
if(nums[pos1] == 0 && nums[pos2] != 0){
swap(nums[pos1], nums[pos2]);
pos1++, pos2++;
}else{
if(nums[pos1] != 0 ) pos1++;
if(nums[pos2] == 0 || pos1 >= pos2) pos2++;
}
}
}
};
|
- Solution 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void swap(int* a,int*b)
{
int c = *a;
*a = *b, *b = c;
}
void moveZeroes(int* nums, int numsSize) {
int left = 0,right = 0;
while(right<numsSize)
{
if(nums[right])
{
swap(nums+right,nums+left);
left++;
}
right++;
}
}
|
