Buttercola: January 2021

Friday, January 29, 2021

Lintcode 1379. The Longest Scene

Solution:

First of all, for each character, we note down the position of the rightmost same character it can reach. E.g. abcdad. For character a, the position of the rightmost is 4.

After that, we can form a list of intervals with start and end position of each character. Then the problem is to merge the intervals.

Code (Java):

public class Solution {
    /**
     * @param str: The scene string
     * @return: Return the length longest scene
     */
    public int getLongestScene(String str) {
        // Write your code here
        if (str == null || str.length() == 0) {
            return 0;
        }
         
        if (str.length() == 1) {
            return 1;
        }
         
        // pos saves the rightmost position of each character
        int[] pos = new int[26];
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            pos[c - 'a'] = i;
        }
         
        // store the intervals into the list. Note that it's already sorted by the start time
        List<Interval> intervals = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (pos[c - 'a'] != i) {
                intervals.add(new Interval(i, pos[c - 'a']));
            }
        }
         
        // now it's time to merge and get the longest interval
        Interval prev = null;
        int ans = 1;
         
        for (int i = 0; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (prev == null || prev.end < curr.start) {
                prev = curr;
            } else { // overlap
                prev.start = Math.min(prev.start, curr.start);
                prev.end = Math.max(prev.end, curr.end);
            }
             
            if (prev.end - prev.start + 1 > ans) {
                ans = prev.end - prev.start + 1;
            }
        }
         
        if (prev != null) {
            ans = Math.max(ans, prev.end - prev.start + 1);
        }
         
        return ans;
         
    }
}
 
class Interval {
    int start;
    int end;
     
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

Lintcode 1397. Digital Coverage

Description

Given some intervals, ask how many are covered most, if there are multiple, output the smallest number.

the number of the interval is not more than 10^5.
the left and right endpoints of the interval are greater than 0 not more than 10^5.

Have you met this question in a real interview?

Example

Example 1:

 Input:intervals = [(1,7),(2,8)]
 Output:2
Explanation:2 is covered 2 times, and is the number of 2 times the smallest number.

Example 2:

Input:intervals = [(1,3),(2,3),(3,4)]
Output:3

Explanation:3 is covered 3 times.

Solution 1:

Split the interval into events and sort by start time. Time complexity O(nlogn)

Code (Java):

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */
 
public class Solution {
    /**
     * @param intervals: The intervals
     * @return: The answer
     */
    public int digitalCoverage(List<Interval> intervals) {
        // Write your code here
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }
         
        List<Event> events = new ArrayList<>();
        for (Interval interval : intervals) {
            events.add(new Event(interval.start, 0));
            events.add(new Event(interval.end, 1));
        }
         
        Collections.sort(events, new MyEventComparator());
         
        int count = 0;
        int ans = 0;
        int maxCount = 0;
         
        for (Event event : events) {
            if (event.flag == 0) {
                count++;
            } else {
                count--;
            }
             
            if (count > maxCount) {
                maxCount = count;
                ans = event.time;
            }
        }
         
        return ans;
    }
}
 
class Event {
    int time;
    int flag; // 0 start, 1 end
     
    public Event(int time, int flag) {
        this.time = time;
        this.flag = flag;
    }
}
 
class MyEventComparator implements Comparator<Event> {
    @Override
    public int compare(Event a, Event b) {
        if (a.time != b.time) {
            return a.time - b.time;
        }
         
        return a.flag - b.flag;
    }
}

Solution 2: prefix sum

Allocate an array with size of data range (10^5 for this problem). for each interval, if it's start, count + 1, otherwise count - 1. In the end, we sum up the counts and get the max number.

Time complexity is O(data range)

Code (Java):

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */
 
public class Solution {
    /**
     * @param intervals: The intervals
     * @return: The answer
     */
    public int digitalCoverage(List<Interval> intervals) {
        // Write your code here
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }
         
        int[] counts = new int[1000001];
         
