-
完美洗牌
给定一棵二叉树的头节点 head，已知所有节点的值都不一样，返回其中最大的且符合搜索二叉树的最大拓扑结构的大小。 拓扑结构：不是子树，只要能连起来的结构都算。分析：假设数组下标从 1 开始，我们可以根据数据的原始下标，通过公式推导出调整后的下标。$f(i)=\begin{cases} 2i & i <=N & 左半区 \ 2(i-N)-1 & i>N & 右半区 \end{cases}$def modify_index(i, length)...…
-
搜索二叉树的最大拓扑结构
给定一棵二叉树的头节点 head，已知所有节点的值都不一样，返回其中最大的且符合搜索二叉树的最大拓扑结构的大小。 拓扑结构：不是子树，只要能连起来的结构都算。概念：拓扑贡献度下图蓝色拓扑结构是一棵以节点 “5” 为根节点的搜索二叉树的拓扑贡献度为 5 = node.left.拓扑贡献度 + node.right.拓扑贡献度 + 1以节点 “3” 为根节点的搜索二叉树的拓扑贡献度为 2以节点 “10” 为根节点的搜索二叉树的拓扑贡献度为 2解法一：暴力算法计算以每个节点为根节点拓扑贡...…
-
正数分裂方法数
给定一个正数 1，裂开的方法有一种：(1) 给定一个正数 2，裂开的方法有一种：(1，1)，(2) 给定一个正数 3，裂开的方法有一种：(1，1，1)，(1，2)，(3) 给定一个正数 4，裂开的方法有一种：(1，1，1，1)，(1，1，2)，(1，3)，(2，2)，(4) 给定一个正数 n，求裂开的方法数。亮点：斜率优化方案一：暴力递归f ( pre, rest ) pre 只之前裂开的数 rest 是本次要裂开的数。rest 要大于 pre。 返回结果：裂开的方法数最...…
-
最少货币数
给定数组 arr，arr 中所有的值都为正整数。每个值代表一张钱的面值，再给定一个整数 aim 代表要找的钱数，求组成 aim 的最少货币数。举例 arr= 【5,2,3】，aim = 20；返回 -1 5 元，2元，3元的钱各有 1 张，无法组成 20 元，返回默认值 -1 arr= 【5,2,5,3】，aim = 10；返回 2 2 张 5 元 arr= 【5,3】，aim=0；返回 0 不用任...…
-
无序数组中最小的第 k 个数
在一个无序数组中，求最小的第 k 个数。解法一：排序时间复杂度：O(N logN)def find_kth_num(arr, k): if not arr: return arr.sort() return arr[k - 1]解法二：大顶堆 建立一个大顶堆存在前 k 个数。 遍历数组，小于堆顶的数据，pop 出堆顶，push 出当前数 遍历完毕后，堆顶元素就是最小的第 k 个数时间复杂度：O(N logK)空间复杂度：O(K)import heapqdef f...…
-
回文串移除方案
给定一个字符串 str，能否从字符串中移除部分（0个或多个）字符使其变为回文串，此处空串认为是回文串，求多少移除方案。（注意：相同字符的由于的移除，认为不同的移除方案）。 【例如】str = “XXY” 有 4 中移除方案 方案一：暴力规划移除字符与保留字符效果是一样的。可能性尝试：范围尝试模型。f( i , j ) 定义：str[ i: j+1 ] 子串中包含回文个数。最终结果：f ( 0, len(str) - 1 )可能性分类： 开头 ...…
-
回文子串的最小切割数
给定一个字符串 str，返回把 str 全部切成回文子串的最小切割数。 【举例】 str = “ABA” 不需要切割，str 本身就是回文串，所以返回 0 str = “ACDCDCDAD” 最少需要切 2 次变成 3 个回文子串，比如“A”、“CDCDC” 和 “DAD”，所以返回 2.方案一：暴力递归动态规划：从左向右尝试模型。不是字符每个位置都可以作为切分点。左边部分必须是一个回文子串，才有资格作为切分点。f( i ) 定义： str[ i: ] 子串中回文子串的个数。最终...…
-
最长回文子序列
给定一个字符串 str，求最长的回文子序列。动态规划：范围尝试模型**范围尝试模型一般根据开头和结尾讨论可能性**f( i , j) 在 str [i:j+1] 上最长回文子序列的长度，终止要求的是 f (0 , len(str)-1)可能性分析：$f(i,j)=\begin{cases} f(i-1,j-1)+2 & ;str[i]==str[j] \ max(f(i-1,j),f(i,j-1)) &;str[i]!=str[j] \end{cases}$ 如果 s...…
-
最长公共子序列
给定两个字符串 str1 和 str2 ，求两个字符串的最长公共子序列。方案一：暴力递归可能性分析f( i, j ) 定义：string1[:i] 和 string2[:j] 两个子串的最长公共子序列的长度。注意：此时或者的最长公共子序列不要求必须以 string1[i] 和 string[2] 结尾。$f(i,j)=\begin{cases} f(i-1,j-1)+1 & string1[i]==string2[j] \ max(f(i-1,j),f(i,j-1)) &...…
-
bool 表达式解析
给定一个只由 0（假）、1 (真)、&（逻辑与）、|（逻辑或）、^（s）五种字符组成的字符串 express，再给定一个布尔值 desired。返回 express 能有多少种组合方式，可以达到 desired 的结果。 【举例】 Express = “1^0|0|1”，desired = false 只有 1^((0|0)|1) 和 (1^0|(0|1)) 的组合可以得到 false ，返回 2 无组合可以得到 false ，返回 0以下 a = 0 ；b = 1验证...…
-
公式计算
给定一个字符串str，str 表示一个公式，公式里可能有整数，加减乘除，返回公式的计算结果。 【举例】 str = “3-6*9+43*70*8-6” , 返回 24023 str = “3+1*4” , 返回 7分析：由于乘除的计算优先级高于加减，因此：第一遍遍历优先计算乘除，第二遍遍历再计算加减。def expression_compute(string): stack = [] i = 0 while i < len(string): ...…
-
贪吃蛇
给定一个二维数组 matrix，每个单元都是一个整数，有正有负。最开始的时候小 Q 操纵一条长度为 0 的蛇。蛇从矩阵最左侧人选一个单元格进入地图，蛇每次只能够到大当前位置的右上相邻，右侧相邻和右下相邻的单元格。蛇蛇到达一个单元格后，自身的长度会瞬间加上改单元格的数值，任何情况下长度为负则游戏结束。小 Q 是个天才，他拥有一个超能力，可以在游戏开始的时候把地图中的某一个节点的值变为相反数（注意：最多只能改变一个节点）。问小 Q 游戏过程中，他的蛇蛇最长长度可以到多少？ 【例如】mat...…
-
01背包
给定 n 种物品和一背包。物品 i 的重量是 $w_i$，其价值为$v_i$ ，背包的容量为 C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 对于一种物品，要么装入背包，要么不装。解法一：暴力递归可能性分析：f ( i, rest ) 物品 i ，背包容量为 rest 时，能装入的物品的最大总价值。 物品 i 放入背包：res1 = f( i + 1, rest - w[i] ) 物品 i 不放入背包：res2 = f( i + 1, rest ) 决策：res...…
-
整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。示例 1:输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:输入: 10输出: 36解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。解法一：暴力递归f( k ) = a * ( k - a )可能性分析：假设 f ( k ) 表示 n = k 时，获得的最大乘积a = 1 尝试 ( k - a ) 是否再拆分 如果不查分：res...…
-
【每日一题】按摩师
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。示例 1：输入： [1,2,3,1]输出： 4解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。示例 2：输入： [2,7,9,3,1]输出： 12解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。示例 3：输...…
-
并查集
查并集背景问题： 在 O(1) 的时间复杂度的情况下，判断 a 和 b 是否属于同一个集合。 在 O(1) 的时间复杂度的情况下，将集合 A 和集合 B 数据合并。尝试使用已有数据结构尝试解决上述问题HashSet要满足问题 1，使用 HashSet，可以在 O(1) 判断 a 和 b 是否属于同一个集合。但是要合并集合 A 和集合 B 时，必须将集合 A 中数据拷贝到集合 B 中，或者将集合 B 中数据拷贝到集合 A 中，就达不到 O(1)LinkedList如果是链表存储，可以实现...…
-
搜索引擎关键字智能提示实践
一、背景搜索关键字智能提示是一个搜索应用的标配，主要作用是避免用户输入错误的搜索词，并将用户引导到相应的关键词上，以提升用户使用体验。雪球以连接人与资产，让财富的雪球越滚越大为使命，在投资社区领域处于领先地位。为了让用户快速准确找到目标的股票，大V，我们搭建搜索提示系统（以下简称Sug系统）来自动补全 Query。用户在查找股票时主要输入股票名称、股票 Symbol 进行搜索，为了提升用户体验和输入效率，本文实现了一种基于 Trie 树前缀匹配查询 + 模型排序关键词智能提示（Sugges...…
-
Query 聚类
背景搜索系统优化长尾 query。想了解一下长尾 query 长什么样？大体上都有几类？最好能归类，一类一类处理。Query 数据源：包含“什么”，“怎么”，“如何” 关键词的 Query。K-means聚类概念生活中的聚类例子：班级分组。 一个班级有 40 名学生，班主任分别让小明，小红，小强，小李将班级中学生分成两组。 小明：男生一组，女生一组。 小红：前三排一组，后三排一组。 小强：左三列一组，右三列一组。 小李：住校生一组，走读生一组。为什么造成大家的分组不一...…
-
Size Balanced Tree
平衡性 每棵子树的大小，不小于其兄弟的子树大小。既每棵叔叔树的大小，不小于其任何侄子树的大小。左旋触发条件：cur = 节点 4，cur.right.right.size > cur.left.size。出现右边子树节点数太多。通过左旋，将 cur.right 的结点替换 cur 节点。具体过程如下图# 左旋def left_rotate(self, cur: Node): right_node = cur.right cur.right = right_node.le...…
-
SkipLists
跳表是一个随机化的搜索数据结构跳表的 NB 之处： 思想先进：跳表不再使用硬规则来数据的平衡性，而是使用概率保证。 由于使用概率随机生成数据层，与用户输入的数据无关。跳表时间复杂度评估第 0 层：N 个节点（每个节点必在第 0 层）第 1 层：$\frac{N}{2}$ 个节点第 2 层：$\frac{N}{4}$ 个节点第 3 层：$\frac{N}{8}$ 个节点…第 k 层：$\frac{N}{2^k}$ 个节点类似满二叉树查找数据查找 50 。从 head 的最上层开始查找...…
