Monthly Archives: August 2016

leetcode 376.

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2

Follow up:
Can you do it in O(n) time?

Solution. An amazing solution is from here. The idea is that when there is a asc, then asc = desc + 1. When there is a desc, then desc = asc + 1.

public int wiggleMaxLength(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int asc = 1, desc = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {    // update increasing by decreasing
            asc = desc + 1;
        }
        else if (nums[i] < nums[i - 1]) {   // update decreasing by increasing
            desc = asc + 1;
        }
    }
    return Math.max(asc, desc);
}

Check my code on github.

leetcode 43.

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:

• The numbers can be arbitrarily large and are non-negative.
• Converting the input string to integer is NOT allowed.
• You should NOT use internal library such as BigInteger.

Solution. An awesome solution is from this post.

1. length of new string is len1 + len2.
2. iterates each element in num1 and num2 from lower to higher position.
3. num1[i] * num2[j] will be placed at [i + j], [i + j + 1] position.

public String multiply(String num1, String num2) {
    int[] digit = new int[num1.length() + num2.length()];
    for (int i = num1.length() - 1; i >= 0; i--) {
        for (int j = num2.length() - 1; j >= 0; j--) {
            int posHigh = i + j, posLow = i + j + 1;
            int curr = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + digit[posLow];
            digit[posLow]  = curr % 10;
            digit[posHigh] += curr / 10;
        }
    }
    StringBuffer sb = new StringBuffer();
    for (int i : digit) {
        if (!(sb.length() == 0 && i == 0)) {
            sb.append(i);
        }
    }
    return sb.length() == 0 ? "0" : sb.toString();
}

Check my code on github.

leetcode 381.

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.

1. insert(val): Inserts an item val to the collection.
2. remove(val): Removes an item val from the collection if present.
3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Solution. Same as previous problem. To solve the duplicate one, all we need to change is that we choose to use HashSet as the value for loc. When we do remove and update, we 1. remove HashSet 2. remove ArrayList 3. Update HashSet 4.Update ArrayList.

public class RandomizedCollection {

    Map<Integer, Set<Integer>> loc;
    List<Integer> list;
    Random random = new Random();

    /** Initialize your data structure here. */
    public RandomizedCollection() {
        loc = new HashMap<>();
        list = new ArrayList<>();
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        Set<Integer> set = loc.getOrDefault(val, new HashSet<>());
        set.add(list.size());
        loc.put(val, set);
        list.add(val);
        return true;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if (!loc.containsKey(val)) {
            return false;
        }
        Set<Integer> set = loc.get(val);
        int pos = set.iterator().next();
        set.remove(pos);    // remove loc
        if (set.isEmpty()) {
            loc.remove(val);
        }
        int lastEle = list.remove(list.size() - 1); // remove list
        if (pos != list.size()) {   // update list and loc
            list.set(pos, lastEle);     // update loc
            Set<Integer> lastEleSet = loc.get(lastEle);
            lastEleSet.remove(list.size()); // update list
            lastEleSet.add(pos);
        }
        return true;
    }

    /** Get a random element from the collection. */
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }

}

Check my code on github.

leetcode 380.

Design a data structure that supports all following operations in average O(1) time.

1. insert(val): Inserts an item val to the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Solution. To solve this problem, we need to use an ArrayList to maintain all the elements, and a HashMap to maintain the position of each element.

Every time when adding, just add in ArrayList and HashMap.
When getting the random, just get a random in ArrayList.
When removing, we delete in HashMap. If element is not in the last, we need to move the last element to the position of deleting element, and update the HashMap.

public class RandomizedSet {

    Map<Integer, Integer> loc;
    List<Integer> list;
    Random random = new Random();

    /** Initialize your data structure here. */
    public RandomizedSet() {
        loc = new HashMap<>();
        list = new ArrayList<>();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (loc.containsKey(val)) {
            return false;
        }
        loc.put(val, list.size());
        list.add(val);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!loc.containsKey(val)) {
            return false;
        }
        int pos = loc.remove(val);
        int lastEle = list.remove(list.size() - 1);
        if (pos != list.size()) {
            list.set(pos, lastEle);
            loc.put(lastEle, pos);
        }
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }

}

Check my code on github.

leetcode 15.

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution. When the array doesn’t has duplicate, it is a classical 3Sum problem, the code is like below

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> list = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                left++;
                right--;
            }
            else if (sum < 0) {
                right--;
            }
            else {
                left++;
            }
        }
    }
    return list;
}

