题目要求 给定一个正整数 n，返回它的二进制表示中 1 的个数。这个数量也叫 Hamming weight。 LeetCode 提供的方法接口是： hammingWeight(n: int) -> int 示例 1 输入：n = 11 二进制：1011 输出：3 示例 2 输入：n = 128 二进制：10000000 输出：1 约束 1 <= n <= 2^31 - 1 输入处于题目给定的非负整数范围内。 虽然当前约束从 1 开始，后面的实现也会自然处理 n = 0，并返回 0。 Step 1：先明确到底在数什么 先看一个不使用十进制表示的小任务： n = 101100₂ 从左到右可以看到三个 1： 1 0 1 1 0 0 ^ ^ ^ 所以答案是 3。 当前 baseline 是： 先看出整数的二进制表示，再人工统计其中的 1。 这个 baseline 的 break 是： ...
题目要求 给定一个非负整数 n，返回一个长度为 n + 1 的数组 answer。 其中： answer[i] = 整数 i 的二进制表示中 1 的数量 需要回答的范围包含 0 和 n。 LeetCode 提供的方法接口是： countBits(n: int) -> List[int] 示例 1 输入：n = 2 输出：[0,1,1] 对应关系是： 0 -> 0 -> 0 个 1 1 -> 1 -> 1 个 1 2 -> 10 -> 1 个 1 示例 2 输入：n = 5 输出：[0,1,1,2,1,2] 约束 0 <= n <= 10^5 Step 1：这次要回答 0 到 n 的所有数字 LeetCode 191 只要求统计一个整数。现在看 n = 5： ...
题目要求 给定一个整数数组 temperatures，其中 temperatures[i] 表示第 i 天的温度。 返回数组 answer，其中： answer[i] = 从第 i 天开始，需要等待多少天才会遇到更高温度 如果之后没有更高温度，answer[i] = 0。 这里的“更高”是严格大于。相同温度不能结算等待中的日期。 LeetCode 提供的方法接口是： dailyTemperatures(temperatures: List[int]) -> List[int] 示例 输入：temperatures = [73,74,75,71,69,72,76,73] 输出：[1,1,4,2,1,1,0,0] 约束 1 <= temperatures.length <= 10^5 30 <= temperatures[i] <= 100 Step 1：答案不是更高温度，而是等待天数 先看一个更小的输入： temperatures = [73,71,72,76] 逐天回答： 第 0 天是 73，右侧第一个更高温度是第 3 天的 76，等待 3 天。 第 1 天是 71，第 2 天的 72 更高，等待 1 天。 第 2 天是 72，第 3 天的 76 更高，等待 1 天。 第 3 天右侧没有日期，答案是 0。 所以结果是： ...
题目要求 给你一个整数数组 nums。 你一开始站在下标 0。 nums[i] 表示： 从下标 i 最多可以向右跳多少步 题目要求返回： 到达最后一个下标所需的最少跳跃次数 输入输出 输入：nums: List[int] 输出：int 从下标 0 出发 每个数字表示最大跳跃长度，不是必须跳这么远 题目保证一定可以到达最后一个下标 只需要返回最少跳数，不需要返回具体路径 示例 输入：nums = [2,3,1,1,4] 输出：2 一种最少跳法是： 0 -> 1 -> 4 从下标 0 跳到下标 1，再从下标 1 跳到最后一个下标。 输入：nums = [2,3,0,1,4] 输出：2 虽然中间有 0，但仍然可以： 0 -> 1 -> 4 约束 1 <= nums.length <= 10^4 0 <= nums[i] <= 1000 题目保证 nums[n - 1] 可达 Step 1：45 不是问能不能到，而是问最少几步到 如果刚做完 LeetCode 55，已经知道可以维护： ...
题目要求 给你一个区间数组 intervals。 每个区间写成： [start, end] 题目要求删除尽量少的区间，使剩下的区间互不重叠。 最后返回： 最少需要删除多少个区间 输入输出 输入：intervals: List[List[int]] 输出：int 每个区间满足 start < end 如果两个区间只是在端点相接，不算重叠 也就是说： [1,2] 和 [2,3] 可以同时保留。 示例 输入：intervals = [[1,2],[2,3],[3,4],[1,3]] 输出：1 删除 [1,3] 后，剩下： [[1,2],[2,3],[3,4]] 这些区间互不重叠。 再看两个边界例子： 输入：intervals = [[1,2],[1,2],[1,2]] 输出：2 三个完全相同的区间最多只能保留一个，所以要删除两个。 输入：intervals = [[1,2],[2,3]] 输出：0 这两个区间只在端点 2 相接，不算重叠，所以不用删除。 约束 1 <= intervals.length <= 10^5 intervals[i].length == 2 -5 * 10^4 <= start_i < end_i <= 5 * 10^4 Step 1：不要先问删哪个，先问最多能留几个 先看这个例子： intervals = [[1,2],[2,3],[3,4],[1,3]] 题目问的是： ...
题目要求 给你一个气球数组 points。 每个气球是一个水平区间： [start, end] 如果一支箭射在横坐标 x 上，并且： start <= x <= end 那么这支箭可以射爆这个气球。 一支箭会一直向上飞，所以同一个 x 上能覆盖到的所有气球都会被射爆。 题目要求返回： 射爆所有气球需要的最少箭数 输入输出 输入：points: List[List[int]] 输出：int 每个气球是一个区间 [start, end] 箭的位置 x 可以落在端点上 不需要返回每支箭的位置，只需要返回最少箭数 示例 输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2 一种射法是： x = 6 射爆 [2,8] 和 [1,6] x = 11 射爆 [10,16] 和 [7,12] 再看两个边界例子： 输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4 这些气球互不相交，每个气球都需要一支箭。 输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2 因为箭可以射在端点上，所以： x = 2 可以射爆 [1,2] 和 [2,3] x = 4 可以射爆 [3,4] 和 [4,5] 约束 1 <= points.length <= 10^5 points[i].length == 2 -2^31 <= start < end <= 2^31 - 1 Step 1：一支箭到底能覆盖哪些气球？ 先看一个很小的问题： ...
题目要求 给你一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。 你只能完成一次交易： 选择某一天买入一支股票 选择未来某一天卖出这支股票 返回能获得的最大利润。如果无法盈利，返回 0。 输入输出 输入：prices: List[int] 输出：最大利润 int 只能买一次、卖一次。 买入日必须早于卖出日。 可以选择不交易，此时利润是 0。 示例 输入：prices = [7,1,5,3,6,4] 输出：5 最优做法是在价格为 1 时买入，在价格为 6 时卖出，利润是 6 - 1 = 5。 输入：prices = [7,6,4,3,1] 输出：0 价格一直下降，任何买入后再卖出都会亏钱，所以返回 0。 约束 1 <= prices.length <= 10^5 0 <= prices[i] <= 10^4 Step 1：先固定买卖顺序 先看这个例子： prices = [7,1,5,3,6,4] 如果只看价格差，最大利润来自： 1 -> 6 profit = 5 这是合法的，因为价格 1 出现在价格 6 之前。 ...
题目要求 给你一个整数数组 nums。 你一开始站在下标 0。nums[i] 表示从位置 i 最多可以向右跳多少步。 题目要求判断：能不能到达最后一个下标。 输入输出 输入：nums: List[int] 输出：bool 从下标 0 出发。 每个位置的数字表示最大跳跃长度，不是必须跳这么远。 只需要判断能否到达最后一个下标，不需要返回具体路径。 示例 输入：nums = [2,3,1,1,4] 输出：true 一种跳法是： 0 -> 1 -> 4 从下标 0 可以跳到下标 1，再从下标 1 跳到最后一个下标。 输入：nums = [3,2,1,0,4] 输出：false 无论怎么跳，都会被下标 3 的 0 卡住，无法到达最后一个下标 4。 约束 1 <= nums.length <= 10^4 0 <= nums[i] <= 10^5 Step 1：不要先猜路径，先看覆盖范围 先看失败样例： nums = [3,2,1,0,4] 从下标 0 最多可以跳到下标 3。 看起来选择很多： 0 -> 1 0 -> 2 0 -> 3 当前 baseline 是： ...
题目要求 给你一个 m x n 的二维字符网格 grid： "1" 表示陆地 "0" 表示水 题目要求返回岛屿数量。 一个岛屿由水平或垂直相邻的陆地组成。对角线相邻不算连通。可以认为网格四周都被水包围。 输入输出 输入：grid: List[List[str]] 输出：岛屿数量 int 只看上下左右四个方向。 "0" 水格子不能算作岛屿的一部分。 示例 输入： [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1 这些陆地通过上下左右连成一整块，所以答案是 1。 输入： [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3 这里有三块互不连通的陆地，所以答案是 3。 约束 m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] 只会是 "0" 或 "1" 这一题可以用 DFS 或 BFS 做。这里的目标是练并查集：把每块陆地当成一个节点，把相邻陆地合并，最后留下的陆地连通分量数量就是岛屿数量。 ...
题目要求 题目给你一个无向图。这个图原本是一棵有 n 个节点的树，节点编号是 1..n，后来额外加了一条边。 树的定义是： 连通 没有环 加上一条额外边之后，图仍然连通，但会出现一个环。 现在给定边数组 edges，其中 edges[i] = [a, b] 表示节点 a 和节点 b 之间有一条无向边。题目要求返回一条可以删除的边，使剩下的图重新变成树。 如果有多个答案，返回在输入中最后出现的那条。 输入输出 输入：edges: List[List[int]] 输出：一条边 List[int] n == len(edges) 节点编号是 1..n 图中没有重复边 给定图是连通的 示例 输入：edges = [[1,2],[1,3],[2,3]] 输出：[2,3] 前两条边形成一棵树： 1 - 2 | 3 再加入 [2,3]，2 和 3 之间已经能通过 2 -> 1 -> 3 连通。现在再加直接边，就形成环。 输入：edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] 输出：[1,4] 加入 [1,4] 之前，1 和 4 已经能通过 1 -> 2 -> 3 -> 4 连通，所以 [1,4] 是冗余边。 ...