Sieve BFS解Leetcode 3629 Minimum Jumps to Reach End via Prime Teleportation
目前記錄為83ms. Using array version of linked lists it 's faster, say 64ms!為何結合Sieve法與BFS的問題。會被Leetcode標示為medium?
幾個100%的解
[codes on Leetcode]https://leetcode.com/problems/minimum-jumps-to-reach-end-via-prime-teleportation/solutions/8164753/sieve-of-eratosthenes-bfs-no-hash83ms-be-f6ci/
----
0:00 - Introduction and performance comparison (103ms vs. 344ms Leetcode editor's solution)
00:34 - Problem Analysis: LeetCode 3629 - Minimum Jumps to Reach End via Prime Teleportation
01:20 - Understanding the rules: Adjacent steps (i±1) and Prime Teleportation (jumping to indices where the value is a multiple of a prime p)
03:15 - Example 1 Walkthrough
04:08 - Example 2 Walkthrough
04:56 - Example 3 Walkthrough
05:48 - Analyzing constraints and potential performance issues (Time/Memory limits)
06:40 - Solution Strategy: Sieve of Eratosthenes and Breadth-First Search (BFS)
08:00 - Data Structures: Using 2D vectors and arrays for prime index mapping
09:15 - BFS Logic: Reverse search from n-1 to 0
11:00 - Implementing the Sieve of Eratosthenes for prime numbers up to 1 million
15:51 - Optimized memory management for prime index containers
18:21 - Detailed BFS implementation using bitsets for performance
25:08 - Submitting the solution and reviewing the runtime results
25:46 - Code Walkthrough: Global variables, Sieve function, and Reset logic
27:28 - Main Logic: Calculating minimum jumps
29:34 - Final Performance Result: 103ms (Beating the standard solution)
----
Most solutions use a hash map to store prime factors, but that’s where you lose time. To hit 88ms, I pre-process everything. I use a Sieve to find primes and store their positions in a 2D vector. This gives us direct memory access during the BFS—no hashing, no collisions, just pure speed.
沒有留言:
張貼留言