Cinte's Leetcode Record
0%

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

125. Valid Palindrome

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
class Solution {
public:
    bool isPalindrome(string s) {
        auto lo = s.begin();
        auto hi = s.end() - 1;
        while(lo < hi)
        {
            if(*lo <= 'Z' && *lo >= 'A')
                *lo += 32;
            if(*hi <= 'Z' && *hi >= 'A')
                *hi += 32;
            if(!isDigitalOrAlphabet(*lo))
                ++lo;
            else if(!isDigitalOrAlphabet(*hi))
                --hi;
            else
            {
                if(*lo != *hi)
                    return false;
                ++lo;
                --hi;
            }
            
        }
        return true;
    }
private:
    bool isDigitalOrAlphabet(char& ch)
    {
        if((ch >= 'a' && ch < 'z') || (ch >= '0' && ch <= '9'))
            return true;
        else
            return false;
    }
};

T(n): O(n)

S(n): O(1)

review
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:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while(left < right)
        {
            while(left < right && !isValid(s[left]))
                ++left;
            while(left < right && !isValid(s[right]))
                --right;
            if(left >= right)
                break;
            if(tolower(s[left++]) != tolower(s[right--]))
                return false;
        }
        return true;
    }
private:
    inline bool isValid(char ch)
    {
        return (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9') || (ch >= 'A' && ch <= 'Z');
    }
};

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

120. Triangle

动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        for(size_t layer = 1; layer < n; ++layer)
        {
            triangle[layer][0] += triangle[layer - 1][0];
            triangle[layer].back() += triangle[layer - 1].back();
            for(size_t i = 1; i < triangle[layer].size() - 1; ++i)
            {
                triangle[layer][i] += min(triangle[layer - 1][i], triangle[layer - 1][i - 1]);
            }
        }
        sort(triangle.back().begin(), triangle.back().end());
        return triangle.back().front();
    }
};

T(n): O(n)

S(n): O(1)

review

IAMSVEG

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int sz = triangle.size();
        for(int i = 1; i < sz; ++i)
        {
            triangle[i].front() += triangle[i - 1].front();
            triangle[i].back() += triangle[i - 1].back();
            for(int j = 1, l = triangle[i].size(); j < l - 1; ++j)
                triangle[i][j] += min(triangle[i - 1][j], triangle[i - 1][j - 1]);
        }
        return *min_element(triangle.back().begin(), triangle.back().end());
    }
};

不修改原数组的O(n)空间复杂度的解法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int sz = triangle.size();
        vector<int> dp(sz);
        dp[0] = triangle[0][0];
        for(int i = 1; i < sz; ++i)
        {
            dp[i] = dp[i - 1] + triangle[i][i]; // 第i行有i+1个元素，所以dp[i]就表示最后一个，这里需要上面一行的前一个元素加上当前元素
            for(int j = i - 1; j > 0; --j)
                dp[j] = min(dp[j], dp[j - 1]) + triangle[i][j];
            dp[0] += triangle[i][0];
        }
        return *min_element(dp.begin(), dp.end());
    }
};
从下往上走 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int level = triangle.size();
        vector<int> dp(triangle.back().begin(), triangle.back().end());
        for(int i = level - 2; i >= 0; --i)
            for(int j = 0; j < i + 1; ++j)
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
        return dp[0];
    }
};

review

要选择最优的过去，不要选择不确定的未来

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int level = triangle.size();
        for(int i = level - 2; i >= 0; --i)
            for(int j = 0; j < i + 1; ++j)
                triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
        return triangle[0][0];
    }
};

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

48. Rotate Image

动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(size_t i = 0; i < (n + 1) / 2; ++i)
        {
            for(size_t j = 0; j < n / 2; ++j)
            {
                int tmp = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = matrix[i][j];
                matrix[i][j] = tmp;
            }
        }
    }
};

抄de

转置 + 翻转

transpose and reflect in linear algebra 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i = 0; i < n; ++i)
            for(int j = i; j < n; ++j)
                swap(matrix[i][j], matrix[j][i]);
        
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n / 2; ++j)
                swap(matrix[i][j], matrix[i][n - j - 1]);
    }
};
顺序反过来

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n / 2; ++j)
                swap(matrix[i][j], matrix[i][n - j - 1]);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j <= n - i - 1; ++j)
                swap(matrix[i][j], matrix[n - j - 1][n - i - 1]);
    }
};

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

96. Unique Binary Search Trees