        for (Interval interval : intervals) {
            counts[interval.start] += 1;
            counts[interval.end + 1] -= 1;
        }
         
        int maxCount = 0;
        int count = 0;
        int ans = -1;
         
        for (int i = 0; i < counts.length; i++) {
            count += counts[i];
            if (count > maxCount) {
                maxCount = count;
                ans = i;
            }
        }
         
        return ans;
    }
}

Thursday, January 28, 2021

Lintcode1399. Take Coins

Example

Example 1:

Input: list = [5,4,3,2,1], k = 2
Output :9
Explanation:Take two coins from the left.

Example 2:

Input: list = [5,4,3,2,1,6], k = 3, 
Output:15
Explanation:Take two coins from the left and one from the right.

Wrong solution:

Greedy. Two pointers from the start and end of the array, respectively. Each time get the larger value until k times. The reason it doesn't work is one example [4, 1, 1, 1, 6, 1] and k = 2. For the greedy. We take 4 and 1, so the value is 5. However, the max value we can get is to get 6 and 1, which is 7 instead.

Correct Solution:

The correct solution is we can take k from left, then 0 from right, e.g.

from left from right

k 0

k - 1 1

k - 2 2

... ...

0 k

So the solution is we first get sum of the first k elements from the left. And then each time we get one from right, we substract from the left side.

Code (Java):

public class Solution {
    /**
     * @param list: The coins
     * @param k: The k
     * @return: The answer
     */
    public int takeCoins(int[] list, int k) {
        // Write your code here
        if (list == null || list.length == 0) {
            return 0;
        }
         
        int sum = 0;
        int maxSum = 0;
         
        int left = 0;
        int right = list.length - 1;
         
        for (left = 0; left < k; left++) {
            sum += list[left];
        }
         
        maxSum = sum;
         
        // left pointer back off by one
        left--;
         
        while (left >= 0) {
            sum -= list[left];
            left--;
             
            sum += list[right];
            right--;
             
            maxSum = Math.max(maxSum, sum);
        }
         
        return maxSum;
    }
}

Monday, January 25, 2021

Lintcode 1390. Short Encoding of Words

Solution:

Two words can be compressed if and only if they share the same suffix. For e.g. time, me, ime can be compressed. But time and im cannot be compressed. And time and ame cannot be compressed as well.

So the solution is to use a trie to store all the words in reverse order. In the end, count the number of nodes of the trie and calculate the final length.

Code (Java):

public class Solution {
    /**
     * @param words: 
     * @return: nothing
     */
    public int minimumLengthEncoding(String[] words) {
        // 
        if (words == null || words.length == 0) {
            return 0;
        }
         
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
         
        return trie.getLength();
    }
}
 
class TrieNode {
    public TrieNode[] children;
     
    public TrieNode() {
        this.children = new TrieNode[26];
    }
}
 
class Trie {
    private TrieNode root;
     
    public Trie() {
        this.root = new TrieNode();
    }
     
    public void insert(String word) {
        TrieNode p = root;
         
        for (int i = word.length() - 1; i >= 0; i--) {
            char c = word.charAt(i);
            if (p.children[c - 'a'] == null) {
                p.children[c - 'a'] = new TrieNode();
            }
             
            p = p.children[c - 'a'];
        }
    }
     
    public int getLength() {
        TrieNode p = root;
         
        return dfs(p, 0);
    }
     
    private int dfs(TrieNode p, int depth) {
        // if p is a leaf node, get the number and return
        boolean leaf = true;
         
        int len = 0;
         
        for (int i = 0; i < 26; i++) {
            if (p.children[i] != null) {
                leaf = false;
                len += dfs(p.children[i], depth + 1);
            }
        }
         
        if (leaf) {
            len += depth + 1;
        }
         
        return len;
    }
     
}

Tuesday, January 19, 2021

Lintcode 1430. Similar String Groups

5.All words in A have the same length and are anagrams of each other.

Solution:

Union-Find. For each of the two words in the list, if they are similar, connect them into the same connected components. In the end, we need to count number of cc.

