【算法数据结构体系篇class03】：数组、链表、栈、队列、递归时间复杂度、哈希表、有序表问题

一、反转链表

package class03;import java.util.ArrayList;
import java.util.List;/*** 链表反转*/
public class ReverseLinkedList {public static class Node {public int value;public Node next;public Node(int data) {value = data;}}public static class DoubleNode {public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int data) {value = data;}}//  head 单链表反转//   a    ->   b    ->  c  ->  null//   c    ->   b    ->  a  ->  nullpublic 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 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;}return pre;}//用集合来实现单链表反转，用于进行对比验证public static Node testReverseLinkedList(Node head) {if (head == null) return null;ArrayList<Node> list = new ArrayList<>();while (head != null) {list.add(head);head = head.next;}list.get(0).next = null;for (int i = 1; i < list.size(); i++) {list.get(i).next = list.get(i - 1);}return list.get(list.size() - 1);}//用集合来实现双链表反转，用于对比验证public static DoubleNode testReverseDoubleList(DoubleNode head) {if (head == null) return null;ArrayList<DoubleNode> list = new ArrayList<>();while (head != null) {list.add(head);head = head.next;}list.get(0).next = null;DoubleNode pre = list.get(0);for (int i = 1; i < list.size(); i++) {DoubleNode cur = list.get(i);cur.last = null;cur.next = pre;pre.last = cur;pre = cur;}return list.get(list.size() - 1);}// for test 随机生成单链表public static Node generateRandomLinkedList(int len, int value) {int size = (int) (Math.random() * (len + 1));if (size == 0) return null;Node head = new Node((int) (Math.random() * (value + 1)));Node pre = head;size--;while (size != 0) {Node cur = new Node((int) (Math.random() * (value + 1)));pre.next = cur;pre = cur;size--;}return head;}// for test 随机生成双链表public static DoubleNode generateRandomDoubleList(int len, int value) {int size = (int) (Math.random() * (len + 1));if (size == 0) return null;DoubleNode head = new DoubleNode((int) (Math.random() * (value + 1)));DoubleNode pre = head;size--;while (size != 0) {DoubleNode cur = new DoubleNode((int) (Math.random() * (value + 1)));pre.next = cur;cur.last = pre;pre = cur;size--;}return head;}// for test 集合存储链表节点值public static List<Integer> getLinkedListOriginOrder(Node head) {List<Integer> ans = new ArrayList<>();while (head != null) {ans.add(head.value);head = head.next;}return ans;}// for test 验证链表节点值是否反转成功public static boolean checkLinkedListReverse(List<Integer> origin, Node head) {for (int i = origin.size() - 1; i >= 0; i--) {if (!origin.get(i).equals(head.value)) {return false;}head = head.next;}return true;}// for testpublic static List<Integer> getDoubleListOriginOrder(DoubleNode head) {List<Integer> ans = new ArrayList<>();while (head != null) {ans.add(head.value);head = head.next;}return ans;}// for test 验证双链表节点值是否反转成功public static boolean checkDoubleListReverse(List<Integer> origin, DoubleNode head) {DoubleNode end = null;for (int i = origin.size() - 1; i >= 0; i--) {if (!origin.get(i).equals(head.value)) {return false;}end = head;head = head.next;}for (int i = 0; i < origin.size(); i++) {if (!origin.get(i).equals(end.value)) {return false;}end = end.last;}return true;}// head = removeValue(head, 2);  删除链表中值为2的节点。 1->3->2->2->4->2->5  =》   1->3->4->5public static Node removeValue(Node head, int num) {//head来到第一个不需要删的位置 先确认头节点，排除排前面如果是num 则需一次跳过，比如 2->2->2->2->1->3   需要将新的头节点head指向到1的位置while(head != null){if(head.value != num){break;}head = head.next;}// 1 ) head == null// 2 ) head != nullNode pre =head,cur=head;while (cur != null){if(cur.value ==num){pre.next = cur.next;}else {pre = cur;}cur = cur.next;}return head;}// for testpublic static void main(String[] args) {int len = 50;int value = 100;int testTime = 100000;System.out.println("test begin!");for (int i = 0; i < testTime; i++) {Node node1 = generateRandomLinkedList(len, value);List<Integer> list1 = getLinkedListOriginOrder(node1);node1 = reverseLinkedList(node1);if (!checkLinkedListReverse(list1, node1)) {System.out.println("Oops1!");}Node node2 = generateRandomLinkedList(len, value);List<Integer> list2 = getLinkedListOriginOrder(node2);node2 = testReverseLinkedList(node2);if (!checkLinkedListReverse(list2, node2)) {System.out.println("Oops2!");}DoubleNode node3 = generateRandomDoubleList(len, value);List<Integer> list3 = getDoubleListOriginOrder(node3);node3 = reverseDoubleList(node3);if (!checkDoubleListReverse(list3, node3)) {System.out.println("Oops3!");}DoubleNode node4 = generateRandomDoubleList(len, value);List<Integer> list4 = getDoubleListOriginOrder(node4);node4 = testReverseDoubleList(node4);if (!checkDoubleListReverse(list4, node4)) {System.out.println("Oops4!");}}System.out.println("test finish!");}
}

