Cinte's Leetcode Record
0%

Posted on Edited on In Disqus:
Symbols count in article: 690 Reading time ≈ 1 mins.

213. House Robber II

我好菜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int rob(vector<int>& nums) {
        int sz = nums.size();
        if(sz == 1)
            return nums[0];
        if(sz < 3)
            return max(nums[0], nums[1]);
        int dpNotRobFirst[2];
        int dpRobFirst[2];
        dpNotRobFirst[0] = nums[1];
        dpNotRobFirst[1] = max(nums[1], nums[2]);
        dpRobFirst[0] = nums[0];
        dpRobFirst[1] = max(nums[0], nums[1]);
        for(int i = 2; i < sz - 1; ++i)
        {
            dpNotRobFirst[0] = max(dpNotRobFirst[1], dpNotRobFirst[0] + nums[i + 1]);
            dpRobFirst[0] = max(dpRobFirst[1], dpRobFirst[0] + nums[i]);
            swap(dpNotRobFirst[0], dpNotRobFirst[1]);
            swap(dpRobFirst[0], dpRobFirst[1]);
        }
        return max(dpNotRobFirst[1], dpRobFirst[1]);
    }
};

分为rob第一个和不rob第一个，问题变为rob[1, n - 2]和rob[2, n - 1]

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

73. Set Matrix Zeroes

我好菜

space compelexity O(m + n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        unordered_set<int> row;
        unordered_set<int> col;
        for(int i = 0; i < matrix.size(); ++i)
        {
            for(int j = 0; j < matrix[0].size(); ++j)
            {
                if(matrix[i][j] == 0)
                {
                    row.insert(i);
                    col.insert(j);
                }
            }
        }
        for(int i = 0; i < matrix.size(); ++i)
        {
            for(int j = 0; j < matrix[0].size(); ++j)
            {
                if(row.find(i) != row.end() || col.find(j) != col.end())
                    matrix[i][j] = 0;
            }
        }
    }
};
space compelexity O1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool firstColZero = false;
        for(int i = 0; i < m; ++i)
        {
            if(matrix[i][0] == 0)
                firstColZero = true;
            for(int j = 1; j < n; ++j)
            {
                if(matrix[i][j] == 0)
                {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i = 1; i < m; ++i)
            for(int j = 1; j < n; ++j)
                if(matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
        if(matrix[0][0] == 0)
            for(int i = 1; i < n; ++i)
                matrix[0][i] = 0;
        if(firstColZero)
            for(int i = 0; i < m; ++i)
                matrix[i][0] = 0;
    }
};

因为第一行和第一列为0都由一个matrix[0][0]指定，将导致二者无法区分，所以用matrix[0][0]指定第一行，isCol这个额外的变量指定第一列。

注意要先填充第一行第一列以外的内容再去填充第一行第一列，不然后面数据会被填充的0所干扰

Posted on Edited on In Disqus:
Symbols count in article: 1k Reading time ≈ 1 mins.

59. Spiral Matrix II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ret(n, vector<int>(n));
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int num = 1;
        while(num <= n * n)
        {
            for(int i = left; i <= right; ++i)
                ret[top][i] = num++;
            ++top;
            for(int i = top; i <= bottom; ++i)
                ret[i][right] = num++;
            --right;
            for(int i = right; i >= left; --i)
                ret[bottom][i] = num++;
            --bottom;
            for(int i = bottom; i >= top; --i)
                ret[i][left] = num++;
            ++left;
        }
        return ret;
    }
};
2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ret(n, vector<int>(n, 0));
        int dir[][2]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int d = 0;
        int m = 0, k = 0;
        for(int i = 1; i <= n * n; ++i)
        {
            ret[m][k] = i;
            int nextm = m + dir[d][0];
            int nextk = k + dir[d][1];
            if(nextm < 0 || nextm >= n || nextk < 0 || nextk >= n || ret[nextm][nextk] > 0)
                d = (d + 1) % 4;
            m += dir[d][0];
            k += dir[d][1];
        }
        return ret;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

