leetcode刷题记录

唉,很久没做做题了.这里记录一下每天刷题练习.

主要刷一些简单中等题,难了我也不会.

剑指Offer 启动

image-20221226173618143

09.用两个栈实现队列

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
package 用两个栈实现队列;

import java.util.ArrayDeque;
import java.util.Deque;

public class CQueue2 {

Deque<Integer> inStack;
Deque<Integer> outStack;

public CQueue2() {
inStack = new ArrayDeque<>();
outStack = new ArrayDeque<>();

}

public void appendTail(int value) {
inStack.push(value);
}

public int deleteHead() {
if(outStack.isEmpty())
{
if(inStack.isEmpty())
{
return -1;
}
else
{
while(!inStack.isEmpty())
{
outStack.push(inStack.pop());
}
return outStack.pop();
}
}
return outStack.pop();
}
}

设计一个有getMin功能的栈

1
实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。

【要求】

1.pop、push、getMin 操作的时间复杂度都是 O(1)。 2.设计的栈类型可以使用现成的栈结构

设计方案

使用辅助栈,多一个存最小值的栈stackmin. 即有stackdata和stackmin

第一种

压入规则

压入数据时,stackdata直接压入;stackmin如果为空,直接压入,如果不为空,进行比较:将要压入的值和栈顶的值进行比较,如果栈顶值更小则不处理,否则压入.

弹出规则

stackdata弹出数据,将弹出的数据与stackmin顶数据比较,如果弹出数据等于stackmin栈顶数据,则同时弹出stackmin数据,否则不处理.

最小值即位stackmin中栈顶值

第二种

压入规则

压入数据时,stackdata直接压入;stackmin如果为空也直接压入,否则将栈顶数据与待压入数据比较,如果栈顶数据更小,则stackmin再压入一次栈顶数据,否则stackmin压入待压入数据.

弹出规则

两个栈都弹出

最小值也是stackmin的栈顶

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
class MinStack {
public:
stack<int>s,min_s;

MinStack() {

}

void push(int val) {
if(s.empty())
{
s.emplace(val);
min_s.emplace(val);
}
else
{
int topvalue = min_s.top();
if(topvalue>val)
{
min_s.emplace(val);
}
else{
min_s.emplace(topvalue);
}
s.emplace(val);
}
}

void pop() {
s.pop();
min_s.pop();
}

int top() {
return s.top();

}

int min() {
return min_s.top();
}
};

从尾到头打印链表

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)

设计方案

利用栈结构或者使用递归

这里使用递归

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
vector<int> reversePrint(ListNode* head) {

if(!head)
{
return {};
}
vector<int> v =reversePrint(head->next);
v.push_back(head->val);
return v;
}
}

使用辅助栈结构

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:
vector<int> reversePrint(ListNode* head) {
stack<int> s;

for(ptr it=head;it!=nullptr;it=it->next)
{
s.push(it->val);
}

vector<int> v;
while(!s.empty())
{
int val = s.top();
s.pop();
v.push_back(val);
}
return v;


}
};

反转链表

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

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
22
23
24
25
26
27
28
29
30
31
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
ListNode(int x):val(x),next(NULL){}
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
typedef ListNode* LN;
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head)
{
return nullptr;
}
LN nd = head->next;
LN pre = head;
pre->next = nullptr;
for(LN it = nd;it!=nullptr;)
{
nd = it->next;
it->next = pre;
pre = it;
it = nd;

}
return pre;
}
};

使用递归方法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};

复杂链表的复制

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null

解题思路

  1. 回溯和哈希表(或者单独使用哈希表)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution
{
public:
unordered_map<Node *, Node *> cachedNode;
Node *copyRandomList(Node *head)
{
if (!head)
{
return nullptr;
}
if (!cachedNode.count(head))
{
cachedNode[head] = new Node(head->val);
cachedNode[head]->next = copyRandomList(head->next);
cachedNode[head]->random = copyRandomList(head->random);
}

return cachedNode[head];
}
};
  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
    class Solution {
    public:
    Node* copyRandomList(Node* head) {
    if (head == nullptr) {
    return nullptr;
    }
    for (Node* node = head; node != nullptr; node = node->next->next) {
    Node* nodeNew = new Node(node->val);
    nodeNew->next = node->next;
    node->next = nodeNew;
    }
    for (Node* node = head; node != nullptr; node = node->next->next) {
    Node* nodeNew = node->next;
    nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
    }
    Node* headNew = head->next;
    for (Node* node = head; node != nullptr; node = node->next) {
    Node* nodeNew = node->next;
    node->next = node->next->next;
    nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
    }
    return headNew;
    }
    };

-------------本文结束感谢您的阅读-------------
感谢阅读.

欢迎关注我的其它发布渠道