LeetCode刷题笔记 2月

Posted on By Guanzhou Song

Go to Leetcode

2020-02-05

588. Design In-Memory File System

Description

Design an in-memory file system to simulate the following functions:

ls: Given a path in string format. If it is a file path, return a list that only contains this file’s name. If it is a directory path, return the list of file and directory names in this directory. Your output (file and directory names together) should in lexicographic order.

mkdir: Given a directory path that does not exist, you should make a new directory according to the path. If the middle directories in the path don’t exist either, you should create them as well. This function has void return type.

addContentToFile: Given a file path and file content in string format. If the file doesn’t exist, you need to create that file containing given content. If the file already exists, you need to append given content to original content. This function has void return type.

readContentFromFile: Given a file path, return its content in string format.

Example:

Input: [“FileSystem”,”ls”,”mkdir”,”addContentToFile”,”ls”,”readContentFromFile”] [[],[”/”],[“/a/b/c”],[“/a/b/c/d”,”hello”],[”/”],[“/a/b/c/d”]]

Output: [null,[],null,null,[“a”],”hello”]

Explanation: filesystem

Note:

You can assume all file or directory paths are absolute paths which begin with / and do not end with / except that the path is just “/”. You can assume that all operations will be passed valid parameters and users will not attempt to retrieve file content or list a directory or file that does not exist. You can assume that all directory names and file names only contain lower-case letters, and same names won’t exist in the same directory.

Solution

class FileSystem {
    class node{
        boolean isFile = false;
        Map<String, node> children = new HashMap();
        String content = "";
        String name="";
    }

    node root = null;
    
    public FileSystem() {
        root = new node();
    }
    
    public List<String> ls(String path) {
        node cur = root;
        List<String> res = new ArrayList();
        for(String child: path.split("/")){
            if(child.isEmpty()) continue;
            node next = cur.children.get(child);
            if(next == null) return res;
            cur = next;
        }
        if(cur.isFile){
            res.add(cur.name);
            return res;
        }
        for(String dirName : cur.children.keySet()){
            res.add(dirName);
        }
        Collections.sort(res);
        return res;
        
    }
    
    public void mkdir(String path) {
        String[] paths = path.split("/");
        node cur = root;
        for(String p:paths){
            if(p.isEmpty()) continue;
            node next = cur.children.get(p);
            if(next == null){
                next = new node();
                next.name = p;
                cur.children.put(p,next);
            }
            cur = next;
        }
    }
    
    public void addContentToFile(String filePath, String content) {
        String[] paths = filePath.split("/");
        node cur = root;
        for(String p:paths){
            if(p.isEmpty()) continue;
            node next = cur.children.get(p);
            if(next == null){
                next = new node();
                next.name = p;
                cur.children.put(p,next);
            }
            cur = next;
        }
        cur.isFile = true;
        cur.content += content;
    }
    
    public String readContentFromFile(String filePath) {
        String[] paths = filePath.split("/");
        node cur = root;
        for(String p:paths){
            if(p.isEmpty()) continue;
            node next = cur.children.get(p);
            if(next == null){
                return "";
            }
            cur = next;
        }
        return cur.content;
    }
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * FileSystem obj = new FileSystem();
 * List<String> param_1 = obj.ls(path);
 * obj.mkdir(path);
 * obj.addContentToFile(filePath,content);
 * String param_4 = obj.readContentFromFile(filePath);
 */

472. Concatenated Words

Description

Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example: Input: [“cat”,”cats”,”catsdogcats”,”dog”,”dogcatsdog”,”hippopotamuses”,”rat”,”ratcatdogcat”]

Output: [“catsdogcats”,”dogcatsdog”,”ratcatdogcat”]

Explanation: “catsdogcats” can be concatenated by “cats”, “dog” and “cats”; “dogcatsdog” can be concatenated by “dog”, “cats” and “dog”; “ratcatdogcat” can be concatenated by “rat”, “cat”, “dog” and “cat”. Note: The number of elements of the given array will not exceed 10,000 The length sum of elements in the given array will not exceed 600,000. All the input string will only include lower case letters. The returned elements order does not matter.

Solution

class Solution {
    //sort by length first, so will start with the shortest word.
    //cause words can only consist with shorter words.
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> res = new ArrayList();
        HashSet<String> dict = new HashSet<>();
        Arrays.sort(words,(a,b)->(a.length()-b.length()));
        
        for(int i = 0; i<words.length;i++){
            if(canConcate(words[i],dict)){
                res.add(words[i]);
            }
            //only add the word to dict afterward, so only contains words smaller than itself.
            dict.add(words[i]);
        }
        
        return res;
    }
    
