Han Zhu's Study Notes

Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must 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 in a word. For example, Given  words  =  ["oath","pea","eat","rain"]  and  board  = [ [' o ',' a ','a','n'], ['e',' t ',' a ',' e '], ['i',' h ','k','r'], ['i','f','l','v'] ] Return  ["eat","oath"] . Note: You may assume that all inputs are consist of lowercase letters  a-z . click to show hint. You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier? If the current candidate does not exist in all words' prefix, you could stop bac...

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 . Thought process: Iterate through every character. For each character, if it matches the first character of word, change the character to a non-letter character to avoid it being reused, and do a DFS on it. Iterate through four directions (top, right, bottom, left). If any neighbor matches the next character of word, changed the character to 0, and do a DFS on that ...

Write an algorithm to determine if a number is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers. Example:  19 is a happy number 1 2  + 9 2  = 82 8 2  + 2 2  = 68 6 2  + 8 2  = 100 1 2  + 0 2  + 0 2  = 1 Thought process: Use a hashset to record every number. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 public class Solution { public boolean isHappy ( int n ) { Set < Integer > set = new HashSet <>(); while ( true ) { int sum = 0 ; while ( n > 0 ) { i...

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and  it will automatically contact the police if two adjacent houses were broken into on the same night . Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight  without alerting the police . Thought process: Dynamic programming: Sub-problem: the maximum amount of money I can rob from a sub-array of houses. Function: f[i] = max(f[i - 2] + money[i], f[i - 1]). Initialization: f[0] = money[0]; f[1] = max(f[0], f[1]). Answer: f[f.length - 1] Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public class Solution { public int rob ( int [] nums ) { if ( nums . length == 0 ) { r...

Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in binary as  00000010100101000001111010011100 ), return 964176192 (represented in binary as  00111001011110000010100101000000 ). Follow up : If this function is called many times, how would you optimize it? Related problem:  Reverse Integer Thought process: Right shift the number until it's 0. For every bit, if it's 1, add n & 1 to the reversed number, and right-shift n. Because input number is a 32 bits unsigned integer, and Java int is 32 bits signed, I should not left-shift reversed if it's the last bit. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class Solution { // you need treat n as an unsigned value public int reverseBits ( int n ) { int reversed = 0 ; for ( int i = 0 ; i < 32 ; i ++) { reversed += n & 1 ; n >>>= 1 ; ...

Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3 begin to intersect at node c1. Notes: If the two linked lists have no intersection at all, return  null . The linked lists must retain their original structure after the function returns. You may assume there are no cycles anywhere in the entire linked structure. Your code should preferably run in O(n) time and use only O(1) memory. Thought process: Iterate both linked lists twice: Get the lengths of both lists. Increment the longer list by the difference between the lists lengths. Iterate both lists again until their pointers collide. Solution 1 (Length): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 4...

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. Thought process: Divide and conquer, recursively attach left sub-tree and right sub-tree to root: Base case: when the array is empty, return null. Recurrence: root is at array's length / 2. Left sub-tree is the root of the first half of the array. Right sub-tree is the root of the second half of the array. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode sortedArrayToBST ( int [] nums ) { return sortedArrayToBST ( nums , 0 , nums . length ); } private TreeNode sortedArrayToBST ( int [] nums , int start , int end ) { if ( start == end ) { ...