当前位置：网站首页>Sword finger offer punch stack queue heap
Sword finger offer punch stack queue heap
2022-07-18 05:57:00 【51CTO】
1、 Queues are implemented with two stacks
public
class
Solution {
public
static
void
main(
String[]
args) {
}
//in
Stack
<
Integer
>
stack1
=
new
Stack
<
Integer
>();
//out
Stack
<
Integer
>
stack2
=
new
Stack
<
Integer
>();
public
void
push(
int
node) {
stack1.
push(
node);
}
public
int
pop()
throws
Exception {
if (
stack2.
isEmpty())
while (
!
stack1.
isEmpty())
stack2.
push(
stack1.
pop());
if (
stack2.
isEmpty())
throw
new
Exception(
"queue is empty");
return
stack2.
pop();
}
}
class
CQueue {
// Power button
/**
* Use two stacks to implement a queue . The declaration of the queue is as follows , Please implement its two functions appendTail and deleteHead ,
* The functions of inserting integers at the end of the queue and deleting integers at the head of the queue are respectively completed .( If there are no elements in the queue ,deleteHead Operation return -1 )
*
* source ： Power button （LeetCode）
* link ：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
*/
Deque
<
Integer
>
stack3;
Deque
<
Integer
>
stack4;
public
CQueue() {
stack3
=
new
LinkedList
<
Integer
>();
stack4
=
new
LinkedList
<
Integer
>();
}
public
void
appendTail(
int
value) {
stack3.
push(
value);
}
public
int
deleteHead() {
// If the second stack is empty
if (
stack4.
isEmpty()) {
while (
!
stack3.
isEmpty()) {
stack4.
push(
stack3.
pop());
}
}
if (
stack4.
isEmpty()) {
return
-
1;
}
else {
int
deleteItem
=
stack4.
pop();
return
deleteItem;
}
}
}
- 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.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.
- 57.
- 58.
- 59.
2、 contain min Function of the stack
/**
* @author inke219223m
* <p>
* Implement a system that includes min() Function of the stack , This method returns the smallest value in the current stack .
* <p>
* <p>
* <p>
* Stack.peek()
* peek() Function returns the element at the top of the stack , But do not pop up the top element of the stack .
* Stack.pop()
* pop() Function returns the element at the top of the stack , And push the top element of the stack out of the stack .
*/
public
class
Solution {
public
static
void
main(
String[]
args) {
}
private
Stack
<
Integer
>
dataStack
=
new
Stack
<>();
private
Stack
<
Integer
>
minStack
=
new
Stack
<>();
public
void
push(
int
node) {
dataStack.
push(
node);
minStack.
push(
minStack.
empty()
?
node :
Math.
min(
minStack.
peek(),
node));
}
public
void
pop() {
dataStack.
pop();
minStack.
pop();
}
public
int
top() {
return
dataStack.
peek();
}
public
int
min() {
return
minStack.
peek();
}
}
// Power button
class
MinStack {
Stack
<
Integer
>
dataStack;
Stack
<
Integer
>
minStack;
/** initialize your data structure here. */
public
MinStack() {
dataStack
=
new
Stack
<>();
minStack
=
new
Stack
<>();
}
public
void
push(
int
x) {
dataStack.
push(
x);
minStack.
push(
minStack.
empty()
?
x :
Math.
min(
minStack.
peek(),
x));
}
public
void
pop() {
dataStack.
pop();
minStack.
pop();
}
public
int
top() {
return
dataStack.
peek();
}
public
int
min() {
return
minStack.
peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.min();
*/
- 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.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.
- 57.
- 58.
- 59.
- 60.
- 61.
- 62.
- 63.
- 64.
- 65.
- 66.
- 67.
- 68.
- 69.
- 70.
- 71.
- 72.
- 73.
- 74.
- 75.
- 76.
- 77.
- 78.
3、 The push in pop-up sequence of the stack
/**
* @author inke219223m
* <p>
* Stack.peek()
* peek() Function returns the element at the top of the stack , But do not pop up the top element of the stack .
* Stack.pop()
* pop() Function returns the element at the top of the stack , And push the top element of the stack out of the stack .
*/
public
class
Solution {
public
static
void
main(
String[]
args) {
}
/**
* Use a stack to simulate push pop operations . One element at a time , We need to determine whether the top of the stack element is the current stack sequence
* popSequence The first element of , If so, the stack operation is executed and popSequence Move one back , Continue to judge .
*
* @param pushA
* @param popA
* @return
*/
public
boolean
IsPopOrder(
int[]
pushA,
int[]
popA) {
int
n
=
pushA.
length;
Stack
<
Integer
>
stack
=
new
Stack
<>();
for (
int
pushIndex
=
0,
popIndex
=
0;
pushIndex
<
n;
pushIndex
++) {
stack.
push(
pushA[
pushIndex]);
while (
popIndex
<
n
&&
!
stack.
empty()
&&
stack.
peek()
==
popA[
popIndex]) {
stack.
pop();
popIndex
++;
}
}
return
stack.
isEmpty();
}
}
- 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.
4、 Median in data stream
/**
* @author inke219223m
* <p>
* Median in data stream
* <p>
* How to get the median in a data stream ？ If you read an odd number of values from the data stream , So the median is the number in the middle after all the numbers are sorted .
* If even numbers are read from the data stream , Then the median is the average of the middle two numbers after all the numbers are sorted .
* We use Insert() Method to read the data stream , Use GetMedian() Method to get the median of the currently read data .
*
* Stack.peek()
* peek() Function returns the element at the top of the stack , But do not pop up the top element of the stack .
* Stack.pop()
* pop() Function returns the element at the top of the stack , And push the top element of the stack out of the stack .
*/
public
class
Solution {
public
static
void
main(
String[]
args) {
}
// Big pile top , Store the left half of the element
private
PriorityQueue
<
Integer
>
left
=
new
PriorityQueue
<>((
o1,
o2)
->
o2
-
o1);
// Small cap pile , Store the right half of the element
// And the right half is bigger than the left half
private
PriorityQueue
<
Integer
>
right
=
new
PriorityQueue
<>();
// The number of elements read into the current data stream
private
int
N
=
0;
public
void
Insert(
Integer
val) {
// Insert to make sure that the two are in equilibrium
if (
N
%
2
==
0) {
/* N Insert into the right half if it's even .
* Because the right half is bigger than the left half , But the newly inserted element is not necessarily larger than the one from the left half ,
* So you need to insert the element in the left half first , Then use the left half for the characteristics of the large top reactor , Taking out the top element is the largest element , Now insert the right half
*/
left.
add(
val);
right.
add(
left.
poll());
}
else {
right.
add(
val);
left.
add(
right.
poll());
}
N
++;
}
public
Double
GetMedian() {
if (
N
%
2
==
0)
return (
left.
peek()
+
right.
peek())
/
2.0;
else
return (
double)
right.
peek();
}
}
- 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.
- 47.
- 48.
- 49.
5、 The smallest K Number
/**
* The smallest K Number
*/
public
class
Solution {
public
static
void
main(
String[]
args) {
System.
out.
println(
new
Solution().
GetLeastNumbers_Solution(
new
int[]{
1,
2,
5,
10,
11,
9},
3));
}
public
ArrayList
<
Integer
>
GetLeastNumbers_Solution(
int[]
input,
int
k) {
if (
k
>
input.
length
||
k
==
0) {
return
new
ArrayList
<>();
}
// Use... When initializing Lambda expression (o1, o2) -> o2 - o1 To achieve the big top
PriorityQueue
<
Integer
>
priorityQueue
=
new
PriorityQueue
<>((
o1,
o2)
->
o2
-
o1);
for (
int
num :
input) {
priorityQueue.
add(
num);
if (
priorityQueue.
size()
>
k) {
priorityQueue.
poll();
}
}
return
new
ArrayList
<>(
priorityQueue);
}
public
int[]
getLeastNumbers(
int[]
arr,
int
k) {
if (
k
>
arr.
length
||
k
==
0) {
return
new
int[]{};
}
// Use... When initializing Lambda expression (o1, o2) -> o2 - o1 To achieve the big top
PriorityQueue
<
Integer
>
priorityQueue
=
new
PriorityQueue
<>((
o1,
o2)
->
o2
-
o1);
for (
int
num :
arr) {
priorityQueue.
add(
num);
if (
priorityQueue.
size()
>
k) {
priorityQueue.
poll();
}
}
return
priorityQueue.
stream().
mapToInt(
Integer::
valueOf).
toArray();
}
}
- 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.
6、 Maximum sliding window
public
class
Solution {
public
static
void
main(
String[]
args) {
System.
out.
println(
new
Solution().
maxInWindows(
new
int[]{
1,
2,
5,
9},
3));
}
public
ArrayList
<
Integer
>
maxInWindows(
int []
num,
int
size) {
ArrayList
<
Integer
>
ret
=
new
ArrayList
<>();
if(
size
>
num.
length
||
size
<
1) {
return
new
ArrayList
<>();
}
// Big pile top
PriorityQueue
<
Integer
>
priorityQueue
=
new
PriorityQueue
<>((
o1,
o2)
->
o2
-
o1);
// Maintain a size of size Big top pile of
for (
int
i
=
0;
i
<
size;
i
++) {
priorityQueue.
add(
num[
i]);
}
ret.
add(
priorityQueue.
peek());
for (
int
i
=
0,
j
=
i
+
size;
j
<
num.
length;
i
++,
j
++) {
priorityQueue.
remove(
num[
i]);
priorityQueue.
add(
num[
j]);
ret.
add(
priorityQueue.
peek());
}
return
ret;
}
}
- 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.
7、 The first character in a character stream that does not repeat
public
class
Solution {
public
static
void
main(
String[]
args) {
Solution
solution
=
new
Solution();
String
str
=
"aancbd";
for(
int
i
=
0;
i
<
str.
length();
i
++) {
solution.
Insert(
str.
charAt(
i));
System.
out.
print(
solution.
FirstAppearingOnce());
}
}
private
int[]
cnts
=
new
int[
128];
private
Queue
<
Character
>
queue
=
new
LinkedList
<>();
//Insert one char from stringstream
public
void
Insert(
char
ch) {
cnts[
ch]
++;
queue.
add(
ch);
// Non empty && The number is larger than 1
// Then remove it
while (
!
queue.
isEmpty()
&&
cnts[
queue.
peek()]
>
1) {
queue.
poll();
}
}
//return the first appearence once char in current stringstream
public
char
FirstAppearingOnce() {
return
queue.
isEmpty()
?
'#' :
queue.
peek();
}
}
- 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.
Code warehouse ：https://gitee.com/codingce/codingce-leetcode
边栏推荐
- 让企业数字化砸锅和IT主管背锅的软件供应链安全风险指北
- Method of marking disk partition as active and method of canceling marking disk partition as active
- Interpolation method to calculate the value between two points
- The software supply chain security risk that makes enterprise digitalization and it executives bear the brunt of the cauldron points to the north
- QDU暑假训练 ---- 热身赛
- 论文精读： 深度强化学习与智慧交通(一）
- Dialogue Yinqi: what we insist on will not change, and broad vision will jump out of the "cyclical law" of enterprise scientific research
- 中国人力资源数字化生态图谱-灵活用工市场
- Live delivery system source code
- [dynamic planning] - state compression DP
猜你喜欢
CEO干货| CSDN演讲回顾：如何利用低代码提升研发和IT效能？
Dialogue Yinqi: what we insist on will not change, and broad vision will jump out of the "cyclical law" of enterprise scientific research
Foundation of deep learning: 9 Reproduce classic networks: lenet5 and alexnet
Apache apisik meetup Nanjing station! See you at 7.30!
工程监测仪器多通道振弦无线采集仪的采集数据发送方式和在线监测管理系统
宝藏功能上新！日历视图+卡片视图强强联合，工作效率快到飞起
要想不踩SaaS那些坑，得先了解“SaaS架构”
让企业数字化砸锅和IT主管背锅的软件供应链安全风险指北
CAS compare and swap exchange after comparison
数据库每日一题---第23天：游戏玩法分析 l
随机推荐
剑指 Offer打卡 栈队列堆
Create a 12g logical volume with one disk and three 5g partitions
【7.8-7.15】寫作社區精彩技術博文回顧
JMM memory model
Fail-Fast ＆ Fail-Safe
深度学习基础：9.复现经典网络：LeNet5与AlexNet
要想不踩SaaS那些坑，得先了解“SaaS架构”
Trigger creation, deletion and other operations
Send your code into space and develop "the greatest work" with Huawei cloud
Teach people to fish - see a field on the sap mm material display interface, how to find which field of which database table to store the trial version
摄提格，是外来词音译，还是有特定含义？
Volatile low configuration syn, realizing visibility and order
浏览器缓存机制详解
CAS compare and swap exchange after comparison
哈工大讯飞联合实验室获得SemEval-2022最佳论文提名奖
About security details timing attack
理财平台选择哪个安全可靠
【动态规划】—— 数位统计DP
Beihang & Institute of Information Technology & meituan proposed lbdt, which is based on spatiotemporal interaction of language bridging to accurately segment directional video objects, with performan
梅科尔工作室-李庆浩 sql语句笔记