    private boolean canConcate(String word, HashSet<String> dict){
        if(dict.isEmpty()) return false;
        int len = word.length();
        boolean[] dp = new boolean[len+1];
        dp[0] = true;
        for(int i = 1;i<=len;i++){
            for(int j = 0; j<i;j++){
                //if the previous is not able to be concated, skip.
                if(!dp[j]){
                    continue;
                }
                String temp = word.substring(j,i);
                if(dict.contains(temp)){
                    //set to true and continue to next position.
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}

1268. Search Suggestions System

Description

Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = [“mobile”,”mouse”,”moneypot”,”monitor”,”mousepad”], searchWord = “mouse” Output: [ [“mobile”,”moneypot”,”monitor”], [“mobile”,”moneypot”,”monitor”], [“mouse”,”mousepad”], [“mouse”,”mousepad”], [“mouse”,”mousepad”] ] Explanation: products sorted lexicographically = [“mobile”,”moneypot”,”monitor”,”mouse”,”mousepad”] After typing m and mo all products match and we show user [“mobile”,”moneypot”,”monitor”] After typing mou, mous and mouse the system suggests [“mouse”,”mousepad”] Example 2:

Input: products = [“havana”], searchWord = “havana” Output: [[“havana”],[“havana”],[“havana”],[“havana”],[“havana”],[“havana”]] Example 3:

Input: products = [“bags”,”baggage”,”banner”,”box”,”cloths”], searchWord = “bags” Output: [[“baggage”,”bags”,”banner”],[“baggage”,”bags”,”banner”],[“baggage”,”bags”],[“bags”]] Example 4:

Input: products = [“havana”], searchWord = “tatiana” Output: [[],[],[],[],[],[],[]]

Constraints:

1 <= products.length <= 1000 There are no repeated elements in products. 1 <= Σ products[i].length <= 2 * 10^4 All characters of products[i] are lower-case English letters. 1 <= searchWord.length <= 1000 All characters of searchWord are lower-case English letters.

Solution

Intuition

In a sorted list of words, for any word A[i], all its sugested words must following this word in the list.

For example, if A[i] is a prefix of A[j], A[i] must be the prefix of A[i + 1], A[i + 2], …, A[j]

Explanation

With this observation, we can binary search the position of each prefix of search word, and check if the next 3 words is a valid suggestion.

Complexity

Time O(NlogN) for sorting Space O(logN) for quick sort.

Time O(logN) for each query Space O(query) for each query where I take word operation as O(1)

class Solution {
    
    
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        String key = "";
        List<List<String>> res = new ArrayList();
        for(char c: searchWord.toCharArray()){
            key += c;
            int idx = Arrays.binarySearch(products, key);
            if(idx<0){
                idx = -idx - 1;
            }
            res.add(checkValidation(key, products, idx));
        }
        return res;
    }
    
    private List<String> checkValidation(String searchWord, String[] words, int idx){
        List<String> res = new ArrayList();
        int len = searchWord.length();
        for(int i = idx; i<words.length && i < idx+3; i++){
            String word = words[i];
            if(word.length() >= len && searchWord.equals(word.substring(0,len))){
                res.add(word);
            }else{
                break;
            }
        }
        return res;
    }
}

#2020-02-06

1044. Longest Duplicate Substring

Description

Given a string S, consider all duplicated substrings: (contiguous) substrings of S that occur 2 or more times. (The occurrences may overlap.)

Return any duplicated substring that has the longest possible length. (If S does not have a duplicated substring, the answer is “”.)

Example 1:

Input: “banana” Output: “ana” Example 2:

Input: “abcd” Output: “”

Note:

2 <= S.length <= 10^5 S consists of lowercase English letters.

Solution

class Solution {
    //use binary search to find the largest lenth of the string.
    public String longestDupSubstring(String S) {
      int lo = 1;
        int hi = S.length()-1;
        int idx = -1;
        while(lo<=hi){
            int mid = lo+(hi-lo)/2;
            int startIndex = find(S,mid);
            if(startIndex==-1){
                hi = mid-1;
            }
            else{
                idx = startIndex;
                lo = mid+1;
            }
        }
        return idx==-1? "" : S.substring(idx,idx+hi);
    }
    
    //if use hashmap, memory will exceed for extra long string, use hash further.
    public int find(String S, int len){
        if(len == 0) return -1;
        HashSet<String> seen = new HashSet();
    
        for(int i = 0;i<=S.length()-len;i++){
            String temp = S.substring(i,i+len);
            if(seen.contains(temp)) return i;
            seen.add(temp);
        }
        return -1;
    }
}

694. Number of Distinct Islands

Description

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Count the number of distinct islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

Example 1: 11000 11000 00011 00011 Given the above grid map, return 1. Example 2: 11011 10000 00001 11011 Given the above grid map, return 3.

Notice that: 11 1 and 1 11 are considered different island shapes, because we do not consider reflection / rotation. Note: The length of each dimension in the given grid does not exceed 50.

Solution

//use a char to record the movement to destroy an island from left up corner.
//use trversal to make sure start from the left up corner.
//use int[][] dirs to make sure the order of the direction it will try to use.
class Solution {
    int[][] dirs = new int[][][[0,-1],[0,1],[1,0],[-1,0]];
    char[] dir_char = new char[]{'u','d','r','l'};
    public int numDistinctIslands(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length ==0) return 0;
        HashSet<String> seen = new HashSet();
        int count = 0;
        for(int i = 0;i<grid.length;i++){
            for(int j = 0;j<grid[0].length;j++){
                if(grid[i][j]==1){
                    StringBuilder sb = new StringBuilder();
                    search(grid, 's', j,i,sb);
                    String path = sb.toString();
                    if(!seen.contains(path)) {
                        count++;
                        seen.add(path);
                    }
                }
            }
        }
        return count;
        
    }
    
    private void search(int[][] grid, char d, int x, int y , StringBuilder sb ){
        grid[y][x] = 0;
        sb.append(d);
        for(int i = 0;i<4;i++){
            int newx = x +  dirs[i][0];
            int newy =  y + dirs[i][1];
            if(newx < 0 || newy<0 || newy>=grid.length || newx >= grid[y].length || grid[newy][newx]!=1 ) continue;
            search(grid, dir_char[i], newx, newy, sb);
            //why adding a back step?
            //[1,1,0]
            //[0,1,1]
            //[0,0,0]
            //[1,1,1]
            //[0,1,0]
            //both path are srdr.
            //with b: srdrbbb & srdbrbb
            sb.append('b');
        }
        
    }
}

1167. Minimum Cost to Connect Sticks

Description

You have some sticks with positive integer lengths.

You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y. You perform this action until there is one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

Example 1:

Input: sticks = [2,4,3] Output: 14 Example 2:

Input: sticks = [1,8,3,5] Output: 30

Constraints:

1 <= sticks.length <= 10^4 1 <= sticks[i] <= 10^4

Solution

//always pick the shortest, casue the earlier the etick participate in the joining, the more duplication it will be.
class Solution {
    public int connectSticks(int[] sticks) {
        if(sticks == null || sticks.length==0) return 0;
        PriorityQueue<Integer> pq = new PriorityQueue(sticks.length);
        for(int num: sticks){
            pq.offer(num);
        }
        int count = 0;
        while(pq.size()>1){
            int cost = pq.poll() + pq.poll();
            count+=cost;
            pq.offer(cost);
        }
        return count;
    }
}

2020-02-09

1000. Minimum Cost to Merge Stones

Description

There are N piles of stones arranged in a row. The i-th pile has stones[i] stones.

A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.

Find the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

Example 1:

Input: stones = [3,2,4,1], K = 2 Output: 20 Explanation: We start with [3, 2, 4, 1]. We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1]. We merge [4, 1] for a cost of 5, and we are left with [5, 5]. We merge [5, 5] for a cost of 10, and we are left with [10]. The total cost was 20, and this is the minimum possible. Example 2:

Input: stones = [3,2,4,1], K = 3 Output: -1 Explanation: After any merge operation, there are 2 piles left, and we can’t merge anymore. So the task is impossible. Example 3:

Input: stones = [3,5,1,2,6], K = 3 Output: 25 Explanation: We start with [3, 5, 1, 2, 6]. We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6]. We merge [3, 8, 6] for a cost of 17, and we are left with [17]. The total cost was 25, and this is the minimum possible.

