Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/08/27 17:40)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串400/719 (看更多)

https://leetcode.com/problems/frog-jump/description/ 403. Frog Jump 給你一個陣列 stones[]，stones[i] 表示石頭的座標，青蛙會從 stones[0] 開始跳，第一次跳 1 步，後面可以跳 k, k + 1, k - 1 步（k 為上一次跳的步數），青蛙只能走在石頭上，求出青蛙是否可以跳到最後一個石頭的位置。 Example 1: Input: stones = [0,1,3,5,6,8,12,17] Output: true Explanation: The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone. Example 2: Input: stones = [0,1,2,3,4,8,9,11] Output: false Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large. 思路： 1.從第一個石頭往後跳 1 步並標記目的地石頭為可到達，之後遍歷所有的石頭，如果這個石頭是可到達的就往後跳 k, k+1, k-1 步，如果目的地是石頭也標記為可到達。 2.最後檢查最後一顆石頭是不是可到達即可。 Java Code： ---------------------------------------------------- class Solution { public boolean canCross(int[] stones) { Map<Integer, Set<Integer>> map = new HashMap<>(); for (int stone : stones) { map.put(stone, new HashSet<>()); } map.computeIfPresent(stones[0] + 1, (k, v) -> { v.add(1); return v; }); for (int i = 1; i < stones.length; i++) { Set<Integer> set = new HashSet<>(map.get(stones[i])); for (int step : set) { if (map.containsKey(stones[i] + step)) { map.get(stones[i] + step).add(step); } if (map.containsKey(stones[i] + step + 1)) { map.get(stones[i] + step + 1).add(step + 1); } if (map.containsKey(stones[i] + step - 1)) { map.get(stones[i] + step - 1).add(step - 1); } } } return map.get(stones[stones.length - 1]).size() > 0; } } ---------------------------------------------------- -- https://i.imgur.com/4nfnn6f.jpg