Leetcoder - Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this? Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

public class Solution {
    public int reverse(int x) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int y = 0;
        boolean neg = false;
        if(x<0) {
            x *= -1;
            neg = true;
        }
        while(x!=0) {
            y *=10;
            int t = x%10;
            x = (x-t)/10;
            y += t;
        }
        if(neg) {
            y *= -1;
        }
        return y;
    }
}

public class Solution {
    public int reverse(int x) {
        if (x==0) {
            return 0;
        }
        boolean neg = x<0;
        long x2 = x;
        if(neg) {
            x2 = -x2;
        }
        long y = 0;
        while (x2!=0) {
            y *= 10;
            y += x2%10;
            x2 = x2/10;
        }
        if(neg) {
            y = -y;
        }
        if (y>Integer.MAX_VALUE || y<Integer.MIN_VALUE) {
            return 0;
        }
        return (int)y;
    }
}

public class Solution {
    public int reverse(int x) {
        int y;
        if(x == Integer.MAX_VALUE || x == Integer.MIN_VALUE) return 0;
        if(x < 0) y = -x;
        else y = x;
        long reverse = 0;
        while(y != 0){
            reverse = reverse * 10 + y % 10;
            y = y / 10;
        }
        if(reverse > Integer.MAX_VALUE) return 0;
        if(x < 0) reverse = - reverse;
        return (int)reverse;
    }
}

===================

public class Solution {
    public int reverse(int x) {
        if (x == 0) {
            return 0;
        } 
        int sign = 1;
        if (x < 0) {
            if (x == Integer.MIN_VALUE) return 0;
            sign = -1;
            x = -x;
        }
        int res = 0;
        while (x != 0) {
            int digit = x % 10;
            if (Integer.MAX_VALUE / 10 < res || (Integer.MAX_VALUE / 10 == res && Integer.MAX_VALUE % 10 < digit) ) {
                return 0;
            }
            res = res * 10 + digit;
            x = x / 10;
        }
        return res * sign;
    }
}

Leetcoder - Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(root==null) {
            return 0;
        }
        return visitNext(root, 0);
    }
 
    public int visitNext(TreeNode node, int maxDepth) {
        if(node==null) {
            return maxDepth;
        } else {
            int dL = visitNext(node.left, maxDepth+1);
            int dR = visitNext(node.right, maxDepth+1);
            return dL>dR?dL:dR;
        }
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        return (root==null)? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

Leetcoder - Same Tree

 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.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        return checkNode(p, q);
    }
   
    public boolean checkNode(TreeNode p, TreeNode q) {
        if(p==null && q==null) {
            return true;
        }
        if(p!=null && q!=null && p.val==q.val) {
            boolean sameL = checkNode(p.left, q.left);
            if(sameL) {
                return checkNode(p.right, q.right);
            } else {
                return false;
            }
        } else {
            return false;
        }
    }
}

Leetcoder - Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

public class Solution {
    public int singleNumber(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int ret = 0;
        for (int k : A) {
            ret ^= k;
        }
        return ret;
    }
}