本节将主要聚焦在二分查找方法，其应用场景为： ❝如果面试题要求在排序的数组（或者部分排序的数组）中查找一个数字或是统计某个数字出现的次数，那么我们可以尝试用「二分查找算法」。...数组的可视化如下图所示，我们将旋转点（即目标元素）左侧的数组称为「左排序数组」，将其右边的数组称为「右排序数组」。一种极端情况是左排序数组中没有元素，即未进行旋转（在本解法中并不需要单独讨论）。 ?...当 numbers[m] == numbers[j] 时，我们选择将右边界指针减一来缩小查找范围，为了证明此操作的正确性，我们只需要证明执行操作后，旋转点 k 仍在 [i,j] 区间内即可。...「情况一」：如果 m 在右排序数组中，此时数组 内所有元素相等，执行 j=j-1 操作后只会抛弃一个重复值，旋转点仍位于区间内； 「情况二」：如果 m 在左排序数组中，此时要再根据旋转点的值 numbers...[k] == numbers[j]：若 j>k，则执行操作后仍满足要求；若 j==k，此时执行操作后旋转点 k 「可能不」位于区间内，但是根据数组的特点，区间 [i,m] 内的元素一定都等于旋转点的值，
例如对一个空栈进行 N 次连续的 push() 调用需要访问数组的元素为 N+4+8+16+...+2N=5N-4（N 是向数组写入元素，其余的都是调整数组大小时进行复制需要的访问数组操作），均摊后每次操作访问数组的平均次数为常数...ThreeSumSlow 该算法的内循环为 if (nums[i] + nums[j] + nums[k] == 0) 语句，总共执行的次数为 N(N-1)(N-2) = N3/6-N2/2+N/3，因此它的近似执行次数为...可以利用这个特性找出数组的第 k 个元素。 该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N。...左旋转 因为合法的红链接都为左链接，如果出现右链接为红链接，那么就需要进行左旋转操作。...插入 先将一个节点按二叉查找树的方法插入到正确位置，然后再进行如下颜色操作： 如果右子节点是红色的而左子节点是黑色的，进行左旋转； 如果左子节点是红色的，而且左子节点的左子节点也是红色的，进行右旋转
还将对这些应用场景的优缺点进行分析，并提供相应的类代码和测试用例。 正文简介 数组在Java中是一种基本的数据结构，可以表示连续的内存空间。它可以用来存储一组相同数据类型的元素。...Java中的数组可以是一维或多维的，而且数组的大小一旦确定就无法更改。 本文将介绍数组的几种常用但不为人知的应用场景，包括二维数组的应用，数组的旋转、查找、去重等操作，以及在算法中使用数组等场景。...并且将分析这些应用场景的优缺点，并提供相应的示例代码和测试用例。源代码解析二维数组的应用 二维数组是由多个一维数组组成的，可以理解为一个表格，行和列分别对应数组的第一维和第二维。...数组的旋转、查找、去重等操作数组的旋转 数组的旋转是将数组中的元素按照某个规律进行旋转。在实际工作中，数组的旋转操作常用于图像处理、游戏等方面。 ...在 main 方法中，没有任何代码。执行结果：小结 数组是Java中常用的数据结构之一，能够优化算法并提高性能。
大小固定：一旦定义了数组的大小，就不能改变。如果需要更大的存储空间，需要重新定义一个新的数组。 元素类型相同：数组中的所有元素必须是相同的数据类型。...易于实现：数组是一种简单的数据结构，容易实现和操作。 数组的缺点： 大小固定：数组的大小是固定的，不能动态扩展。如果需要更多的存储空间，需要重新定义一个新的数组，这会增加额外的开销。...本课程中我们介绍下和Java关联性比较强的非线性结构-树 1.2.1 树 树[Tree]是n（n>=0)个结点的有限集。n=0时称为空树。...三种操作：左旋、右旋和变色 操作 描述 左旋 以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。...旋转操作 左旋：以某个节点作为旋转点，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变。 右旋：以某!
如果添加操作后，HashMap 中的键值对数目超过了负载因子乘以当前数组的长度，则进行 rehash 操作，即将数组大小扩大一倍，并将旧的键值对重新分桶到新数组中。 ...TreeMap中每个键值对存储在一个节点中，该节点包含键、值、左子节点和右子节点等信息。底层数据结构 TreeMap底层的数据结构是一棵红黑树，每个节点都包含一个键值对。...红黑树是一种自平衡二叉搜索树，它能够保持树的高度平衡，因此能够保证查询、插入和删除操作都能够在O(log n)的时间复杂度内完成。 ...具体地说，我们需要执行以下步骤：1.创建一个新的节点e来保存键值对，并将其父节点设置为parent。2.将e插入到树中，将其置于parent的左子树或右子树中，具体取决于cmp的值。...测试用例下面是一个简单的示例，演示如何使用Map接口：测试代码演示package com.demo.javase.day65;import java.util.HashMap;import java.util.Map
以 Java 语言为例，当声明一个数组后，数组变量会指向数组对象的起始地址，也就是第一个元素的位置，如下图以此看来，当查询数组中的某个元素时，通过下标就可以计算出这个元素的内存地址，比如想查找下标为2的元素...以 Java 为例，一个节点的结构是这样表示的：public class Node { //存储数据元素的数据域 private T value; //下一个节点地址的指针域...以下图为例，当插入节点5时，节点7左右子树的高度差为2，这时候节点7就需要进行右旋保持树的平衡。右旋就是：以某个节点为旋转点，其左子节点变为其父节点，左子节点的右子节点变为其左子节点，右子节点不变。...虽然AVL通过旋转保持树的平衡，但是在插入和删除频繁的场景中，频繁的旋转会导致性能下降，为解决此问题红黑树被提出。红黑树红黑树大家应该都比较耳熟，但是理不理解是另一回事，面试的时候应该经常会被问到。...红黑树后面专门写一篇文章介绍，这里先给结论：红黑树的旋转次数相对于AVL树来说较少，因此在插入、删除等操作较多的情况下，通常使用红黑树，比如大家都知道的HashMap。
层序遍历的实现需要利用队列结构，首先将根节点入队，当队列中有元素时，执行以下操作：将队首元素出队，对该元素进行操作，并将该元素的左子树、右子树依次入队。 层序遍历并不需要用到递归。...根结点的右子树个数+1=森林中树的数量； 前序遍历一棵树等价于前序遍历该树对应的二叉树； 后序遍历一棵树等价于中序遍历该树对应的二叉树。...（递归执行，与树的前中后序遍历思路相似） 在代码实现时，利用了一个辅助数组visit，用于标记该结点是否已经被访问。...辅助空间：n，一个与原待排序对象数组同样大小的辅助数组。 归并排序算法中，递归深度为O(logn)，对象关键字的比较次数为O(nlogn)。算法总的时间复杂度为O(nlogn)。...例：棋盘覆盖 在一个2^k\times 2^k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
思路： 在Java和C中，对字符串的处理略有不同，在C中字符串是以字符数组的形式存储的，并且在字符串或者字符数组中都有一个结束符"\0"；而在Java中，却没有这样的结束符，所以本题在Java下的处理与...思路： 主要考察的是二叉搜索树和后序遍历的性质，其中后序遍历的最后一个数是根结点，在二叉搜索树中，左子树的值都小于根结点，右子树的值都大于跟结点，这样便能构造左右子树的序列，用同样的方法分别处理左右子树序列...思路： 在遍历数组的过程中纪录两个量，一个是数组中的数字，一个是次数，当下一个数字和我们保存的一致时则次数加1，当不一致时次数减1，当次数为0时，重置两个量。...思路： 在Java中可以把字符串转换成字符数组处理，可以使用HashMap的数据结构存储，其中key为字符，value为对应出现的次数，这样通过两次遍历字符数组就可以找出，其中，第一次是构建HashMap...但是在Java中声明对象数组必须对数组中的对象初始化才能开辟空间。所以我这题不知道利用Java怎么实现。书中的其他几种方式主要是利用C++的一些特性。如果有人知道，可以告诉我，谢谢。
当键的数量很大时，将以块形式从磁盘读取数据，与主存储器访问时间相比，磁盘访问时间非常高。 B树是一种自平衡搜索树，设计的主要思想是减少磁盘访问次数。...O(log n) p.s:B树由术语最小度t定义，t的值取决于磁盘块的大小，数值上m = 2t。...从B树中删除键的各种情况(设删除键k所在节点为n)： k所在节点n为树中节点(非叶子节点也非根节点)，则根据以下不同的情况执行子节点key上移或合并完成删除操作 a....节点n中在k之前的子节点kln(key left node)键数至少有m/2个，则在kln节点中查找最接近k的键k0，将k0替换k，结束删除操作。...节点n中在k之前的子节点kln键数少于m/2个，且k后的子节点krn(key的右侧节点)键数至少有m/2个，则在krn节点中查找最接近k的键k0，将k0替换k，结束删除操作。
一、用go语言，写出 RIGHT-ROTATE 的伪代码。 文心一言： 在计算机科学中，右旋转（RIGHT-ROTATE）是一种常见的操作，通常用于数组或链表。...以下是一个使用Go语言实现右旋转的伪代码： func rightRotate(arr []int, k int) []int { n := len(arr) k %= n //...智谱清言： 在Go语言中实现一个RIGHT-ROTATE操作，我们可以通过以下步骤来完成： 1.定义一个函数，接受两个参数：一个表示要旋转的节点的指针，以及表示要旋转的次数的整数。...此外，这段代码假设了旋转次数k是有效的，并没有处理k大于链表长度的情况，这在实际应用中也需要考虑。 通义千问： 在二叉树的旋转操作中，右旋（RIGHT-ROTATE）通常用于平衡树的操作。...在实际的红黑树实现中，这个指针是必要的，因为它允许我们在旋转操作中正确地更新父节点的子节点指针。 混元： 在红黑树中，RIGHT-ROTATE操作用于将一个节点的左子节点旋转为右子节点。
面试题33：把数组排成最小数：首先将数组中的数字全部转换为字符串存储在一个新的数组中，然后比较每两个数字串的拼接的mn和nm的大小，若mn<nm，则m更小，反之n更小，然后把更小的数放入一个新的List...面试题36：数组中的逆序对：这道题可以这么想，我们要找到数组中的逆序对，可以看做对数据进行排序，需要交换数组中的元素的次数，但是防止相同大小的元素发生交换，因此需要选择一个稳定的排序方法，记录发生交换的次数...面试题45：n个骰子的点数：用两个数组来存储骰子点数的每一个总数出现次数。在一次循环中，第一个数组中的第n个数字表示骰子和为n出现的次数。...注意考虑测试用例为0的情况。 面试题49：不用加减乘除做加法：将两个数的加法看作两步，第一步是两个数相加但是不进位，第二步是记录之前的两数相加应该进位的地方加上前一个相加但是不进位的数。...m，n的大小，如果当前节点的值均大于m，n，则在当前节点的左子树继续操作，如果当前节点均小于m，n，则在当前节点的右子树继续操作，反之，则当前结点是最小公共祖先。
I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。 输出格式 共一行，将整个链表从头到尾输出。 数据范围 1≤M≤100000 所有操作保证合法。...其每个结点的值，均小于等于左右子节点，即根节点为整棵树的最小值 操作思想 存储方式：用一维数组存储，设根节点的下标是i,则左儿子是2*i，右儿子是2*i+1 //对无序的一维数组进行建堆(小根堆) for...不考虑对堆中的数据进行修改 模板 ////以小根堆为例 const int N=1e6+10; //堆的大小 int h[N]; //h[N]为堆 int idx; //idx表示当前的结点在数组中的下标...输入格式 第一行包含整数 N，表示操作数量。 接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。...字符串中只包含大小写英文字母和数字。 输入格式 第一行包含整数 n 和 m，表示字符串长度和询问次数。 第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。
最核心的逻辑就是函数 N 了，它做的其实是把 T 的数组长度放大 10 倍再追加上当前数量的 1 在数组末尾。...[] 有 10 个，所以 12 个 1 变成 120 个，加上映射表中 3，一共有 123 个 1 总结一下，就是将数字 T 变成字符串，从最左侧开始获取，每次都把已经积累的数组数量乘以 10 再追加上当前值数量的...never : Q]: T[Q] } 但不匹配测试用例，原因是最终类型正确，但因为分成了两个对象合并无法匹配成一个对象，所以需要用一点点 Magic 行为合并： // 本题答案 type PartialByKeys...因为 Omit 中 K 有来自于 keyof T 的限制，而测试用例又包含 unknown 这种不存在的 Key 值，此时可以用 extends PropertyKey 处理此场景。...K> 虽然本身逻辑没错，但无法把必选覆盖为可选，因此测试用例都挂了。
因此，除去可能的插入外，所有树的操作都可以以时间O(logN)执行。...(k1->left); rotateWithRightChild(k1); } 5 高级数据结构 大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话...B树中的每个结点根据实际情况可以包含大量的关键字信息和分支(当然是不能超过磁盘块的大小，根据磁盘驱动(disk drives)的不同，一般块的大小在1k~4k左右)；这样树的深度降低了，这就意味着查找一个元素只要很少结点从外存磁盘中读入内存...这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。...应用 红黑树这种数据结构应用十分广泛，在多种编程语言中被用作符号表的实现 Java中的java.util.TreeMap,java.util.TreeSet C++ STL中的：map,multimap
左旋转字符串 题目 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。...数组中重复的数字 题目 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。...在排序数组中查找数字 I 题目 统计一个数字在排序数组中出现的次数。...] 闭区间内，因此执行 high = pivot； 当 nums[pivot] = nums[high] 时： 无法判断 pivot 在哪个排序数组中，即无法判断旋转点 x 在 [low, pivot]...数组中数字出现的次数 II 题目 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
7、调整数组顺序使奇数位于偶数前面 8、数组中出现次数超过一半的数字 9、连续子数组的最大和 10、把数组排成最小的数 11、数组中的逆序对 12、数字在排序数组中出现的次数 五、其他 1.求1+...2+3+…+n 2.不用加减乘除做加法 3、旋转数组的最小数字 六、其他 1.整数中1出现的次数（从1到n中的整数中1出现的次数） 2.扑克牌顺子 3.孩子们的游戏（圆圈中剩下的数） 4、替换空格 5、...如果是点，要判断至此点的数量和e的数量是否已经有了，因为java 中e要求后面为整数，如果有了肯定false。索引后移，dotnum增加。 如果是e，判断是否重复e，或者前面没有数字返回false。...统计一个数字在排序数组中出现的次数。...为了方便起见,你可以认为大小王是0。 思路：剑指和博客 思路:用数组记录五张扑克牌，将数组调整为有序的，若0出现的次数>=顺子的差值，即为顺子。
而是一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度，时间复杂度通常用大O渐进表示法。...Func3的执行操作次数： F（N）= N + M 时间复杂度为： O(M+N) 由于不确定M和N的大小，所以这里都不能忽略掉。...旋转数组 旋转数组 题意：输入一个数k，将数组中的每个元素向右移动k位，数组的最后一个元素向右移动移位后就成了数组的第一个元素。...这种算法的时间复杂度为O（N * K） 思路二：以空间换时间，创建一个和nums同样大的数组，将nums数组的后k位元素与前k位元素进行互换，然后在将新数组中的元素拷贝到nums中。...样例中可能会出现k大于数组元素的个数，对k取数组大小的余数即可。
时间复杂度 时间复杂度是定性的描述了一段程序的运行时间， 官方定义：算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(...n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。...在长度为N的数组中，如果次数与N的大小无关，始终为一个固定的次数，或许是1次，或许是3次，它们都记为O(1)，也叫常数阶，一个遍历就是O(N)，也叫线性阶，嵌套两个遍历就是 O(N^2)，也叫平方阶，...假设数组的长度为N，第一层循环的第一次操作是执行1次，第二次操作是执行2次，直到第N-1次操作是执行N-1次，那么总次数为一个等差数列求和，即N*(N-1)/2，当问题规模扩大到无穷大时，小数量级的加减可以忽略...：数组长度：32，执行交换次数：185 下沉操作：数组长度：32，执行交换次数：139 通过结果可以看出，下沉操作的执行交换次数是较少的，因为下沉操作的目标位置只是所有的父节点，而上浮操作要遍历整个数组
红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。...右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋- 转结点的左子结点，右子结点保持不变。如图4。 变色：结点的颜色由红变黑或由黑变红。...HashMap的底层结构是Node的数组： transient Node[] table 当HashMap中存储的数据过多的时候，table数组就会被装满，这时候就需要扩容，HashMap的扩容是以...put操作： 当执行put操作时，会经历两个步骤： 判断是否需要扩容； 定位到添加元素的位置，将其放入 HashEntry 数组中。...16.一道和Java并发编程相关的题目 估计是 三个线程 同时执行 顺序执行 交替执行 之类的题目 顺序执行 使用 join public class ThreadTest1 { // T1、T2
领取专属 10元无门槛券
手把手带您无忧上云
