Binary Tree Right Side View – leetcode

Question:
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,
1 <—
/ \
2 3 <—
\ \
5 4 <—
You should return [1, 3, 4].

Thought:
Same as level order traverse. Use a Queue. when queue is empty, add cur.val to result.

public List<Integer> rightSideView(TreeNode root) {
List<Integer> aList= new ArrayList<>();
Queue<TreeNode> q= new LinkedList<>();
Queue<TreeNode> q2= new LinkedList<>();
if(root!=null) q.add(root);
while(!q.isEmpty()){
TreeNode cur=q.poll();
if(cur.left!=null) q2.add(cur.left);
if(cur.right!=null) q2.add(cur.right);
if(q.isEmpty()){
aList.add(cur.val);
q=q2;
q2=new LinkedList<>();
}
}
return aList;
}

Number of Islands – leetcode

Question:
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

Thought:
BFS. Use a boolean matrix to keep track whether a element is visited or not. When we finish one BFS, count of island++.

    public int numIslands(char[][] grid) {
        if(grid==null||grid.length==0||grid[0].length==0) return 0;
        int row=grid.length;
        int col=grid[0].length;
        boolean[][] isVisited= new boolean[row][col];
        int[] result=new int[1];
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(!isVisited[i][j]){
                bfs(grid,i,j,isVisited,result);}
            }
        }
        return result[0];
    }

    public void bfs(char[][]grid, int x, int y, boolean[][] isVisited,int[]result){
           if(grid[x][y]=='0') return;
           int row=grid.length;
           int col=grid[0].length;
            Queue<Cor> q= new LinkedList<>();
            q.add(new Cor(x,y));
        while(!q.isEmpty()){
            Cor c=q.poll();
            isVisited[c.x][c.y]=true;
            if(c.x-1>=0&&grid[c.x-1][c.y]=='1'&&!isVisited[c.x-1][c.y]){
                isVisited[c.x-1][c.y]=true;
                q.add(new Cor(c.x-1,c.y));
            }
            if(c.x+1<row&&grid[c.x+1][c.y]=='1'&&!isVisited[c.x+1][c.y]){
                isVisited[c.x+1][c.y]=true;
                q.add(new Cor(c.x+1,c.y));
            }
            if(c.y-1>=0&&grid[c.x][c.y-1]=='1'&&!isVisited[c.x][c.y-1]){
                isVisited[c.x][c.y-1]=true;
                q.add(new Cor(c.x,c.y-1));
            }
            if(c.y+1<col&&grid[c.x][c.y+1]=='1'&&!isVisited[c.x][c.y+1]){
                isVisited[c.x][c.y+1]=true;
                q.add(new Cor(c.x,c.y+1));
            }
        }
        result[0]+=1;
    }

    public class Cor{
        int x;
        int y;
        public Cor(int x, int y){
            this.x=x;
            this.y=y;
        }
    }

Happy Number – leetcode

Question:
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

12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Thought:
Use hashset to record whether number has appeared or not.

    public boolean isHappy(int n) {
        Set <Long> aSet = new HashSet <> ();
        long a=(long) n;
        while (a != 1) {
            long re = 0;
            while (a > 0) {
                long val = a % 10;
                re += val * val;
                a = a / 10;
            }
            if (aSet.contains (re))
                return false;
            else {
                aSet.add (re);
            }
            a =  re;
        }
        return true;
    }

Isomorphic Strings – leetcode

Question:
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.

Note:
You may assume both s and t have the same length.

Thought:
Use hashMap to represent char mapping relationship. Note this is two direction mapping. Not one way mapping. eg. “ab” “aa” should return false.

    public boolean isIsomorphic(String s, String t) {
        if (s == null || s.length () == 0)
            return true;
        Map <Character, Character> aMap = new HashMap <> ();
        Map <Character, Character> bMap = new HashMap <> ();
        for (int i = 0; i < s.length (); i++) {
            char c1 = s.charAt (i);
            char c2 = t.charAt (i);
            if (aMap.containsKey (c1)) {
                if (aMap.get (c1) != c2) {
                    return false;
                }
            }
            if (bMap.containsKey (c2)) {
                if (bMap.get (c2) != c1) {
                    return false;
                }
            }
            aMap.put (c1, c2);
            bMap.put (c2, c1);
        }
        return true;
    }

Rotate Array — leetcode

