当前位置：首页 > news >正文

力扣热门算法题 204.计数质数，207.课程表，213.打家劫舍II

news 2025/7/13 14:13:47

力扣热门算法题 204.计数质数，207.课程表，213.打家劫舍II，每题做详细思路梳理，配套Python&Java双语代码， 2025.07.07 可通过leetcode所有测试用例。

204.计数质数

解题思路

完整代码

207.课程表

解题思路

完整代码

213.打家劫舍II

解题思路

完整代码

204.计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：0
提示：

0 <= n <= 5 * 10^6

解题思路

对于每一个质数 p，从 p*p 开始，把所有 p 的倍数标记为非质数。

创建一个长度为 n 的布尔数组 isPrime，全部初始化为 True；
将 0 和 1 设为 False，它们不是质数；
从 2 开始，如果 isPrime[i] 为真，则它是质数；
- 将从 i*i 到 n-1 范围内所有 i 的倍数设为 False；
最后统计 True 的个数，就是质数的个数。

完整代码

python

class Solution:def countPrimes(self, n: int) -> int:if n < 2:return 0is_prime = [True] * nis_prime[0:2] = [False, False]for i in range(2, int(n ** 0.5) + 1):if is_prime[i]:for j in range(i * i, n, i):is_prime[j] = Falsereturn sum(is_prime)

java

class Solution {public int countPrimes(int n) {if (n < 2) return 0;boolean[] isPrime = new boolean[n];Arrays.fill(isPrime, true);isPrime[0] = false;isPrime[1] = false;for (int i = 2; i * i < n; i++) {if (isPrime[i]) {for (int j = i * i; j < n; j += i) {isPrime[j] = false;}}}int count = 0;for (boolean prime : isPrime) {if (prime) count++;}return count;}
}

207.课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
提示：

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同

解题思路

每门课是一节点，先修关系是有向边：

bi → ai 表示上课方向，先学 bi 再学 ai
如果图中有环，就无法修完全部课程。

建立 邻接表 graph 和 入度数组 in_degree
所有入度为 0 的点入队（无依赖的课可以先学）
进行 BFS：
1. 每弹出一个节点 u，将其邻接的节点 v 入度减一
2. 如果 v 入度变为 0，也加入队列
最终计数是否等于总课程数 numCourses

完整代码

python

from collections import deque
from typing import Listclass Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:graph = [[] for _ in range(numCourses)]in_degree = [0] * numCoursesfor a, b in prerequisites:graph[b].append(a)in_degree[a] += 1queue = deque([i for i in range(numCourses) if in_degree[i] == 0])count = 0while queue:node = queue.popleft()count += 1for neighbor in graph[node]:in_degree[neighbor] -= 1if in_degree[neighbor] == 0:queue.append(neighbor)return count == numCourses

java

import java.util.*;class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<List<Integer>> graph = new ArrayList<>();int[] inDegree = new int[numCourses];for (int i = 0; i < numCourses; i++) {graph.add(new ArrayList<>());}for (int[] pair : prerequisites) {int a = pair[0], b = pair[1];graph.get(b).add(a);inDegree[a]++;}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) queue.offer(i);}int count = 0;while (!queue.isEmpty()) {int node = queue.poll();count++;for (int neighbor : graph.get(node)) {inDegree[neighbor]--;if (inDegree[neighbor] == 0) queue.offer(neighbor);}}return count == numCourses;}
}

213.打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：
输入：nums = [1,2,3]
输出：3
提示：

1 <= nums.length <= 100
0 <= nums[i] <= 1000

解题思路

我们把问题转换为两个不包含首尾同时偷的情况：

不偷第一个房子 → 考虑 nums[1:]
不偷最后一个房子 → 考虑 nums[:-1]

标准动态规划：

定义：dp[i] 表示前 i 间房最多能偷多少钱；

完整代码

python

from typing import Listclass Solution:def rob(self, nums: List[int]) -> int:if len(nums) == 1:return nums[0]def rob_linear(nums: List[int]) -> int:prev, curr = 0, 0for num in nums:prev, curr = curr, max(curr, prev + num)return currreturn max(rob_linear(nums[1:]), rob_linear(nums[:-1]))

java

class Solution {public int rob(int[] nums) {if (nums.length == 1) return nums[0];return Math.max(robRange(nums, 0, nums.length - 2),robRange(nums, 1, nums.length - 1));}private int robRange(int[] nums, int start, int end) {int prev = 0, curr = 0;for (int i = start; i <= end; i++) {int temp = curr;curr = Math.max(curr, prev + nums[i]);prev = temp;}return curr;}
}