题目:
思想:
首先用Counter计数,用 &
符号连接两个字典的keys, 剩下的部分就是两者都有的。
遍历这个剩下的部分,判断是不是都等于 1 就行
代码:
1 | class Solution: |
1 | return sum(1 for i in Counter(words1) & Counter(words2) if Counter(words1)[i] == 1 and Counter(words2)[i] == 1) |
首先用Counter计数,用 &
符号连接两个字典的keys, 剩下的部分就是两者都有的。
遍历这个剩下的部分,判断是不是都等于 1 就行
1 | class Solution: |
1 | return sum(1 for i in Counter(words1) & Counter(words2) if Counter(words1)[i] == 1 and Counter(words2)[i] == 1) |
就排序,排完之后,两两比较后merge.
1 | from typing import List |
现有一份 n + m
次投掷单个 六面 骰子的观测数据,骰子的每个面从 1
到 6
编号。观测数据中缺失了 n
份,你手上只拿到剩余 m
次投掷的数据。幸好你有之前计算过的这 n + m
次投掷数据的 平均值 。
给你一个长度为 m
的整数数组 rolls
,其中 rolls[i]
是第 i
次观测的值。同时给你两个整数 mean
和 n
。
返回一个长度为 n
的数组,包含所有缺失的观测数据,且满足这 n + m
次投掷的 平均值 是 mean
。如果存在多组符合要求的答案,只需要返回其中任意一组即可。如果不存在答案,返回一个空数组。
k
个数字的 平均值 为这些数字求和后再除以 k
。
注意 mean
是一个整数,所以 n + m
次投掷的总和需要被 n + m
整除。
示例 1:
输入:rolls = [3,2,4,3], mean = 4, n = 2 输出:[6,6] 解释:所有 n + m 次投掷的平均值是 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4 。
示例 2:
输入:rolls = [1,5,6], mean = 3, n = 4 输出:[2,3,2,2] 解释:所有 n + m 次投掷的平均值是 (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3 。
示例 3:
输入:rolls = [1,2,3,4], mean = 6, n = 4 输出:[] 解释:无论丢失的 4 次数据是什么,平均值都不可能是 6 。
示例 4:
输入:rolls = [1], mean = 3, n = 1 输出:[5] 解释:所有 n + m 次投掷的平均值是 (1 + 5) / 2 = 3 。
提示:
m == rolls.length
1 <= n, m <= 105
1 <= rolls[i], mean <= 6
Problem: 2028. 找出缺失的观测数据
数学上我们先算出用剩下的n个数值,是否能构造出给出的平均数,如果全为1是否还比平均数大,以及全为6了是否还比平均数小。
然后就是构造一个全为1的数组,开始用抽屉法依次填充,直到剩余的个数不足5个,就把剩余的个数全部分配给遍历的终端,然后结束程序即可
时间复杂度: $O(m + n)$ 空间复杂度: $O(n)$
1 | class Solution: |
1 |
|
“””
在给定的 m x n
网格
grid
中,每个单元格可以有以下三个值之一:
0
代表空单元格;1
代表新鲜橘子;2
代表腐烂的橘子。每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1
。
示例 1:
输入:grid = [[2,1,1],[1,1,0],[0,1,1]] 输出:4
示例 2:
输入:grid = [[2,1,1],[0,1,1],[1,0,1]] 输出:-1 解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个方向上。
示例 3:
输入:grid = [[0,2]] 输出:0 解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j]
仅为 0
、1
或 2
这个问题可以用广度优先搜索(BFS)来解决。我们需要跟踪腐烂橘子的扩散过程,记录时间,并检查是否存在无法腐烂的新鲜橘子。最初的想法雏形:
1 | class Solution: |
类似于多线程,每个线程存入一个初始队列,初始队列通过BFS逐步扩散
1 | from collections import deque |
1 | import ( |
我们首先将初始值 x 和操作次数 0 放入队列中。然后,我们不断地从队列中取出当前的值和操作次数,检查是否已经达到了目标值 y。
如果没有,我们将对这个值执行可能的操作,并将新值和操作次数加入队列中,直到找到最短路径。
1 | class Solution: |
1 | a = 0b1001 |
接着,我们可以考虑 xor_sum XOR k 的结果。由于异或运算的特性,任何位上的不同会导致结果中该位为1。这意味着,我们需要改变 xor_sum 和 k 在二进制表示中所有不同的位。
如果 xor_sum = 1010,k = 0011,那么 xor_sum XOR k = 1001。我们需要改变第一位和第四位来让 xor_sum 变成 k。
也就是说 nums的异或合
与 k
的异或的值, 其中1的数目就是需要转换的数目。可以看0x3f的解法
1 | class Solution: |
1 | func minOperations(nums []int, k int) int { |
这道题和quiz4很相似,都是双指针。
这道题做的时候犯了个错,计算右指针的时候是计算的负索引的right = -left + 1
,很难计算和正索引的关系,因此换成了right = len(nums) - 1 - left
。
1 | class Solution: |
9021大家已经在卷运行时间了,这刚好就是$算法$发展的本质。
“有一堆函数的代码和没有函数调用的代码,哪个运行的更快?”
我们先说结论:没有函数调用的代码运行的更快。但是可读性更差,而且运行速度的差距并不大。
我们可以提出来以下问题:
函数调用通常涉及将参数压入堆栈、跳转到函数代码、执行函数代码、将返回值放入适当的位置、然后跳回到调用函数的地方。
尾递归优化、死代码消除、常量传播和常量折叠、内联拓展等。这一章主要说内联拓展。
维基百科:
Inline expansion is used to eliminate the time overhead (excess time) when a function is called. It is typically used for functions that execute frequently. It also has a space benefit for very small functions, and is an enabling transformation for other optimizations.
内联扩展用于消除调用函数时的时间开销(超额时间)。它通常用于频繁执行的函数。对于非常小的函数来说,它还具有空间优势,并且是一种支持其他优化的转换。
频繁地调用函数可能会导致一些额外的开销,这种开销是由于函数调用时的堆栈操作、参数传递和返回值处理等因素引起的。
为了避免这种开销,编译器会尝试将函数调用处的代码替换为函数体,这个过程称为内联扩展(inline expansion)。
ref:
https://www.jstage.jst.go.jp/article/sptj1978/44/3/44_3_206/_pdf
https://www.semanticscholar.org/search?q=Inline%20expansion&sort=relevance