Code (Java):

100

101

102

public class Solution {
    /**
     * @param A: a string array
     * @return: the number of groups 
     */
    public int numSimilarGroups(String[] A) {
        // Write your code here
        if (A == null || A.length == 0) {
            return 0;
        }
         
        UF uf = new UF(A);
         
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                if (isSimilar(A[i], A[j])) {
                    uf.connect(A[i], A[j]);
                }
            }
        }
         
        return uf.getNumCC();
    }
     
    private boolean isSimilar(String s1, String s2) {
        int first = -1;
        int second = -1;
         
        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
             
            if (c1 == c2) {
                continue;
            }
             
            if (first == -1) {
                first = i;
            } else if (second == -1) {
                second = i;
            } else {
                return false;
            }
        }
         
        if (first == -1 && second == -1) {
            return true;
        }
         
        if (s1.charAt(first) == s2.charAt(second) && s1.charAt(second) == s2.charAt(first)) {
            return true;
        }
         
        return false;
    }
}
 
class UF {
    private Map<String, String> parents;
    private int numCC;
     
    public UF (String[] A) {
        parents = new HashMap<>();
         
        for (String a : A) {
            parents.put(a, a);
        }
         
        numCC = parents.size();
    }
     
    public String find(String a) {
        String root = a;
         
        while (!root.equals(parents.get(root))) {
            root = parents.get(root);
        }
         
        // path compression
        while (!root.equals(a)) {
            String parent = parents.get(a);
            parents.put(a, root);
            a = parent;
        }
         
        return root;
    }
     
    public void connect(String a, String b) {
        String pa = find(a);
        String pb = find(b);
         
        if (!pa.equals(pb)) {
            parents.put(pa, pb);
            numCC--;
        }
    }
     
    public int getNumCC() {
        return numCC;
    }
}

Lintcode 1641. Max Remove Order

Example

Example 1:

Input：[[1,1,1,1],[1,1,0,1],[1,0,1,0]]
Output：8
Explanation:
In the board
1, 1, 1, 1
1, 1, 0, 1
1, 0, 1, 0
We can remove 1 from right to left, from bottom to top, until there is only one 1 at (0, 0). Totally 8 removed.

Example 2:

Input：[[1,0],[1,0]]
Output：1
Explanation:
In the board
1, 0
1, 0
We can only remove (0,0) or (1,0)

Solution:

Use Union Find.

Consider from a simpler example. [1, 1, 1, 1]. We can remove three 1s from the set until the last one. So if we scan from left to right, up to bottom, for each element if the value is 1, we connect to the right-most element from the row and bottom-most element from the column. At the end, how many elements we cannot remove? It's the number of connected components.

Code (Java):

public class Solution {
    /**
     * @param mp: the board
     * @return: the max number of points we can remove
     */
    public int getAns(int[][] mp) {
        // Write your code here.
        if (mp == null || mp.length == 0) {
            return 0;
        }
         
        int m = mp.length;
        int n = mp[0].length;
         
        int numOnes = 0;
         
        // cols[i]: for ith col, the index of the bottom-most one
        // rows[i], for ith row, the index of the right-most one
        int[] rows = new int[m];
        int[] cols = new int[n];
         
        UF uf = new UF(mp);
         
        // step 1: calculate the number of 1s and the right-most position and 
        // bottom-most position of the 1s
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mp[i][j] == 1) {
                    numOnes++;
                    rows[i] = j;
                    cols[j] = i;
                }
            }
        }
         
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mp[i][j] == 1) {
                    uf.connect(i * n + j, i * n + rows[i]);
                    uf.connect(i * n + j, cols[j] * n + j);
                }
            }
        }
         
        return numOnes - uf.getNumCC();
         
    }
}
 
class UF {
    private int[] parents;
    private int numCC;
     
