全球快看点丨链表栈队列递归哈希表有序表

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

全球快看点丨链表栈队列递归哈希表有序表

2023-01-11 18:06:15 来源：博客园

链表

单链表

单链表的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 {public Node head;public Node tail;//双向链表头部插入节点public void addFromHead(T value) {Node cur = new Node(value);if (head == null) {head = cur;tail = cur;} else {cur.next = head;head.last = cur;head = cur;}}//双向链表尾部插入节点public void addFromBottom(T value) {Node cur = new Node(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 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 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 {private DoubleEndsQueue queue;public MyStack() {queue = new DoubleEndsQueue();}    //入栈 在双向链表头部插入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 stackData;   private Stack stackMin;   public MyStack1() {      this.stackData = new Stack();      this.stackMin = new Stack();   }   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 {public Queue queue;public Queue 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 tmp = queue;queue = help;help = tmp;return ans;}public T peek() {while (queue.size() > 1) {help.offer(queue.poll());}T ans = queue.peek();Queue tmp = queue;queue = help;help = tmp;help.offer(ans);return ans;}public boolean isEmpty() {return queue.isEmpty();}}

队列

队列的原理就是先进先出，就像在食堂打饭排队一样。

双向链表实现队列：

public static class DoubleEndsQueue {public Node head;public Node tail;public void addFromHead(T value) {Node cur = new Node(value);if (head == null) {head = cur;tail = cur;} else {cur.next = head;head.last = cur;head = cur;}}public void addFromBottom(T value) {Node cur = new Node(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 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 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 {private DoubleEndsQueue queue;public MyQueue() {queue = new DoubleEndsQueue();}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 stackPush;public Stack stackPop;public TwoStacksQueue() {stackPush = new Stack();stackPop = new Stack();}// 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 casereturn arr[L];}//  L..mid  mid+1...R// int mid = (L+R)/2int 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)不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度

关键词：双向链表可以使用时间复杂度