Note:

1 <= stones.length <= 30 2 <= K <= 30 1 <= stones[i] <= 100

Solution

class Solution {

    public static int mergeStones(int[] stones, int K) {
        if (stones == null || stones.length == 0 || (stones.length - 1) % (K - 1) != 0) {
            return -1;
        }
        int len = stones.length;
        int[] prefix = new int[len + 1];
        //prefix to count sum between i & j.
        for (int i = 0; i < len; i++) {
            prefix[i + 1] = prefix[i] + stones[i];
        }
        int[][] dp = new int[len][len];
        //base case.
        for (int i = 0; i <= len - K; i++) {
            dp[i][i + K - 1] = prefix[i + K] - prefix[i];
        }

        //m is the interval.
        for (int m = K+1; m <= len; m++) {
            //start from 0 to tail.
            for(int i = 0; i+m <=len;i++ ){
                int j = i+m-1;
                dp[i][j] = Integer.MAX_VALUE;
                //must jump K-1 so i->i+mid is always valid, otherwise will always getting 0 cause the min.
                for(int mid = i; mid <j;mid+=K-1){
                    dp[i][j] = Math.min(dp[i][mid]+dp[mid+1][j], dp[i][j]);
                }
                if((j-i)%(K-1)==0){
                    //need to add the sum, cause no matter how to group inside i->j, the count is always sum[i,j], plus the cost to group i->mid and mid+1->j.
                    dp[i][j] += prefix[j+1] - prefix[i];
                }

            }
        }

        return dp[0][len-1];
    }
}

866. Prime Palindrome

Description

Find the smallest prime palindrome greater than or equal to N.

Recall that a number is prime if it’s only divisors are 1 and itself, and it is greater than 1.

For example, 2,3,5,7,11 and 13 are primes.

Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.

For example, 12321 is a palindrome.

Example 1:

Input: 6 Output: 7 Example 2:

Input: 8 Output: 11 Example 3:

Input: 13 Output: 101

Note:

1 <= N <= 10^8 The answer is guaranteed to exist and be less than 2 * 10^8.

Solution

Intuition Write some example, you find all even length palindromes are divisible by 11. So we need to search only palindrome with odd length.

We can prove as follow: 11 % 11 = 0 1111 % 11 = 0 111111 % 11 = 0 11111111 % 11 = 0

So: 1001 % 11 = (1111 - 11 * 10) % 11 = 0 100001 % 11 = (111111 - 1111 * 10) % 11 = 0 10000001 % 11 = (11111111 - 111111 * 10) % 11 = 0