二、双向链表实现栈和队列

package class03;import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;//双向链表实现队列和栈
public class DoubleEndsQueueToStackAndQueue {public static class Node<T> {public T value;public Node<T> last;public Node<T> next;public Node(T data) {value = data;}}public static class DoubleEndQueue<T> {public Node<T> head;public Node<T> tail;//头端添加节点public void addFromHead(T value) {Node<T> 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<T> 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<T> cur = head;if (head == tail) {head = null;tail = null;} else {head = head.next;head.last = null;cur.next = 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 DoubleEndQueue<T> queue;//构造器public MyStack() {queue = new DoubleEndQueue<>();}//入栈public void push(T data) {queue.addFromHead(data);}//出栈public T pop() {return queue.popFromHead();}//是否为空public boolean isEmpty() {return queue.isEmpty();}}//构造队列public static class MyQueue<T> {private DoubleEndQueue<T> queue;public MyQueue() {queue = new DoubleEndQueue<>();}public void push(T data) {queue.addFromHead(data);}public T poll() {return queue.popFromBottom();}public boolean isEmpty() {return queue.isEmpty();}}//判断两个Integer节点是否相等public static boolean isEqual(Integer o1, Integer o2) {if (o1 == null && o2 == null) return true;if (o1 == null && o2 != null) return false;if (o1 != null && o2 == null) return false;return o1.equals(o2);}public static void main(String[] args) {int oneTestDataNum = 100;int value = 10000;int testTimes = 100000;for (int i = 0; i < testTimes; i++) {Code03_DoubleEndsQueueToStackAndQueue.MyStack<Integer> myStack = new Code03_DoubleEndsQueueToStackAndQueue.MyStack<>();Code03_DoubleEndsQueueToStackAndQueue.MyQueue<Integer> myQueue = new Code03_DoubleEndsQueueToStackAndQueue.MyQueue<>();Stack<Integer> stack = new Stack<>();Queue<Integer> queue = new LinkedList<>();for (int j = 0; j < oneTestDataNum; j++) {int nums = (int) (Math.random() * value);if (stack.isEmpty()) {myStack.push(nums);stack.push(nums);} else {if (Math.random() < 0.5) {myStack.push(nums);stack.push(nums);} else {if (!isEqual(myStack.pop(), stack.pop())) {System.out.println("oops!");}}}int numq = (int) (Math.random() * value);if (queue.isEmpty()) {myQueue.push(numq);queue.offer(numq);} else {if (Math.random() < 0.5) {myQueue.push(numq);queue.offer(numq);} else {if (!isEqual(myQueue.poll(), queue.poll())) {System.out.println("oops!");}}}}}System.out.println("finish!");}
}

三、数组实现队列

（数组实现栈就比较简单 因为都是入栈出栈只需在一个方向，下一个index索引加1就能满足，其他逻辑类似，而队列，需要判断是index+1还是回到0索引位置）

package class03;/*** */
//数组实现队列， 栈就比较简单 入栈就直接按需从0索引赋值，出栈也是从最后一个索引arr.length-1开始弹出
//队列就是先进先进，入栈从0开始，出栈从0开始，而且中间出栈后，0位置空，接着要入栈就得判断下一个位置
// 是否超边界，是否超大小，如果超大小就肯定满了，如果没有超，就看下个位置会不会越界，会就需要入栈到0位置，
// 形成一个环形循环数组public class RingArray {public static class MyQueue {private int[] arr;private int pushi; //随着插入，这个索引就往下，所以表示是 元素边界的end边界private int polli; //beginprivate int size;  //存在数组中的元素个数private final int limit; //数组的长度设置为常量 不可修改public MyQueue(int limit) {arr = new int[limit];pushi = 0;polli = 0;size = 0;this.limit = limit;}public void push(int value) {//先判断size元素实际个数是否与数组长度相等 相等就不能入队列了if (size == limit) {throw new RuntimeException("队列满，不能添加元素！");}size++;//赋值arr[pushi] = value;//判断下个索引pushi = nextIndex(pushi);}public int poll() {//先判断size元素实际个数是否为0，0则没有元素 不能出队列if (size == 0) {throw new RuntimeException("队列空，不能弹出元素！");}size--;//返回弹出元素，该索引位置的内容无需重新赋值，因为下次元素push到该位置会赋值覆盖的int ans = arr[polli];//判断下个索引polli = nextIndex(polli);return ans;}public boolean isEmpty() {return size == 0;}//判断元素的下个索引，需要与arr[limit-1]即数组最后一个索引比较，如果小于表示可以接着+1，//大于等于就需要循环走到0索引位置public int nextIndex(int index) {return index < limit - 1 ? ++index : 0;}}
}