    public UF (int[][] mp) {
        int m = mp.length;
        int n = mp[0].length;
         
        parents = new int[m * n];
     
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mp[i][j] == 1) {
                    parents[i * n + j] = i * n + j;
                    numCC++;
                }
            }
        }
    }
     
    public int find(int a) {
        int root = a;
         
        while (parents[root] != root) {
            root = parents[root];
        }
         
        while (root != a) {
            int parent = parents[a];
            parents[a] = root;
            a = parent;
        }
         
        return root;
    }
     
    public void connect(int a, int b) {
        int pa = find(a);
        int pb = find(b);
         
        if (parents[pa] != pb) {
            parents[pa] = pb;
            numCC--;
        }
    }
     
    public int getNumCC() {
        return numCC;
    }
}

Friday, January 15, 2021

Lintcode 1391. Making A Large Island

Example

Example 1:

Input:[[1, 0], [0, 1]]
Output:3

Explanation:
Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: [[1, 1], [1, 0]]
Output:4

Explanation:
 Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

Input:[[1, 1], [1, 1]]
Output:4

Explanation:
 Can't change any 0 to 1, only one island with area = 4.

Code (Java):

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

public class Solution {
    /**
     * @param grid: 
     * @return: nothing
     */
    public int largestIsland(int[][] grid) {
        // 
        if (grid == null || grid.length == 0) {
            return 0;
        }
         
        int m = grid.length;
        int n = grid[0].length;
         
        UF uf = new UF(m, n, grid);
         
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
         
        // step 1: connect all 1s
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] dir : dirs) {
                    int nx = i + dir[0];
                    int ny = j + dir[1];
                     
                    if (grid[i][j] == 1 && nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                        uf.union(i * n + j, nx * n + ny);
                    }
                }
            }
        }
         
        int maxSize = 0;
         
        // step 2: find all 0s and try to connect
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int size = 1;
                Set<Integer> parents = new HashSet<>();
                for (int[] dir : dirs) {
                    int nx = i + dir[0];
                    int ny = j + dir[1];
                     
                    if (grid[i][j] == 0 && nx >= 0 && nx < m && ny >=0 && ny < n && grid[nx][ny] == 1) {
                        int parent = uf.getParent(nx * n + ny);
                        if (!parents.contains(parent)) {
                            parents.add(parent);
                            size += uf.getSize(nx * n + ny);
                        }
                    }
                }
                 
                maxSize = Math.max(size, maxSize);
            }
        }
         
        return maxSize;
    }
}
 
class UF {
    int[] parents;
    int[] size;
    int m;
    int n;
    int[][] grid;
     
    public UF (int m, int n, int[][] grid) {
        this.m = m;
        this.n = n;
        this.grid = grid;
         
        parents = new int[m * n];
        size = new int[m * n];
         
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                parents[i * n + j] = i * n + j;
                size[i * n + j] = 1;
            }
        }
    }
     
    public void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
         
        if (pa != pb) {
            parents[pa] = pb;
            size[pb] += size[pa];
        }
    }
     
    private int find(int a) {
        int root = a;
         
        while (root != parents[root]) {
            root = parents[root];
        }
         
        // path compression
        while (root != a) {
            int parent = parents[a];
            parents[a] = root;
            a = parent;
        }
         
        return root;
    }
     
    public int getSize(int a) {
        int pa = find(a);
        return size[pa];
    }
     
    public int getParent(int a) {
        return find(a);
    }
}

Lintcode 1411. Edit Distance - Replace Edition

Example

Example 1:

Input: s1 = "abb", s2 = "dad"
Output: 2
Explantion: Then first letters will coincide when we will replace letter 'a' with 'd'. Second letters will coincide when we will replace 'b' with 'a'. Third letters will coincide when we will at first replace 'b' with 'a' and then 'a' with 'd'.

Two strings with same length consisting only of lowercase English letters.

Solution:

Use Union Find. For each character from s1 to s2, say c1->c2, if there is a change, we connect c1 to c2 in one connected component.

Code (Java):

