Binary Tree Inorder Traversal – leetcode

Question:
Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Thought:
Use a stack and a pointer cur. if cur !=null and stack not empty, keep looping. cur=cur.left. if cur==null, means we reached the leaf, pop from stack, put in the result list and cur=cur.right;

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result= new ArrayList<>();
        if(root==null) return result;
        Stack<TreeNode> stack= new Stack<>();
        TreeNode cur= root;
        
        while(!stack.isEmpty()||cur!=null){//bug
            if(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }else{
                cur=stack.pop();
                result.add(cur.val);
                cur=cur.right;
            }
        }
        return result;
    }

Reverse Linked List II – leetcode

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

Thought:
Keep a counter and a pointer pre, when counter met m, assign pre to current tail, start reversing use a different way to insert to dum list. When counter is equals to n+1, start inserting to the tail again.

        if(head==null) return null;
        int count=1;
        ListNode dum= new ListNode(-1);
        ListNode re=dum;
        ListNode pre=null;
        while(head!=null){
            ListNode next=head.next;
            if(count==m) pre=head;
            if(count==n+1) dum=pre;
            if(count>=m&&count<=n){
                head.next=dum.next;
                dum.next=head;
            }else{
                dum.next=head;
                head.next=null;
                dum=dum.next;
            }
            count++;
            head=next;
        }
        return re.next;
        
    

Decode Ways – leetcode

Question:
A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

Thought:
One dimension DP. Use array to represent how many ways to decode. if s.charAt(i) is a valid number, dp[i]=dp[i]+dp[i-1]; if s.substring(i-2,i) is a valid number dp[i]+=dp[i-2];

Need to pay attention to boundaries. Also there is a trick to have the length of the array to be s.length()+1, and plant 1 to the beginning of the array.

 public int numDecodings(String s) {
        if(s.length()==0) return 0;
        int[] dp= new int[s.length()+1];    
        dp[0]=1;
        if(isValid(s.substring(0,1))){
            dp[1]=1;
        }else{
            dp[1]=0;
        }
        for(int i=2;i<dp.length;i++){//bug
           if(isValid(s.substring(i-1,i))){//bug
                dp[i]+=dp[i-1];
            }
            if(isValid(s.substring(i-2,i))){//bug
                dp[i]+=dp[i-2];   
            }
        }
        return dp[dp.length-1];
    }
    
    public boolean isValid(String s){
        if(s.charAt(0)=='0') return false;
        int a=Integer.valueOf(s);
        return a>0&&a<=26;
    }        

Same Tree – leetcode

Question:
Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Thought:
Check the current treeNode value is the same, then do the same to left tree and right sub tree.
Note need to consider all the base case.

 public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null) return true;
        if(p==null) return q==null;
        if(q==null) return p==null;
        if(p.val!=q.val){
            return false;
        }
        return  isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }

Scramble String – leetcode

Question:

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = “great”:

great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that “rgeat” is a scrambled string of “great”.

Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.

rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
We say that “rgtae” is a scrambled string of “great”.

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Thought:
Recursion is the most easiest way to do this. Because we don’t know at which point the string got scrambled, so we need to start the second position, split string to two halves and do the same to s2, and check to see if both splited string are scrambled.

In order to avoid TLE, we can sort both string, if their sorted version are not the same, then return false.
Note there are two ways to scramble s2. Start from beginning or start from the end.

Code:

 public boolean isScramble(String s1, String s2) {
        if (s1.length () != s2.length ())
            return false;
        if (s1.equals (s2))
            return true;
        char[] c1 = s1.toCharArray ();
        char[] c2 = s2.toCharArray ();
        Arrays.sort (c1);
        Arrays.sort (c2);
        if (!new String (c1).equals (new String (c2)))
            return false;
        for (int i = 1; i < s1.length (); i++) {
            String s11 = s1.substring (0, i);
            String s12 = s1.substring (i);
            String s21 = s2.substring (0, i);
            String s22 = s2.substring (i);
            if (isScramble (s11, s21) && isScramble (s12, s22))
                return true;
            s21 = s2.substring (s2.length () - i);
            s22 = s2.substring (0, s2.length () - i);
            if (isScramble (s11, s21) && isScramble (s12, s22))
                return true;
        }
        return false;
    }

Merge Sorted Array – leetcode

Question:
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

Thought:
Straight forward solution is to start from end, and merge to nums1.

Note, we need to use index for both array. This way will better avoid out of bound.

