Leetcode Review(2)

Posted on | In |

突然得知19号就是career fair, 吓得我精神抖擞。

一定要坚持！！

Leetcode 98 Validate Binary Search Tree

Description:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume aBST is defined as follows:

The leftsubtree of a node contains only nodes with keys less than the node’s key.

The rightsubtree of a node contains only nodes with keys greater than the node’s key.

Both theleft and right subtrees must also be binary search trees.

Methods:

想法就是，按照中序遍历的顺序遍历这个binary tree, 然后check是否node的值是递增的（！注意，不是非减）

需要栈的辅助（非递归的中序遍历）

并且使while循环不断进行的条件是：

1
2
3
4
5
while(!stack.isEmpty() || root!=null)
while(root!=null)
{
	left node blah
}

运行到整棵树的根节点和一开始的时候，会出现stack.isEmpty()==true的情况，但此时root!=null;

其他时候都是root会等于null，但是stack非空。

节点值比较小，所有用long作为tmp的type。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        long tmp = Long.MIN_VALUE;
        
 
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
            stack.push(root);
            root = root.left;    
        }
            root = stack.pop();
            if(root.val<=tmp) return false;
            tmp = root.val;
            root = root.right;
        }
        return true; 
    }
}

大佬，我是真的不会dfs。

Leetcode 4 Median of Two Sorted Arrays

Description:

Thereare two sorted arrays nums1 and nums2 of size m and n respectively.

Find the medianof the two sorted arrays. The overall run time complexity should be O(log(m+n)).

Methods:

这题，我是脑子真的转不过来。

先用最土的方法吧: Merge sort. Find the median.

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
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
        int l1 = nums1.length;
        int l2 = nums2.length;
        if(l1==0) return l2%2==0?(nums2[l2/2]+nums2[l2/2-1])/2.0:nums2[l2/2];
        if(l2==0) return l1%2==0?(nums1[l1/2]+nums1[l1/2-1])/2.0:nums1[l1/2];
        
        int[] aux = new int[l1+l2];
        
        int i=0;
        int j=0;
        int k=0;
        while(i<l1 || j<l2){
            if(i<l1 && j<l2){
                if(nums1[i]<nums2[j])
                    aux[k++]=nums1[i++];
                else
                    aux[k++]=nums2[j++];
            }
            else if(i>=l1)
                aux[k++]=nums2[j++];
            else if(j>=l2)
                aux[k++]=nums1[i++];
            
        }
        return (l1+l2)%2==0?(aux[(l1+l2)/2]+aux[(l1+l2)/2-1])/2.0:aux[(l1+l2)/2];
        
    }
}

改天回来再做！

Leetcode 7 Reverse Integer

Description:

Given a 32-bit signed integer, reverse digits of an integer.

Methods:

这题比较简单

但是有一个tricky的地方，就是如何判断是否overflow

可以在每次乘10的时候，比较乘10之前和乘10之后的除了个位之外的数是否相同。

如果不同，就是溢出了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int reverse(int x) {
        int rev=0;
        while(x!=0){
            int tail = rev;
            rev = rev*10+x%10;
            if(tail!=rev/10) return 0;
            x=x/10;           
        }
        return rev;      
    }
}

闲话：

网页快做来不及啦！！