推荐最新

cloud-atlas

### 《云图》这是一个不断迭代改进的开源技术分享项目，我想以每获得100个GitHub Star作为0.1版本的递进，不断完善这本技术书。请访问 readthedocs平台上的云图以便获得最佳阅读体验。 ### 这本书的目标大概在两年前，作者萌生了以开源技术构建自动化部署和交付数据中心的想法。通过开源技术来构建 one personal detacenter ，即一个人来实现完整的数据中心的构建和运维，实现IaaS，PaaS，SaaS。开源技术的迅速发展，已经赋能给全栈工程师，或许能以一己之力实现数据中心构建和维护。从存储、网络、虚拟化，从操作系统到数据库，从Web服务到消息中间件，只要是基础的服务，都应该通过自动化以及精心构建的架构来实现效率的最大化。作者写这本书是自己思考和实践的结合。为了能够模拟集群技术，作者采用了个人笔记本和二手服务器来构建实验环境，模拟构建IDC所使用的各种开源技术，力求能够将实践的方案无缝扩展成真实的数据中心。 ### 本书的特点本书的(几乎)所有文章都经过作者自己的实践验证，完整分享每个操作步骤，力求清晰、准确、可复现: 和很多(空洞的)PPT分享不同，作者的分享就是真实可复现的操作实践，没有隐藏和遗漏即使是翻译和综合，作者也会把自己的实践经验以及踩过的坑和解决方法融合到文章中，使Clous Atlas成为真正的实践指南

浏览量253

英勇黄铜

顺序表与ArrayList