57. Insert Interval

My vegetable exploded

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int l = newInterval[0], r = newInterval[1];
        vector<vector<int>> ret;
        int i = 0;
        while(i < intervals.size() && intervals[i][1] < newInterval[0]) // 添加所有没有交叠的
            ret.push_back(intervals[i++]);
        while(i < intervals.size() && intervals[i][0] <= r) // 合并所有交叠的
        {
            l = min(l, intervals[i][0]);
            r = max(r, intervals[i][1]);
            ++i;
        }
        ret.push_back({l, r});
        while(i < intervals.size()) // 添加剩下的
            ret.push_back(intervals[i++]);
        return ret;
    }
};

三步走，先处理交叠前的，在处理正在交叠的，再添加剩下的

review

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ret;
        int i = 0, sz = intervals.size();
        for(; i < sz && intervals[i][1] < newInterval[0]; ++i)
            ret.push_back(intervals[i]);
        int l = newInterval[0], r = newInterval[1];
        for(; i < sz && r >= intervals[i][0]; ++i)
        {
            l = min(intervals[i][0], l);
            r = max(intervals[i][1], r);
        }
        ret.push_back({l, r});
        for(; i < sz; ++i)
            ret.push_back(intervals[i]);
        return ret;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 490 Reading time ≈ 1 mins.

11. Container With Most Water

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxVal = 0;
        int i = 0, j = height.size() - 1;
        while(i < j)
        {
            maxVal = max(maxVal, (j - i) * min(height[i], height[j]));
            if(height[i] < height[j])
                ++i;
            else
                --j;
        }
        return maxVal;
    }
};

当height[i] < height[j]时，如果不舍弃他而移动右边j，那么结果肯定时小于现在的，所以舍弃i

假设a2,a6为最大，需要证明当left=a2时，右边会移到a6。 即当left=a2,right=a7的下一位时left=a2,left=a6。而这一步必然时height[a2]>height[a7]，若不然，则最小边界为a2，宽度只会减少，则总值减少，所以必定移动a.

Posted on Edited on In Disqus:
Symbols count in article: 3.1k Reading time ≈ 3 mins.

10. Regular Expression Matching

题目: 

1
2
3
4
5
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*' where: 

'.' Matches any single character.​​​​
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
这里的'*'表达有些含糊，改为Matches zero or more of the preceding character.较好

递归

思路：

.可以匹配任何字符，因此当遇到了.那就是直接匹配成功，其余状况就是比较字符是否相等即可。*可以匹配之前的元素，0次或多次，当匹配0次的时候，那么就将原text和pattern除去这一匹配0次的模式后的部分再次进行匹配，当匹配一次或多次的时候，就在text中删去匹配成功的部分继续把剩下的和pattern匹配，由于每一都会有这2种抉择，所以采用递归，二者状况其一匹配成功即可。

当pattern为空时，当且仅到s为空才会匹配成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isMatch(string s, string p) {
        return helper(s, p, 0, 0);
    }
