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 中 pip 常用命令

Python 中 pip 常用命令 1. 安装 pip 从 Python 3.4 ，pip 默认包含在安装包中。安装完 Python 后，你可以直接使用 pip。如果需要手动安装，可以运行以下命令： py -m ensurepip --upgrade 或者，你也可以从官网下载 get-pip.py 脚本并运行： pyt ..

Python 知识总结

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

关于同步功能的建议

目前这个云端同步，如果开启了自动同步，他会在打开以及关闭的时候，都去扫描同步一次！ [图片] 这个对于多设备，多端使用的用户来说，是必要的，因为你每个设备的数据都得保持一致，那么就得去云端扫描同步！不知道是什么原因，我这边每次打开电脑，思源都要去云端扫半天，完全打开思源最起码半分钟以上！所以我现在只能改为手动同步！ ..

关于 SiYuan v3.1.12 后默认自动清理超过 180 天快照的调查

目前思源加入了自动的快照清理功能，触发时机如下：手动触发同步每 24 小时执行一次默认的配置是保留 180 天内的快照，每天保留两份。在启动、退出时的同步不会触发，但是 30s 的自动同步会触发。我个人不喜欢这个设计，因此以下的描述可能会有偏颇。不喜欢的原因如下：清理功能是自动的且没有开关默认开启，这导致假 ..

欢迎来到这里！

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

关于

Question Template

[id] Question Name

[975] 奇偶跳

单调栈解法

`TreeMap`解法

单调栈解法

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

[1726] 同积元组

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

相关帖子

Python 连接到 Microsoft SQL 数据库

简易的指数转换 Web

windows 的 just focus

Python 中 pip 常用命令

Python 知识总结

关于同步功能的建议

关于 SiYuan v3.1.12 后默认自动清理超过 180 天快照的调查

欢迎来到这里！

近期热议

推荐标签标签

最新标签

Question Bank

Question Template

[id] Question Name

[975] 奇偶跳

单调栈解法

TreeMap​解法

单调栈解法

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

[1726] 同积元组

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

相关帖子

Python 连接到 Microsoft SQL 数据库

简易的指数转换 Web

windows 的 just focus

Python 中 pip 常用命令

Python 知识总结

关于同步功能的建议

关于 SiYuan v3.1.12 后默认自动清理超过 180 天快照的调查

欢迎来到这里！

近期热议

推荐标签 标签

最新标签

`TreeMap`解法

推荐标签标签