Cinte's Leetcode Record
0%

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

115. 不同的子序列

动态规划

设f(i, j)是s[0...i)中t[0...j]匹配到的个数

Base:

当t为空时，s总能成功匹配t

转移方程：

  1. 当s[i] == t[j]时

    1. s[i]让自己和t[j]匹配：那么f(i + 1, j + 1)的值就包括了f(i, j)
    2. s[i]不让自己和t[j]匹配：那么对于s[0...i+1)来说，因为没有匹配，所以f(i + 1, j + 1)的值就包括f(i, j + 1)，就是让前面s[0...i)去和t[0...j + 1)匹配

  2. 当s[i] != t[j]时

    只能由前面的字符串去和t[0...i + 1)尝试匹配了。

所以最终的递推方程也由此得到。

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 numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        if(m < n)
            return 0;
        vector<vector<unsigned int>> dp(m + 1, vector<unsigned int>(n + 1));
        dp[0][0] = 1;
        for(int i = 0; i < m; ++i)
        {
            dp[i + 1][0] = 1;
            for(int j = 0; j < n; ++j)
            {
                if(s[i] == t[j])
                    dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
                else
                    dp[i + 1][j + 1] = dp[i][j + 1];
            }
        }
        return dp.back().back();
    }
};

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

175. 组合两个表

1
2
3
4
# Write your MySQL query statement below
SELECT FirstName, LastName, City, state
FROM Person LEFT OUTER JOIN Address
ON Person.PersonId = Address.PersonId

必知必会P110

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

187. 重复的DNA序列

暴力法(超时)
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int n = s.size();
        unordered_set<string> set;
        for(int i = 0; i < n - 10; ++i)
        {
            if(s.find(s.substr(i, 10), i + 1) != std::string::npos)
                set.insert(s.substr(i, 10));
        }
        return vector<string>(set.begin(), set.end());
    }
};
哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_map<string, int> map;
        vector<string> ret;
        int n = s.size();
        for(int i = 0; i <= n - 10; ++i)
        {
            string sub = s.substr(i, 10);
            if(++map[sub] == 2)
                ret.push_back(std::move(sub));
        }
        return ret;
    }
};
用位运算来实现hash

c++中一般使用int值本身作为hash值

这里在O(1)时间内计算出hash

具体看题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int n = s.size();
        if(n < 11)
            return {};
        unordered_map<char, int> bin{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
        int x = 0;
        for(int i = 0; i < 10; ++i)
            x = (x << 2) | bin[s[i]];
        unordered_map<int, int> map{{x, 1}};
        vector<string> ret;
        for(int i = 1; i < n - 9; ++i)
        {
            x = ((x << 2) | bin[s[i + 9]]) & ((1 << 20) - 1);
            if(++map[x] == 2)
                ret.push_back(s.substr(i, 10));
        }
        return ret;
    }
};
字符串哈希

参考

字符串哈希

看不懂

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

1154. 一年中的第几天

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int dayOfYear(string date) {
        int dayCount[]{0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};
        int year = atoi(date.substr(0, 4).c_str());
        int month = atoi(date.substr(5, 2).c_str());
        int day = atoi(date.substr(8, 2).c_str());
        int ret = dayCount[month - 1] + day;
        if(month > 2 && ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0))
            ++ret;
        return ret;
    }
};

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

81. 搜索旋转排序数组 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:
    bool search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while(lo <= hi)
        {
            int mid = lo + (hi - lo) / 2;
            if(nums[mid] == target)
                return true;
            if(nums[mid] == nums[lo]) // 缩小区间，不然无法确定mid在左还是右
            {
                ++lo;
            }else if(nums[mid] > nums[lo])
            {
                if(target >= nums[lo] && target < nums[mid])
                    hi = mid - 1;
                else
                    lo = mid + 1;
            }else
            {
                if(target < nums[lo] && target > nums[mid])
                    lo = mid + 1;
                else
                    hi = mid - 1;
            }
        }
        return false;
    }
};

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

686. 重复叠加字符串匹配

模拟法

下界：复制后的a的长度必须大于等于b的长度