四、通过两个栈结构，来实现获取栈中的最小值

package class03;import java.util.Stack;/****///通过两个栈结构，来实现获取栈中的最小值
public class GetMinStack {public static class MyStack1 {private Stack<Integer> stackData;private Stack<Integer> stackMin;public MyStack1() {stackData = new Stack<>();stackMin = new Stack<>();}public void push(int num) {//如果当前最小值为空，那么入栈的值就定为最小值，入最小栈if (stackMin.isEmpty()) {stackMin.push(num);} else {//如果非空，而当前值小于等于最小栈的最小值，那么就入栈，大于则不用入栈。保证最小栈栈顶是最小值if (num <= this.getmin()) {stackMin.push(num);}}stackData.push(num);}public int pop() {if (stackData.isEmpty()) {throw new RuntimeException("数据栈为空，没有元素！");}//数据栈出栈int ans = stackData.pop();//同时要判断是否出栈的是与当前最小栈的栈顶一样 是则需要一起出栈 才能保持始终为最小值栈顶if (ans == this.getmin()) {stackMin.pop();}return ans;}public int getmin() {if (stackMin.isEmpty()) {throw new RuntimeException("最小栈为空，没有元素！");}//非空则取栈顶元素即最小值return stackMin.peek();}}public static void main(String[] args) {MyStack1 stack1 = new MyStack1();stack1.push(3);System.out.println(stack1.getmin());stack1.push(4);System.out.println(stack1.getmin());stack1.push(1);System.out.println(stack1.getmin());System.out.println(stack1.pop());System.out.println(stack1.getmin());System.out.println("=============");}
}

五、两个栈实现队列,队列先进先出，栈先进后出，需要用两个栈来实现

package class03;import java.util.Stack;/*** 两个栈实现队列,队列先进先出，栈先进后出，需要用两个栈来实现*/
public class TwoStacksImplementQueue {public static class TwoStacksQueue{private Stack<Integer> stackPush;private Stack<Integer> stackPop;public TwoStacksQueue(){stackPush = new Stack<>();stackPop = new Stack<>();}public void add(int num){stackPush.push(num);}//出栈注意，假设//pop栈有数据就直接出栈。 没数据就需要将现有的push栈数据全部清空入pop栈，在出pop栈public int poll(){if(stackPop.isEmpty() && stackPush.isEmpty()){throw new RuntimeException("队列为空，没有元素！");}if(!stackPop.isEmpty()){return stackPop.pop();}else{while(!stackPush.empty())stackPop.push(stackPush.pop());}return stackPop.pop();}public int peek(){if(stackPop.isEmpty() && stackPush.isEmpty()){throw new RuntimeException("队列为空，没有元素！");}if(!stackPop.isEmpty()){return stackPop.peek();}else{while(!stackPush.empty())stackPop.push(stackPush.pop());}return stackPop.peek();}}public static void main(String[] args) {TwoStacksQueue test = new TwoStacksQueue();test.add(1);test.add(2);test.add(3);test.add(4);System.out.println(test.peek());System.out.println(test.poll());System.out.println(test.peek());System.out.println(test.poll());System.out.println(test.peek());System.out.println(test.poll());}
}

六、两个队列实现一个栈结构

package class03;import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;/*** 两个队列实现一个栈结构*/
public class TwoQueueImplementStack {public static class TwoQueueStack<T> {private Queue<T> queue;private Queue<T> help;public TwoQueueStack() {queue = new LinkedList<>();help = new LinkedList<>();}public void push(T value) {queue.offer(value);}public T poll() {//把队列都弹出到help辅助队列，保留最后一个不弹，用来popwhile (queue.size() > 1) {help.offer(queue.poll());}T ans = queue.poll();//此时queue为空队列，再把help队列数据放回来Queue<T> temp = queue;queue = help;help = temp;return ans;}public T peek() {//把队列都弹出到help辅助队列，保留最后一个不弹，用来popwhile (queue.size() > 1) {help.offer(queue.poll());}T ans = queue.poll();//这里注意要把弹出的最后一个元素入回队列help.offer(ans);//此时queue为空队列，再把help队列数据放回来Queue<T> temp = queue;queue = help;help = temp;return ans;}public boolean isEmpty() {return queue.isEmpty();}}public static void main(String[] args) {System.out.println("test begin");TwoQueueStack<Integer> myStack = new TwoQueueStack<>();Stack<Integer> test = new Stack<>();int testTime = 1000000;int max = 1000000;for (int i = 0; i < testTime; i++) {if (myStack.isEmpty()) {if (!test.isEmpty()) {System.out.println("Oops");}int num = (int) (Math.random() * max);myStack.push(num);test.push(num);} else {if (Math.random() < 0.25) {int num = (int) (Math.random() * max);myStack.push(num);test.push(num);} else if (Math.random() < 0.5) {if (!myStack.peek().equals(test.peek())) {System.out.println("Oops");}} else if (Math.random() < 0.75) {if (!myStack.poll().equals(test.pop())) {System.out.println("Oops");}} else {if (myStack.isEmpty() != test.isEmpty()) {System.out.println("Oops");}}}}System.out.println("test finish!");}}

七、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)

注意：

(注意是需要两次子递归的递归元素是同等的，比如中点分开左右两数组，分别递归，此时两个子递归元素都是N/2,时间复杂度O(N/2)+O(N/2),例如归并排序)

归并排序，递归过程还需要进行合并左右数组，需要合并操作时间复杂度为O(N)

此形式符合Master公式，T(N)= 2 * T(N/2) + O(N^1)  ，a=2,b=2,d=1，

log(2,2) == 1 所以归并排序复杂度为O(N *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)不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度

1)void put(K key, V value)
将一个(key，value)记录加入到表中，或者将key的记录更新成value。
2)V get(K key)
根据给定的key，查询value并返回。
3)void remove(K key)
移除key的记录。
4)boolean containsKey(K key)
询问是否有关于key的记录。
5)K firstKey()
返回所有键值的排序结果中，最小的那个。
6)K lastKey()
返回所有键值的排序结果中，最大的那个。
7)K floorKey(K key)
返回<=key 离key最近的那个
8)K ceilingKey(K key）
返回>=key 离key最近的那个

哈希表在使用时，增删改查时间复杂度都是O(1)

有序表在使用时，比哈希表功能多，时间复杂度都是O(logN)