每周有营养的大厂算法面试题 第001节 2021年11月第4周流行算法题目解析 给定一棵多叉树的头节点head，每个节点只有黑白两色 所有黑节点都保留，所有从头节点到黑节点路径上的点都保留 返回处理后树的头节点 我们正在玩一个猜数游戏，游戏规则如下： 我从 1 到 n 之间选择一个数字。 你来猜我选了哪个数字。 如果你猜到正确的数字，就会 赢得游戏 。 如果你猜错了，那么我会告诉你，我选的数字比你的 更大或者更小 ，并且你需要继续猜数。 每当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。 如果你花光了钱，就会 输掉游戏 。 给你一个特定的数字 n ，返回能够 确保你获胜 的最小现金数，不管我选择那个数字 。 Leetcode链接 : https://leetcode.com/problems/guess-number-higher-or-lower-ii/ 来自真实面试，同学给我的问题 限制：0 <= start <= end，0 <= target <= 64 [start,end]范围上的数字，有多少数字二进制中1的个数等于target 第002节 2021年12月第1周流行算法题目解析 int n, int[][] roads, int x, int y n表示城市数量，城市编号0~n-1 roads[i][j] == distance，表示城市i到城市j距离为distance(无向图) 求城市x到城市y的最短距离 一开始屏幕上什么也没有，粘贴板里什么也没有， 你只能在键盘上做如下4种操作中的1种： 输入：在屏幕上已经显示内容的后面加一个A 全选：把屏幕上已经显示的全部内容选中 复制：被选中的内容复制进粘贴板 粘贴：在屏幕上已经显示内容的后面添加粘贴板里的内容 给定一个正数n，表示你能操作的步数， 返回n步内你能让最多多少个A显示在屏幕上 Leetcode链接 : https://leetcode.com/problems/4-keys-keyboard/ 给定一棵树的头节点head，原本是一棵正常的树 现在，在树上多加了一条冗余的边 请找到这条冗余的边并返回 Leetcode链接 : https://leetcode.com/problems/redundant-connection-ii/ 第003节 2021年12月第2周流行算法题目解析 给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。 另外给一个下标从 0 开始的二维整数数组 meetings ， 其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。 一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson 。 专家 0 有一个 秘密 ，最初，他在时间 0 将这个秘密分享给了专家 firstPerson 。 这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。更正式的表达是，每次会议， 如果专家 xi 在时间 timei 时知晓这个秘密，那么他将会与专家 yi 分享这个秘密，反之亦然。 秘密共享是 瞬时发生 的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。 在所有会议都结束之后，返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。 Leetcode链接 : https://leetcode.com/problems/find-all-people-with-secret/ 来自美团 所有黑洞的中心点记录在holes数组里 比如[[3,5] [6,9]]表示，第一个黑洞在(3,5)，第二个黑洞在(6,9) 并且所有黑洞的中心点都在左下角(0,0)，右上角(x,y)的区域里 飞船一旦开始进入黑洞，就会被吸进黑洞里 返回如果统一所有黑洞的半径，最大半径是多少， 依然能保证飞船从(0,0)能到达(x,y) arr数组长度为n, magic数组长度为m 比如 arr = { 3, 1, 4, 5, 7 }，如果完全不改变arr中的值， 那么收益就是累加和 = 3 + 1 + 4 + 5 + 7 = 20 magics[i] = {a,b,c} 表示arr[a~b]中的任何一个值都能改成c 并且每一种操作，都可以执行任意次，其中 0 <= a <= b < n 那么经过若干次的魔法操作，你当然可能得到arr的更大的累加和 返回arr尽可能大的累加和 n <= 10^7 m <= 10^6 arr中的值和c的范围 <= 10^12 已知一棵二叉树上所有的值都不一样， 给定这棵二叉树的头节点head， 给定一个整型数组arr，arr里放着不同的值，每个值一定在树上 返回数组里所有值的最低公共祖先 Leetcode链接 : https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv/ 给定一棵多叉树的头节点head 每个节点的颜色只会是0、1、2、3中的一种 任何两个节点之间的都有路径 如果节点a和节点b的路径上，包含全部的颜色，这条路径算达标路径 (a -> ... -> b)和(b -> ... -> a)算两条路径 求多叉树上达标的路径一共有多少？ 点的数量 <= 10^5 第004节 2021年12月第3周流行算法题目解析 来自TME2022校园招聘后台开发/运营开发/业务运维/应用开发笔试 给定一棵二叉树的头节点head，和一个正数k。从最底层开始，每一层右移k位，然后往上走过每一层，进行树的调整 返回调整之后树的头节点 具体详情请参加如下的测试页面 测试链接 : https://www.nowcoder.com/test/33701596/summary 本题目为该试卷第1题 来自TME2022校园招聘后台开发/运营开发/业务运维/应用开发笔试 给定一个只由'0'和'1'组成的字符串，代表一个无符号整数 你只能在连续的一个子串上，翻转子串，也就是子串上，0变1，1变0。返回最大的结果 具体详情请参加如下的测试页面 测试链接 : https://www.nowcoder.com/test/33701596/summary 本题目为该试卷第2题 来自TME2022校园招聘后台开发/运营开发/业务运维/应用开发笔试 给定两个参数n和k，返回m 含义：k进制的情况下，把1~m每一位的状态列出来，其中1状态出现的数量要>=n 返回最小的、能做到这一点的m值 具体详情请参加如下的测试页面 测试链接 : https://www.nowcoder.com/test/33701596/summary 本题目为该试卷第3题 你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中： 0 表示障碍，无法触碰 1 表示地面，可以行走 比1大的数 表示有树的单元格，也可以行走，数值表示树的高度 每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。 你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。 你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。 可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树 Leetcode链接 : https://leetcode.com/problems/cut-off-trees-for-golf-event/ 来自CMU入学申请考试 给定一个长度为 N 的字符串 S，由字符'a'和'b'组成，空隙由 '?' 表示 你的任务是用a字符或b字符替换每个间隙， 替换完成后想让连续出现同一种字符的最长子串尽可能短 例如，S = "aa??bbb"， 如果将"??"替换为"aa" ，即"aaaabbb"，则由相等字符组成的最长子串长度为4 如果将"??"替换为"ba" ，即"aababbb"，则由相等字符组成的最长子串长度为3 那么方案二是更好的结果，返回3 S的长度 <= 10^6 第005节 2021年12月第4周流行算法题目解析 来自美团 给定一个无向图 从任何一个点x出发，比如有一条路径: x -> a -> b -> c -> y 这条路径上有5个点并且5个点都不一样的话，我们说(x,a,b,c,y)是一条合法路径 这条合法路径的代表，就是x,a,b,c,y所组成的集合，我们叫做代表集合 如果从b到y，还有一条路径叫(b,a,c,x,y)，那么(x,a,b,c,y)和(b,a,c,x,y)是同一个代表集合 返回这个无向图中所有合法路径的代表集合数量 题目给定点的数量n <= 15，边的数量m <= 60 所有的点编号都是从0~n-1的 来自北京北明数科信息技术有限公司 class AreaResource { String area; // area表示的是地区全路径,最多可能有6级，比如： 中国,四川,成都  或者  中国,浙江,杭州 String spliter; // 比如：逗号 -> , long count; // 表示地区的门店数量 } 现在需要把  List 进行转换，需要做到同级的地域能合并 比如：area为中国,四川,成都 ，有10个门店；area为中国,浙江,杭州，有25个门店；area为中国,浙江,义乌，有22个门店 最终生成的JSON字符串为： {"中国":{"四川":{"成都":10]},"浙江":{"义乌":22,"杭州":25}}} 请实现下面的方法 public String mergeCount(List areas)  来自hulu 有一个以原点为圆心，半径为1的圆 在这个圆的圆周上，有一些点 因为所有的点都在圆周上，所以每个点可以有很简练的表达 比如：用0来表示一个圆周上的点，这个点就在(1,0)位置 比如：用6000来表示一个点，这个点是(1,0)点沿着圆周逆时针转60.00度之后所在的位置 比如：用18034来表示一个点，这个点是(1,0)点沿着圆周逆时针转180.34度之后所在的位置 这样一来，所有的点都可以用[0, 36000)范围上的数字来表示 那么任意三个点都可以组成一个三角形，返回能组成钝角三角形的数量 整个二维平面算是一张地图，给定[x,y]，表示你站在x行y列 你可以选择面朝的任何方向 给定一个正数值angle，表示你视野的角度为 这个角度内你可以看无穷远，这个角度外你看不到任何东西 给定一批点的二维坐标， 返回你在朝向最好的情况下，最多能看到几个点 有m个同样的苹果，认为苹果之间无差别 有n个同样的盘子，认为盘子之间也无差别 还有，比如5个苹果如果放进3个盘子， 那么1、3、1和1、1、3和3、1、1的放置方法，也认为是一种方法 如上的设定下，返回有多少种放置方法 第006节 2021年12月第5周流行算法题目解析 有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱， 以及不同程度的安静值（quietness） 为了方便起见，我们将编号为 x 的人简称为 "person x "。 给你一个数组 richer ，其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱 另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值 richer 中所给出的数据 逻辑自洽 也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况 现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是： 在所有拥有的钱肯定不少于 person x 的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。 leetcode链接 : https://leetcode.com/problems/loud-and-rich/ 来自hulu 有n个人，m个任务，任务之间有依赖记录在int[][] depends里 比如: depends[i] = [a, b]，表示a任务依赖b任务的完成 其中 0 <= a < m，0 <= b < m 1个人1天可以完成1个任务，每个人都会选当前能做任务里，标号最小的任务 一个任务所依赖的任务都完成了，该任务才能开始做 返回n个人做完m个任务，需要几天 来自hulu 你只有1*1、1*2、1*3、1*4，四种规格的砖块 你想铺满n行m列的区域，规则如下： 1）不管那种规格的砖，都只能横着摆 比如1*3这种规格的砖，3长度是水平方向，1长度是竖直方向 2）会有很多方法铺满整个区域，整块区域哪怕有一点点不一样，就算不同的方法 3）区域内部(不算区域整体的4条边界)，不能有任何砖块的边界线（从上一直贯穿到下） 返回符合三条规则下，铺满n行m列的区域，有多少种不同的摆放方法 第007节 2022年1月第1周流行算法题目解析 来自阿里 给定一个只由'a'和'b'组成的字符串str， str中"ab"和"ba"子串都可以消除， 消除之后剩下字符会重新靠在一起，继续出现可以消除的子串... 你的任务是决定一种消除的顺序，最后让str消除到尽可能的短 返回尽可能的短的剩余字符串 在一张 无向 图上，节点编号0~N-1。老鼠开始在1节点，猫在2节点，0号节点是洞，老鼠想进洞 老鼠第先出发，猫后出发，轮流行动。 在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动 此外猫无法移动到洞中（节点 0）。 然后，游戏在出现以下三种情形之一时结束： 如果猫和老鼠出现在同一个节点，猫获胜。 如果老鼠到达洞中，老鼠获胜。 如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。 给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏，返回谁获胜 leetcode链接 : https://leetcode.com/problems/cat-and-mouse/ 给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ，其中 n >= m ， 数组下标 从 1 开始 计数。 初始时，你的分数为 0 。 你需要执行恰好 m 步操作。在第 i 步操作（从 1 开始 计数）中，需要： 选择数组 nums 开头处或者末尾处 的整数 x 。 你获得 multipliers[i] * x 分，并累加到你的分数中。 将 x 从数组 nums 中移除。 在执行 m 步操作后，返回 最大 分数。 leetcode链接 : https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/ 来自学员问题 给定一个二维数组，其中全是非负数 每一步都可以往上、下、左、右四个方向运动 返回从左下角走到右下角的最短距离 第008节 2022年1月第2周流行算法题目解析 给定一个非常大的List list 每一个字符串类似 : "hello,world,have,hello,world" 这一个字符串中，有2个hello，2个world，1个have 请设计一种多线程处理方案，统计list中每一个字符串，切分出来的单词数量，并且汇总 最终返回一个HashMap表示每个字符串在list中一共出现几次 多线程设计 + 算法 本题没有代码实现，会在课上讲述思路 给定一个正数数组arr，其中每个值代表砖块长度 所有砖块等高等宽，只有长度有区别 每一层可以用1块或者2块砖来摆 要求每一层的长度一样 要求必须使用所有的砖块 请问最多摆几层 来自兴业数金 给定一个字符串形式的数，比如"3421"或者"-8731" 如果这个数不在-32768~32767范围上，那么返回"NODATA" 如果这个数在-32768~32767范围上，那么这个数就没有超过16个二进制位所能表达的范围 返回这个数的2进制形式的字符串和16进制形式的字符串，用逗号分割 给你一个下标从 0 开始包含 n 个正整数的数组 arr ，和一个正整数 k 。 如果对于每个满足 k <= i <= n-1 的下标 i ，都有 arr[i-k] <= arr[i] ，那么我们称 arr 是 K 递增 的。 比方说，arr = [4, 1, 5, 2, 6, 2] 对于 k = 2 是 K 递增的，因为： arr[0] <= arr[2] (4 <= 5) arr[1] <= arr[3] (1 <= 2) arr[2] <= arr[4] (5 <= 6) arr[3] <= arr[5] (2 <= 2) 但是，相同的数组 arr 对于 k = 1 不是 K 递增的（因为 arr[0] > arr[1]）， 对于 k = 3 也不是 K 递增的（因为 arr[0] > arr[3] ）。 每一次 操作 中，你可以选择一个下标 i 并将 arr[i] 改成任意 正整数。 请你返回对于给定的 k ，使数组变成 K 递增的 最少操作次数 。 leetcode链接 : https://leetcode.com/problems/minimum-operations-to-make-the-array-k-increasing/ 来自美团 小美有一个长度为n的数组， 为了使得这个数组的和尽量大，她向会魔法的小团进行求助 小团可以选择数组中至多两个不相交的子数组， 并将区间里的数全都变为原来的10倍 小团想知道他的魔法最多可以帮助小美将数组的和变大到多少? 给定一个非负数组arr，学生依次坐在0~N-1位置，每个值表示学生的安静值 如果在i位置安置插班生，那么i位置的安静值变成0，同时任何同学都会被影响到而减少安静值 同学安静值减少的量: N - 这个同学到插班生的距离 但是减到0以下的话，当做0处理 返回一个和arr等长的ans数组，ans[i]表示如果把插班生安排在i位置，所有学生的安静值的和 比如 : arr = {3,4,2,1,5}，应该返回{4,3,2,3,4} 比如 : arr = {10,1,10,10,10}，应该返回{24,27,20,20,22} arr长度 <= 10^5 arr中值 <= 2 * 10^5 注意：本题在直播课上讲错了，已经发了重新录制的视频，请一定要看更正后的视频 第009节 2022年1月第3周流行算法题目解析 A*算法 过程和Dijskra高度相处 有到终点的预估函数 只要预估值<=客观上最优距离，就是对的 预估函数是一种吸引力： 1）合适的吸引力可以提升算法的速度 2）吸引力“过强”会出现错误 在一个10^6 * 10^6的网格中， source = [sx, sy]是出发位置，target = [tx, ty]是目标位置 数组blocked是封锁的方格列表，被禁止的方格数量不超过200 blocked[i] = [xi, yi] 表示(xi, yi)的方格是禁止通行的 每次移动都可以走上、下、左、右四个方向 但是来到的位置不能在封锁列表blocked上 同时不允许走出网格 如果从source能到达target返回 true。否则返回false。 来自字节跳动 给定一个数组arr，其中的值有可能正、负、0 给定一个正数k 返回累加和>=k的所有子数组中，最短的子数组长度 第010节 2022年1月第4周流行算法题目解析 things是一个N*3的二维数组，商品有N件，商品编号从1~N 比如things[3] = [300, 2, 6] 代表第3号商品：价格300，重要度2，它是6号商品的附属商品 再比如things[6] = [500, 3, 0] 代表第6号商品：价格500，重要度3，它不是任何附属，它是主商品 每件商品的收益是价格*重要度，花费就是价格 如果一个商品是附属品，那么只有它附属的主商品购买了，它才能被购买 任何一个附属商品，只会有1个主商品 任何一个主商品的附属商品数量，不会超过2件 主商品和附属商品的层级最多有2层 给定二维数组things、钱数money，返回整体花费不超过money的情况下，最大的收益总和 来自美团 小团去参加军训，军训快要结束了，长官想要把大家一排n个人分成m组，然后让每组分别去参加阅兵仪式 只能选择相邻的人一组，不能随意改变队伍中人的位置 阅兵仪式上会进行打分，其中有一个奇怪的扣分点是每组的最大差值，即每组最大值减去最小值 长官想要让这分成的m组总扣分量最小，即这m组分别的极差之和最小 长官正在思索如何安排中，就让小团来帮帮他吧 给定一个包含 [0，n) 中不重复整数的黑名单 blacklist 写一个函数从 [0, n) 中返回一个不在 blacklist 中的随机整数 对它进行优化使其尽量少调用系统方法 Math.random() 1 <= n <= 1000000000 0 <= blacklist.length < min(100000, N) leetcode链接: https://leetcode.com/problems/random-pick-with-blacklist/ 来自米哈游 给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' 返回在甲板 board 上放置的 战舰 的数量 战舰只能水平或者垂直放置在 board 上。换句话说，战舰只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状建造 其中 k 可以是任意大小 两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰） leetcode链接: https://leetcode.com/problems/battleships-in-a-board 第011节 2022年2月第2周流行算法题目解析 给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字 您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。 你须遵守以下规则: 除法运算符 '/' 表示实数除法，而不是整数除法。 例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。 每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。 例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。 你不能把数字串在一起 例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。 如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。 leetcode链接: https://leetcode.com/problems/24-game/ 设计位图 leetcode链接: https://leetcode-cn.com/problems/design-bitset/ 给定一个整数数组，返回所有数对之间的第 k 个最小距离 一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值 leetcode链接 : https://leetcode.com/problems/find-k-th-smallest-pair-distance/ 从点 (x, y) 可以转换到 (x, x+y)  或者 (x+y, y)。 给定一个起点 (sx, sy) 和一个终点 (tx, ty)， 如果通过一系列的转换可以从起点到达终点， 则返回 True ，否则返回 False。 leetcode链接 : https://leetcode.com/problems/reaching-points/ Alice 有一个下标从 0 开始的数组 arr ，由 n 个正整数组成。 她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher ： 对每个满足 0 <= i < n 的下标 i ，lower[i] = arr[i] - k 对每个满足 0 <= i < n 的下标 i ，higher[i] = arr[i] + k 不幸地是，Alice 丢失了全部三个数组。但是，她记住了在数组 lower 和 higher 中出现的整数 但不知道每个整数属于哪个数组。请你帮助 Alice 还原原数组。 给你一个由 2n 个整数组成的整数数组 nums ，其中 恰好 n 个整数出现在 lower ，剩下的出现在 higher ， 还原并返回 原数组 arr 。如果出现答案不唯一的情况，返回 任一 有效数组。 注意：生成的测试用例保证存在 至少一个 有效数组 arr 。 leetcode链接 : https://leetcode.com/problems/recover-the-original-array/ 第012节 2022年2月第3周流行算法题目解析 有 n 个城市通过一些航班连接。给你一个数组 flights ， 其中 flights[i] = [fromi, toi, pricei] ， 表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst， 你的任务是找到出一条最多经过 k 站中转的路线， 使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。 leetcode链接: https://leetcode.com/problems/cheapest-flights-within-k-stops/ 厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子 1）吃掉一个橘子。 2）如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。 3）如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。 每天你只能从以上 3 种方案中选择一种方案。 请你返回吃掉所有 n 个橘子的最少天数。 leetcode链接: https://leetcode.com/problems/minimum-number-of-days-to-eat-n-oranges/ 在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方 机器人可以接受下列三条指令之一： "G"：直走 1 个单位 "L"：左转 90 度 "R"：右转 90 度 机器人按顺序执行指令 instructions，并一直重复它们。 只有在平面中存在环使得机器人永远无法离开时，返回 true 否则，返回 false。 leetcode链接 : https://leetcode.com/problems/robot-bounded-in-circle/ 来自微软 给定一个数组arr，一个正数num，一个正数k 可以把arr中的某些数字拿出来组成一组 要求该组中的最大值减去最小值<=num 且该组数字的个数一定要正好等于k 每个数字只能选择进某一组，不能进多个组 返回arr中最多有多少组 Alice 和 Bob 设计了一款新的石子游戏 现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值 给你一个整数数组 stones ，其中 stones[i] 是第 i 个石子的价值。 Alice 和 Bob 轮流进行自己的回合，Alice 先手 每一回合，玩家需要从 stones 中移除任一石子 如果玩家移除石子后，导致 所有已移除石子 的价值 总和 可以被 3 整除，那么该玩家就 输掉游戏 。 如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。 假设两位玩家均采用 最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 false 。 leetcode链接 : https://leetcode.com/problems/stone-game-ix/ 第013节 2022年2月第4周流行算法题目解析 来自微软 比如，str = "ayxbx" 有以下4种切法 : a | yxbx、ay | xbx、ayx | bx、ayxb | x 其中第1、3、4种切法符合：x和y的个数，至少在左右两块中的一块里有相同的数量 所以返回3 给定一个字符串str，长度为N 你有N-1种划分方法，把str切成左右两半，返回有几种切法满足： x和y的个数，至少在左右两块中的一块里有相同的数量 来自微软 给定一个正数num，要返回一个大于num的数， 并且每一位和相邻位的数字不能相等 返回达标的数字中，最小的那个 给你一个整数数组 arr 请你将该数组分隔为长度最多为 k 的一些（连续）子数组 分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。 返回将数组分隔变换后能够得到的元素最大和 注意： 原数组和分隔后的数组对应顺序应当一致， 也就是说，你只能选择分隔数组的位置而不能调整数组中的顺序。 leetcode链接 : https://leetcode.com/problems/partition-array-for-maximum-sum/ 来自学员贡献 返回一个数组中，所有降序三元组的数量 比如 : {5, 3, 4, 2, 1} 所有降序三元组为 :  {5, 3, 2}、{5, 3, 1}、{5, 4, 2}、{5, 4, 1}、{5, 2, 1}、{3, 2, 1}、{4, 2, 1} 所以返回数量7 给你一个下标从 0 开始的字符串数组 words 。每个字符串都只包含 小写英文字母  words 中任意一个子串中，每个字母都至多只出现一次。 如果通过以下操作之一，我们可以从 s1 的字母集合得到 s2 的字母集合，那么我们称这两个字符串为 关联的 ： 往 s1 的字母集合中添加一个字母。从 s1 的字母集合中删去一个字母 将 s1 中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。 数组 words 可以分为一个或者多个无交集的 组 。如果一个字符串与另一个字符串关联，那么它们应当属于同一个组 你需要确保分好组后，一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下，分组方案是唯一的 请你返回一个长度为 2 的数组 ans ： ans[0] 是 words 分组后的 总组数 。 ans[1] 是字符串数目最多的组所包含的字符串数目。 leetcode链接 : https://leetcode.com/problems/groups-of-strings/ 第014节 2022年3月第1周流行算法题目解析 强连通分量的原理 1，理解什么是dfn序号 2，理解什么是low序号 3，理解算法流程中，节点的三种状态：未遍历、遍历了未结算、遍历了已结算 4，理解什么是scc序号 tarjan(cur)算法求强连通分量流程： 1，遍历到一个“未遍历”状态的节点cur 2，给cur节点dfn编号和low编号，初始时low(cur) = dfn(cur) 3，将cur标记为“遍历了未结算”状态，并放入栈中 4，对于cur的每个孩子q，做如下两步操作： 1）如果q未遍历，执行tarjen(u)；否则，不执行tarjan(u) 2）步骤1)后，q就遍历过了，如果是“遍历未结算”，令low(cur) = min ( low(cur), low(q))； 如果是“已结算”，什么也不做 5，如果经历完步骤4，依然发现low(cur) = dfn(cur)， 说明cur是一个强连通分量的头节点，分配给cur一个scc号， 并去结算cur及其cur之下的点(利用栈) 强连通分量代码解析 N个学校之间有单向的网络，每个学校得到一套软件后， 可以通过单向网络向周边的学校传输 问题1： 初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件 问题2： 至少需要添加几条传输线路(边)，使任意向一个学校发放软件后， 经过若干次传送，网络内所有的学校最终都能得到软件 2 <= N <= 1000 A -> B，表示A认为B是红人 A -> B -> C，表示A认为B是红人，B认为C是红人， 规定“认为”关系有传递性，所以A也认为C是红人 给定一张有向图，方式是给定M个有序对(A, B) (A, B)表示A认为B是红人，该关系具有传递性 给定的有序对中可能包含(A, B)和(B, C)，但不包含(A,C) 求被其他所有人认为是红人的总数 在一个地图上有若干个炸弹，每个炸弹会呈现十字型引爆 每个炸弹都有其当量值，这个值决定了这个炸弹的爆炸半径 如果一个炸弹被引爆时，有其它炸弹在其爆炸半径内， 那么其它炸弹也会爆炸 请问使地图上所有炸弹爆炸所需的最少人为引爆次数。 第015节 2022年3月第2周流行算法题目解析 来自字节飞书团队 在字节跳动，大家都使用飞书的日历功能进行会议室的预订，遇到会议高峰时期， 会议室就可能不够用，现在请你实现一个算法，判断预订会议时是否有空的会议室可用。 为简化问题，这里忽略会议室的大小，认为所有的会议室都是等价的， 只要空闲就可以容纳任意的会议，并且： 1. 所有的会议预订都是当日预订当日的时段 2. 会议时段是一个左闭右开的时间区间，精确到分钟 3. 每个会议室刚开始都是空闲状态，同一时间一个会议室只能进行一场会议 4. 会议一旦预订成功就会按时进行 比如上午11点到中午12点的会议即[660, 720) 给定一个会议室总数m 一个预定事件由[a,b,c]代表 : a代表预定动作的发生时间，早来早得; b代表会议的召开时间; c代表会议的结束时间 给定一个n*3的二维数组，即可表示所有预定事件 返回一个长度为n的boolean类型的数组，表示每一个预定时间是否成功 来自字节飞书团队 小歪每次会给你两个字符串： 笔记s1和关键词s2，请你写一个函数 判断s2的排列之一是否是s1的子串 如果是，返回true 否则，返回false 来自字节飞书团队 语法补全功能，比如"as soon as possible" 当我们识别到"as soon as"时, 基本即可判定用户需要键入"possible" 设计一个统计词频的模型，用于这个功能 类似(prefix, next word)这样的二元组 比如一个上面的句子"as soon as possible" 有产生如下的二元组(as, soon, 1)、(as soon, as, 1)、(as soon as, possible, 1) 意思是这一个句子产生了如下的统计： 当前缀为"as"，接下来的单词是"soon"，有了1个期望点 当前缀为"as soon"，接下来的单词是"as"，有了1个期望点 当前缀为"as soon as"，接下来的单词是"possible"，有了1个期望点 那么如果给你很多的句子，当然就可以产生很多的期望点，同一个前缀下，同一个next word的期望点可以累加 现在给你n个句子，让你来建立统计 然后给你m个句子，作为查询 最后给你k，表示每个句子作为前缀的情况下，词频排在前k名的联想 返回m个结果，每个结果最多k个单词 来自字节飞书团队 假设数组a和数组b为两组信号 1) length(b) <= length(a) 2) 对于任意0<=i 1 返回你最多能挑选几个数 来自美团 有一块10000 * 10000 * 10000的立方体豆腐 豆腐的前左下角放在(0,0,0)点，豆腐的后右上角放在(10000,10000,10000)点 下面给出切法的数据结构 [a,b] a = 1，表示x = b处，一把无穷大的刀平行于yz面贯穿豆腐切过去 a = 2，表示y = b处，一把无穷大的刀平行于xz面贯穿豆腐切过去 a = 3，表示z = b处，一把无穷大的刀平行于xy面贯穿豆腐切过去 a = 1 or 2 or 3，0<=b<=10000 给定一个n*2的二维数组，表示切了n刀 返回豆腐中最大的一块体积是多少 来自美团 最大子段和是 一个经典问题，即对于一个数组找出其和最大的子数组。 现在允许你在求解该问题之前翻转这个数組的连续一段 如翻转(1,2,3,4,5,6)的第三个到第五个元素組成的子数组得到的是(1,2,5,4,3,6)， 则翻转后该数组的最大子段和最大能达到多少？ 来自字节 和上一题一样的题，来自字节笔试第4题 给定两个数組values和numbers， values[i]表示i号宝石的单品价值 numbers[i]表示i号宝石的数量 i号宝石的总价值 = values[i] * numbers[i] 如果有一种魔法，可以翻转任何区间L...R的宝石，也就是改变L..R的宝石排列，变成逆序的 求在允许用一次魔法的情况下，任取一段连续区间，能达到的最大价值 这两个问法解法都几乎一样，区别无非是: 上一题美团的问题: 可进行一次翻转情况下，子数组最大累加和 这一题字节的问题: 可进行一次翻转情况下，子数组最大价值和 来自美团 void add(int L, int R, int C)代表在arr[L...R]上每个数加C int get(int L, int R)代表查询arr[L...R]上的累加和 假设你可以在所有操作开始之前，重新排列arr 请返回每一次get查询的结果都加在一起最大能是多少 输入参数: int[] arr : 原始数组 int[][] ops，二维数组每一行解释如下: [a,b,c]，如果数组有3个数，表示调用add(a,b,c) [a,b]，如果数组有2个数，表示调用get(a,b) a和b表示arr范围，范围假设从1开始，不从0开始 输出：假设你可以在开始时重新排列arr，返回所有get操作返回值累计和最大是多少？ 来自bilibili 现在有N条鱼，每条鱼的体积为Ai，从左到右排列，数组arr给出 每一轮，左边的大鱼一定会吃掉右边比自己小的第一条鱼， 并且每条鱼吃比自己小的鱼的事件是同时发生的。 返回多少轮之后，鱼的数量会稳定 注意：6 6 3 3 第一轮过后 : 对于两个6来说，右边比自己小的第一条鱼都是第1个3，所以只有这个3被吃掉， 数组变成 : 6 6 3（第2个3） 第二轮过后 : 6 6 返回2 来自银联编程比赛 某公司计划推出一批投资项目。 product[i] = price 表示第 i 个理财项目的投资金额 price 。 客户在按需投资时，需要遵循以下规则： 客户在首次对项目 product[i] 投资时，需要投入金额 price 对已完成首次投资的项目 product[i] 可继续追加投入， 但追加投入的金额需小于上一次对该项目的投入(追加投入为大于 0 的整数) 为控制市场稳定，每人交易次数不得大于 limit。(首次投资和追加投入均记作 1 次交易) 若对所有理财项目中最多进行 limit 次交易，使得投入金额总和最大，请返回这个最大值的总和。 测试链接 : https://leetcode-cn.com/contest/cnunionpay-2022spring/problems/I4mOGz/ 来自银联编程比赛 为了不断提高用户使用的体验，开发团队正在对产品进行全方位的开发和优化。 已知开发团队共有若干名成员，skills[i] 表示第 i 名开发人员掌握技能列表。 如果两名成员各自拥有至少一门对方未拥有的技能，则这两名成员可以「合作开发」。 请返回当前有多少对开发成员满足「合作开发」的条件。 由于答案可能很大，请你返回答案对 10^9 + 7 取余的结果。 测试链接 : https://leetcode-cn.com/contest/cnunionpay-2022spring/problems/lCh58I/ 第017节 2022年3月第4周流行算法题目解析 来自学员的考试 来自华为 给定一个n*2的二维数组，表示有n个任务 一个信息是任务能够开始做的时间，另一个信息是任务的结束期限，后者一定大于前者，且数值上都是正数 你作为单线程的人，不能并行处理任务，但是每个任务都只需要一个单位时间完成 你需要将所有任务的执行时间，位于开始做的时间和最后期限之间 返回你能否做到这一点 来自字节内部训练营 某公司游戏平台的夏季特惠开始了，你决定入手一些游戏。现在你一共有X元的预算。 该平台上所有的 n 个游戏均有折扣，标号为 i 的游戏的原价a_i元，现价只要b_i元 也就是说该游戏可以优惠 a_i - b_i，并且你购买该游戏能获得快乐值为 w_i 由于优惠的存在，你可能做出一些冲动消费导致最终买游戏的总费用超过预算， 只要满足 : 获得的总优惠金额不低于超过预算的总金额 那在心理上就不会觉得吃亏。 现在你希望在心理上不觉得吃亏的前提下，获得尽可能多的快乐值。 测试链接 : https://leetcode-cn.com/problems/tJau2o/ 来自学员问题 给定一个数组arr，可能有正、有负、有0，无序 只能挑选两个数字，想尽量让两个数字加起来的绝对值尽量小 返回可能的最小的值 来自字节 一开始在0位置，每一次都可以向左或者向右跳 第i次能向左或者向右跳严格的i步 请问从0到x位置，至少跳几次可以到达 字节考的问题其实就是这个问题 leetcode测试链接 : https://leetcode.com/problems/reach-a-number/ 来自理想汽车 a -> b，代表a在食物链中被b捕食 给定一个有向无环图，返回 这个图中从最初级动物到最顶级捕食者的食物链有几条 线上测试链接 : https://www.luogu.com.cn/problem/P4017 来自学员问题 给定一个数字n，表示一开始有编号1~n的树木，列成一条直线 给定一个有序数组arr，表示现在哪些树已经没了，arr[i]一定在[1,n]范围 给定一个数字m，表示你可以补种多少棵树 返回补种之后，最长的连续树木，有多少棵 来自网易 不规则数独问题 3*3填数独 每一行要填1~3 每一列要填1~3 3*3的区域会拆分成不规则的三个集团区域 每个集团区域3个格子 每个集团的区域都一定是一个连在一起的整体，可能不规则 每个集团内要填1~3 如果只有一个解返回"Unique"，如果有多个解返回"Multiple"，如果没有解返回"No" 解析请看，大厂刷题班，28节，leetcode原题，数独那两个题 本题就是改变一下桶的归属而已 来自学员问题 大妈一开始手上有x个鸡蛋，她想让手上的鸡蛋数量变成y 操作1 : 从仓库里拿出1个鸡蛋到手上，x变成x+1个 操作2 : 如果手上的鸡蛋数量是3的整数倍，大妈可以直接把三分之二的鸡蛋放回仓库，手里留下三分之一 返回从x到y的最小操作次数 1 <= x,y <= 10^18 练一下，用平凡解做限制 第018节 2022年3月第5周流行算法题目解析 km算法流程详解、代码实现 来自微软 在N*N的正方形棋盘中，有N*N个棋子，那么每个格子正好可以拥有一个棋子 但是现在有些棋子聚集到一个格子上了，比如： 2 0 3 0 1 0 3 0 0 如上的二维数组代表，一共3*3个格子 但是有些格子有2个棋子、有些有3个、有些有1个、有些没有 请你用棋子移动的方式，让每个格子都有一个棋子 每个棋子可以上、下、左、右移动，每移动一步算1的代价 返回最小的代价 给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ，满足2 * numSlots >= n 总共有 numSlots 个篮子，编号为 1 到 numSlots 你需要把所有 n 个整数分到这些篮子中，且每个篮子 至多 有 2 个整数 一种分配方案的 与和 定义为每个数与它所在篮子编号的 按位与运算 结果之和。 比方说，将数字 [1, 3] 放入篮子 1 中，[4, 6] 放入篮子 2 中， 这个方案的与和为 (1 AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4 。 请你返回将 nums 中所有数放入 numSlots 个篮子中的最大与和。 Leetcode链接：https://leetcode.com/problems/maximum-and-sum-of-array 来自网易 我军一起干掉敌人的最少移动数 km算法的又一个题 给定一个矩阵int[][] matrix matrix[i][j] == -2，代表此处(i,j)有山脉，无法通行 matrix[i][j] == -1，代表此处(i,j)是一个敌军 matrix[i][j] == 0，代表此处(i,j)是空地，可以自由行动 matrix[i][j] > 0，代表此处(i,j)是一个我军，行动能力就是matrix[i][j] 我军只能上、下、左、右移动，只可以穿过同样是我军的地点和空地的地点，但是最多移动matrix[i][j]步 任何一个我军都不能穿过山脉，任何一个我军可以来到敌军的位置，表示消灭了敌军，但是如果这么做了，这个我军就不能再移动了 你可以任意决定所有我军的行动策略，每一步你都可以随意选择一个友军移动随意方向的，但是必须合法。 如果你可以让所有我军在消耗完自身的行动能力之前，消灭所有的敌军，请返回总距离的最小值 如果你就是无法消灭所有敌军，返回-1 第019节 2022年4月第1周流行算法题目解析 来自阿里笔试 牛牛今年上幼儿园了，老师叫他学习减法 老师给了他5个数字，他每次操作可以选择其中的4个数字减1 减一之后的数字不能小于0，因为幼儿园的牛牛还没有接触过负数 现在牛牛想知道，自己最多可以进行多少次这样的操作 扩展问题来自leetcode 2141，掌握了这个题原始问题就非常简单了 leetcode测试链接 : https://leetcode.com/problems/maximum-running-time-of-n-computers/ 来自学员问题 找到非负数组中拥有"最大或的结果"的最短子数组 来自通维数码 每个会议给定开始和结束时间 后面的会议如果跟前面的会议有任何冲突，完全取消冲突的、之前的会议，安排当前的 给定一个会议数组，返回安排的会议列表 来自小红书 小红书第一题： 薯队长从北向南穿过一片红薯地（南北长M，东西宽N），红薯地被划分为1x1的方格， 他可以从北边的任何一个格子出发，到达南边的任何一个格子， 但每一步只能走到东南、正南、西南方向的三个格子之一， 而且不能跨出红薯地，他可以获得经过的格子上的所有红薯，请问他可以获得最多的红薯个数。 来自小红书 小红书第二题： 薯队长最近在参加了一个活动，主办方提供了N个礼物以供挑选， 每个礼物有一个价值，范围在0 ~ 10^9之间， 薯队长可以从中挑选k个礼物 返回：其中价值最接近的两件礼物之间相差值尽可能大的结果 来自小红书 小红书第三题： 薯队长最近在玩一个游戏，这个游戏桌上会有一排不同颜色的方块， 每次薯队长可以选择一个方块，便可以消除这个方块以及和他左右相临的 若干的颜色相同的方块，而每次消除的方块越多，得分越高。 具体来说，桌上有以个方块排成一排 (1 <= N <= 200）， 每个方块有一个颜色，用1~N之间的一个整数表示，相同的数宇代表相同的颜色， 每次消除的时候，会把连续的K个相同颜色的方块消除，并得到K*K的分数， 直到所有方块都消除。显然，不同的消除顺序得分不同，薯队长希望您能告诉他，这个游戏最多能得到多少分 体系学习班，代码46节，视频在47节，消箱子原题，RemoveBoxes 给定一个数组arr，含有n个数字，都是非负数 给定一个正数k 返回所有子序列中，累加和最小的前k个子序列累加和 假设K不大，怎么算最快？ 来自Amazon 给定一个数组arr，含有n个数字，可能有正、有负、有0 给定一个正数k 返回所有子序列中，累加和最大的前k个子序列累加和 假设K不大，怎么算最快？ 第020节 2022年4月第2周流行算法题目解析 来自携程 给出n个数字，你可以任选其中一些数字相乘，相乘之后得到的新数字x x的价值是x的不同质因子的数量 返回所有选择数字的方案中，得到的x的价值之和 来自网易 3.27笔试 一个二维矩阵，上面只有 0 和 1，只能上下左右移动 如果移动前后的元素值相同，则耗费 1 ，否则耗费 2。 问从左上到右下的最小耗费 来自美团 3.26笔试 给定一个非负数组，任意选择数字，使累加和最大且为7的倍数，返回最大累加和 n比较大，10的5次方 来自美团 3.26笔试 给定一个正数n, 表示有0~n-1号任务 给定一个长度为n的数组time，time[i]表示i号任务做完的时间 给定一个二维数组matrix matrix[j] = {a, b} 代表：a任务想要开始，依赖b任务的完成 只要能并行的任务都可以并行，但是任何任务只有依赖的任务完成，才能开始 返回一个长度为n的数组ans，表示每个任务完成的时间 输入可以保证没有循环依赖 来自百度 给出一个长度为n的01串，现在请你找到两个区间， 使得这两个区间中，1的个数相等，0的个数也相等 这两个区间可以相交，但是不可以完全重叠，即两个区间的左右端点不可以完全一样 现在请你找到两个最长的区间，满足以上要求。 来自阿里 x = { a, b, c, d } y = { e, f, g, h } x、y两个小数组长度都是4 如果有: a + e = b + f = c + g = d + h 那么说x和y是一个完美对 题目给定N个小数组，每个小数组长度都是K 返回这N个小数组中，有多少完美对 来自快手 某公司年会上，大家要玩一食发奖金游戏，一共有n个员工， 每个员工都有建设积分和捣乱积分 他们需要排成一队，在队伍最前面的一定是老板，老板也有建设积分和捣乱积分 排好队后，所有员工都会获得各自的奖金， 该员工奖金 = 排在他前面所有人的建设积分乘积 / 该员工自己的捣乱积分，向下取整 为了公平(放屁)，老板希望 : 让获得奖金最高的员工，所获得的奖金尽可能少 所以想请你帮他重新排一下队伍，返回奖金最高的员工获得的、尽可能少的奖金数额 1 <= n <= 1000, 1<= 积分 <= 10000; 第021节 2022年4月第3周流行算法题目解析 来自小红书 3.13 笔试 数组里有0和1，一定要翻转一个区间，翻转：0变1，1变0 请问翻转后可以使得1的个数最多是多少？ 来自小红书 3.13 笔试 给定一个数组，想随时查询任何范围上的最大值 如果只是根据初始数组建立、并且以后没有修改， 那么RMQ方法比线段树方法好实现，时间复杂度O(N*logN)，额外空间复杂度O(N*logN) 来自腾讯音乐 原本数组中都是大于0、小于等于k的数字，是一个单调不减的数组 其中可能有相等的数字，总体趋势是递增的 但是其中有些位置的数被替换成了0，我们需要求出所有的把0替换的方案数量： 1) 填充的每一个数可以大于等于前一个数，小于等于后一个数 2) 填充的每一个数不能大于k 来自学员问题 总长度为n的数组中，所有长度为k的子序列里，有多少子序列的和为偶数 来自微众 4.11笔试 给定n位长的数字字符串和正数k，求该子符串能被k整除的子串个数 (n<=1000，k<=100) 第022节 2022年5月第1周流行算法题目解析 来自蔚来汽车 给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。 每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ： i + 1 需满足：i + 1 < arr.length i - 1 需满足：i - 1 >= 0 j 需满足：arr[i] == arr[j] 且 i != j 请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。 注意：任何时候你都不能跳到数组外面。 leetcode测试链接 : https://leetcode-cn.com/problems/jump-game-iv/ 来自微众 人工智能岗 一开始有21个球，甲和乙轮流拿球，甲先、乙后 每个人在自己的回合，一定要拿不超过3个球，不能不拿 最终谁的总球数为偶数，谁赢 请问谁有必胜策略 来自学员问题，真实大厂面试题 1、2、3...n-1、n、n、n+1、n+2... 在这个序列中，只有一个数字有重复(n) 这个序列是无序的，找到重复数字n 这个序列是有序的，找到重复数字n 来自学员问题，蓝桥杯练习题 f(i) : i的所有因子，每个因子都平方之后，累加起来 比如f(10) = 1平方 + 2平方 + 5平方 + 10平方 = 1 + 4 + 25 + 100 = 130 给定一个数n，求f(1) + f(2) + .. + f(n) n <= 10的9次方 来自optiver 给定一个字符串str，和一个正数k 你可以随意的划分str成多个子串， 目的是找到在某一种划分方案中，有尽可能多的回文子串，长度>=k，并且没有重合 返回有几个回文子串 第023节 2022年5月第2周流行算法题目解析 来自字节 5.6笔试 给定N件物品，每个物品有重量(w[i])、有价值(v[i]) 只能最多选两件商品，重量不超过bag，返回价值最大能是多少？ N <= 10^5, w[i] <= 10^5, v[i] <= 10^5, bag <= 10^5 本题的关键点：什么数据范围都很大，唯独只需要最多选两件商品，这个可以利用一下 来自网易 小红拿到了一个长度为N的数组arr，她准备只进行一次修改 可以将数组中任意一个数arr[i]，修改为不大于P的正数（修改后的数必须和原数不同) 并使得所有数之和为X的倍数 小红想知道，一共有多少种不同的修改方案 1 <= N, X <= 10^5, 1 <= arr[i], P <= 10^9 来自字节 一共有n个人，从左到右排列，依次编号0~n-1 h[i]是第i个人的身高 v[i]是第i个人的分数 要求从左到右选出一个子序列，在这个子序列中的人，从左到右身高是不下降的 返回所有符合要求的子序列中，分数最大累加和是多大 n <= 10的5次方, 1 <= h[i] <= 10的9次方, 1 <= v[i] <= 10的9次方 来自网易 给出一个有n个点，m条有向边的图 你可以施展魔法，把有向边，变成无向边 比如A到B的有向边，权重为7。施展魔法之后，A和B通过该边到达彼此的代价都是7。 求，允许施展一次魔法的情况下，1到n的最短路，如果不能到达，输出-1。 n为点数, 每条边用(a,b,v)表示，含义是a到b的这条边，权值为v 点的数量 <= 10^5，边的数量 <= 2 * 10^5，1 <= 边的权值 <= 10^6 来自网易 小红拿到了一个大立方体，该大立方体由1*1*1的小方块拼成，初始每个小方块都是白色。 小红可以每次选择一个小方块染成红色 每次小红可能选择同一个小方块重复染色 每次染色以后，你需要帮小红回答出当前的白色连通块数 如果两个小方块共用同一个面，且颜色相同，则它们是连通的 给定n、m、h，表示大立方体的长、宽、高 给定k次操作，每一次操作用(a, b, c)表示在大立方体的该位置进行染色 返回长度为k的数组，表示每一次操作后，白色方块的连通块数 n * m * h <= 10 ^ 5，k <= 10 ^ 5 第024节 2022年5月第3周流行算法题目解析 来自字节 输入: 去重数组arr，里面的数只包含0~9 limit，一个数字 返回: 要求比limit小的情况下，能够用arr拼出来的最大数字 来自京东 4.2笔试 给定一个数组arr，长度为N，arr中所有的值都在1~K范围上 你可以删除数字，目的是让arr的最长递增子序列长度小于K 返回至少删除几个数字能达到目的 N <= 10^4，K <= 10^2 来自学员问题 给定一个数组arr，表示从早到晚，依次会出现的导弹的高度 大炮打导弹的时候，如果一旦大炮定了某个高度去打，那么这个大炮每次打的高度都必须下降一点 1) 如果只有一个大炮，返回最多能拦截多少导弹 2) 如果所有的导弹都必须拦截，返回最少的大炮数量 来自学员问题 为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机 游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1 初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处 通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置 也就是说，在编号为 i 弹簧处按动弹簧， 小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器） 小球位于编号 0 处的弹簧时不能再向左弹。 为了获得奖励，你需要将小球弹出机器。 请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。 测试链接 : https://leetcode-cn.com/problems/zui-xiao-tiao-yue-ci-shu/ 第025节 2022年5月第4周流行算法题目解析 每一个方案都有两个值(a,b)，a为娱乐值，b为进攻值 给定很多的方案数组，给定娱乐值总目标(int)，给定进攻值总目标(int) 要求选一些方案，这些方案的总娱乐值>=娱乐值总目标，总进攻值>=进攻值总目标 返回至少需要选几个方案 给定绳子总长度为M，每一个长度的绳子对应一个价格，比如(6, 10)表示剪成长度为6的绳子，对应价格10 可以重复切出某个长度的绳子，返回总长度为M的情况下，能得到的最大价值 每一个序列都是[a,b]的形式，a < b 序列连接的方式为，前一个序列的b，要等于后一个序列的a 比如 : [3, 7]、[7, 13]、[13, 26]这三个序列就可以依次连接 给定若干个序列，求最大连接的数量 给定区间的范围[xi,yi]，xi<=yi，且都是正整数 找出一个坐标集合set，set中有若干个数字 set要和每个给定的区间，有交集 求set的最少需要几个数 比如给定区间 : [5, 8] [1, 7] [2, 4] [1, 9] set最小可以是: {2, 6}或者{2, 5}或者{4, 5} 来自字节 5.6笔试 给定一个数组arr，长度为n，最多可以删除一个连续子数组， 求剩下的数组，严格连续递增的子数组最大长度 n <= 10^6 来自京东 4.2笔试 给定一个长度为3N的数组，其中最多含有0、1、2三种值 你可以把任何一个连续区间上的数组，全变成0、1、2中的一种 目的是让0、1、2三种数字的个数都是N 返回最小的变化次数 第026节 2022年6月第1周流行算法题目解析 最好打开链接看图 用一个大小为 m x n 的二维网格 grid 表示一个箱子 你有 n 颗球。箱子的顶部和底部都是开着的。 箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角， 可以将球导向左侧或者右侧。 将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。 将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。 在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。 如果球恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。 返回一个大小为 n 的数组 answer ， 其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标， 如果球卡在盒子里，则返回 -1 本题测试链接 : https://leetcode.com/problems/where-will-the-ball-fall/ 把字符串 s 看作 "abcdefghijklmnopqrstuvwxyz" 的无限环绕字符串， 所以 s 看起来是这样的： ...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd.... 现在给定另一个字符串 p 。返回 s 中 不同 的 p 的 非空子串 的数量 测试链接 : https://leetcode.com/problems/unique-substrings-in-wraparound-string/ 给你一个字符串化学式 formula ，返回 每种原子的数量 。 原子总是以一个大写字母开始，接着跟随 0 个或任意个小写字母，表示原子的名字。 如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。 例如，"H2O" 和 "H2O2" 是可行的，但 "H1O2" 这个表达是不可行的。 两个化学式连在一起可以构成新的化学式。 例如 "H2O2He3Mg4" 也是化学式。 由括号括起的化学式并佐以数字（可选择性添加）也是化学式。 例如 "(H2O2)" 和 "(H2O2)3" 是化学式。 返回所有原子的数量，格式为：第一个（按字典序）原子的名字，跟着它的数量（如果数量大于 1）， 然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。 示例 1： 输入：formula = "H2O" 输出："H2O" 解释：原子的数量是 {'H': 2, 'O': 1}。 示例 2： 输入：formula = "Mg(OH)2" 输出："H2MgO2" 解释：原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。 示例 3： 输入：formula = "K4(ON(SO3)2)2" 输出："K4N2O14S4" 解释：原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。 测试链接 : https://leetcode.com/problems/number-of-atoms/ 字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。 给你一个字符串 s ，它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。 子字符串 是一个字符串的一段连续字符序列。 注意：必须同时有，最多字符和最少字符的字符串才是有效的 测试链接 : https://leetcode.cn/problems/substring-with-largest-variance/ 第027节 2022年6月第2周流行算法题目解析 n块石头放置在二维平面中的一些整数坐标点上 每个坐标点上最多只能有一块石头 如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。 给你一个长度为 n 的数组 stones ， 其中 stones[i] = [xi, yi] 表示第 i 块石头的位置， 返回 可以移除的石子 的最大数量。 测试链接 : https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/ 作为国王的统治者，你有一支巫师军队听你指挥。 给你一个下标从 0 开始的整数数组 strength ， 其中 strength[i] 表示第 i 位巫师的力量值。 对于连续的一组巫师（也就是这些巫师的力量值是 strength 的 子数组）， 总力量 定义为以下两个值的 乘积 ： 巫师中 最弱 的能力值 * 组中所有巫师的个人力量值 之和 。 请你返回 所有 巫师组的 总 力量之和。由于答案可能很大，请将答案对 109 + 7 取余 后返回。 子数组 是一个数组里 非空 连续子序列。 测试链接 : https://leetcode.cn/problems/sum-of-total-strength-of-wizards/ 给你一个由正整数组成的数组 nums 。 数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。 例如，序列 [4,6,16] 的最大公约数是 2 。 数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。 例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。 计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。 测试链接 : https://leetcode.com/problems/number-of-different-subsequences-gcds/ 给定一个正整数 n，返回 连续正整数满足所有数字之和为 n 的组数 。  示例 1: 输入: n = 5 输出: 2 解释: 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。 示例 2: 输入: n = 9 输出: 3 解释: 9 = 4 + 5 = 2 + 3 + 4 示例 3: 输入: n = 15 输出: 4 解释: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5 测试链接 : https://leetcode.com/problems/consecutive-numbers-sum/ 第028节 2022年6月第3周流行算法题目解析 arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”， 并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。 我们最多能将数组分成多少块？ 示例 1: 输入: arr = [5,4,3,2,1] 输出: 1 解释: 将数组分成2块或者更多块，都无法得到所需的结果。 例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。 示例 2: 输入: arr = [2,1,3,4,4] 输出: 4 解释: 我们可以把它分成两块，例如 [2, 1], [3, 4, 4]。 然而分成 [2, 1], [3], [4], [4] 可以得到最多的块数。 测试链接 : https://leetcode.com/problems/max-chunks-to-make-sorted-ii/ 给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。 同时给你一个二维整数数组 prices ，其中 prices[i] = [hi, wi, pricei]  表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。 每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块： 沿垂直方向按高度 完全 切割木块，或 沿水平方向按宽度 完全 切割木块 在将一块木块切成若干小木块后，你可以根据 prices 卖木块。 你可以卖多块同样尺寸的木块。 你不需要将所有小木块都卖出去。 你 不能 旋转切好后木块的高和宽。 请你返回切割一块大小为 m x n 的木块后，能得到的 最多 钱数。 注意你可以切割木块任意次。 测试链接 : https://leetcode.cn/problems/selling-pieces-of-wood/ Range模块是跟踪数字范围的模块。 设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。 半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。 实现 RangeModule 类: RangeModule() 初始化数据结构的对象 void addRange(int left, int right) : 添加 半开区间 [left, right)，跟踪该区间中的每个实数。 添加与当前跟踪的数字部分重叠的区间时， 应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。 boolean queryRange(int left, int right) : 只有在当前正在跟踪区间 [left, right) 中的每一个实数时，才返回 true 否则返回 false 。 void removeRange(int left, int right) : 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。 测试连接 : https://leetcode.com/problems/range-module/ 一个字符串s，表示仓库的墙 与 货物，其中'|'表示墙,'*'表示货物。 给定一个起始下标start和一个终止下标end， 找出子串中 被墙包裹的货物 数量 比如 s = "|**|**|*" start = 1, end = 7 start和end截出的子串是 "**|**|*" 被 '|'包裹的 '*' 有两个，所以返回2 现在给定一系列的start，startIndices[]，和对应一系列的end ,endIndices[] 返回每一对[start,end]的截出来的货物数量 数据规模： 字符串s长度<=10^5 startIndices长度 == endIndices长度 <=10^5 第029节 2022年6月第4周流行算法题目解析 给定字符串 S and T，找出 S 中最短的（连续）子串 W ，使得 T 是 W 的 子序列 。 如果 S 中没有窗口可以包含 T 中的所有字符，返回空字符串 ""。 如果有不止一个最短长度的窗口，返回开始位置最靠左的那个。 示例 1： 输入： S = "abcdebdde", T = "bde" 输出："bcde" 解释： "bcde" 是答案，因为它在相同长度的字符串 "bdde" 出现之前。 "deb" 不是一个更短的答案，因为在窗口中必须按顺序出现 T 中的元素。 测试链接 : https://leetcode.cn/problems/minimum-window-subsequence/ 来自微软 请设计一种叫做“栈的管理器”的结构，实现如下6个功能 1) void createNewStack() : 可以在该结构中生成一个栈结构，编号从0开始 2) void push(int num, int stackIndex) : 将编号为stackIndex的栈里，压入num 3) int pop(int stackIndex) : 从编号为stackIndex的栈里，弹出栈顶返回 4) int peek(int stackIndex) ：从编号为stackIndex的栈里，返回栈顶但是不弹出 5) boolean isEmpty(int statckIndex)：返回编号为stackIndex的栈是否为空 6) int stackSize() : 返回一共生成了多少个栈 要求：不管用户调用多少次上面的方法，只使用有限几个动态数组(常数个)，完成代码实现 有n个动物重量分别是a1、a2、a3.....an， 这群动物一起玩叠罗汉游戏， 规定从左往右选择动物，每只动物左边动物的总重量不能超过自己的重量 返回最多能选多少个动物，求一个高效的算法。 比如有7个动物，从左往右重量依次为：1，3，5，7，9，11，21 则最多能选5个动物：1，3，5，9，21 注意本题给的例子是有序的，但是实际给定的动物数组，可能是无序的， 要求从左往右选动物，且不能打乱原始数组 整数数组 stations 表示 水平数轴 上各个加油站的位置。给你一个整数 k 。 请你在数轴上增设 k 个加油站， 新增加油站可以位于 水平数轴 上的任意位置，而不必放在整数位置上。 设 penalty() 是：增设 k 个新加油站后，相邻 两个加油站间的最大距离。 请你返回 penalty() 可能的最小值。与实际答案误差在 10-6 范围内的答案将被视作正确答案。 测试链接 : https://leetcode.cn/problems/minimize-max-distance-to-gas-station/ 第030节 2022年7月第1周流行算法题目解析 来自真实笔试 给定一个二维数组matrix，数组中的每个元素代表一棵树的高度。 你可以选定连续的若干行组成防风带，防风带每一列的防风高度为这一列的最大值 防风带整体的防风高度为，所有列防风高度的最小值。 比如，假设选定如下三行 1 5 4 7 2 6 2 3 4 1、7、2的列，防风高度为7 5、2、3的列，防风高度为5 4、6、4的列，防风高度为6 防风带整体的防风高度为5，是7、5、6中的最小值 给定一个正数k，k <= matrix的行数，表示可以取连续的k行，这k行一起防风。 求防风带整体的防风高度最大值 给定一个棵树 树上每个节点都有自己的值，记录在数组nums里 比如nums[4] = 10，表示4号点的值是10 给定树上的每一条边，记录在二维数组edges里 比如edges[8] = {4, 9}表示4和9之间有一条无向边 可以保证输入一定是一棵树，只不过边是无向边 那么我们知道，断掉任意两条边，都可以把整棵树分成3个部分。 假设是三个部分为a、b、c a部分的值是：a部分所有点的值异或起来 b部分的值是：b部分所有点的值异或起来 c部分的值是：c部分所有点的值异或起来 请问怎么分割，能让最终的：三个部分中最大的异或值 - 三个部分中最小的异或值，最小 返回这个最小的差值 测试链接 : https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/ 在第 1 天，有一个人发现了一个秘密。 给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后， 每天 给一个新的人 分享 秘密。 同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。 一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。 给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。 由于答案可能会很大，请你将结果对 10^9 + 7 取余 后返回。 测试链接 : https://leetcode.cn/problems/number-of-people-aware-of-a-secret/ 第031节 2022年7月第2周流行算法题目解析 给定一个字符串 s，计算 s 的 不同非空子序列 的个数 因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。 字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符 但不改变剩余字符相对位置的一个新字符串。 本题来自大厂刷题班17节 但是为了讲述一个最新题目，不得不重提这个题 本题测试链接 : https://leetcode.com/problems/distinct-subsequences-ii/ 来自SnowFlake 给定一个正数n，比如6 表示数轴上有 0,1,2,3,4,5,6 <0 或者 >6 的位置认为无法到达 给定两个数字x和y，0<= x，y <= n 表示小人一开始在x的位置，它的目的地是y的位置，比如x = 1, y = 3 给定一个字符串s，比如 : rrlrlr 任何一个s的子序列，对应着一种运动轨迹，r表示向右，l表示向左 比如一开始小人在1位置，"rlr"是s的一个子序列 那么运动轨迹是：1 -> 2 -> 1 -> 2 求，s中有多少个字面值不同的子序列，能让小人从x走到y， 走的过程中完全不走出0到n的区域。 比如，s = "rrlrlr", n = 6, x = 1, y = 3 有如下5个字面值不同的子序列 rr : 1 -> 2 -> 3 rrlr : 1 -> 2 -> 3 -> 2 -> 3 rrrl : 1 -> 2 -> 3 -> 4 -> 3 rlrr : 1 -> 2 -> 1 -> 2 -> 3 rrlrlr : 1 -> 2 -> 3 -> 2 -> 3 -> 2 -> 3 注意：一定要是字面值不同的子序列！相同字面值的子序列算一种 比如s中，有很多个rr的子序列，但是算一个 数据规模 : s串长度 <= 1000, x,y,n <= 2500 在一个 n x n 的整数矩阵 grid 中， 每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。 当开始下雨时，在时间为 t 时，水池中的水位为 t 。 你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。 假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。 当然，在你游泳的时候你必须待在坐标方格里面。 你从坐标方格的左上平台 (0，0) 出发。 返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。 测试链接 ：https://leetcode.cn/problems/swim-in-rising-water 给定员工的 schedule 列表，表示每个员工的工作时间。 每个员工都有一个非重叠的时间段  Intervals 列表，这些时间段已经排好序。 返回表示 所有 员工的 共同，正数长度的空闲时间 的有限时间段的列表，同样需要排好序。 测试链接 : https://leetcode.cn/problems/employee-free-time/ 我们给出了一个（轴对齐的）二维矩形列表 rectangles 。 对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标 (xi1, yi1) 是该矩形 左下角 的坐标， (xi2, yi2) 是该矩形 右上角 的坐标。 计算平面中所有 rectangles 所覆盖的 总面积 。 任何被两个或多个矩形覆盖的区域应只计算 一次 。 返回 总面积 。因为答案可能太大，返回 10^9 + 7 的 模 。 Leetcode测试链接 : https://leetcode.cn/problems/rectangle-area-ii/ 洛谷测试链接 : https://www.luogu.com.cn/problem/P5490 第032节 2022年7月第3周流行算法题目解析 一个整数区间 [a, b]  ( a < b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。 给你一组整数区间intervals，请找到一个最小的集合 S， 使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。 输出这个最小集合S的大小。 测试链接 : https://leetcode.cn/problems/set-intersection-size-at-least-two/ 来自蔚来汽车 给定一个只包含三种字符的字符串：( 、) 和 *， 写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则： 任何左括号 ( 必须有相应的右括号 ) 任何右括号 ) 必须有相应的左括号 ( 左括号 ( 必须在对应的右括号之前 ) * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符。 一个空字符串也被视为有效字符串。 测试链接 : https://leetcode.cn/problems/valid-parenthesis-string/ 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。 你可以按 任意顺序 返回答案。 要求时间复杂度O(N) 测试链接 : https://leetcode.cn/problems/top-k-frequent-elements/ 特殊的二进制序列是具有以下两个性质的二进制序列： 0 的数量与 1 的数量相等。 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。 给定一个特殊的二进制序列 S，以字符串形式表示。 定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。 (两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符) 在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？ 测试链接 : https://leetcode.cn/problems/special-binary-string/ 第033节 2022年7月第4周流行算法题目解析 一个数组如果满足 : 升降升降升降... 或者 降升降升...都是满足的 给定一个数组， 1，看有几种方法能够剔除一个元素，达成上述的要求 2，数组天然符合要求返回0 3，剔除1个元素达成不了要求，返回-1， 比如： 给定[3, 4, 5, 3, 7]，返回3 移除0元素，4 5 3 7 符合 移除1元素，3 5 3 7 符合 移除2元素，3 4 3 7 符合 再比如：给定[1, 2, 3, 4] 返回-1 因为达成不了要求 你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。 你要用 所有的火柴棍 拼成一个正方形。 你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。 如果你能拼出正方形，则返回 true ，否则返回 false 。 测试链接 : https://leetcode.cn/problems/matchsticks-to-square/ 给你一个整数数组 nums 。如果 nums 的一个子集中， 所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积，那么我们称它为 好子集 。 比方说，如果 nums = [1, 2, 3, 4] ： [2, 3] ，[1, 2, 3] 和 [1, 3] 是 好 子集，乘积分别为 6 = 2*3 ，6 = 2*3 和 3 = 3 。 [1, 4] 和 [4] 不是 好 子集，因为乘积分别为 4 = 2*2 和 4 = 2*2 。 请你返回 nums 中不同的 好 子集的数目对 109 + 7 取余 的结果。 nums 中的 子集 是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除） 元素后剩余元素组成的数组。 如果两个子集删除的下标不同，那么它们被视为不同的子集。 测试链接 : https://leetcode.cn/problems/the-number-of-good-subsets/ 第034节 2022年8月第1周流行算法题目解析 在一个 2 * 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换. 最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。 给出一个谜板的初始状态 board ， 返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。 测试链接 : https://leetcode.cn/problems/sliding-puzzle/ 找到数组中的水王数 本题来自，大厂刷题班，23节 为了讲述下一个题，才重新讲述这个题 比较简单 设计一个数据结构，有效地找到给定子数组的 多数元素 。 子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。 实现 MajorityChecker 类: MajorityChecker(int[] arr)  会用给定的数组 arr 对 MajorityChecker 初始化。 int query(int left, int right, int threshold)  返回子数组中的元素  arr[left...right] 至少出现 threshold 次数， 如果不存在这样的元素则返回 -1。 为了让同学们听懂这个题 才安排的水王问题重讲 测试链接 : https://leetcode.cn/problems/online-majority-element-in-subarray/ 给你一个长度为 n 的整数数组 rolls 和一个整数 k 。 你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ， 其中第 i 次扔得到的数字是 rolls[i] 。 请你返回 无法 从 rolls 中得到的 最短 骰子子序列的长度。 扔一个 k 面的骰子 len 次得到的是一个长度为 len 的 骰子子序列 。 注意 ，子序列只需要保持在原数组中的顺序，不需要连续。 测试链接 : https://leetcode.cn/problems/shortest-impossible-sequence-of-rolls/ 给定一个只由小写字母和数字字符组成的字符串str 要求子串必须只含有一个小写字母，数字字符数量随意 求这样的子串最大长度是多少 栈只提供push、pop、isEmpty三个方法 请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大 只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数 除此之外不能使用任何的容器，任何容器都不许，连数组也不行 也不能自己定义任何结构体 就是只用： 1) 栈提供的push、pop、isEmpty三个方法 2) 简单返回值的递归函数 第035节 2022年8月第2周流行算法题目解析 来自猿辅导 2022.8.7笔试第三道 给定一个数组arr，和一个正数k 如果arr[i] == 0，表示i这里既可以是左括号也可以是右括号， 而且可以涂上1~k每一种颜色 如果arr[i] != 0，表示i这里已经确定是左括号，颜色就是arr[i]的值 那么arr整体就可以变成某个括号字符串，并且每个括号字符都带有颜色 返回在括号字符串合法的前提下，有多少种不同的染色方案 不管是排列、还是颜色，括号字符串任何一点不一样，就算不同的染色方案 最后的结果%10001，为了方便，我们不处理mod，就管核心思路 2 <= arr长度 <= 5000 1 <= k <= 1000 0 <= arr[i] <= k 来自米哈游 给定一个正数n，表示有多少个节点 给定一个二维数组edges，表示所有无向边 edges[i] = {a, b} 表示a到b有一条无向边 edges一定表示的是一个无环无向图，也就是树结构 每个节点可以染1、2、3三种颜色 要求 : 非叶节点的相邻点一定要至少有两种和自己不同颜色的点 返回一种达标的染色方案，也就是一个数组，表示每个节点的染色状况 1 <= 节点数量 <= 10的5次方 给定一个逆波兰式 转化成正确的中序表达式 要求只有必要加括号的地方才加括号 给定平面上n个点，x和y坐标都是整数 找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的 返回最短距离，精确到小数点后面4位 测试链接 : https://www.luogu.com.cn/problem/P1429 第036节 2022年8月第3周流行算法题目解析 给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ， 其中每个节点 至多 有一条出边。 图用一个大小为 n 下标从 0 开始的数组 edges 表示， 节点 i 到节点 edges[i] 之间有一条有向边。 如果节点 i 没有出边，那么 edges[i] == -1 。 请你返回图中的 最长 环，如果没有任何环，请返回 -1 。 一个环指的是起点和终点是 同一个 节点的路径。 测试链接 : https://leetcode.cn/problems/longest-cycle-in-a-graph/ 来自学员问题 给定怪兽的血量为hp 第i回合如果用刀砍，怪兽在这回合会直接掉血，没有后续效果 第i回合如果用毒，怪兽在这回合不会掉血， 但是之后每回合都会掉血，并且所有中毒的后续效果会叠加 给定的两个数组cuts、poisons，两个数组等长，长度都是n 表示你在n回合内的行动， 每一回合的刀砍的效果由cuts[i]表示 每一回合的中毒的效果由poisons[i]表示 如果你在n个回合内没有直接杀死怪兽，意味着你已经无法有新的行动了 但是怪兽如果有中毒效果的话，那么怪兽依然会在hp耗尽的那回合死掉 返回你最快能在多少回合内将怪兽杀死 数据范围 : 1 <= n <= 10的5次方 1 <= hp <= 10的9次方 1 <= cuts[i]、poisons[i] <= 10的9次方 设计一个最大栈数据结构，既支持栈操作，又支持查找栈中最大元素。 实现 MaxStack 类： MaxStack() 初始化栈对象 void push(int x) 将元素 x 压入栈中。 int pop() 移除栈顶元素并返回这个元素。 int top() 返回栈顶元素，无需移除。 int peekMax() 检索并返回栈中最大元素，无需移除。 int popMax() 检索并返回栈中最大元素，并将其移除。 如果有多个最大元素，只要移除 最靠近栈顶 的那个。 测试链接 : https://leetcode.cn/problems/max-stack/ 这里有 n 个航班，它们分别从 1 到 n 进行编号。 有一份航班预订表 bookings ， 表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。 请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。 测试链接 : https://leetcode.cn/problems/corporate-flight-bookings/ 给你一个数组 nums，我们可以将它按一个非负整数 k 进行轮调， 例如，数组为 nums = [2,4,1,3,0]， 我们按 k = 2 进行轮调后，它将变成 [1,3,0,2,4]。 这将记为 3 分， 因为 1 > 0 [不计分]、3 > 1 [不计分]、0 <= 2 [计 1 分]、 2 <= 3 [计 1 分]，4 <= 4 [计 1 分]。 在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调下标 k 。 如果有多个答案，返回满足条件的最小的下标 k 。 测试链接 : https://leetcode.cn/problems/smallest-rotation-with-highest-score/ 第037节 2022年8月第4周流行算法题目解析 来自神策 给定一个数组arr，表示连续n天的股价，数组下标表示第几天 指标X：任意两天的股价之和 - 此两天间隔的天数 比如 第3天，价格是10 第9天，价格是30 那么第3天和第9天的指标X = 10 + 30 - (9 - 3) = 34 返回arr中最大的指标X 来自美团 8.20笔试 小团生日收到妈妈送的两个一模一样的数列作为礼物！ 他很开心的把玩，不过不小心没拿稳将数列摔坏了！ 现在他手上的两个数列分别为A和B，长度分别为n和m。 小团很想再次让这两个数列变得一样。他现在能做两种操作： 操作一是将一个选定数列中的某一个数a改成数b，这会花费|b-a|的时间， 操作二是选择一个数列中某个数a，将它从数列中丢掉，花费|a|的时间。 小团想知道，他最少能以多少时间将这两个数列变得再次相同！ 输入描述： 第一行两个空格隔开的正整数n和m，分别表示数列A和B的长度。 接下来一行n个整数，分别为A1 A2…An 接下来一行m个整数，分别为B1 B2…Bm 对于所有数据，1 ≤ n,m ≤ 2000， |Ai|,|Bi| ≤ 10000 输出一行一个整数，表示最少花费时间，来使得两个数列相同。 来自美团 题目1 8.20笔试 小美将要期中考试，有n道题，对于第i道题， 小美有pi的几率做对，获得ai的分值，还有(1-pi)的概率做错，得0分。 小美总分是每道题获得的分数。 小美不甘于此，决定突击复习，因为时间有限，她最多复习m道题，复习后的试题正确率为100%。 如果以最佳方式复习，能获得期望最大总分是多少？ 输入n、m 接下来输入n个整数，代表pi%，为了简单期间，将概率扩大了100倍。 接下来输入n个整数，代表ai，某道题的分值 输出最大期望分值，精确到小数点后2位 数据 1m<=n<=50000 简单题, 课上提一下解法即可 题目2 小团在地图上放了3个定位装置，想依赖他们进行定位！ 地图是一个n*n的棋盘， 有3个定位装置(x1,y1),(x2,y2),(x3,y3)，每个值均在[1,n]内。 小团在(a,b)位置放了一个信标， 每个定位装置会告诉小团它到信标的曼哈顿距离，也就是对于每个点，小团知道|xi-a|+|yi-b| 求信标位置，信标不唯一，输出字典序最小的。 输入n，然后是3个定位装置坐标， 最后是3个定位装置到信标的曼哈顿记录。 输出最小字典序的信标位置。 1 <= 所有数据值 <= 50000 来自微软 给定一个字符串s，只含有0~9这些字符 你可以使用来自s中的数字，目的是拼出一个最大的回文数 使用数字的个数，不能超过s里含有的个数 比如 : 39878，能拼出的最大回文数是 : 898 00900，能拼出的最大回文数是 : 9 54321，能拼出的最大回文数是 : 5 最终的结果以字符串形式返回 str的长度为N，1 <= N <= 100000 测试链接 : https://leetcode.cn/problems/largest-palindromic-number/ 来自微软 给定两个数组A和B，比如 A = { 0, 1, 1 } B = { 1, 2, 3 } A[0] = 0, B[0] = 1，表示0到1有双向道路 A[1] = 1, B[1] = 2，表示1到2有双向道路 A[2] = 1, B[2] = 3，表示1到3有双向道路 给定数字N，编号从0~N，所以一共N+1个节点 题目输入一定保证所有节点都联通，并且一定没有环 默认办公室是0节点，其他1~N节点上，每个节点上都有一个居民 每天所有居民都去往0节点上班 所有的居民都有一辆5座的车，也都乐意和别人一起坐车 车不管负重是多少，只要走过一条路，就耗费1的汽油 比如A、B、C的居民，开着自己的车来到D居民的位置，一共耗费3的汽油 D居民和E居民之间，假设有一条路 那么D居民可以接上A、B、C，4个人可以用一辆车，去往E的话，就再耗费1的汽油 求所有居民去办公室的路上，最少耗费多少汽油 测试链接 : https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/ 来自网易 小红拿到了一个仅由r、e、d组成的字符串 她定义一个字符e为"好e" : 当且仅当这个e字符和r、d相邻 例如"reeder"只有一个"好e"，前两个e都不是"好e"，只有第三个e是"好e" 小红每次可以将任意字符修改为任意字符，即三种字符可以相互修改 她希望"好e"的数量尽可能多 小红想知道，自己最少要修改多少次 输入一个只有r、e、d三种字符的字符串 长度 <= 2 * 10^5 输出最小修改次数 第038节 2022年8月第5周流行算法题目解析 来自学员面试 nim博弈 有a块草莓蛋糕，有b块芝士蛋糕，两人轮流拿蛋糕 每次不管是谁只能选择在草莓蛋糕和芝士蛋糕中拿一种 拿的数量在1~m之间随意 谁先拿完最后的蛋糕谁赢 返回先手赢还是后手赢 给定一个由 '[' ，']'，'('，‘)’ 组成的字符串 请问最少插入多少个括号就能使这个字符串的所有括号左右配对 例如当前串是 "([[])"，那么插入一个']'即可满足 输出最少插入多少个括号 测试链接 : https://www.nowcoder.com/practice/e391767d80d942d29e6095a935a5b96b 来自Amazon 定义一个概念叫"变序最大和" "变序最大和"是说一个数组中，每个值都可以减小或者不变， 在必须把整体变成严格升序的情况下，得到的最大累加和 比如，[1,100,7]变成[1,6,7]时，就有变序最大和为14 比如，[5,4,9]变成[3,4,9]时，就有变序最大和为16 比如，[1,4,2]变成[0,1,2]时，就有变序最大和为3 给定一个数组arr，其中所有的数字都是>=0的 求arr所有子数组的变序最大和中，最大的那个并返回 1 <= arr长度 <= 10^6 0 <= arr[i] <= 10^6 给定n棵树，和两个长度为n的数组a和b i号棵树的初始重量为a[i]，i号树每天的增长重量为b[i] 你每天最多能砍1棵树，这天收益 = 砍的树初始重量 + 砍的树增长到这天的总增重 给定m，表示你有m天，返回m天内你获得的最大收益 本题测试链接 : https://zoj.pintia.cn/problem-sets/91827364500/problems/91827367873 增加的题目: 小红定义"漂亮串"为：至少有两个"red"子串 例如"redxred"为漂亮串，但"reedred"则不是漂亮串 小红想知道长度为n，仅包含小写字母的所有字符串中，共有多少个不同的漂亮串？ 输入描述： 一个正整数n，代表字符串长度 n <= 10^6 输出描述： 长度为n，仅包含小写字母的所有字符串中，共有多少个不同的漂亮串，结果对10^9 + 7取模 本题为课堂临时增加，只有当堂讲述，没有代码实现 回答帖子 : https://www.mashibing.com/question/detail/34493 第039节 2022年9月第1周流行算法题目解析 给你一个由小写字母组成的字符串 s ，和一个整数 k 如果满足下述条件，则可以将字符串 t 视作是 理想字符串 ： t 是字符串 s 的一个子序列。 t 中每两个 相邻 字母在字母表中位次的绝对差值小于或等于 k 。 返回 最长 理想字符串的长度。 字符串的子序列同样是一个字符串，并且子序列还满足： 可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。 注意：字母表顺序不会循环 例如，'a' 和 'z' 在字母表中位次的绝对差值是 25，而不是 1 。 测试链接 : https://leetcode.cn/problems/longest-ideal-subsequence/ 来自美团 有n个城市，城市从0到n-1进行编号。小美最初住在k号城市中 在接下来的m天里，小美每天会收到一个任务 她可以选择完成当天的任务或者放弃该任务 第i天的任务需要在ci号城市完成，如果她选择完成这个任务 若任务开始前她恰好在ci号城市，则会获得ai的收益 若她不在ci号城市，她会前往ci号城市，获得bi的收益 当天的任务她都会当天完成 任务完成后，她会留在该任务所在的ci号城市直到接受下一个任务 如果她选择放弃任务，她会停留原地，且不会获得收益 小美想知道，如果她合理地完成任务，最大能获得多少收益 输入描述: 第一行三个正整数n, m和k，表示城市数量，总天数，初始所在城市 第二行为m个整数c1, c2,...... cm，其中ci表示第i天的任务所在地点为ci 第三行为m个整数a1, a2,...... am，其中ai表示完成第i天任务且地点不变的收益 第四行为m个整数b1, b2,...... bm，其中bi表示完成第i天的任务且地点改变的收益 0 <= k, ci <= n <= 30000 1 <= m <= 30000 0 <= ai, bi <= 10^9 输出描述 输出一个整数，表示小美合理完成任务能得到的最大收益 来自美团 给定一个正数n, 表示从0位置到n-1位置每个位置放着1件衣服 从0位置到n-1位置不仅有衣服，每个位置还摆着1个机器人 给定两个长度为n的数组，powers和rates powers[i]表示i位置的机器人的启动电量 rates[i]表示i位置的机器人收起1件衣服的时间 使用每个机器人只需要付出启动电量 当i位置的机器人收起i位置的衣服，它会继续尝试往右收起i+1位置衣服 如果i+1位置的衣服已经被其他机器人收了或者其他机器人正在收 这个机器人就会停机, 不再收衣服。 不过如果它不停机，它会同样以rates[i]的时间来收起这件i+1位置的衣服 也就是收衣服的时间为每个机器人的固定属性，当它收起i+1位置的衣服， 它会继续检查i+2位置...一直到它停机或者右边没有衣服可以收了 形象的来说，机器人会一直尝试往右边收衣服，收k件的话就耗费k * rates[i]的时间 但是当它遇见其他机器人工作的痕迹，就会认为后面的事情它不用管了，进入停机状态 你手里总共有电量b，准备在0时刻将所有想启动的机器人全部一起启动 过后不再启动新的机器人，并且启动机器人的电量之和不能大于b 返回在最佳选择下，假快多久能收完所有衣服 如果无论如何都收不完所有衣服，返回-1 给定数据: int n, int b, int[] powers, int[] rates 数据范围: powers长度 == rates长度 == n <= 1000 1 <= b <= 10^5 1 <= powers[i]、rates[i] <= 10^5 来自学员问题 给你一个长度为n的数组，并询问q次 每次询问区间[l,r]之间是否存在小于等于k个数的和大于等于x 每条查询返回true或者false 1 <= n, q <= 10^5 k <= 10 1 <= x <= 10^8 来自微软面试 给定一个长度为n的二维数组graph，代表一张图 graph[i] = {a,b,c,d} 表示i讨厌(a,b,c,d)，讨厌关系为双向的 一共有n个人，编号0~n-1 讨厌的人不能一起开会 返回所有人能不能分成两组开会 测试链接 : https://leetcode.cn/problems/is-graph-bipartite/ 第040节 2022年9月第2周流行算法题目解析 来自百度 二狗买了一些小兵玩具，和大胖一起玩 一共有n个小兵，这n个小兵拍成一列 第i个小兵战斗力为hi，然后他们两个开始对小兵进行排列 一共进行m次操作，二狗每次操作选择一个数k，将前k个小兵战斗力从小到大排列 大胖每次操作选择一个数k，将前k个小兵战斗力从大到小排列 问所有操作结束后，排列顺序什么样 给定一个长度为n的数组arr，表示每个小兵的战斗力 给定一个长度为m的数组op, op[i] = { k , 0 }, 表示对前k个士兵执行从小到大的操作 op[i] = { k , 1 }, 表示对前k个士兵执行从大到小的操作 返回数组ans，表示最终的排列 1 <= n, m <= 2 * 10^5 - 10^9 <= arr[i] <= + 10^9 来自微众银行 给定一个数字n，代表数组的长度 给定一个数字m，代表数组每个位置都可以在1~m之间选择数字 所有长度为n的数组中，最长递增子序列长度为3的数组，叫做达标数组 返回达标数组的数量 1 <= n <= 500 1 <= m <= 10 来自微软 给定一个字符串s，其中都是英文小写字母 如果s中的子串含有的每种字符都是偶数个 那么这样的子串就是达标子串，子串要求是连续串 返回s中达标子串的最大长度 1 <= s的长度 <= 10^5 字符种类都是英文小写 来自学员问题 有一个数组包含0、1、2三种值， 有m次修改机会，第一种将所有连通的1变为0，修改次数-1 第二种将所有连通的2变为1或0，修改次数-2， 返回m次修改机会的情况下，让最大的0连通区，最长能是多少？ 1 <= arr长度 <= 10^6 0 <= 修改机会 <= 10^6 第041节 2022年9月第3周流行算法题目解析 来自360 有n个黑白棋子，它们的一面是黑色，一面是白色 它们被排成一行，位置0~n-1上。一开始所有的棋子都是黑色向上 一共有q次操作，每次操作将位置标号在区间[L，R]内的所有棋子翻转 那么这个范围上的每一颗棋子的颜色也就都改变了 请在每次操作后，求这n个棋子中，黑色向上的棋子个数 1 <= n <= 10^18 1 <= q <= 300 0 <= 每一条操作的L、R <= n - 1 输出q行，每一行一个整数，表示操作后的所有黑色棋子的个数 注意 : 其实q <= 10^5也可以通过，360考试时候降低了难度 来自美团 某天小美进入了一个迷宫探险，根据地图所示，这个迷宫里有无数个房间 序号分别为1、2、3、...入口房间的序号为1 任意序号为正整数x的房间，都与序号 2*x 和 2*x + 1 的房间之间各有一条路径 但是这些路径是单向的，即只能从序号为x的房间去到序号为 2*x 或 2*x+1 的房间 而不能从 2*x 或 2*x+1 的房间去到序号为x的房间 在任何时刻小美都可以选择结束探险并离开迷宫，但是离开之后将无法再次进入迷宫 小美还提前了解了迷宫中宝藏的信息 已知宝藏共有n个，其中第i个宝藏在序号为pi的房间，价值为wi 且一个房间中可能有多个宝藏 小美为了得到更多的宝藏，需要精心规划路线，她找到你帮忙 想请你帮她计算一下，能获得的宝藏价值和最大值为多少 第一行一个正整数n，表示宝藏数量。 第二行为n个正整数p1, p2,...... pn，其中pi表示第 i 个宝藏在序号为pi的房间。 第三行为n个正整数w1, w2,...... wn，其中wi表示第i个宝藏的价值为wi。 1 <= n <= 40000, 1 <= pi < 2^30, 1 <= wi <= 10^6。 来自美团 某天，小美在玩一款游戏，游戏开始时，有n台机器， 每台机器都有一个能量水平，分别为a1、a2、…、an， 小美每次操作可以选其中的一台机器，假设选的是第i台， 那小美可以将其变成 ai+10^k（k为正整数且0<=k<=9）， 由于能量过高会有安全隐患，所以机器会在小美每次操作后会自动释放过高的能量 即变成 (ai+10^k)%m 其中%m表示对m取模，由于小美还有工作没有完成，所以她想请你帮她计算一下， 对于每台机器，将其调节至能量水平为0至少需要多少次操作 机器自动释放能量不计入小美的操作次数）。 第一行两个正整数n和m，表示数字个数和取模数值。 第二行为n个正整数a1, a2,...... an，其中ai表示第i台机器初始的能量水平。 1 <= n <= 30000，2 <= m <= 30000, 0 <= ai <= 10^12。 来自美团 有三个题库A、B、C，每个题库均有n道题目，且题目都是从1到n进行编号 每个题目都有一个难度值 题库A中第i个题目的难度为ai 题库B中第i个题目的难度为bi 题库C中第i个题目的难度为ci 小美准备组合出一套试题，试题共有三道题， 第一题来自题库A，第二题来自题库B，第三题来自题库C 试题要求题目难度递增，且梯度不能过大 具体地说，第二题的难度必须大于第一题的难度，但不能大于第一题难度的两倍 第三题的难度必须大于第二题的难度，但不能大于第二题难度的两倍 小美想知道在满足上述要求下，有多少种不同的题目组合 (三道题目中只要存在一道题目不同，则两个题目组合就视为不同 输入描述 第一行一个正整数n, 表示每个题库的题目数量 第二行为n个正整数a1, a2,...... an，其中ai表示题库A中第i个题目的难度值 第三行为n个正整数b1, b2,...... bn，其中bi表示题库B中第i个题目的难度值 第四行为n个正整数c1, c2,...... cn，其中ci表示题库C中第i个题目的难度值 1 <= n <= 20000, 1 <= ai, bi, ci <= 10^9。 来自字节 给定一个只由小写字母组成的字符串str，长度为N 给定一个只由0、1组成的数组arr，长度为N arr[i] == 0表示str中i位置的字符不许修改 arr[i] == 1表示str中i位置的字符允许修改 给定一个正数m，表示在任意允许修改的位置 可以把该位置的字符变成a~z中的任何一个 可以修改m次 返回在最多修改m次的情况下，全是一种字符的最长子串是多长 1 <= N, M <= 10^5 所有字符都是小写 来自阿里 小红定义一个仅有r、e、d三种字符的字符串中 如果仅有一个长度不小于2的回文子串，那么这个字符串定义为"好串" 给定一个正整数n，输出长度为n的好串有多少个 结果对10^9 + 7取模， 1 <= n <= 10^9 示例： n = 1, 输出0 n = 2, 输出3 n = 3, 输出18 https://www.mashibing.com/question/detail/37485 第042节 2022年9月第4周流行算法题目解析 来自学员问题 智能机器人要坐专用电梯把货物送到指定地点 整栋楼只有一部电梯，并且由于容量限制智能机器人只能放下一件货物 给定K个货物，每个货物都有所在楼层(from)和目的楼层(to) 假设电梯速度恒定为1，相邻两个楼层之间的距离为1 例如电梯从10层去往19层的时间为9 机器人装卸货物的时间极快不计入 电梯初始地点为第1层，机器人初始地点也是第1层 并且在运送完所有货物之后，机器人和电梯都要回到1层 返回智能机器人用电梯将每个物品都送去目标楼层的最快时间 注意：如果智能机器人选了一件物品，则必须把这个物品送完，不能中途丢下 输入描述： 正数k，表示货物数量，1 <= k <= 16 from、to数组，长度都是k，1 <= from[i]、to[i] <= 10000 from[i]表示i号货物所在的楼层 to[i]表示i号货物要去往的楼层 返回最快的时间 来自华为 一个n*n的二维数组中，只有0和1两种值 当你决定在某个位置操作一次 那么该位置的行和列整体都会变成1，不管之前是什么状态 返回让所有值全变成1，最少的操作次数 1 < n < 10，没错！原题就是说n < 10, 不会到10！最多到9！ 来自华为 给定一个二维数组map，代表一个餐厅，其中只有0、1两种值 map[i][j] == 0 表示(i,j)位置是空座 map[i][j] == 1 表示(i,j)位置坐了人 根据防疫要求，任何人的上、下、左、右，四个相邻的方向都不能再坐人 但是为了餐厅利用的最大化，也许还能在不违反防疫要求的情况下，继续安排人吃饭 请返回还能安排的最大人数 如果一开始的状况已经不合法，直接返回-1 比如: 1 0 0 0 0 0 0 1 不违反防疫要求的情况下，这个餐厅最多还能安排2人，如下所示，X是新安排的人 1 0 X 0 0 X 0 1 再比如: 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 不违反防疫要求的情况下，这个餐厅最多还能安排7人，如下所示，X是新安排的人 1 0 0 X 0 1 0 0 X 0 X 0 0 1 0 X 0 1 X 0 X 0 X 0 数据范围 : 1 <= 矩阵的行、列 <= 20 给你两个整数 m 和 n 。构造一个 m x n 的网格，其中每个单元格最开始是白色 请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色 涂色方案需要满足：不存在相邻两个单元格颜色相同的情况 返回网格涂色的方法数。因为答案可能非常大 返回 对 109 + 7 取余 的结果。 1 <= n <= 1000 1 <= m <= 5 测试链接 : https://leetcode.cn/problems/painting-a-grid-with-three-different-colors/ 来自字节 给定正数N，表示用户数量，用户编号从0~N-1 给定正数M，表示实验数量，实验编号从0~M-1 给定长度为N的二维数组A， A[i] = { a, b, c }表示，用户i报名参加了a号、b号、c号实验 给定正数Q，表示查询的条数 给定长度为Q的二维数组B， B[i] = { e, f }表示，第i条查询想知道e号、f号实验，一共有多少人(去重统计) 返回每一条查询的结果数组 数据描述 : 1 <= N <= 10^5 1 <= M <= 10^2 1 <= Q <= 10^4 所有查询所列出的所有实验编号数量(也就是二维数组B，行*列的规模) <= 10^5 第043节 2022年10月第1周流行算法题目解析 力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号 它们之间以「服务器到服务器」点对点的形式相互连接组成了一个内部集群 其中连接 connections 是无向的 从形式上讲，connections[i] = [a, b] 表示服务器 a 和 b 之间形成连接 任何服务器都可以直接或者间接地通过网络到达任何其他服务器。 "关键连接"是在该集群中的重要连接，也就是说，假如我们将它移除 便会导致某些服务器无法访问其他服务器。 请你以任意顺序返回该集群内的所有"关键连接" 测试链接 : https://leetcode.cn/problems/critical-connections-in-a-network/ 来自Leetcode周赛 魔物了占领若干据点，这些据点被若干条道路相连接， roads[i] = [x, y] 表示编号 x、y 的两个据点通过一条道路连接。 现在勇者要将按照以下原则将这些据点逐一夺回： 在开始的时候，勇者可以花费资源先夺回一些据点， 初始夺回第 j 个据点所需消耗的资源数量为 cost[j] 接下来，勇者在不消耗资源情况下， 每次可以夺回一个和「已夺回据点」相连接的魔物据点， 并对其进行夺回 为了防止魔物暴动，勇者在每一次夺回据点后（包括花费资源夺回据点后）， 需要保证剩余的所有魔物据点之间是相连通的（不经过「已夺回据点」）。 请返回勇者夺回所有据点需要消耗的最少资源数量。 输入保证初始所有据点都是连通的，且不存在重边和自环 测试链接 : https://leetcode.cn/problems/s5kipK/ 来自学员问题 商场中有一展柜A，其大小固定，现已被不同的商品摆满 商家提供了一些新商品B，需要对A中的部分商品进行更新替换 B中的商品可以自由使用，也就是可以用B中的任何商品替换A中的任何商品 A中的商品一旦被替换，就认为消失了！而不是回到了B中！ 要求更新过后的展柜中，商品严格按照价格由低到高进行排列 不能有相邻商品价格相等的情况 A[i]为展柜中第i个位置商品的价格，B[i]为各个新商品的价格 求能够满足A中商品价格严格递增的最小操作次数，若无法满足则返回-1 来自美团 两种颜色的球，蓝色和红色，都按1～n编号，共计2n个 为方便放在一个数组中，红球编号取负，篮球不变，并打乱顺序， 要求同一种颜色的球按编号升序排列，可以进行如下操作： 交换相邻两个球，求最少操作次数。 [3,-3,1,-4,2,-2,-1,4] 最终交换结果为 [1,2,3,-1,-2,-3,-4,4] 最少交换次数为10 n <= 1000 第044节 2022年10月第2周流行算法题目解析 来自小红书 小A认为如果在数组中有一个数出现了至少k次 且这个数是该数组的众数，即出现次数最多的数之一 那么这个数组被该数所支配 显然当k比较大的时候，有些数组不被任何数所支配 现在小A拥有一个长度为n的数组，她想知道内部有多少个区间是被某个数支配的 2 <= k <= n <= 100000 1 <= 数组的值 <= n 来自京东 实习岗位笔试题 给定一个数组arr，长度为n 任意相邻的两个数里面至少要有一个被选出来，组成子序列，才是合法的！ 求所有可能的合法子序列中，最大中位数是多少 中位数的定义为上中位数 [1, 2, 3, 4]的上中位数是2 [1, 2, 3, 4, 5]的上中位数是3 2 <= n <= 10^5 1 <= arr[i] <= 10^9 我写的帖子解答 : https://www.mashibing.com/question/detail/34771 定义一个二维数组N*M，比如5*5数组下所示： 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路 只能横着走或竖着走，不能斜着走 要求编程序找出从左上角到右下角距离最短的路线 测试链接 : https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc 来自Airbnb、Uber 给定一个二维网格 grid ，其中： '.' 代表一个空房间 '#' 代表一堵 '@' 是起点 小写字母代表钥匙 大写字母代表锁 我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间 我们不能在网格外面行走，也无法穿过一堵墙 如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。 假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6， 字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母 换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁 另外，代表钥匙和锁的字母互为大小写并按字母顺序排列 返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。 测试链接：https://leetcode.cn/problems/shortest-path-to-get-all-keys 来自华为 给定一个N*M的二维矩阵，只由字符'O'、'X'、'S'、'E'组成 'O'表示这个地方是可通行的平地 'X'表示这个地方是不可通行的障碍 'S'表示这个地方有一个士兵，全图保证只有一个士兵 'E'表示这个地方有一个敌人，全图保证只有一个敌人 士兵可以在上、下、左、右四个方向上移动 走到相邻的可通行的平地上，走一步耗费a个时间单位 士兵从初始地点行动时，不管去哪个方向，都不用耗费转向的代价 但是士兵在行动途中，如果需要转向，需要额外再付出b个时间单位 返回士兵找到敌人的最少时间 如果因为障碍怎么都找不到敌人，返回-1 1 <= N,M <= 1000 1 <= a,b <= 100000 只会有一个士兵、一个敌人 第045节 2022年10月第3周流行算法题目解析 给定一个整数数组 A，坡是元组 (i, j)，其中  i < j 且 A[i] <= A[j] 这样的坡的宽度为 j - i 找出 A 中的坡的最大宽度，如果不存在，返回 0 示例 1： 输入：[6,0,8,2,1,5] 输出：4 解释： 最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5 示例 2： 输入：[9,8,1,0,1,9,4,0,4,1] 输出：7 解释： 最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1 测试链接 : https://leetcode.cn/problems/maximum-width-ramp/ 给定一个由 0 和 1 组成的数组 arr ，将数组分成 3 个非空的部分 使得所有这些部分表示相同的二进制值。 如果可以做到，请返回任何 [i, j]，其中 i+1 < j，这样一来 arr[0], arr[1], ..., arr[i] 为第一部分 arr[i + 1], arr[i + 2], ..., arr[j - 1] 为第二部分 arr[j], arr[j + 1], ..., arr[arr.length - 1] 为第三部分 这三个部分所表示的二进制值相等 如果无法做到，就返回 [-1, -1] 注意，在考虑每个部分所表示的二进制时，应当将其看作一个整体 例如，[1,1,0] 表示十进制中的 6，而不会是 3。此外，前导零也是被允许的 所以 [0,1,1] 和 [1,1] 表示相同的值。 测试链接 : https://leetcode.cn/problems/three-equal-parts/ 来自阿里 给定一个长度n的数组，每次可以选择一个数x 让这个数组中所有的x都变成x+1，问你最少的操作次数 使得这个数组变成一个非降数组 n <= 3 * 10^5 0 <= 数值 <= 10^9 来自Lucid Air 给定一个无向图，保证所有节点连成一棵树，没有环 给定一个正数n为节点数，所以节点编号为0~n-1，那么就一定有n-1条边 每条边形式为{a, b, w}，意思是a和b之间的无向边，权值为w 要求：给定一个正数k，表示在挑选之后，每个点相连的边，数量都不能超过k 注意：是每个点的连接数量，都不超过k！不是总连接数量不能超过k！ 你可以随意挑选边留下，剩下的边删掉，但是要满足上面的要求 返回不违反要求的情况下，你挑选边所能达到的最大权值累加和 给定一个字符串str 如果删掉连续一段子串，剩下的字符串拼接起来是回文串 那么该删除叫做有效的删除 返回有多少种有效删除 注意 : 不能全删除，删成空串不允许 字符串长度 <= 3000 第046节 2022年10月第4周流行算法题目解析 来自华为 若两个正整数的和为素数，则这两个正整数称之为"素数伴侣" 给定N(偶数)个正整数中挑选出若干对，组成"素数伴侣" 例如有4个正整数：2，5，6，13， 如果将5和6分为一组的话，只能得到一组"素数伴侣" 如果将2和5、6和13编组，将得到两组"素数伴侣" 这是得到"素数伴侣"最多的划分方案 输入: 有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。 输出: 输出一个整数 K ，表示最多能找出几对"素数伴侣" 数据范围： 1 <= n <= 100, 2 <= val <= 30000 测试链接 : https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e 来自学员问题 给定一个二维数组matrix 每个格子都是正数，每个格子都和上、下、左、右相邻 你可以从任何一个格子出发，走向相邻的格子 把沿途的数字乘起来，希望得到的最终数字中，结尾的0最多 走的过程中，向左走或者向右走的拐点，最多只能有一次 返回结尾最多的0，能是多少 1 <= 行、列 <= 400 有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置 给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置 你可以按顺序完成切割，也可以根据需要更改切割的顺序 每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和 对棍子进行切割将会把一根木棍分成两根较小的木棍 这两根木棍的长度和就是切割前木棍的长度 返回切棍子的最小总成本 测试链接 : https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/ 来自拼多多 第一行有一个正整数n(3<=n<=100000)，代表小A拟定的路线数量 第二行有n个正整数，第i个代表第i条路线的起始日期 第三行有n个正整数，第i个代表第i条路线的终止日期 输入保证起始日期小于终止日期 日期最小是1，最大不超过1000000000 小A打算选三个路线进行旅游，比如 A -> B -> C 要求A的结束日期要小于B的开始日期，B的结束日期要小于C的开始日期 输出一个非负整数，代表线路的方案数量 例子 输入 6 4 1 3 2 1 2 4 1 3 3 2 2 输出 6 解释 [1,1] -> [2,2] -> [3,3] [1,1] -> [2,2] -> [4,4] [1,1] -> [2,3] -> [4,4] [1,2] -> [3,3] -> [4,4] [1,1] -> [3,3] -> [4,4] [2,2] -> [3,3] -> [4,4] 给定一个字符串 s，返回 s 中不同的非空 回文子序列 个数 通过从 s 中删除 0 个或多个字符来获得子序列 如果一个字符序列与它反转后的字符序列一致，那么它是 回文字符序列 如果有某个 i , 满足 ai != bi ，则两个序列 a1, a2, ... 和 b1, b2, ... 不同 注意：结果可能很大，你需要对 10^9 + 7 取模 测试链接 : https://leetcode.cn/problems/count-different-palindromic-subsequences/ 来自学员问题 设计一个仓库管理器，提供如下的方法： 1) void supply(String item, int num, int price) 名字叫item的商品，个数num，价格price 2) int sell(String item, int num) 卖出叫item的商品，个数num个，价格从低到高，返回卖出总价 如果商品很多，每种商品的数量可能很多，该怎么设计这个结构 来自亚马逊 给定一个数组arr，和一个正数k 你可以随意删除arr中的数字，最多删除k个 目的是让连续出现一种数字的长度尽量长 返回这个尽量长的长度 比如数组arr = { 3, -2, 3, 3, 5, 6, 3, -2 }, k = 3 你可以删掉-2、5、6(最多3个)，这样数组arr = { 3, 3, 3, 3, -2 } 可以看到连续出现3的长度为4 这是所有删除方法里的最长结果，所以返回4 1 <= arr长度 <= 3 * 10^5 -10^9 <= arr中的数值 <= 10^9 0 <= k <= 3 * 10^5 第047节 2022年11月第1周流行算法题目解析 来自华为 做甜点需要购买配料，目前共有n种基料和m种配料可供选购 制作甜点需要遵循以下几条规则： 必须选择1种基料；可以添加0种、1种或多种配料，每种类型的配料最多添加2份 给定长度为n的数组base, base[i]表示第i种基料的价格 给定长度为m的数组topping, topping[j]表示第j种配料的价格 给定一个正数target，表示你做的甜点最终的价格要尽量接近这个数值 返回最接近这个数值的价格是多少 如果有多个方案，都最接近target，返回价格最小的那个答案 1 <= n,m <= 10 1 <= base[i], topping[j] <= 10 ^ 4 1 <= target <= 10 ^ 4 来自蚂蚁金服 得分的定义 : 含有大小2*2的矩阵，要么： 1 0 0 1 可以得1分 要么 0 1 1 0 可以得1分 那么一个任意大小的矩阵就有若干得分点，比如 0 1 0 1 0 1 这个矩阵就有2个得分点 给定正数N，正数M，求所有可能的情况里，所有的得分点总和 1 <= N、M <= 10^9 来自蚂蚁金服 小红有n个朋友, 她准备开个宴会，邀请一些朋友 i号朋友的愉悦值为a[i]，财富值为b[i] 如果两个朋友同时参加宴会，这两个朋友之间的隔阂是其财富值差值的绝对值 宴会的隔阂值，是财富差距最大的两人产生的财富值差值的绝对值 宴会的愉悦值，是所有参加宴会朋友的愉悦值总和 小红可以邀请任何人， 希望宴会的愉悦值不能小于k的情况下， 宴会的隔阂值能最小是多少 如果做不到，返回-1 1 <= n <= 2 * 10^5 1 <= 愉悦值、财富值 <= 10^9 1 <= k <= 10^14 来自CISCO 给定两个正整数x、y，都是int整型(java里) 返回0 ~ x以内，每位数字加起来是y的数字个数 比如，x = 20、y = 5，返回2 因为0 ~ x以内，每位数字加起来是5的数字有：5、14 x、y范围是java里正整数的范围 x <= 2 * 10^9 y <= 90 给你下标从 0 开始、长度为 n 的字符串 pattern ， 它包含两种字符，'I' 表示 上升 ，'D' 表示 下降 。 你需要构造一个下标从 0 开始长度为 n + 1 的字符串，且它要满足以下条件： num 包含数字 '1' 到 '9' ，其中每个数字 至多 使用一次。 如果 pattern[i] == 'I' ，那么 num[i] < num[i + 1] 。 如果 pattern[i] == 'D' ，那么 num[i] > num[i + 1] 。 请你返回满足上述条件字典序 最小 的字符串 num。 测试链接 : https://leetcode.cn/problems/construct-smallest-number-from-di-string/ 第048节 2022年11月第3周流行算法题目解析 来自亚马逊 给定一个字符串数组strs，其中每个字符串都是小写字母组成的 如果i < j，并且strs[i]和strs[j]所有的字符随意去排列能组成回文串 那么说(i,j)叫做一个互补对(complementary) 求strs中有多少个互补对 strs长度 <= 3 * 10^5 单个字符串长度 <= 10^5 strs里所有字符串总长度 <= 10^6 n对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手 人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的ID 情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1) 返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起 每次交换可选择任意两人，让他们站起来交换座位 测试链接 : https://leetcode.cn/problems/couples-holding-hands/ 来自谷歌 给定一个长度为N的数组，值一定在0~N-1范围，且每个值不重复 比如，arr = [4, 2, 0, 3, 1] 把0想象成洞，任何非0数字都可以来到这个洞里，然后在原本的位置留下洞 比如4这个数字，来到0所代表的洞里，那么数组变成 : arr = [0, 2, 4, 3, 1] 也就是原来的洞被4填满，4走后留下了洞 任何数字只能搬家到洞里，并且走后留下洞 通过搬家的方式，想变成有序的，有序有两种形式 比如arr = [4, 2, 0, 3, 1]，变成 [0, 1, 2, 3, 4]或者[1, 2, 3, 4, 0]都叫有序 返回变成任何一种有序的情况都可以，最少的数字搬动次数 测试链接 : https://leetcode.cn/problems/sort-array-by-moving-items-to-empty-space/ 设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。 实现 WordFilter 类： WordFilter(string[] words) 使用词典中的单词 words 初始化对象 f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 的单词的下标 如果存在不止一个满足要求的下标，返回其中 最大的下标 如果不存在这样的单词，返回 -1 。 测试链接 : https://leetcode.cn/problems/prefix-and-suffix-search/ 设计一个叫Bank的类，并提供如下方法 Bank(int n) 初始化的时候，准备好0、1、2 ... n-1个座位 int hello() : 如果此时所有座位都无人，那么分配0号座位给当前用户 如果此时座位上有人，那么分配一个座位，这个座位保证是所有座位中离最近的人距离最远的座位 如果有多个座位都满足，分配座位编号最小的座位 返回座位编号 如果已经没有座位，返回-1表示无法分配 void goodbye(int x) : 如果x号座位上无人，什么也不用做 如果x号座位上有人，现在这个人离开了，该座位又能重新考虑分配 举例 : Bank b = new Bank(10) 0~9号座位被初始化出来 b.hello()，返回0，表示给当前用户分配了0座位 b.hello()，返回9，因为此时9座位离0座位的人最远，此时 0 1 2 3 4 5 6 7 8 9 X X b.hello()，虽然座位4和座位5，离最近人的距离都是4(最远) 这种情况，根据描述，分配座位编号最小的座位，返回4，此时 0 1 2 3 4 5 6 7 8 9 X X X b.hello()，座位2、座位6、座位7，都是离最近人的距离最远的(2) 这种情况，根据描述，分配座位编号最小的座位，返回2，此时 0 1 2 3 4 5 6 7 8 9 X X X X b.goodbye(4)，4座位的人离开了，此时 0 1 2 3 4 5 6 7 8 9 X X X b.hello()，座位5、座位6，都是离最近人的距离最远的(3) 这种情况，根据描述，分配座位编号最小的座位，返回5 测试连接 : https://leetcode.cn/problems/exam-room/ 第049节 2022年11月第4周流行算法题目解析 来自国外题目论坛 给定一个非负数组arr 任何两个数差值的绝对值，如果arr中没有，都要加入到arr里 然后新的arr继续，任何两个数差值的绝对值，如果arr中没有，都要加入到arr里 一直到arr大小固定 请问最终arr长度是多少 1 <= arr的长度 <= 10^5 0 <= arr的数值 <= 10^5 来自字节 11.02笔试 leetcode原题 有一堆石头，用整数数组 stones 表示 其中 stones[i] 表示第 i 块石头的重量。 每一回合，从中选出任意两块石头，然后将它们一起粉碎 假设石头的重量分别为 x 和 y，且 x <= y 那么粉碎的可能结果如下： 如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块 石头 返回此石头 最小的可能重量 如果没有石头剩下，就返回 0 测试链接 : https://leetcode.cn/problems/last-stone-weight-ii/ 给你两个正整数数组 nums 和 target ，两个数组长度相等。 在一次操作中，你可以选择两个 不同 的下标 i 和 j ， 其中 0 <= i, j < nums.length ，并且： 令 nums[i] = nums[i] + 2 且 令 nums[j] = nums[j] - 2 。 如果两个数组中每个元素出现的频率相等，我们称两个数组是 相似 的。 请你返回将 nums 变得与 target 相似的最少操作次数。 测试数据保证 nums 一定能变得与 target 相似。 测试链接 : https://leetcode.cn/problems/minimum-number-of-operations-to-make-arrays-similar/ 给定你一个整数数组 nums 我们要将 nums 数组中的每个元素移动到 A 集合 或者 B 集合中 使得 A 集合和 B 集合不为空，并且 average(A) == average(B) 如果可以完成则返回true，否则返回false。 注意：对于数组 arr, average(arr) 是 arr 的所有元素的和除以 arr 长度。 测试链接 : https://leetcode.cn/problems/split-array-with-same-average/ 来自第四届全国大学生算法设计与编程挑战赛（秋季赛） 给定两个长度为N的数组，a[]和b[] 也就是对于每个位置i来说，有a[i]和b[i]两个属性 现在想为了i，选一个最好的j位置，搭配能得到最小的如下值: (a[i] + a[j]) ^ 2 + b[i] + b[j] 我们把这个最小的值，定义为i的最in值 比如 : a = { 2, 3, 6, 5, 1 } b = { 100, 70, 20, 40, 150 } 0 1 2 3 4 0位置和2位置搭配，可以得到最in值 : 184 1位置和2位置搭配，可以得到最in值 : 171 2位置和1位置搭配，可以得到最in值 : 171 3位置和1位置搭配，可以得到最in值 : 174 4位置和2位置搭配，可以得到最in值 : 219 注意 : i位置可以和i位置(自己)搭配，并不是说i和j一定要是不同的位置 返回每个位置i的最in值 比如上面的例子，最后返回[184, 171, 171, 174, 219] 1 <= N <= 10^5 1 <= a[i]、b[i] <= 10^9 第050节 2022年11月第5周流行算法题目解析 来自学员问题 给定一个数组componets，长度为A， componets[i] = j，代表i类型的任务需要耗时j 给定一个二维数组orders，长度为M， orders[i][0]代表i号订单下单时间 orders[i][1]代表i号订单是哪种类型的任务，毫无疑问orders[i][1] < A 一开始所有流水线都在0时刻待命， 给定一个正数nums，表示流水线的数量，流水线编号为0 ~ nums-1 每一个流水线可以承接任何类型的任务，耗时就是componets数组给定的 所有订单的下单时间一定是有序的，也就是orders数组，是根据下单时间排序的 每一个订单开始执行的时间不能早于下单时间， 如果有多个流水线都可以执行当前订单，选择编号最小的流水线 根据上面说的任务执行细节，去依次完成所有订单 返回长度为M的数组ans，也就是和orders等长 ans[i][0]代表i号订单是由哪条流水线执行的 ans[i][1]代表i号订单的完成时间 1 <= A <= 10^5 1 <= M <= 10^5 1 <= nums <= 10^5 1 <= 时间数值 <= 10^5 将一个给定字符串 s 根据给定的行数 numRows 以从上往下、从左到右进行 Z 字形排列 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下 P A H N A P L S I I G Y I R 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串 "PAHNAPLSIIGYIR" 请你实现这个将字符串进行指定行数变换的函数 string convert(string s, int numRows) 测试链接 : https://leetcode.cn/problems/zigzag-conversion/ 一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。 给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 由于答案可能非常大，请返回对 109 + 7 取余 后的结果。 子序列 定义为从一个数组里删除一些（或者不删除）元素， 但不改变剩下元素的顺序得到的数组 例如，[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。 测试链接 : https://leetcode.cn/problems/sum-of-subsequence-widths/ 给你一个整数 n ， 请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。 测试链接 : https://leetcode.cn/problems/nth-digit/ 1 <= n <= 2^31 - 1 第051节 2022年12月第1周流行算法题目解析 如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。 给你一个正整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。 测试链接 : https://leetcode.cn/problems/count-special-integers/ 给你一棵 二叉树 的根节点 root ，树中有 n 个节点 每个节点都可以被分配一个从 1 到 n 且互不相同的值 另给你一个长度为 m 的数组 queries 你必须在树上执行 m 个 独立 的查询，其中第 i 个查询你需要执行以下操作： 从树中 移除 以 queries[i] 的值作为根节点的子树 题目所用测试用例保证 queries[i] 不 等于根节点的值。 返回一个长度为 m 的数组 answer ，其中 answer[i] 是执行第 i 个查询后树的高度。 注意： 查询之间是独立的，所以在每个查询执行后，树会回到其 初始 状态。 树的高度是从根到树中某个节点的 最长简单路径中的边数 。 测试链接 : https://leetcode.cn/problems/height-of-binary-tree-after-subtree-removal-queries/ 给定一个无向、连通的树 树中有 n 个标记为 0...n-1 的节点以及 n-1 条边 。 给定整数 n 和数组 edges ， edges[i] = [ai, bi]表示树中的节点 ai 和 bi 之间有一条边。 返回长度为 n 的数组 answer ，其中 answer[i] : 树中第 i 个节点与所有其他节点之间的距离之和。 测试链接 : https://leetcode.cn/problems/sum-of-distances-in-tree/ X轴上有一些机器人和工厂。给你一个整数数组robot，其中robot[i]是第i个机器人的位置 再给你一个二维整数数组factory，其中 factory[j] = [positionj, limitj] 表示第 j 个工厂的位置在 positionj ，且第 j 个工厂最多可以修理 limitj 个机器人 每个机器人所在的位置 互不相同。每个工厂所在的位置也互不相同 注意一个机器人可能一开始跟一个工厂在相同的位置 所有机器人一开始都是坏的，他们会沿着设定的方向一直移动 设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向 当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动 任何时刻，你都可以设置 部分 机器人的移动方向 你的目标是最小化所有机器人总的移动距离 请你返回所有机器人移动的最小总距离 注意： 所有机器人移动速度相同 如果两个机器人移动方向相同，它们永远不会碰撞 如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过 如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动 机器人从位置 x 到位置 y 的移动距离为 |y - x| 1 <= robot.length, factory.length <= 100 factory[j].length == 2 -10^9 <= robot[i], positionj <= 10^9 0 <= limitj <= robot.length 测试数据保证所有机器人都可以被维修 测试链接 : https://leetcode.cn/problems/minimum-total-distance-traveled/ 不打算讲了，非常难 蓝桥杯练习题 洛谷原题 等差数列的概念人人都知道 给定一个原始数组arr，长度为N 并且实现如下两个操作 : void add(int l, int r, int a, int b) : 表示在arr[l...r]这个范围上， 从左往右依次加 : a、a + b * 1、a + b*2、...、a + b*(r-l) int number(int l, int r) : 表示arr[l...r]这一段，最少可以划分成几个等差数列 这两个方法都要求实现的特别高效，因为调用次数很多 N <= 100000 add调用次数 <= 100000 number调用次数 <= 100000 测试链接 : https://www.luogu.com.cn/problem/P4243 第052节 2022年12月第2周流行算法题目解析 有100个犯人被关在监狱里，编号0~99 监狱长构思了一个处决犯人的计划 监狱长准备了100个盒子，每个盒子里面装有一个犯人的名字 一开始每个犯人都知道自己的盒子在哪 因为自己的编号，与盒子的编号一致， 这100个盒子排成一排，放在一个房间里面，盒子编号0~99，从左到右排列 监狱长彻底随机的打乱了盒子的排列，并且犯人并没有看到打乱的过程 监狱长规定，每个犯人依次进入房间，每个犯人都可以开启50个盒子，然后关上 每一个犯人全程无法进行任何交流，完全无法传递任何信息 监狱长规定，每个犯人在尝试50次的过程中，都需要找到自己的名字 如果有哪怕一个犯人没有做到这一点，100个罪犯全部处决 但是监狱长允许这个游戏开始之前，所有犯人在一起商量策略 请尽量制定一个让所有人存活概率最大的策略 来自论文 作者Anna Gal和Peter Bro Miltersen写于2007年 如今该题变成了流行科普视频，我们来玩一玩 来自亚马逊、谷歌、微软、Facebook、Bloomberg 给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。 返回执行此操作后，grid 中最大的岛屿面积是多少？ 岛屿 由一组上、下、左、右四个方向相连的 1 形成。 测试链接 : https://leetcode.cn/problems/making-a-large-island/ 我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符， 并返回唯一字符的个数。 例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符， 因为它们只出现一次，所以 countUniqueChars(s) = 5 。 本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和， 其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。 注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串 （也就是说，你必须统计 s 的所有子字符串中的唯一字符）。 测试链接 : https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/ 石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。 有 n 块石子排成一排。 每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头， 并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。 鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输）， 所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。 给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值， 如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。 测试链接 : https://leetcode.cn/problems/stone-game-vii/ 给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉树中，存在一条一直向下的路径 且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True 否则返回 False 。 一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。 测试链接 : https://leetcode.cn/problems/linked-list-in-binary-tree/ 最优解是KMP算法来解 官方题解都没有写的最优解 如果二叉树节点数是N，链表节点数M，时间复杂度为O(M+N) 第053节 2022年12月第4周流行算法题目解析 给你一个 m x n 的二进制矩阵 grid 每个格子要么为 0 （空）要么为 1 （被占据） 给你邮票的尺寸为 stampHeight x stampWidth 我们想将邮票贴进二进制矩阵中，且满足以下 限制 和 要求 ： 覆盖所有空格子，不覆盖任何被占据的格子 可以放入任意数目的邮票，邮票可以相互有重叠部分 邮票不允许旋转，邮票必须完全在矩阵内 如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false 测试链接 : https://leetcode.cn/problems/stamping-the-grid/ Floyd算法解析 本题测试链接 : https://www.luogu.com.cn/problem/P2910 Floyd算法应用 存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号 给你一个数组 graph 表示这个图 其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成 返回能够访问所有节点的最短路径的长度 你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边 测试链接 : https://leetcode.cn/problems/shortest-path-visiting-all-nodes/ 你现在手里有一份大小为 n x n 的 网格 grid 上面的每个 单元格 都用 0 和 1 标记好了其中 0 代表海洋，1 代表陆地。 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的 并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）： (x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。 测试链接 : https://leetcode.cn/problems/as-far-from-land-as-possible/ 你的赛车可以从位置 0 开始，并且速度为 +1 ，在一条无限长的数轴上行驶 赛车也可以向负方向行驶 赛车可以按照由加速指令 'A' 和倒车指令 'R' 组成的指令序列自动行驶。 当收到指令 'A' 时，赛车这样行驶： position += speed speed *= 2 当收到指令 'R' 时，赛车这样行驶： 如果速度为正数，那么speed = -1 否则 speed = 1 当前所处位置不变。 例如，在执行指令 "AAR" 后，赛车位置变化为 0 --> 1 --> 3 --> 3 速度变化为 1 --> 2 --> 4 --> -1 给你一个目标位置 target ，返回能到达目标位置的最短指令序列的长度。 测试链接 : https://leetcode.cn/problems/race-car/ 对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次 能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值 测试链接 : https://leetcode.cn/problems/k-similar-strings/ 第054节 2023年1月第1周流行算法题目解析 给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。 请你找到这个数组里第 k 个缺失的正整数。 测试链接 : https://leetcode.cn/problems/kth-missing-positive-number/ 一个正整数如果能被 a 或 b 整除，那么它是神奇的。 给定三个整数 n , a , b ，返回第 n 个神奇的数字。 因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。 测试链接 : https://leetcode.cn/problems/nth-magical-number/ 有 n 名工人。 给定两个数组 quality 和 wage ， 其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。 现在我们想雇佣 k 名工人组成一个工资组。在雇佣 一组 k 名工人时， 我们必须按照下述规则向他们支付工资： 对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。 工资组中的每名工人至少应当得到他们的最低期望工资。 给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 测试链接 : https://leetcode.cn/problems/minimum-cost-to-hire-k-workers/ 汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。 沿途有加油站，每个 station[i] 代表一个加油站， 它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。 假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。 它每行驶 1 英里就会用掉 1 升汽油。 当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。 为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。 注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。 如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。 测试链接 : https://leetcode.cn/problems/minimum-number-of-refueling-stops/ 给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个 并把它加到字符串的末尾 返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串 测试链接 : https://leetcode.cn/problems/orderly-queue/ 给定一个长度为 n 的字符串 s ，其中 s[i] 是: D 意味着减少 I 意味着增加 有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm ，使得对所有的 i： 如果 s[i] == 'D'，那么 perm[i] > perm[i+1]，以及； 如果 s[i] == 'I'，那么 perm[i] < perm[i+1]。 返回 有效排列 perm的数量 。因为答案可能很大，所以请返回你的答案对 10^9 + 7 取余。 测试链接 : https://leetcode.cn/problems/valid-permutations-for-di-sequence/ 第055节 2023年1月第2周流行算法题目解析 如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等， 那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。 例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。 总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。 注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。 形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。 给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。 请问 strs 中有多少个相似字符串组？ 测试链接 : https://leetcode.cn/problems/similar-string-groups/ 设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。 实现 FreqStack 类: FreqStack() 构造一个空的堆栈。 void push(int val) 将一个整数 val 压入栈顶。 int pop() 删除并返回堆栈中出现频率最高的元素。 如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。 测试链接 : https://leetcode.cn/problems/maximum-frequency-stack/ 给定一个正整数 x，我们将会写出一个形如 x (op1) x (op2) x (op3) x ... 的表达式 其中每个运算符 op1，op2，… 可以是加、减、乘、除之一 例如，对于 x = 3，我们可以写出表达式 3 * 3 / 3 + 3 - 3，该式的值为3 在写这样的表达式时，我们需要遵守下面的惯例： 除运算符（/）返回有理数 任何地方都没有括号 我们使用通常的操作顺序：乘法和除法发生在加法和减法之前 不允许使用一元否定运算符（-）。例如，“x - x” 是一个有效的表达 因为它只使用减法，但是 “-x + x” 不是，因为它使用了否定运算符 我们希望编写一个能使表达式等于给定的目标值 target 且运算符最少的表达式 返回所用运算符的最少数量 测试链接 : https://leetcode.cn/problems/least-operators-to-express-number/ 给你一个只包含小写英文字母的字符串 s 。 每一次 操作 ，你可以选择 s 中两个 相邻 的字符，并将它们交换。 请你返回将 s 变成回文串的 最少操作次数 。 注意 ，输入数据会确保 s 一定能变成一个回文串。 测试链接 : https://leetcode.cn/problems/minimum-number-of-moves-to-make-palindrome/ 一条单向的铁路线上，火车站编号为1~n 每个火车站都有一个级别，最低为 1 级。 现有若干趟车次在这条线路上行驶， 每一趟都满足如下要求： 如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站x的都必须停靠。 (注意：起始站和终点站自然也算作事先已知需要停靠的站点） 现有 m 趟车次的运行情况（全部满足要求）， 试推算这n个火车站至少分为几个不同的级别。 测试链接 : https://www.luogu.com.cn/problem/P1983 第056节 2023年2月第1周流行算法题目解析 给你一个由 n 个正整数组成的数组 nums 你可以对数组的任意元素执行任意次数的两类操作 如果元素是 偶数 ，除以 2 例如，如果数组是 [1,2,3,4] 那么你可以对最后一个元素执行此操作使其变成 [1,2,3,2] 如果元素是 奇数 ，乘上 2 例如，如果数组是 [1,2,3,4] ，那么你可以对第一个元素执行此操作，使其变成 [2,2,3,4] 数组的 偏移量 是数组中任意两个元素之间的 最大差值 返回数组在执行某些操作之后可以拥有的 最小偏移量 测试链接 : https://leetcode.cn/problems/minimize-deviation-in-array/ 给定一个整数数组 A，你可以从某一起始索引出发，跳跃一定次数 在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃 而第 2、4、6... 次跳跃称为偶数跳跃 你可以按以下方式从索引 i 向后跳转到索引 j（其中 i < j）： 在进行奇数跳跃时（如，第 1，3，5... 次跳跃），你将会跳到索引 j 使得 A[i] <= A[j]，A[j] 是可能的最小值。如果存在多个这样的索引 j 你只能跳到满足要求的最小索引 j 上。 在进行偶数跳跃时（如，第 2，4，6... 次跳跃） 你将会跳到索引 j，使得 A[i] >= A[j]，A[j] 是可能的最大值 如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。 对于某些索引 i，可能无法进行合乎要求的跳跃 如果从某一索引开始跳跃一定次数（可能是 0 次或多次） 就可以到达数组的末尾（索引 A.length - 1） 那么该索引就会被认为是好的起始索引 返回好的起始索引的数量 测试链接 : https://leetcode.cn/problems/odd-even-jump/ 给定一个二进制数组 nums 和一个整数 k k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能，则返回 -1 子数组 是数组的 连续 部分。 测试链接 : https://leetcode.cn/problems/minimum-number-of-k-consecutive-bit-flips/ 一共有 4 种硬币。面值分别为c1、c2、c3、c4 一开始就给定了，就是这些面值不再改变 某人去商店买东西，去了 n 次， 每次都是一次查询： 这个人每次代的每种硬币的数量不一样，都记录在d数组中 1) d[i]表示他带了的i种面值的数量 2) 他要购买s价值的东西 返回每次有多少种购买方法 1 <= c1、c2、c3、c4、d[i]、s <= 10^5 1 <= n <= 1000 测试链接 : https://www.luogu.com.cn/problem/P1450 第057节 2023年2月第2周流行算法题目解析 你的音乐播放器里有 N 首不同的歌 在旅途中，你的旅伴想要听 L 首歌（不一定不同，即，允许歌曲重复 请你为她按如下规则创建一个播放列表 每首歌至少播放一次 一首歌只有在其他 K 首歌播放完之后才能再次播放 返回可以满足要求的播放列表的数量 由于答案可能非常大，请返回它模 10^9 + 7 的结果 测试链接 : https://leetcode.cn/problems/number-of-music-playlists/ 给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。 对位于 (row, col) 的每个结点而言， 其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 树的根结点位于 (0, 0) 。 二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点， 形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点， 则按结点的值从小到大进行排序。 返回二叉树的 垂序遍历 序列。 测试链接 : https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/ 给你一棵二叉树的根节点 root ，返回树的 最大宽度 。 树的 最大宽度 是所有层中最大的 宽度 。 每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。 将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点， 这些 null 节点也计入长度。 题目数据保证答案将会在 32 位 带符号整数范围内。 测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/ 给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示 在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。 一些节点 initial 最初被恶意软件感染。只要两个节点直接连接， 且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。 这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。 假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。 我们可以从 initial 中删除一个节点， 并完全移除该节点以及从该节点到任何其他节点的任何连接。 请返回移除后能够使 M(initial) 最小化的节点。 如果有多个节点满足条件，返回索引 最小的节点 。 initial 中每个整数都不同 测试链接 : https://leetcode.cn/problems/minimize-malware-spread-ii/ 第058节 2023年2月第3周流行算法题目解析 如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。 现在，给定两个正整数 L 和 R （以字符串形式表示）， 返回包含在范围 [L, R] 中的超级回文数的数目。 测试链接 : https://leetcode.cn/problems/super-palindromes/ 我们从二叉树的根节点 root 开始进行深度优先搜索。 在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度） 然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1 根节点的深度为 0 如果节点只有一个子节点，那么保证该子节点为左子节点 给出遍历输出 S，还原树并返回其根节点 root。 测试链接 : https://leetcode.cn/problems/recover-a-tree-from-preorder-traversal/ 给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。 所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。 请你返回「表现良好时间段」的最大长度。 测试链接 : https://leetcode.cn/problems/longest-well-performing-interval/ 来自TikTok美国笔试 给定一个长度为N的一维数组scores, 代表0~N-1号员工的初始得分 scores[i] = a, 表示i号员工一开始得分是a 给定一个长度为M的二维数组operations, operations[i] = {a, b, c} 表示第i号操作为 : 如果a==1, 表示将目前分数 1并且m > 1 每段绳子的长度记为 k[0],k[1]...k[m - 1] 请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少 例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18 答案需要取模1000000007 测试链接 : https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/ 在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态 给你一个由灯的位置组成的二维数组 lamps 其中 lamps[i] = [rowi, coli] 表示 打开 位于 grid[rowi][coli] 的灯 即便同一盏灯可能在 lamps 中多次列出，不会影响这盏灯处于 打开 状态 当一盏灯处于打开状态，它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 另给你一个二维数组 queries ，其中 queries[j] = [rowj, colj] 对于第 j 个查询，如果单元格 [rowj, colj] 是被照亮的 则查询结果为 1 ，否则为 0 。在第 j 次查询之后 [按照查询的顺序] 关闭 位于单元格 grid[rowj][colj] 上 及相邻 8 个方向上（与单元格 grid[rowi][coli] 共享角或边）的任何灯 返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果 1 表示照亮，0 表示未照亮 测试链接 : https://leetcode.cn/problems/grid-illumination/ 你想要用小写字母组成一个目标字符串 target。 开始的时候，序列由 target.length 个 '?' 记号组成 而你有一个小写字母印章 stamp。 在每个回合，你可以将印章放在序列上，并将序列中的每个字母替换为印章上的相应字母 你最多可以进行 10 * target.length 个回合 举个例子，如果初始序列为 "?????"，而你的印章 stamp 是 "abc" 那么在第一回合，你可以得到 "abc??"、"?abc?"、"??abc" （请注意，印章必须完全包含在序列的边界内才能盖下去。） 如果可以印出序列，那么返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成 如果不能印出序列，就返回一个空数组。 例如，如果序列是 "ababc"，印章是 "abc" 那么我们就可以返回与操作 "?????" -> "abc??" -> "ababc" 相对应的答案 [0, 2] 另外，如果可以印出序列，那么需要保证可以在 10 * target.length 个回合内完成 任何超过此数字的答案将不被接受 测试链接 : https://leetcode.cn/problems/stamping-the-sequence/ 给你一个 rows * cols 大小的矩形披萨和一个整数 k 矩形包含两种字符： 'A' （表示苹果）和 '.' （表示空白格子） 你需要切披萨 k-1 次，得到 k 块披萨并送给别人 切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置 将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人 如果水平地切，那么需要把上面的部分送给一个人 在切完最后一刀后，需要把剩下来的一块送给最后一个人 请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数 由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果 测试链接 : https://leetcode.cn/problems/number-of-ways-of-cutting-a-pizza/ 第060节 2023年3月第1周流行算法题目解析 来自学员问题 给定一个1~N的排列，每次将相邻两数相加，可以得到新的序列，长度是N-1 再对新的序列，每次将相邻两数相加，可以得到新的序列，长度是N-2 这样下去可以最终只剩一个数字 比如 : 3 1 2 4 4 3 6 7 9 16 现在如果知道N，和最后的数字sum，反推最原始的序列是什么 如果有多个答案，返回字典序最小的那个 字典序看做所有数字拼起来的字符串字典序 比如 1, 10, 2... 拼起来是 1102... 1, 2, 3, 4... 拼起来是 1234... 认为 1, 10, 2...的字典序更小 如果给定的n和sum，有答案，返回一个N长度的答案数组 如果给定的n和sum，无答案，返回一个1长度的数组{ -1 } 输入 : N = 4, sum = 16 输出 : 3 1 2 4 输入 : N = 10, sum = 4116 输出 : 1 3 5 7 10 9 8 6 4 2 0 < n <= 10, sum随意 来自学员问题，国外算法面经帖子上的题 给定一个数组A, 把它分成两个数组B和C 对于数组A每个i位置的数来说， A[i] = B[i] + C[i] 也就是一个数字分成两份，然后各自进入B和C 要求B[i], C[i] >= 1 最终B数组要求从左到右不能降序 最终C数组要求从左到右不能升序 比如 A = { 5, 4, 5 } 可以分成 B = { 2, 2, 3 } C = { 3, 2, 2 } 这是一种有效的划分 返回有多少种有效的划分方式 1 <= A的长度 <= 10^7 1 <= A[i] <= 10^7 最终结果可能很大，请返回对1000000007取余的结果 HH有一串由各种漂亮的贝壳组成的项链 HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳， 思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。 有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？ 这个问题很难回答... 因为项链实在是太长了 于是，他只好求助睿智的你，来解决这个问题 测试链接 : https://www.luogu.com.cn/problem/P1972 请同学们务必参考如下代码中关于输入、输出的处理 这是输入输出处理效率很高的写法 提交以下所有代码，把主类名改成Main 洛谷对java太不友好了，大量时间不是消耗在算法本身上，而是耗在了IO上 多提交几次能全通过 主席树详解 测试链接 : https://www.luogu.com.cn/problem/P3834 请同学们务必参考如下代码中关于输入、输出的处理 这是输入输出处理效率很高的写法 提交以下所有代码，把主类名改成Main，可以通过 第061节 2023年3月第2周流行算法题目解析 爱丽丝和鲍勃继续他们的石子游戏 许多堆石子 排成一行，每堆都有正整数颗石子 piles[i] 游戏以谁手中的石子最多来决出胜负。 爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。 在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M 然后，令 M = max(M, X)。 游戏一直持续到所有石子都被拿走。 假设爱丽丝和鲍勃都发挥出最佳水平 返回爱丽丝可以得到的最大数量的石头。 测试链接 : https://leetcode.cn/problems/stone-game-ii/ 给出两个字符串 str1 和 str2 返回同时以 str1 和 str2 作为子序列的最短字符串 如果答案不止一个，则可以返回满足条件的任意一个答案。 测试链接 : https://leetcode.cn/problems/shortest-common-supersequence/ 体系学习班，最长公共子序列问题 大厂刷题班，章节11，根据动态规划表，生成路径 来自学员问题 给定N、M两个参数 一共有N个格子，每个格子可以涂上一种颜色，颜色在M种里选 当涂满N个格子，并且M种颜色都使用了，叫一种有效方法 求一共有多少种有效方法 1 <= N, M <= 5000 返回结果比较大，请把结果 % 1000000007 之后返回 给定正整数 n 返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。 测试链接 : https://leetcode.cn/problems/numbers-with-repeated-digits/ 如果你熟悉 Shell 编程，那么一定了解过花括号展开，它可以用来生成任意字符串。 花括号展开的表达式可以看作一个由 花括号、逗号 和 小写英文字母 组成的字符串 定义下面几条语法规则： 如果只给出单一的元素 x，那么表达式表示的字符串就只有 "x"。R(x) = {x} 例如，表达式 "a" 表示字符串 "a"。 而表达式 "w" 就表示字符串 "w"。 当两个或多个表达式并列，以逗号分隔，我们取这些表达式中元素的并集 R({e_1,e_2,...}) = R(e_1) ∪ R(e_2) ∪ ... 例如，表达式 "{a,b,c}" 表示字符串 "a","b","c"。 而表达式 "{{a,b},{b,c}}" 也可以表示字符串 "a","b","c"。 要是两个或多个表达式相接，中间没有隔开时， 我们从这些表达式中各取一个元素依次连接形成字符串 R(e_1 + e_2) = {a + b for (a, b) in R(e_1) × R(e_2)} 例如，表达式 "{a,b}{c,d}" 表示字符串 "ac","ad","bc","bd"。 表达式之间允许嵌套，单一元素与表达式的连接也是允许的。 例如，表达式 "a{b,c,d}" 表示字符串 "ab","ac","ad"​​​​​​。 例如，表达式 "a{b,c}{d,e}f{g,h}" 可以表示字符串 : "abdfg", "abdfh", "abefg", "abefh", "acdfg", "acdfh", "acefg", "acefh"。 给出表示基于给定语法规则的表达式 expression 返回它所表示的所有字符串组成的有序列表。 测试链接 : https://leetcode.cn/problems/brace-expansion-ii/ 第062节 2023年3月第3周流行算法题目解析 给你一个 非递减 的正整数数组 nums 和整数 K 判断该数组是否可以被分成一个或几个 长度至少 为 K 的 不相交的递增子序列 测试链接 : https://leetcode.cn/problems/divide-array-into-increasing-sequences/ 来自学员问题 真实大厂笔试题 给定一个数组arr，长度为n 再给定一个数字k，表示一定要将arr划分成k个集合 每个数字只能进一个集合 返回每个集合内部的平均值都累加起来最小的值 平均值向下取整 1 <= n <= 10^5 0 <= arr[i] <= 10^5 1 <= k <= n 给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空） 使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。 请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。 子数组 定义为原数组中连续的一组元素。 测试链接 : https://leetcode.cn/problems/make-sum-divisible-by-p/ 布尔表达式 是计算结果不是 true 就是 false 的表达式 有效的表达式需遵循以下约定： 't'，运算结果为 true 'f'，运算结果为 false '!(subExpr)'，运算过程为对内部表达式 subExpr 进行 逻辑非（NOT）运算 '&(subExpr1, subExpr2, ..., subExprn)' 运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, ..., subExprn 进行 逻辑与（AND）运算 '|(subExpr1, subExpr2, ..., subExprn)' 运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, ..., subExprn 进行 逻辑或（OR）运算 给你一个以字符串形式表述的 布尔表达式 expression，返回该式的运算结果。 题目测试用例所给出的表达式均为有效的布尔表达式，遵循上述约定。 测试链接 : https://leetcode.cn/problems/parsing-a-boolean-expression/ 来自学员问题，大厂笔试面经帖子 假设一共有M个车库，编号1~M，时间点从早到晚是从1~T 一共有N个记录，每一条记录如下{a, b, c} 表示一辆车在b时间点进入a车库，在c时间点从a车库出去 一共有K个查询，每个查询只有一个数字X，表示请问在X时刻， 有多少个车库包含车的数量>=3，请返回K个查询的答案 1 <= M, N, K <= 10^5 1 <= T <= 10^9 第063节 2023年3月第4周流行算法题目解析 来自学员问题 一共有n个项目，每个项目都有两个信息 projects[i] = {a, b} 表示i号项目做完要a天，但是当你投入b个资源，它就会缩短1天的时间 你一共有k个资源，你的目标是完成所有的项目，但是希望总天数尽可能缩短 在所有项目同时开工的情况下，返回尽可能少的天数 1 <= n <= 10^5 1 <= k <= 10^7 来自华为 给你 n 个任务和 m 个工人 每个任务需要一定的力量值才能完成 需要的力量值保存在下标从 0 开始的整数数组 tasks 中 第 i 个任务需要 tasks[i] 的力量才能完成 每个工人的力量值保存在下标从 0 开始的整数数组 workers 中 第 j 个工人的力量值为 workers[j] 每个工人只能完成 一个 任务 且力量值需要 大于等于 该任务的力量要求值, 即 workers[j] >= tasks[i] 除此以外，你还有 pills 个神奇药丸 可以给 一个工人的力量值 增加 strength 你可以决定给哪些工人使用药丸 但每个工人 最多 只能使用 一片 药丸 给你下标从 0 开始的整数数组tasks 和 workers 以及 两个整数 pills 和 strength ，请你返回 最多 有多少个任务可以被完成。 测试链接 : https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/ 你驾驶出租车行驶在一条有 n 个地点的路上 这 n 个地点从近到远编号为 1 到 n ，你想要从 1 开到 n 通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向 乘客信息用一个下标从 0 开始的二维数组 rides 表示 其中 rides[i] = [starti, endi, tipi] 表示第 i 位乘客需要从地点 starti 前往 endi 愿意支付 tipi 元的小费 每一位 你选择接单的乘客 i ，你可以 盈利 endi - starti + tipi 元 你同时 最多 只能接一个订单。 给你 n 和 rides ，请你返回在最优接单方案下，你能盈利 最多 多少元。 注意：你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。 测试链接 : https://leetcode.cn/problems/maximum-earnings-from-taxi/ 最长可整合子数组的长度 数组中的数字排序之后，相邻两数的差值是1 这种数组就叫可整合数组 给定一个数组，求最长可整合子数组的长度 给你一个由数字组成的字符串 s，返回 s 中独特子字符串数量 其中的每一个数字出现的频率都相同。 测试链接 : https://leetcode.cn/problems/unique-substrings-with-equal-digit-frequency/ 第064节 2023年3月第5周流行算法题目解析 来自百度 用r、e、d三种字符，拼出一个回文子串数量等于x的字符串 1 <= x <= 10^5 来自腾讯音乐 给定一棵树，一共有n个点 每个点上没有值，请把1~n这些数字，不重复的分配到二叉树上 做到 : 奇数层节点的值总和 与 偶数层节点的值总和 相差不超过1 返回奇数层节点分配值的一个方案 2 <= n <= 10^5 来自小红书、字节跳动 村里面一共有 n 栋房子 我们希望通过建造水井和铺设管道来为所有房子供水。 对于每个房子 i，我们有两种可选的供水方案： 一种是直接在房子内建造水井 成本为 wells[i - 1] （注意 -1 ，因为 索引从0开始 ） 另一种是从另一口井铺设管道引水 数组 pipes 给出了在房子间铺设管道的成本 其中每个 pipes[j] = [house1j, house2j, costj] 代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。 请返回 为所有房子都供水的最低总成本 。 这道题很高频，引起注意 本身也不难，转化一下变成最小生成树的问题即可 测试链接 : https://leetcode.cn/problems/optimize-water-distribution-in-a-village/ 来自学员问题，蓝桥杯练习题 小青蛙住在一条河边, 它想到河对岸的学校去学习 小青蛙打算经过河里 的石头跳到对岸 河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上 给定一个长度为n的数组arr，表示每块儿石头的高度数值 每块石头有一个高度, 每次小青蛙从一块石头起跳 这块石头的高度就会下降1, 当石头的高度下降到0时 小青蛙不能再跳到这块石头上(跳跃后使石头高度下降到0是允许的) 小青蛙一共需要去学校上x天课, 所以它需要往返x次(去x次，回x次) 当小青蛙具有 一个跳跃能力y时, 它能跳不超过y的距离 请问小青蛙的跳跃能力至少是多少才能用这些石头上完x次课 1 <= n <= 10^5 1 <= arr[i] <= 10^4 1 <= x <= 10^9 测试链接 : https://www.luogu.com.cn/problem/P8775 来自谷歌 给你一棵 n 个节点的树（连通无向无环的图） 节点编号从 0 到 n - 1 且恰好有 n - 1 条边 给你一个长度为 n 下标从 0 开始的整数数组 vals 分别表示每个节点的值 同时给你一个二维整数数组 edges 其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边 一条 好路径 需要满足以下条件： 开始节点和结束节点的值 相同 。 开始节点和结束节点中间的所有节点值都 小于等于 开始节点的值 也就是说开始节点的值应该是路径上所有节点的最大值 请你返回不同好路径的数目 注意，一条路径和它反向的路径算作 同一 路径 比方说， 0 -> 1 与 1 -> 0 视为同一条路径。单个节点也视为一条合法路径 测试链接 : https://leetcode.cn/problems/number-of-good-paths/ 第065节 2023年4月第2周流行算法题目解析 来自学员问题，来自真实笔试 景区里有m个项目，也就是项目数组为int[][] game，这是一个m*2的二维数组 景区的第i个项目有如下两个参数： game[i] = { Ki, Bi } Ki一定是负数，Bi一定是正数 举个例子 : Ki = -2, Bi = 10 如果只有1个人买票，单张门票的价格为 : Ki * 1 + Bi = 8 所以这1个人游玩该项目要花8元 如果有2个人买票，单张门票的价格为 : Ki * 2 + Bi = 6 所以这2个人游玩该项目要花6 * 2 = 12元 如果有5个人买票，单张门票的价格为 : Ki * 2 + Bi = 0 所以这5个人游玩该项目要花0 * 5 = 0元 如果有更多人买票，都认为花0元(因为你让项目倒贴钱实在是太操蛋了) 于是可以认为，如果有x个人买票，单张门票的价格为 : Ki * x + Bi x个人游玩这个项目的总花费是 : max { (Ki * x + Bi) * x , 0 } 你作为领导，单位一共有n个人，每个人最多可以选1个项目来游玩，也可以不选任何项目 所有员工将在明晚提交选择，然后由你去按照上面的规则，统一花钱，统一购票 但是现在，你想知道自己需要准备多少钱，就可以应付可能的各种情况， 支持各种可能下的开销，返回这个最保险的钱数 数据量描述 : 1 <= N、M、Bi <= 10^5 -(10^5) <= Ki < 0 来自小红书 实验室需要配制一种溶液，现在研究员面前有n种该物质的溶液， 每一种有无限多瓶，第i种的溶液体积为v[i]，里面含有w[i]单位的该物质 研究员每次可以选择一瓶溶液， 将其倒入另外一瓶（假设瓶子的容量无限），即可以看作将两个瓶子内的溶液合并 此时合并的溶液体积和物质含量都等于之前两个瓶子内的之和。 特别地，如果瓶子A与B的溶液体积相同，那么A与B合并之后 该物质的含量会产生化学反应，使得该物质含量增加x单位 研究员的任务是配制溶液体积恰好等于c的，且尽量浓的溶液(即物质含量尽量多） 研究员想要知道物质含量最多是多少 对于所有数据，1 <= n, v[i], w[i], x, c <= 1000 来自谷歌、亚马逊、微软、蔚来、腾讯、字节跳动、Uber 给出两个长度相同的字符串 str1 和 str2 请你帮忙判断字符串 str1 能不能在 零次 或 多次 转化 后变成字符串 str2 每一次转化时，你可以将 str1 中出现的 所有 相同字母变成其他 任何 小写英文字母 只有在字符串 str1 能够通过上述方式顺利转化为字符串 str2 时才能返回 true 。​​ 测试链接 : https://leetcode.cn/problems/string-transforms-into-another-string/ 来自Indeed、谷歌、亚马逊、领英、英伟达 一个坐标可以从 -infinity 延伸到 +infinity 的 无限大的 棋盘上 你的 骑士 驻扎在坐标为 [0, 0] 的方格里。 骑士的走法和中国象棋中的马相似，走 “日” 字： 即先向左（或右）走 1 格，再向上（或下）走 2 格 或先向左（或右）走 2 格，再向上（或下）走 1 格 每次移动，他都可以像中国象棋中的马一样，选八个方向中的一个前进 返回 骑士前去征服坐标为 [x, y] 的部落所需的最小移动次数 本题确保答案是一定存在的。 测试链接 : https://leetcode.cn/problems/minimum-knight-moves/ 来自小红书、谷歌、Bloomberg、微软、亚马逊、字节跳动、摩根大通、Uber 你会得到一个字符串 text 你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk) 要求满足: subtexti 是 非空 字符串 所有子字符串的连接等于 text ( 即subtext1 + subtext2 + ... + subtextk == text ) subtexti == subtextk - i + 1 表示所有 i 的有效值( 即 1 <= i <= k ) 返回k可能最大值。 测试链接 : https://leetcode.cn/problems/longest-chunked-palindrome-decomposition/ 第066节 2023年4月第3周流行算法题目解析 来自华为OD 完美走位问题 给定一个由'W'、'A'、'S'、'D'四种字符组成的字符串，长度一定是4的倍数 你可以把任意连续的一段子串，变成'W'、'A'、'S'、'D'组成的随意状态 目的是让4种字符词频一样 返回需要修改的最短子串长度 找到了出处，是leetcode原题 测试链接 : https://leetcode.cn/problems/replace-the-substring-for-balanced-string/ 来自腾讯笔试 给定一个长度为N的正数数组，还有一个正数K 返回有多少子序列的最大公约数为K 结果可能很大，对1000000007取模 原题目简单转化就是如下的题目 测试链接 : https://www.luogu.com.cn/problem/CF803F 所以课上会讲怎么转化，然后就是讲测试链接里的题目 1 <= N <= 10^5 1 <= arr[i] <= 10^5 (上课时网络卡顿，将在下节课安排重讲) 来自学员问题，蓝桥杯练习题 给定一个长度为n的数组arr 现在你有一次机会, 将其中连续的K个数全修改成任意一个值 请你计算如何修改可以使修改后的数 列的最长不下降子序列最长 请输出这个最长的长度。 最长不下降子序列:子序列中的每个数不小于在它之前的数 1 <= k, n <= 10^5 1 <= arr[i] <= 10^6 测试链接 : https://www.luogu.com.cn/problem/P8776 第067节 2023年4月第4周流行算法题目解析 (因为上节课网络卡顿，所以这节课安排重讲) 来自学员问题，蓝桥杯练习题 给定一个长度为n的数组arr 现在你有一次机会, 将其中连续的K个数全修改成任意一个值 请你计算如何修改可以使修改后的数 列的最长不下降子序列最长 请输出这个最长的长度。 最长不下降子序列:子序列中的每个数不小于在它之前的数 1 <= k, n <= 10^5 1 <= arr[i] <= 10^6 测试链接 : https://www.luogu.com.cn/problem/P8776 开心一下的智力题 : 有一个村庄，一共250人 每一个村民要么一定说谎，要么只说真话 村里有A、B、C、D四个球队，且每个村民只会喜欢其中的一支球队 但是说谎者会不告知真实喜好，而且会说是另外三支球队的支持者（全支持另外三支球队） 访问所有的村民之后，得到的访谈结果如下 : A的支持者有90 B的支持者有100 C的支持者有80 D的支持者有80 问村里有多少个说谎者 下面是正式题 : 你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ， 其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。 假设将多边形 剖分 为 n - 2 个三角形。 对于每个三角形，该三角形的值是顶点标记的乘积， 三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。 返回 多边形进行三角剖分后可以得到的最低分 。 测试链接 : https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/ 给你一个正整数数组nums, 同时给你一个长度为 m 的整数数组 queries 第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作 任意 次： 将数组里一个元素 增大 或者 减小 1 。请你返回一个长度为 m 的数组 answer ， 其中 answer[i]是将 nums 中所有元素变成 queries[i] 的 最少 操作次数。 注意，每次查询后，数组变回最开始的值。 测试链接 : https://leetcode.cn/problems/minimum-operations-to-make-all-array-elements-equal/ 来自微众银行 两个魔法卷轴问题 给定一个数组arr，其中可能有正、负、0， 一个魔法卷轴可以把arr中连续的一段全变成0，你希望数组整体的累加和尽可能大 你有两个魔法卷轴，请返回数组尽可能大的累加和 1 <= arr长度 <= 100000 -100000 <= arr里的值 <= 100000 来自微众银行 给出两个长度均为n的数组 A = { a1, a2, ... ,an } B = { b1, b2, ... ,bn }。 你需要求出其有多少个区间[L,R]满足: 数组A中下标在[L,R]中的元素之和在[La,Ra]之中 数组B中下标在[L,R]中的元素之和在[Lb,Rb]之中 输入 第一行有一个正整数N(1<=N<=100000)，代表两个数组的长度。 第二行有N个非负整数，范围在0到1000000000之间，代表数组中的元素。 第三行有N个非负整数，范围在0到1000000000之间，代表数组中的元素。 第四行有4个整数La,Ra,Lb,Rb，范围在0到10^18之间，代表题目描述中的参数。 输出 输出一个整数，代表所求的答案 给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ， 其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。 再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ， 1 表示节点 i 处有一个金币。 一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次： 收集距离当前节点距离为 2 以内的所有金币，或者 移动到树中一个相邻节点。 你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。 如果你多次经过一条边，每一次经过都会给答案加一。 测试链接 : https://leetcode.cn/problems/collect-coins-in-a-tree/ 第068节 2023年5月第2周流行算法题目解析 来自华为OD，学员问题 一个图像有n个像素点，存储在一个长度为n的数组arr里， 每个像素点的取值范围[0,s]的整数 请你给图像每个像素点值加上一个整数k（可以是负数） 像素值会自动截取到[0,s]范围， 当像素值<0，会更改为0，当新像素值>s，会更改为s 这样就可以得到新的arr，想让所有像素点的平均值最接近中位值s/2, 向下取整 请输出这个整数k, 如有多个整数k都满足, 输出小的那个 1 <= n <= 10^6 1 <= s <= 10^18 来自学员问题，来自真实笔试 塔子哥最近在处理一些字符串相关的任务 他喜欢 R 字符，因为在某些任务中，这个字符通常表示“正确”的结果 另一方面，他不喜欢 B 字符，因为在某些任务中，这个字符通常表示“错误”的结果 为了解决他的任务，塔子哥定义了字符串的权值为字符串中 R 字符的出现次数 例如，对于字符串 BBRBRB，它的权值为 2，因为其中有 2 个 R 字符 现在，塔子哥面临一个问题，他有一个长度为 n 的字符串 s，它仅由 R 和 B 组成 他想知道，长度为 n 的仅由 R 和 B组成的字符串中， 字典序不小于 s 的字符串的权值之和是多少？ 因此，他需要编写一个程序来解决这个问题 输入第一行为一个整数 n ，表示字符串的长度 输入第二行为一个长度为 n 的字符串 s ，字符串中元素组成仅为 R 和 B 输出一个整数，代表长度为 n 的、字典序不小于 s 的字符串权值之和 输入样例： 3 RBR 输出： 7 解释：共有 3 个字符串字典序大于等于"RBR"，RBR权值为2，RRB为2，RRR为3 1 <= n <= 100000 结果可能很大，对1000000007取模 帖子链接 : https://www.mashibing.com/question/detail/67223 作为项目经理，你规划了一份需求的技能清单 req_skills， 并打算从备选人员名单 people 中选出些人组成一个「必要团队」 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表 所谓「必要团队」，就是在这个团队中， 对于所需求的技能列表 req_skills 中列出的每项技能， 团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员： 例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。 请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。 你可以按 任意顺序 返回答案，题目数据保证答案存在。 测试链接 : https://leetcode.cn/problems/smallest-sufficient-team/ 给定一个整数数组 nums 和一个正整数 k， 找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。 测试链接 : https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/ 给你一个整数 n 和一个在范围 [0, n - 1] 以内的整数 p ， 它们表示一个长度为 n 且下标从 0 开始的数组 arr ， 数组中除了下标为 p 处是 1 以外，其他所有数都是 0 。 同时给你一个整数数组 banned ，它包含数组中的一些位置。 banned 中第 i 个位置表示 arr[banned[i]] = 0 ，题目保证 banned[i] != p 。 你可以对 arr 进行 若干次 操作。一次操作中，你选择大小为 k 的一个 子数组 并将它 翻转 。在任何一次翻转操作后， 你都需要确保 arr 中唯一的 1 不会到达任何 banned 中的位置。 换句话说，arr[banned[i]] 始终 保持 0 。 请你返回一个数组 ans ，对于 [0, n - 1] 之间的任意下标 i ， ans[i] 是将 1 放到位置 i 处的 最少 翻转操作次数， 如果无法放到位置 i 处，此数为 -1 。 子数组 指的是一个数组里一段连续 非空 的元素序列。 对于所有的 i ，ans[i] 相互之间独立计算。 将一个数组中的元素 翻转 指的是将数组中的值变成 相反顺序 。 测试链接 : https://leetcode.cn/problems/minimum-reverse-operations/ 第069节 2023年5月第3周流行算法题目解析 保证一定是n*n的正方形，实现从里到外转圈打印的功能 如果n是奇数，中心点唯一，比如 a b c d e f g h i e是中心点，依次打印 : e f i h g d a b c 如果n是偶数，中心点为最里层2*2的右下点 比如 a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9 最里层是 o p u v v是中心点，依次打印 : v u o p q w .... 来自学员问题 假设每一次获得随机数的时候，这个数字大于100的概率是P 尝试N次，其中大于100的次数在A次~B次之间的概率是多少? 0 < P < 1, P是double类型 1 <= A <= B <= N <= 100 在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始 并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0) 右下单元格是 (n - 1, n - 1)，象棋骑士有8种可能的走法 每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格，类似马走日 每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。 骑士继续移动，直到它走了 k 步或离开了棋盘 返回 骑士在棋盘停止移动后仍留在棋盘上的概率 测试链接 : https://leetcode.cn/problems/knight-probability-in-chessboard/ 来自小红书 给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 每一次移动，你可以选择 相邻 两个数字并将它们交换 请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数 测试链接 : https://leetcode.cn/problems/minimum-adjacent-swaps-for-k-consecutive-ones/ 现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号 给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ， 其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。 每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。 给定路径的 价格总和 是该路径上所有节点的价格之和。 另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示 从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。 在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。 返回执行所有旅行的最小价格总和。 测试链接 : https://leetcode.cn/problems/minimize-the-total-price-of-the-trips/ 第070节 2023年5月第4周流行算法题目解析 先来一个智力题，来自美团面试题 给定n个二维坐标，表示在二维平面的n个点， 坐标为double类型，精度最多小数点后两位 希望在二维平面上画一个圆，圈住其中的k个点，其他的n-k个点都要在圆外 返回一个圆心和半径，表示哪个圆可以圈住其中的k个点 坐标和半径都是double类型，最多保留小数点后两位 下面是正式题目 给你一个整数数组 arr 和一个整数 k 现需要从数组中恰好移除 k 个元素 请找出移除后数组中不同整数的最少数目 测试链接 : https://leetcode.cn/problems/least-number-of-unique-integers-after-k-removals/ 来自华为 一个数字n，一定要分成k份 得到的乘积尽量大是多少 数字n和k，可能非常大，到达10^12规模 结果可能更大，所以返回结果对1000000007取模 来自美团 给定 pushed 和 popped 两个序列，每个序列中的 值都不重复， 只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时， 返回 true；否则，返回 false 。 测试链接 : https://leetcode.cn/problems/validate-stack-sequences/ 来自招商银行 给定一个数组arr，长度为n，表示有0~n-1号设备 arr[i]表示i号设备的型号，型号的种类从0~k-1，一共k种型号 给定一个k*k的矩阵map，来表示型号之间的兼容情况 map[a][b] == 1，表示a型号兼容b型号 map[a][b] == 0，表示a型号不兼容b型号 兼容关系是有向图，也就是a型号兼容b型号，不代表b型号同时兼容a型号 如果i设备的型号兼容j设备的型号，那么可以从i设备修建一条去往j设备的线路 修建线路的代价是i设备到j设备的距离：|i-j| 你的目标是从0号设备到达n-1号设备，并不一定每个设备都联通，只需要到达即可 返回最小的修建代价，如果就是无法到达返回-1 1 <= n <= 1000 1 <= k <= 50 来自招商银行 这个题是个破题，但这可能是经常遇到的一种题， 讲一下思路即可，没有必要投入大多时间给这种题目 一共有三个服务A、B、C，网络延时分别为a、b、c 并且一定有：1 <= a <= b <= c <= 10^9 但是具体的延时数字丢失了，只有单次调用的时间 一次调用不可能重复使用相同的服务， 一次调用可能使用了三个服务中的某1个、某2个或者全部3个服务 比如一个调用的时间，T = 100 100的延时可能来自以下7种情况： a = 100，这次调用可能单独使用了A b = 100，这次调用可能单独使用了B c = 100，这次调用可能单独使用了C a + b = 100，这次调用可能组合使用了A、B a + c = 100，这次调用可能组合使用了A、C b + c = 100，这次调用可能组合使用了B、C a + b + c = 100，这次调用可能组合使用了A、B、C全部服务 那么可想而知，如果给的调用时间足够多，是可以猜测出a、b、c的 给定一个数组times，长度为n，并且一定有4 <= n <= 7 times[i] = s，表示i号调用用时s，而且times中一定都是正数且没有重复值 请根据n次调用，猜测出a、b、c三元组可能的情况数 如果任何a、b、c都无法匹配上给定的调用耗时，返回0 测试的次数T <= 100 也就是说，一共最多给定100个数组，每一次让你返回a、b、c三元组可能的情况数 来自招商银行 原始题目描述 假如某公司目前推出了N个在售的金融产品(1<=N<=100) 对于张三，用ai表示他购买了ai(0<=ai<=10^4)份额的第i个产品(1<=i<=N) 现给出K(1<=K<=N)个方案，通过这些方案，能够支持将多个不同的产品进行整合 (也可以对单个产品进行优化)形成新的产品。 新的产品形成后，若用户持有了组成新产品所需的全部的原产品份额， 则能够将用户持有的原产品份额转换为新产品的份额，各原产品份额与新产品份额比例均为1:1 我们保证对于每个产品最多存在一个方案使用旧产品整合成该产品 并且根据方案产出的新产品的产品编号均大于各旧产品的产品编号 现计划根据这些方案，帮助部分愿意升级到最新产品的用户对产品进行升级 请协助工作人员计算当前用户能够转换出的最新产品份额的最大值 输入描述 第一行包含整数N，第二行包含N个整数ai，第三行包含整数K 接下来的K行，每一行代表一个方案，每一行包含整数1和M(M>=1) L为该方案产生的新产品的编号，M代表方案所需原产品个数 接下来的M个整数代表了该方案所需的每个原产品的个数 输出描述 根据日前的份额和给出的方案，经过若干次转换，输出当前用户能够得到产品N的份额最大值 举例 输入: 5 2 0 0 1 0 3 5 2 3 4 2 1 1 3 1 2 输出: 1 解释: 第一步将1份1产品转化为1份2产品 第二步将1份2产品转化为1份3产品 第三步将1份3产品和1份4产品，转成为1份5产品 然后不能得到更多的5产品了，所以返回1 实在是太困惑了，上文说的意思可谓不做人，那么我们改写一下意思，变得好理解 如下是改写后的题目描述 给定一个数组arr，长度为n，产品编号从0~n-1 arr[i]代表初始时i号产品有多少份 存在一系列的产品转化方案的数组convert，长度为k，代表k个方案 比如具体某一个方案，convert[j] = {a, b, c, d, ...} 表示当前的j号方案转化出来的产品是a，转化1份a需要：1份b、1份c、1份d... 其中a、b、c、d...一定都在0~n-1范围内 并且题目保证a > Math.max(b, c, d, ....) 而且题目保证所有方案转化出来的产品编号一定是不重复的 请返回最终能得到的第n-1号商品的最大值 1 <= n <= 100 0 <= arr[i] <= 10^4 k < n 第071节 2023年5月第5周流行算法题目解析 来自字节 给定一个n*m的二维矩阵，每个位置都是字符 U、D、L、R表示传送带的位置，会被传送到 : 上、下、左、右 . 、O分别表示空地、目标，一定只有一个目标点 可以在空地上选择上、下、左、右四个方向的一个 到达传送带的点会被强制移动到其指向的下一个位置 如果越界直接结束，返回有几个点可以到达O点 来自学员问题 沿街有一排连续的房屋。每间房屋内都藏有一定的现金 现在有一位小偷计划从这些房屋中窃取现金 由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 给你一个整数数组 nums 表示每间房屋存放的现金金额 形式上，从左起第 i 间房屋中放有 nums[i] 美元 另给你一个整数 k ，表示窃贼将会窃取的最少房屋数 小偷一定要要窃取至少 k 间房屋，返回小偷的 最小 窃取能力 测试链接 : https://leetcode.cn/problems/house-robber-iv/ 来自华为OD 如果n = 1，打印 1*** 如果n = 2，打印 1*** 3*** 2*** 如果n = 3，打印 1*** 3*** 2*** 4*** 5*** 6*** 如果n = 4，打印 1*** 3*** 2*** 4*** 5*** 6*** 10** 9*** 8*** 7*** 输入一个数n，表示有多少行，从1开始输出， 奇数行输出奇数个数，奇数行正序，偶数行输出偶数个数，偶数行逆序 每个数后面加*补满四位，中间空4个，第n行顶格输出 字符串哈希原理和实现 字符串哈希+二分的例题 给定长为 n 的源串 s，以及长度为 m 的模式串 p， 要求查找源串中有多少子串与模式串匹配 s' 与 s 匹配，当且仅当 s' 与 s 长度相同，且最多有 k 个位置字符不同 其中 1 <= n, m <= 10^6，0 <= k <= 5 正方形矩阵哈希实现 二维哈希只适用于正方形的情况 如果想支持普通矩阵，需要更复杂度的过程，这里不做展开 如果一个正方形矩阵上下对称并且左右对称，对称的意思是互为镜像 那么称这个正方形矩阵叫做神奇矩阵 比如 : 1 5 5 1 6 3 3 6 6 3 3 6 1 5 5 1 这个正方形矩阵就是神奇矩阵 给定一个大矩阵n*m，返回其中神奇矩阵的数目 1 <= n,m <= 1000 测试链接 : https://www.luogu.com.cn/problem/P2601 第072节 2023年6月第2周流行算法题目解析 给你一个长度为 n 下标从 0 开始的整数数组 nums 它包含 1 到 n 的所有数字，请你返回上升四元组的数目。 如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的： 0 <= i < j < k < l < n 且 nums[i] < nums[k] < nums[j] < nums[l] 。 测试链接 : https://leetcode.cn/problems/count-increasing-quadruplets/ 来自华为od 给定一个数组arr，长度为n，表示n个格子的分数，并且这些格子首尾相连 孩子不能选相邻的格子，不能回头选，不能选超过一圈 但是孩子可以决定从任何位置开始选，也可以什么都不选 返回孩子能获得的最大分值 1 <= n <= 10^6 0 <= arr[i] <= 10^6 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次 需保证 返回结果的字典序最小 要求不能打乱其他字符的相对位置) 测试链接 : https://leetcode.cn/problems/remove-duplicate-letters/ 大厂刷题班讲过，不过那时没有讲出最优解，安排一下重讲 给你一个由 n 个数对组成的数对数组 pairs 其中 pairs[i] = [lefti, righti] 且 lefti < righti 。 现在，我们定义一种 跟随 关系，当且仅当 b < c 时 数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面 我们用这种形式来构造 数对链 找出并返回能够形成的 最长数对链的长度 你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。 测试链接 : https://leetcode.cn/problems/maximum-length-of-pair-chain/ 给你两个整数数组 arr1 和 arr2 返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。 每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引， 分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length， 然后进行赋值运算 arr1[i] = arr2[j]。如果无法让 arr1 严格递增，请返回 -1。 之前讲过这个题，能通过但不是最优解，所以我们直接补一个最优解 测试链接 : https://leetcode.cn/problems/make-array-strictly-increasing/ 第073节 2023年6月3周流行算法题目解析 课前放松一下 做一个令人不开心的实验 一开始有100个人，每个人都有100元 在每一轮都做如下的事情 : 每个人都必须拿出1元钱给除自己以外的其他人，给谁完全随机 如果某个人在这一轮的钱数为0，那么他可以不给，但是可以接收 发生很多很多轮之后，这100人的社会财富分布很均匀吗？ 来自字节 密码是一串长度为n的小写字母，一则关于密码的线索纸条 首先将字母a到z编号为0到25编号 纸条上共有n个整数ai，其中a1表示密码里第一个字母的编号 若i>1的话就表示第i个字母和第i-1个字母编号的差值 例如，a2就代表密码中第1个字母和第2个字母编号的差值 若密码是acb，那么纸条上的数字就是[0, 2, 1] 返回可能的密码的个数，由于结果可能很大， 输出对1000000007取模的结果 1 <= n <= 10^5 0 <= ai <= 25 来自字节 给定整数数组arr，求删除任一元素后， 新数组中长度为k的子数组累加和的最大值 来自字节 给定一个数组arr，长度为n，在其中要选两个不相交的子数组 两个子数组的累加和都要是T，返回所有满足情况中，两个子数组长度之和最小是多少 如果没有有效方法，返回-1 正式 : 2 <= n <= 10^6 0 <= arr[i] <= 10000 1 <= T <= 10^8 扩展 : 2 <= n <= 10^6 -10000 <= arr[i] <= 10000 1 <= T <= 10^8 都能时间复杂度做到O(N) 来自华为OD 一支n个士兵的军队正在趁夜色逃亡，途中遇到一条湍急的大河 敌军在T的时长后到达河面，没到过对岸的士兵都会被消灭 现在军队只找到了1只小船，这船最多能同时坐上2个士兵。 1) 当1个士兵划船过河，用时为a[i] 2) 当2个士兵坐船同时划船过河时, 用时为max(a[j],a[i])两士兵中用时最长的 3) 当2个士兵坐船只有1个士兵划船时, 用时为a[i] * 10, a[i]为划船士兵用时 请帮忙给出一种解决方案，保证存活的士兵最多，且过河用时最短 我们先看一下如下的题，再讲一下华为OD的扩展 测试链接 : https://www.luogu.com.cn/problem/P1809 有一个大晴天, Oliver与同学们一共N人出游, 他们走到一条河的东岸边，想要过河到西岸 而东岸边有一条小船。船太小了，一次只能乘坐两人，每个人都有一个渡河时间T 船划到对岸的时间等于船上渡河时间较长的人所用时间 现在已知N个人的渡河时间Ti Oliver 想要你告诉他，他们最少要花费多少时间，才能使所有人都过河 注意，只有船在东岸（西岸）的人才能坐上船划到对岸。 来自华为OD 1号店铺贿赂问题 店铺数量n，编号1~n 人的数量m，编号1~m 每个人有自己投票的店铺p，和改投1号店的报价x 返回想让1号店铺成为人气最高的店，至少花多少钱 1 <= p,n,m <= 3000 1 <= x <= 10^9 第074节 2023年6月4周流行算法题目解析 给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数 如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列 对于 0 <= i < n - 1 的下标 i 要么 nums[i] % nums[i+1] == 0 要么 nums[i+1] % nums[i] == 0 请你返回特别排列的总数目，由于答案可能很大，请将它对 1000000007 取余 后返回 测试链接 : https://leetcode.cn/problems/special-permutations/ 给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time 分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠 一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间 开销为 cost[i] 单位的钱。 一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 但是必须在付费油漆匠 工作 时，免费油漆匠才会工作 请你返回刷完 n 堵墙最少开销为多少 测试链接 : https://leetcode.cn/problems/painting-the-walls/ 来自华为社招笔试 在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧 在桥上有一些石子，青蛙很讨厌踩在这些石子上 由于桥的长度和青蛙一次跳过的距离都是正整数 我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0...L 其中L是桥的长度，坐标为 0 的点表示桥的起点，坐标为 L 的点表示桥的终点 青蛙从桥的起点开始，不停的向终点方向跳跃 一次跳跃的距离是 S 到 T 之间的任意正整数（包括S,T） 当青蛙跳到或跳过坐标为 L 的点时，就算青蛙已经跳出了独木桥。 题目给出独木桥的长度 L，青蛙跳跃的距离范围[S,T] 以及桥上石子的位置 你的任务是确定青蛙要想过河，最少需要踩到的石子数 测试链接 : https://www.luogu.com.cn/problem/P1052 欧拉路径问题 给你一个下标从 0 开始的二维整数数组 pairs 其中 pairs[i] = [starti, endi] 如果 pairs 的一个重新排列 满足对每一个下标 i （ 1 <= i < pairs.length ） 都有 endi-1 == starti ， 那么我们就认为这个重新排列是 pairs 的一个 合法重新排列 请你返回 任意一个 pairs 的合法重新排列 注意：数据保证至少存在一个 pairs 的合法重新排列 测试链接 : https://leetcode.cn/problems/valid-arrangement-of-pairs/ 第075节 2023年7月1周流行算法题目解析 先来一个最近国外同学考的题目 已知一些供应点的位置，一共n个供应点 其中有n-1个供应点一定都在x轴上，比如(15,0)位置，(2,0)位置等 只有1个供应点不在x轴上，比如(23,17)位置 给出每个供应点的位置，并且给定第k号供应点是出发点 要求每个供应点最多走过2次，返回从k点出发，走完所有供应点的最少距离 上面这个题没有代码实现 因为这个题就是彻底的业务分析，只有一系列的贪心设计，代码也不难写 同时这个题没有给出数据量，但是课上会讲O(n)的方法，所以也就无所谓了 以下是这节课的正式题，来自学员问题 现在有一个打怪类型的游戏，这个游戏是这样的，你有n个技能 每一个技能会有一个伤害， 同时若怪物小于等于一定的血量，则该技能可能造成双倍伤害 每一个技能最多只能释放一次，已知怪物有m点血量 现在想问你最少用几个技能能消灭掉他(血量小于等于0) 技能的数量是n，怪物的血量是m i号技能的伤害是x[i]，i号技能触发双倍伤害的血量最小值是y[i] 1 <= n <= 10 1 <= m、x[i]、y[i] <= 10^6 测试链接 : https://www.nowcoder.com/questionTerminal/d88ef50f8dab4850be8cd4b95514bbbd 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如，如果 words = ["ab","cd","ef"] 那么 "abcdef"， "abefcd"，"cdabef" "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。 返回所有串联字串在 s 中的开始索引 你可以以 任意顺序 返回答案 1 <= s.length <= 10^4 1 <= words.length <= 5000 1 <= words[i].length <= 30 words[i] 和 s 由小写英文字母组成 测试链接 : https://leetcode.cn/problems/substring-with-concatenation-of-all-words/ 小扣在探索丛林的过程中，无意间发现了传说中"落寞的黄金之都" 而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场 经过不断的勘测记录，小扣将所有力场的分布都记录了下来 forceField[i] = [x,y,side] 表示第 i 片力场将覆盖以坐标 (x,y) 为中心，边长为 side 的正方形区域。 若任意一点的 力场强度 等于覆盖该点的力场数量 请求出在这片地带中 力场强度 最强处的 力场强度 注意：力场范围的边缘同样被力场覆盖。 测试链接 : https://leetcode.cn/problems/xepqZ5/ 来自网易 题目出处 : https://leetcode.cn/circle/discuss/uOnnUA/ 已知一个n*n的01矩阵， 只能通过通过行交换、或者列交换的方式调整矩阵， 判断这个矩阵的对角线是否能全为1，如果能返回true，不能返回false 我们升级一下: 已知一个n*n的01矩阵， 只能通过通过行交换、或者列交换的方式调整矩阵， 判断这个矩阵的对角线是否能全为1，如果不能打印-1 如果能，打印需要交换的次数，并且打印怎么交换 测试链接 : http://acm.hdu.edu.cn/showproblem.php?pid=2819 第076节 2023年7月2周流行算法题目解析 阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有N堆金币 第i堆金币的总重量和总价值分别是m[i]、v[i] 阿里巴巴有一个承重量为T的背包，但并不一定有办法将全部的金币都装进去 他想装走尽可能多价值的金币 所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变 请问阿里巴巴最多可以拿走多少价值的金币？ 测试链接 : https://www.luogu.com.cn/problem/P2240 来自字节 机器人正在玩一个古老的基于DOS的游戏 游戏中有N+1座建筑，从0到N编号，从左到右排列 编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位 起初， 机器人在编号为0的建筑处 每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E 下一步它将跳到第个k+1建筑 它将会得到或者失去正比于与H(k+1)与E之差的能量 如果 H(k+1) > E 那么机器人就失去H(k+1)-E的能量值，否则它将得到E-H(k+1)的能量值 游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位 现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏 测试链接 : https://www.nowcoder.com/questionTerminal/7037a3d57bbd4336856b8e16a9cafd71 你有 k 个背包。给你一个下标从 0 开始的整数数组 weights 其中 weights[i] 是第 i 个珠子的重量。同时给你整数 k 请你按照如下规则将所有的珠子放进 k 个背包。 没有背包是空的。 如果第 i 个珠子和第 j 个珠子在同一个背包里 那么下标在 i 到 j 之间的所有珠子都必须在这同一个背包中 如果一个背包有下标从 i 到 j 的所有珠子，那么这个背包的价格是 weights[i] + weights[j] 。 一个珠子分配方案的 分数 是所有 k 个背包的价格之和。 请你返回所有分配方案中，最大分数 与 最小分数 的 差值 为多少。 测试链接 : https://leetcode.cn/problems/put-marbles-in-bags/ 一个公司准备组织一场会议，邀请名单上有 n 位员工 公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工 员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工 每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议 每位员工喜欢的员工 不会 是他自己。 给你一个下标从 0 开始的整数数组 favorite 其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 测试链接 : https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/ 给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边 最小生成树 (MST) 是给定图中边的一个子集 它连接了所有节点且没有环，而且这些边的权值和最小 请你找到给定图中最小生成树的所有关键边和伪关键边 如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边 伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边 请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标 测试链接 : https://leetcode.cn/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/ 第077节 2023年7月3周流行算法题目解析 先来一个最近学员在国外面试的题 有一个由x轴和y轴组成的坐标系 "y下"和"y上"表示一条无限延伸的道路，"y下"表示这个道路的下限，"y上"表示这个道路的上限 给定一批长方形，每一个长方形有(x1, x2, y1, y2)，4个坐标可以表示一个长方形 判断这条道路整体是不是可以走通的 以下为正式题目 图片在计算机处理中往往是使用二维矩阵来表示的 给你一个大小为 m x n 的二进制矩阵 image 表示一张黑白图片，0 代表白色像素，1 代表黑色像素 黑色像素相互连接，也就是说，图片中只会有一片连在一块儿的黑色像素。像素点是水平或竖直方向连接的 给你两个整数 x 和 y 表示某一个黑色像素的位置 请你找出包含全部黑色像素的最小矩形（与坐标轴对齐），并返回该矩形的面积 你必须设计并实现一个时间复杂度低于 O(m*n) 的算法来解决此问题。 测试链接 : https://leetcode.cn/problems/smallest-rectangle-enclosing-black-pixels/ 一个句子是由一些单词与它们之间的单个空格组成 且句子的开头和结尾没有多余空格 比方说，"Hello World" ，"HELLO" ，"hello world hello world" 都是句子 每个单词都 只 包含大写和小写英文字母 如果两个句子 sentence1 和 sentence2 可以通过往其中一个句子插入一个任意的句子（可以是空句子）而得到另一个句子 那么我们称这两个句子是 相似的 比方说，sentence1 = "Hello my name is Jane" 且 sentence2 = "Hello Jane" 我们可以往 sentence2 中 "Hello" 和 "Jane" 之间插入 "my name is" 得到 sentence1 给你两个句子 sentence1 和 sentence2 如果 sentence1 和 sentence2 是相似的，请你返回 true ，否则返回 false 测试链接 : https://leetcode.cn/problems/sentence-similarity-iii/ 每一种货币都给定面值val[i]，和拥有的数量cnt[i] 想知道目前拥有的货币，在钱数为1、2、3...m时，能找零成功的钱数有多少 也就是说当钱数的范围是1~m，返回这个范围上有多少可以找零成功的钱数 比如只有3元的货币，数量是5张 m = 10 那么在1~10范围上，只有钱数是3、6、9时，可以成功找零 所以返回3，表示有3种钱数可以找零成功 测试链接 : http://poj.org/problem?id=1742 我们把无限数量的栈排成一行，按从左到右的次序从 0 开始编号 每个栈的的最大容量 capacity 都相同。实现一个叫「餐盘」的类 DinnerPlates DinnerPlates(int capacity) - 给出栈的最大容量 capacity void push(int val) 将给出的正整数 val 推入 从左往右第一个 没有满的栈 int pop() 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除 如果所有的栈都是空的，请返回 -1。 int popAtStack(int index) - 返回编号 index 的栈顶部的值，并将其从栈中删除 如果编号 index 的栈是空的，请返回 -1。 测试链接 : https://leetcode.cn/problems/dinner-plate-stacks/ 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/ 第078节 2023年7月4周流行算法题目解析 给你一个正整数数组 nums 每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半 注意，在后续操作中你可以对减半过的数继续执行操作 请你返回将 nums 数组和 至少 减少一半的 最少 操作数 测试链接 : https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/ 自 01背包问世之后，小 A 对此深感兴趣 一天，小 A 去远游，却发现他的背包不同于 01 背包，他的物品大致可分为 k 组 每组中的物品只能选择1件，现在他想知道最大的利用价值是多少 测试链接 : www.luogu.com.cn/problem/P1757 一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币 每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里 给你一个列表 piles ，其中 piles[i] 是一个整数数组 分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k 请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少 测试链接 : https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/ 给你一个二进制字符串数组 strs 和两个整数 m 和 n 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 测试链接 : https://leetcode.cn/problems/ones-and-zeroes/ 集团里有 n 名员工，他们可以完成各种各样的工作创造利润 第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与 如果成员参与了其中一项工作，就不能参与另一项工作 工作的任何至少产生 minProfit 利润的子集称为 盈利计划 并且工作的成员总数最多为 n 有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。 测试链接 : https://leetcode.cn/problems/profitable-schemes/ 在一个小城市里，有 m 个房子排成一排 你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ) 有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新涂色 我们将连续相同颜色尽可能多的房子称为一个街区 比方说 houses = [1,2,2,3,3,2,1,1] 它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}] 给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target，其中： houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色 cost[i][j]：是将第 i 个房子涂成颜色 j+1 的花费 请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区 如果没有可用的涂色方案，请返回 -1 测试链接 : https://leetcode.cn/problems/paint-house-iii/