525. Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

---

给定一个二进制数组（即数组中只包含0和1），要求找到最长的子数组，使得该子数组中0和1的个数相等。 感觉应该用DP和累加和，但是没想出具体的解法，参考网上的题解。 把数组中的0换成-1，然后计算累加和，把[0,i]的累加和及对应的下标存入到一个hash中，即hash[sum[0,i]]=i，在后续的累加计算中，如果遇到累加和出现在hash中，则说明这两个区间之间的0和1个数相等。比如下面的例子：

• 序列：    1,-1,-1,-1,1,-1,-1,-1,1
• 累加和：1,0,-1,-2,-1,-2,-3,-4,-3

累加和第一次遇到-2时，记录hash[-2]=3，表示sum[0,3]=-2，当再次遇到累加和为-2时，是sum[0,5]=-2，则说明[4,5]之间的1和-1个数是相等的。因为序列中没有0元素，两次的累加和又一样，说明中间经过的数累加和是0，导致累加和没变化，累加和是0，又说明1和-1的个数相等，即1和0的个数相等。
代码如下，初始时，没有元素，累加和也是0，但是要记录下标是-1，实际跑一下第一个样例就知道了。

class Solution {
public:
    int findMaxLength(vector<int>& nums)
    {
        unordered_map<int, int> hash;
        hash[0] = -1; // init
        int sum = 0, n = nums.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            sum += nums[i] == 1 ? 1 : -1;
            if (hash.find(sum) != hash.end()) {
                ans = max(ans, i – hash[sum]);
            }
            else {
                hash[sum] = i;
            }
        }
        return ans;
    }
};

本代码提交AC，用时138MS。
果然遇到子数组的问题，要善于利用累加和/积的方法。

274. H-Index 274. H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

Example:

Input: citations = [3,0,6,1,5]
Output: 3 
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had 
             received 3, 0, 6, 1, 5 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index. 274. H-Index

---

给定一个研究人员的n篇文章及其引用数，求该研究人员的H-index。
一个人的H-index为h说明他有h篇引用数至少为h的论文，比如例子中[3,0,6,1,5]的H-index为3，指他有3篇引用数至少为3的文章，即引用数为3,6,5的3篇文章。
求解方法也不难，先对所有引用数按从大到小排序，然后从大到小累加文章数目，直到引用数小于文章数时停止。代码如下：

class Solution {
public:
    int hIndex(vector<int>& citations)
    {
        sort(citations.begin(), citations.end(), std::greater<int>());
        int h = 1;
        while (h <= citations.size()) {
            if (citations[h – 1] < h)
                return h – 1;
            ++h;
        }
        return h – 1;
    }
};

本代码提交AC，用时3MS。 还有一种方法是，不排序，使用Hash。先求出最大引用数，然后把相同引用数的文章Hash到同一个位置。最后从引用数大的开始遍历，累加文章数，直到文章数大于引用数时停止。 此时的返回值需要注意，是较大的h-index，即max(h – hash, c)。比如[2,3,3,3]，则hash[3]=3,hash[2]=1，当遍历到2时，发现不满足，此时的最大h-index是h-hash=4-1=3。 但是如果[2,3,2]，则hash[3]=1,hash[2]=2，当遍历到2时，也发现不满足，但此时并不需要完全回退到3，还可以拿一篇2引用的文章，即最大的h-index是c=2。
代码如下：

class Solution {
public:
    int hIndex(vector<int>& citations)
    {
        int maxC = -1, n = citations.size();
        if (n == 0)
            return 0;
        for (int i = 0; i < n; ++i)
            maxC = max(maxC, citations[i]);
        vector<int> hash(maxC + 1, 0);
        for (int i = 0; i < n; ++i)
            ++hash[citations[i]];
        int c = maxC, h = hash[maxC];
        while (c >= h) {
            –c;
            h += hash[c];
        }
        return max(h – hash[c], c);
    }
};

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

LeetCode Most Frequent Subtree Sum Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order. Examples 1 Input:

  5
 /  \
2   -3

return [2, -3, 4], since all the values happen only once, return all of them in any order. Examples 2 Input:

  5
 /  \
2   -5

return [2], since 2 happens twice, however -5 only occur once. Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

---

给定一棵二叉树，问频率最大的子树之和是哪个数。子树之和是指根节点及其子节点的和。 简单题，使用后序遍历把所有子树之和统计一遍，用Hash记录和与频率的关系，然后找出最大频率的和。 代码如下： [cpp] class Solution { private: int postOrder(TreeNode* root, unordered_map<int, int>& hash) { int sum = 0; if (root->left)sum += postOrder(root->left, hash); if (root->right)sum += postOrder(root->right, hash); sum += root->val; ++hash[sum]; return sum; } public: vector<int> findFrequentTreeSum(TreeNode* root) { if (!root)return vector<int>(); unordered_map<int, int> hash; postOrder(root, hash); int maxCnt = 0; for (auto it = hash.begin(); it != hash.end(); ++it)maxCnt = max(maxCnt, (*it).second); vector<int> ans; for (auto it = hash.begin(); it != hash.end(); ++it) { if ((*it).second == maxCnt)ans.push_back((*it).first); } return ans; } }; [/cpp] 本代码提交AC，用时19MS。]]>

LeetCode Encode and Decode TinyURL

Note: This is a companion problem to the System Design problem: Design TinyURL.

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk. Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

---