Code:

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (nums1 == null || nums2 == null || nums2.length == 0 || nums1.length == 0)
            return;
        while(m-1>=0&&n-1>=0){
            if(nums1[m-1]<nums2[n-1]){
                nums1[m+n-1]=nums2[n-1];
                n--;
            }else{
                nums1[m+n-1]=nums1[m-1];
                m--;
            }
        }
        while(n>0){
            nums1[m+n-1]=nums2[n-1];//bug
            n--;//bug
        }        
    }
 

Gray Code – leetcode

Question:
The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 – 0
01 – 1
11 – 3
10 – 2
Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Thought:
This question, you need to draw an example to see the pattern.

The pattern is for sequence for n, it is 0+sequence n-1 + 1+sequence n-1 in reverse order

To calculate the result, for the second part, we just need to reverse the order and plus 1<<n-1

public List <Integer> grayCode (int n) {
if (n == 0)
return Arrays.asList (0);
if (n == 1)
return Arrays.asList (0, 1);
List <Integer> re = grayCode (n – 1);
int tmp = 1 << n – 1;
List <Integer> re1 = new ArrayList <> (re);
for (int i = re.size () – 1; i >= 0; i–) {
re1.add (tmp + re.get (i));
}
return re1;
}

Largest Rectangle in Histogram – leetcode

Question:
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Thought:
Take above as example, when we calculate area, we can only go from bigger height to smaller height. Not the other way around.

Thus, we use a stack to keep track of the index. When we pushing each index to the stack, if we find the one we are about to push (let’s say index is right) is lower than the top one in the stack, we pop the top one and calculate area using the top height. area=height[top]*(right-1-(stack.peek()+1)+1);

We repeat the same operation until the top of the stack is smaller than the one we want to push. Than push the current one.

When we finished pushing the stack, for each height left in the stack, their right bound will be (length-1), their left bound will be stack.peek()+1. We keep popping the stack and calculate the area for each height.

    public int largestRectangleArea(int[] height) {
        int max=0;
        Stack<Integer> stack= new Stack<>();
        for(int i=0;i<height.length;i++){
            if(stack.isEmpty()) {stack.push(i);}
            else if(height[stack.peek()]>height[i]){
                while(!stack.isEmpty()&&height[stack.peek()]>height[i]){
                   int j=stack.pop();
                    int left=0;
                   if(!stack.isEmpty()){
              left=stack.peek()+1;
            }
                   max=Math.max(max,height[j]*(i-left));
                }
            }
                stack.push(i);
        }
        while(!stack.isEmpty()){
            int j=stack.pop();
            int left=0;
            if(!stack.isEmpty()){
              left=stack.peek()+1;
            }
            max=Math.max(max,height[j]*(height.length-left));
        }
        return max;
    }

Remove Duplicates from Sorted List II – leetcode

Question:
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Thought:
1. 2 pointers. 1 pre and 1 cur. If pre==cur, cur=cur.next until cur!=pre. Then pre=cur, cur=cur.next;
2. if pre!=cur, then we attach pre to dum. pre=pre.next, cur=cur.next
Things need attention, after the loop, we also need to check is pre==null, there is a chance that pre still not null. eg. [1,2] , End of the loop, pre=2, cur=null. we need to attach pre in the last;

    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode pre=head;
        ListNode cur=head.next;
        ListNode dum= new ListNode(-1);
        ListNode re=dum;
        while(cur!=null){
            if(cur.val==pre.val){
                while(cur!=null&&cur.val==pre.val){
                    cur=cur.next;
                }
                pre=cur;
                if(cur!=null){cur=cur.next;}
            }else{
                ListNode next=pre.next;
                dum.next=pre;
                pre.next=null;
                pre=next;
                cur=cur.next; 
                dum=dum.next;
            }
        }
        dum.next=pre; //bug  [1,2]
        return re.next;
    }

Remove Duplicates from Sorted List – leetcode

Question:
Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Thought:
Straight forward the solution. Things need attention is don’t forget to null out head.next after connecting to dum node.

   public ListNode deleteDuplicates(ListNode head) {
        if(head==null) return null;
        ListNode dum= new ListNode(head.val-1);
        ListNode re=dum;
        while(head!=null){
            ListNode next=head.next;
            if(dum.val!=head.val){
                dum.next=head;
                dum=dum.next;
                head.next=null;
            }
            head=next;
        }
        return re.next;
    }