2115. Find All Possible Recipes from Given Supplies

Problem

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

Solution

class Solution {
    private HashMap<String, Integer> recipes;
    private HashMap<String, Boolean> visitedAndFound; // false to detect cycle
    private List<List<String>> ingredients;
    private HashSet<String> supplies;

    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        this.recipes = new HashMap<>();
        for (int i = 0; i < recipes.length; i++) {
            this.recipes.put(recipes[i], i);
        }
        this.ingredients = ingredients;
        this.visitedAndFound = new HashMap<>();
        this.supplies = new HashSet<>();
        for (String supply : supplies) {
            this.supplies.add(supply);
        }

        List<String> res = new LinkedList<>();
        for (String recipe : recipes) {
            if (findRecipe(recipe)) {
                res.add(recipe);
            }
        }
        return res;
    }

    public boolean findRecipe(String recipe) {
        if (visitedAndFound.containsKey(recipe)) {
            return visitedAndFound.get(recipe);
        }
        visitedAndFound.put(recipe, false);

        if (supplies.contains(recipe)) {
            visitedAndFound.put(recipe, true);
            return true;
        }
        if (!recipes.containsKey(recipe)) {
            return false;
        }

        for (String ingredient : ingredients.get(recipes.get(recipe))) {
            if (findRecipe(ingredient) == false) {
                return false;
            }
        }
        visitedAndFound.put(recipe, true);
        return true;
    }
}

253. Meeting Rooms II

Problem

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

Constraints:

1 <= intervals.length <= 10⁴
0 <= start_i < end_i <= 10⁶

Java Solution

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int room = 0, endIdx = 0;
        for (int i = 0; i < starts.length; i++) {
            if (starts[i] < ends[endIdx]) {
                room++;
            } else {
                endIdx++;
            }
        }
        return room;
    }
}

539. Minimum Time Difference

Problem

Given a list of 24-hour clock time points in “HH:MM” format, return the minimum minutes difference between any two time-points in the list.

Example 1:

Input: timePoints = ["23:59","00:00"]
Output: 1

Example 2:

Input: timePoints = ["00:00","23:59","00:00"]
Output: 0

Constraints:

2 <= timePoints.length <= 2 * 10⁴
timePoints[i] is in the format “HH:MM”.

Java Solution

class Solution {
    public int findMinDifference(List<String> timePoints) {
        int[] exist = new int[24 * 60];
        for (String time : timePoints) {
            int minutes = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3, 5));
            if (exist[minutes] != 0) {
                return 0;
            } else {
                exist[minutes] = 1;
            }
        }

        int prev = -1;
        int res = Integer.MAX_VALUE, start = Integer.MAX_VALUE, end = Integer.MIN_VALUE;
        for (int i = 0; i < 24 * 60; i++) {
            if (exist[i] == 1) {
                if (prev == -1) {
                    prev = i;
                } else {
                    res = Math.min(res, i - prev);
                }
                prev = i;
                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }
        return Math.min(res, 24 * 60 - (end - start));
    }
}

1048. Longest String Chain

Problem

You are given an array of words where each word consists of lowercase English letters.

word_A is a predecessor of word_B if and only if we can insert exactly one letter anywhere in word_A without changing the order of the other characters to make it equal to word_B.

For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chain is a sequence of words [word₁, word₂, ..., word_k] with k >= 1, where word₁ is a predecessor of word₂, word₂ is a predecessor of word₃, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

Example 1:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chains is ["a","ba","bda","bdca"].

Example 2:

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

Example 3:

Input: words = ["abcd","dbqca"]
Output: 1
Explanation: The trivial word chain ["abcd"] is one of the longest word chains.
["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of lowercase English letters.

Java Solution

class Solution {
    public int longestStrChain(String[] words) {
        HashMap<String, Integer> longestPre = new HashMap<>(); // Including the word itself
        TreeMap<Integer, List<String>> wordsByCharLength = new TreeMap<>();
        int res = 1;
        for (String word : words) {
            wordsByCharLength.putIfAbsent(word.length(), new LinkedList<>());
            wordsByCharLength.get(word.length()).add(word);
        }
        int longest = wordsByCharLength.lastKey();
        for (int i = 1; i <= longest; i++) {
            if (!wordsByCharLength.containsKey(i)) {
                continue;
            }
            for (String curWord : wordsByCharLength.get(i)) {
                if (!wordsByCharLength.containsKey(i - 1)) {
                    longestPre.put(curWord, 1);
                    continue;
                }
                int prevLongest = 0;
                for (String prevWord : wordsByCharLength.get(i - 1)) {
                    if (isPredecessorOf(prevWord, curWord)) {
                        prevLongest = Math.max(prevLongest, longestPre.get(prevWord));
                    }
                }
                longestPre.put(curWord, prevLongest + 1);
                res = Math.max(res, prevLongest + 1);
            }
        }
        return res;
    }

    private boolean isPredecessorOf(String prevWord, String curWord) {
        int skipped = 0;
        int i = 0;
        while (i < prevWord.length() && i + skipped < curWord.length()) {
            if (prevWord.charAt(i) != curWord.charAt(i + skipped)) {
                if (skipped == 0) {
                    skipped = 1;
                    continue;
                } else {
                    return false;
                }
            }
            i++;
        }
        return true;
    }
}

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Java Solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Result {
    boolean val;
    Result() {
        this.val = true;
    }
    public void setValue(boolean val) {
        this.val = val;
    }
    public boolean getValue() {
        return val;
    }
}
class Solution {
    public boolean isBalanced(TreeNode root) {
        Result isBalanced = new Result();
        getHeight(root, isBalanced);
        return isBalanced.getValue();
    }
    
    private int getHeight(TreeNode node, Result isBalanced) {
        if (node == null) return 0;
        int leftHeight = getHeight(node.left, isBalanced);
        int rightHeight = getHeight(node.right, isBalanced);
        if (Math.abs(leftHeight - rightHeight) > 1) {
            isBalanced.setValue(false);
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

Essentially, trying to “hack” the pass-by-reference C++ has into the Java solution. But it solves the problem in one pass.

Deploy Jupyter behind Apache reverse proxy

Jupyter was deployed on one LXD container and Apache was deployed on another. At first Jupyter kept complaining “Connecting to kernel… Failed.”

Ubuntu: 16.04LTS

Apache: Server version: Apache/2.4.18 (Ubuntu)

Solution:

Add those two lines BEFORE “/” one:

ProxyPass /api/kernels/ ws://xxx.lxd:8888/api/kernels/
ProxyPassReverse /api/kernels/ http://xxx.lxd:8888/api/kernels/

AND: make sure proxy_wstunnel is enabled for Apache:

a2enmod proxy proxy_wstunnel

Convertion of grey code and binary

Source: http://www.cnblogs.com/grandyang/p/4315607.html

以下转换代码摘自维基百科 Wikipedia：

/*
The purpose of this function is to convert an unsigned
binary number to reflected binary Gray code.

The operator >> is shift right. The operator ^ is exclusive or.
*/
unsigned int binaryToGray(unsigned int num)
{
return (num >> 1) ^ num;
}

/*
The purpose of this function is to convert a reflected binary
Gray code number to a binary number.
*/
unsigned int grayToBinary(unsigned int num)
{
unsigned int mask;
for (mask = num >> 1; mask != 0; mask = mask >> 1)
{
num = num ^ mask;
}
return num;
}