Question Bank

⚙ Question Template¹
📄 [975] 奇偶跳²
📄 [1155] 掷骰子等于目标和的方法数⁵
📄 [1726] 同积元组⁶
📄 [2530] 执行 K 次操作后的最大分数⁷

‍

Question Template

[id] Question Name
- address
  
  question address
- tags
  
  #leetcode#
- solution explain
  
  ‍
- solution code
  - Python3
‍ ↩

[975] 奇偶跳

address

[975] 奇偶跳
tags

#leetcode# #alg/动态规划# #alg/单调栈#
solution explain

在给定的数组中，每个位置使用奇数跳跃或者偶数跳跃，落点都是可以唯一确定的。确定了在每个位点奇偶跳的落点，即可判断从每个点能否最终到达末尾。

奇数跳，只不过是在后续大于等于自己的元素中找值最接近的位置；
反之偶数跳，是在小于等于自己的元素中找最接近自己的元素。
- 单调栈解法
  
  统计在 i点的奇数跳落点时：
  
  将原始数组 A的索引按位置的数值从小到大进行排序。即 B = sorted(range(N), key = lambda i: A[i])
  
  这样就可以知道每个位置与之数值最接近的值（A[B[1]]与之最接近的值是 A[B[2]]）,但是不能这样这样粗暴认为 A[B[n+1]]就是 A[B[i]]的奇数跳落点坐标，因为 B[n+1]和 B[n]还必须满足 B[n+1] > B[n]，即索引位置关系。
  
  因为 A[B[n]]这个数组已经是升序，于是我们就可以总结：“==在 B 数组中 B[n]之后首个大于 B[n]的值 B[m]即为 A[B[n]]的奇数跳落点 A 坐标 A[B[m]]==”(细细品~) 相当于在 B 数组中寻找递减序列。
  
  使用一个单调栈即可实现，遍历 B，保证栈内元素由低至顶递减，当新元素 Y 大于栈顶元素时，弹出栈顶 X，即 A 数组中索引为 X 的点奇数跳落点索引为 Y，遍历完成后仍然在栈中的元素，表明在 A 数组中这些索引位置处无法进行奇数跳，落点记为 None。详见 Python3 - 单调栈¹中 make
  
  偶数跳同理，只需将元素取负即可（小于等于并最接近自己的元素，取负后成为大于等于并最接近自己）。
在奇偶数跳跃落点两个数组的基础上即可求出 DP 数组，dp[i][0]表示能否从 i 处通过偶数跳最终到达终点，dp[i][1]表示能否从 i 处通过奇数跳最终到达终点，且 dp[len-1][0] = dp[len-1][1] = 1，从末尾往前推导即可完善整个 DP 数组，规则为：
1. 如果 i 处能进行偶数跳（即 even[i] is not None），此处能否偶数跳最终最终到达终点取决于跳跃落点处能否通过奇数跳并最终到达终点（即 dp[i][0] = dp[even[i]][1]）
2. 奇数跳与上同理。
因为起始跳跃为奇数跳，对 dp[][1]进行求和即为题解。
- TreeMap解法
  
  单调栈解法¹中我们所做的事情 TreeMap提供了 API:lowerKey(v)和 higherKey(v)，即为略小于 v 的值，略大于 v 的值。

solution code

Python3 - 单调栈

class Solution(object):
    def oddEvenJumps(self, A):
        N = len(A)

        def make(B):
            ans = [None] * N
            stack = []  # invariant: stack is decreasing
            for i in B:
                while stack and i > stack[-1]:
                    ans[stack.pop()] = i
                stack.append(i)
            return ans

        B = sorted(range(N), key = lambda i: A[i])
        oddnext = make(B)
        B.sort(key = lambda i: -A[i])
        evennext = make(B)

        odd = [False] * N
        even = [False] * N
        odd[N-1] = even[N-1] = True

        for i in range(N-2, -1, -1):
            if oddnext[i] is not None:
                odd[i] = even[oddnext[i]]
            if evennext[i] is not None:
                even[i] = odd[evennext[i]]

        return sum(odd)

作者：LeetCode
链接：https://leetcode.cn/problems/odd-even-jump/solutions/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Java - TreeMap 解法

