1.链表结构

class Node {
public int value;
public Node next;
public Node(int data) {
value = data;
}
}

class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
value = data;
}
}

1）单链表和双链表如何反转

2）把给定值都删除

// 反转单链表
Node pre = null;
Node next = null;
}
return pre;
}
// 反转双向链表
public static DoubleNode reverseDoubleList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
}
return pre;
}
// 删除单链表元素
public static Node removeValue(Node head, int num) {
// 跳过链表头部值为num的部分
break;
}
}
// 头节点为第一个值不为num的节点
while (cur != null) {
// pre始终保持其值不等于num
if (num == cur.value) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
}
// 删除双向链表元素
public static DoubleNode removeValue(DoubleNode head, int num) {
// 跳过头节点
break;
}
}
}
while (cur != null) {
if (cur.value == num) {
pre.next = cur.next;
cur.last = null;
} else {
pre = cur;
}
cur = cur.next;
}
}

Java和C++在垃圾回收方面存在区别：

C++ 内存泄漏是因为声明的变量忘记释放，必须手动调用函数释放。

2.栈和队列

（1）基于双向链表

package structure02;
/**
* @author Corley
* @date 2021/10/7 14:02
* @description LeetCodeAlgorithmZuo-structure02
*/
/*
自定义节点
*/
static class Node<T> {
public Node<T> last;
public Node<T> next;
public T value;
public Node(T value) {
this.value = value;
}
}
/*
自定义双向链表
*/
public Node<T> tail;
Node<T> cur = new Node<>(value);
tail = cur;
} else {
}
}
Node<T> cur = new Node<>(value);
tail = null;
} else {
cur.last = tail;
tail.next = cur;
tail = cur;
}
}
return null;
}
tail = null;
} else {
}
return res;
}
public T popFromBottom() {
return null;
}
T res = tail.value;
tail = null;
} else {
tail = tail.last;
tail.next = null;
}
return res;
}
public boolean isEmpty() {
}
}
/*
自定义栈
*/
static class Stack<T> {
public Stack() {
}
public void push(T value) {
}
public T pop() {
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
/*
自定义队列
*/
static class Queue<T> {
public Queue() {
}
public void push(T value) {
}
public T pop() {
return queue.popFromBottom();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
}


（2）基于数组

package structure02;
/**
* @author Corley
* @date 2021/10/7 14:50
* @description LeetCodeAlgorithmZuo-structure02
* 使用环形数组RingBuffer的思想实现队列
*/
public class ArrayQueueStack {
static class Queue {
private final int[] arr;
private int pushi;          // 加元素的下标
private int pulli;          // 取元素的下标
private int size;
private final int limit;    // 队列大小
public Queue(int limit) {
arr = new int[limit];
pushi = 0;
pulli = 0;
size = 0;
this.limit = limit;
}
public void push(int num) {
if (size == limit) {
throw new RuntimeException("队列已满，不能再添加元素！");
}
size++;
arr[pushi] = num;
pushi = nextIndex(pushi);
}
public int pull() {
if (isEmpty()) {
throw new RuntimeException("队列已空，不能再取元素！");
}
size--;
int res = arr[pulli];
pulli = nextIndex(pulli);
return res;
}
public boolean isEmpty() {
return 0 == size;
}
private int nextIndex(int index) {
return index < (limit - 1) ? (index + 1) : 0;
}
}
class Stack {
int[] arr;
int size;
int limit;
public Stack(int limit) {
arr = new int[limit];
this.limit = limit;
size = 0;
}
public void push(int num) {
if (size == limit) {
throw new RuntimeException("栈已满，不能再添加元素！");
}
arr[size++] = num;
}
public int pop() {
if (0 == size) {
throw new RuntimeException("栈已空，不能再取元素！");
}
return arr[--size];
}
}
}


1）算法问题无关语言；

2）语言提供的API是有限的，当有新的功能是API不提供的就需要改写；

3）任何软件工具的底层都是最基本的算法和数据结构，这是绕不过去的。

1)pop: push、getMin操作的时间复杂度都是O(1)；

2)设计的栈类型可以使用现成的栈结构。

static class MinStack1 {
private final Stack<Integer> stackData;
private final Stack<Integer> stackMin;
public MinStack1() {
this.stackData = new Stack<>();
this.stackMin = new Stack<>();
}
public void push(int num) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(num);
} else if (num < this.stackMin.peek()) {
this.stackMin.push(num);
} else {
this.stackMin.push(this.stackMin.peek());
}
this.stackData.push(num);
}
public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty!");
}
stackMin.pop();
return stackData.pop();
}
public int getMin() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty!");
}
return  stackMin.peek();
}
}

static class MinStack2 {
private final Stack<Integer> stackData;
private final Stack<Integer> stackMin;
public MinStack2() {
this.stackData = new Stack<>();
this.stackMin = new Stack<>();
}
public void push(int num) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(num);
} else if (num <= this.stackMin.peek()) {
this.stackMin.push(num);
}
this.stackData.push(num);
}
public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty!");
}
int res = stackData.pop();
if (res == getMin()) {
stackMin.pop();
}
return res;
}
public int getMin() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty!");
}
return  stackMin.peek();
}
}

1)如何用栈结构实现队列结构；

2)如何用队列结构实现栈结构。

static class TwoQueueStack<T> {
private Queue<T> queue;
private Queue<T> help;
public TwoQueueStack() {
}
public void push(T value) {
queue.offer(value);
}
public T pop() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T res = queue.poll();
Queue<T> tmp = queue;
queue = help;
help = tmp;
return res;
}
public T peek() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T res = queue.poll();
help.offer(res);
Queue<T> tmp = queue;
queue = help;
help = tmp;
return res;
}
public boolean isEmpty() {
return queue.isEmpty();
}
}

|
3天前
|

13 1
|
2天前
|
Python
Python实现数据结构（如：链表、栈、队列等）。
Python实现数据结构（如：链表、栈、队列等）。
17 0
|
3天前
|

【数据结构与算法】7、队列（Queue）的实现【用栈实现队列】
【数据结构与算法】7、队列（Queue）的实现【用栈实现队列】
23 0
|
3天前
|

【数据结构与算法】6、栈（Stack）的实现、LeetCode：有效的括号
【数据结构与算法】6、栈（Stack）的实现、LeetCode：有效的括号
13 0
|
3天前
|

【数据结构与算法】1、学习动态数组数据结构（基本模拟实现 Java 的 ArrayList 实现增删改查）
【数据结构与算法】1、学习动态数组数据结构（基本模拟实现 Java 的 ArrayList 实现增删改查）
34 0
|
5天前
|

【数据结构查找算法篇】----散列查找【实战项目】
【数据结构查找算法篇】----散列查找【实战项目】
34 10
|
5天前
|

【数据结构查找算法篇】----二分查找【实战项目】
【数据结构查找算法篇】----二分查找【实战项目】
14 1
|
5天前
|

【数据结构查找算法篇】----线性查找【实战项目】
【数据结构查找算法篇】----线性查找【实战项目】
21 5
|
5天前
|

【数据结构排序算法篇】----对十大经典算法的总结
【数据结构排序算法篇】----对十大经典算法的总结
17 0
|
2天前
|

【MATLAB】语音信号识别与处理：SG滤波算法去噪及谱相减算法呈现频谱
【MATLAB】语音信号识别与处理：SG滤波算法去噪及谱相减算法呈现频谱
11 1

• 云迁移中心

更多

更多

更多