个人中心
文章发布
退出
作者热门文章
- Java锁的逻辑（结合对象头和ObjectMonitor）
- 还在用饼状图？来瞧瞧这些炫酷的百分比可视化新图形（附代码实现）⛵
- 自动注册实体类到EntityFrameworkCore上下文，并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
34
4
本文已收录到 AndroidFamily ，技术和职场问题，请关注公众号 [彭旭锐] 提问.
大家好，我是小彭.
昨晚是 LeetCode 第 335 场周赛，你参加了吗？这场周赛整体难度不高，有两道模板题，第三题和第四题应该调换一下位置.
小彭的 Android 交流群 02 群来了，公众号回复 “加群” 加入我们~ 。
https://leetcode.cn/problems/pass-the-pillow/ 。
n 个人站成一排，按从 1 到 n 编号.
最初，排在队首的第一个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头.
n 个人时，TA 会将枕头传递给第 n - 1 个人，然后传递给第 n - 2 个人，依此类推。 给你两个正整数 n 和 time ，返回 t 。
简单模拟题.
class Solution {
fun passThePillow(n: Int, time: Int): Int {
var index = 1
var flag = true
for (count in 0 until time) {
if (flag) {
if (++index == n) flag = !flag
} else {
if (--index == 1) flag = !flag
}
}
return index
}
}
复杂度分析:
以 n = 4 为例，显然每 n - 1 次传递为一轮，则有 time % (n - 1) 分辨出奇数轮 / 偶数轮。其中偶数轮是正向传递，奇数轮是逆向传递.
class Solution {
fun passThePillow(n: Int, time: Int): Int {
val mod = n - 1
return if (time / mod % 2 == 0) {
(time % mod) + 1
} else {
n - (time % mod)
}
}
}
复杂度分析:
https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/ 。
给你一棵二叉树的根节点 root 和一个正整数 k .
树中的 层和 是指 同一层 上节点值的总和.
返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 .
注意 ，如果两个节点与根节点的距离相同，则认为它们在同一层.
BFS 模板题，使用小顶堆记录最大的 k 个数.
class Solution {
fun kthLargestLevelSum(root: TreeNode?, k: Int): Long {
if (null == root) return 0L
val heap = PriorityQueue<Long>()
// BFS
val queue = LinkedList<TreeNode>()
queue.offer(root)
while (!queue.isEmpty()) {
var levelSum = 0L
for (count in 0 until queue.size) {
val node = queue.poll()
levelSum += node.`val`
if (null != node.left) {
queue.offer(node.left)
}
if (null != node.right) {
queue.offer(node.right)
}
}
if (heap.size < k) {
heap.offer(levelSum)
} else if (heap.peek() < levelSum) {
heap.poll()
heap.offer(levelSum)
}
}
return if (heap.size >= k) heap.peek() else -1L
}
}
复杂度分析:
https://leetcode.cn/problems/split-the-array-to-make-coprime-products/ 。
给你一个长度为 n 的整数数组 nums ，下标从 0 开始.
如果在下标 i 处 分割 数组，其中 0 <= i <= n - 2 ，使前 i + 1 个元素的乘积和剩余元素的乘积互质，则认为该分割 有效 .
nums = [2, 3, 3] ，那么在下标 i = 0 处的分割有效，因为 2 和 9 互质，而在下标 i = 1 处的分割无效，因为 6 和 3 不互质。在下标 i = 2 处的分割也无效，因为 i == n - 1 。 返回可以有效分割数组的最小下标 i ，如果不存在有效分割，则返回 -1 .
当且仅当 gcd(val1, val2) == 1 成立时， val1 和 val2 这两个值才是互质的，其中 gcd(val1, val2) 表示 val1 和 val2 的最大公约数.
这道题是这场周赛中最复杂的题目，应该放在 T4.
因为多个数相乘的结果会溢出（如果题目中存在 0 还会干扰），所以这道题不能用前后缀分解的思路。 比较容易想到的思路是做质因子分解：显然合法分割数点的左右两边不能有公共质因子，否则子集的乘积必然是非互质的.
举个例子，在数组 [1, 2, 3, 2, 5] 中，将质因子 2 划分到不同子集的方案是错误的:
脑海中有闪现过状态压缩，但题目输入数据较大无法实现，只能有散列表记录质因子信息。因此我们的算法是：先对 nums 数组中的每个元素做质因数分解，然后枚举所有分割点，统计左右子集中质因子的出现次数。如果出现同一个质因子再左右子集中的出现次数同时大于 1，说明分割点不成立.
class Solution {
fun findValidSplit(nums: IntArray): Int {
val n = nums.size
// 质因子计数
val leftCount = HashMap<Int, Int>()
val rightCount = HashMap<Int, Int>()
// 质因子分解
val primeMap = HashMap<Int, HashSet<Int>>()
for (num in nums) {
// 对 num 做质因数分解
primeMap[num] = HashSet<Int>()
var x = num
var prime = 2
while (prime * prime <= x) {
if (x % prime == 0) {
// 发现质因子
primeMap[num]!!.add(prime)
rightCount[prime] = rightCount.getOrDefault(prime, 0) + 1
// 消除所有 prime 因子
while (x % prime == 0) x /= prime
}
prime++
}
if(x > 1) {
// 剩下的质因子
primeMap[num]!!.add(x)
rightCount[x] = rightCount.getOrDefault(x, 0) + 1
}
}
// 枚举分割点
outer@ for (index in 0..n - 2) {
for (prime in primeMap[nums[index]]!!) {
leftCount[prime] = leftCount.getOrDefault(prime, 0) + 1
rightCount[prime] = rightCount[prime]!! - 1
}
for ((prime, count) in leftCount) {
if (rightCount[prime]!! != 0) continue@outer
}
return index
}
return -1
}
}
复杂度分析:
思路来源： 灵茶山艾符的题解 。
统计每种质因子在数组中出现的起始位置 left 和终止位置 right ，如果分割点位于 [left, right) 区间，那么左右两子集一定会存在公共质因子.
因此我们的算法是：将质数的分布看成一个连续区间，按照区间起始位置对所有区间排序。遍历区间并维护最大区间终止位置 preEnd ，如果当前区间与 preEnd 不连续，则说明以当前位置为分割点的方案不会拆分区间，也就找到目标答案.
如果按照这个思路理解，这道题本质上和 55. 跳跃游戏 类似.
class Solution {
fun findValidSplit(nums: IntArray): Int {
// 质因子区间 <首次出现位置，末次出现位置>
val primeMap = HashMap<Int, IntArray>()
// 质因数分解
for ((index, num) in nums.withIndex()) {
// 对 num 做质因数分解
var x = num
var prime = 2
while (prime * prime <= x) {
if (x % prime == 0) {
// 发现质因子
primeMap.getOrPut(prime) { intArrayOf(index, index) }[1] = index
// 消除所有 prime 因子
while (x % prime == 0) x /= prime
}
prime++
}
if (x > 1) {
// 剩下的质因子
primeMap.getOrPut(x) { intArrayOf(index, index) }[1] = index
}
}
// 区间排序
val areaList = primeMap.values.toMutableList()
Collections.sort(areaList) { e1, e2 ->
e1[0] - e2[0]
}
// 枚举区间
var preEnd = 0
for (area in areaList) {
if (area[0] > preEnd) return area[0] - 1
preEnd = Math.max(preEnd, area[1])
}
return -1
}
}
复杂度分析:
题解二中的排序时间可以优化.
由于我们是从前往后分解 nums 数组，每分解一个质因子 prime 时，它一定可以更新该质数区间的末次出现位置。所以我们不用等到最后再做一次区间排序，直接在做质因数分解时维护 preEnd。在题解二中，我们是从区间的维度维护 preEnd ，现在我们直接从 nums 数组的维度维护 preEnd.
class Solution {
fun findValidSplit(nums: IntArray): Int {
val n = nums.size
// start[p] 表示质数 p 首次出现为止
val start = HashMap<Int, Int>()
// end[i] 表示以 i 为左端点的区间的最大右端点
val end = IntArray(n)
// 质因数分解
for ((index, num) in nums.withIndex()) {
// 对 num 做质因数分解
var x = num
var prime = 2
while (prime * prime <= x) {
if (x % prime == 0) {
// 发现质因子
if (!start.containsKey(prime)) {
start[prime] = index
} else {
end[start[prime]!!] = index
}
// 消除所有 prime 因子
while (x % prime == 0) x /= prime
}
prime++
}
if (x > 1) {
// 剩下的质因子
if (!start.containsKey(x)) {
start[x] = index
} else {
end[start[x]!!] = index
}
}
}
var preEnd = 0
for (index in 0 until n) {
if (index > preEnd) return index - 1
preEnd = Math.max(preEnd, end[index])
}
return -1
}
}
复杂度分析:
https://leetcode.cn/problems/number-of-ways-to-earn-points/ 。
考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道，每道题目对应 marksi 分.
返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 109 +7 取余.
注意 ，同类型题目无法区分.
3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。 
这是分组背包模板题， OIWiki-背包 DP .
定义 $dp[i][j]$ 表示以物品 $[i]$ 为止且分数为 $j$ 的方案数，则有:
$dp[i][j] = dp[i - 1][j] + \sum_{k=0}^{k=j/count_i}dp[i - 1][j - k*·marks_{si}]$ 。
class Solution {
fun waysToReachTarget(target: Int, types: Array<IntArray>): Int {
val MOD = 1000000007
// 背包问题
val n = types.size
// dp[i][j] 表示以 [i] 为止且分数为 j 的方案数
val dp = Array(n + 1) { IntArray(target + 1) }.apply {
// 不选择且分数为 0 的方案数为 1
this[0][0] = 1
}
// 枚举物品
for (i in 1..n) {
val count = types[i - 1][0]
val mark = types[i - 1][1]
for (j in target downTo 0) {
dp[i][j] += dp[i - 1][j]
for (k in 1..Math.min(count, j / mark)) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - k * mark]) % MOD
}
}
}
return dp[n][target]
}
}
完全背包可以取消物品维度优化空间:
class Solution {
fun waysToReachTarget(target: Int, types: Array<IntArray>): Int {
val MOD = 1000000007
// 背包问题
val n = types.size
// dp[i][j] 表示以 [i] 为止且分数为 j 的方案数
val dp = IntArray(target + 1).apply {
// 不选择且分数为 0 的方案数为 1
this[0] = 1
}
// 枚举物品
for (i in 1..n) {
val count = types[i - 1][0]
val mark = types[i - 1][1]
for (j in target downTo 0) {
for (k in 1..Math.min(count, j / mark)) {
dp[j] = (dp[j] + dp[j - k * mark]) % MOD
}
}
}
return dp[target]
}
}
复杂度分析:
最后此篇关于LeetCode周赛335，纯纯手速场！的文章就讲到这里了,如果你想了解更多关于LeetCode周赛335，纯纯手速场！的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
34
4
0
在 firefox 中，链接手形光标显示正常，但在 IE7 中显示文本光标。 如何在所有浏览器的链接上获得相同的光标(手)？ 我可以在 CSS 重置中添加一些内容，以便在所有浏览器中的链接上获取光标吗
我试图在表单元素上方显示我的表单标签，所以我在我的 CSS 中使用了 display:block。但是，我无法通过这种方式每行显示超过 1 个表单元素。 如何正确更新我的 CSS 以在表单元素上方显示
我想找到人手的宽度，但卡在手上的洞上。 我有一只手的图片并找到了它的二进制文件。手上有一个圆圈，其半径和中心已知(引用对象)。我想找到手的宽度，但它上面有一些补丁(孔)，这阻碍了找到手的最佳宽度。 这
我尝试为一款游戏制作一个机器人，但他们有很酷的反像素机器人技术。 所以我想，“如果我可以制作一个机器人，只检查光标是否变为手形然后单击，它就会起作用，”因为我需要收集奖金盒，当你将光标指向它时，它变为
我尝试为一款游戏制作一个机器人，但他们有很酷的反像素机器人技术。 所以我想，“如果我可以制作一个机器人，只检查光标是否变为手形然后单击，它就会起作用，”因为我需要收集奖金盒，当你将光标指向它时，它变为
所以我有一副牌的代码，但我不知道如何让另一个类来处理 4 手牌，每手 10 张牌。另一类应在屏幕上以文字形式打印 4 手 10 张随机卡片。有人可以向我展示如何完成此任务的代码吗？我也使用 blueJ
我正在尝试通过在开放正方形内插入图标来使用 fontawesome 创建图标。悬停时，我想更改正方形内背景的颜色，以及正方形的实际颜色和图标颜色。 我在这里举了一个例子:http://jsfiddle
当我手动启 Action 业时，我正在寻找设置变量的正确方法。 我试过 : stages: - test my_job: stage: test script: - echo "H
我必须添加以下代码: a {cursor:pointer;} 在 angular-ui-bootstrap 中将光标更改为标签、分页、下拉切换等链接上的指针/手。 为什么默认不改为指针？这是故意的吗？
我是一名优秀的程序员,十分优秀！