Question:
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].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Thought:
Reverse the whole array, reverse the first k, then reverse the rest array.O(2n)

    public void rotate(int[] nums, int k) {
        int len=nums.length;
        k=k%len;
        revert(nums,0,len-1);
        revert(nums,0,k-1);
        revert(nums,k,len-1);
    }

    public void revert(int[] nums, int start,int end){
        while(start<end){
            int tmp=nums[start];
            nums[start]=nums[end];
            nums[end]=tmp;
            start++;
            end--;
        }
    }

Clone Graph

Question:
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

1
/ \
/ \
0 — 2
/ \
\_/

Thought:
BFS. Use hashMap to keep track of newly created node. If hashMap contains the node we are about to visit, it means we already visited this node, then do not add to the queue.

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node==null) return null;
        Map<Integer,UndirectedGraphNode> aMap= new HashMap<>();
        Queue<UndirectedGraphNode> q= new LinkedList<>();
        q.add(node);
        while(!q.isEmpty()){
            UndirectedGraphNode cur=q.poll();
            if(!aMap.containsKey(cur.label)){
                aMap.put(cur.label,new UndirectedGraphNode(cur.label));
            }
            
            for(UndirectedGraphNode n:cur.neighbors){
                if(!aMap.containsKey(n.label)){
                    q.add(n);
                    aMap.put(n.label,new UndirectedGraphNode(n.label));
                }
                    aMap.get(cur.label).neighbors.add(aMap.get(n.label));
            }
        }
        return aMap.get(node.label);
        
    }

Palindrome Partitioning II – leetcode

Question:
Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = “aab”,
Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

Thought:
dp[i][j] represents s.substring(i,j+1) is palindrome or not. dp2[i] represents s.substring(i-s.length()) min palindrome cut. if dp[i][j]==true, dp2[i]=Math.min(dp2[i],dp2[j+1]+1);

    public int minCut(String s) {
        if(s==null) return -1;
        int len=s.length();
        if(len<=1) return 0;
        boolean [][] dp= new boolean[len][len];
        int[] re= new int[len+1]; //bug, we use the additional position to be a start buffer
        for(int i=0;i<len;i++){
            re[i]=len-i;
        }

        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){
                if(s.charAt(i)==s.charAt(j)&&(j-i<2||dp[i+1][j-1])){
                    dp[i][j]=true;
                    re[i]=Math.min(re[i],re[j+1]+1);
                }
            }
        }
        return re[0]-1;
    }

Word Ladder II – leetcode

Question:
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,

Given:
start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]
Return
[
[“hit”,”hot”,”dot”,”dog”,”cog”],
[“hit”,”hot”,”lot”,”log”,”cog”]
]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.

Thought:
We cannot use hashmap to trace back as using that will miss some result set. Because when do word ladder 1, after we find transformed word that match dictionary, we remove from dictionary, that will lead to missing result set.

    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        Queue <String> q = new LinkedList <> ();
        q.add (start);
        dict.add (end);
        Map <String, Set <List <String>>> bt = new HashMap <> ();
        Set <List <String>> startSet = new HashSet <> ();
        List <String> startPath = new ArrayList <> ();
        startPath.add (start);
        startSet.add (startPath);
        bt.put (start, startSet);
        List <List <String>> result = new ArrayList <> ();
        while (!q.isEmpty ()) {
            String str = q.poll ();
            if (str.equalsIgnoreCase (end)) {
                result.addAll (bt.get (str));
                return result;
            }
            List <String> strList = transform (str);
            for (String newStr: strList) {
                if (dict.contains (newStr)) {
                    if (!bt.containsKey (newStr)) {
                        Set <List <String>> strSet = bt.get (str);
                        Set <List <String>> newStrSet = new HashSet <> ();
                        for (List <String> re: strSet) {
                            List <String> newList = new ArrayList <> (re);
                            newList.add (newStr);
                            newStrSet.add (newList);
                        }
                        bt.put (newStr, newStrSet);
                        q.add (newStr);
                        
                    } else {
                        Set <List <String>> strSet = bt.get (str);
                        Set <List <String>> newStrSet = bt.get (newStr);
                        Iterator <List <String>> oldSet = strSet.iterator ();
                        Iterator <List <String>> newSet = newStrSet.iterator ();
                        if (oldSet.next ().size () + 1 == newSet.next ().size ()) {
                            for (List <String> oldPath: strSet) {
                                List <String> newPath = new ArrayList <> (oldPath);
                                newPath.add (newStr);
                                newStrSet.add (newPath);
                            }
                            bt.put (newStr, newStrSet);
                        }
                    }
                }
            }
        }
        return result;
    }
    
     private List <String> transform (String str) {
        List <String> result = new ArrayList <> ();
        for (int i = 0; i < str.length (); i++) {
            for (int j = 0; j < 26; j++) {
                StringBuilder sb = new StringBuilder (str);
                sb.setCharAt (i, (char) ('a' + j));
                result.add (sb.toString ());
            }
        }
        return result;
    }

