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, t a r g e t) = \sum_{p i c k = 1}^{k} f (n - 1, t a r g e t - p i c k)$
  
  因为条件限制了 1 <= n,k <= 30，则初始状态就是 $f (1, 1.. t a r g e t)$ ，当我们只有一个骰子时，所有小于等于**k**的 target, 其结果都是 1，反之则为 0
  
  $f (1, t a r g e t) = {10 if t a r g e t \leq k if t a r g e t > k$
  
  这样从上直下，就可以推算出整个 dp 数组，dp[n][target] = $f (n, t a r g e t)$ 即为所求
- 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作为堆的替代实现 ↩

函数

函数就像「代码的魔法工具箱」，把常用的功能打包起来，随用随取。让我们用做奶茶的比喻来理解它~ ‍ 一、函数是什么？想象你开奶茶店：原料（水果、牛奶）→ 输入参数制作流程 → 函数内部的代码成品奶茶 → 返回值代码示例： # 定义「做奶茶」函数 def make_milk_tea(tea_base, toppi ..

控制流

控制流就像「程序的交通指挥官」，它决定代码该走哪条路、重复做什么事。让我们用最生活化的方式理解它~ ‍ 一、控制流是什么？想象你每天出门前：如果下雨 → 带伞（条件判断）重复刷牙 1 分钟 → 直到刷干净（循环）这就是生活中的控制流！编程中也一样 ‍ 二、条件判断：如果...就... 1️⃣ 最简单的 i ..

常用数据结构

数据结构就像「收纳数据的各种容器」️，不同的容器适合存放不同类型的数据。让我们用最生活化的方式认识它们吧~ ‍ 一、列表（List）→ 购物车特点：有顺序的容器可以随时增删改用方括号 [] 表示 # 创建购物车 cart = ['苹果', '笔记本', '️铅笔'] # 常用操作 cart.append('咖啡 ..

变量与数据类型

一、变量：就像贴标签的小盒子比喻：想象你有一个小盒子，上面贴着「零食盒」的标签，里面装了饼干。在编程中：变量名 = 盒子的标签（比如 my_snack）数据 = 盒子里的东西（比如 '饼干'）代码例子： # 把'饼干'放进叫my_snack的盒子里 my_snack = '饼干' # 查看盒子里有什么 prin ..

配置虚拟环境

虚拟环境管理（venv/pipenv/virtualenv/conda）为什么需要虚拟环境？隔离项目依赖：不同项目可能需要不同版本的 Python 或第三方库避免全局污染：防止系统 Python 环境被意外修改依赖可重现：方便团队协作和部署 1. venv（Python 内置，一般使用这个就够了，其他的知道有就 ..

欢迎来到这里！

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

关于

Question Template

[id] Question Name

[975] 奇偶跳

单调栈解法

`TreeMap`解法

单调栈解法

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

[1726] 同积元组

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

相关帖子

打包工具 -Pex

函数

控制流

常用数据结构

变量与数据类型

配置虚拟环境

认识开发工具

欢迎来到这里！

近期热议

推荐标签标签

最新标签

Question Bank

Question Template

[id] Question Name

[975] 奇偶跳

单调栈解法

TreeMap​解法

单调栈解法

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

[1726] 同积元组

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

相关帖子

打包工具 -Pex

函数

控制流

常用数据结构

变量与数据类型

配置虚拟环境

认识开发工具

欢迎来到这里！

近期热议

推荐标签 标签

最新标签

`TreeMap`解法

推荐标签标签