class Solution {
    public int oddEvenJumps(int[] A) {
        int N = A.length;
        if (N <= 1) return N;
        boolean[] odd = new boolean[N];
        boolean[] even = new boolean[N];
        odd[N-1] = even[N-1] = true;

        TreeMap<Integer, Integer> vals = new TreeMap();
        vals.put(A[N-1], N-1);
        for (int i = N-2; i >= 0; --i) {
            int v = A[i];
            if (vals.containsKey(v)) {
                odd[i] = even[vals.get(v)];
                even[i] = odd[vals.get(v)];
            } else {
                Integer lower = vals.lowerKey(v);
                Integer higher = vals.higherKey(v);

                if (lower != null)
                    even[i] = odd[vals.get(lower)];
                if (higher != null) {
                    odd[i] = even[vals.get(higher)];
                }
            }
            vals.put(v, i);
        }

        int ans = 0;
        for (boolean b: odd)
            if (b) ans++;
        return ans;
    }
}

作者：LeetCode
链接：https://leetcode.cn/problems/odd-even-jump/solutions/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

↩

Python3 - 单调栈

class Solution(object):
    def oddEvenJumps(self, A):
        N = len(A)

        def make(B):
            ans = [None] * N
            stack = []  # invariant: stack is decreasing
            for i in B:
                while stack and i > stack[-1]:
                    ans[stack.pop()] = i
                stack.append(i)
            return ans

        B = sorted(range(N), key = lambda i: A[i])
        oddnext = make(B)
        B.sort(key = lambda i: -A[i])
        evennext = make(B)

        odd = [False] * N
        even = [False] * N
        odd[N-1] = even[N-1] = True

        for i in range(N-2, -1, -1):
            if oddnext[i] is not None:
                odd[i] = even[oddnext[i]]
            if evennext[i] is not None:
                even[i] = odd[evennext[i]]

        return sum(odd)

作者：LeetCode
链接：https://leetcode.cn/problems/odd-even-jump/solutions/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

↩ ↩

- 单调栈解法
统计在 i点的奇数跳落点时：

将原始数组 A的索引按位置的数值从小到大进行排序。即 B = sorted(range(N), key = lambda i: A[i])

这样就可以知道每个位置与之数值最接近的值（A[B[1]]与之最接近的值是 A[B[2]]）,但是不能这样这样粗暴认为 A[B[n+1]]就是 A[B[i]]的奇数跳落点坐标，因为 B[n+1]和 B[n]还必须满足 B[n+1] > B[n]，即索引位置关系。

因为 A[B[n]]这个数组已经是升序，于是我们就可以总结：“==在 B 数组中 B[n]之后首个大于 B[n]的值 B[m]即为 A[B[n]]的奇数跳落点 A 坐标 A[B[m]]==”(细细品~) 相当于在 B 数组中寻找递减序列。

使用一个单调栈即可实现，遍历 B，保证栈内元素由低至顶递减，当新元素 Y 大于栈顶元素时，弹出栈顶 X，即 A 数组中索引为 X 的点奇数跳落点索引为 Y，遍历完成后仍然在栈中的元素，表明在 A 数组中这些索引位置处无法进行奇数跳，落点记为 None。详见 Python3 - 单调栈¹中 make

偶数跳同理，只需将元素取负即可（小于等于并最接近自己的元素，取负后成为大于等于并最接近自己）。 ↩
[1155] 掷骰子等于目标和的方法数
- address
  
  [1155] 掷骰子等于目标和的方法数
- tags
  
  #leetcode# #alg/动态规划#
- solution explain
  
  🥰 很经典的动态规划题
  
  首先按题意 n个 k面骰子一共能产生k^n种结果，要从这些结果中筛选出结果为 target的结果数量。
  
  k可以视为常量，利用动态规划思想拆分问题：
  
  n 个骰子能组合出 target 的结果数量 = n-1 个骰子能组合出 target - 1 的结果数量（假设第 n 个骰子掷出点数为 1） + ... + n-1 个骰子能组合出 target - k 的结果数量（假设第 n 个骰子掷出点数为 k）
  
  这样转换公式就显而易见了：f(n, target) = \sum_{pick=1}^k f(n-1, target-pick)
  
  因为条件限制了 1 <= n,k <= 30，则初始状态就是f(1, 1..target)，当我们只有一个骰子时，所有小于等于**k**的 target, 其结果都是 1，反之则为 0
  
  f(1, target) = \begin{cases} 1 &\text{if } target \leq k \\ 0 &\text{if } target \gt k\end{cases}
  
  这样从上直下，就可以推算出整个 dp 数组，dp[n][target] = f(n, target) 即为所求
- solution code
  - Python3
```
class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        dp = [[0] * (target + 1) for _ in range(n + 1)]
        for i in range(1, target + 1):
            if k >= i:
                dp[1][i] = 1

        for cnt in range(2, n + 1):
            for sum in range(1, target + 1):
                for pick in range(1, k + 1):
                    if sum > pick:
                        dp[cnt][sum] += dp[cnt - 1][sum - pick]
                        dp[cnt][sum] %= (10 ** 9 + 7)

        return dp[-1][-1]
```
    Tips: 在确定了 target 和 k 之后，可以通过大小关系对循环次数进行缩减，甚至可以对 dp 数组进行压缩，以优化空间占用和运行时间。 ↩