private:
    bool helper(string& s, string& p, int i, int j)
    {
        // 这里if和return的顺序不能对换，因为当且仅当p走完，才表示匹配结束，此时如果也是空串，那么就是匹配成功。
        // 如果对换，当s走完时候，如果p还没走完，但是p后面又可以表示匹配0个，就会导致错误的结果
        if(j >= p.size())
            return i >= s.size();
        bool firstMatch = i < s.size() && (s[i] == p[j] || p[j] == '.');
        if(j <= p.size() - 2 && p[j + 1] == '*')
            return helper(s, p, i, j + 2) || (firstMatch && helper(s, p, i + 1, j));
        else
            return firstMatch && helper(s, p, i + 1, j + 1);
    }
};
top-down dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
enum status {
    UNKNOWN,
    TRUE,
    FALSE
};
class Solution {
public:
    bool isMatch(string s, string p) {
        dp = vector<vector<status>>(s.size() + 1, vector<status>(p.size() + 1, UNKNOWN));
        return helper(0, 0, s, p);
    }
private:
    vector<vector<status>> dp;
    bool helper(int i, int j, const string& s, const  string& p)
    {
        if(dp[i][j] != UNKNOWN)
            return dp[i][j] == TRUE;
        else
        {
            if(j >= p.size())
                return i >= s.size();
            bool firstMatch = i < s.size() && (p[j] == s[i] || p[j] == '.');
            bool ret;
            if(j <= p.size() - 2 && p[j + 1] == '*')
                ret = helper(i, j + 2, s, p) || (firstMatch && helper(i + 1, j, s, p));
            else
                ret = firstMatch && helper(i + 1, j + 1, s, p);
            dp[i][j] = ret ? TRUE : FALSE;
            return ret;
        }
    }
};

由于递归检索过程中会出现许多的交叠，因此自然而然想到避免这种重复，所以通过dp保存起来以供后续读取，其中vector的size全都+1是防止溢出。

而且将substr的工作转为有i,j表示，避免了多次创建string

但是这种仅仅可以避免交叠，top-down，顾名思义，从大往下走，分为一个个小问题从而解决，转而使用bottom-up，一个个小问题进行组合合成大问题

bottom-up dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false)); // +1 表示了空
        dp[s.size()][p.size()] = true;
        for(int i = s.size(); i >= 0; --i) // s从空串开始匹配，因为对于*a,是可以匹配到空串的
        {
            for(int j = p.size() - 1; j >=0; --j) // 这里不用，因为当p为空时候，当且仅当s为空才为真，其他为假，而这种情况已经包含在了base中
            {
                bool firstMatch = i < s.size() && (p[j] == '.' || p[j] == s[i]);
                if(j + 1 < p.size() && p[j + 1] == '*')
                    dp[i][j] = dp[i][j + 2] || (firstMatch && dp[i + 1][j]);
                else
                    dp[i][j] = firstMatch && dp[i + 1][j + 1];
            }
        }
        return dp[0][0];
    }
};

base为当两者全为空的时候，匹配结果为true。

从后面往前走，当i == 0 && j == 0时，表示匹配了整个字符串和pattern

如果从前往后，不便于计算下标