动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numTrees(int n) {
        int *dp = new int[n + 1]{ 0 };
        dp[0] = dp[1] = 1;
        for(int i = 2; i <= n; ++i)
        {
            for(int j = 1; j <= i; ++j)
                dp[i] += dp[j - 1] * dp[i - j];
        }
        return dp[n];
    }
};

抄了discussion

将问题分解为每个小小的n会生成多少的树，最后左树数 * 右树数

review 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= i; ++j)
                dp[i] += dp[j - 1] * dp[i - j];
        return dp.back();
    }
};

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

63. Unique Paths 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
25
26
27
28
29
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid[0][0]) 
            return 0;
        else
            obstacleGrid[0][0] = 1;
        
        size_t m = obstacleGrid.size();
        size_t n = obstacleGrid[0].size();
        
        for(size_t i = 1; i < m; ++i)
        {
            obstacleGrid[i][0] = obstacleGrid[i][0] ? 0 : obstacleGrid[i - 1][0];
        }
        for(size_t i = 1; i < n; ++i)
        {
            obstacleGrid[0][i] = obstacleGrid[0][i] ? 0 : obstacleGrid[0][i - 1];
        }
        for(size_t i = 1; i < m; ++i)
        {
            for(size_t j = 1; j < n; ++j)
            {
                obstacleGrid[i][j] = obstacleGrid[i][j] ? 0 : obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
            }
        }
        return obstacleGrid.back().back();
    }
};

T(n) : O(m * n)

S(n) : O(1)

动态规划问题可以归结为网格，此处网格中元素为每个块对路径的贡献度，当本块为障碍时则贡献为0，当本块无障碍，则上方和左方的方块可以走过来，贡献的路径就是上和左相加

review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid[0][0] == 1 || obstacleGrid.back().back() == 1)
            return 0;
        int nx = obstacleGrid.size(), ny = obstacleGrid[0].size();
        obstacleGrid[0][0] = 1;
        for(int i = 1; i < ny; ++i)
            obstacleGrid[0][i] = obstacleGrid[0][i] ? 0 : obstacleGrid[0][i - 1];
        for(int i = 1; i < nx; ++i)
        {
            obstacleGrid[i][0] = obstacleGrid[i][0] ? 0 : obstacleGrid[i - 1][0]; // 放到这里而不是像上面那种首先遍历，是考虑到空间局部性
            for(int j = 1; j < ny; ++j)
                obstacleGrid[i][j] = obstacleGrid[i][j] ? 0 : obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
        }
        return obstacleGrid.back().back();
    }
};

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

64. Minimum Path Sum

动态规划
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 minPathSum(vector<vector<int>>& grid) {
        size_t m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = grid[0][0];      
        for(size_t i = 0; i < m; ++i)
        {
            for(size_t j = 0; j < n; ++j)
            {
                if(i == 0 && j == 0)
                    continue;
                if(i == 0)
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                else if(j == 0)
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                else
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};

T(n) : O(m * n)

S(n) : O(m * n)

尝试对S(n) 优化

观察代码，发现每次用到的数据只有dp[i][j], dp[i][j - 1]和dp[i - 1][j]，考虑dp[i][j], dp[i][j - 1]合并到一个一维数组，剩下的再生产一个一维数组。

参考unique path中的方法 

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 minPathSum(vector<vector<int>>& grid) {
        size_t m = grid.size(), n = grid[0].size();
        int* cur = new int[n];
        int* pre = new int[n];
        for (size_t i = 0; i < m; ++i)
        {
            for (size_t j = 0; j < n; ++j)
            {
                if (i == 0 && j == 0)
                    cur[j] = grid[i][j];
                else if (i == 0)
                    cur[j] = cur[j - 1] + grid[i][j];
                else if (j == 0)
                    cur[j] = pre[j] + grid[i][j];
                else
                    cur[j] = min(pre[j], cur[j - 1]) + grid[i][j];
            }
            swap(cur, pre);
        }
        return pre[n - 1];
    }
};
T(n) : O(m * n)

S(n) : O(2 * n)

再优化

pre[j] 与 cur[j] 可以合并

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 minPathSum(vector<vector<int>>& grid) {
        size_t m = grid.size(), n = grid[0].size();
        int* cur = new int[n];
        for (size_t i = 0; i < m; ++i)
        {
            for (size_t j = 0; j < n; ++j)
            {
                if (i == 0 && j == 0)
                    cur[j] = grid[i][j];
                else if (i == 0)
                    cur[j] = cur[j - 1] + grid[i][j];
                else if (j == 0)
                    cur[j] = cur[j] + grid[i][j];
                else
                    cur[j] = min(cur[j], cur[j - 1]) + grid[i][j];
            }
        }
        return cur[n - 1];
    }
};