public class Solution {
    /**
     * @param s1: a string
     * @param s2: a string
     * @return: the least number of operations and make the two strings equal
     */
    public int editDistance(String s1, String s2) {
        // Write your code here
        if (s1 == null || s1.length() == 0) {
            return 0;
        }
         
        int[] parents = new int[26];
        int ans = 0;
         
        for (int i = 0; i < 26; i++) {
            parents[i] = i;
        }
         
        for (int i = 0; i < s1.length(); i++) {
            int n1 = s1.charAt(i) - 'a';
            int n2 = s2.charAt(i) - 'a';
             
            int p1 = find(n1, parents);
            int p2 = find(n2, parents);
             
            if (p1 != p2) {
                ans++;
                parents[p1] = p2;
            }
        }
         
        return ans;
    }
     
    private int find(int node, int[] parents) {
        int root = node;
         
        while (parents[root] != root) {
            root = parents[root];
        }
         
        while (root != node) {
            int parent = parents[node];
            parents[node] = root;
            node = parent;
        }
         
        return root;
    }
}

Thursday, January 14, 2021

Lintcode 1257. Evaluate Division

Description

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.

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Have you met this question in a real interview?

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"] ].

Solution:

Graph + DFS

Code (Java):

100

101

102

103

104

public class Solution {
    /**
     * @param equations: 
     * @param values: 
     * @param queries: 
     * @return: return a double type array
     */
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // write your code here
        double[] ans = new double[queries.size()];
         
        if (equations == null || equations.size() == 0 || values == null|| values.length == 0) {
            return ans;
        }
         
        // build the graph
        Map<String, List<Node>> adjList = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            double value = values[i];
            String n1 = equation.get(0);
            String n2 = equation.get(1);
             
            // n1->n2
            List<Node> neighbors = adjList.getOrDefault(n1, new ArrayList<>());
            neighbors.add(new Node(n2, value));
            adjList.put(n1, neighbors);
             
            // n2->n1
            List<Node> neighbors2 = adjList.getOrDefault(n2, new ArrayList<>());
            neighbors2.add(new Node(n1, 1.0 / value));
            adjList.put(n2, neighbors2);
        }
         
        // dfs to find the answer
        for (int i = 0; i < queries.size(); i++) {
            List<String> query = queries.get(i);
            String n1 = query.get(0);
            String n2 = query.get(1);
             
            if (!adjList.containsKey(n1) || !adjList.containsKey(n2)) {
                ans[i] = -1.0;
            } else if (n1.equals(n2)) {
                ans[i] = 1.0;
            } else {
                Set<String> visited = new HashSet<>();
                RetVal retval = dfs(n1, n2, adjList, 1.0, visited);
                if (retval.found) {
                    ans[i] = retval.val;
                } else {
                    ans[i]= -1.0;
                }
            }
        }
         
        return ans;
    }
     
    private RetVal dfs(String start, String end, Map<String, List<Node>> adjList, double val, Set<String> visited) {
        RetVal retval = new RetVal(false, -1.0);
        visited.add(start);
         
        if (start.equals(end)) {
            return new RetVal(true, val);
        }
         
        List<Node> neighbors = adjList.get(start);
         
        for (Node neighbor: neighbors) {
            if (visited.contains(neighbor.label)) {
                continue;
            }
             
            retval = dfs(neighbor.label, end, adjList, val * neighbor.val, visited);
             
            if (retval.found) {
                return retval;
            }
        }
         
        visited.remove(start);
        return retval;
    }
}
 
class Node {
    String label;
    double val;
     
    public Node (String label, double val) {
        this.label = label;
        this.val = val;
    }
}
 
class RetVal {
    boolean found;
    double val;
     
    public RetVal (boolean found, double val) {
        this.found = found;
        this.val = val;
    }
}

Friday, January 29, 2021

Example

Notice

Description

Example

Thursday, January 28, 2021

1399. Take Coins

Example

Notice

Monday, January 25, 2021

Example

Notice

Tuesday, January 19, 2021

Example

Clarification

Notice

Example

Notice

Friday, January 15, 2021

Example

Notice

Example

Notice

Thursday, January 14, 2021

Description

Example