moecly

自由之路 Category Difficulty Likes Dislikes algorithms Hard (50.82%) 249 - Tags Companies 电子游戏“辐射4”中，任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘，并使用表盘拼写特定关键词才能开门。 给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。 最初，ring 的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。 旋转 ring 拼出 key 字符 key[i] 的阶段中： 您可以将 ring 顺时针或逆时针旋转 一个位置 ，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。 如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行 ...

等差数列划分 II - 子序列 Category Difficulty Likes Dislikes algorithms Hard (54.91%) 262 - Tags Companies 给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。 如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。 例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。 再例如，[1, 1, 2, 5, 7] 不是等差序列。 数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。 例如，[2,5,10] 是 [1,2,1,***2***,4,1,***5\***,***10***] 的一个子序列。 题目数据保证答案是一个 32-bit 整数。 示例 1： 12345678910输入：nums = [2,4,6,8,10]输出：7解释：所有的等差子序列为：[2,4,6][4,6,8][6,8,10][2,4,6,8][4,6,8,10][2,4,6, ...

分割数组的最大值 Category Difficulty Likes Dislikes algorithms Hard (58.74%) 731 - Tags Companies 给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法使得这 m 个子数组各自和的最大值最小。 示例 1： 123456输入：nums = [7,2,5,10,8], m = 2输出：18解释：一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。 示例 2： 12输入：nums = [1,2,3,4,5], m = 2输出：9 示例 3： 12输入：nums = [1,4,4], m = 3输出：4 提示： 1 <= nums.length <= 1000 0 <= nums[i] <= 106 1 <= m <= min(50, nums.length) 动态规划(c ...

青蛙过河 Category Difficulty Likes Dislikes algorithms Hard (45.80%) 447 - Tags Companies 一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。 给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 1 跳至单元格 2 ）。 如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。 示例 1： 123输入：stones = [0,1,3,5,6,8,12,17]输出：true解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 ...

买卖股票的最佳时机 IV Category Difficulty Likes Dislikes algorithms Hard (42.25%) 806 - Tags Companies 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1： 123输入：k = 2, prices = [2,4,1]输出：2解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。 示例 2： 1234输入：k = 2, prices = [3,2,6,5,0,3]输出：7解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 ...

俄罗斯套娃信封问题 Category Difficulty Likes Dislikes algorithms Hard (40.57%) 803 - Tags Companies 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。 注意：不允许旋转信封。 示例 1： 123输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]输出：3解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。 示例 2： 12输入：envelopes = [[1,1],[1,1],[1,1]]输出：1 提示： 1 <= envelopes.length <= 105 envelopes[i].length == 2 1 &l ...

修剪二叉搜索树 Category Difficulty Likes Dislikes algorithms Medium (66.80%) 666 - Tags Companies 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。 示例 1： 12输入：root = [1,0,2], low = 1, high = 2输出：[1,null,2] 示例 2： 12输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3输出：[3,2,null,1] 提示： 树中节点数在范围 [1, 104] 内 0 <= Node.val <= 104 树中每个节点的值都是 唯一 的 题目数据 ...

地下城游戏 Category Difficulty Likes Dislikes algorithms Hard (48.68%) 664 - Tagsbinary-search | dynamic-programming Companiesmicrosoft 一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。 为了尽快到达公主，骑士决定每次只向右或向下移动一步。 编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。 例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -&g ...

分割回文串 II Category Difficulty Likes Dislikes algorithms Hard (49.72%) 617 - Tagsdynamic-programming CompaniesUnknown 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。 返回符合要求的 最少分割次数 。 示例 1： 123输入：s = "aab"输出：1解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。 示例 2： 12输入：s = "a"输出：0 示例 3： 12输入：s = "ab"输出：1 提示： 1 <= s.length <= 2000 s 仅由小写英文字母组成 动态规划(c++)123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555 ...

单词接龙 II Category Difficulty Likes Dislikes algorithms Hard (39.75%) 608 - Tagsarray | string | backtracking | breadth-first-search Companiesamazon | yelp 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足： 每对相邻的单词之间仅有单个字母不同。 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。 sk == endWord 给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回 ...