上界：下界+1(因为原字符串长度可能大于下界-1但小于下界，所以不能保证b的结尾可以具备使用a中所有字符的能力，因此多复制一个可以保证a中所有字符都作为b的开头和结尾)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        int m = a.size(), n = b.size();
        int c = 0;
        string tmp;
        while(tmp.size() < b.size() && ++c)
            tmp += a;
        tmp += a;
        int pos = tmp.find(b, 0);
        if(pos == std::string::npos)
            return -1;
        if(pos + n - 1 < m * c)
            return c;
        return c + 1;
    }
};
kmp

一文详解 KMP 算法

字符串哈希

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

630. 课程表 III

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
class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(courses.begin(), courses.end(), [](auto& v1, auto& v2)
        {
            return v1[1] < v2[1];
        });
        priority_queue<int> pq;
        int endTime = 0;
        for(auto& course : courses)
        {
            if(endTime + course[0] <= course[1])
            {
                endTime += course[0];
                pq.push(course[0]);
            }
            else if(!pq.empty() && course[0] < pq.top()) // 重点在这，如果当前不能简单得加到原来的序列中，那么如果当前的消耗时间小于里面的最长时间，就替换进去
            {
                endTime -= pq.top();
                endTime += course[0];
                pq.pop();
                pq.push(course[0]);
            }
        }
        return pq.size();
    }
};

设之前的是t1 + t2 + .... t_j-1 + t_j + t_j+1 +.....tk <= dk

那么将t_j替换成t_i后，由于后者小于前者，所以上述关系仍旧存在，而由于d_i <= d_k，所以都成立。

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

524. 通过删除字母匹配到字典里最长单词

暴力判断

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
class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        int n = s.size();
        int maxLength{ 0 }, ret = -1;
        for(int i = 0, sz = dictionary.size(); i < sz; ++i)
        {
            int j{ 0 };
            int m = dictionary[i].size();
            for(int q = 0; q < n && j < m; ++q)
            {
                if(s[q] == dictionary[i][j])
                    ++j;
            }
            if(j == m)
            {
                if(m > maxLength)
                {
                    ret = i;
                    maxLength = m;
                }
                if(m == maxLength && (ret == -1 || dictionary[i] < dictionary[ret]))
                    ret = i;
            }
        }
        return ret == -1 ? "" : dictionary[ret];
    }
};

先排序后在老方法判断也行，但是没有意义

dp(离谱)

f[i][j]表示第i位置之后j+'a'字母第一次出现的位置。

如果s[i] == j = 'a'，那么f[i][j] = i，否则f[i][j] = f[i + 1][j]

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
class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        int n = s.size();
        vector<vector<int>> dp(n + 1, vector<int>(26, n));
        int ret = -1;
        for(int i = n - 1; i >= 0; --i)
            for(int j = 0; j < 26; ++j)
                dp[i][j] = (s[i] == j + 'a') ? i : dp[i + 1][j];
        for(int i = 0, sz = dictionary.size(); i < sz; ++i)
        {
            int m = dictionary[i].size(), j = 0;
            int k = 0;
            for(; j < m; ++j)
            {
                if(dp[k][dictionary[i][j] - 'a'] == n)
                    break;
                else
                    k = dp[k][dictionary[i][j] - 'a'] + 1; // 注意加一。否则小心困在原地
            }
            if(j == m)
                if(ret == -1 || (m > dictionary[ret].size() || (m == dictionary[ret].size() && dictionary[i] < dictionary[ret])))
                    ret = i;
        }
        return ret == -1 ? "" : dictionary[ret];
    }
};

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

807. 保持城市天际线

直接遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> rowMax(n), colMax(n);
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                rowMax[i] = max(rowMax[i], grid[i][j]);
                colMax[j] = max(colMax[j], grid[i][j]);
            }
        }
        int ret{ 0 };
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                ret += min(rowMax[i], colMax[j]) - grid[i][j];
        return ret;
    }
};

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

680. 验证回文字符串 Ⅱ

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:
    bool validPalindrome(string s) {
        int l = 0, r = s.size() - 1;
        while(l < r)
        {
            if(s[l] != s[r])
                return check(s, l + 1, r) || check(s, l, r - 1); // 删掉后分别检查是不是回文串
            ++l;
            --r;
        }
        return true;
    }
private:
    bool check(string& s, int l, int r)
    {
        while(l < r && s[l] == s[r]) 
        {
            ++l;
            --r;
        }
        return l >= r;
    }
};