Category: 不学无术

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

1. The root is the maximum number in the array.
2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.
 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* subMaxBinTree(vector<int>::iterator begin, vector<int>::iterator end)
    {
        if (begin == end)
            return nullptr;
        auto maxElemIt = std::max_element(begin, end);
        TreeNode* root = new TreeNode(*maxElemIt);
        root->left = subMaxBinTree(begin, maxElemIt);
        root->right = subMaxBinTree(maxElemIt+1, end);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.empty())
            return nullptr;
        return subMaxBinTree(nums.begin(), nums.end());
    }
};

https://leetcode.com/problems/subarray-sum-equals-k/description/
O(N^2)的方法想必所有人都会，这里有个用到prefix sum的O(N)方法。
试想一下，如果当前检查到end位置且目前所有项的和为sum，如果有那么一个(start, end)子序列的和为k，那么肯定有一个(0, start-1)的序列它的和是sum – k.

[a, b, c] \___k__/
[a, b, c, d, e, f]
/sum - k\

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> cum_sums;   // <cum_sum, count>
        cum_sums[0] = 1;
        int sum = 0;
        int count = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            if (cum_sums.count(sum - k) > 0)
                count += cum_sums[sum - k];
            cum_sums[sum]++;
        }
        return count;
    }
};

类似的东西还有：
674. Longest Continuous Increasing Subsequence
https://leetcode.com/problems/longest-continuous-increasing-subsequence/description/
300. Longest Increasing Subsequence
https://leetcode.com/problems/longest-increasing-subsequence/description/
longest path increasing by 1
https://www.geeksforgeeks.org/find-the-longest-path-in-a-matrix-with-given-constraints/
 
下面的代码是这个题的：

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/ 
主要思路就是瞎JB搜索，不过某一个位置的结果可以记录下来给后续的重复搜索使用。

class Solution {
public:
	int subLIP(vector<vector<int>>& matrix, vector<vector<int>>& sub_results, int row, int col)
	{
		if (row < 0 || row >= matrix.size())
			return 0;
		if (col < 0 || col >= matrix[0].size())
			return 0;
		if (sub_results[row][col] != -1)
			return sub_results[row][col];
		// go left
		int maxResult = -1;
		if (col > 0 && matrix[row][col - 1] > matrix[row][col])
			maxResult = max(maxResult, 1 + subLIP(matrix, sub_results, row, col - 1));
		// go right
		if (col < matrix[0].size() - 1 && matrix[row][col + 1] > matrix[row][col])
			maxResult = max(maxResult, 1 + subLIP(matrix, sub_results, row, col + 1));
		// go up
		if (row > 0 && matrix[row - 1][col] > matrix[row][col])
			maxResult = max(maxResult, 1 + subLIP(matrix, sub_results, row - 1, col));
		// go down
		if (row < matrix.size() - 1 && matrix[row + 1][col] > matrix[row][col])
			maxResult = max(maxResult, 1 + subLIP(matrix, sub_results, row + 1, col));
		sub_results[row][col] = max(1, maxResult);
		return sub_results[row][col];
	}
	int longestIncreasingPath(vector<vector<int>>& matrix) {
		vector<vector<int>> sub_results;
		sub_results.resize(matrix.size());
		for (int i = 0; i < matrix.size(); ++i)
		{
			sub_results[i].resize(matrix[0].size(), -1);   // -1 means unknown
		}
		int result = 0;
		for (int r = 0; r < matrix.size(); ++r)
		{
			for (int c = 0; c < matrix[r].size(); ++c)
			{
				result = max(result, subLIP(matrix, sub_results, r, c));
			}
		}
		return result;
	}
};

https://leetcode.com/problems/number-of-islands/description/
DFS of a map, O(N^2)

class Solution {
public:
    bool visit(vector<vector<char>>& grid, int row, int col)
    {
        // if has any island, return true
        // DFS on grid
        const int rows = grid.size();
        if (rows == 0 || row >= rows || row < 0)
            return false;
        const int cols = grid[0].size();
        if (cols == 0 || col >= cols || col < 0)
            return false;
        if (grid[row][col] == 'V')
            return false;
        else if (grid[row][col] == '0')
            return false;
        grid[row][col] = 'V';
        visit(grid, row, col-1);
        visit(grid, row-1, col);
        visit(grid, row+1, col);
        visit(grid, row, col+1);
        return true;
    }
    int numIslands(vector<vector<char>>& grid) {
        // mark visited as 'V'
        int result = 0;
        for (int row = 0; row < grid.size(); ++row)
        {
            for (int col = 0; col < grid[0].size(); ++col)
            {
                if (grid[row][col] == 'V' || grid[row][col] == '0')
                {
                    continue;
                }
                if (visit(grid, row, col))
                    result++;
            }
        }
        return result;
    }
};

76. Minimum Window Substring
思路:
构造一个哈希表结构统计我们的需求，也就是字符串t中每个字符的数量，方便起见如果有需求则哈希表的对应值-1。另外存储一下当前解的起始位置START以及最优解的位置。
扫描字符串s，在位置s[i]时如果能够满足需求（即哈希表中没有负值），则从START开始清除无用的字符直至无法满足需求位置。比如需求是A:1, B:2，START开始的字符是DEFBAB，则清除DEF。清除完成后更新START值并跟当前已知的最优解比较，更新最优解。
啰嗦一句，似乎相当一部分substring类型的题目都能用hash table + two pointers的方式解决。

class Solution {
public:
    static string minWindow(string s, string t) {
        int count_map[128] = {0};
        set<char> req_set;
        int start_index = -1, min_start_index = 0;
        int min_end_index = INT_MAX;
        for (const char& c : t)
        {
            count_map[c] --;
            req_set.insert(c);
        }
        for (int i = 0; i < s.size(); ++i)
        {
            const char c = s[i];
            count_map[c] ++;
            bool require_sufficed = true;
            for (const char& c : req_set)
            {
                if (count_map[c] < 0)
                {
                    require_sufficed = false;
                    break;
                }
            }
            if (!require_sufficed) continue;
            // clear left
            for (int j = start_index + 1; j <= i; ++j)
            {
                if (--count_map[s[j]] < 0)
                {
                    start_index = j;
                    break;
                }
                start_index = j;
            }
            if (i - start_index < min_end_index - min_start_index)
            {
                min_start_index = start_index;
                min_end_index = i;
            }
        }
        if (min_end_index == INT_MAX)
            return "";
        else
            return s.substr(min_start_index, min_end_index - min_start_index + 1);
    }
};