Question:

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Thinking:

Firstly, I want to traverse the tree, but we can do better. Because we know its structure is special. For example, if this root’s height is this root’s right child’s height minus 1, its left subtree must be a full tree. So we need to caclulate the rest nodes which remain in its right subtree. Otherwise, we need to go to left.

Solution:

public int countNodes(TreeNode root) {
    int h = height(root);
    if (h == 0)
        return 0;
    if (h == height(root.right)+1){
        return (1 << (h-1)) + countNodes(root.right);
    } else {
        return (1 << (h-2)) + countNodes(root.left);
    }
}

private int height(TreeNode root) {
    return root == null? 0 : 1 + height(root.left);
}

Question:

Sort a linked list in O(n log n) time using constant space complexity.

Thinking:

There are three basic algorithm to sort in n*logn time. They are merge sort, heap sort and quick sort. And I implement the sort method in merge sort. In order to do this, I have to implement the function such as getLength, get the mid node, merge and so on.

Basic idea of merge sort is to divide a list into two lists, and make them sorted then merge them together.

Solution:

//merge
public ListNode sortList(ListNode head) {
    int len = getLength(head);
    if (len == 0)    return null;
    ListNode nhead = mergeSort(head, len);
    addTail(nhead, len);
    return nhead;
}

private ListNode mergeSort(ListNode head, int n) {
    if (n <= 1)
        return head;
    ListNode mid = getNode(head, n/2);
    ListNode nhead = mergeSort(head, n/2);
    ListNode nmid = mergeSort(mid, n - n/2);
    return merge(nhead, nmid, n);
}

private int getLength(ListNode head) {
    int l = 0;

    while (head != null) {
        head = head.next;
        l++;
    }

    return l;
}

private ListNode getNode(ListNode head, int index) {
    while (index > 0) {
        head = head.next;
        index--;
    }

    return head;
}

private ListNode merge(ListNode p1, ListNode p2, int len) {
    ListNode dummy = new ListNode(0);
    ListNode p = dummy;
    int l1 = 0;
    int l2 = 0;
    while (l1 < len/2 && l2 < len - len/2) {
        if (p1.val < p2.val) {
            p.next = p1;
            p1 = p1.next;
            p = p.next;
            l1++;
        } else {
            p.next = p2;
            p2 = p2.next;
            p = p.next;
            l2++;
        }
    }
    if (l1 == len/2) {
        p.next = p2;
    } else {
        p.next = p1;
    }
    return dummy.next;
}

private void addTail(ListNode head, int n) {
    while (n > 1) {
        head = head.next;
        n--;
    }
    head.next = null;
}

More efficient method:
Reference:https://leetcode.com/discuss/1709/have-pretty-mergesort-method-anyone-speed-reduce-memory-usage

It use the fast pointer and slow pointer to find the middle index of the linked list. Add a null to the first half to implement the merge operation.

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ListNode f = head.next.next;
    ListNode p = head;
    while (f != null && f.next != null) {
        p = p.next;
        f =  f.next.next;
    }
    ListNode h2 = sortList(p.next);
    p.next = null;
    return merge(sortList(head), h2);
}
public ListNode merge(ListNode h1, ListNode h2) {
    ListNode hn = new ListNode(Integer.MIN_VALUE);
    ListNode c = hn;
    while (h1 != null && h2 != null) {
        if (h1.val < h2.val) {
            c.next = h1;
            h1 = h1.next;
        }
        else {
            c.next = h2;
            h2 = h2.next;
        }
        c = c.next;
    }
    if (h1 != null)
        c.next = h1;
    if (h2 != null)
        c.next = h2;
    return hn.next;
}

Question:

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Thinking:

We can conclude the position of the element in the searching tree according to the k. For example, there are n subtrees in the first level, so the k/(n-1) means picking the k/(n-1) th element in the array. And delete the element from the element, pick the next one. Do this recursively.

Solution:

public String getPermutation(int n, int k) {
    ArrayList<Integer> nums = new ArrayList<Integer>();
    int fac = 1;
    int[] pos = new int[n+1];
    for (int i = 1; i <= n; i++){
        nums.add(i);
        fac *= i;
    }
    fac /= n;
    k -= 1;
    for (int i = 1; i < n; i++){
        pos[i] = k / fac;
        k %= fac;
        fac /= (n-i);
    }
    StringBuilder res = new StringBuilder();
    for (int i = 1; i <= n; i++){
        res.append(nums.remove(pos[i]));
    }

    return res.toString();
}

Question:

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Thinking:

The basic idea is to maintain a hashmap to keep the exsiting characters. If there is a character appered in the hashmap, then move the index to the last position it emerged. Hold two pointers: one is to record the substring’s start position and the other is to record the substring’s end position. And the pointers can only move forward.

Solution:

public int lengthOfLongestSubstring(String s) {
    HashMap<Character, Integer> alphabeta = new HashMap<Character, Integer>();
    int max = 0;
    int count = 0;
    int idx = 0;

    while (idx+count < s.length()) {

        if (!alphabeta.containsKey(s.charAt(idx + count))) {
            alphabeta.put(s.charAt(idx + count), idx+count);
            count++;
        }
        else {
            idx = alphabeta.get(s.charAt(idx + count)) + 1;
            alphabeta = new HashMap<Character, Integer>();
            count = 0;
        }
        max = Math.max(max, count);
    }

    return max;
}

Question:

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Thinking:

Run from left to right and check each element in different index. The check method is select a index, and expand its range to two sides of it. Record the max value and max substring.

Solution:

int max = 1;
String res = "";
public String longestPalindrome(String s) {
    if (s.length() < 2)
        return s;
    for (int i = 0; i < s.length() - max/2; i++){

        if (i+1<s.length() && s.charAt(i) == s.charAt(i+1)){
            check(s, i-1, i+2, 2);
        }

        check(s, i-1, i+1, 1);
    }

    return res;
}

private void check(String s, int i, int j, int len){
    int count = len;
    while (i >= 0 && j < s.length()){
        if (s.charAt(i) == s.charAt(j))
            count += 2;
        else
            break;
        i--;
        j++;
    }
    if (count > max){
        res = s.substring(i+1, j);
        max = count;
    }

}