For any palindrome with even length: abcddcba % 11 = (a * 10000001 + b * 100001 * 10 + c * 1001 * 100 + d * 11 * 1000) % 11 = 0

All palindrome with even length is multiple of 11. So among them, 11 is the only one prime if (8 <= N <= 11) return 11

For other cases, we consider only palindrome with odd dights.

More Generally Explanation from @chuan-chih: A number is divisible by 11 if sum(even digits) - sum(odd digits) is divisible by 11. Base case: 0 Inductive step: If there is no carry when we add 11 to a number, both sums +1. Whenever carry happens, one sum -10 and the other +1. The invariant holds in both cases.

Time Complexity O(10000) to check all numbers 1 - 10000. isPrime function is O(sqrt(x)) in worst case. But only sqrt(N) worst cases for 1 <= x <= N In general it’s O(logx)

class Solution {
    public int primePalindrome(int N) {
        if(N>=8 && N<=11) return 11;
        for(int x = 1; x<=100000;x++){
            String s = String.valueOf(x);
            String r = new StringBuilder(s).reverse().toString();
            int y = Integer.parseInt(s+r.substring(1));
            if(y>=N && isPrime(y)) return y;
        }
        return -1;
    }

    private boolean isPrime(int N){
        if(N < 2 || N % 2 == 0) return N==2;
        for(int  i = 3;i*i<=N;i+=2){
            if(N%i==0) return false;
        }
        return true;
    }
}

1102. Path With Maximum Minimum Value

Description

Given a matrix of integers A with R rows and C columns, find the maximum score of a path starting at [0,0] and ending at [R-1,C-1].

The score of a path is the minimum value in that path. For example, the value of the path 8 → 4 → 5 → 9 is 4.

A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).

Example 1:

Input: [[5,4,5],[1,2,6],[7,4,6]] Output: 4 Explanation: The path with the maximum score is highlighted in yellow. Example 2:

Input: [[2,2,1,2,2,2],[1,2,2,2,1,2]] Output: 2 Example 3:

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

Note:

1 <= R, C <= 100 0 <= A[i][j] <= 10^9

Solution

even though the pq might include some node not int e final path, the min will always be in the path. Cause you always choose the larger one, so the node outside the path is still larger than the one in the node, so it will not effect the min inside the path.

class Solution {
    class cell{
        int row, col, val;
        cell(int row, int col, int val){
            this.row = row;
            this.col = col;
            this.val = val;
        }
    }
    static int[][] moves = new int[][] [[-1, 0], [1, 0], [0, 1], [0, -1]];
    public int maximumMinimumPath(int[][] A) {
        PriorityQueue<cell> q = new PriorityQueue<>((a,b)->b.val-a.val);
        q.add(new cell(0,0,A[0][0]));
        boolean[][] visited = new boolean[A.length][A[0].length];
        visited[0][0] = true;
        int min = A[0][0];
        while(!q.isEmpty()){
            cell cur = q.poll();
            if(cur.val<min) min = cur.val;
            if(cur.row == A.length-1&& cur.col == A[0].length-1) return min;
            for(int[] dir : moves){
                int newr = cur.row + dir[0];
                int newc = cur.col + dir[1];
                if(newr>= 0 && newr < A.length && newc >=0 && newc < A[0].length && !visited[newr][newc]){
                    q.add(new cell(newr, newc, A[newr][newc]));
                    visited[newr][newc] = true;
                }
            }
        }
        return -1;
    }

}

1099. Two Sum Less Than K

Description

Given an array A of integers and integer K, return the maximum S such that there exists i < j with A[i] + A[j] = S and S < K. If no i, j exist satisfying this equation, return -1.

Example 1:

Input: A = [34,23,1,24,75,33,54,8], K = 60 Output: 58 Explanation: We can use 34 and 24 to sum 58 which is less than 60. Example 2:

Input: A = [10,20,30], K = 15 Output: -1 Explanation: In this case it’s not possible to get a pair sum less that 15.

Note:

1 <= A.length <= 100 1 <= A[i] <= 1000 1 <= K <= 2000

Solution

class Solution {
    public int twoSumLessThanK(int[] A, int K) {
        Arrays.sort(A);
        int i = 0, j = A.length-1, max = -1;
        while(i<j){
            int sum = A[i] + A[j];
            if(sum<K){
                max = Math.max(sum, max);
                i++;
            }else{
                j--;
            }
        }
        return max;
    }
}

146. LRU Cache

Description

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up: Could you do both operations in O(1) time complexity?

Example:

cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4

Solution

class LRUCache {

    class Node{
        Node pre;
        Node next;
        int value;
        int key;
    }
    
    Node head;
    Node tail;
    int capacity;
    int count;
    HashMap<Integer, Node> cache;
        
    private void addNode(Node node){
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        
    }
    
    private void removeNode(Node node){
        Node preNode = node.pre;
        Node nextNode = node.next;
        
        preNode.next = nextNode;
        nextNode.pre = preNode;
    }
    
    private void moveToHead(Node node){
        this.removeNode(node);
        this.addNode(node);
    }
    
