Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

Naive Way: Use a HashMap to note down the mapping. Also use .containsKey and .containsValue function to check duplicates. The point being easily ignored is the value also needs to be uniquely mapped. No two characters can map to the same value.

 public class Solution {  
   public boolean isIsomorphic(String s, String t) {  
     Map<Character, Character> map = new HashMap<Character, Character>();  
     for(int i = 0;i < s.length();i++){  
       if(map.containsKey(s.charAt(i))){  
         if(t.charAt(i)!=map.get(s.charAt(i))) return false;  
       }else{  
         if(map.containsValue(t.charAt(i))) return false;  
         map.put(s.charAt(i), t.charAt(i));  
       }  
     }  
     return true;  
   }  
 }  

Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5


Naive Way: It is the most common way of manipulating linked list. But as for linked list, null pointer will always be a problem.

As usual, I use a fake head pointer to make my code more smooth.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public ListNode removeElements(ListNode head, int val) {  
     ListNode fake = new ListNode(0);  
     ListNode pre = fake;  
     fake.next = head;  
     while(pre.next!=null){  
       ListNode cur = pre.next;  
       if(cur.val==val)  
         pre.next = cur.next; // remove the node  
       else  
         pre = cur;  
     }  
     return fake.next;  
   }  
 }  

Happy Number

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² + 9² = 82
• 8² + 2² = 68
• 6² + 8² = 100
• 1² + 0² + 0² = 1

Naive Way: The statement is describing a recursive process. So it is obvious that the question want me to write a recursive method. The logic has been stated and clear. Base case (ending condition) is either n=1 or n has been visited. And since I need to mark whether a number has been visited, a hashset is required.

 public class Solution {  
   Set<Integer> visited = new HashSet<Integer>();  
   public boolean isHappy(int n) {  
     // base case  
     if(n==1) return true;  
     // visited  
     if(visited.contains(n)) return false;  
     // main processing  
     int sum = 0;  
     visited.add(n);  
     while(n!=0){  
       int lastDigit = n % 10;  
       sum += lastDigit * lastDigit;  
       n /= 10;  
     }  
     return isHappy(sum);  
   }  
 }  

Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.

Naive Way: My first thought was to use "&" operation going though all numbers between m and n inclusively. That gets a TLE. I later wrote some test cases and find out that "&" operation is hard to keep even one bit when there is a gap between n and m.
For example: 4-8: 0100, 0101, 0110, 0111, 1000. result is 0000.
It turns out that m and n need to have same highest bit, otherwise the result will be 0.

I tried many times and finally find out that a method use only bit shift operation will do the trick. Any ">" or "<" compare condition will possibly ruin he algorithm because 0x80000000 is a negative number.

My method is a recursive one. The idea is keep finding highest bit of m, check if n has a higher bit. And let the recursive call do the rest bits.

 public class Solution {  
   public int rangeBitwiseAnd(int m, int n) {  
     return rangeBitwiseAnd(m,n,0x80000000);  
   }  
     
   private int rangeBitwiseAnd(int m, int n, int shift){  
       
     // edge case  
     if(m==0) return 0;  
       
     // find highest bit of m  
     while((shift & m) == 0){  
       if((shift & n) != 0) return 0;  
       shift >>>= 1;  
     }  
       
     return shift + rangeBitwiseAnd(m - shift, n - shift, shift);  
   }  
 }  

Improved Way: After viewing the Discuss, I find there are tons of lot better solutions.

One is from applewolf, who find out that keep comparing from lower bits to higher bits can do the trick.

 int rangeBitwiseAnd(int m, int n) {  
   return (n > m) ? (rangeBitwiseAnd(m/2, n/2) << 1) : m;  
 }  

Another is from haw64, who find out that the result of AND operation is just left most consecutive common part of n and m (just two numbers, no need of numbers in between).

 public int rangeBitwiseAnd(int m, int n) {  
     int count = 0;  
     while(m != n){  
       m >>= 1;  
       n >>= 1;  
       count++;  
     }  
     return m<<=count;  
   }  

Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:

11110
11010
11000
00000

Answer: 1
Example 2:

11000
11000
00100
00011

Answer: 3

Naive Way: Use DFS to go though all grid cells. Use a hashset to keep visited grid cells. Run time is O(n^2). And space is O(n^2).

 public class Solution {  
   public int numIslands(char[][] grid) {  
     Set<List<Integer>> visited = new HashSet<List<Integer>>();  
     int num = 0;  
     for(int i = 0;i < grid.length;i++)  
       for(int j = 0;j < grid[0].length;j++)  
         num+=dfs(grid,i,j,visited);  
     return num;  
   }  
   private int dfs(char[][] grid, int x, int y, Set<List<Integer>> visited){  
     // edge case  
     if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) return 0;  
     // island  
     if(grid[x][y] == '1'){  
       List<Integer> list = new ArrayList<Integer>();  
       list.add(x);  
       list.add(y);  
       if(!visited.contains(list)){  
         visited.add(list);  
         dfs(grid, x-1, y, visited);  
         dfs(grid, x+1, y, visited);  
         dfs(grid, x, y-1, visited);  
         dfs(grid, x, y+1, visited);  
         return 1;  
       }  
     }  
     return 0;  
   }  
 }  

I saw a algorithm in Discuss use the original grid to store visited grid cells. Thus reduce space used to O(1).