刷题记录

2/16/2018  update Loop through edges, connect nodes parents with union find. If their parents are equal, so there is a loop. Remember to check edges.length == n - 1, Union find can not check number of edges iterated. Solution: Still need to do path compression. It's faster. class Solution { public boolean validTree ( int n, int [][] edges) { int [] roots = new int [n]; for ( int i = 0 ; i < n; i ++ ) { roots[i] = i; } for ( int [] edge : edges) { int x = find(roots, edge[ 0 ]); int y = find(roots, edge[ 1 ]); if (x == y) return false; roots[x] = y; } return edges . length == n - 1 ; } private int find ( int [] roots, int n) { if (roots[n] != n) roots[n] = find(roots, roots[n]); return roots[n]; } } ---------------------------- ---------------------------- -----------------------...

1/31/2018 Solution: /** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { public UndirectedGraphNode cloneGraph ( UndirectedGraphNode node) { if (node == null) return null; // copy nodes Queue< UndirectedGraphNode > queue = new LinkedList<> (); Set< UndirectedGraphNode > set = new HashSet<> (); queue . offer(node); set . add(node); while ( ! queue . isEmpty()) { UndirectedGraphNode curNode = queue . poll(); for ( UndirectedGraphNode n : curNode . neighbors) { if (set . contains(n)) continue ; queue . offer(n); set . add(n); } } // map old and new nodes ...

Problem: Given an integer  n , generate a square matrix filled with elements from 1 to  n 2  in spiral order. For example, Given  n  =  3 , You should return the following matrix: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] Analysis: Spiral matrix的马甲。 Solution: class Solution { public int [][] generateMatrix ( int n) { int m = n; int [][] matrix = new int [m][n]; int [] dx = new int []{ 0 , 1 , 0 , - 1 }; int [] dy = new int []{ 1 , 0 , - 1 , 0 }; boolean [][] visited = new boolean [m][n]; int x = 0 , y = 0 ; int d = 0 ; for ( int i = 1 ; i <= n * n; i ++ ) { matrix[x][y] = i; visited[x][y] = true; int newx = x + dx[d]; int newy = y + dy[d]; if ( 0 <= newx && newx < m && 0 <= newy && newy < n && ! visited...

Problem: 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] . 10/4/2018 update 一开始是往右走，如果invalid，就要换方向。所以在一开始就加到结果里面比较合理。 ------------------- ------------------- ------------------- ------------------- ------------------- ------------------- ------------------- ------- Analysis: Since the direction is left -> down -> right -> up. It's intuitive that we come up with direction array. To maintain the boundary we can use a visited[m][n] matrix to help, no need to think about 4 different boundaries.  本来思路都自己想好了，但是看到要用visited matrix就放弃了。 Space is cheap! 这道题实现还挺有挑战的。 Solution： class Solution { public List< Integer > spiralOrder ( int [][] matrix) { List< Integer > res = new ArrayList<> (); ...

Solution: class Solution { public void solveSudoku ( char [][] board) { if (board == null || board . length == 0 || board[ 0 ] . length == 0 ) return ; solve(board); } public boolean solve ( char [][] board) { for ( int i = 0 ; i < board . length; i ++ ) { for ( int j = 0 ; j < board[ 0 ] . length; j ++ ) { if (board[i][j] == '.' ) { for ( char c = '1' ; c <= '9' ; c ++ ) { if (valid(board, i, j, c)) { board[i][j] = c; if (solve(board)) return true; else board[i][j] = '.' ; } } return false; } } } return true; } private boolean valid ( char [][] board, int row, int col, char c) {...

Search a 2D matrix  can be prerequisite for this problem. Use mid/n to get row index,  use mid%n to get column index. Maybe  Spiral Matrix  can use the same technique.  Solution 1: Row, column and cube can be checked in one loop. When checking ith row, by swaping i and j, can check ith column. Need to memorize the cube index calculation. Divide the board into 9 3x3. The rowIndex and colIndex are starting indexes of each 3x3. With this information is very easy to iterate through the 3x3 with j incrementing. class Solution { public boolean isValidSudoku ( char [][] board) { if (board == null || board[ 0 ] . length == 0 ) return false; for ( int i = 0 ; i < board . length; i ++ ) { Set< Character > rowSet = new HashSet<> (); Set< Character > colSet = new HashSet<> (); Set< Character > cubeSet = new HashSet<> (); ...

Problem: Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. For example, Given  board  = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word  =  "ABCCED" , -> returns  true , word  =  "SEE" , -> returns  true , word  =  "ABCB" , -> returns  false . Analysis: 6/6/2018 update: 这一遍居然忘了剪枝。。。直接调用4方向的dfs,比用dir 数组快得多 14ms.之前是21ms. 剪枝通常和检查处在同一个level上面。这道题的实现里面，检查是在dfs level,所以剪枝也是。一般基于树的dfs，检查和剪枝都在for 循环里面。 class Solution { int m; int n; public boolean exist ( char [][] board, String word) { if (board == null || board . length == 0 || board[ 0 ] . length == 0 ) re...

Problem: Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Input: Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 3/26/2018 update: Eliminate index and use stringbuilder will be faster. class Solution { public List< String > letterCombinations ( String digits) { List< String > res = new ArrayList<> (); String [] keys = { "" , "" , "abc" , "def" , "ghi" , "jkl" , "mno" , "pqrs" , "tuv" , "wxyz" }; if (digits == null || digits . length() == 0 ) return res; dfs(res, new StringBuilder (), keys, digits); return res; } private void dfs ...

Problem: Given  n  pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given  n  = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] Analysis: 5/9/2018 update: See graph below: First add left, is no doubt. The case when to add right is when left par remain is less than right par remain. Implementation with string builder to increase performance. Backtrack is at the current dfs method level. class Solution { public List< String > generateParenthesis ( int n) { List< String > res = new ArrayList<> (); dfs(res, n, n, new StringBuilder (), "" ); return res; } private void dfs ( List< String > res, int left, int right, StringBuilder sb, String par) { sb . append(par); if (left == 0 &...

Problem: Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example: Given  "25525511135" , return  ["255.255.11.135", "255.255.111.35"] . (Order does not matter) Analysis: It's very similar to  palindrome-partitioning , but implementation has to be very careful with corner cases.  Solution: items.size() > 4 is critical to backtrack.  class Solution { public List< String > restoreIpAddresses ( String s) { List< String > res = new ArrayList<> (); if (s . length() < 4 || s == null) return res; helper(res, new ArrayList<> (), s); return res; } private void helper ( List< String > res, List< String > items, String s) { if (items . size() == 4 && s . length() == 0 ) { res . add(convert(items)); return ; } ...

Problem： Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3  →  1,3,2 3,2,1  →  1,2,3 1,1,5  →  1,5,1 Analysis: 这题真无聊啊，这种类型的题面试如果之前没遇到过肯定挂。除非面试官提示规律，完全想不出来。 Solution: class Solution { public void nextPermutation ( int [] nums) { if (nums == null || nums . length == 0 || nums . length == 1 ) return ; int p = - 1 ; // partition index int c = - 1 ; for ( int i = nums . length - 2 ; i >= 0 ; i -- ) { if (nums[i] < nums[i + 1 ]) { p = i; break ; } ...

Problem: Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. 6/18/2018 update: Using N-Queens code template class Solution { int res; public int totalNQueens ( int n) { int [] queens = new int [n]; Arrays . fill(queens, - 1 ); dfs(queens, 0 ); return res; } private void dfs ( int [] queens, int row) { if (row == queens . length) { res ++ ; return ; } for ( int i = 0 ; i < queens . length; i ++ ) { if (isValid(queens, row, i)) { queens[row] = i; dfs(queens, row + 1 ); queens[row] = - 1 ; } } } private boolean isValid ( int [] queens, int row, int col) { // i is row for ( int i = 0 ; i < row; i ++ ) { if (queens[i] == col) ...