    public LRUCache(int capacity) {
        head = new Node();
        tail = new Node();
        head.next =tail;
        head.pre = null;
        tail.pre = head;
        tail.next = null;
        cache = new HashMap();
        this.capacity = capacity;
        this.count = 0;
    }
    
    public int get(int key) {
        Node cur = cache.get(key);
        if(cur == null){
            return -1;
        }
        this.moveToHead(cur);
        return cur.value;
    }
    
    public void put(int key, int value) {
        if(cache.containsKey(key)){
            Node cur = cache.get(key);
            removeNode(cur);
            cur.value = value;
            addNode(cur);
            cache.put(key,cur);
        }else{
            Node cur = new Node();
            cur.key = key;
            cur.value = value;
            addNode(cur);
            cache.put(key,cur);
            count++;
        }
        while(count >capacity){
            cache.remove(tail.pre.key);
            removeNode(tail.pre);
            
            count--;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

56. Merge Intervals

Description

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. Example 2:

Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Solution

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals==null || intervals.length==0) return new int[0][0];
        Arrays.sort(intervals,new Comparator<int[]>(){
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });

        int start = intervals[0][0],end = intervals[0][1];
        List<int[]> res = new ArrayList<int[]>();
        for(int i=1;i<intervals.length;i++){
            int[] cur = intervals[i];
            if(cur[0]<=end){
                end = Math.max(cur[1], end);
            }else{
                res.add(new int[]{start,end});
                start = cur[0];
                end = cur[1];
            }
        }
        res.add(new int[]{start,end});
        int[][] resArray = new int[res.size()][2];
        for(int i = 0;i<resArray.length;i++){
            resArray[i] = res.get(i);
        }
        return resArray;
    }
}

269. Alien Dictionary

Description

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:

Input: [ “wrt”, “wrf”, “er”, “ett”, “rftt” ]

Output: “wertf” Example 2:

Input: [ “z”, “x” ]

Output: “zx” Example 3:

Input: [ “z”, “x”, “z” ]

Output: “”

Explanation: The order is invalid, so return “”. Note:

You may assume all letters are in lowercase. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary. If the order is invalid, return an empty string. There may be multiple valid order of letters, return any one of them is fine.

Solution


//main idea is to compare each word from the first letter that is different.
//use a set to store all letter that are behind this char.
//use topological sort to find the relative order.
class Solution {
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) return "";
        HashMap<Character, Integer> degree = new HashMap();
        HashMap<Character, Set<Character>> order = new HashMap<Character, Set<Character>>();
        for (String word : words) {
            for (char c : word.toCharArray()) {
                degree.put(c, 0);
            }
        }

        for (int idx = 0; idx < words.length - 1; idx++) {
            String cur = words[idx];
            String next = words[idx + 1];
            int length = Math.min(cur.length(), next.length());
            for(int i = 0;i<length;i++){
                char c1 = cur.charAt(i);
                char c2 = next.charAt(i);
                if (c1 != c2) {
                    Set<Character> set = order.getOrDefault(c1, new HashSet<>());
                    //if (!set.contains(c2)) {
                        set.add(c2);
                        order.put(c1, set);
                        degree.put(c2, degree.get(c2) + 1);
                    //}
                    break;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        Queue<Character> q = new LinkedList<>();
        for(char c: degree.keySet()){
            if(degree.get(c)==0){
                q.add(c);
            }
        }
        while(!q.isEmpty()){
            char c = q.poll();
            sb.append(c);
            if(order.containsKey(c)){
                for(char c2 :order.get(c)){
                    int d = degree.get(c2)-1;
                    degree.put(c2,d);
                    if(d==0) q.add(c2);
                }
            }
        }
        if(sb.length()!=degree.size()) return "";
        return sb.toString();
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        String[] in = new String[]{"wrt","wrf","er","ett","rftt"};
        System.out.println(s.alienOrder(in));
    }
}

2020-02-13

76. Minimum Window Substring

Description

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = “ADOBECODEBANC”, T = “ABC” Output: “BANC” Note:

If there is no such window in S that covers all characters in T, return the empty string “”. If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

Solution

//main idea is to use count to see if the current range contains all chars in t.
//but need to be careful when duplicated char in s, so only update count when map.get(c) is larger than 0;
class Solution {
    public String minWindow(String s, String t) {
        if(s==null || t==null || s.length() == 0|| t.length()==0){
            return "";
        }
        HashMap<Character, Integer> map = new HashMap();
        int len = s.length();
        int count = t.length(); // the number of characters that I need to match
        for(char c : t.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);
        int minLeft = -1,minRight = -1;
        int i = 0,j=0,minLen = s.length();
        
        while(j<len){
            char c = s.charAt(j);
            if(map.containsKey(c)){
                map.put(c,map.get(c)-1);
                //if map.get(c) is already negative, means this one is duplicate, no need to decrement.
                if(map.get(c)>=0) count--;
            }
            
            while(count == 0 && i<=j){
                int curLen = j-i+1;
                if(curLen<=minLen){
                    minLeft = i;
                    minRight = j;
                    minLen = curLen;
                }
                
                char leftC = s.charAt(i);
                if(map.containsKey(leftC)){
                    map.put(leftC, map.get(leftC) + 1);
                    //if the previous map.get(c) is negative, means it's duplicated, there still will be another c in the range.
                    //so no need to increment.
                    if(map.get(leftC) >= 1) count++;
                }
                i++;
            }
            
            j++;
        }
        return minLeft==-1 && minRight==-1?"":s.substring(minLeft,minRight+1);
    }
}

560. Subarray Sum Equals K

Description

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1: Input:nums = [1,1,1], k = 2 Output: 2 Note: The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solution

//main idea is to solve this problem is SUM[i, j]. So if we know SUM[0, i - 1] and SUM[0, j], then we can easily get SUM[i, j]. To achieve this, we just need to go through the array, calculate the current sum and save number of all seen PreSum to a HashMap. Time complexity O(n), Space complexity O(n).
class Solution {
    public int subarraySum(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        HashMap<Integer,Integer> preSum = new HashMap();
        preSum.put(0,1);
        int res = 0, sum =0;
        for(int i = 0;i<nums.length;i++){
            int cur = nums[i];
            sum+=cur;
            if(preSum.containsKey(sum-k)){
                res += preSum.get(sum-k);
            }
            preSum.put(sum,preSum.getOrDefault(sum,0)+1);
        }
        return res;
    }
}

139. Word Break

Description

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1:

Input: s = “leetcode”, wordDict = [“leet”, “code”] Output: true Explanation: Return true because “leetcode” can be segmented as “leet code”. Example 2:

Input: s = “applepenapple”, wordDict = [“apple”, “pen”] Output: true Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”. Note that you are allowed to reuse a dictionary word. Example 3:

Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] Output: false

