侯瑞哲的博客

问题： 有一只青蛙，向右跳x步可以到达右边中点，向左边跳n-x步可以到达左边中点，问到达左边中点的概率。 求解方法 我们定义f(x)为到达左边中点的概率。 那么f(0) = 0，因为我们已经到达右边终点，f(n) = 1，因为我们已经到达左边终点。 我们知道，f(x) 接下来有两种走法，f(x-1)和f(x+1)，所以有 f(x) = 0.5 * f(x-1) + 0.5 * f(x+1) 我们由

Splay的插入操作 正如前篇博文所讲的，Splay树是一种自平衡的数据结构，最后一个访问的键总是根。插入操作和二叉搜索树的插入类似，额外多了一些步骤来保证新插入的键称为新的根节点。 以下是插入键值k到一个Splay Tree的不同情况 root是空：我们简单的分配一个新的节点，并将它作为root返回 splay（伸展）给定的键值k。如果k已经存在，那么它称为新的根节点。如果不存在，那么最后访问

数据结构与算法 leetcode刷到300题啦，继续加油啊！ 2020.08.22 第一次leetcode周赛全对，继续努力！ 2020.08.23 leetcode周赛进了前500，继续努力！ 2020.08.30 leetcode 204 周赛全国排名68，进入前100啦！世界排名239，进入前300啦！继续加油啊！ 2020.09.20 leetcode 207 周赛全国排名86，继续加油

示例解法 这道题目的dp要仔细分析。分析过程写在了注释中（个人习惯…）。 123456789101112131415161718192021222324252627282930# 我们来分析这个问题# 我们定义f(i)为距离终点为i时所需的指令大小# 如果i == 2 ** n - 1，指令的长度就为n# 如果i != 2 ** n - 1，我们有两种走法# 假设 2**(n-1) -1 <

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6] 输出: 1->1->2->3->4->4->5->6 是工业界很常见的一种操作，比如分布式系统中、数据库中，我们有多个索引是有序的，且在多个小文件中存储，我们要合并成一个新的有序链表。我们

快速排序作为一种基础的算法，广泛用于各种语言的内置排序库中，其中java使用了双基准快速排序（主要是双基准更有效的利用了计算机的缓存机制）。它是一种原地的，空间复杂度为O(1)、时间复杂度O(nlogn)、不稳定的排序算法。分为切分，和递归两个步骤。其中切分的步骤可以帮助我们以O(n)的时间复杂度找到数组中某种排名为K的元素。然而在实际实现中，快排有一些小技巧，也是我们必须要掌握的一种算法。 以下

题目描述 在排序数组中查找元素的第一个和最后一个位置 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值，返回 [-1, -1]。 示例 1: 12输入: nums = [5,7,7,8,8,10], target = 8输出: [3,

题目描述 给定一个非空二维矩阵 matrix 和一个整数 k，找到这个矩阵内部不大于 k 的最大矩形和。 示例: 输入: matrix = [[1,0,1],[0,-2,3]], k = 2 输出: 2 解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。 说明： 矩阵内的矩形区域面积必须大于 0。 如果行数远大于列数，你将如何解答

二叉搜索树最坏的时间复杂度比如查找、删除、插入是O(n)的。最坏的情况发生在这棵树已经倾斜了。我们可以使最坏情况的时间复杂度也为O(logn)使用AVL和红黑树。 我们可以比AVL和红黑树在实践中做得更好吗？ 像AVL和红黑树一样，splay tree也是自平衡二叉搜索树。splay tree的主要思想是将最近访问的项目放到树的根节点，这使得最近搜索过的项目可以在O(1)的时间复杂度内被搜索到，如

张玉环事件有感