Design Snake Game

https://leetcode.com/problems/design-snake-game/

  • Looked at this post: https://discuss.leetcode.com/topic/48626/java-deque-and-hashset-design-with-detailed-comments
  • Keys:
    • Use Deque interface (stands for Double Ended Queue) which means you can remove and insert elements from both ends of the queue, this is exactly what we wanted in this problem. This is also why LinkedList in java is implemented as Doubly-linked list, to support operations in both directions.
    • The typical trick to convert a 2D matrix into a 1D array:
      • rowNumber*width + columnNumber
    • in switch branches, remember to add break; when needed
    • remember to have a field called foodIndex and check if it’s right for the given food[][] position and also remember to increment it by 1 each time a normal eat happens.

public class SnakeGame {

private Set<Integer> set;//Use a set to hold all occupied points for the snake body, this is for easy access for the case of eating its own body
private Deque<Integer> body;//use a queue to hold all occupied points for the snake body as well, this is for easy access to update the tail
int[][] food;
int score;
int foodIndex;
int width;
int height;

/** Initialize your data structure here.
@param width - screen width
@param height - screen height
@param food - A list of food positions
E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
public SnakeGame(int width, int height, int[][] food) {
this.set = new HashSet<Integer>();
set.add(0);//initially at [0][0]
this.body = new LinkedList<Integer>();
body.offerLast(0);
this.food = food;
this.width = width;
this.height = height;
}

/** Moves the snake.
@param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
@return The game's score after the move. Return -1 if game over.
Game over when snake crosses the screen boundary or bites its body. */
public int move(String direction) {
if(score == -1) return -1;

//compute head
int rowHead = body.peekFirst() / width;
int colHead = body.peekFirst() % width;
switch(direction){
case "U":
rowHead--;
break;
case "D":
rowHead++;
break;
case "L":
colHead--;
break;
default:
colHead++;
}
int newHead = rowHead*width+colHead;

set.remove(body.peekLast());//we'll remove the tail from set for now to see if it hits its tail
//if it hits the boundary
if(set.contains(newHead) || rowHead < 0 || colHead < 0 || rowHead >= height || colHead >= width){
return score = -1;
}

//add head for the following two normal cases:
set.add(newHead);
body.offerFirst(newHead);

//normal eat case: keep tail, add head
if(foodIndex < food.length && rowHead == food[foodIndex][0] && colHead == food[foodIndex][1]){
set.add(body.peekLast());//old tail does not change, so add it back to set since we removed it earlier
foodIndex++;
return ++score;
}

//normal move case without eating: move head and remove tail
body.pollLast();
return score;

}
}

/**
* Your SnakeGame object will be instantiated and called as such:
* SnakeGame obj = new SnakeGame(width, height, food);
* int param_1 = obj.move(direction);
*/

Advertisements

Course Schedule II

https://leetcode.com/problems/course-schedule-ii/

  • Cool! Following that idea, I wrote this one completely by myself, nice!
  • Idea:
    • use a queue to hold all zero-degree vertex
    • loop through all other vertices, whenever one vertex’s indegree becomes zero, offer it into the q
    • when finished iterating the set, make sure to check if all indegree[] equals to zero, if not, that means there’s a cycle within the graph, in that case, just return an empty array as the problem requires, otherwise, return vertices in the queue
public int[] findOrder(int numCourses, int[][] prerequisites) {

int[] indegree = new int[numCourses];
for(int i = 0; i < prerequisites.length; i++){
indegree[prerequisites[i][0]]++;
}

Set<Integer> zeroDegree = new HashSet();
Queue<Integer> q = new LinkedList<Integer>();
for(int i = 0; i < numCourses; i++){
if(indegree[i] == 0) {
zeroDegree.add(i);
q.offer(i);
}
}

while(!zeroDegree.isEmpty()){
Iterator<Integer> it = zeroDegree.iterator();
int course = it.next();
zeroDegree.remove(course);
for(int[] edge : prerequisites){
if(edge[1] == course){
indegree[edge[0]]--;
if(indegree[edge[0]] == 0){
zeroDegree.add(edge[0]);
q.offer(edge[0]);
}
}
}
}

for(int i = 0; i < numCourses; i++){
if(indegree[i] != 0) return new int[0];
}

int[] order = new int[numCourses];
int i = 0;
while(!q.isEmpty() && i < numCourses){
order[i] = q.poll();
i++;
}

return order;

}

 

Shortest Distance from All Buildings

https://leetcode.com/problems/shortest-distance-from-all-buildings/

Inspired by this post: https://discuss.leetcode.com/topic/31925/java-solution-with-explanation-and-time-complexity-analysis

Kind of complex BFS, I guess this is why it’s rated as HARD.

As that post explains, it’s pretty straightforward to follow, I just need to be bold to think that we’ll have to do BFS for every single building (grid with value == 1) and calculate the distance for each one of them. Also:

  • count the total number of buildings during the outer most two for loops
  • update reach[][] array in each BFS
  • update distance[][] array in each BFS
  • how the shift[] array is ordered is super important and cannot be randomly changed, because it denotes how to get the four neighbors of each cell
  • don’t forget to add (grid[nextRow][nextCol] == 0) as one of the conditions in the innermost if condition
public int shortestDistance(int[][] grid) {
int m = grid.length;
if(m == 0) return -1;
int n = grid[0].length;
int[][] reach = new int[m][n];
int[][] distance = new int[m][n];
int[] shift = new int[]{0, 1, 0, -1, 0};//how these five elements is ordered is important since it denotes the neighbor of the current node
int numBuilding = 0;

for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 1){
numBuilding++;
int dist = 1;
boolean[][] visited = new boolean[m][n];

Queue<int[]> q = new LinkedList<int[]>();
q.offer(new int[]{i, j});
while(!q.isEmpty()){
int size = q.size();
for(int l = 0; l < size; l++){
int[] current = q.poll();
for(int k = 0; k < 4; k++){
int nextRow = current[0] + shift[k];
int nextCol = current[1] + shift[k+1];
if(nextRow >= 0 && nextRow < m && nextCol >= 0
&& nextCol < n && !visited[nextRow][nextCol] && grid[nextRow][nextCol] == 0){
distance[nextRow][nextCol] += dist;
visited[nextRow][nextCol] = true;
reach[nextRow][nextCol]++;
q.offer(new int[]{nextRow, nextCol});
}
}
}
dist++;
}
}
}
}

int result = Integer.MAX_VALUE;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 0 && reach[i][j] == numBuilding && distance[i][j] < result){
result = distance[i][j];
}
}
}
return result == Integer.MAX_VALUE ? -1 : result;
}