Author: hetengda123

Convert BST to Doubly Linked List

Inorder iterative traversal

DoublyListNode head, previous

 Solution

Advertisements

Coins in a Line III

There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

Could you please decide the first player will win or lose?

Follow Up Question:

If n is even. Is there any hacky algorithm that can decide whether first player will win or lose in O(1) memory and O(n) time?
solution

Merge Sort Template

public void sortIntegers2(int[] A) {
    // use a shared temp array, the extra memory is O(n) at least
    int[] temp = new int[A.length];
    mergeSort(A, 0, A.length - 1, temp);
}
private void mergeSort(int[] A, int start, int end, int temp){
    if(start >= end){
        return;
    }
    int mid = start + (end - start) / 2;
    mergeSort(A, start, mid, temp);
    mergeSort(A, mid + 1, end, temp);
    merge(A, start, mid, end, temp);
}
private void merge(int[] A, int start, int mid, int end, int[] temp){
    int left = start;
    int right = mid + 1;
    int index = start;
    // merge two sorted subarrays in A to temp array
    while(left <= mid && right <= end){
        if(A[left] < A[right]){
            temp[index++] = A[left++];
        } else {
            temp[index++] = A[right++];
        }
    }
    while(left <= mid){
        temp[index++] = A[left++];
    }
    while(right <= mid){
        temp[index++] = A[right++];
    }
    // copy temp back to A
    for(index = start; index <= end; index++){
        A[index] = temp[index];
    }
}

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

High Five

/**
 * @param results a list of <student_id, score>
 * @return find the average of 5 highest scores for each person
 * Map<Integer, Double> (student_id, average_score)
 */
public Map<Integer, Double> highFive(Record[] results) {
    Map<Integer, Double> answer = new HashMap<>();
    Map<Integer, List<Integer>> hash = new HashMap<Integer, List<Integer>>();
    for(Record r : results){
        if(!hash.containsKey(r.id)){
            hash.put(r.id, new ArrayList<Integer>());
        }
        if(hash.get(r.id).size() < 5){
            hash.get(r.id).add(r.score);
        } else {
            int lowest_index = 0;
            for(int i = 1; i < 5; i++){
                if(hash.get(r.id).get(i) < hash.get(r.id).get(lowest_index)){
                    lowest_index = i;
                }
            }
            if(hash.get(r.id).get(lowest_index) < r.score){
                hash.get(r.id).set(lowest_index, r.score);
            }
        }
    }
    for(Map.Entry<Integer, List<Integer>> entry : hash.entrySet()){
        int id = entry.getKey();
        List<Integer> scores = entry.getValue();
        double average = 0.0;
        for(int i = 0; i < scores.size(); i++){
            average += scores.get(i);
        }
        average /= scores.size();
        answer.put(id, average);
    }
    return answer;
}

K Closest Points

/**
 * @param points a list of points
 * @param origin a point
 * @param k an integer
 * @return the k closest points
 */
public Point[] kClosest(Point[] points, Point origin, int k) {
    final Point global_origin = origin;
    PriorityQueue<Point> priorityqueue = new PriorityQueue<Point>(k, new Comparator<Point>(){
            @Override
            public int compare(Point a, Point b){
                int diff = getDistance(b, global_origin) - getDistance(a, global_origin);
                if(diff == 0){
                    diff = b.x - a.x;
                }
                if(diff == 0){
                    diff = b.y - a.y;
                }
                return diff;
            }
        });
    
    for(int i = 0; i < points.length; i++){
        priorityqueue.offer(points[i]);
        if(priorityqueue.size() > k){
            priorityqueue.poll();
        }
    }
    k = priorityqueue.size();
    Point[] res = new Point[k];
    while(!priorityqueue.isEmpty()){
        res[--k] = priorityqueue.poll();
    }
    return res;
}
private int getDistance(Point a, Point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

sort map by value

Class ValueComparator implements Comparator<String> {
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    public ValueComparator(HashMap<String, Integer> map){
        this.map.putAll(map);
    }
    int compare(String key1, String key2){
        if(map.get(key1) < map.get(key2)){
            return 1;
        } else {
            return -1;
        }
    }
}
...
Comparator<String> comparator = new ValueComparator(originalMap);
TreeMap<String, Integer> result = new TreeMap<String, Integer>(comparator);
result.putAll(orignalMap);
return result;

java-sort-map-by-value