Word Ladder – leetcode

Question:
Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,

Given:
start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]
As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.

Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

Thought:
BFS, use a hashmap to trace back the path once we find endWord. For each word, we transform them by changing one char at a time.

    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
       int count=0;
        Map<String,String> aMap= new HashMap<>();
        Queue<String> q= new LinkedList<>();
        q.add(beginWord);
        while(!q.isEmpty()){
            String s=q.poll();
            Set<String> aSet= transform(s);
            for(String s1:aSet){
                if(wordDict.contains(s1)){
                    aMap.put(s1,s);
                    if(s1.equals(endWord)){
                        while(!aMap.get(s1).equals(beginWord)){
                            count++;
                            s1=aMap.get(s1);
                        }
                        return count+2;
                    }
                        q.add(s1);
                    wordDict.remove(s1);
                }
            }
        }
        return 0;
    }
     public Set<String> transform(String s){
        Set<String> re= new HashSet<>();
        for(int i=0;i<s.length();i++){
            char[] c= s.toCharArray();
            for(int j=0;j<26;j++){
                char a=(char)('a'+j);
                c[i]=a;
                String s1= new String(c);
                re.add(s1);
            }
        }
        return re;
    }

Surrounded Regions – leetcode

Question:
Given a 2D board containing ‘X’ and ‘O’, capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Thought:
BFS, first go through 4 bounds of the matrix, if ‘O’ found, do BFS to mark all adjacent ‘O’ to ‘Y’. (These ‘O’ will not be surrounded by ‘X’)

Then we iterate matrix again, mark all ‘O’=’X’, all ‘Y’=’O’.

Note, we use a boolean matrix to mark the visited element in BFS, this will help program run faster. If we don’t use boolean matrix, same element will be enqueue more than once.

    public void solve(char[][] board) {
        if(board==null||board.length==0||board[0].length==0) return;
        int row=board.length;
        int col=board[0].length;
        boolean [][] isVisited = new boolean[row][col];
        for(int i=0;i<col;i++){
               mark(board,0,i,isVisited);
               mark(board,row-1,i,isVisited);
        }
        for(int i=0;i<row;i++){
                mark(board,i,0,isVisited);
                mark(board,i,col-1,isVisited);   
        }
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(board[i][j]=='O'){
                    board[i][j]='X';
                }
                if(board[i][j]=='Y'){
                    board[i][j]='O';
                }
            }
        }
    }
    
    public void mark(char[][]board,int x,int y,boolean[][] isVisited){
        if(board[x][y]!='O') return;
        Queue<Cor> q= new LinkedList<>();
        q.add(new Cor(x,y));
        int row=board.length;
        int col=board[0].length;
        while(!q.isEmpty()){
            Cor c=q.poll();
            board[c.x][c.y]='Y';
            isVisited[c.x][c.y]=true;
            if(c.x-1>=0&&board[c.x-1][c.y]=='O'&&!isVisited[c.x-1][c.y]){
                    q.add(new Cor(c.x-1,c.y));
                    isVisited[c.x-1][c.y]=true;
            }
            if(c.x+1<row&&board[c.x+1][c.y]=='O'&&!isVisited[c.x+1][c.y]){
                q.add(new Cor(c.x+1,c.y));
                isVisited[c.x+1][c.y]=true;
            }
           if(c.y-1>=0&&board[c.x][c.y-1]=='O'&&!isVisited[c.x][c.y-1]){
                    q.add(new Cor(c.x,c.y-1));
                    isVisited[c.x][c.y-1]=true;
            }
           if(c.y+1<col&&board[c.x][c.y+1]=='O'&&!isVisited[c.x][c.y+1]){
                    q.add(new Cor(c.x,c.y+1));
                    isVisited[c.x][c.y+1]=true;
            }            
        }
    }
   public class Cor{
        int x;
        int y;
        public Cor(int x, int y){
            this.x=x;
            this.y=y;
        }
    }