线性表线性表就是有多个相同属性的数据元素的有限序列。线性表是一种在我们工作中广泛可以使用到的数据结构，常见的线性表：顺序表，链表，栈，队列……线性表在逻辑上是线性结构，是一条连续的直线。但是它在物理结构上可可能不是连续的。线性表在物理上存储时，一般是以数组和链式结构的方式存储。顺序表顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。简单顺序表的模拟实现大家可以移步到 Gitee 上看代码：structure_code/java2023.9.12/src/mylist · 彭子杰/数据结构 - 码云 - 开源中国 (gitee.com)集合框架java 集合框架，也称为容器，是定义在 java.util 包下的一组接口 interfaces 和其实现类 class 。它是要的作用是将多个元素 element 置于一个单元中，用于对这些元素进行快速，便捷的存储 store ，检索 retrieve ，管理 manipulate ，即平时我们说的增删查改。类与接口总览：ArrayList 介绍在 java 的集合框架（容器）中，ArrayList 就是一个顺序表，它是一个普通的类，实现了 List 接口，框架如下：注意：ArrayList 是以泛型方式实现的，使用时需要先实例化ArrayList 实现了 RandomAccess 接口，表明 ArrayList 支持随机访问ArrayList 实现了 cloneble 接口，表明 ArrayList 是可以 clone 的ArrayList 实现了 Serializable 接口，表明 ArrayList 是支持序列化的和 Vector 不同，ArrayList 不是线程安全的，在单线程下可以使用，在多线程中可以选择 Vector 或者 CopyOnWriteArrayListArrayList 底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表ArrayList 的使用ArrayList 的构造public class Test { public static void main(String[] args) { // ArrayList创建，推荐写法 // 构造一个空的列表 List<Integer> list1 = new ArrayList<>(); // 构造一个具有10个容量的列表 List<Integer> list2 = new ArrayList<>(10); list2.add(1); list2.add(2); list2.add(3); // list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素 // list3构造好之后，与list中的元素一致 ArrayList<Integer> list3 = new ArrayList<>(list2); // 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难 List list4 = new ArrayList(); list4.add("111"); list4.add(100); } }ArrayList 的基本方法 public static void main(String[] args) { List<String> list = new ArrayList<>(); list.add("JavaSE"); list.add("JavaWeb"); list.add("JavaEE"); list.add("JVM"); list.add("测试课程"); System.out.println(list); // 获取list中有效元素个数 System.out.println(list.size()); // 获取和设置index位置上的元素，注意index必须介于[0, size)间 System.out.println(list.get(1)); list.set(1, "JavaWEB"); System.out.println(list.get(1)); // 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置 list.add(1, "Java数据结构"); System.out.println(list); // 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置 list.remove("JVM"); System.out.println(list); // 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常 list.remove(list.size()-1); System.out.println(list); } // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找 list.add("JavaSE"); System.out.println(list.indexOf("JavaSE")); System.out.println(list.lastIndexOf("JavaSE")); // 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组 // List<String> ret = list.subList(0, 4); System.out.println(ret); list.clear(); System.out.println(list.size()); }ArrayList 的遍历ArrayList 可以使用三个方式来遍历： for 循环， foreach ，迭代器 public static void main(String[] args) { List<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); // 使用下标+for遍历 for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i) + " "); } System.out.println(); // 借助foreach遍历 for (Integer integer : list) { System.out.print(integer + " "); } System.out.println(); // 使用迭代器遍历 Iterator<Integer> it = list.listIterator(); while(it.hasNext()){ System.out.print(it.next() + " "); } System.out.println(); }这里的迭代器是设计模式的一种。ArrayList 的扩容机制首选我们来看一段代码：public static void main(String[] args) { List<Integer> list = new ArrayList<>(); for (int i = 0; i < 100; i++) { list.add(i); } }我们知道，ArrayList 是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。我们可以看一下源码：Object[] elementData; // 存放元素的空间 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间 private static final int DEFAULT_CAPACITY = 10; // 默认容量大小 public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; private void grow(int minCapacity) { // 获取旧空间大小 int oldCapacity = elementData.length; // 预计按照1.5倍方式扩容 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果用户需要扩容大小超过原空间1.5倍，按照用户所需大小扩容 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 调用copyOf扩容 elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { // 如果minCapacity小于0，抛出OutOfMemoryError异常 if (minCapacity < 0) throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }画图分析【总结】检查是否真正需要扩容，如果是 g 调用了 row 准备扩容估计需要库容的大小初步按照 1.5 倍的大小扩容如果用户需要的大小超过1.5倍，则按照用户所需大小扩容真正扩容之前检查是否可以扩容成功，防止太大导致扩容失败使用 copyof 进行扩容ArrayList 的具体使用这里举一个简单的洗牌算法：public class Card { public int rank; // 牌面值 public String suit; // 花色 @Override public String toString() { return String.format("[%s %d]", suit, rank); } } import java.util.List; import java.util.ArrayList; import java.util.Random; public class CardDemo { public static final String[] SUITS = {"♠", "♥", "♣", "♦"}; // 买一副牌 private static List<Card> buyDeck() { List<Card> deck = new ArrayList<>(52); for (int i = 0; i < 4; i++) { for (int j = 1; j <= 13; j++) { String suit = SUITS[i]; int rank = j; Card card = new Card(); card.rank = rank; card.suit = suit; deck.add(card); } } return deck; } private static void swap(List<Card> deck, int i, int j) { Card t = deck.get(i); deck.set(i, deck.get(j)); deck.set(j, t); } private static void shuffle(List<Card> deck) { Random random = new Random(20190905); for (int i = deck.size() - 1; i > 0; i--) { int r = random.nextInt(i); swap(deck, i, r); } } public static void main(String[] args) { List<Card> deck = buyDeck(); System.out.println("刚买回来的牌:"); System.out.println(deck); shuffle(deck); System.out.println("洗过的牌:"); System.out.println(deck); // 三个人，每个人轮流抓 5 张牌 List<List<Card>> hands = new ArrayList<>(); hands.add(new ArrayList<>()); hands.add(new ArrayList<>()); hands.add(new ArrayList<>()); for (int i = 0; i < 5; i++) { for (int j = 0; j < 3; j++) { hands.get(j).add(deck.remove(0)); } } System.out.println("剩余的牌:"); System.out.println(deck); System.out.println("A 手中的牌:"); System.out.println(hands.get(0)); System.out.println("B 手中的牌:"); System.out.println(hands.get(1)); System.out.println("C 手中的牌:"); System.out.println(hands.get(2)); } }顺序表 ArrayList 存储结构的优缺点优点不用为了表达清楚元素之间的关系而增加额外的存储空间。可以快速地存取表中的任意一个位置的元素缺点在任位置删除插入元素的时间复杂度为O(N)，所以需要移动大量的元素当顺序表长度变化较大时，难以确定存储空间的容量。容易造成存储空间的碎片，也就是浪费空间。

浏览量2287

英勇黄铜

栈与队列

栈栈的概念栈它是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守着先进后出的规则。压栈：栈的插入操作叫做进栈，压栈，入栈，入数据在栈顶。出栈：栈的删除操作叫做出栈。出数据在栈顶。栈的使用代码示范：public class Test { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println(stack.peek()); System.out.println(stack.pop()); System.out.println(stack.empty()); System.out.println(stack.size()); } }栈的模拟实现Stack 继承了 Vector ，Vector 和 ArrayList 类似，都是动态的顺序表，但不同的是 Vector 是线性安全的。代码模拟实现：public class MyStack implements Istack{ private int[] elem; private int usedsize; private static final int DEFAULT_CAPACITY = 10; public MyStack() { this.elem = new int[DEFAULT_CAPACITY]; } @Override public void push(int x) { if(full()) { elem = Arrays.copyOf(elem, 2*elem.length); } elem[usedsize] = x; usedsize++; } @Override public boolean full() { if(usedsize == elem.length) { return true; } return false; } @Override public int pop() { if(Empty()) { throw new Emptyexception("数组为空"); } int ret = elem[usedsize-1]; usedsize--; return ret; } @Override public int peek() { if(Empty()) { throw new Emptyexception("数组为空"); } return elem[usedsize - 1]; } @Override public int size() { return usedsize; } @Override public boolean Empty() { if(usedsize == 0) { return true; } return false; } } 栈的应用将递归转化为循环// 递归方式 void printList(Node head){ if(null != head){ printList(head.next); System.out.print(head.val + " "); } } // 循环方式 void printList(Node head){ if(null == head){ return; } Stack<Node> s = new Stack<>(); // 将链表中的结点保存在栈中 Node cur = head; while(null != cur){ s.push(cur); cur = cur.next; } // 将栈中的元素出栈 while(!s.empty()){ System.out.print(s.pop().val + " "); } }栈，虚拟机栈，栈帧的区分栈：是一种数据结构虚拟机栈：是 java 虚拟机 JVM 中分配的一块内存栈帧：是在调用方法的时候，会在虚拟机中为这个方法分配一块内存队列（ Queue ）队列的概念队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO ( FirstIn First Out ) 入队列：进行插入操作的一端称为队尾（ Tail / Rear ）出队列：进行删除操作的一端称为队头队列的使用在 java 中， Queue 是一个接口，底层是通过链表来实现的这里要注意一个点：Queue 是一个接口，在实例化时必须实例化 LinkedList 的对象，因为 LinkedList 实现了 Queue 接口public static void main(String[] args) { Queue<Integer> q = new LinkedList<>(); q.offer(1); q.offer(2); q.offer(3); q.offer(4); q.offer(5); // 从队尾入队列 System.out.println(q.size()); System.out.println(q.peek()); // 获取队头元素 q.poll(); System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回 if(q.isEmpty()){ System.out.println("队列空"); }else{ System.out.println(q.size()); } }队列模拟实现链式结构对列：public class MyLinkqueue { static class ListNode { int val; ListNode prev; ListNode next; public ListNode(int val) { this.val = val; } } ListNode head; ListNode last; int usedsize; public void offer(int val) { ListNode node = new ListNode(val); if(head == null) { head = node; last = node; usedsize++; return; } last.next = node; node.prev = last; last = node; usedsize++; } public int poll() { if(head == null) { return -1; } int ret = head.val; if(head.next == null) { head = null; last = null; } else { head.next.prev = null; head = head.next; } usedsize--; return ret; } public int peek() { if(head == null) { return -1; } return head.val; } public boolean Empty(){ return head == null; } public int size() { return usedsize; } } 循环队列实际中我们有时还会使用一种队列叫循环队列，操作系统课程讲解生产者消费者模型时可以就会使用循环队列，环形队列通常使用数组实现代码：class MyCircularQueue { int[] elem; int front; int rear; public MyCircularQueue(int k) { elem = new int[k+1]; } public boolean enQueue(int value) { if(isFull()) { return false; } elem[rear] = value; rear = (rear+1) % elem.length; return true; } public boolean deQueue() { if(isEmpty()) { return false; } front = (front+1)% elem.length; return true; } public int Front() { if(isEmpty()) { return -1; } return elem[front]; } public int Rear() { if(isEmpty()) { return -1; } int ret = (rear == 0) ? elem.length-1 : rear-1; return elem[ret]; } public boolean isEmpty() { return front == rear; } public boolean isFull() { return (rear+1) % elem.length == front; } }双端队列双端队列是指允许两端都可以进行入队和出队操作的队列， deque 是 “ double ended queue ” 的简称，那就说明元素可以从队头出队和入队，也可以从队尾出队和入队，Deque 是一个接口，使用时必须创建 LinkedList 的对象

浏览量2152

英勇黄铜

时间复杂度和空间复杂度

引入这里提出一个问题，我们应该如何衡量一个算法的好坏？这里就要提到算法效率了。算法效率分为两种：一种为时间效率，一种为空间效率。时间效率为称为时间复杂度，空间效率被称为空间复杂度。时间复杂度主要衡量的是一个算法的运行速度，空间复杂度衡量的是一个算法所需要的空间。在计算机的早期，因为计算机空间小，我们队空间复杂度很重视。但是在经过一段的时间的发展后，计算机的内存变得庞大起来后，我们就不太关注空间复杂度了，而是比较关心时间复杂度。时间复杂度时间复杂度的概念时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。大 O 的渐进表示法 void func1(int N){ int count = 0; for (int i = 0; i < N ; i++) { for (int j = 0; j < N ; j++) { count++; } } for (int k = 0; k < 2 * N ; k++) { count++; } int M = 10; while ((M--) > 0) { count++; } System.out.println(count); }通过简单的计算我们可以得到 func的时间复杂度为：n^2+2*n+10 但是在实际中我们计算时间复杂度的时候，我们其实并不一定要计算精确的执行次数，而只需要大概的执行次数，这里就是我们的大 O 渐进表达法。大 O 阶表达方式1 用常数1取代运行时间中的所有加法常数。2 在修改后的运行次数函数中，加法中只保留最高阶项3 如果最高阶存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶那么，我们使用大O阶的渐进表示法后，func1的时间复杂度就是 O(n^2)算法的时间复杂度是会存在最好，平均，最坏的情况：最坏：任意输入规模的最大运行次数平均：任意输入规模的期望运行次数最好：任意输入规模的最小运行次数一般情况下，我们关注的是最坏的运行情况常见的时间复杂度计算实例 1 void func2(int N) { int count = 0; for (int k = 0; k < 2 * N ; k++) { count++; } int M = 10; while ((M--) > 0) { count++; } System.out.println(count); }实例一我们得到基本执行次数为 2*n+10 ,通过大 O 阶表示，func2 的时间复杂度为 O(n)实例 2 void func3(int N, int M) { int count = 0; for (int k = 0; k < M; k++) { count++; } for (int k = 0; k < N ; k++) { count++; } System.out.println(count); }func 3 基本执行次数为 m+n 次，又因为 m、n 都是未知数，时间复杂度为 O(n+m)实例 3 void func4(int N) { int count = 0; for (int k = 0; k < 100; k++) { count++; } System.out.println(count); }实例 3 基本操作执行了 100 次，通过推导大 O 阶方法，常数都为 1 得 func4 的复杂度为 1实例 4 void bubbleSort(int[] array) { for (int end = array.length; end > 0; end--) { boolean sorted = true; for (int i = 1; i < end; i++) { if (array[i - 1] > array[i]) { Swap(array, i - 1, i); sorted = false; } } if (sorted == true) { break; } } }实例 4 我们采用最坏的基本操作执行了 1/2*(n^2) ,大 O 阶推导就是 n^2实例 5 int binarySearch(int[] array, int value) { int begin = 0; int end = array.length - 1; while (begin <= end) { int mid = begin + ((end-begin) / 2); if (array[mid] < value) begin = mid + 1; else if (array[mid] > value) end = mid - 1; else return mid; } return -1; }实例5的最坏基本操作执行次数为 log2N，时间复杂度为 log2N实例 6 long factorial(int N) { return N < 2 ? N : factorial(N - 1) * N; }实例 6 的基本执行次数为 n 次，时间复杂度为 n实例 7 long factorial(int N) { return N < 2 ? N : factorial(N - 1) * N; }实例 7 的基本操作执行次数为 (1-2^N) / -1 , 时间复杂度为 2^n空间复杂度空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少 bytes 的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。常见的空间复杂度计算话不多说，我们直接上代码：实例1 void bubbleSort(int[] array) { for (int end = array.length; end > 0; end--) { boolean sorted = true; for (int i = 1; i < end; i++) { if (array[i - 1] > array[i]) { Swap(array, i - 1, i); sorted = false; } } if (sorted == true) { break; } }实例1使用了常数个空间，所以空间复杂度为 O(1)实例 2 long[] fibonacci(int n) { long[] fibArray = new long[n + 1]; fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n ; i++) { fibArray[i] = fibArray[i - 1] + fibArray [i - 2]; } return fibArray; }实例二它动态开辟了 n 个空间，时间复杂度为 O(n)实例 3long factorial(int N) { return N < 2 ? N : factorial(N-1)*N; }实例 3 递归调用了 n 次，所以空间复杂度为 O(n)

浏览量2222

英勇黄铜

二叉树

树形结构什么是树形结构树是一种非线性的数据结构，它是由 n（ >= 0）个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一个根朝上，叶朝下的倒挂树。特点：有一个特殊的结点，称为根结点，根节点没有前驱结点除根结点外，其他结点被分为m个互不相交的集合树是递归定义的注意：树形结构中，子树是不能有交集的，否则就不是树形结构重要概念结点的度：一个结点含有子树的个数称为该结点的度树的度：一棵树中，所有结点度中的最大值为该树的度叶子结点：度为 0 的结点称为叶结点父结点：如果一个节点有子结点，则这个结点被称为父结点子结点：一个结点含有的子树的根结点称为该结点的子结点根结点：一课树中，没有父结点的结点结点的层次：从根结点开始定义起，根为第一层，根的子结点为第二层，依次类推树的高度或深度：树中结点的最大层次非终端结点或分支结点：度不为 0 的结点兄弟结点：具有相同父结点的结点互称为兄弟结点堂兄弟结点：双亲在同一层的结点互为堂兄弟结点的祖先：从根到该结点所经分支上的所有结点子孙：以某结点为根的子树中任一结点都称为该结点的子孙森林：由 m（ m >= 0 ）棵互不相交的树组成的集合称为森林树的表示形式树的结构相对线性表比较复杂，要储存表示起来比较麻烦，实际中树有许多表示方法：双亲表示法，孩子表示法，孩子双亲表示法，孩子兄弟表示法等等。下面写一种最常用的孩子兄弟表示法。class Node { int value; // 树中存储的数据 Node firstChild; // 第一个孩子引用 Node nextBrother; // 下一个兄弟引用 } 树的应用一般我们文件系统管理就是用树形结构来处理的二叉树什么是二叉树一颗二叉树是结点的有限集合，这个集合：可能为空可能是由一个根结点加上两颗左子树和右子树的二叉树组成的注意：二叉树不存在度大于 2 的结点二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树二叉树有几种情况复合而成：二叉树的性质若根结点的层数为 1 ，则一颗非空的二叉树的第i层上最多有 2^( i-1 ) 个结点若规定只有根结点的二叉树的深度为 1，则深度为K的二叉树的最大结点数是 2^k - 1对任何一个二叉树，如果其叶结点个数为 n0 ，度为2的非叶结点的个数为 n2 ，则有 n0 = n2 + 1具有n个结点的完全二叉树的深度 K 为 log2(n+1) 向上取整对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：若 i>0，双亲序号：(i-1)/2 ；i=0 ，i 为根结点编号，无双亲结点若 2i+1<n ，左孩子序号：2i+1 ，否则无左孩子若 2i+2<n ，右孩子序号：2i+2 ，否则无右孩子二叉树的存储二叉树的存储结构分为：顺序存储和链式存储二叉树的链式存储是通过一个一个节点引用起来的，通常表示的方式有二叉和三叉表示方式// 孩子表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树 } // 孩子双亲表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树 Node parent; // 当前节点的根节点 } 二叉树的基本操作下面是二叉树一些基本功能的代码：public class BinaryTree { static class TreeNode { char val; TreeNode left; TreeNode right; public TreeNode(char val) { this.val = val; } } public TreeNode createTree() { TreeNode A = new TreeNode('A'); TreeNode B = new TreeNode('B'); TreeNode C = new TreeNode('C'); TreeNode D = new TreeNode('D'); TreeNode E = new TreeNode('E'); TreeNode F = new TreeNode('F'); TreeNode G = new TreeNode('G'); TreeNode H = new TreeNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; C.left = F; C.right = G; E.right = H; return A; } //前序遍历 public void preOrder(TreeNode root) { if(root == null) { return; } System.out.print(root.val+" "); preOrder(root.left); preOrder(root.right); } //中序遍历 public void inOrder(TreeNode root) { if(root == null) { return; } preOrder(root.left); System.out.print(root.val+" "); preOrder(root.right); } //后序遍历 public void lastOrder(TreeNode root) { if(root == null) { return; } preOrder(root.right); preOrder(root.left); System.out.print(root.val+" "); } //求tree的节点个数 int Treesize; public int size(TreeNode root) { if(root == null) { return 0; } Treesize++; size(root.left); size(root.right); return Treesize; } public int size1(TreeNode root) { if(root == null) { return 0; } return size1(root.left) + size1(root.right) + 1; } // 获取叶子节点的个数 int getLeafNodeCount(TreeNode root) { if(root == null) { return 0; } if(root.left == null && root.right == null) { return 1; } return getLeafNodeCount(root.left)+getLeafNodeCount(root.right); } // 获取第K层节点的个数 int getKLevelNodeCount(TreeNode root, int k) { if(root == null) { return 0; } if(k==1) { return 1; } return getKLevelNodeCount(root.left, k-1) + getKLevelNodeCount(root.right, k-1); } // 获取二叉树的高度 int getHeight(TreeNode root){ if(root == null) { return 0; } int a = getHeight(root.left); int b = getHeight(root.right); return a > b ? a+1 : b+1; } // 检测值为value的元素是否存在 TreeNode find(TreeNode root, char val) { if(root == null) { return null; } if(root.val == val) { return root; } TreeNode leftNode = find(root.left, val); if(leftNode != null) { return leftNode; } TreeNode rightNode = find(root.right, val); if(rightNode != null) { return rightNode; } return null; }二叉树的遍历前中后序遍历在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L 代表根节点的左子树，R 代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：NLR：前序遍历 (Preorder Traversal 亦称先序遍历) —— 访问根结点 ---> 根的左子树 ---> 根的右子树。LNR：中序遍历 (Inorder Traversal)—— 根的左子树 ---> 根节点 ---> 根的右子树。LRN：后序遍历 (Postorder Traversal) —— 根的左子树 ---> 根的右子树 ---> 根节点。具体代码：//前序遍历 public void preOrder(TreeNode root) { if(root == null) { return; } System.out.print(root.val+" "); preOrder(root.left); preOrder(root.right); } //中序遍历 public void inOrder(TreeNode root) { if(root == null) { return; } preOrder(root.left); System.out.print(root.val+" "); preOrder(root.right); } //后序遍历 public void lastOrder(TreeNode root) { if(root == null) { return; } preOrder(root.right); preOrder(root.left); System.out.print(root.val+" "); }层序遍历除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为 1 ，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第 2 层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历具体代码：class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> array = new ArrayList<>(); if(root == null) { return array; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()) { List<Integer> tmp = new ArrayList<>(); int size = queue.size(); while(size != 0) { TreeNode x = queue.poll(); tmp.add(x.val); size--; if(x.left != null) { queue.offer(x.left); } if(x.right != null) { queue.offer(x.right); } } array.add(tmp); } return array; } }

浏览量2174

英勇黄铜

String类对象的创建与字符串常量池的“神秘交易”

创建对象内的“那些事”话不多说，直接上代码：public static void main(String[] args) { String s1 = "hello"; String s2 = "hello"; String s3 = new String("hello"); String s4 = new String("hello"); System.out.println(s1 == s2); // true System.out.println(s1 == s3); // false System.out.println(s3 == s4); // false }上面这个代码我们发现创建的 String 对象的方式类似，但是结果 s1 和 s2 是同一个对象，但 s3 和 s4 却却不是？这就是要深究到 java 中的常量池了。在 java 中，“hello”，“1234” 等常量经常被频繁使用，java 为了让程序运行的速度更加快，跟节省内存，就为 8 种基本类型和 String 类提供了常量池。java 中引入了：Class 文件常量池：每个 Java 源文件编译后生成的 Class 文件中会保存当前类中的字面常量以及符号信息运行时常量池：在. Class 文件被加载时，Class 文件中的常量池被加载到内存中称为运行时常量池，运行时常量池每个类都会有一份"池" 是编程中的一种常见的, 重要的提升效率的方式, 我们会在遇到各种 "内存池", "线程池", "数据库连接池"字符串常量池字符串常量池在 JVM 中是一个 StringTable 类，实际是一固定大小的 HashTable，它是一种高效查找的数据结构，在不同的 JDK 版本下字符串常量池的位置以及默认大小是不同的：对 String 对象创建的具体分析直接使用字符串常量进行赋值public static void main(String[] args) { String str1 ="hello"; String str2 ="hello"; System.out.println(str1 == str2); } 这里直接通过画图分析：通过 new 创建 String 对象public static void main(String[] args) { String str1 = new String("hello"); String str2 = "hello"; System.out.println(str1 == str2); }这里我们得到一个结论：只要是 new 出来的对象，就是唯一的这里我们可以知道：使用常量串创建 String 类型对象的效率更高，更节省空间。用户也可以将创建的字符串对象通过 intern 方式添加进字符串常量池中intern 方法intern 方法的作用就是将创建的 String 对象添加到常量池中、public static void main(String[] args) { char[] ch = new char[]{'a', 'b', 'c'}; String s1 = new String(ch); // s1对象并不在常量池中 //s1.intern(); 调用之后，会将s1对象的引用放入到常量池中 String s2 = "abc"; // "abc" 在常量池中存在了，s2创建时直接用常量池中"abc"的引用 System.out.println(s1 == s2); }放开前返回的是 false，放开后返回 true：使用方法前，常量池中没有 “abc” ，导致 str2 自己重新创建了一份 “abc”使用方法后，常量池中有了 “abc” ， str2 直接拿过来用就可以了

浏览量2138

英勇黄铜

哈希表

什么是哈希表顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为 O(N)，平衡树中为树的高度，即 O( logN)，搜索的效率取决于搜索过程中元素的比较次数。理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素向该结构中插入元素时：根据待插入的关键码，以此函数计算出该元素的存储位置并按此位置进行存放搜索元素时：堆元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，按此位置取元素比较，若关键码相等，则查找成功这个方式就是哈希方法，哈希方法中使用的转换函数称为哈希函数，构造出来的结构称为哈希表，使用这个方法进行搜索不必进行多次的关键码的比价，使用搜索速度比较快，但是它有发生冲突的可能冲突冲突的概念不同的数据在通过同一个哈希函数的计算出相同的哈希地址的数据元素称为同义词，也就是发生冲突了。冲突的避免冲突的发生是无法避免的，因为我们哈希表的底层数组的容量往往是小于要存储的数据的数量的，这就导致冲突的发生是必然的，我们只能尽量的降低冲突率减少冲突的哈希函数引起哈希冲突的一个原因可能是：哈希函数设计不够合理。这里哈希函数的设计有一些原则：1 哈希函数的定义域必须包括需要存储的全部数据2 哈希函数计算出来的地址可以均匀分布在空间中3 哈希函数需要比较简单常见的哈希函数1. 直接定制法取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀缺点：需要事先知道关键字的分布情况使用场景：适合查找比较小且连续的情况面试题：字符串中第一个只出现一次字符2. 除留余数法设散列表中允许的地址数为 m，取一个不大于 m，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址，Java 中的哈希函数就是使用的这3. 平方取中法假设关键字为 1234，对它平方就是 1522756，抽取中间的 3 位 227 作为哈希地址；再比如关键字为 4321，对它平方就是 8671041，抽取中间的 3 位 671 (或 710) 作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况这里要注意一点：哈希函数虽然设计的越巧妙，哈希冲突的可能性就越小，但是哈希冲突是无法避免的冲突避免的负载因子载荷因子定义为：a = 哈希表中放入元素个数 /哈希表的长度通过图我们可以发现，放冲突率到一个程度的时候，我们就需要通过降低负载因子来降低冲突率。我们知道哈希表放入的数据是不可以变的，那我们只能调整哈希表中的数组大小了。冲突的解决我们一般解决冲突有两种方法：闭散列和开散列闭散列闭散列也叫开放地址法，当发生哈希冲突的时候，如果哈希表没有被装满，那么可以将数据方法冲突位置的下一个空位置去。1. 线性探测比如上面的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，下标为 4 ，因此 44 理论上应该插在该位置，但是该位置已经放了值为 4 的元素，即发生哈希冲突。线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。插入通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素 4，如果直接删除掉，44 查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素 2. 二次探测线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为 Hi = (H0 + i^2) % m , 其中：i = 1,2,3…，是通过散列函数 Hash(x) 对元素的关键码 key 进行计算得到的位置，m 是表的大小.研究表明：当表的长度为质数且表装载因子 a 不超过 0.5 时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子 a 不超过 0.5，如果超出必须考虑增容。因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷开散列/哈希桶Java 中的 HashMap 和 HashSet 底层就是使用的哈希桶开散列法又叫链地址法 (开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。我们知道，桶中放的就是冲突的元素，开散列就是一个大集合中的搜索问题转化为在小集合中做搜索了。冲突严重中的解决方法刚才我们提到了，哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了，那如果冲突严重，就意味着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：1. 每个桶的背后是另一个哈希表2. 每个桶的背后是一棵搜索树哈希桶的模拟实现 public class HashBucket { static class Node { int key; int val; Node next; public Node(int key, int val) { this.key = key; this.val = val; } } private Node[] array = new Node[10]; private int usedsize; private static final float DEFAULT_LOAD_FACTOR = 0.75f; public void put(int key, int val) { Node node = new Node(key, val); int Index = key % array.length; Node cur = array[Index]; while(cur != null) { if(cur.key == key) { cur.val = val; return; } cur = cur.next; } node.next = array[Index]; array[Index] = node; usedsize++; if(usedsize * 1.0f / array.length > DEFAULT_LOAD_FACTOR) { array = resize(array); } } private Node[] resize(Node[] array) { Node[] newArray = Arrays.copyOf(array, 2*array.length); for (int i = 0; i < array.length; i++) { Node cur = array[i]; while(cur != null) { int Index = cur.key % newArray.length; Node nextcur = cur.next; cur.next = newArray[Index]; newArray[Index] = cur; cur = nextcur; } } return newArray; } public int get(int key) { int Index = key % array.length; Node cur = array[Index]; while(cur != null) { if(cur.key == key) { return cur.val; } cur = cur.next; } return -1; } } 性能分析虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是 O(1) 哈希表与 Java 集合的关系1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set2. java 中使用的是哈希桶方式解决冲突的3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）4. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode 一定是一致的。

浏览量2143

英勇黄铜

链表与LinkedList

链表链表的概念与结构链表是一种物理存储结构上非连续的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。大家可以把它理解为现实中的绿皮火车这里要注意：链式在逻辑上是连续的，但是在物理上不一定是连续的现实中的结点一般都是从堆上申请出来的从堆上申请的空间，是按照一定的策略来分配的，所以两次申请的空间可能连续，也可能不连续链表中的结构是多样的，根据情况来使用，一般使用一下结构：单向或双向带头和不带头循环和非循环这些结构中，我们需要重点掌握两种：无头单向非循环链表：结构简单，一般不会单独来存数据，实际上更多的是作为其他数据结构的子结构，如哈希桶，图的邻接表等。无头双向链表：在我们java的集合框架中LinkedList低层实现的就是无头双向循环链表。单向链表的模拟实现下面是单向链表需要实现的一些基本功能：// 1、无头单向非循环链表实现 public class SingleLinkedList { //头插法 public void addFirst(int data){ } //尾插法 public void addLast(int data){ } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){ } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ return false; } //删除第一次出现关键字为key的节点 public void remove(int key){ } //删除所有值为key的节点 public void removeAllKey(int key){ } //得到单链表的长度 public int size(){ return -1; } public void clear() { } public void display() {} }具体实现代码MyLinkedListpackage myLinkedList; import sun.awt.image.ImageWatched; import java.util.List; /** * Created with IntelliJ IDEA. * Description: * User: sun杰 * Date: 2023-09-14 * Time: 10:38 */ public class MyLinkedList implements IList{ static class LinkNode { public int value; public LinkNode next; public LinkNode(int data) { this.value = data; } } LinkNode head; public void createNode() { LinkNode linkNode1 = new LinkNode(12); LinkNode linkNode2 = new LinkNode(23); LinkNode linkNode3 = new LinkNode(34); LinkNode linkNode4 = new LinkNode(56); LinkNode linkNode5 = new LinkNode(78); linkNode1.next = linkNode2; linkNode2.next = linkNode3; linkNode3.next = linkNode4; linkNode4.next = linkNode5; this.head = linkNode1; } @Override public void addFirst(int data) { //实例化一个节点 LinkNode firstNode = new LinkNode(data); if(this.head == null) { this.head = firstNode; return; } //将原第一个对象的地址给新节点的next，也就是将head给新next firstNode.next = this.head; //将新的对象的地址给head头 this.head = firstNode; } @Override public void addLast(int data) { //实例化一个节点 LinkNode lastNode = new LinkNode(data); //找到最后一个节点 LinkNode cur = this.head; while(cur.next!= null) { cur = cur.next; } cur.next = lastNode; //将最后一个节点的next记录插入节点的地址 } @Override public void addIndex(int index, int data) throws indexillgality { if(index < 0 || index > size()) { throw new indexillgality("index不合法"); } LinkNode linkNode = new LinkNode(data); if(this.head == null) { addFirst(data); return; } if(size() == index ) { addLast(data); return; } LinkNode cur = this.head; int count = 0; while(count != index - 1) { cur = cur.next; count++; } linkNode.next = cur.next; cur.next = linkNode; } @Override public boolean contains(int key) { LinkNode cur = this.head; while(cur != null) { if(cur.value == key) { return true; } cur = cur.next; } return false; } @Override public void remove(int key) { if(this.head.value == key) { this.head = this.head.next; return ; } //找前驱 LinkNode cur = findprev(key); //判断返回值 if(cur != null) { //删除 LinkNode del = cur.next; cur.next = del.next; //cur.next = cur.next.next; } } //找删除的前驱 private LinkNode findprev(int key) { LinkNode cur = head; while(cur.next != null) { if(cur.next.value == key) { return cur; } cur = cur.next; } return null; } @Override public void removeAllKey(int key) { if(size() == 0) { return ; } if(head.value == key) { head = head.next; } LinkNode cur = head.next; LinkNode prev = head; while(cur != null) { if(cur.value == key) { prev.next = cur.next; } prev = cur; cur = cur.next; } } @Override public int size() { LinkNode cur = head; int count = 0; while(cur != null) { count++; cur = cur.next; } return count; } @Override public void display() { LinkNode x = head; while(x != null) { System.out.print(x.value + " "); x = x.next; } System.out.println(); } @Override public void clear() { LinkNode cur = head; while(cur != null) { LinkNode curNext = cur.next; cur.next = null; cur = curNext; } head = null; } } indexillgality这时一个自定义异常package myLinkedList; /** * Created with IntelliJ IDEA. * Description: * User: sun杰 * Date: 2023-09-14 * Time: 12:55 */ public class indexillgality extends RuntimeException { public indexillgality(String message) { super(message); } }LinkedListLinkedList 的模拟实现这相当于无头双向链表的实现，下面是它需要的基本功能：// 2、无头双向链表实现 public class MyLinkedList { //头插法 public void addFirst(int data){ } //尾插法 public void addLast(int data){} //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){} //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){} //删除第一次出现关键字为key的节点 public void remove(int key){} //删除所有值为key的节点 public void removeAllKey(int key){} //得到单链表的长度 public int size(){} public void display(){} public void clear(){} }MyLinkedListpackage myLinkedList; import java.util.List; /** * Created with IntelliJ IDEA. * Description: * User: sun杰 * Date: 2023-09-20 * Time: 18:49 */ public class MyLinkedList implements IList { //单个节点 public static class ListNode { private int val; private ListNode prev; private ListNode next; public ListNode(int val) { this.val = val; } } ListNode head; ListNode last; @Override public void addFirst(int data) { ListNode cur = new ListNode(data); if(head == null) { cur.next = head; head = cur; last = cur; }else { cur.next = head; head.prev = cur; head = cur; } } @Override public void addLast(int data) { ListNode cur = new ListNode(data); if(head == null) { head = cur; last = cur; } else { last.next = cur; cur.prev = last; last = cur; } } @Override public void addIndex(int index, int data) throws Indexexception { ListNode cur = new ListNode(data); if(index < 0 || index > size()) { throw new Indexexception("下标越界"); } //数组为空时 if(head == null) { head = cur; last = cur; return ; } //数组只有一个节点的时候 if(head.next == null || index == 0) { head.prev = cur; cur.next = head; head = cur; return; } if(index == size()) { last.next = cur; cur.prev = last; return ; } //找到对应下标的节点 ListNode x = head; while(index != 0) { x = x.next; index--; } //头插法 cur.next = x; cur.prev = x.prev; x.prev.next = cur; x.prev = cur; } @Override public boolean contains(int key) { ListNode cur = head; while(cur != null) { if(cur.val == key) { return true; } cur = cur.next; } return false; } @Override public void remove(int key) { if(head == null) { return; } ListNode cur = head; while(cur != null) { if(cur.val == key) { if(cur.next == null && cur.prev == null) { head = null; last = null; return; }else if(cur.next == null){ cur.prev.next = null; last = cur.prev; return; }else if(cur.prev == null) { head = cur.next; cur.next.prev = null; return ; }else { ListNode frone = cur.prev; ListNode curnext = cur.next; frone.next = curnext; curnext.prev = frone; return ; } } cur = cur.next; } } @Override public void removeAllKey(int key) { if(head == null) { return; } ListNode cur = head; while(cur != null) { if(cur.val == key) { if(cur.next == null && cur.prev == null) { head = null; last = null; } else if(cur.next == null){ cur.prev.next = null; last = cur.prev; }else if(cur.prev == null) { head = cur.next; cur.next.prev = null; }else { ListNode frone = cur.prev; ListNode curnext = cur.next; frone.next = curnext; curnext.prev = frone; } } cur = cur.next; } } @Override public int size() { int count = 0; ListNode cur = head; while(cur != null) { count++; cur = cur.next; } return count; } @Override public void display() { ListNode cur = head; while(cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } @Override public void clear() { if(head == null) { return; } ListNode cur = head.next; while(cur != null) { head = null; head = cur; cur = cur.next; } head = null; } }Indexexception这也是一个自定义异常package myLinkedList; /** * Created with IntelliJ IDEA. * Description: * User: sun杰 * Date: 2023-09-21 * Time: 9:47 */ public class Indexexception extends RuntimeException{ public Indexexception(String message) { super(message); } }java 中的 LinkedListLinkedList 的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来。因为这样，在任意位置插入和删除元素时，是不需要搬移元素，效率比较高。在集合框架中， LinkedList 也实现了 List 接口：注意：LinkedList 实现了 List 接口LinkedList 的底层使用的是双向链表Linked 没有实现 RandomAccess 接口，因此 LinkedList 不支持随机访问LinkedList 的随机位置插入和删除元素时效率较高，复杂度为 O(1)LinkedList 比较适合任意位置插入的场景LinkedList 的使用LinkedList 的构造：一般来说有两种方法：无参构造：List<Integer> list = new LinkedList<>();使用其他集合容器中的元素构造List：public LinkedList(Collection<? extends E> c)栗子：public static void main(String[] args) { // 构造一个空的LinkedList List<Integer> list1 = new LinkedList<>(); List<String> list2 = new java.util.ArrayList<>(); list2.add("JavaSE"); list2.add("JavaWeb"); list2.add("JavaEE"); // 使用ArrayList构造LinkedList List<String> list3 = new LinkedList<>(list2); }LinkedList 的基本方法：public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); // add(elem): 表示尾插 list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); list.add(7); System.out.println(list.size()); System.out.println(list); // 在起始位置插入0 list.add(0, 0); // add(index, elem): 在index位置插入元素elem System.out.println(list); list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst() list.removeFirst(); // removeFirst(): 删除第一个元素 list.removeLast(); // removeLast(): 删除最后元素 list.remove(1); // remove(index): 删除index位置的元素 System.out.println(list); // contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false if(!list.contains(1)){ list.add(0, 1); } list.add(1); System.out.println(list); System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置 System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置 int elem = list.get(0); // get(index): 获取指定位置元素 list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem System.out.println(list); // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回 List<Integer> copy = list.subList(0, 3); System.out.println(list); System.out.println(copy); list.clear(); // 将list中元素清空 System.out.println(list.size()); }LinkedList 的多种遍历foreach：public static void main(String[] args) { List<Integer> list = new LinkedList<>(); list.add(1); list.add(3); list.add(5); list.add(2); list.remove(1); for (int x:list) { System.out.print(x + " "); } } 使用迭代器遍历： ListIterator<Integer> it = list.listIterator(); while(it.hasNext()) { System.out.println(it.next() + " "); } }ArrayList 与 LinkedList的区别

浏览量2144

英勇黄铜

优先级队列（堆）

我们了解过的队列，是一种先进先出的数据结构。但是呢，在有些情况下，数据的出入是有优先级的，一般出队时，可能需要优先级高的元素先出队列，在这种场景下，使用队列就不合适了。优先级就比如：我们使用手机玩游戏的时候，有电话打过来的时候，手机就要先处理打过来的电话。在这种情况下，我们就应该提供两种基本的操作，返回最高优先级对象和新增对象。这种数据结构就是优先级队列。优先级队列的模拟实现在 JDK1.8 中的 priorityQueue 底层使用了堆这种数据结构，而这个堆又是在完全二叉树的基础上进行的调整。什么是堆如果有一个关键码的集合 K = {k0，k1， k2，…，kn-1} ，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆 ( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆堆的性质：堆中某个节点的值总是不大于 (小根堆) 或者不小于 (大根堆) 其父节点的值堆一定是一颗完全二叉树堆的存储方式堆是一颗完全二叉树，可以用层序的规则采用顺序的方式来高效存储这里要注意：对于不是完全二叉树的，就不适合使用顺序存储了，因为要还原二叉树，就要将空节点也保存，这样子就会浪费空间，空间利用率低。我们可以根据以下二叉树的性质来还原二叉树：如果 i 为 0，表示的节点为根结点，否则 i 节点的双亲节点为（i - 1）/ 2如果 2*i+1 小于节点个数，则节点i的左孩子下标为 2*i+1 ,否则没有左孩子如果 2*i+2 小于节点个数，则节点i的右孩子下标为 2*i+1 ，否则没有右孩子堆的创建这里创建堆的方式是使用向下调整的方式来建堆的。想法就是从堆的最后一个节点的父结点开始向下调整，调整完后再向前一个节点向下调整，依次不断到 0 下标的节点调整完后就算建堆成功了。画图分析：建堆的时间复杂度分析这里我们考虑最坏的情况即是一颗满叉树且每一个节点都要调整画图分析：通过上图得知向上调整的时间复杂度为 O(n)向下调整的复杂度会比向上调整的复杂度高上很多，不建议使用它来建堆原因：我们知道向上调整是从最后一层的最后一个节点开始，而向下调整只需要从倒数第二层的最后一个节点开始，而往往最后一层的节点就基本等于前面全部节点加起来之和 -1堆的插入和删除堆的插入堆的插入就只有 4 个步骤：检查空间大小将需插入节点放入最后一个位置再从最后一个位置开始向上调整最后有效位置加一画图分析：堆的删除注意这里的删除是堆顶的元素。具体步骤：将堆顶元素和堆尾元素交换有效位置减一从堆顶开始向下调整画图分析：具体代码import java.util.Arrays; public class MyHeap { private int[] elem; int usedsize; public MyHeap() { this.elem = new int[10]; } //初始化elem数组 public void initElem(int[] array) { for(int i = 0; i < array.length; i++) { elem[i] = array[i]; usedsize++; } } //创建大根堆 public void createHeap() { for(int parent = (usedsize-1-1)/2; parent>=0; parent--) { siftDown(parent, usedsize); } } private void siftDown(int parent, int len) { //左孩子 int child = 2*parent+1; while(child < len) { if(child+1 < len && elem[child] < elem[child+1] ) { child += 1; } if(elem[child] > elem[parent]) { //交换 int temp = elem[child]; elem[child] = elem[parent]; elem[parent] = temp; parent = child; child = 2*parent+1; }else { break; } } } //插入元素 public void push(int val) { //满了 if(elem.length == usedsize) { elem = Arrays.copyOf(elem, elem.length * 2); } elem[usedsize] = val; siftUp(usedsize); usedsize++; } private void siftUp(int child) { int parent = (child - 1) / 2; while(child > 0 ) { if(elem[child] > elem[parent]) { int temp = elem[child]; elem[child] = elem[parent]; elem[parent] = temp; child = parent; parent = (child - 1) / 2; }else { break; } } } /* * * 删除元素 * */ public void pop() { if(isEmpty()) { return ; } int temp = elem[0]; elem[0] = elem[usedsize-1]; elem[usedsize-1] = temp; usedsize--; int parent = 0; int child = 2 * parent + 1 ; while(child < usedsize) { if(child+1<usedsize && elem[child] < elem[child+1]) { child+=1; } if(elem[child] > elem[parent]) { int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; parent = child; child = 2*parent+1; }else { break; } } } public boolean isEmpty() { return usedsize == 0; } } priorityQueuejava 集合中提供了 priorityQueue 和 priorityBlockingQueue 两种类型的优先级队列，priorityQueue 是线程不安全的，PriorityQueue 是线程安全的。使用 priorityQueue 的注意事项:1 使用时必须导入 PriorityQueue 所在的包：import java.util.PriorityQueue;2 priorityQueue 中放置元素必须要能够比较大小，不能插入无法比较大小的对象，不然会抛出 ClassCastException 异常3 不能插入 null 对象，不然会 1 抛出 nullpointerException没有容量限制，任意插入多个元素，内部会自动扩容4 插入和删除元素的时间复杂度都是 O(logn)5 priorityQueue 的底层使用堆数据结构6 priorityQueue 默认情况下是小堆---即每次获取到的元素都是最小的元素，想要建立大堆需要自己传比较器priorityQueue 的使用优先级队列的构造方法static void TestPriorityQueue(){ // 创建一个空的优先级队列，底层默认容量是11 PriorityQueue<Integer> q1 = new PriorityQueue<>(); // 创建一个空的优先级队列，底层的容量为initialCapacity PriorityQueue<Integer> q2 = new PriorityQueue<>(100); ArrayList<Integer> list = new ArrayList<>(); list.add(4); list.add(3); list.add(2); list.add(1); // 用ArrayList对象来构造一个优先级队列的对象 // q3中已经包含了三个元素 PriorityQueue<Integer> q3 = new PriorityQueue<>(list); System.out.println(q3.size()); System.out.println(q3.peek()); } 一般在默认的情况下，PriorityQueue队列是小堆，需要变成大堆需要提供比较器： class IntCmp implements Comparator<Integer>{ @Override public int compare(Integer o1, Integer o2) { return o2-o1; } } 插入，删除，获取优先级最高的元素 static void TestPriorityQueue2() { int[] arr = {4, 1, 9, 2, 8, 0, 7, 3, 6, 5}; // 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好 // 否则在插入时需要不多的扩容 // 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低 PriorityQueue<Integer> q = new PriorityQueue<>(arr.length); for (int e : arr) { q.offer(e); } System.out.println(q.size()); // 打印优先级队列中有效元素个数 System.out.println(q.peek()); // 获取优先级最高的元素 // 从优先级队列中删除两个元素之和，再次获取优先级最高的元素 q.poll(); q.poll(); System.out.println(q.size()); // 打印优先级队列中有效元素个数 System.out.println(q.peek()); // 获取优先级最高的元素 q.offer(0); System.out.println(q.peek()); // 获取优先级最高的元素 // 将优先级队列中的有效元素删除掉，检测其是否为空 q.clear(); if (q.isEmpty()) { System.out.println("优先级队列已经为空!!!"); } }这里要注意优先级队列扩容说明：如果容量小于 64 时，就是按 oldCapacity 的两倍大小来扩容如果容量大于等于 64 时，就是按 oldCapacity 的 1.5 倍大小扩容如果扩容后的容量大小大于整型的最大值，则按整型的最大值来扩容堆的应用用堆为数据结构来封装优先级队列Java 中的 priorityQueue 底层就是用堆来实现的堆排序堆排序就是使用堆的思想来进行排序1. 建堆升序：建大堆降序：建小堆2. 使用堆元素删除思想来进行排序交换堆顶和堆尾元素，然后向下调整

浏览量2146

英勇黄铜

八大排序算法（内含思维导图和画图分析）

什么是排序排序：就是让一串数据，按照其中的某个或某些关键字大小，递增或递减排列起来的操作。内部排序：数据元素全部放在内存中的排序外部排序：数据元素太多不能同时放在内存中的时候，根据排序过程中的要求不能在内外存之间移动的排序。稳定性：在经过排序后，这些数据的相对次序还保持不变，则这种排序算法就是稳定的常见的排序算法插入排序基本思想就是将待排序的记录按关键值的大小一个一个插入已经先排好有序的序列中，直到所有的记录插入完为止，这样就可以得到一个新的有序序列。我们打牌时的摸牌过程就是这个思想：直接插入排序它的操作就是从第二个元素开始向前比较，前面的元素大就交换，把前面的元素比较完，这就是第一轮。然后第二轮就是开始从第三个元素向前比较，以此到最后一个元素。这里比较过后的元素就是有序的了，所以要是在比较的过程中发现前面的元素比比较元素小就不必继续比较下去了，直接进入下一轮。特点：元素越有序，直接插入排序的时间效率越来越高时间复杂度：O(N^2)空间复杂度：O(1)稳定性：稳定具体代码//直接插入排序 /* *时间复杂度 O(n^2) *空间复杂度 O(1) *稳定性：稳定 */ public static void initorderSort(int[] array) { for(int i = 1; i < array.length; i++) { int tmp = array[i]; int j = 0; for(j = i - 1; j >= 0; j--) { if(array[j] > array[j+1]) { array[j+1] = array[j]; }else { break; } array[j+1] = tmp; } } } 画图分析希尔排序它的基本思想就是选定一个整数 gap ，把需要排序的数据分成若干份，将间隔这个数的数据放在一组，并对每个组进行直接插入排序，这是一轮。然后再重复以上步骤，只不过 gap 每次 /2 ，知道 gao=1 时，全部的数据再排序就排好序了。特性：希尔排序是对直接插入排序的优化gap>1 时，属于预排序，这样可以让排序更加接近有序。gap==1 时，数据就是有序了，这时直接插入排序效率就是会很高时间复杂度：O(N^1.25~1.6*N^1.25)空间复杂度：O(1)稳定性：稳定具体代码public static void shellSort(int[] array) { int gap = array.length; while(gap > 1) { gap /= 2; shell(array, gap); } } private static void shell(int[] array, int gap) { for(int i = gap; i < array.length; i++) { int tmp = array[gap]; int j = 0; for (j = i - gap; j >= 0; j-=gap) { if(array[j] > tmp) { array[j+gap] = array[j]; }else { break; } } array[j+gap] = tmp; } } 画图分析选择排序基本思想每一次从需要排序中的元素中挑出最小的元素放在数据的起始位置，不断重复以上操作，每操作完一轮最小元素放入的位置要往后走一个，直到数全部排序完成。直接选择排序在数据中 array[i] ~ array[n-1] 中选择最小的元素将他与这组数据的第一个元素交换在剩下的 array[i] ~ array[n-1] 中，不断重复以上操作特性：这个排序易理解，但效率地下，实际很少使用时间复杂度：O(N^2)空间复杂度：O(1)稳定性：不稳定具体代码public static void selectSort(int[] array) { for (int i = 0; i < array.length; i++) { int minIndex = i; for (int j = i+1; j < array.length; j++) { if(array[minIndex] > array[j]) { minIndex = j; } } int temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; } }画图分析堆排序堆排序是指利用堆这种数据结构设计的一种排序算法，它是通过堆来进行的选择数据。排升序是建大堆，排降序建小堆。特性：堆排序使用堆来排序，效率就有明显的提高时间复杂度：O(N*logN)空间复杂度：O(1)稳定性：稳定具体代码public static void heapSort(int[] array) { createHeap(array); int end = array.length - 1; while(end > 0) { int tmp = array[0]; array[0] = array[end]; array[end] = tmp; siftDowm(array,0, end); end--; } } private static void siftDowm(int[]array, int parent, int len) { int child = 2*parent + 1; while(child < len) { if(child+1 < len && array[child+1] > array[child]) { child+=1; } if(array[child] > array[parent]) { int tmp = array[child]; array[child] = array[parent]; array[parent] = tmp; parent = child; child = parent*2 + 1; }else { break; } } } private static void createHeap(int[] array) { if(array.length == 0) { return; } int parent = (array.length - 1 - 1) / 2; for (int i = parent; i >= 0 ; i--) { siftDowm(array, parent, array.length); } }画图分析交换排序基本思想就是根据数据中两个元素的比较结果来交换这两个数据的位置，它的特点就是将值大的元素向后移动，小的向前移动冒泡排序冒泡排序就是进行 n-1 趟比较排序，每一趟都比较 n-1 次，每比较完一次都减一次比较特性：易于理解时间复杂度：O(N^2)空间复杂度：O(1)稳定性：稳定具体代码 public static void bubbleSort(int[] array) { int len = array.length; for(int i = 0; i < len - 1; i++) { boolean flag = false; for(int j = 0; j < len - 1 - i; j++) { if (array[j] > array[j+1]) { int tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; flag = true; } } if(!flag) { break; } } }画图分析快速排序它是一种二叉树结构的交换排序算法。基本思想就是去待排序中的任意一个元素作为基准值，按照这个基准值将数据分割为两个子序列，左边的都小于基准值，右边的都大于基准值，然后左右子序列再重复以上操作，知道最后元素都已经有序。特性：快速排序的性能和使用场景都是比较好的时间复杂度：O(N*logN)空间复杂度：O(logN)稳定性：不稳定具体代码递归版 public static void quickSort(int[] array, int start, int end) { if(start >= end) { return; } int key = array[start]; int left = start; int right = end; while(left < right) { while(left < right && array[right] >= key) { right--; } while(left < right && array[left] <= key) { left++; } swap(array, left, right); } swap(array, start, left); //左子树 quickSort(array, start, left - 1); //右子树 quickSort(array, left+1, end); }非递归版public static void quickSortnor(int[] array, int start, int end) { Stack<Integer> stack = new Stack<>(); int pivot = partition(array, start, end); if(pivot- 1 > start) { stack.push(start); stack.push(pivot - 1); } if(pivot+1 < end) { stack.push(pivot + 1); stack.push(end); } while(!stack.isEmpty()) { int right = stack.pop(); int left = stack.pop(); pivot = partition(array, left, right); if(pivot - 1 > left) { stack.push(start); stack.push(pivot - 1); } if(pivot+1 < right) { stack.push(pivot + 1); stack.push(end); } } } private static int partition(int[] array, int left, int right) { int i = left; int j = right; int pivot = array[left]; while (i < j) { while (i < j && array[j] >= pivot) { j--; } array[i] = array[j]; while (i < j && array[i] <= pivot) { i++; } array[j] = array[i]; } array[i] = pivot; return i; } 画图分析递归：非递归：归并排序基本思想归并排序是建立在归并操作上的一种有效的排序算法，它采用的是分治法，将已有序的序列合并，得到完全有序的序列。就是先让子序列有序，再使子序列何合并有序，这样叫做二路归并。特性归并排序的缺点在于需要O(N)的空间复杂度，归并排序的思考是解决在磁盘中的外存排序问题时间复杂度：O(N*logN)空间复杂度：O(N)稳定性：稳定具体代码递归版//归并排序 /* *时间复杂度:O(n*logn) *空间复杂度 O(logn) *稳定性：稳定 */ public static void mergeSort(int[] array, int start, int end) { if(start >= end) { return ; } //分解 int mid = (start + end) / 2; mergeSort(array,start, mid); mergeSort(array, mid+1, end); //合并 merge(array, start, mid, end); } private static void merge(int[] array, int start, int mid, int end) { int s1 = start; int s2 = mid; int e1 = mid+1; int e2 = end; int i = 0; int[] arr = new int[end - start + 1]; while(s1 <= s2 && e1<=e2) { if(array[s1] < array[e1]) { arr[i++] = array[s1++]; }else { arr[i++] = array[e1++]; } } while(s1 <= s2) { arr[i++] = array[s1++]; } while(e1 <= e2) { arr[i++] = array[e1++]; } //把排好序的数组放到原来的数组中 for (int j = 0; j < arr.length; j++) { array[j+start] = arr[j]; } } 非递归版public static void mergesortNor(int[] array) { int gap = 1; while(gap < array.length) { for (int i = 0; i < array.length; i+=2*gap) { int left = i; int mid = left + gap - 1; int right = mid + gap; //防止越界 if(mid >= array.length) { mid = array.length - 1; } if(right >= array.length) { right = array.length - 1; } merge(array, left, mid, right); } gap*=2; } } 画图分析递归：非递归：海量数据的排序处理外部排序：排序过程需要在磁盘等外部存储进行的排序前提：内存只有一个 G，需要排序的数据有 100G因为内存中无法把所有的数据发放下，所以需要外部排序，归并排序就是最常用的外部排序处理方式：先将文件分成 200 份，每个 512M分别对 512M 排序，因为内存已经可以放的下，排序进行 2 路归并，堆 200 份文件过归并过程，最后就会有序排序算法复杂度与稳定性计数排序基本思想计数排序是对哈希直接定址法的应用1 统计相同的元素次数2 根据统计的结果将序列回收到原来的序列中具体代码 public static void countSort(int[] array) { //确定长度 int max = 0; int min = 0; for (int i = 0; i < array.length; i++) { if(array[i] > max) { max = array[i]; } if(array[i] < min) { min = array[i]; } } int[] count = new int[max - min + 1]; int j = 0; //将相同的数的次数存储到计数数组中 for(int i = 0; i < array.length; i++) { count[array[i] - min]++; } //遍历计数数组把实际的数据写到array中 for (int i = 0; i < count.length; i++) { while(count[i] > 0) { array[j++] = i+min; count[i]--; } } } 画图分析特性计数排序在数据范围集中时，效率很高，但是这种情况比较少时间复杂度：O(范围)空间复杂度：O(范围)稳定性：稳定

浏览量2136