实现短网址的功能，即把一个长的网址加密成短网址，并且能够把短网址还原为原来的长网址。 显然要用Hash，有多种方法，参考：https://leetcode.com/articles/encode-and-decode-tinyurl/ 直接用一个计数器当key，相当于自己维护了一个长的url池，给每个url编了一个号。加密的时候把号码给他，解密的时候根据编号找到原始的url。代码如下： [cpp] class Solution { private: unsigned long long m_ullCnt; unordered_map<unsigned long long, string> m_umHash; public: Solution() :m_ullCnt(0) {}; // Encodes a URL to a shortened URL. string encode(string longUrl) { m_umHash[m_ullCnt] = longUrl; return "http://tinyurl.com/" + to_string(m_ullCnt++); } // Decodes a shortened URL to its original URL. string decode(string shortUrl) { int id = atoi(shortUrl.substr(19).c_str()); return m_umHash[id]; } }; [/cpp] 本代码提交AC，用时9MS。 既然可以用计数器，也可以生成不重复的随机数作为key，不断random，和上面的解法类似。 还有一种生成key的方法，就是用STL自带的hash函数，把string hash成一个size_t作为key。注意要从短url中还原回hash值时，不能用atoi和atol，因为size_t可能是unsigned int，也可能和平台有关，所以必须用sscanf “%zu”的形式转换成size_t。 代码如下： [cpp] class Solution { private: unordered_map<size_t, string> m_umHash; public: // Encodes a URL to a shortened URL. string encode(string longUrl) { hash<string> h; m_umHash[h(longUrl)] = longUrl; return "http://tinyurl.com/" + to_string(h(longUrl)); } // Decodes a shortened URL to its original URL. string decode(string shortUrl) { size_t id = 0; sscanf(shortUrl.substr(19).c_str(), "%zu", &id); return m_umHash[id]; } }; [/cpp] 本代码提交AC，用时6MS。]]>

205. Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Note:
You may assume both s and t have the same length.

---

判断两个字符串是否同构。同构的意思是字符串s和t中的字母能找到一种一一映射的关系，使得通过这个映射之后s能变成t，t也能变成s。 简单题，维护两个hash表，一个保存s到t的映射，另一个保存t到s的映射。在遍历字符串的过程中，同时判断两个映射是否满足一一映射。 注意不能只用一个hash，因为可能出现s=ab,t=aa的情况，看s->t，a映射到a，b映射到b，没有问题。但是看t->s时，有问题，出现了a既映射到a又映射到b的情况。所以需要同时保存s到t和t到s的映射。 代码如下：

class Solution {
public:
    bool isIsomorphic(string s, string t)
    {
        unordered_map<char, char> hash1, hash2;
        for (int i = 0; i < s.size(); ++i) {
            if (hash1.find(s[i]) == hash1.end())
                hash1[s[i]] = t[i];
            else {
                if (hash1[s[i]] != t[i])
                    return false;
            }
            if (hash2.find(t[i]) == hash2.end())
                hash2[t[i]] = s[i];
            else {
                if (hash2[t[i]] != s[i])
                    return false;
            }
        }
        return true;
    }
};

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

LeetCode Next Greater Element I You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1‘s elements in the corresponding places of nums2. The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number. Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

Note:

1. All elements in nums1 and nums2 are unique.
2. The length of both nums1 and nums2 would not exceed 1000.

---

给定两个数组nums1和nums2，其中nums1是nums2的子集，两个数组中的都没有重复元素。现在要问nums1中的每个数在nums2中其右边第一个更大的数是什么。 比如Example 2中，nums1[0]=2，在nums2中2的右边有3和4，则第一个更大的数是3。 常规思路是对于nums1中的每个数，在nums2中找到位置，并在其右边搜索第一个比它的数。更好一点的解法是，对nums2中的每个数，建立数和下标的hash关系，这样对于nums1中的每个数，就能O(1)找到其在nums2中的位置，直接开始在其右边找更大的数，但是渐进复杂度都是O(n*m)。 代码如下： [cpp] class Solution { public: vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) { unordered_map<int, int> hash; for (int i = 0; i < nums.size(); ++i)hash[nums[i]] = i; vector<int> ans; for (int i = 0; i < findNums.size(); ++i) { int idx = hash[findNums[i]], ret = -1; for (int j = idx + 1; j < nums.size(); ++j) { if (nums[j] > findNums[i]) { ret = nums[j]; break; } } ans.push_back(ret); } return ans; } }; [/cpp] 本代码提交AC，用时9MS。 还有一种比较巧妙的解法，借助栈，用O(m)时间就可以得到nums2中所有数的其右边更大数。具体举例，比如Example 1中nums2 = [1,3,4,2]，先不断压栈，遇到1，压栈；遇到3，发现栈顶原始1比3小，说明1的右边更大数是3，建立hash关系，把1弹栈，栈内没东西了，3进栈。 更极端一点，假设nums2 = [9, 8, 7, 3, 2, 1, 6]，则从9~1都一直压栈，因为后面的数一直比栈顶元素小，当不了栈顶原始的右边更大数。当遇到6时，发现栈顶是1，则6可以当1的右边更大数，把1弹栈；又发现6比当前栈顶2大，又可以当2的右边更大数；如此不断弹栈，直到栈顶为7时，6压栈。此时9~7和6都没有右边更大数。对于没有右边更大树的数，其右边更大数赋值为-1。 代码如下： [cpp] class Solution { public: vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) { unordered_map<int, int> hash; stack<int> stk; for (int i = 0; i < nums.size(); ++i) { while (!stk.empty() && stk.top() < nums[i]) { hash[stk.top()] = nums[i]; stk.pop(); } stk.push(nums[i]); } vector<int> ans; for (int i = 0; i < findNums.size(); ++i) { if (hash.find(findNums[i]) == hash.end())ans.push_back(-1); else ans.push_back(hash[findNums[i]]); } return ans; } }; [/cpp] 本代码提交AC，用时12MS。]]>