Lintcode review(7)

Posted on | In |

Hhh I will change to Lintcode for a while~

Lintcode 626 Rectangle Overlay

Description:

Given two rectangles, find if the given two rectangles overlap or not.

Methods:

If we classify different situations for overlap, that would be a huge amount of work.

So we can consider when these two squares are not overlapped.

Code:

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
/**
 * Definition for a point.
 * class Point {
 *     public int x, y;
 *     public Point() { x = 0; y = 0; }
 *     public Point(int a, int b) { x = a; y = b; }
 * }
 */
 
 
public class Solution {
    /*
     * @param l1: top-left coordinate of first rectangle
     * @param r1: bottom-right coordinate of first rectangle
     * @param l2: top-left coordinate of second rectangle
     * @param r2: bottom-right coordinate of second rectangle
     * @return: true if they are overlap or false
     */
    public boolean doOverlap(Point l1, Point r1, Point l2, Point r2) {
        // write your code here
        if( l1.y < r2.y || r1.y>l2.y)
            return false;
        if( l1.x > r2.x || r1.x < l2.x)
            return false;
        
        return true;
    }
}

Lintcode 628 Maximum Subtree

Description:

Given a binary tree, find the subtree with maximum sum. Return the root of the subtree.

Methods:

Divide the work into two parts:

  1. to calculate the sum of each node and its childnodes;
  2. to update maxinum and the TreeNode.

So we need to use global variables.

Code:

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
public class Solution {
    /*
     * @param root: the root of binary tree
     * @return: the maximum weight node
     */
     
    private TreeNode resNode=null;
    private int maxSum=Integer.MIN_VALUE;
    public TreeNode findSubtree(TreeNode root) {
        // write your code here
        if(root==null) return null;
        
        MaxSum(root);
        return resNode;
    }
    private int MaxSum(TreeNode root){
        if(root==null) return 0;
        
        int left = MaxSum(root.left);
        int right = MaxSum(root.right);
        
        int sum = left+right+root.val;
        
        if(sum>maxSum){
            maxSum=sum;
            resNode = root;
        }
        return sum;
        
    }
}

Lintcode 627 Longest Palindrome

Description:

Given a string whichconsists of lowercase or uppercase letters, find the length of the longestpalindromes that can be built with those letters.

This is case sensitive, forexample “Aa” is not considered apalindrome here.

Methods:

Not very hard. Use hash and to count even and odd number.

But the most important is that ! Get even by substract one from odd!!

Code:

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
public class Solution {
    /*
     * @param s: a string which consists of lowercase or uppercase letters
     * @return: the length of the longest palindromes that can be built
     */
    public int longestPalindrome(String s) {
        // write your code here
       
        int l = s.length();
        if(l<=1) return l;
      
        int[] hash = new int[256];
        char[] sc = s.toCharArray();
      
        for(char c:sc)
            hash[c]++;
        
        int max=0;
        int sum=0;
        boolean flag=false;
        for(int d:hash){
            if(d%2==0)
                sum+=d;
            else{
                sum+=d-1;
                flag=true;
            }
            
        }
        if(flag)
            return sum+max+1;
        return sum+max;
    }  
}