然后分解成小问题，对于当前dp[i][j]来说，从递归的思想引过来

  1. 如果p[j] == '.'或p[j] == s[i]，那么dp[i][j] == dp[i + 1][j + 1]，说明当前匹配可以正常走，结果=除了这个位之后的匹配结果
  2. 如果p[j + 1] == '*'，那么`dp[i][j] == dp[i][j + 2] || s[i] == p[j] || p[j] == '.' &&dp[i + 1][j]，这是可以匹配s[i]的0个或多个，当0个时候，这匹配没有生效，所以取后两位继续匹配的结果，当匹配多个，那么p[j]被使用了，结果就是当p[j]匹配成功后，结合后面串的匹配结果得出当前的结果。
  3. 当2个长度都只有1个时候，直接比对当前的字母再结合之前的匹配结果。

Posted on Edited on In Disqus:
Symbols count in article: 5.5k Reading time ≈ 5 mins.

32. Longest Valid Parentheses

stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        int maxLength = 0;
        st.push(-1);
        for(int i = 0; i < s.size(); ++i)
        {
            if(s[i] == '(')
                st.push(i);
            else
            {
                st.pop();
                if(st.empty())
                    st.push(i);
                else
                    maxLength = max(maxLength, i - st.top());
            }
        }
        return maxLength;
    }
};

stack中存储坐标，括号两端(左端为括号开始的前一个, 右端为当前括号)构成最长的值。先push(-1)是便于计算，每遇到一个)就pop出一个，空的时候就push，为了方便后面计算坐标。

review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestValidParentheses(string s) {
        s.append("(");
        stack<int> st;
        st.push(-1);
        int ret = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            ret = max(i - st.top() -1, ret);
            if(st.size() != 1 && s[i] == ')' && s[st.top()] == '(')
            {
                st.pop();
            }else
                st.push(i);
        }
        return ret;
    }
};
dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty())
            return 0;
        vector<int> dp(s.size());
        dp[0] = 0;
        int maxLen = 0;
        for(int i = 1; i < s.size(); ++i)
        {
            if(s[i] == ')' && s[i - 1] == '(')
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            else if(s[i] == ')' && s[i - 1] == ')')
            {
                if(i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(')
                    dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
            }
            maxLen = max(maxLen, dp[i]);
        }
        return maxLen;
    }
};

对于s[i] == ')'这时一个括号要收尾

  1. 如果s[i - 1] == '('，则dp[i] = dp[i - 2] + 2
  2. 如果s[i - 1] == ')'，此时如果s[i-1]有配对的'('或者多个合法的配对，那么通过先前这个的长度往前减坐标寻找是否有与s[i]配对的'('若有，则这个与其配对的将之中包裹的合法括号和先前的合法括号连接相加dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2
review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty())
            return 0;
        vector<int> dp(s.size(), 0);
        int ret = 0;
        for(int i = 1; i < s.size(); ++i)
        {
            if(s[i] == ')')
            {
                if(s[i - 1] == '(')
                    dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
                else if(s[i - 1] == ')' && (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '('))
                    dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
            }
            ret = max(ret, dp[i]);       
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty())
            return 0;
        vector<int> dp(s.size() + 2);
        int ret = 0;
        dp[0] = dp[1] = dp[2] = 0;
        for(int i = 1; i < s.size(); ++i)
        {
            if(s[i] == ')')
            {
                if(i - dp[i + 1] >= 1 && s[i - dp[i + 1] - 1] == '(')
                {
                    dp[i + 2] = dp[i + 1] + 2 + dp[i - dp[i + 1]];
                    ret = max(dp[i + 2], ret);
                }
            }else
                dp[i + 2] = 0;
        }
        return ret;
    }
};

r

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty())
            return 0;
        int n = s.size();
        vector<int> dp(n);
        int ret{0};
        for(int i = 1; i < n; ++i)
        {
            if(s[i] == ')' && i - dp[i - 1] - 1 >= 0)
                dp[i] = s[i - dp[i - 1] - 1] == '(' ? (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2 : 0;
            ret = max(dp[i], ret);
        }
        return ret;
    }
};
two point
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0, right = 0;
        int maxLength = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            if(s[i] == '(')
                ++left;
            else if(s[i] == ')')
                ++right;
            if(left == right)
                maxLength = max(maxLength, 2 * right);
            else if(right > left)
                left = right = 0;
        }
        left = right = 0;
        for(int i = s.size() - 1; i >=0; --i)
        {
            if(s[i] == '(')
                ++left;
            else if(s[i] == ')')
                ++right;
            if(left == right)
                maxLength = max(maxLength, 2 * right);
            else if(right < left)
                left = right = 0;
        }
        return maxLength;
    }
};

遇见(就增加left，遇见)就增加right，当二者相等时候，表明所有(和)配对了，计算长度，更新max

从左到右时，当right>left，表示前面遇到的(比)少，因此由于括号的顺序，不可能再长下去了，由此重置left和right继续开始计数

从右往左时，当left>right, 表示前面遇到的)比(少，同理

要从左往右和从右往左都走一遍是因为... 证明：[@wander](https://leetcode.com/wanders/) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Proof of validity for approach 4:

Let i and j denote the starting and ending indices of the longest valid subsequence.
Note that in the forward pass after (fully) processing each character, it's always the case that left >= right. (*)
This is in particular true after processing i-1 (immediately before processing i).

Case 1: If immediately before i left = right, then the forward pass will detect the length of the longest valid subsequence.
(The number of '(' and ')' is the same for any valid subseq. Thus after processing j, left = right.)

Case 2: If immediately before i left > right, the forward pass will not detect the longest valid subsequence, but we claim the backward pass will.
Similar to observation (*) above, note that right >= left after fully processing each element in the backward pass. We detect the longest valid subsequence in the backward pass if and only if right = left after processing j+1 (immediately before processing j).
So what if right > left (in the backward pass immediately before processing j)?
Well, then the maximality of our subsequence from i to j would be contradicted.
Namely, we can increase j to j' so that (j,j'] has one more ')' than '(', and decrease i to i', so that [i',i) has one more '(' than ')'.
The resulting subsequence from i' to j' will have longer length and will still be valid (the number of '(' and ')' will be incremented by the same amount).

Thus, either the backward pass or forward pass (possibly both) will detect the longest valid subsequence.

Edit: as @papercup points out in response to @bmunot9 , one can take i' = i - 1 and j' = j + 1, since

left > right immediately before i in the forward pass implies that s[i] == '(', otherwise maximality would already be contradicted (one could find i0<i such that s[i0,i) is valid, and thus s[i0,j] would be valid). Similarly
right > left immediately after j+1 (before j) in the backward pass implies s[j] == ')'
左边走不到的右边必然走的到，否则矛盾，具体见上面

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

41. First Missing Positive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int sz = nums.size();
        for(int i = 0; i < sz; ++i)
        {
            while(nums[i] > 0 && nums[i] <= sz && nums[i] != nums[nums[i] - 1]) // 这里之所以使用nums[i] != nums[nums[i] - 1]而不是nums[i] != i + 1, 是为了防止2个相同的数出现在这两处。这里是让当前的数字搬到正确的地方去，而不是让当前地方具有正确的数字。因为如果当前地方的数字缺失，那么永远也出不了循环。
                swap(nums[i], nums[nums[i] - 1]);
        }
        for(int i = 0; i < sz; ++i)
        {
            if(nums[i] != i + 1)
                return i + 1;
        }
        return sz + 1;
    }
};

一个长度为n的数列中，如果所有正数都没缺失，那么必然是1,2,3,4...排列，且一个数a的正确位置必定是在a-1处，因此如果A[i]不处在A[A[i] - 1]，那么交换A[i]和A[A[i] - 1]让他去正确位置，由此直到所有该到正确位置的到正确位置，其中<=0和>n的数没有正确位置，所以终止。 排好位置后再遍历

手动hash？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        nums.push_back(0); // 使得每个处于i位置的数对应为i，所以需要多加一个
        int n = nums.size();
        for(auto& num : nums)
        {
            if(num < 0 || num >= n) // 此处需要 >= n 而不是 > n 是因为原数组为n-1长度，那么最大正数为n-1，现在因为加了一个，但是n是不合法的
                num = 0;
        }
        for(auto& num : nums)
        {
            nums[num % n] += n;
        }
        for(int i = 1; i < n; ++i)
        {
            if(nums[i] / n == 0)
                return i;
        }
        return n;
    }
};

引用一段解释[@triton11](https://leetcode.com/triton11/) 

1
So consider an array like [1,4,3,3,3]. The length is 5, so n = 5. For each item, we are basically overwriting the spot at the index of the item with 5 + spot. So, at index 0 we have a 1, and 1%5 is 1, so we replace the item at index 1 with 5 + that item. Now our array is [1,9,3,3,3]. Next, at index 1 we have a 9, and 9%5 is 4 (notice how adding 5 didn't change the fact that we can still find the original value with % 5), so we replace the item at index 4 with 5 + that item. Our array is now [1, 9, 3, 3, 8]. Continuing, we get [1, 9, 3, 8, 8] then [1, 9, 3, 13, 8] and finally [1, 9, 3, 18, 8]. When we iterate through to find the values at the end, starting at index 1, we find that 9/5 is greater than 1, 3/5 is not greater than 1, 13/5 and 8/5 are greater than 1. Thus, since 3/5 is the first not greater than 5, we know index 2 was never used or added to, so 2 is the missing number. Feel free to comment if you have Qs or if I made any mistakes.
一个数加上一个模值后可以通过取余保留其原来的信息，也可以通过其大小显示出频率，如果一个位置的数没被加到，那他就小于模，就是missing的数

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

124. Binary Tree Maximum Path Sum

和543. Diameter of Binary Tree很像
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int curMax = INT_MIN;
        helper(root, curMax);
        return curMax;
    }
private:
    int helper(TreeNode* node, int& curMax)
    {
        if(!node)
            return 0;

        auto left = helper(node->left, curMax);
        auto right = helper(node->right, curMax);
        auto curSum = (left < 0 ? 0 : left) + (right < 0 ? 0 :right) + node->val;
        curMax = max(curSum, curMax);
        return max(max(left, right), 0) + node->val;

        return 0;
    } 
};

稍微改改，思想没变，但可以少1次的判断 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int curMax = INT_MIN;
        helper(root, curMax);
        return curMax;
    }
private:
    int helper(TreeNode* node, int& curMax)
    {
        if(!node)
            return 0;
        auto left = max(helper(node->left, curMax), 0);
        auto right = max(helper(node->right, curMax), 0);
        auto curSum = left + right + node->val;
        curMax = max(curSum, curMax);
        return max(left, right) + node->val;
    } 
};

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

76. Minimum Window Substring

使用了之前sliding window的范式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    string minWindow(string s, string t) {
        int begin = 0;
        int end = 0;
        pair<int, int> ret{0, 0};
        int curMax = s.size() + 1;
        unordered_map<char, int> map;
        for(auto& ch : t)
            map[ch] += 1;
        int count = map.size();
        while(end < s.size())
        {
            if(map.find(s[end]) != map.end())
            {
                --map[s[end]];
                if(!map[s[end]])
                    --count; 
            }
            ++end;
            while(!count)
            {
                if(map.find(s[begin]) != map.end())
                {
                    ++map[s[begin]];
                    if(map[s[begin]] > 0)
                        ++count;
                }
                if(end - begin < curMax)
                {
                    curMax = end - begin;
                    ret.first = begin;
                    ret.second = curMax;
                }
                ++begin;
            }
        }
        return s.substr(ret.first, ret.second);
    }
};
filtered

只记录存在于t中的字符的坐标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> map;
        for(auto& ch : t)
            map[ch] += 1;
        
        vector<pair<char, int>> newS;
        for(int i = 0; i < s.size(); ++i)
        {
            if(map.find(s[i]) != map.end())
                newS.push_back(pair<char, int>{s[i], i});
        }
        int begin = 0, end = 0;
        int count = map.size();
        int curWindow = s.size();
        int ansL = 0, ansR = 0;
        while(end < newS.size())
        {
            if(--map[newS[end].first] == 0)
                --count;
            while(!count)
            {
                if(newS[end].second - newS[begin].second < curWindow)
                {
                    ansL = newS[begin].second;
                    ansR = newS[end].second + 1;
                    curWindow = ansR - ansL;
                }
                if(++map[newS[begin].first] > 0)
                    ++count;
                ++begin;
            }
            ++end;
        }
        return s.substr(ansL, ansR - ansL);
    }
};

review 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.size();
        unordered_map<char, int> map;
        for(auto ch : t)
            ++map[ch];
        int count = map.size();
        int begin = 0, end = 0;
        int rl = 0;
        int subSize = INT_MAX;
        while(end < n)
        {
            if(--map[s[end]] == 0)
                --count;
            while(count == 0)
            {
                if(end - begin + 1 < subSize)
                {
                    rl = begin;
                    subSize = end - begin + 1;
                }
                if(++map[s[begin]] > 0)
                    ++count;
                ++begin;
            }
            ++end;
        }
        if(subSize == INT_MAX)
            return "";
        return s.substr(rl, subSize);
    }
};