LeetCode Minimum Index Sum of Two Lists Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings. You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer. Example 1:

Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".

Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

1. The length of both lists will be in the range of [1, 1000].
2. The length of strings in both lists will be in the range of [1, 30].
3. The index is starting from 0 to the list length minus 1.
4. No duplicates in both lists.

LeetCode Find Duplicate File in System Given a list of directory info including directory path, and all the files with contents in this directory, you need to find out all the groups of duplicate files in the file system in terms of their paths. A group of duplicate files consists of at least two files that have exactly the same content. A single directory info string in the input list has the following format: "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)" It means there are n files (f1.txt, f2.txt … fn.txt with content f1_content, f2_content … fn_content, respectively) in directory root/d1/d2/.../dm. Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory. The output is a list of group of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format: "directory_path/file_name.txt" Example 1:

Input:
["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]
Output:
[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

1. No order is required for the final output.
2. You may assume the directory name, file name and file content only has letters and digits, and the length of file content is in the range of [1,50].
3. The number of files given is in the range of [1,20000].
4. You may assume no files or directories share the same name in a same directory.
5. You may assume each given directory info represents a unique directory. Directory path and file infos are separated by a single blank space.

1. Imagine you are given a real file system, how will you search files? DFS or BFS ?
2. If the file content is very large (GB level), how will you modify your solution?
3. If you can only read the file by 1kb each time, how will you modify your solution?
4. What is the time complexity of your modified solution? What is the most time consuming part and memory consuming part of it? How to optimize?
5. How to make sure the duplicated files you find are not false positive?

LeetCode Permutation in String Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string. Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Input:s1= "ab" s2 = "eidboaoo"
Output: False

1. The input strings only contain lower case letters.
2. The length of both given strings is in range [1, 10,000].

560. Subarray Sum Equals K

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:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

给定一个数组，问有多少个子数组的和等于k。
暴力方法$O(n^3)$肯定不行，这种连续子数组的问题，肯定会用到数组的前缀和，所以先把前缀和求出来sum[i]，这样任意区间[i,j]之间的和都可以用sum[i]-sum[i-1]求到。不过还是需要$O(n^2)$的时间，代码如下：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k)
    {
        int n = nums.size();
        if (n == 0)
            return 0;
        vector<int> sum(n + 1, 0);
        for (int i = 1; i <= n; ++i)
            sum[i] = sum[i – 1] + nums[i – 1];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (sum[j] – sum[i] == k)
                    ++ans;
            }
        }
        return ans;
    }
};

本代码提交AC，用时533MS。

看了下tag要用map来做。我们把所有前缀和及其频率存到一个map中，假设当前前缀和为sum，则如果sum-k也在map中，说明由产生sum-k前缀和的位置到当前位置的和是k。
比如样例[1,1,1]，遇到第一个1时，前缀和为1，之前没有前缀和为1的情况，所以map[1]=1。当加到最后一个数时，前缀和sum=3，sum-k=1也在map中，正好说明从1开始到结束的位置的和为2，如果map[1]=2，说明有两个前缀和等于1的位置，也就有两个连续和为2的子数组。
代码如下，注意只能在遍历的同时求ans，不能等map都构建好了再求ans，这样保证前缀和为sum-k的位置肯定在i前面，也就是我们统一前缀和为k的结束位置为i，做到不重不漏。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k)
    {
        int n = nums.size();
        if (n == 0)
            return 0;
        int ans = 0, sum = 0;
        unordered_map<int, int> cnt;
        for (int i = 0; i < n; ++i) {
            ++cnt[sum];
            sum += nums[i];
            ans += cnt[sum – k];
        }
        return ans;
    }
};

本代码提交AC，用时36MS。

二刷。思路同上，但不把sum=0插入到map中，会不会更好理解一些：

class Solution {
public:
	int subarraySum(vector<int>& nums, int k) {
		int i = 0, j = 0, n = nums.size();
		map<int, int> sum_cnt;
		int sum = 0, ans = 0;
		for (int i = 0; i < n; ++i) {
			sum += nums[i];
			if (sum == k)++ans;
			if (sum_cnt.find(sum - k) != sum_cnt.end()) {
				ans += sum_cnt[sum - k];
			}
			++sum_cnt[sum];
		}
		return ans;
	}
};

本代码提交AC，用时56MS。

LeetCode Can I Win In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins. What if we change the game so that players cannot re-use integers? For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100. Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally. You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300. Example

Input:
maxChoosableInteger = 10
desiredTotal = 11
Output:
false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.