左神算法课笔记（二）：链表、栈和队列、递归Master公式、哈希表、有序表

2023-12-31 20:38
文章标签 算法 公式 链表 笔记 有序 队列 哈希 递归 master 左神

本文主要是介绍左神算法课笔记（二）：链表、栈和队列、递归Master公式、哈希表、有序表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

单向链表

在这里插入图片描述

双向链表

在这里插入图片描述

单链表、双链表最简单的面试题

在这里插入图片描述

1、单链表和双链表如何反转
package class02;import java.util.ArrayList;public class Code01_ReverseList {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;}}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 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;int N = list.size();for (int i = 1; i < N; i++) {list.get(i).next = list.get(i - 1);}return list.get(N - 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);int N = list.size();for (int i = 1; i < N; i++) {DoubleNode cur = list.get(i);cur.last = null;cur.next = pre;pre.last = cur;pre = cur;}return list.get(N - 1);}public static Node generateRandomLinkedList(int len, int value) {int size = (int) (Math.random() * (len + 1));if (size == 0) {return null;}size--;Node head = new Node((int) (Math.random() * (value + 1)));Node pre = head;while (size != 0) {Node cur = new Node((int) (Math.random() * (value + 1)));pre.next = cur;pre = cur;size--;}return head;}public static DoubleNode generateRandomDoubleList(int len, int value) {int size = (int) (Math.random() * (len + 1));if (size == 0) {return null;}size--;DoubleNode head = new DoubleNode((int) (Math.random() * (value + 1)));DoubleNode pre = head;while (size != 0) {DoubleNode cur = new DoubleNode((int) (Math.random() * (value + 1)));pre.next = cur;cur.last = pre;pre = cur;size--;}return head;}// 要求无环，有环别用这个函数public static boolean checkLinkedListEqual(Node head1, Node head2) {while (head1 != null && head2 != null) {if (head1.value != head2.value) {return false;}head1 = head1.next;head2 = head2.next;}return head1 == null && head2 == null;}// 要求无环，有环别用这个函数public static boolean checkDoubleListEqual(DoubleNode head1, DoubleNode head2) {boolean null1 = head1 == null;boolean null2 = head2 == null;if (null1 && null2) {return true;}if (null1 ^ null2) {return false;}if (head1.last != null || head2.last != null) {return false;}DoubleNode end1 = null;DoubleNode end2 = null;while (head1 != null && head2 != null) {if (head1.value != head2.value) {return false;}end1 = head1;end2 = head2;head1 = head1.next;head2 = head2.next;}if (head1 != null || head2 != null) {return false;}while (end1 != null && end2 != null) {if (end1.value != end2.value) {return false;}end1 = end1.last;end2 = end2.last;}return end1 == null && end2 == null;}public static void main(String[] args) {int len = 50;int value = 100;int testTime = 100000;for (int i = 0; i < testTime; i++) {Node node1 = generateRandomLinkedList(len, value);Node reverse1 = reverseLinkedList(node1);Node back1 = testReverseLinkedList(reverse1);if (!checkLinkedListEqual(node1, back1)) {System.out.println("oops!");break;}DoubleNode node2 = generateRandomDoubleList(len, value);DoubleNode reverse2 = reverseDoubleList(node2);DoubleNode back2 = testReverseDoubleList(reverse2);if (!checkDoubleListEqual(node2, back2)) {System.out.println("oops!");break;}}System.out.println("finish!");}
}
2、把给定值都删除
package class02;public class Code02_DeleteGivenValue {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) {while (head != null) {if (head.value != num) {break;}head = head.next;}// head来到 第一个不需要删的位置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;}
}

栈和队列

在这里插入图片描述栈
在这里插入图片描述队列
在这里插入图片描述栈和队列的实际实现：

  • 双向链表实现（头指针、尾指针）提供四种方法：从头部进、从头部出、从尾部进、从尾部出
  • 数组实现
1、双向链表实现
package class02;import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class Code03_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 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 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 boolean isEqual(Integer o1, Integer o2) {if (o1 == null && o2 != null) {return false;}if (o1 != null && o2 == null) {return false;}if (o1 == null && o2 == null) {return true;}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++) {MyStack<Integer> myStack = new MyStack<>();MyQueue<Integer> myQueue = new 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 (stack.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!");}
}
2、数组实现

动态数组 / 固定大小的静态数组
在这里插入图片描述

package class02;public class Code04_RingArray {public static class MyQueue {private int[] arr;private int pushi;private int polli;private 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) {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(polli);return ans;}public boolean isEmpty() {return size == 0;}// 如果现在的下标是i，返回下一个位置private int nextIndex(int i) {return i < limit - 1 ? i + 1 : 0;}}
}

在这里插入图片描述

3、实现一个特殊额栈

在这里插入图片描述维护一个最小栈。

普通栈正常使用，最小栈存放的是每一个状态下当前数的最小值

普通栈和最小栈同步push、pop，只不过给用户返回的是普通栈里的内容

在这里插入图片描述

4、如何用队列实现一个栈

两个队列，都是从头进、从尾出
data队列
help队列

例如，现在要push进1,2,3,4,5
在这里插入图片描述
现在要 pop 1,2,3,4,5
（除了最后一个数5以外，剩余的移动到help队列中，留下5用来给用户返回，更改data队列和help队列的属性，这样以此类推）
在这里插入图片描述

package class02;import java.util.Stack;public class Code06_TwoStacksImplementQueue {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();}}public static void main(String[] args) {TwoStacksQueue test = new TwoStacksQueue();test.add(1);test.add(2);test.add(3);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());}}
5、如何用栈实现一个队列

