algorithm-problem-leetcode-1944
1944. 队列中可以看到的人数(2105)
有 n 个人排成一个队列，从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights ，每个整数 互不相同，heights[i] 表示第 i 个人的高度。
一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的，第 i 个人能看到第 j 个人的条件是 i < j 且 min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]) 。
请你返回一个长度为 n 的数组 answer ，其中 answer[i] 是第 i 个人在他右侧队列中能 看到 的 人数 。
示例 1：
123456789输入：heights = [10,6,8,5,11,9]输出：[3,1,2,1,1,0]解释：第 0 个人能看到编号为 1 ，2 和 4 的人。第 1 个人能看到编号为 2 的人。第 2 个人能看到编号为 3 和 4 的人。第 3 个人能看到编号为 4 的人。第 4 个人能看到编号为 5 的人。第 5 ...
algorithm-problem-leetcode-2866
2866. 美丽塔 II(2072)
给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。
你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。
如果以下条件满足，我们称这些塔是 美丽 的：
1 <= heights[i] <= maxHeights[i]
heights 是一个 山脉 数组。
如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山脉 数组：
对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]
对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]
请你返回满足 美丽塔 要求的方案中，高度和的最大值 。
示例 1：
123456输入：maxHeights = [5,3,4,1,1]输出：13解释：和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：- 1 <= heights[i] <= ...
algorithm-problem-leetcode-2944
2944. 购买水果需要的最少金币数(1709)
你在一个水果超市里，货架上摆满了玲琅满目的奇珍异果。
给你一个下标从 1 开始的数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。
水果超市有如下促销活动：
如果你花费 price[i] 购买了下标为 i 的水果，那么你可以免费获得下标范围在 [i + 1, i + i] 的水果。
注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以获得它的奖励。
请你返回获得所有水果所需要的 最少 金币数。
示例 1：
**输入：**prices = [3,1,2]
**输出：**4
解释：
用 prices[0] = 3 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
用 prices[1] = 1 个金币购买第 2 个水果，你可以免费获得第 3 个水果。
免费获得第 3 个水果。
请注意，即使您可以免费获得第 2 个水果作为购买第 1 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。
示例 2：
**输入：**prices = [1,10 ...
algorithm-problem-leetcode-2896
2896. 执行操作使两个字符串相等(2172)
给你两个下标从 0 开始的二进制字符串 s1 和 s2 ，两个字符串的长度都是 n ，再给你一个正整数 x 。
你可以对字符串 s1 执行以下操作 任意次 ：
选择两个下标 i 和 j ，将 s1[i] 和 s1[j] 都反转，操作的代价为 x 。
选择满足 i < n - 1 的下标 i ，反转 s1[i] 和 s1[i + 1] ，操作的代价为 1 。
请你返回使字符串 s1 和 s2 相等的 最小 操作代价之和，如果无法让二者相等，返回 -1 。
注意 ，反转字符的意思是将 0 变成 1 ，或者 1 变成 0 。
示例 1：
1234567输入：s1 = "1100011000", s2 = "0101001010", x = 2输出：4解释：我们可以执行以下操作：- 选择 i = 3 执行第二个操作。结果字符串是 s1 = "1101111000" 。- 选择 i = 4 执行第二个操作。结果字符串是 s1 = "1101001000" 。 ...
algorithm-dp-game-theory
博弈dp
一人最大化得分，一人最小化得分
3283. 吃掉所有兵需要的最多移动次数
algorithm-problem-leetcode-3283
3283. 吃掉所有兵需要的最多移动次数
给你一个 50 x 50 的国际象棋棋盘，棋盘上有 一个 马和一些兵。给你两个整数 kx 和 ky ，其中 (kx, ky) 表示马所在的位置，同时还有一个二维数组 positions ，其中 positions[i] = [xi, yi] 表示第 i 个兵在棋盘上的位置。
Alice 和 Bob 玩一个回合制游戏，Alice 先手。玩家的一次操作中，可以执行以下操作：
玩家选择一个仍然在棋盘上的兵，然后移动马，通过 最少 的 步数 吃掉这个兵。注意 ，玩家可以选择 任意 一个兵，不一定 要选择从马的位置出发 最少 移动步数的兵。
在马吃兵的过程中，马 可能 会经过一些其他兵的位置，但这些兵 不会 被吃掉。只有 选中的兵在这个回合中被吃掉。
Alice 的目标是 最大化 两名玩家的 总 移动次数，直到棋盘上不再存在兵，而 Bob 的目标是 最小化 总移动次数。
假设两名玩家都采用 最优 策略，请你返回 Alice 可以达到的 最大 总移动次数。
在一次 移动 中，如下图所示，马有 8 个可以移动到的位置，每个移动位置都是沿着坐标轴的一个方向 ...
algorithm-problem-leetcode-3260
3260. 找出最大的 N 位 K 回文数(2370)
给你两个 正整数 n 和 k。
如果整数 x 满足以下全部条件，则该整数是一个 k 回文数：
x 是一个
回文数
。
x 可以被 k 整除。
以字符串形式返回 最大的 n 位 k 回文数。
注意，该整数 不 含前导零。
示例 1：
输入： n = 3, k = 5
输出： “595”
解释：
595 是最大的 3 位 k 回文数。
示例 2：
输入： n = 1, k = 4
输出： “8”
解释：
1 位 k 回文数只有 4 和 8。
示例 3：
输入： n = 5, k = 6
输出： “89898”
提示：
1 <= n <= 10^5
1 <= k <= 9
数位dp，记忆化搜索
123456789101112131415161718192021222324252627282930313233class Solution { char res[]; public String largestPalindrome(int n, int k) { ...
algorithm-problem-leetcode-3251
3251. 单调数组对的数目 II(2323)
给你一个长度为 n 的 正 整数数组 nums 。
如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：
两个数组的长度都是 n 。
arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。
arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。
对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。
请你返回所有 单调 数组对的数目。
由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。
示例 1：
**输入：**nums = [2,3,2]
**输出：**4
解释：
单调数组对包括：
([0, 1, 1], [2, 2, 1])
([0, 1, 2], [2, 2, 0])
([0, 2, 2], [2, 1, 0])
([1, 2, 2] ...
algorithm-problem-leetcode-2920
2920. 收集所有金币可获得的最大积分(2351)
节点 0 处现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 。给你一个长度为 n - 1 的二维 整数 数组 edges ，其中 edges[i] = [ai, bi] 表示在树上的节点 ai 和 bi 之间存在一条边。另给你一个下标从 0 开始、长度为 n 的数组 coins 和一个整数 k ，其中 coins[i] 表示节点 i 处的金币数量。
从根节点开始，你必须收集所有金币。要想收集节点上的金币，必须先收集该节点的祖先节点上的金币。
节点 i 上的金币可以用下述方法之一进行收集：
收集所有金币，得到共计 coins[i] - k 点积分。如果 coins[i] - k 是负数，你将会失去 abs(coins[i] - k) 点积分。
收集所有金币，得到共计 floor(coins[i] / 2) 点积分。如果采用这种方法，节点 i 子树中所有节点 j 的金币数 coins[j] 将会减少至 floor(coins[j] / 2) 。
返回收集 所有 树节点的金币之后可以获得的最大积分。
示例 1：
...
algorithm-problem-leetcode-2581
2581. 统计可能的树根数目(2228)
Alice 有一棵 n 个节点的树，节点编号为 0 到 n - 1 。树用一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ai, bi] ，表示树中节点 ai 和 bi 之间有一条边。
Alice 想要 Bob 找到这棵树的根。她允许 Bob 对这棵树进行若干次 猜测 。每一次猜测，Bob 做如下事情：
选择两个 不相等 的整数 u 和 v ，且树中必须存在边 [u, v] 。
Bob 猜测树中 u 是 v 的 父节点 。
Bob 的猜测用二维整数数组 guesses 表示，其中 guesses[j] = [uj, vj] 表示 Bob 猜 uj 是 vj 的父节点。
Alice 非常懒，她不想逐个回答 Bob 的猜测，只告诉 Bob 这些猜测里面 至少 有 k 个猜测的结果为 true 。
给你二维整数数组 edges ，Bob 的所有猜测和整数 k ，请你返回可能成为树根的 节点数目 。如果没有这样的树，则返回 0。
示例 1：
123456789输入：edges = [[0,1],[1,2] ...