T(n) : O(m * n)

S(n) : O(n)

review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(n, 0);
        dp[0] = grid[0][0];
        for(int i = 1; i < n; ++i)
            dp[i] = dp[i - 1] + grid[0][i];
        for(int i = 1; i < m; ++i)
            for(int j = 0; j < n; ++j)
                dp[j] = (j > 0 ? min(dp[j], dp[j - 1]) : dp[j]) + grid[i][j];
        return dp.back();
    }
};

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

49. Group Anagrams

按照排序后的字符串作为索引
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        for(auto& str : strs)
        {
            string key = str;
            sort(key.begin(), key.end());
            map[key].push_back(str);
        }
        vector<vector<string>> ret;
        for(auto& [_, it] : map)
            ret.push_back(std::move(it));
        return ret;
    }
};
根据字母出现的频次来hash

官解的手写hash函数或者string作为位图，每一位来记录。

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

62. Unique Paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int uniquePaths(int m, int n) {
        return path(m, n);
    }
private:
    int path(int m, int n)
    {
        if(m == 1 || n == 1)
            return 1;
        
        return path(m - 1, n) + path(m, n - 1);
    }
};

Time Limit Exceeded

动态规划，划分为子路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1));
        for(size_t i = 1; i < m; ++i)
        {
            for(size_t j = 1; j < n; ++j)
            {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};

空间优化 

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1);
        for(int i = 1; i < m; ++i)
            for(int j = 1; j < n; ++j)
                dp[j] += dp[j - 1];   
        return dp.back();
    }
};

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

70. Climbing Stairs

动态规划，每一步都可分为1 + 剩余n-1 + 2 + 剩余n-2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int climbStairs(int n) {
        if(n == 1) return 1;
        vector<int> dp;
        dp.push_back(1);
        dp.push_back(2);
        for(size_t i = 2; i < n; ++i)
        {
            dp.push_back(dp[i - 1] + dp[i - 2]);
        }
        return dp.back();
    }
};
优化S(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int climbStairs(int n) {
        if(n < 2)
            return n;
        int dp[2]{1, 2};
        for(int i = 2; i < n; ++i)
        {
            dp[0] = dp[0] + dp[1];
            swap(dp[0], dp[1]);
        }
        return dp[1];
    }
};

review 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int climbStairs(int n) {
        if(n < 2)
            return n;
        int a = 1, b = 2;
        for(int i = 3; i <= n; ++i)
        {
            a += b;
            swap(a, b);
        }
        return b;
    }
};

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

53. Maximum Subarray

Kadane算法

Whenever you see a question that asks for the maximum or minimum of something, consider Dynamic Programming as a possibility

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSofar = nums[0];
        int maxCur = 0;
        for(auto num : nums)
        {
            maxCur = max(num, num + maxCur);
            maxSofar = max(maxCur, maxSofar);
        }
        return maxSofar;
    }
};
分而知之D&Q
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
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return find(0, nums.size() - 1, nums);
    }
private:
    int find(int left, int right, vector<int>& nums)
    {
        if(left > right) return INT_MIN;
        
        int mid = (left + right) / 2;
        int cur = 0;
        int maxLeft = 0; // 如果都小于0，那就不采用那边，那么那边的和就是0
        int maxRight = 0;
        
        for(int i = mid - 1; i >= left ; --i)
        {
            cur += nums[i];
            maxLeft = max(maxLeft, cur);
        }
        
        cur = 0;
        
        for(int i = mid + 1; i <= right; ++i)
        {
            cur += nums[i];
            maxRight = max(maxRight, cur);
        }
        
        int bestCombined = nums[mid] + maxLeft + maxRight;
        int leftHalf = find(left, mid - 1, nums); // 这里不用考虑为什么不把mid包含进来，因为如果包含的mid是属于最大的子序列，且只有单边，那么maxRight = 0的情况就已经将其包括了
        int rightHalf = find(mid + 1, right, nums);
        
        return max(bestCombined, max(leftHalf, rightHalf));
    }
};

取中点，往左计算和，往右计算和，这时候有三种情况，中点是最长子串之中的元素，最长子串在中点右边，最长子串在中点左边。对于第一种情况，那就是左+右+中，对于后两种，那么再对左右子串进行同样的查找(DQ)