算法题记录 10

2595.奇偶位数（1207）

给你一个 正 整数 n 。

用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。

用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。

请注意，在数字的二进制表示中，位下标的顺序 从右到左。

返回整数数组 answer ，其中 answer = [even, odd] 。

涉及知识点

位操作

解决思路

秒答题，如果直接对n除2的话效率不会很高，可以采用n&1和n>>=1这种位操作来进行取最后一位和移位操作。

class Solution:
    def evenOddBit(self, n: int) -> List[int]:
        ans=[0,0]
        i=0
        while n:
            ans[i]+=n&1
            n>>=1
            i^=1
        return ans

2266.统计打字方案数（1857）

Alice 在给 Bob 用手机打字。为了 打出 一个字母，Alice 需要 按 对应字母 i 次，i 是该字母在这个按键上所处的位置。

比方说，为了按出字母 ‘s’ ，Alice 需要按 ‘7’ 四次。类似的， Alice 需要按 ‘5’ 两次得到字母 ‘k’ 。
注意，数字 ‘0’ 和 ‘1’ 不映射到任何字母，所以 Alice 不 使用它们。
但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息 。

比方说，Alice 发出的信息为 “bob” ，Bob 将收到字符串 “2266622” 。
给你一个字符串 pressedKeys ，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息 。

由于答案可能很大，将它对 109 + 7 取余 后返回。

涉及知识点

动态规划

解决思路

仔细思考题意，可以发现是动态规划题，这里贴出两种方案，一种是很常规的按题目一步步翻译做出来的，效率很低。一种是套用了各种模板、小方法做出来的，包括预处理、双存储数组以及调用groupby函数，效率很高，可以比较看看在解答算法题时记住模板和套路的重要性。

普通

class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        l = len(pressedKeys)
        count = 0
        record = [0] * (l+4)
        record[3] = 1
        value = pressedKeys[0]
        ans = 1
        for i in range(3,l+3):
            if pressedKeys[i-3] == value:
                count += 1
                if value != '7' and value != '9':
                    for i in range(4):
                        record[count+3] += record[count + 3 - i]
                elif (value == '7' or value == '9'):
                    for i in range(5):
                        record[count+3] += record[count +3 - i]

            else:
                ans *= record[count+3]
                count = 1
                value = pressedKeys[i-3]
                record = [0] * (l+4)
                record[3] = 1
                record[4]=1


        ans *=record[count+3]
        return int(ans % (10 ** 9 + 7))

优化

MOD = 1_000_000_007
f = [1, 1, 2, 4]
g = [1, 1, 2, 4]
for _ in range(10 ** 5 - 3):  # 预处理所有长度的结果
    f.append((f[-1] + f[-2] + f[-3]) % MOD)
    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % MOD)

class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        ans = 1
        for ch, s in groupby(pressedKeys):
            m = len(list(s))
            ans = ans * (g[m] if ch in "79" else f[m]) % MOD
        return ans

3001.捕获黑皇后需要的最少移动次数（1797）

现有一个下标从 1 开始的 8 x 8 棋盘，上面有 3 枚棋子。

给你 6 个整数 a 、b 、c 、d 、e 和 f ，其中：

(a, b) 表示白色车的位置。
(c, d) 表示白色象的位置。
(e, f) 表示黑皇后的位置。
假定你只能移动白色棋子，返回捕获黑皇后所需的最少移动次数。

请注意：

车可以向垂直或水平方向移动任意数量的格子，但不能跳过其他棋子。
象可以沿对角线方向移动任意数量的格子，但不能跳过其他棋子。
如果车或象能移向皇后所在的格子，则认为它们可以捕获皇后。
皇后不能移动。

涉及知识点

表格

解决思路

秒答题，很显然答案要么1要么2，如果已经将军且车和象没互相挡住，那就是1，其余情况就是2.我们只需要将将军且车和象没互相挡住的判断条件写出来即可，这里就涉及到最基本的表格、棋盘移动，是否在一行、一列、一斜向的问题了。

class Solution:
    def minMovesToCaptureTheQueen(self, a: int, b: int, c: int, d: int, e: int, f: int) -> int:
        # m 在 l 和 r 之间（写不写等号都可以）
        def in_between(l: int, m: int, r: int) -> bool:
            return min(l, r) < m < max(l, r)

        # 车直接攻击到皇后 or 象直接攻击到皇后
        if a == e and (c != e or not in_between(b, d, f)) or \
           b == f and (d != f or not in_between(a, c, e)) or \
           c + d == e + f and (a + b != e + f or not in_between(c, a, e)) or \
           c - d == e - f and (a - b != e - f or not in_between(c, a, e)):
            return 1
        return 2

350.两个数组的交集2（简单）

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

涉及知识点

哈希表

解决思路

秒答题，用Counter对nums1计数，然后判断nums2的元素是否在Counter中，如果在就-1，并且在ans中append一个该元素即可。

如果是要求返回一个列表，列表中包含不重复的两数组交集，即哈希集合，利用list(set(nums1)&set(nums2))即可。

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        cnt = Counter(nums1)
        ans = []
        for x in nums2:
            if cnt[x] > 0:
                cnt[x] -= 1
                ans.append(x)
        return ans

1081.不同字符的最小子序列（2185）

返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。

涉及知识点

哈希，字典序

解决思路

看图说话题，分析题目要求，一步步解决需求即可，过程会需要用到哈希表。

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        left=Counter(s)
        ans=[]
        in_ans=set()
        for c in s:
            left[c]-=1
            if c in in_ans:
                continue
            while ans and c<ans[-1] and left[ans[-1]]:
                in_ans.remove(ans.pop())
            ans.append(c)
            in_ans.add(c)
        return ''.join(ans)

837.新21点（2350）

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：

爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。 抽取时，她从 [1, maxPts] 的范围中随机获得一个整数作为分数进行累计，其中 maxPts 是一个整数。 每次抽取都是独立的，其结果具有相同的概率。

当爱丽丝获得 k 分 或更多分 时，她就停止抽取数字。

爱丽丝的分数不超过 n 的概率是多少？

与实际答案误差不超过 10-5 的答案将被视为正确答案。

涉及知识点

动态规划

解决思路

非常有意思的一道题，当我们明确题意后可以作初步尝试。如果用数学知识通过筛出所有可能再算概率，这样势必会很复杂。那么有没有别的方法呢？我们可以尝试逆向思维：
当爱丽丝有a分时（a小于k），此时可以继续抽卡，那么在此时她能获胜的概率为f[a]=1/maxPts*(f[a+1]+f[a+2]+…+f[a+maxPts])。而k到n之间的f值为1，n到k+maxPts之间的f值为0。于是乎，我们就有了逆向的动态规划。
为了简化计算，f[a+1]+f[a+2]+…+f[a+maxPts]可以用一个变量保存，每次算完去掉f[a+maxPts]加上f[a]即可。

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp=[None]*(k+maxPts)
        s=0
        for i in range(k,k+maxPts):
            dp[i]=1 if i<=n else 0
            s+=dp[i]
        for i in range(k-1,-1,-1):
            dp[i]=s/maxPts
            s=s-dp[i+maxPts]+dp[i]
        return dp[0]

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。