If it has duplicate, we need to skip the duplicate by several rules:
1. When iterating i, if nums[i] has same value as the previous one, nums[i] == nums[i – 1]. We need to skip
2. After we found a new pair at nums[i], nums[left] and nums[right], we need to move left forward until a different value; move right backward until a different value.

public List<List<Integer>> threeSumWithDuplicate(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> list = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
            }
            else if (sum < 0) {
                right--;
            }
            else {
                left++;
            }
        }
    }
    return list;
}

Check my code on github.

leetcode 3

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution. An awesome solution is from here. It has two pointers, left and right. s[left, right] has no duplicate.

Iterate right, if s[right] is not in HashSet, then put it in, and update ans = max(ans, right – left).

If s[right] is already in HashSet, we need to loop from left and remove s[left], until there is no s[right] in HashSet.

If the string is [a b c d e f g h i e j k l], then the process is like:

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0, right = 0, ans = 0;
    while (right < s.length()) {
        if (set.contains(s.charAt(right))) {    // has duplicate, move left until there is no duplicate between [left, right]
            set.remove(s.charAt(left++));
        }
        else {
            set.add(s.charAt(right++)); // has no duplicate between [left, right], move right
            ans = Math.max(ans, right - left);
        }
    }
    return ans;
}

Check my code on github.

leetcode 155.

There are many ways to solve the min stack problem. However, there is one solution which only requiring O(1) extra space.

The idea is that when pushinng, store the offset of the current min value. When pop or getTop, use the offset and min to get the top or next min.

If the [3, 4, 2, 1] enters stack sequentially, the stack looks like this:

public class MinStack {

    long min;
    Stack<Long> stack;

    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int x) {
        if (stack.size() == 0) {
            min = x;
            stack.push(0l);
        }
        else {
            stack.push(x - min);
            min = Math.min(min, x);
        }
    }

    public void pop() {
        long pop = stack.pop();
        if (pop < 0) {
            min = min - pop;
        }
    }

    public int top() {
        long top = stack.peek();
        if (top < 0) {
            return (int)min;
        }
        return (int)(top + min);
    }

    public int getMin() {
        return (int)min;
    }

}

Check my code on github.

leetcode 33, 81

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

What if duplicates are allowed?

Solution. I referred this nice solution.

Compared to without duplicate, the version for with duplicate has a part of code to judge if nums[left] == nums[mid] == nums[rigt]. If so, then left++, right–.

One more thing we need to pay attention is that when we check the first type of shape, we need to check use >= for nums[mid] >= nums[left] instead of nums[mid] > nums[left].

public static boolean search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (target == nums[mid]) {
            return true;
        }
        if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
            left++;
            right--;
        }
        else if (nums[mid] >= nums[left]) { // left side is longer
            if (target >= nums[left] && target < nums[mid]) {   // to left
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        else {  // right side is longer
            if (nums[mid] < target && target <= nums[right]) {  // to right
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
    }
    return false;
}

Check my code on github i, ii.

leetcode 87.

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Solution. This is a interesting problem. The idea is to compare isScramble(S1[0, …, i], S2[0, …, i]) and isScsramble(S1[i + 1, …, len – 1]), S2[i + 1, …, len – 1]), or isScramebl(S1[0, …, i], S2[len – i, len – i + 1, …, len]) and isScramble(S1[i + 1, i + 2, …, len – 1), S2[0, 1, …, len – i]).

For this case

S1 = X0 X1 X2 X3 X4 X5 X6
S2 = Y0 Y1 Y2 Y3 Y4 Y5 Y6

We check isScramble(X0X1X2, Y0Y1Y2) and isScramble(X3X4X5X6, Y3Y4Y5Y6)

Or check isScamble(X0X1X2, Y4Y5Y6) and isScramble(X3X4X5X6, Y0Y1Y2Y3)

public static boolean isScramble(String s1, String s2) {
    if (s1.equals(s2)) {
        return true;
    }
    int[] letters = new int[26];
    for (int i = 0; i < s1.length(); i++) { // this check to avoid enter useless loop.
        letters[s1.charAt(i) - 'a']++;
        letters[s2.charAt(i) - 'a']--;
    }
    for (int count : letters) {
        if (count != 0) {
            return false;
        }
    }
    for (int i = 1; i < s1.length(); i++) {
        if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) {
            return true;
        }
        if (isScramble(s1.substring(0, i), s2.substring(s1.length() - i)) && isScramble(s1.substring(i), s2.substring(0, s1.length() - i))) {
            return true;
        }
    }
    return false;
}

Check my code on github.