Monday, October 31, 2016

Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
For example:
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
Hint:
  1. Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
  2. According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

First, the graph should not contain cycle. Second, all nodes should connect to each other. The easiest way is to use union find. After all unions of edges, the size should be only 1.


    public boolean validTree(int n, int[][] edges) {
        UnionFind unionFind = new UnionFind(n);
        for (int[] e : edges) {
            if (!unionFind.union(e[0], e[1])) {
                return false;
            }
        }
        return unionFind.size == 1;

    }

    private class UnionFind {
        int[] vertices;
        int size = 0;

        public UnionFind(int n) {
            vertices = new int[n];
            Arrays.fill(vertices, -1);
            size = n;
        }
        public int find(int v) {
            validate(v);
            if (vertices[v] < 0) {
                return v;
            }
            vertices[v] = find(vertices[v]);
            return vertices[v];
        }

        public boolean union(int u, int v) {
            int uR = find(u);
            int vR = find(v);
            if (uR == vR) {
                return false;
            }
            if (vertices[vR] < vertices[uR]) {
                vertices[uR] = v;
            } else {
                if (vertices[vR] == vertices[uR]) {
                    vertices[uR]--;
                }
                vertices[vR] = u;
            }
            size--;
            return true;
        }

        private void validate(int v) {
            if (v < 0 || v >= vertices.length) {
                throw new InvalidParameterException("Invalid input!");
            }
        }
    }



3 sum smaller


Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]
Follow up: Could you solve it in O(n2) runtime?


Similar to 3 sum. Note we need to calculate the count, so if sum <= target, total sums we can get is right - left because all pairs (left, right), (left  + 1, right) ...  (right - 1, right) together with nums[i] will lead to a sum smaller than/equal to target.

public int threeSumSmaller(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i + 3 <= nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum <= target) {
                    count += right - left;
                    left++;
                } else {
                    right--;
                }
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
            }
        }
        return count;
    }

Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.
Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Using a stack, pop out the previous digits that is larger if doesn't exceed n. If the string is in ascending order, pop out any extra chars. Remove all "0"s in the front and return result.


public String removeKdigits(String num, int k) {
        if (num.length() == 0) {
            return "0";
        }
        Stack stack = new Stack<>();
        for (char c : num.toCharArray()) {
            while (!stack.isEmpty() && k > 0 && stack.peek() > c) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }
        while (stack.size() > num.length() - k) {
            stack.pop();
        }
        StringBuilder rst = new StringBuilder();
        while (!stack.isEmpty()) {
            rst.append(stack.pop());
        }
        int index = rst.length();
        while (index > 0 && rst.charAt(index - 1) == '0') {
            index--;
        }
        rst.delete(index, rst.length());
        return rst.length() == 0 ? "0" : rst.reverse().toString();
    }


Nth Digit

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...
Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).
Example 1:
Input:
3

Output:
3
Example 2:
Input:
11

Output:
0

Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.


Math. :(

0 - 9 : 9 * 1 digits
10 - 99 : 90 * 2 digits
100 - 999: 900 * 3 digits
...

So we can calculate the number of digits by finding the range of the number first, e.g., if n = 1000, 1000 - 9 - 90 = 811, which is the 811th digit starting from 100. Now the actual number is calculated by 100 + (811 - 1)/ 3 = 370. The digit is calculated by (811 - 1) % 3. 

Now why should we do (811 - 1)? For number 370, let n1, n2, and n3 for the nth digit of digit 3, 7, and 0. Then n1/3, n2/3 and n3/3 should all equal 370. To achieve that, we need to do (811 - 1). Let's use another example. If we have n = 190, 191, or 192, all three n should lead to number 100. The reminder after we subtract the first two digits are 1, 2, and 3 (190 - 189, 191 - 189, 192 - 189). If we want all 1, 2, 3 / 3 leads to 0 (100 + 0), we need to subtract the reminder by 1, i.e., change it to 0 based expression. 




public int findNthDigit(int n) {
        long digitLen = 1, count = 9, start = 1;
        long m = (long)n;
        while (m > count * digitLen) {
            m -= count * digitLen;
            start *= 10;
            count *= 10;
            digitLen++;
        }
        start += (m - 1) / digitLen;
        return String.valueOf(start).charAt((int)((m - 1)% digitLen)) - '0';
    }


Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]


