現(xiàn))
根據(jù)已收集的信息我來(lái)為你提供 LCP 15. 游樂園的迷宮 的 Rust 實(shí)現(xiàn)。題目分析這道題是貪心 計(jì)算幾何問題。核心思想是 每次選擇一個(gè)極端的點(diǎn)使得剩余未訪問的點(diǎn)全部位于當(dāng)前轉(zhuǎn)向方向要求的一側(cè)從而保證后續(xù)每一步都有可行的選擇。核心洞察- 起點(diǎn)選擇選擇橫坐標(biāo)最小最左側(cè)的點(diǎn)作為起點(diǎn)保證它是凸包上的一個(gè)頂點(diǎn)- 轉(zhuǎn)向?yàn)?L左轉(zhuǎn)選擇相對(duì)方向最右的點(diǎn)使得剩余所有點(diǎn)都在當(dāng)前方向的左側(cè)- 轉(zhuǎn)向?yàn)?R右轉(zhuǎn)選擇相對(duì)方向最左的點(diǎn)使得剩余所有點(diǎn)都在當(dāng)前方向的右側(cè)向量叉積判斷方向?qū)τ谙蛄?a (x1, y1) 和 b (x2, y2)- cross(a, b) x1*y2 - y1*x2- cross 0b 在 a 的逆時(shí)針方向左側(cè)- cross 0b 在 a 的順時(shí)針方向右側(cè)Rust 實(shí)現(xiàn)rustimpl Solution {pub fn visit_order(points: VecVeci32, direction: String) - Veci32 {let n points.len();let dir_chars: Vecchar direction.chars().collect();// 訪問標(biāo)記let mut used vec![false; n];let mut ans: Veci32 Vec::with_capacity(n);// 1. 找最左側(cè)的點(diǎn)作為起點(diǎn)橫坐標(biāo)最小相同則縱坐標(biāo)最小let mut start 0usize;for i in 1..n {if points[i][0] points[start][0]|| (points[i][0] points[start][0] points[i][1] points[start][1]) {start i;}}used[start] true;ans.push(start as i32);// 2. 貪心根據(jù) direction 依次選擇下一個(gè)點(diǎn)for d in dir_chars {let mut next: i32 -1;if d L {// 下一步要左轉(zhuǎn)選擇相對(duì)方向最右的點(diǎn)// 這樣剩余所有點(diǎn)都在當(dāng)前方向的左側(cè)for j in 0..n {if used[j] { continue; }if next -1 {next j as i32;continue;}// 比較向量 (next - start) 和 (j - start) 的叉積// 如果 cross 0說明 j 在 next 的順時(shí)針方向更右let nx points[next as usize][0] - points[start][0];let ny points[next as usize][1] - points[start][1];let jx points[j][0] - points[start][0];let jy points[j][1] - points[start][1];let cross nx * jy - ny * jx;if cross 0 {next j as i32;}}} else {// 下一步要右轉(zhuǎn)選擇相對(duì)方向最左的點(diǎn)for j in 0..n {if used[j] { continue; }if next -1 {next j as i32;continue;}let nx points[next as usize][0] - points[start][0];let ny points[next as usize][1] - points[start][1];let jx points[j][0] - points[start][0];let jy points[j][1] - points[start][1];let cross nx * jy - ny * jx;if cross 0 {next j as i32;}}}used[next as usize] true;ans.push(next);start next as usize;}// 3. 添加最后一個(gè)未訪問的點(diǎn)for i in 0..n {if !used[i] {ans.push(i as i32);}}ans}}關(guān)鍵點(diǎn)解釋要點(diǎn) 說明起點(diǎn)選擇 橫坐標(biāo)最小的點(diǎn)最左側(cè)保證在凸包上后續(xù)總能找到滿足條件的點(diǎn)L 轉(zhuǎn)向 選最右的點(diǎn)使得剩余點(diǎn)全在當(dāng)前方向的左側(cè)保證下一步左轉(zhuǎn)可行R 轉(zhuǎn)向 選最左的點(diǎn)使得剩余點(diǎn)全在當(dāng)前方向的右側(cè)保證下一步右轉(zhuǎn)可行叉積判斷 cross(a, b) 0 表示 b 在 a 的順時(shí)針方向更右 0 則更左為什么可行 每次選擇極端點(diǎn)后剩余點(diǎn)全在要求的一側(cè)遞歸下去總有解復(fù)雜度分析- 時(shí)間復(fù)雜度O(N^2)每次選擇下一個(gè)點(diǎn)需要遍歷所有未訪問的點(diǎn)- 空間復(fù)雜度O(N)用于訪問標(biāo)記和結(jié)果數(shù)組示例驗(yàn)證示例1points [[1,1],[1,4],[3,2],[2,1]], direction LL- 最左側(cè)點(diǎn)[1,1]索引0- 第一步方向 L從點(diǎn)0出發(fā)找最右的點(diǎn) → 點(diǎn)2 [3,2]- 第二步方向 L從點(diǎn)2出發(fā)找最右的點(diǎn) → 點(diǎn)1 [1,4]- 最后剩余點(diǎn)3 [2,1]- 輸出[0, 2, 1, 3] ?示例2points [[1,3],[2,4],[3,3],[2,1]], direction LR- 最左側(cè)點(diǎn)[1,3]索引0- 第一步方向 L找最右的點(diǎn) → 點(diǎn)3 [2,1]- 第二步方向 R找最左的點(diǎn) → 點(diǎn)1 [2,4]- 最后剩余點(diǎn)2 [3,3]- 輸出[0, 3, 1, 2] ? Kimi LeetCode LCP 15. 游樂園的迷宮 Rust實(shí)現(xiàn)
根據(jù)已收集的信息我來(lái)為你提供 LCP 15. 游樂園的迷宮 的 Rust 實(shí)現(xiàn)。題目分析這道題是貪心 計(jì)算幾何問題。核心思想是 每次選擇一個(gè)極端的點(diǎn)使得剩余未訪問的點(diǎn)全部位于當(dāng)前轉(zhuǎn)向方向要求的一側(cè)從而保證后續(xù)每一步都有可行的選擇。核心洞察- 起點(diǎn)選擇選擇橫坐標(biāo)最小最左側(cè)的點(diǎn)作為起點(diǎn)保證它是凸包上的一個(gè)頂點(diǎn)- 轉(zhuǎn)向?yàn)?L左轉(zhuǎn)選擇相對(duì)方向最右的點(diǎn)使得剩余所有點(diǎn)都在當(dāng)前方向的左側(cè)- 轉(zhuǎn)向?yàn)?R右轉(zhuǎn)選擇相對(duì)方向最左的點(diǎn)使得剩余所有點(diǎn)都在當(dāng)前方向的右側(cè)向量叉積判斷方向?qū)τ谙蛄?a (x1, y1) 和 b (x2, y2)- cross(a, b) x1*y2 - y1*x2- cross 0b 在 a 的逆時(shí)針方向左側(cè)- cross 0b 在 a 的順時(shí)針方向右側(cè)Rust 實(shí)現(xiàn)rustimpl Solution {pub fn visit_order(points: VecVeci32, direction: String) - Veci32 {let n points.len();let dir_chars: Vecchar direction.chars().collect();// 訪問標(biāo)記let mut used vec![false; n];let mut ans: Veci32 Vec::with_capacity(n);// 1. 找最左側(cè)的點(diǎn)作為起點(diǎn)橫坐標(biāo)最小相同則縱坐標(biāo)最小let mut start 0usize;for i in 1..n {if points[i][0] points[start][0]|| (points[i][0] points[start][0] points[i][1] points[start][1]) {start i;}}used[start] true;ans.push(start as i32);// 2. 貪心根據(jù) direction 依次選擇下一個(gè)點(diǎn)for d in dir_chars {let mut next: i32 -1;if d L {// 下一步要左轉(zhuǎn)選擇相對(duì)方向最右的點(diǎn)// 這樣剩余所有點(diǎn)都在當(dāng)前方向的左側(cè)for j in 0..n {if used[j] { continue; }if next -1 {next j as i32;continue;}// 比較向量 (next - start) 和 (j - start) 的叉積// 如果 cross 0說明 j 在 next 的順時(shí)針方向更右let nx points[next as usize][0] - points[start][0];let ny points[next as usize][1] - points[start][1];let jx points[j][0] - points[start][0];let jy points[j][1] - points[start][1];let cross nx * jy - ny * jx;if cross 0 {next j as i32;}}} else {// 下一步要右轉(zhuǎn)選擇相對(duì)方向最左的點(diǎn)for j in 0..n {if used[j] { continue; }if next -1 {next j as i32;continue;}let nx points[next as usize][0] - points[start][0];let ny points[next as usize][1] - points[start][1];let jx points[j][0] - points[start][0];let jy points[j][1] - points[start][1];let cross nx * jy - ny * jx;if cross 0 {next j as i32;}}}used[next as usize] true;ans.push(next);start next as usize;}// 3. 添加最后一個(gè)未訪問的點(diǎn)for i in 0..n {if !used[i] {ans.push(i as i32);}}ans}}關(guān)鍵點(diǎn)解釋要點(diǎn) 說明起點(diǎn)選擇 橫坐標(biāo)最小的點(diǎn)最左側(cè)保證在凸包上后續(xù)總能找到滿足條件的點(diǎn)L 轉(zhuǎn)向 選最右的點(diǎn)使得剩余點(diǎn)全在當(dāng)前方向的左側(cè)保證下一步左轉(zhuǎn)可行R 轉(zhuǎn)向 選最左的點(diǎn)使得剩余點(diǎn)全在當(dāng)前方向的右側(cè)保證下一步右轉(zhuǎn)可行叉積判斷 cross(a, b) 0 表示 b 在 a 的順時(shí)針方向更右 0 則更左為什么可行 每次選擇極端點(diǎn)后剩余點(diǎn)全在要求的一側(cè)遞歸下去總有解復(fù)雜度分析- 時(shí)間復(fù)雜度O(N^2)每次選擇下一個(gè)點(diǎn)需要遍歷所有未訪問的點(diǎn)- 空間復(fù)雜度O(N)用于訪問標(biāo)記和結(jié)果數(shù)組示例驗(yàn)證示例1points [[1,1],[1,4],[3,2],[2,1]], direction LL- 最左側(cè)點(diǎn)[1,1]索引0- 第一步方向 L從點(diǎn)0出發(fā)找最右的點(diǎn) → 點(diǎn)2 [3,2]- 第二步方向 L從點(diǎn)2出發(fā)找最右的點(diǎn) → 點(diǎn)1 [1,4]- 最后剩余點(diǎn)3 [2,1]- 輸出[0, 2, 1, 3] ?示例2points [[1,3],[2,4],[3,3],[2,1]], direction LR- 最左側(cè)點(diǎn)[1,3]索引0- 第一步方向 L找最右的點(diǎn) → 點(diǎn)3 [2,1]- 第二步方向 R找最左的點(diǎn) → 點(diǎn)1 [2,4]- 最后剩余點(diǎn)2 [3,3]- 輸出[0, 3, 1, 2] ?