唉,很久没做做题了.这里记录一下每天刷题练习.
主要刷一些简单中等题,难了我也不会.
剑指Offer 启动
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
40package 用两个栈实现队列;
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
43class 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
13class 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
22class 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 | /** |
使用递归方法1
2
3
4
5
6
7
8
9
10
11
12class 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
22
23
24
25class 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;
}
};