Lowest Common Ancestor of a Binary Tree leetcode

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).”

        _______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.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public 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;
        } else if (right != null) {
            return right;
        } else if (left != null) {
            return left;
        } else {
            return null;
        }
    }
}

Lowest Common Ancestor of a Binary Search Tree leetcode

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

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).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

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

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
    
}

Palindrome Linked List leetcode

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

找到list的中点, 然后翻转后面的list 一一对比

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = reverse(slow.next);// 这里导入的是中点的下一个 因为这种找中点情况 偶数时候是在左中点, 奇数时候是在正中点
        while (cur != null) {////这里不能是head!=null 对于0->0这个list head后面还有一个元素0

            if (head.val != cur.val) {
                return false;
            }
            head = head.next;
            cur = cur.next;
        }
        return true;
    }
    public ListNode reverse(ListNode node) {
        ListNode dummy = new ListNode(0);
        dummy.next = node;
        ListNode next = node.next;
        while (next != null) {
            node.next = next.next;
            next.next = dummy.next;
            dummy.next = next;
            next = node.next;
        }
        return dummy.next;
    
    }
}

Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

思路: http://blog.csdn.net/xudli/article/details/46798619

public class Solution {
    public int countDigitOne(int n) {
         int res = 0;
         for (long m = 1; m <= n; m*= 10) {
             long a = n / m;
             long b = n % m;
             res += (a + 8) / 10 * m;
             if (a % 10 == 1) {
                 res += b + 1;
             }
         }
         return res;
    }
}

Implement Queue using Stacks leetcode

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

//方法1 push() O(n), pop() O(1), peek() O(1)
class MyQueue {
    Stack<Integer> stack = new Stack<Integer>();
    Stack<Integer> tem = new Stack<Integer>();
    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(x);
        } else {
            while (!stack.isEmpty()) {
                tem.push(stack.pop());
            }
            tem.push(x);
            while (!tem.isEmpty()) {
                stack.push(tem.pop());
            }
            
        }
    }
    public void pop() {
        stack.pop();
    }
    public int peek() {
        return stack.peek();
    }
    public boolean empty() {
        return stack.isEmpty();
    }
}
//方法2 push() O(1), pop() O(n), peek() O(n)
class MyQueue {
    private Stack<Integer> stack = new Stack<Integer>();
    private Stack<Integer> tem = new Stack<Integer>();
    public void push(int x) {
        stack.push(x);
    }
    public void pop() {
        int x = peek();
        tem.pop();
    }
    public int peek() {
        if (tem.isEmpty()) {
            while (!stack.isEmpty()) {
                tem.push(stack.pop());
            }
         }
         return tem.peek();
    }
    public boolean empty() {
        return stack.isEmpty() && tem.isEmpty();
    }
}

Kth Smallest Element in a BST leetcode

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

非递归方法: 类似线序遍历, 每访问到一个最小的count++, 直到count == k

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        int count = 0;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode tem = stack.pop();
                count++;
                
                if (count == k) {
                    return tem.val;
                }
                node = tem.right;
            }
        }
        return 0;
    }
}

递归方法:

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int count = count(root.left);
        if (count + 1 > k) {
            return kthSmallest(root.left, k);
        } else if (count + 1 < k) {
            return kthSmallest(root.right, k - count- 1);
        } else {
            return root.val;
        }
    }
    public int count(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return count(root.left) + count(root.right) + 1;
    }
}

Majority Element II leetcode

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        int n1 = 0, n2 = 0;
        int count1 = 0, count2 = 0;
        for (int s : nums) {
            if (count1 == 0) {
                n1 = s;
                count1++;
            } else if (count2 == 0 && n1 != s) {
                n2 = s;
                count2++;
            } else if (s == n1) {
                count1++;
            } else if (s == n2) {
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int s  : nums) {
            if (s == n1) {
                count1++;
            } else if (s == n2) {
                count2++;
            }
        }
        if (count1 > nums.length / 3) {
            res.add(n1);
        }
        if (count2 > nums.length / 3) {
            res.add(n2);
        }
        return res;
    }
}