Using a bit mask, if the number exists in the array, sets that bit to 1. Then check from 1 to n, if any bit is 0, the number is missing.


public List findDisappearedNumbers(int[] nums) {
        List rst = new ArrayList<>();
        int mask = 0;
        for (int n : nums) {
            mask |= (1 << n);
        }
        for (int i = 1; i <= nums.length; i++) {
            if (((mask >> i) & 1) != 1) {
                rst.add(i);
            }
        }
        return rst;
    }


Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".


This is a quite easy problem, except... it's easy to exceed time limit. One way to optimize is to calculate the first substring in s with length of p, i.e., s.substring(0, p.length()), check if they are anagrams, if they are, add 0 to result. Then we go with a sliding window manner, we add one char to the substring, and remove one char from it. After this operation, we compare if the substrings are anagrams.

public List<integer> findAnagrams(String s, String p) {
        List<integer> rst = new ArrayList<>();
        int lenS = s.length();
        int lenP = p.length();
        if (lenS == 0 || lenP == 0 || lenS < lenP) {
            return rst;
        }
        Map<character, integer> pCounter = new HashMap<>();
        Map<character, integer> sCounter = new HashMap<>(pCounter);
        for (int i = 0; i < lenP; i++) {
            char c1 = p.charAt(i);
            char c2 = s.charAt(i);
            pCounter.put(c1, pCounter.containsKey(c1) ? pCounter.get(c1) + 1 : 1);
            sCounter.put(c2, sCounter.containsKey(c2) ? sCounter.get(c2) + 1 : 1);
        }

        if (pCounter.equals(sCounter)) {
            rst.add(0);
        }

        for (int i = lenP; i < lenS; i++) {
            char c2 = s.charAt(i - lenP);
            if (sCounter.get(c2) == 1) {
                sCounter.remove(c2);
            } else {
                sCounter.put(c2, sCounter.get(c2) - 1);
            }
            char c1 = s.charAt(i);
            sCounter.put(c1, sCounter.containsKey(c1) ? sCounter.get(c1) + 1 : 1);
            if (pCounter.containsKey(c1) && pCounter.equals(sCounter)) {
                rst.add(i - lenP + 1);
            }
        }
        return rst;
    }


Path Sum III

You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Use recursion and traverse the tree and get number of paths with current root. Now recursively call pathSum(root.left, sum) and pathSum(root.right, sum) to get all result from left and right children.

public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        return getPathSum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    private int getPathSum(TreeNode root, int sum) {
        int rst = 0;
        if (root == null) {
            return rst;
        }
        if (sum == root.val) {
            rst++;
        }
        rst += getPathSum(root.left, sum - root.val);
        rst += getPathSum(root.right, sum - root.val);
        return rst;
    }


Sunday, October 30, 2016

Factor Combinations

Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
  = 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.
Note: 
You may assume that n is always positive.
Factors should be greater than 1 and less than n.

Backtracking. Note since we only iterate till i * i <= n, we need to add n to the result to get 1 * n = n. Note this operation is used to get the remaining numbers. For example, 2 * 2 * 3 = 12, now n = 3 and i starts with 2, 2 * 2 > 3, so the function will exit the loop. we need to add 3 to the result to get the final one.


public List> getFactors(int n) {
        List> rst = new ArrayList<>();
        if (n < 2) {
            return rst;
        }
        getFactors(rst, n, new ArrayList<>());
        return rst;
    }

    private void getFactors(List> rst, int n, List curr) {
        if (n == 1) {
            if (curr.size() > 1) {
                rst.add(new ArrayList<>(curr));
            }
            return;
        }
        for (int i = 2; i * i <= n; i++) {
            if (!curr.isEmpty() && i < curr.get(curr.size() - 1)) {
                continue;
            }
            if (n % i == 0) {
                curr.add(i);
                getFactors(rst, n / i, curr);
                curr.remove(curr.size() - 1);
            }
        }
        curr.add(n);
        getFactors(rst, 1, curr);
        curr.remove(curr.size() - 1);
    }