Solution

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> dict = new HashSet<>(wordDict);
        int len = s.length();
        boolean[] dp = new boolean[len+1];
        dp[0] = true;
        //note: j is always 1 less than i, so in the range 0->i-1, dp[] are all valid.
        //so just need to check if dp[j] and substring(j,i) are both valid then dp[i] is valid.
        for(int i = 1;i<=len;i++){
            for(int j = 0;j<i;j++){
                if(dp[j] && dict.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}

2020-02-16

986. Interval List Intersections

Description

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval {a, b} (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Example 1:

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

Note:

0 <= A.length < 1000 0 <= B.length < 1000 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

Main Idea

main idea is to use two pointer and iterate through. start is the max among two starts, end is the min among two ends. everytime end >= start, means there’s a intefval. which end is reached, should increment.

Solution

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        if (A == null || A.length == 0 || B == null || B.length == 0) {
            return new int[0][0];
        }
        int alen = A.length, blen = B.length;
        int i = 0, j = 0;
        List<int[]> res = new ArrayList();
        while( i<alen && j<blen){
            int[] a = A[i];
            int[] b = B[j];
            int start = Math.max(a[0],b[0]);
            int end = Math.min(a[1],b[1]);
            
            if(end >= start){
                res.add(new int[]{start, end});
            }
            if(end == a[1]) i++;
            if(end == b[1]) j++;
        }
        int[][] resArray = new int[res.size()][2];
        for(int idx = 0;idx<res.size();idx++){
            resArray[idx] = res.get(idx);
        }
        return resArray;
    }
}

140. Word Break II

Description

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1:

Input: s = “catsanddog” wordDict = [“cat”, “cats”, “and”, “sand”, “dog”] Output: [ “cats and dog”, “cat sand dog” ] Example 2:

Input: s = “pineapplepenapple” wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”] Output: [ “pine apple pen apple”, “pineapple pen apple”, “pine applepen apple” ] Explanation: Note that you are allowed to reuse a dictionary word. Example 3:

Input: s = “catsandog” wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] Output: []

Main Idea

maintain a map to avoid duplicate search.

break the string into two part, if the first part is in the dict, then search into the remaining part and return the all possible break for the remaining part.

glue all the result together and return.

before return add to map.

Solution

class Solution {
    
    HashMap<String, List<String>> map;
    HashSet<String> wordSet;
    public List<String> wordBreak(String s, List<String> wordDict) {
        map = new HashMap();
        wordSet = new HashSet(wordDict);
        return helper(s);
        
    }
    
    public List<String> helper(String s){
        List<String> res = new ArrayList();
        if(s == null || s.isEmpty()) return res;
        if(map.containsKey(s)) return map.get(s);
        if(wordSet.contains(s)) {
            res.add(s);
        } 
        for(int i = 1;i<s.length();i++){
            String t = s.substring(0, i);
            if(wordSet.contains(t)){
                List<String> temp = helper(s.substring(i));
                if(temp!=null && temp.size()!=0){
                    for(int j = 0;j<temp.size();j++){
                        res.add(t+" "+temp.get(j));
                    }
                }
            }
        }
        map.put(s,res);
        return res;
    }
}

1249. Minimum Remove to Make Valid Parentheses

Description

Given a string s of ‘(‘ , ‘)’ and lowercase English characters.

Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string.

Example 1:

Input: s = “lee(t(c)o)de)” Output: “lee(t(c)o)de” Explanation: “lee(t(co)de)” , “lee(t(c)ode)” would also be accepted. Example 2:

Input: s = “a)b(c)d” Output: “ab(c)d” Example 3:

