Java Solution


  • 1
    S

    public class Solution {
    class StoneValue implements Comparable {
    int stoneValue;
    int unitValue;

        StoneValue(int stoneValue, int unitValue) {
            this.stoneValue = stoneValue;
            this.unitValue = unitValue;
        }
        
        public int compareTo(Object sv) {
            return Integer.compare(this.stoneValue, ((StoneValue)sv).stoneValue);
        }
    }
    public boolean canCross(int[] stones) {
        if (!(stones[0] == 0 && stones[1] == 1)) {
            return false;
        }
        int last = stones[stones.length - 1];
        Set mySet = new HashSet();
        for (Integer i : stones) {
            mySet.add(i);
        }
        PriorityQueue<StoneValue> queue = new PriorityQueue<StoneValue>(Collections.reverseOrder());
        queue.add(new StoneValue(1, 1));
        
        while (!queue.isEmpty()) {
            StoneValue stone = queue.remove();
            if (stone.stoneValue == last) {
                return true;
            }
            if (mySet.contains(stone.stoneValue + stone.unitValue)) {
                queue.add(new StoneValue(stone.stoneValue + stone.unitValue, stone.unitValue));
            } 
            if (stone.stoneValue + stone.unitValue - 1 > stone.stoneValue) {
                if (mySet.contains(stone.stoneValue + stone.unitValue - 1)) {
                    queue.add(new StoneValue(stone.stoneValue + stone.unitValue - 1, stone.unitValue - 1));
                }
            }
            
            if (mySet.contains(stone.stoneValue + stone.unitValue + 1)) {
                queue.add(new StoneValue(stone.stoneValue + stone.unitValue + 1, stone.unitValue + 1));
            }
        }
        return false;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.