Meeting rooms I && II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.
For example, Given [[0, 30],[5, 10],[15, 20]], return false.

The first one can be solved by checking each interval's start time, and comparing it with the latest end time previously seen.


public boolean canAttendMeetings(Interval[] intervals) {
        if (intervals.length == 0) {
            return true;
        }
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1.start != o2.start) {
                return o1.start - o2.start;
            } else {
                return o1.end - o2.end;
            }
        });
        int latest = intervals[0].end;
        for (Interval interval : intervals) {
            if (interval.start < latest) {
                return false;
            }
            latest = Math.max(latest, interval.end);
        }
        return true;
    }


Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
For example, Given [[0, 30],[5, 10],[15, 20]], return 2.

The second one utilizes a priority queue. The idea is whenever a meeting's start time is later than the earliest meeting in the queue, we can update the end time (by removing the head and add the new element). If the meeting's start time is earlier than the earliest meeting in the queue, we add a new end time in it, which indicates we need a new meeting room. In the end we return the size of the queue.


public int minMeetingRooms(Interval[] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, (interval1, interval2) -> {
            if (interval1.start != interval2.start) {
                return interval1.start - interval2.start;
            } else {
                return interval1.end - interval2.end;
            }
        });
        PriorityQueue endTimes = new PriorityQueue<>();
        for (Interval interval : intervals) {
            if (!endTimes.isEmpty() && interval.start > endTimes.peek()) {
                endTimes.poll();
            }
            endTimes.add(interval.end);
        }
        return endTimes.size();
    }


Count Univalue Subtrees

Given a binary tree, count the number of uni-value subtrees.
A Uni-value subtree means all nodes of the subtree have the same value.
For example:
Given binary tree,
              5
             / \
            1   5
           / \   \
          5   5   5

return 4.

Recursion.


public class CountUnivalueSubtrees {
    int count = 0;
    public int countUnivalSubtrees(TreeNode root) {
        if (root == null) {
            return count;
        }
        validTree(root);
        return count;
    }

    private boolean validTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.left == null || root.right == null) {
            count++;
            return true;
        }
        boolean left = validTree(root.left);
        boolean right = validTree(root.right);
        if (left && right
            && ( (root.left == null && root.val == root.right.val)
                || (root.right == null && root.val == root.left.val)
                || (root.val == root.left.val && root.val == root.right.val)
        )) {
            count++;
            return true;
        }
        return false;
    }
}


Group Shifted Strings

Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:
"abc" -> "bcd" -> ... -> "xyz"
Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.
For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Return:
[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]
Note: For the return value, each inner list's elements must follow the lexicographic order.

Fairly easy, the difference between all successive letters and the first letter should be the same for string in the same group. Note that subsequent letters may be smaller than the first one, thus the difference can be calculated by ((currChar - firstChar) + 26) % 26.


public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> rst = new ArrayList<>();
        if (strings.length == 0) {
            return rst;
        }
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strings) {
            String key = "";
            if (s.length() == 1) {
                key = "1";
            } else {
                char first = s.charAt(0);
                for (int i = 1; i < s.length(); i++) {
                    key += ((s.charAt(i) - first) + 26) % 26;
                }
            }
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }

        for (List list : map.values()) {
            rst.add(list);
        }
        return rst;
    }


Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
Example:
Given a / b = 2.0, b / c = 3.0. 
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . 
return [6.0, 0.5, -1.0, 1.0, -1.0 ].
The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.
According to the example above:
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Build a map from all the equations. The variables are indices and equations are edges. Map the string variable with certain index using hash map. Then build a matrix to represent all values that can be represented by the given equations. For example, a/b means a and b are neighbors, b/c means b and c are neighbors, thus we know a and c are connected and we can calculate the value of a/c by a/b * b/c, as well as c / a by 1.0 / (a/c).

