Lintcode Easy题（1）

1 A + B Problem

不推荐用+来解决，最后答案是用位运算来解决的。对位运算实在没有兴趣，故用+直接放弃。

408 Add Binary

题目的意思就是输入两个二进制的数字，做加法，然后返回二进制的答案。

这一类的题目都是先将输入的数字倒序，然后逐位相加，遇到进一位的情况，用一个参数表明。

public String addBinary(String a, String b)
 {
        StringBuilder stringBuilder1 = new StringBuilder(a), stringBuilder2 = new StringBuilder(b);

        int aLength = a.length();
        int bLength = b.length();

        // 倒序排列
        stringBuilder1 = stringBuilder1.reverse();
        stringBuilder2 = stringBuilder2.reverse();

        String string1 = stringBuilder1.toString(), string2 = stringBuilder2.toString();

        // 取两者较长的长度作为最后的比较范围，在运算的时候，位数不足的用0来补
        int length = aLength > bLength ? aLength : bLength;

        int temp_result= 0;
        StringBuilder final_result = new StringBuilder();
        boolean plusOne = false;
        int num1, num2 = 0;
        for (int i = 0; i <= length; i ++)
        {
            temp_result = 0;
            if (plusOne)
            {
                temp_result += 1;
                plusOne = false;
            }

            num1 = i >= aLength ? 0 : Integer.parseInt(string1.charAt(i) + "");
            num2 = i >= bLength ? 0 : Integer.parseInt(string2.charAt(i) + "");

            temp_result = temp_result + num1 + num2;
            if (temp_result >= 2)
            {
                plusOne = true;
                temp_result = temp_result % 2;
            }
            final_result.append(temp_result);
        }

        return String.valueOf(Integer.parseInt(final_result.reverse().toString()));
    }

167 Add Two Numbers

跟上一题很像，需要多考虑一种222+778的情况

public ListNode addLists(ListNode l1, ListNode l2) 
{
        ListNode l1temp = l1, l2temp = l2;
        int l1Length = 0, l2Length = 0;
        while (l1temp != null)
        {
            l1Length ++;
            l1temp = l1temp.next;
        }
        while (l2temp != null)
        {
            l2Length ++;
            l2temp = l2temp.next;
        }

        int length = l1Length > l2Length ? l1Length : l2Length;

        ListNode resultHead = new ListNode(0), temp = new ListNode(0);
        boolean carries = false;
        int tempVal, l1Value, l2Value;

        for (int i = 0; i < length; i ++)
        {
            tempVal = 0;
            if (carries)
            {
                tempVal += 1;
                carries = false;
            }

            if (l1 != null)
            {
                l1Value = l1.val;
                l1 = l1.next;
            }
            else
            {
                l1Value = 0;
            }

            if (l2 != null)
            {
                l2Value = l2.val;
                l2 = l2.next;
            }
            else
            {
                l2Value = 0;
            }

            tempVal = tempVal + l1Value + l2Value;

            if (tempVal >= 10)
            {
                carries = true;
                tempVal = tempVal % 10;
            }

            if (i == 0)
            {
                resultHead = new ListNode(tempVal);
                temp = resultHead;
            }
            else
            {
                temp.next = new ListNode(tempVal);
                temp = temp.next;
            }
        }

        if (carries)
        {
            temp.next = new ListNode(1);
        }
        return resultHead;
    }

93 Balanced Binary Tree

题目可以解释为判断root的左右两个分支left和right是否存在不平衡的情况。

进而可以解释为

• left的左右两个分支是否存在不平衡的情况
• right的左右两个分支是否存在不平衡的情况

...

也就是利用递归，从树的最底端往上推，看每一层的左右分支是否平衡。

    public boolean isBalanced(TreeNode root) 
    {
        return maxDepth(root) != -1;
    }

    private int maxDepth(TreeNode node)
    {
        if (node == null)
        {
            return 0;
        }

        int leftLength = maxDepth(node.left);
        int rightLength = maxDepth(node.right);

        if (leftLength == -1 || rightLength == -1 || Math.abs(leftLength - rightLength) > 1)
        {
            return -1;
        }

        return Math.max(leftLength, rightLength) + 1;
    }