维护两个栈：
push栈，pop栈
现用户给我1,2,3,4,5
在这里插入图片描述
现在我要pop
在这里插入图片描述
（1）pop栈为空的时候才能往外导数据
（2）如果决定导数据，push栈在导的过程中要一次性的导完
在这里插入图片描述
只要满足上面两个原则，不管什么时候导数据，都是对的

package class02;import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class Code07_TwoQueueImplementStack {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.poll();help.offer(ans);Queue<T> tmp = queue;queue = help;help = tmp;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!");}
}

递归

在这里插入图片描述

例子

在这里插入图片描述递归函数的思维导图
在这里插入图片描述

下面这个解法的复杂度是O(n)

package class02;public class Code08_GetMax {// 求arr中的最大值public static int getMax(int[] arr) {return process(arr, 0, arr.length - 1);}// arr[L..R]范围上求最大值  L ... R   Npublic static int process(int[] arr, int L, int R) {if (L == R) { // arr[L..R]范围上只有一个数，直接返回，base casereturn arr[L];}int mid = L + ((R - L) >> 1); // 中点   	1int leftMax = process(arr, L, mid);int rightMax = process(arr, mid + 1, R);return Math.max(leftMax, rightMax);}
}

递归在语言上是怎么实现的？
递归实际上是运用的系统栈
在这里插入图片描述任何递归都可以改成非递归。
“尾递归”是一些语言对递归行为进行的优化，在底层执行的过程中已经是迭代了。

对于某一类递归，它的时间复杂度是可以直接确定的：
子问题的规模是N/b，子问题被调用a次，除去递归调用过程之外剩下所有行为的时间复杂度是O(n^d)

在这里插入图片描述
则时间复杂度可以直接确定如下（Master公式）：
在这里插入图片描述

比如说我们上面这个问题就是
在这里插入图片描述

哈希表 HashMap

在这里插入图片描述

有序表 TreeMap

有序表的特点在于，你可以乱序插入元素，但他自己内部是有序的。
但是它的时间复杂度是O(logn)
有序表的底层实现可以是AVL树/SB树/红黑树，或跳表
非基础类型在有序表中，怎么比较大小？以后会在堆的章节讲。

package class02;import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeMap;public class HashMapAndSortedMap {public static class Node{public int value;public Node(int v) {value = v;}}public static void main(String[] args) {// UnSortedMapHashMap<Integer, String> map = new HashMap<>();map.put(1000000, "我是1000000");map.put(2, "我是2");map.put(3, "我是3");map.put(4, "我是4");map.put(5, "我是5");map.put(6, "我是6");map.put(1000000, "我是1000001");System.out.println(map.containsKey(1));System.out.println(map.containsKey(10));System.out.println(map.get(4));System.out.println(map.get(10));map.put(4, "他是4");System.out.println(map.get(4));map.remove(4);System.out.println(map.get(4));//       keyHashSet<String>  set = new HashSet<>();set.add("abc");set.contains("abc");set.remove("abc");// 哈希表，增、删、改、查，在使用时，O（1）System.out.println("=====================");int a = 100000;int b = 100000;System.out.println(a == b);Integer c = 100000;Integer d = 100000;System.out.println(c.equals(d));Integer e = 127;  //  - 128  ~  127Integer f = 127;System.out.println(e == f);HashMap<Node, String> map2 = new HashMap<>();Node node1 = new Node(1);Node node2 = node1;map2.put(node1, "我是node1");map2.put(node2, "我是node1");System.out.println(map2.size());System.out.println("======================");TreeMap<Integer, String> treeMap = new TreeMap<>();treeMap.put(3, "我是3");treeMap.put(4, "我是4");treeMap.put(8, "我是8");treeMap.put(5, "我是5");treeMap.put(7, "我是7");treeMap.put(1, "我是1");treeMap.put(2, "我是2");System.out.println(treeMap.containsKey(1));System.out.println(treeMap.containsKey(10));System.out.println(treeMap.get(4));System.out.println(treeMap.get(10));treeMap.put(4, "他是4");System.out.println(treeMap.get(4));treeMap.remove(4);System.out.println(treeMap.get(4));System.out.println(treeMap.firstKey());System.out.println(treeMap.lastKey());// <= 4System.out.println(treeMap.floorKey(4));// >= 4System.out.println(treeMap.ceilingKey(4));// O(logN)	}	
}

这篇关于左神算法课笔记（二）：链表、栈和队列、递归Master公式、哈希表、有序表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/557084。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2