After that, for each query, if we cannot find the index in the map, we cannot get the result.


public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        int len = equations.length;
        
        Map indices = new HashMap<>();
        int index = 0;
        for (String[] eq : equations) {
            if (!indices.containsKey(eq[0])) {
                indices.put(eq[0], index++);
            }
            if (!indices.containsKey(eq[1])) {
                indices.put(eq[1], index++);
            }
        }
        
        double[][] relations = new double[index][index];
        for (int i = 0; i < index; i++) {
            Arrays.fill(relations[i], -1.0);
        }
        for (int i = 0; i < len; i++) {
            String[] eq = equations[i];
            double v = values[i];
            int first = indices.get(eq[0]);
            int second = indices.get(eq[1]);
            relations[first][second] = v;
            relations[second][first] = 1.0 / v;
        }
        
        for (int i = 0; i < index; i++) {
            for (int j = 0; j < index; j++) {
                for(int k = 0; k < index; k++) {
                    if (relations[i][j] != -1.0) {
                        continue;
                    }
                    if (relations[i][k] != -1.0 && relations[k][j] != -1.0) {
                        relations[i][j] = relations[i][k] * relations[k][j];
                        if (relations[i][j] != 0.0) {
                            relations[j][i] = 1.0 / relations[i][j];
                        }
                    }
                }
            }
        } 
        
        double[] rst = new double[queries.length];
        for (int i = 0; i < queries.length; i++) {
            if (!indices.containsKey(queries[i][0]) || !indices.containsKey(queries[i][1])) {
                rst[i] = -1.0;
            } else {
                int first = indices.get(queries[i][0]);
                int second = indices.get(queries[i][1]);
                rst[i] = relations[first][second];
            }
        }
        return rst;
    }


Random Pick Index

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.
Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.
Example:
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

Now each number should have the same probability to be picked up, which is 1/n. The easiest solution is to keep picking a number in the array until we get one that equals target.

public class Solution {
    int[] numbers;
    Random random;
    public Solution(int[] nums) {
        this.numbers = Arrays.copyOf(nums, nums.length);
        random = new Random();
    }
    
    public int pick(int target) {
        int index = random.nextInt(numbers.length);
        while (numbers[index] != target) {
            index = random.nextInt(numbers.length);
        }
        return index;
    }
}


Integer Replacement

Given a positive integer n and you can do operations as follow:
  1. If n is even, replace n with n/2.
  2. If n is odd, you can replace n with either n + 1 or n - 1.
What is the minimum number of replacements needed for n to become 1?
Example 1:
Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1
Example 2:
Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

The most straightforward way is to use recursion. Recursively calculate number of replacement needed until integer reaches 1.  

public int integerReplacement(int n) {
        return getCount(n, 0);
    }
    
    private int getCount(long n, int count) {
        if (n == 1) {
            return count;
        }
        
        count++;
        if (n % 2 == 0) {
            return getCount(n / 2, count);
        } else {
            return Math.min(getCount(n - 1, count), getCount(n + 1, count));
        }
    }


