链表栈队列递归哈希表有序表
2023-04-18 15:19:56 时间
链表
单链表
单链表的Java实现：
public static class Node {
public int value;
public Node next;
public Node(int data) {
value = data;
}
}
单链表反转：
public static Node reverseLinkedList(Node head){
Node pre = null;
Node next = null;
while(head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
删除单链表的某个数：
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public static Node removeValue(Node head, int num){
//确定头节点 ，如果头节点不是num，直接跳出，如果是，头节点往下走
while(head != null){
if(head.value != num){
break;
}
head = head.next;
}
Node pre = head;
Node cur = head;
while(cur != null){
if(cur.value == num){
pre.next = cur.next
}else{
pre = cur
}
cur = cur.next
}
return head
}
双向链表
双向链表Java实现：
public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
value = data;
}
}
双向链表反转：
public static DoubleNode reverseDoubleList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
while(head != null){
next = head.next;
head.next = pre;
head.last = next;
pre = head;
head = next;
}
}
栈
栈的原理很简单，就是先进后出，类似弹夹。但是实现方式很多。
双向链表实现栈：
public static class DoubleEndsQueue<T> {
public Node<T> head;
public Node<T> tail;
//双向链表头部插入节点
public void addFromHead(T value) {
Node<T> cur = new Node<T>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.next = head;
head.last = cur;
head = cur;
}
}
//双向链表尾部插入节点
public void addFromBottom(T value) {
Node<T> cur = new Node<T>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.last = tail;
tail.next = cur;
tail = cur;
}
}
//双向链表头部弹出节点
public T popFromHead() {
if (head == null) {
return null;
}
Node<T> cur = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
cur.next = null;
head.last = null;
}
return cur.value;
}
//双向链表尾部弹出节点
public T popFromBottom() {
if (head == null) {
return null;
}
Node<T> cur = tail;
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.last;
tail.next = null;
cur.last = null;
}
return cur.value;
}
public boolean isEmpty() {
return head == null;
}
}
//栈
public static class MyStack<T> {
private DoubleEndsQueue<T> queue;
public MyStack() {
queue = new DoubleEndsQueue<T>();
}
//入栈 在双向链表头部插入
public void push(T value) {
queue.addFromHead(value);
}
//出栈 在双向链表头部删除并返回
public T pop() {
return queue.popFromHead();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
面试题 数组实现栈：
public static class MyStatic{
private int[] arr ;
private int pull ;
private int poli ;
private int size ;
private int limit ;
public MyStatic(int l){
arr = new int[l];
pull = 0;
poli = 0;
size = 0;
limit = l ;
}
public void pull(int value ){
if(size == limit ){
throw new RuntimeException("栈满了，不能再加了");
}
arr[pull] = value;
poli = pull;
pull = pullIndex(pull);
}
public int pop(){
if(size == 0){
throw new RuntimeException("栈空了");
}
int res = arr[poli];
poli = pollIndex(poli);
return res;
}
public int pullIndex(int i ){
return i < limit -1 ? i+1 : 0;
}
public int pollIndex(int i){
return i > 0 ? i-1 : limit -1;
}
}
要求用系统栈实现取出栈最小值的方法，要求时间复杂度O（1）：
需要用两个栈实现，如果最小栈为空，数据栈入栈则最小栈入栈，如果数据栈入栈值大于最小栈栈顶，最小栈不入栈。数据栈出栈，数据栈值==最小栈 最小栈出栈。
public static class MyStack1 {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MyStack1() {
this.stackData = new Stack<Integer>();
this.stackMin = new Stack<Integer>();
}
public void push(int newNum) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if (newNum <= this.getmin()) {
this.stackMin.push(newNum);
}
this.stackData.push(newNum);
}
public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
int value = this.stackData.pop();
if (value == this.getmin()) {
this.stackMin.pop();
}
return value;
}
public int getmin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
return this.stackMin.peek();
}
}
双队列实现栈：两个队列互相转换
public static class TwoQueueStack<T> {
public Queue<T> queue;
public Queue<T> help;
public TwoQueueStack() {
queue = new LinkedList<>();
help = new LinkedList<>();
}
public void push(T value) {
queue.offer(value);
}
public T poll() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.poll();
Queue<T> tmp = queue;
queue = help;
help = tmp;
return ans;
}
public T peek() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.peek();
Queue<T> tmp = queue;
queue = help;
help = tmp;
help.offer(ans);
return ans;
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
队列
队列的原理就是先进先出，就像在食堂打饭排队一样。
双向链表实现队列：
public static class DoubleEndsQueue<T> {
public Node<T> head;
public Node<T> tail;
public void addFromHead(T value) {
Node<T> cur = new Node<T>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.next = head;
head.last = cur;
head = cur;
}
}
public void addFromBottom(T value) {
Node<T> cur = new Node<T>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.last = tail;
tail.next = cur;
tail = cur;
}
}
public T popFromHead() {
if (head == null) {
return null;
}
Node<T> cur = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
cur.next = null;
head.last = null;
}
return cur.value;
}
public T popFromBottom() {
if (head == null) {
return null;
}
Node<T> cur = tail;
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.last;
tail.next = null;
cur.last = null;
}
return cur.value;
}
public boolean isEmpty() {
return head == null;
}
}
public static class MyQueue<T> {
private DoubleEndsQueue<T> queue;
public MyQueue() {
queue = new DoubleEndsQueue<T>();
}
public void push(T value) {
queue.addFromHead(value);
}
public T poll() {
return queue.popFromBottom();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
面试题 数组实现队列：
public static class MyQueue {
private int[] arr;
private int pushi;
private int polli;
private int size;
private final int limit;
public MyQueue(int l) {
arr = new int[l];
pushi = 0;
polli = 0;
size = 0;
limit = l;
}
public void push(int value) {
if (size == limit) {
throw new RuntimeException("栈满了，不能再加了");
}
size++;
arr[pushi] = value;
pushi = nextIndex(pushi);
}
public int pop() {
if (size == 0) {
throw new RuntimeException("栈空了，不能再拿了");
}
size--;
int ans = arr[polli];
polli = nextIndex(pushi);
return ans;
}
public boolean isEmpty() {
return size == 0;
}
private int nextIndex(int i) {
return i < limit - 1 ? i + 1 : 0;
}
}
面试题 用栈实现队列
public static class TwoStacksQueue {
public Stack<Integer> stackPush;
public Stack<Integer> stackPop;
public TwoStacksQueue() {
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}
// push栈向pop栈倒入数据
private void pushToPop() {
if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
}
public void add(int pushInt) {
stackPush.push(pushInt);
pushToPop();
}
public int poll() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.pop();
}
public int peek() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.peek();
}
}
递归
从思想上理解递归，可以把一个大事件分成若干个小事件，然后通过判断，完成大事件。
递归的底层是利用系统栈实现的。任何递归方法都可以改成非递归。
题目：递归求数组L，R上的最大值。
public static int process(int[] arr, int L, int R) {
if (L == R) { // arr[L..R]范围上只有一个数，直接返回，base case
return arr[L];
}
// L..mid mid+1...R
// int mid = (L+R)/2
int mid = L + ((R - L) >> 1); // 中点
int leftMax = process(arr, L, mid);
int rightMax = process(arr, mid + 1, R);
return Math.max(leftMax, rightMax);
}
时间复杂度可以通过Master公式来计算
T(N) = a * T(N/b) + O(N^d)(其中的a、b、d都是常数)
的递归函数，可以直接通过Master公式来确定时间复杂度
如果 log(b,a) < d，复杂度为O(N^d)
如果 log(b,a) > d，复杂度为O(N^log(b,a))
如果 log(b,a) == d，复杂度为O(N^d * logN)
哈希表
1)哈希表在使用层面上可以理解为一种集合结构
2)如果只有key，没有伴随数据value，可以使用HashSet结构
3)如果既有key，又有伴随数据value，可以使用HashMap结构
4)有无伴随数据，是HashMap和HashSet唯一的区别，实际结构是一回事
5)使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为 O(1)，但是常数时间比较大
6)放入哈希表的东西，如果是基础类型，内部按值传递，内存占用是这个东西的大小
7)放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是8字节
有序表
1)有序表在使用层面上可以理解为一种集合结构
2)如果只有key，没有伴随数据value，可以使用TreeSet结构
3)如果既有key，又有伴随数据value，可以使用TreeMap结构
4)有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事
5)有序表把key按照顺序组织起来，而哈希表完全不组织
6)红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同
7)放入如果是基础类型，内部按值传递，内存占用就是这个东西的大小
8)放入如果不是基础类型，内部按引用传递，内存占用是8字节
9)不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度
相关文章
- 直接在代码里面对list集合进行分页
- .NET Framework 4.5新特性详解
- 大数据的简要介绍
- 大数据的由来
- 高斯混合模型的自然梯度变量推理
- timing-wheel 仿Kafka实现的时间轮算法
- 使用Navicat软件连接自建数据库（Linux系统）
- 那一天，我被Redis主从架构支配的恐惧
- Redis 深入了解键的过期时间
- C#使用委托调用实现用户端等待闪屏
- 基于流计算 Oceanus 和 Elasticsearch Service 构建百亿级实时监控系统
- GRAND | 转录调控网络预测数据库
- JFreeChart API中文文档
- 临床相关突变查询数据库
- TIGER | 人类胰岛基因变化查询数据库
- 视频边缘计算网关EasyNVR在视频整体监控解决方案中的应用分析
- Apache Arrow - 大数据在数据湖后的下一个风向标
- 常见的电商数据指标体系
- AKShare-艺人数据-艺人流量价值
- MySQL中多表联合查询与子查询的这些区别，你可能不知道！