Category: Uncategorized

Convert BST to Doubly Linked List

Inorder iterative traversal

DoublyListNode head, previous

 Solution

Advertisements

The Maze

class Point {
    int x, y;
    public Point(int _x, int _y){
        x = _x;
        y = _y;
    }
}
public boolean hasPath(int[][] maze, int[] start, int[] destination){
    int rows = maze.length;
    int cols = maze[0].length;
    if(start[0] == destination[0] && start[1] == destination[1]){
        return true;
    }
    int[][] direct = int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    boolean[][] visited = new boolean[rows][cols];
    Queue<Point> queue = new LinkedList<>();
    visited[start[0]][start[1]] = true;
    queue.offer(new Point(start[0], start[1]));
    while(!queue.isEmpty()){
        Point p = queue.poll();
        int x = p.x;
        int y = p.y;
        for(int i = 0; i i < direct.length; i++){
            int new_x = x, new_y = y;
            while(new_x >= 0 && new_x < rows && new_y >= 0 && new_y < cols && maze[new_x][new_y] == 0){
                new_x += direct[i][0];
                new_y += direct[i][1];
            }
            new_x -= direct[i][0];
            new_y -= direct[i][1];
            if(visited[new_x][new_y]){
                continue;
            }
            visited[new_x][new_y] = true;
            if(destination[0] == new_x && destination[1] == new_y){
                return true;
            }
            queue.offer(new Point(new_x, new_y));
        }
    }
    return false;
}

[LeetCode] The Maze

Meeting Rooms II

public int minMeetingRooms(Interval[] intervals) {
    if(intervals == null || intervals.length == 0){
        return 0;
    }
    Arrays.sort(intervals, new Comparator<Interval>(){
        public int compare(Interval a, Interval b){
            return a.start - b.start;
        }
    });
    PriorityQueue<Integer> queue = new PriorityQueue<>();
    int count = 1;
    queue.offer(intervals[0].end);
    for(int i = 1; i < intervals.length; i++){
        if(intervals[i].start < queue.peek()){
            count++;
        } else {
            queue.poll();
        }
        queue.offer(intervals[i].end);
    }
    return count;
}

meeting-rooms-II-java

largest closed loop

/*
     * A zero-indexed array A consisting of N different integers is given. The
     * array contains all integers in the range [0..N−1]. Sets S[K] for 0 ≤ K &lt;
     * N are defined as follows: S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }. Sets
     * S[K] are finite for each K.
     *
     * Write a function:
     *
     * class Solution { public int solution(int[] A); }
     *
     * that, given an array A consisting of N integers, returns the size of the
     * largest closed loop set S[K] for this array. The function should return 0 if the
     * array is empty.
     */
    /*
     * changed value
     */
public int largestClosedLoopSet(int[] A){
    if(A == null || A.length == 0){
        return 0;
    }
    int res = 1;
    int count = 0;
    for(int i = 0; i < A.length; i++){
        count = 0;
        while(A[i] >= 0 && A[i] < A.length){
            count++;
            int nextIndex = A[i];
            // reset A[i] to prevent future repeat iteration.
            A[i] = -1;
            i = inextIndex;
        }
        res = Math.max(res, count);
    }
return res;
}