Question Bank

本贴最后更新于 565 天前,其中的信息可能已经事过境迁
  1. ⚙ Question Template1
  2. 📄 [975] 奇偶跳2
  3. 📄 [1155] 掷骰子等于目标和的方法数5
  4. 📄 [1726] 同积元组6
  5. 📄 [2530] 执行 K 次操作后的最大分数7


  1. Question Template

    [id] Question Name

    • address

      question address

    • tags

      ​#leetcode#​

    • solution explain

    • solution code

      • Python3

  2. [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 - 单调栈1make

        偶数跳同理,只需将元素取负即可(小于等于并最接近自己的元素,取负后成为大于等于并最接近自己)。

      在奇偶数跳跃落点两个数组的基础上即可求出 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​解法

        单调栈解法1中我们所做的事情 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 - 单调栈1make

    偶数跳同理,只需将元素取负即可(小于等于并最接近自己的元素,取负后成为大于等于并最接近自己)。

  3. [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 数组进行压缩,以优化空间占用和运行时间。

  4. [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

  5. [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 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    557 引用 • 675 回帖

相关帖子

回帖

欢迎来到这里!

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

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    286 引用 • 248 回帖
  • webpack

    webpack 是一个用于前端开发的模块加载器和打包工具,它能把各种资源,例如 JS、CSS(less/sass)、图片等都作为模块来使用和处理。

    42 引用 • 130 回帖 • 250 关注
  • 尊园地产

    昆明尊园房地产经纪有限公司,即:Kunming Zunyuan Property Agency Company Limited(简称“尊园地产”)于 2007 年 6 月开始筹备,2007 年 8 月 18 日正式成立,注册资本 200 万元,公司性质为股份经纪有限公司,主营业务为:代租、代售、代办产权过户、办理银行按揭、担保、抵押、评估等。

    1 引用 • 22 回帖 • 786 关注
  • Mac

    Mac 是苹果公司自 1984 年起以“Macintosh”开始开发的个人消费型计算机,如:iMac、Mac mini、Macbook Air、Macbook Pro、Macbook、Mac Pro 等计算机。

    168 引用 • 597 回帖
  • 一些有用的避坑指南。

    69 引用 • 93 回帖
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 548 关注
  • JavaScript

    JavaScript 一种动态类型、弱类型、基于原型的直译式脚本语言,内置支持类型。它的解释器被称为 JavaScript 引擎,为浏览器的一部分,广泛用于客户端的脚本语言,最早是在 HTML 网页上使用,用来给 HTML 网页增加动态功能。

    730 引用 • 1280 回帖
  • HTML

    HTML5 是 HTML 下一个的主要修订版本,现在仍处于发展阶段。广义论及 HTML5 时,实际指的是包括 HTML、CSS 和 JavaScript 在内的一套技术组合。

    108 引用 • 295 回帖
  • wolai

    我来 wolai:不仅仅是未来的云端笔记!

    2 引用 • 14 回帖 • 4 关注
  • BAE

    百度应用引擎(Baidu App Engine)提供了 PHP、Java、Python 的执行环境,以及云存储、消息服务、云数据库等全面的云服务。它可以让开发者实现自动地部署和管理应用,并且提供动态扩容和负载均衡的运行环境,让开发者不用考虑高成本的运维工作,只需专注于业务逻辑,大大降低了开发者学习和迁移的成本。

    19 引用 • 75 回帖 • 666 关注
  • Jenkins

    Jenkins 是一套开源的持续集成工具。它提供了非常丰富的插件,让构建、部署、自动化集成项目变得简单易用。

    54 引用 • 37 回帖 • 1 关注
  • 京东

    京东是中国最大的自营式电商企业,2015 年第一季度在中国自营式 B2C 电商市场的占有率为 56.3%。2014 年 5 月,京东在美国纳斯达克证券交易所正式挂牌上市(股票代码:JD),是中国第一个成功赴美上市的大型综合型电商平台,与腾讯、百度等中国互联网巨头共同跻身全球前十大互联网公司排行榜。

    14 引用 • 102 回帖 • 317 关注
  • flomo

    flomo 是新一代 「卡片笔记」 ,专注在碎片化时代,促进你的记录,帮你积累更多知识资产。

    6 引用 • 143 回帖 • 1 关注
  • abitmean

    有点意思就行了

    34 关注
  • IPFS

    IPFS(InterPlanetary File System,星际文件系统)是永久的、去中心化保存和共享文件的方法,这是一种内容可寻址、版本化、点对点超媒体的分布式协议。请浏览 IPFS 入门笔记了解更多细节。

    21 引用 • 245 回帖 • 226 关注
  • PHP

    PHP(Hypertext Preprocessor)是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点,主要适用于 Web 开发领域,据说是世界上最好的编程语言。

    181 引用 • 408 回帖 • 485 关注
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    557 引用 • 675 回帖
  • Shell

    Shell 脚本与 Windows/Dos 下的批处理相似,也就是用各类命令预先放入到一个文件中,方便一次性执行的一个程序文件,主要是方便管理员进行设置或者管理用的。但是它比 Windows 下的批处理更强大,比用其他编程程序编辑的程序效率更高,因为它使用了 Linux/Unix 下的命令。

    125 引用 • 74 回帖 • 1 关注
  • Vim

    Vim 是类 UNIX 系统文本编辑器 Vi 的加强版本,加入了更多特性来帮助编辑源代码。Vim 的部分增强功能包括文件比较(vimdiff)、语法高亮、全面的帮助系统、本地脚本(Vimscript)和便于选择的可视化模式。

    29 引用 • 66 回帖
  • B3log

    B3log 是一个开源组织,名字来源于“Bulletin Board Blog”缩写,目标是将独立博客与论坛结合,形成一种新的网络社区体验,详细请看 B3log 构思。目前 B3log 已经开源了多款产品:SymSoloVditor思源笔记

    1063 引用 • 3455 回帖 • 160 关注
  • 书籍

    宋真宗赵恒曾经说过:“书中自有黄金屋,书中自有颜如玉。”

    78 引用 • 396 回帖
  • 快应用

    快应用 是基于手机硬件平台的新型应用形态;标准是由主流手机厂商组成的快应用联盟联合制定;快应用标准的诞生将在研发接口、能力接入、开发者服务等层面建设标准平台;以平台化的生态模式对个人开发者和企业开发者全品类开放。

    15 引用 • 127 回帖 • 2 关注
  • Mobi.css

    Mobi.css is a lightweight, flexible CSS framework that focus on mobile.

    1 引用 • 6 回帖 • 758 关注
  • 电影

    这是一个不能说的秘密。

    122 引用 • 608 回帖 • 1 关注
  • Swift

    Swift 是苹果于 2014 年 WWDC(苹果开发者大会)发布的开发语言,可与 Objective-C 共同运行于 Mac OS 和 iOS 平台,用于搭建基于苹果平台的应用程序。

    36 引用 • 37 回帖 • 547 关注
  • OpenResty

    OpenResty 是一个基于 NGINX 与 Lua 的高性能 Web 平台,其内部集成了大量精良的 Lua 库、第三方模块以及大多数的依赖项。用于方便地搭建能够处理超高并发、扩展性极高的动态 Web 应用、Web 服务和动态网关。

    17 引用 • 53 关注
  • PostgreSQL

    PostgreSQL 是一款功能强大的企业级数据库系统,在 BSD 开源许可证下发布。

    22 引用 • 22 回帖 • 2 关注