小奏

Leetcode 双指针 下面是的题目都会涉及双指针，除此外，还有 Leetcode3 最长不重复子串，在 hash 表部分讲过了 快排中 二分中 … 移动零-Leetcode 283 123456789101112131415161718192021public class MoveZeroesLeetcode283 { static void moveZeroes(int[] nums) { int i = 0; int j = 0; while (j < nums.length) { if (nums[j] != 0) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; i++; } j++; } } ...

Backtracking Algorithm 入门例子 12345678910111213141516public class Backtracking { public static void main(String[] args) { rec(1, new LinkedList<>()); } static void rec(int n, LinkedList<String> list) { if (n == 3) { return; } System.out.println("before:" + list); list.push("a"); rec(n + 1, list); list.pop(); System.out.println("after:" + list);  ...

Divide and Conquer 概述 分治思想 将大问题划分为两个到多个子问题 子问题可以继续拆分成更小的子问题，直到能够简单求解 如有必要，将子问题的解进行合并，得到原始问题的解 之前学过的一些经典分而治之的例子 二分查找 快速排序 归并排序 合并K个排序链表 - LeetCode 23 二分查找 1234567891011121314151617public static int binarySearch(int[] a, int target) { return recursion(a, target, 0, a.length - 1);}public static int recursion(int[] a, int target, int i, int j) { if (i > j) { return -1; } int m = (i + j) >>> 1; if (target < a[m]) { return ...

Dynamic-Programming Fibonacci 123456789101112131415161718public class Fibonacci { public static void main(String[] args) { System.out.println(fibonacci(13)); } public static int fibonacci(int n) { int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; if (n < 2) { return dp[n]; } for (int i = 2; i <= n; i++) { dp[i] = dp[i - 2] + dp[i - 1]; } return dp[n];  ...

Greedy Algorithm 贪心例子 称之为贪心算法或贪婪算法，核心思想是 将寻找最优解的问题分为若干个步骤 每一步骤都采用贪心原则，选取当前最优解 因为没有考虑所有可能，局部最优的堆叠不一定让最终解最优 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择，从而希望导致结果是最好或最优的算法。这种算法通常用于求解优化问题，如最小生成树、背包问题等。 贪心算法的应用： 背包问题：给定一组物品和一个背包，每个物品有一定的重量和价值，要求在不超过背包容量的情况下，尽可能多地装入物品。 活动选择问题：在一个活动集合中，每次只能参加一个活动，问如何安排时间以最大化所有活动的收益。 编辑距离问题：给定两个字符串，求它们之间的最小编辑距离(即将一个字符串转换为另一个字符串所需的最少操作次数)。 网络流问题：给定一张有向图和一些起点和终点，求最大流量。 找零问题：给定一定数量的硬币和需要找零的金额，求使用最少的硬币数。 常见问题及解答： 贪心算法一定会找到最优解吗？ 答：不一定。贪心算法只保证在每一步选择中都是最优的，但并不能保证整个问题的最优解。例如，背包问题 ...

图 概念 图是由顶点（vertex）和边（edge）组成的数据结构，例如 123456graph LR A--->B A--->C B--->D C--->D 该图有四个顶点：A、B、C、D 以及四条有向边，有向图中，边是单向的 有向 vs 无向 如果是无向图，那么边是双向的，下面是一个无向图的例子 12345graph LR A---B A---C B---D C---D 度 度是指与该顶点相邻的边的数量 12345678910graph LR A((A))---B((B)) A---C((C)) B---D((D)) C---D D---E((E)) D---F((F)) E---F A & B & C & D & E & F 例如上图中 A、B、C、E、F 这几个顶点度数为 2 D 顶点度数为 4 有向图中，细分为入度和出度，参见下图 12345678910graph LR A((A))-->B((B)) ...

排序算法 概述 比较排序算法 算法 最好 最坏 平均 空间 稳定 思想 注意事项 冒泡 O(n) O(n2n^2n2) O(n2n^2n2) O(1) Y 比较 最好情况需要额外判断 选择 O(n2n^2n2) O(n2n^2n2) O(n2n^2n2) O(1) N 比较 交换次数一般少于冒泡 堆 O(nlognnlognnlogn) O(nlognnlognnlogn) O(nlognnlognnlogn) O(1) N 选择 堆排序的辅助性较强，理解前先理解堆的数据结构 插入 O(n) O(n2n^2n2) O(n2n^2n2) O(1) Y 比较 插入排序对于近乎有序的数据处理速度比较快，复杂度有所下降，可以提前结束 希尔 O(nlogn) O(n2n^2n2) O(nlognnlognnlogn) O(1) N 插入 gap序列的构造有多种方式，不同方式处理的数据复杂度可能不同 归并 O(nlognnlognnlogn) O(nlognnlognnlogn) O(nlognnlognnlogn) O(n) Y 分治 需要额外的O(n)的存储空 ...

哈希表 第一版 未考虑 hash 码的生成，假定该 hash 码由我们提供 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148public class HashTable { // 节点类 static class Entry { int hash; // 哈希码 Object key; // 键 O ...

B 树 ai 问题列表 请用中文回答：B-树历史 请用中文回答：100万的数据使用 avl 树来存储，树高是多少? 20 请用中文回答：100万的数据，如果存储到B-树(最小度数是500)，那么树高大约是多少? 3 请用中文回答：B-树的特性有哪些？ 概述 历史 B树（B-Tree）结构是一种高效存储和查询数据的方法，它的历史可以追溯到1970年代早期。B树的发明人Rudolf Bayer和Edward M. McCreight分别发表了一篇论文介绍了B树。这篇论文是1972年发表于《ACM Transactions on Database Systems》中的，题目为"Organization and Maintenance of Large Ordered Indexes"。 这篇论文提出了一种能够高效地维护大型有序索引的方法，这种方法的主要思想是将每个节点扩展成多个子节点，以减少查找所需的次数。B树结构非常适合应用于磁盘等大型存储器的高效操作，被广泛应用于关系数据库和文件系统中。 B树结构有很多变种和升级版，例如B+树，B*树和SB树等。这些变种和升级版本都 ...

红黑树 概述 历史 红黑树是一种自平衡二叉查找树，最早由一位名叫Rudolf Bayer的德国计算机科学家于1972年发明。然而，最初的树形结构不是现在的红黑树，而是一种称为B树的结构，它是一种多叉树，可用于在磁盘上存储大量数据。 在1980年代早期，计算机科学家Leonard Adleman和Daniel Sleator推广了红黑树，并证明了它的自平衡性和高效性。从那时起，红黑树成为了最流行的自平衡二叉查找树之一，并被广泛应用于许多领域，如编译器、操作系统、数据库等。 红黑树的名字来源于红色节点和黑色节点的交替出现，它们的颜色是用来维护树的平衡性的关键。它们的颜色具有特殊的意义，黑色节点代表普通节点，而红色节点代表一个新添加的节点，它们必须满足一些特定的规则才能维持树的平衡性。 红黑树也是一种自平衡的二叉搜索树，较之 AVL，插入和删除时旋转次数更少 红黑树特性 所有节点都有两种颜色：红:red_circle:、黑:black_circle: 所有 null 视为黑色:black_circle: 红色:red_circle:节点不能相邻 根节点是黑色:black_circle: ...