Leecode

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 题目 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/super-ugly-number 编写一段程序来查找第 n 个超级丑数。超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。 示例 输入: n = 12, primes = [2,7,13,19] 输出: 32 解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32]。 说明: 1 是任何给定 primes 的超级丑数。 给定 primes 中的数字以升序排列。 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。 第 n 个超级丑数确保在 32 位有符整数范围内。 解题思路1 由于这是一道中等难度的题目，萌叔第一想到的是穷举，从1开始穷举，1、2 3、… N 判断每个数是否是超级丑数。这个思路肯定是没错的，结果提交后发现超时了。超时的原因是扫描了太多无用的数据。 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 题目 给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组。 实例1: 输入: [0,1] 输出: 2 说明: [0, 1] 是具有相同数量0和1的最长连续子数组。 实例2 输入: [0,1,0] 输出: 2 说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。 解题思路 注意 数组中只会有0、1 两种数据 相同数量的 0 和 1 的最长连续子数组中肯定包含有相同数量的0和1 这里我们要利用0和1数量相同，互相抵消的特性 如果我们把0都当做-1， 1还是1，沿着数组求和，对于以下数组 [0, 1, 1, 0, 1, 1, 1, 0] 我们可以想到如果2个位置(i, j)之间有相同数量0和1的最长连续数组, 那么这2个位置的sum(i) == sum(j) 这里要注意的是，对于数组初始的sum值是0，我们可以记为sum(-1) = 0 要找到最长连续子数组，只需找到sum值相同，且位置相距最大的情况即可 最终代码 find_max.go func findMaxLength(nums []int) int { // sum -> index // 存最小值 cache := map[int]int{} cache[0] = -1 sum := 0 res := 0 for i := 0; i < len(nums); i++ { if nums[i] == 0 { sum -= 1 } else { sum += 1 } if _, ok := cache[sum]; ok { index := cache[sum] res = max(i-index, res) } else { cache[sum] = i } } return res } func max(a int, b int) int { if a < b { return b } else { return a } } 请我喝瓶饮料

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc leecode 上第851题 1. 题目如下 在一组 N 个人（编号为 0, 1, 2, …, N-1）中，每个人都有不同数目的钱，以及不同程度的安静（quietness）。 为了方便起见，我们将编号为 x 的人简称为 “person x “。 如果能够肯定 person x 比 person y 更有钱的话，我们会说 richer[i] = [x, y] 。注意 richer 可能只是有效观察的一个子集。 另外，如果 person x 的安静程度为 q ，我们会说 quiet[x] = q 。 现在，返回答案 answer ，其中 answer[x] = y 的前提是，在所有拥有的钱不少于 person x 的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。 示例： 输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0] 输出：[5,5,2,5,4,5,6,7] 解释： answer[0] = 5， person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。 唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7， 但是目前还不清楚他是否比 person 0 更有钱。 answer[7] = 7， 在所有拥有的钱肯定不少于 person 7 的人中(这可能包括 person 3，4，5，6 以及 7)， 最安静(有较低安静值 quiet[x])的人是 person 7。 其他的答案也可以用类似的推理来解释。 2. 提示 2.1 思考 对于示例，我们能够根据richer信息得出如下关系 我们能够得到富有程度的关系如上图 ...