Follow up for “Unique Paths”: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the middle of a 3x3 grid as illustrated below. [ [0,0,0], [0,1,0], [0,0,0] ] Solution: public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int[][] dp

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there? Solution: public class Solution { public int uniquePaths(int m, int n)

Reverse a singly linked list. Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode reverseList(ListNode head) { ListNode cur=head, reverse=null; while(cur!=null){ ListNode tmp = cur.next; cur.next = reverse; reverse = cur; cur = tmp; } return reverse; } }

Reverse a linked list from position m to n. Do it in-place and in one-pass. For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL. Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list. Solution: first attempt /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { int i=0; ListNode scan=head, reverse=null; ListNode preNodeM = new ListNode(0); preNodeM.next = head; while(scan!=null){ i++; if(i==m-1) preNodeM=scan; if(i<m) { scan = scan.next; continue; } else if(i>n) { preNodeM.next.next = scan; preNodeM.next = reverse; break; } else { ListNode tmp = scan.next; scan.next = reverse; reverse = scan; scan = tmp; } } preNodeM.next = reverse; return m==1 ?

Rotate an array of n elements to the right by k steps. For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]. Solution: public class Solution { public void rotate(int[] nums, int k) { k = k%nums.length; reverse(nums, 0, nums.length-k-1); reverse(nums, nums.length-k, nums.length-1); reverse(nums, 0, nums.length-1); } public void reverse(int[] nums, int l, int r){ while(l<r){ int tmp = nums[l]; nums[l++] = nums[r];

Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL. Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode rotateRight(ListNode head, int k) { if(head==null) return null; ListNode

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. For example, Given n = 3, You should return the following matrix: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] Solution: public class Solution { public int[][] generateMatrix(int n) { int[][] ans = new int[n][n]; int[][] dir = new int[][]{{0,1},{1,0},{0,-1},{-1,0}}; int[] step =

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] You should return [1,2,3,6,9,8,7,4,5]. Solution: public class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> ans = new ArrayList<>(); if(matrix.length==0) return ans; int[][] dir = new

Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. Solution: public class Solution { Set<Integer> col = new HashSet<>(); Set<Integer> diag1 = new HashSet<>(); Set<Integer> diag2 = new HashSet<>(); public int totalNQueens(int n) { return solve(0, n, 0); } public int solve(int row, int n, int count){ if(row==n) return count+1; for(int c=0; c<n; c++){ if(col.contains(c) || diag1.contains(row+c) || diag2.contains(row-c)) continue; col.add(c); diag1.add(row+c);

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively. For example, There exist two distinct solutions to the 4-queens puzzle: [