力扣熱門算法題 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

• 如果圖中有環，就無法修完全部課程。

1. 建立 鄰接表 graph 和 入度數組 in_degree
2. 所有入度為 0 的點入隊（無依賴的課可以先學）
3. 進行 BFS：

   1. 每彈出一個節點 u，將其鄰接的節點 v 入度減一

   2. 如果 v 入度變為 0，也加入隊列

4. 最終計數是否等于總課程數 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;}
}