每周有营养的大厂算法面试题 第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周流行算法题目解析