Leetcode Review(4)

Posted on | In |

Leetcode 414 Third Maximum Number

Description:

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Methods:

We can use an auxiliary array to maintain the top3 value.

And go through the nums to get the top 3.

PS the aux array need to use LONG data type ,otherwise it would cause overflow.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int thirdMax(int[] nums) {
        long[] top = {Long.MIN_VALUE,Long.MIN_VALUE,Long.MIN_VALUE};
        //top3,top2,top1
        
        for(int num:nums){
            if(num>top[2]){
                top[0]=top[1];
                top[1]=top[2];
                top[2]=num;
            }
            else if(num<top[2]&&num>top[1]){
                top[0]=top[1];
                top[1]=num;
            }
            else if(num<top[1]&num>top[0])
                top[0]=num;
        }
        return top[0]==Long.MIN_VALUE ? (int)top[2]:(int)top[0];
                
            }
        }

Leetcode 236 Lowest Common Ancestor of a Binary Tree

Description:

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

1
2
3
4
5
6
7
     _______3______
    /              \
 ___5__          ___1__
/      \        /      \
6      _2       0       8
      /  \
      7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Methods:

This problem needs to use recurrence to solve. I still feel very anxious about recurrence. (Need to draw the picture to get the idea).

The method is very simple:

  • If p and q are in two different sides of root, root should be the LCA.
  • If p and q are in the same side of root, then the LCA would be in that side(recurrence)

Then how to design the recurrence??? How to write from scratch..

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        if(root==null) return root;
        
        if(root==p || root==q)
            return root;
        
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        
        if(left!=null && right!=null)
            return root;
        
        return left!=null?left:right;        
    }      
}

把它当一个黑盒子。从最通用的情况来考虑。

Leetcode 139 Word Break

Description:

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Methods:

Dynamic Programming again.LOL

p[i] stands for that whether there is a word break in substring of s[0:i].

So p[i]=true or not(p[j]+s[j:i]) j from 0 to i

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int l = s.length();
        boolean[] p = new boolean[l+1];
        p[0]=true;
        
        for(int i=1;i<l+1;i++){
            for(int j=0;j<i;j++){
                p[i]=p[j]&&wordDict.contains(s.substring(j,i));
                if(p[i])
                    break;
                }     
            }
        return p[l];          
        }
}