All O`one Data Structure

Implement a data structure supporting the following operations:
  1. Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
  2. Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
  3. GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "".
  4. GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string "".
Challenge: Perform all these in O(1) time complexity.

Using a doubly linked list and a hash map. See this post for detail: https://discuss.leetcode.com/topic/65439/an-accepted-java-solution-detailed-explanation-hashmap-double-linked-list.


public class AllOne {
    

    private ValueNode head;//largest
    private ValueNode tail;//smallest
    private Map elements;

    /** Initialize your data structure here. */
    public AllOne() {
        head = null;
        tail = null;
        this.elements = new HashMap<>();
    }

    /** Inserts a new key  with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        // if no element in the map, add the element to tail with value 1
        if (!elements.containsKey(key)) {
            if (tail == null || tail.value > 1) {
                ValueNode prevTail = null;
                if (tail != null) {
                    prevTail = tail;
                }
                tail = new ValueNode(1, key);
                if (head == null) {
                    head = tail;
                }
                if (prevTail != null) {
                    prevTail.next = tail;
                    tail.prev = prevTail;
                }
            } else {
                tail.keys.add(key);
            }
            elements.put(key, tail);
        } else {
            ValueNode curr = elements.get(key);
            if (curr.prev != null && curr.prev.value == curr.value + 1) {
                curr.prev.keys.add(key);
                elements.put(key, curr.prev);
            } else {
                ValueNode prev = new ValueNode(curr.value + 1, key);
                if (curr.prev != null) {
                    ValueNode prevprev = curr.prev;
                    prevprev.next = prev;
                    prev.prev = prevprev;
                    //which means curr is head
                } else {
                    head = prev;
                }
                curr.prev = prev;
                prev.next = curr;
                elements.put(key, prev);
            }
            curr.keys.remove(key);
            if (!checkEmpty(curr)) {
                curr.updateOneKey(key);
            }
        }
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        if (elements.containsKey(key)) {
            ValueNode curr = elements.get(key);
            if (curr.next != null && curr.next.value == curr.value - 1) {
                curr.next.keys.add(key);
                elements.put(key, curr.next);
            } else {
                if (curr.value > 1) {
                    ValueNode next = new ValueNode(curr.value - 1, key);
                    if (curr.next != null) {
                        ValueNode nextnext = curr.next;
                        next.next = nextnext;
                        nextnext.prev = next;
                    } else {
                        tail = next;
                    }
                    curr.next = next;
                    next.prev = curr;
                    elements.put(key, next);
                } else {
                    elements.remove(key);
                }
            }
            curr.keys.remove(key);
            if (!checkEmpty(curr)) {
                curr.updateOneKey(key);
            }
        }
    }

    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        return head != null ? head.oneKey : "";
    }

    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        return tail != null ? tail.oneKey : "";
    }

    private boolean checkEmpty(ValueNode node) {
        if (node.keys.isEmpty()) {
            if (node == head) {
                head = node.next;
                node.next.prev = null;
            } else if (node == tail) {
                tail = node.prev;
                node.prev.next = null;
            } else {
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
            node = null;
            return true;
        } else {
            return false;
        }
    }

    //Doubly linked list node
    private class ValueNode {
        int value;
        Set keys;
        ValueNode prev;
        ValueNode next;
        String oneKey; // any key with the value

        public ValueNode(int value, String key) {
            this.value = value;
            keys = new HashSet<>();
            keys.add(key);
            oneKey = key;
            prev = null;
            next = null;
        }

        public void updateOneKey(String key) {
            if (oneKey.equals(key)) {
                Iterator it = keys.iterator();
                oneKey = it.next();
            }
        }
    }
}


Strong Password CheckerStrong Password Checker

A password is considered strong if below conditions are all met:
  1. It has at least 6 characters and at most 20 characters.
  2. It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
  3. It must NOT contain three repeating characters in a row ("...aaa..." is weak, but "...aa...a..." is strong, assuming other conditions are met).
Write a function strongPasswordChecker(s), that takes a string s as input, and return the MINIMUM change required to make s a strong password. If s is already strong, return 0.
Insertion, deletion or replace of any one character are all considered as one change.

The problem can be split to three parts(quite obvious) :

1. if the password contains all three types;
2. If the password has at least 6 chars and at most 20 chars;
3. If the password doesn't have any three or more repeating characters.

Now for the first part, we can go through the string and use a flag, whenever we see a type, we mark that type to true. In the end, we can get how many types we have in the password, and also how many types we still need. And the second part is fairly easy, check the length of the string.

The third part is the hardest. We know for every 3 - 5 repeating characters, we only need to modify one character to cut down the repeating length. similarly for every 6 - 8 repeating characters, we need to modify 2 characters, thus the number of characters needs to be modified = number of repeating characters / 3. After we go through the string, we will know how many changes we need to make.

If the length of the string exceeds 20, we know deletion is necessary. So we need to find out how many changes that can be modified by deletion. For each extra repeating word we have, we need to delete it. For example, if we have 5 repeating characters, we need delete 2, and if we have 4, we need to delete 1. We know that if we have 4 or 5 repeating characters, we only need to modify 1 character. So each modification operation can be replaced by number of repeating characters % 3 + 1 deletions. For example, 5 % 3 = 2, we need 2 + 1 = 3 deletion operations, but we only need 1 change operation. So when we go through the string, we also track how many deletion operations we can have instead of change operations. In the end if the length is greater than 20, we reduce the change operations by deletion operation.

If the length of the string is less than 6, adding a character is similar to replace a character, so the change required = max( 6 - len, # type required, # changes).


public int strongPasswordChecker(String s) {
        int len = s.length();
        
        if(len <= 2)  {
            return 6 - len;
        }
            

        char end = s.charAt(0);
        boolean upper = (end >= 'A' && end <= 'Z'), lower = (end >= 'a' && end <= 'z'), digit = (end >= '0' && end <= '9');
        
        
        //delete[0] indicates 1 change operation can be replaced by 1 deletion
        //delete[1] indicates 1 change operation can be replaced by 2 deletion
        int[] delete = new int[3];
        int change = 0;
        
        int repeating = 1;
        for(int i = 1; i < len; i++){
            if(s.charAt(i) == end) {
                repeating++;
            }
            else{
                change += (repeating / 3);
                if(repeating / 3 > 0) {
                    delete[repeating % 3] += (repeating / 3);
                }
                end = s.charAt(i);
                upper |= (end >= 'A'&& end<='Z');
                lower |= (end >='a' && end<='z');
                digit |= (end >= '0'&& end<='9');
                repeating = 1;
            }
        }
        //if last char equals to the char before, need to count repeating chars for the last one
        if (s.charAt(len - 1) == end) {
            change += repeating / 3;
            if(repeating / 3 > 0) delete[repeating % 3] += (repeating / 3);

        }        
        
        int typeStillNeeded = (upper ? 0 : 1) + (lower ? 0 : 1) + (digit ? 0 : 1);
        
        if(len > 20){
            int delRequired = len - 20;
            //since deletion requires more operations at most of the time, delete only when necessary
            if(delRequired <= delete[0]) {
                change -= delRequired;
            }
            // delete[1] indicates #repeating % 3 == 1, thus one change requires two deletions
            else if(delRequired - delete[0] <= 2 * delete[1]) {
                change -= delete[0] + (delRequired - delete[0]) / 2;
            }
            else {
                change -= delete[0] + delete[1] / 2 + (delRequired - delete[0] - 2 * delete[1]) / 3;
            }
            
            return delRequired + Math.max(typeStillNeeded, change);
        }
        return Math.max(6 - len, Math.max(typeStillNeeded, change));
    }


Saturday, October 29, 2016

Longest Repeating Character Replacement

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.
Note:
Both the string's length and k will not exceed 104.
Example 1:
Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

Update 2016-11-12

A more explainable solution:


public int characterReplacement(String s, int k) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }
        
        int[] count = new int[26];
        int max = 0;
        int start = 0;
        for (int end = 0; end < len; end++) {
            max = Math.max(max, ++count[s.charAt(end) - 'A']);
            if (max + k < end - start + 1) {
                count[s.charAt(start++) - 'A']--;
            }
            
        }
        return len - start;
    }


The idea is that the window never needs to shrink. After the length of the substring expands to maximum, when we add one more char, if it is the char with the maximum occurrence, nothing changes, otherwise, the length of the substring increases but max + k doesn't, so we need to move window leftward (start++). In the following rounds, until we find another char has more occurrence, we only need to move window to keep the max length correct. So "max" here is defined as the maximum occurrence seen so far, not the maximum occurrence in current window.





This problem asks us to find the longest substring of repeating characters if we can make at most k replacement. Now if we remove the restriction that we can only make k replacement, the solution should be length of string - occurrence of character with maximum occurrence. With the k restriction, we can use sliding window manner, if length of the window - max occurrence so far > k, we know we cannot construct such substring with at most k replacement, so we move window rightward. The longest substring should be updated with the length of the window.


public int characterReplacement(String s, int k) {
        if (s.length() == 0) {
            return 0;
        }
        int start = 0;
        int len = s.length();
        int[] count = new int[26];
        int maxCount = 0;
        int rst = 0;
        for (int i = 0; i < len; i++) {
            maxCount = Math.max(maxCount, ++count[s.charAt(i) - 'A']);
            while (i - start + 1 - maxCount > k) {
                maxCount = Math.max(maxCount, --count[s.charAt(start) - 'A']);
                start++;
            }
            rst = Math.max(rst, i - start + 1);
        }
        return rst;
    }


Reconstruct Original Digits from English


Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.
Note:
  1. Input contains only lowercase English letters.
  2. Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as "abc" or "zerone" are not permitted.
  3. Input length is less than 50,000.
Example 1:
Input: "owoztneoer"

Output: "012"
Example 2:
Input: "fviefuro"

Output: "45"
There is a trick in this problem. For all numbers from 0 - 9, there are certain characters that only exists once in the numbers' english expressions:

z: zero 0
w: two 2
u: four 4
x: six 6
g: eight 8

which means from the occurrence of the above five characters, we can find 5 numbers. Now let's take a look of the rest:

o: zero 0, one 1, two 2, four 4

since we already know number of 0, 2, 4, we can calculate number of 1s by nums[1] = counts['o'] - nums[0] - nums[2] - nums[4], similarly, we can find all following numbers:

h: three 3, eight 8
f: four 4, five 5
s: six 6, seven 7
i: five 5, six 6, eight 8, nine 9

public String originalDigits(String s) {
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }
        
        int[] nums = new int[10];
        nums[0] = count['z' - 'a'];
        nums[2] = count['w' - 'a'];
        nums[4] = count['u' - 'a'];
        nums[6] = count['x' - 'a'];
        nums[8] = count['g' - 'a'];
        nums[1] = count['o' - 'a'] - nums[0] - nums[2] - nums[4];
        nums[3] = count['h' - 'a'] - nums[8];
        nums[5] = count['f' - 'a'] - nums[4];
        nums[7] = count['s' - 'a'] - nums[6];
        nums[9] = count['i' - 'a'] - nums[5] - nums[6] - nums[8];
        
        String rst = "";
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < nums[i]; j++) {
                rst += i;    
            }
        }
        return rst;
    }


Rotate function

Given an array of integers A and let n to be its length.
Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow:
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].
Calculate the maximum value of F(0), F(1), ..., F(n-1).
Note:
n is guaranteed to be less than 105.
Example:
A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

This is a math problem. :(

Do this:

f = 0 *A[0] + 1 * A[1] + ... + (n - 1) * A[n - 1]

sum = A[0] + A[1] + ... + A[n - 1]

f + sum = 1 * A[0] + 2 * A[1] + ... + n * A[n - 1]

k = 1 f = f + sum - n * A[n - k] = 1 * A[0] + 2 * A[1] + ... + n * A[n - 1] - n * A[n - 1]
                                             =  1 * A[0] + 2 * A[1] + ... + 0 * A[n - 1] = f(n - 1)
k = 2 f = 2 * A[0] + 3 * A[1] + ... + n * A[n - 2] + 1 * A[n - 1] - n * A[n - 2] = f(n - 2)
.
.
.


public int maxRotateFunction(int[] A) {
        int len = A.length;
        
        int f = 0;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            f += i * A[i];
            sum += A[i];
        }
        
        int max = f;
        
        for (int k = 1; k < len; k++) {
            f = f + sum - len * A[len - k];
            max = Math.max(max, f);
        }
        return max;
    }


Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:
Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

For this kind of problem, we definitely need to count the occurrence of each characters. Now the problem is how to get the longest substring. The idea is that for each character that has lower than k occurrence, we treat it as a separator. However, the substring that contains all chars with k occurrence may not have k occurrence anymore after the split. Thus we need to recursively call the function and find the longest substring.

The bit mask here is used to track if all characters have occurrence of at least k. We set the bit the character corresponds to 1 if it has occurrence smaller than k, later if the same character appears again and the occurrence exists k, we set the bit back to 0. If in the end the mask is 0, we know all characters have at least k occurrence.


public int longestSubstring(String s, int k) {
        if (s.length() == 0 || k == 0) {
            return s.length();
        }
        int[] chars = new int[26];
        int len = s.length();
        int mask = 0;
        for (int i = 0; i < len; i++) {
            int index = s.charAt(i) - 'a';
            chars[index]++;
            if (chars[index] < k) {
                mask |= (1 << index);
            } else {
                mask &= ~(1 << index);
            }
        }
        if (mask == 0) {
            return s.length();
        }
        int last_start = 0;
        int longest = 0;
        for (int i = 0; i < len; i++) {
            if (chars[s.charAt(i) - 'a'] < k) {
                longest = Math.max(longest, longestSubstring(s.substring(last_start, i), k));
                last_start = i + 1;
            }
        }
        longest = Math.max(longest, longestSubstring(s.substring(last_start), k));
        return longest;
    }


Decode String

Given an encoded string, return it's decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].
Examples:
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

Now it comes with layer by layer, we know stack should be the best choice. For this problem, we keep two stacks, one for the numbers, the other for the letters. When we see a number, we push it to the number stack. When we see a "[", we add all current layer letters to the stack. When we see a "]", we append current layer string with correct repeating times to last layer string.


public String decodeString(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        Stack repeatingTimes = new Stack<>();
        Stack layer = new Stack<>();
        String rst = "";
        int pos = 0;
        int len = s.length();
        while (pos < len) {
            char c = s.charAt(pos);
            if (Character.isDigit(c)) {
                int curr = pos;
                while (Character.isDigit(s.charAt(curr))) {
                    curr++;
                }
                repeatingTimes.push(Integer.parseInt(s.substring(pos, curr)));
                pos = curr;
            } else if (Character.isLetter(c)) {
                rst += c;
                pos++;
            } else if (c == '[') {
                layer.push(rst);
                rst = "";
                pos++;
            } else if (c == ']') {
                StringBuilder builder = new StringBuilder();
                int times = repeatingTimes.pop();
                while (times > 0) {
                    builder.append(rst);
                    times--;
                }
                rst = layer.pop() + builder.toString();
                pos++;
            } else {
                return "";
            }
        }
        return rst;
    }


Thursday, October 27, 2016

Battleships in a Board

Given an 2D board, count how many different battleships are in it. The battleships are represented with 'X's, empty slots are represented with'.'s. You may assume the following rules:
  • You receive a valid board, made of only battleships or empty slots.
  • Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) orNx1 (N rows, 1 column), where N can be of any size.
  • At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.
Example:
X..X
...X
...X
In the above board there are 2 battleships.
Invalid Example:
...X
XXXX
...X
This is not a valid board - as battleships will always have a cell separating between them.

At first I was thinking to use DFS, but for this problem it would be too complicated. Based on the description, the battleship will only be horizontally or vertically placed, that means two consecutive Xs are from the same ship. Now the only thing we need to do is to go through the board and exclude all those points.


public int countBattleships(char[][] board) {
        if (board.length == 0 || board[0].length == 0) {
            return 0;
        }
        int rows = board.length;
        int cols = board[0].length;
        int rst = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == '.' 
                || (i > 0 && board[i - 1][j] == 'X')
                || (j > 0 && board[i][j - 1] == 'X')) {
                    continue;
                }
                rst++;
            }
        }
        return rst;
    }