Input: s = “))((“ Output: “” Explanation: An empty string is also valid. Example 4:

Input: s = “(a(b(c)d)” Output: “a(b(c)d)”

Constraints:

1 <= s.length <= 10^5 s[i] is one of ‘(‘ , ‘)’ and lowercase English letters.

Main Idea

Use stack to record the index of left par, everytime meet a right, pop, make a pair.

  1. if the right one, and st is empty, means it’s not valid, marked it.
  2. if after the iteration, st is still not empty, means left par in the stack is not valid, mark all.
  3. remove all char marked invalid.

Solution

class Solution {
    public String minRemoveToMakeValid(String s) {
        if(s == null || s.length() == 0){
            return s;
        }
        Stack<Integer> st = new Stack();
        StringBuilder sb = new StringBuilder(s);
        for(int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            if(c == '('){
                st.push(i);
            }else if(c == ')'){
                if(st.isEmpty()){
                    sb.setCharAt(i,'*');
                }else{
                    st.pop();
                }
            }
        }
        while(!st.isEmpty()){
            sb.setCharAt(st.pop(),'*');
        }
        return sb.toString().replaceAll("\\*","");
        
    }
}

34. Find First and Last Position of Element in Sorted Array

Description

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2:

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

Main Idea

The last step before end, there will be only two elements, which is [i,j].

There will only be six scenarios which are:

  1. [t,t+1]
  2. [t,t]
  3. [t-1,t]
  4. [t-2,t-1]
  5. [t-1,t+1]
  6. [t+1,t-2]

4-6 are all invalid, so the return value will always not equals target, we don’t need to take care of.

For 1-3, if we are lokking for left bound:

i=mid, j = mid+1

  1. [t,t+1]
  2. [t,t]
  3. [t-1,t]

1,2: a[mid] >= target, return i=mid, j =mid;

3: a[mid] < target, return i = mid+1, j = mid+1;

so the returned i will be the answer.

Looking for right boundary:

We need to bias the mid to avoid the i stuck in the loop.

So mid = (i+j)/2 + 1;

i=mid-1, j = mid

  1. [t,t+1]
  2. [t,t]
  3. [t-1,t]

for 1: a[mid] > t: return i = mid-1, j = mid-1;

for 2,3 : a[mid] <= t: return i = mid, j = mid;

now returned j is the answer.

So In order to find a solution for binary search, think about the last step.

The problem can be simply broken down as two binary searches for the begining and end of the range, respectively:

First let’s find the left boundary of the range. We initialize the range to [i=0, j=n-1]. In each step, calculate the middle element [mid = (i+j)/2]. Now according to the relative value of A[mid] to target, there are three possibilities:

If A[mid] < target, then the range must begins on the right of mid (hence i = mid+1 for the next iteration) If A[mid] > target, it means the range must begins on the left of mid (j = mid-1) If A[mid] = target, then the range must begins on the left of or at mid (j= mid) Since we would move the search range to the same side for case 2 and 3, we might as well merge them as one single case so that less code is needed:

2*. If A[mid] >= target, j = mid;

Surprisingly, 1 and 2* are the only logic you need to put in loop while (i < j). When the while loop terminates, the value of i/j is where the start of the range is. Why?

No matter what the sequence originally is, as we narrow down the search range, eventually we will be at a situation where there are only two elements in the search range. Suppose our target is 5, then we have only 7 possible cases:

case 1: [5 7] (A[i] = target < A[j]) case 2: [5 3] (A[i] = target > A[j]) case 3: [5 5] (A[i] = target = A[j]) case 4: [3 5] (A[j] = target > A[i]) case 5: [3 7] (A[i] < target < A[j]) case 6: [3 4] (A[i] < A[j] < target) case 7: [6 7] (target < A[i] < A[j]) For case 1, 2 and 3, if we follow the above rule, since mid = i => A[mid] = target in these cases, then we would set j = mid. Now the loop terminates and i and j both point to the first 5.

For case 4, since A[mid] < target, then set i = mid+1. The loop terminates and both i and j point to 5.

For all other cases, by the time the loop terminates, A[i] is not equal to 5. So we can easily know 5 is not in the sequence if the comparison fails.

In conclusion, when the loop terminates, if A[i]==target, then i is the left boundary of the range; otherwise, just return -1;

For the right of the range, we can use a similar idea. Again we can come up with several rules:

If A[mid] > target, then the range must begins on the left of mid (j = mid-1) If A[mid] < target, then the range must begins on the right of mid (hence i = mid+1 for the next iteration) If A[mid] = target, then the range must begins on the right of or at mid (i= mid) Again, we can merge condition 2 and 3 into:

2* If A[mid] <= target, then i = mid; However, the terminate condition on longer works this time. Consider the following case:

[5 7], target = 5 Now A[mid] = 5, then according to rule 2, we set i = mid. This practically does nothing because i is already equal to mid. As a result, the search range is not moved at all!

The solution is by using a small trick: instead of calculating mid as mid = (i+j)/2, we now do:

mid = (i+j)/2+1 Why does this trick work? When we use mid = (i+j)/2, the mid is rounded to the lowest integer. In other words, mid is always biased towards the left. This means we could have i == mid when j - i == mid, but we NEVER have j == mid. So in order to keep the search range moving, you must make sure the new i is set to something different than mid, otherwise we are at the risk that i gets stuck. But for the new j, it is okay if we set it to mid, since it was not equal to mid anyways. Our two rules in search of the left boundary happen to satisfy these requirements, so it works perfectly in that situation. Similarly, when we search for the right boundary, we must make sure i won’t get stuck when we set the new i to i = mid. The easiest way to achieve this is by making mid biased to the right, i.e. mid = (i+j)/2+1.

Solution

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1,-1};
        if(nums == null || nums.length == 0) return res;
        int i = 0, j = nums.length - 1;
        while(i<j){
            int mid = i + (j-i)/2;
            if(nums[mid]<target) i = mid+1;
            else j = mid;
        }
        if(nums[i]!= target) return res;
        res[0] = i;
        j = nums.length-1;
        while(i<j){
            int mid = i + (j-i)/2 + 1;
            if(nums[mid] > target) j = mid - 1;
            else i = mid;
        }
        res[1] = j;
        return res;
    }
}