[1726] 同积元组

address

[1726] 同积元组
tags

#leetcode# #alg/哈希表#
solution explain
在所给的数组中均为不同的正整数，任意 4 个符合要求的数字，通过排列组合即可形成 8 个元组。

统计数组中所有的乘积（共 len(nums) * (len(nums) - 1)个乘积），这些乘积结果中必然有相同的，那么即为一组题解。

针对每一个乘积结果，统计数对个数，即可得出 a * b = c * d = product的题解数：
```
例如有`n`个数对乘积均为`product`，那么从`n`个数对中任意取出两个即可组成一个题解，共有$C_n^2$种取法即$\frac{n(n - 1)}{2}$  
```
将题解个数 * 8 即为最终元组个数。

solution code

Python3

class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        res = 0
        productCount: dict = {}
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                product = nums[i] * nums[j]
                productCount[product] = productCount.get(product, 0) + 1
        for _, cnt in productCount.items():
            res += int((cnt * (cnt - 1)) / 2)
        return res * 8

‍ ↩

[2530] 执行 K 次操作后的最大分数
- address
  
  [2530] 执行 K 次操作后的最大分数
- tags
  
  #leetcode# #alg/堆(优先队列)# #alg/贪心#
- solution explain
  
  看到“最”即联想贪心算法，每次都从待选列表（nums）中取出最大的元素即为目标实现。
  
  Q: 每次元素变化后如何快速从其中找到最值元素？
  
  A: 大/小根堆（优先队列）
- solution code
  - Python3
```
from heapq import heapify, heappush, heappop

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        nums = [-num for num in nums]
        heapify(nums)
        res: int = 0
        for _ in range(k):
            top = heappop(nums)
            res += -top
            heappush(nums, -((-top + 2) // 3))
        return res
```
    Python 中 heapify默认小根堆，通过对元素进行取反实现所需的“大根堆”，每次取出堆顶值 top，然后进行 (-top+2) // 3【等效 ceil(top / 3)】，将结果取负后重新 push 进堆中。
  - Java
    
    使用 PriorityQueue作为堆的替代实现 ↩

Python 知识总结

[图片] python 知识总结--简介 - 问尤龙の时光 (wenyoulong.com) python 知识总结--基础语法 - 问尤龙の时光 (wenyoulong.com) python 知识总结--常用数据结构 - 问尤龙の时光 (wenyoulong.com) Python 知识总结--高级 - 问尤龙の时 ..

python 基础 3- 函数

函数函数可以认为是提供一种功能，当我们需要使用该功能时，就可以来调用该函数。 Python 中，函数可以分为两种：内建函数：可以直接去访问的函数，例如 print,input,id,len 等自定义函数：当我们需要的功能，Python 没有提供给我们时，我们可以自行来实现。为什么使用函数：我们要实现的功能，未必 ..

安装 Python 3.11 在 Ubuntu 20.04 中

python3.11 版本说明 Python 3.11 是开源编程语言 Python 的最新主要版本之一。相比之前的 Python 3.10，它引入了各种新特性、增强功能和 Bug 修复。Python 以易用性、语言清晰度和适应性而闻名。因此，它一直是 Web 开发、科学计算、数据分析和人工智能等领域的首要选项。以下 ..

欢迎来到这里！

我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。

关于

Question Template

[id] Question Name

[975] 奇偶跳

单调栈解法

`TreeMap`解法

单调栈解法

[1155] 掷骰子等于目标和的方法数

[1726] 同积元组

[2530] 执行 K 次操作后的最大分数

相关帖子

Python 知识总结

Pyinstaller 的使用指南

python 基础 3- 函数

安装 Python 3.11 在 Ubuntu 20.04 中

混合精度方法

改动

Python 中 PyQt6 只读属性问题

欢迎来到这里！

近期热议

推荐标签标签

最新标签

Question Bank

Question Template

[id] Question Name

[975] 奇偶跳

单调栈解法

TreeMap​解法

单调栈解法

[1155] 掷骰子等于目标和的方法数

[1726] 同积元组

[2530] 执行 K 次操作后的最大分数

相关帖子

Python 知识总结

Pyinstaller 的使用指南

python 基础 3- 函数

安装 Python 3.11 在 Ubuntu 20.04 中

混合精度方法

改动

Python 中 PyQt6 只读属性问题

欢迎来到这里！

近期热议

推荐标签 标签

最新标签

`TreeMap`解法

推荐标签标签