158. Read N Characters Given Read4 II - Call multiple times

Description

Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.

Method read4:

The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf.

The return value is the number of actual characters read.

Note that read4() has its own file pointer, much like FILE *fp in C.

Definition of read4:

Parameter:  char[] buf
Returns:    int

Note: buf[] is destination not source, the results from read4 will be copied to buf[] Below is a high level example of how read4 works:

File file(“abcdefghijk”); // File is “abcdefghijk”, initially file pointer (fp) points to ‘a’ char[] buf = new char[4]; // Create buffer with enough space to store characters read4(buf); // read4 returns 4. Now buf = “abcd”, fp points to ‘e’ read4(buf); // read4 returns 4. Now buf = “efgh”, fp points to ‘i’ read4(buf); // read4 returns 3. Now buf = “ijk”, fp points to end of file

Method read:

By using the read4 method, implement the method read that reads n characters from the file and store it in the buffer array buf. Consider that you cannot manipulate the file directly.

The return value is the number of actual characters read.

Definition of read:

Parameters: char[] buf, int n
Returns:    int

Note: buf[] is destination not source, you will need to write the results to buf[]

Example 1:

File file(“abc”); Solution sol; // Assume buf is allocated and guaranteed to have enough space for storing all characters from the file. sol.read(buf, 1); // After calling your read method, buf should contain “a”. We read a total of 1 character from the file, so return 1. sol.read(buf, 2); // Now buf should contain “bc”. We read a total of 2 characters from the file, so return 2. sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0. Example 2:

File file(“abc”); Solution sol; sol.read(buf, 4); // After calling your read method, buf should contain “abc”. We read a total of 3 characters from the file, so return 3. sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0.

Note:

Consider that you cannot manipulate the file directly, the file is only accesible for read4 but not for read. The read function may be called multiple times. Please remember to RESET your class variables declared in Solution, as static/class variables are persisted across multiple test cases. Please see here for more details. You may assume the destination buffer array, buf, is guaranteed to have enough space for storing n characters. It is guaranteed that in a given test case the same buffer buf is called by read.

Solution

/**
 * The read4 API is defined in the parent class Reader4.
 *     int read4(char[] buf); 
 */
public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    Queue<Character> q = new LinkedList();
    public int read(char[] buf, int n) {
        int remain = n;
        int i = 0;
        while(remain > 0){
            if(q.size()<4){
                char[] b = new char[4];
                int c = read4(b);
                for(int k = 0;k<c;k++){
                    q.add(b[k]);
                }
            }
            for(int k = 0; k<4 && remain > 0;k++,remain--){
                 if(q.isEmpty()){
                    return n-remain;
                }
                buf[i++] = q.poll();
            }
               
            
        }
        return n-remain;
    }
}


438. Find All Anagrams in a String

Destination

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

Main Idea

use a int[26] and a count to record the status. if int[c-‘a’] is larger than 0, means it’s not in the cur range. if is less than 0, means there’s duplicate. iterate through the array, each step, pop out the previous one and take a new one.

maintain the dict and count.

If the count is 0, means the current range include all char in p, so record it in the res.

Solution

class Solution {

    public List<Integer> findAnagrams(String s, String p) {
        int[] dict = new int[26];
        int count = 0;
        HashSet<Character> set = new HashSet();
        for (char c : p.toCharArray()) {
            dict[c - 'a']++;
            count++;
            set.add(c);
        }
        List<Integer> res = new ArrayList();
        int len = p.length();
        for (int i = 0; i < s.length(); i++) {
            if (i < len) {
                char c = s.charAt(i);
                if (set.contains(c)) {
                    dict[c - 'a']--;
                    if (dict[c - 'a'] >= 0) {
                        count--;
                    }
                }
            } else {
                char cur = s.charAt(i);
                char pre = s.charAt(i-len);
                if (set.contains(pre)) {
                    dict[pre - 'a']++;
                    if (dict[pre - 'a'] > 0) {
                        count++;
                    }
                }
                if (set.contains(cur)) {
                    dict[cur - 'a']--;
                    if (dict[cur - 'a'] >= 0) {
                        count--;
                    }
                }
            }
            if (count == 0) {
                res.add(i - len + 1);
            }
        }
        return res;

    }
}