Cinte's Leetcode Record
0%

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

92. 反转链表 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
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode pseudoHead;
        ListNode* pre = &pseudoHead;
        pre->next = head;
        int count = 1;
        while(head)
        {
            if(count == left)
                break;
            pre = head;
            head = head->next;
            ++count;
        }
        ListNode* pt = nullptr;
        while(head)
        {
            auto next = head->next;
            head->next = pt;
            pt = head;
            head = next;
            if(count++ == right)
                break;
        }
        pre->next->next = head;
        pre->next = pt;
        return pseudoHead.next;
    }
};

边遍历边顺便反转，事实上也是遍历一次，比关解方法一中先找左右再切断要好。

方法2

好绕，建议画图，head永远是那个点，会换了几次后换到最后

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode pseudoHead;
        ListNode* pre = &pseudoHead;
        pre->next = head;
        int count = 1;
        while(count != left)
        {
            pre = head;
            head = head->next;
            ++count;
        }
        ListNode* next;
        while(count != right)
        {
            next = head->next;
            head->next = next->next;
            next->next = pre->next;
            pre->next = next;
            ++count;
        }
        return pseudoHead.next;
    }
};

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

204. 计数质数

暴力法(超时)

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 countPrimes(int n) {
        if(n <= 2)
            return 0;
        int ret = 1;
        for(int i = 3; i < n; ++i)
        {
            ret += isPrime(i);
        }
        return ret;
    }
private:
    int isPrime(int x)
    {
        for(int i = 2; i * i <= x; ++i)
        {
            if(x % i == 0)
                return 0;
        }
        return 1;
    }
};
埃氏筛

计数质数 - 计数质数 - 力扣（LeetCode） (leetcode-cn.com)

如果 xx 是质数，那么大于 xx 的 xx 的倍数 2x,3x,2x,3x,… 一定不是质数，因此我们可以从这里入手。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countPrimes(int n) {
        vector<int> memo(n, 1);
        int ret = 0;
        for(int i = 2; i < n; ++i)
        {
            if(memo[i])
            {
                ++ret;
                for(long j = long(i) * i; j < n; j += i) // 因为小于x的x倍，比如2x，3x，(x-1)x在前面遍历2,3,x-1时候已经标记了，所以这里只需要从x倍开始
                {
                    memo[j] = 0;
                }
            }
        }
        return ret;
    }
};
线性筛

保留

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

190. 颠倒二进制位

题目意思讲的有点不清楚，题意是：

把给定的二进制串左右颠倒，即111001 -> 100111

不得不说，whca

直接循环32次，然后把位倒着放。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        int ret = 0;
        for(int i = 0; i < 32; ++i)
        {
            ret |= (n & 1) << (31 - i);
            n >>= 1;
        }
        return ret;
    }
};
DQ

颠倒2位->颠倒4位->颠倒8位->颠倒16位->颠倒32位 自底而上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = ((n >> 1) & M1) | (n & M1) << 1;
        n = ((n >> 2) & M2) | (n & M2) << 2;
        n = ((n >> 4) & M3) | (n & M3) << 4;
        n = ((n >> 8) & M4) | (n & M4) << 8;
        return (n >> 16) | (n << 16);
    }
private:
    uint32_t M1 = 0x55555555;
    uint32_t M2 = 0x33333333;
    uint32_t M3 = 0x0f0f0f0f;
    uint32_t M4 = 0x00ff00ff;
};

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

172. 阶乘后的零

看答案

是一道数学找规律题目

总体就是出现10就会多一个0，10由2x5构成，而2因子个数远大于5因子个数，所以最后就是求5因子个数就是0的个数

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int trailingZeroes(int n) {
        int ret = 0;
        while(n)
        {
            ret += n / 5;
            n /= 5; // 依次隔5，隔25...
        }
        return ret;
    }
};

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

166. 分数到小数

主要难点是对于循环小数的处理，当循环小数出现时，表示计算式子也出现了循环，由于分母在这里是始终保持不变的，所以循环的出现等价于分子的循环，也就是余数的循环。因此，当出现同一个余数2次时，表示开始循环了，而循环小数的起始处就是第一次出现这个余数的时候。使用map来记录每个余数的出现及其第一次出现的位置即可在后续出现时使用括号括起来。

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
class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if(denominator == 0)
            return "";
        if(numerator == 0)
            return "0";
        // 防止溢出，转换为long
        // 在win32和win64和linux32中，long和int都是32位(双字)，但是在linux64中long为64位
        // 但是long long一般都是64位
        long lNumerator = static_cast<long>(numerator);
        long lDenominator = static_cast<long>(denominator);
        string ret;
        if(lNumerator < 0 ^ lDenominator < 0)
            ret.push_back('-');
        lNumerator = labs(lNumerator);
        lDenominator = labs(lDenominator);
        ret += to_string(lNumerator / lDenominator);
        if(lNumerator % lDenominator)
            ret.push_back('.');
        int index = ret.size() - 1;
        unordered_map<long, int> record;
        while(lNumerator % lDenominator)
        {
            lNumerator = (lNumerator % lDenominator) * 10;
            if(record.count(lNumerator))
            {
                ret.insert(record[lNumerator], "(");
                ret.push_back(')');
                break;
            }
            // 这里记录的是余数而不是当前的数位，因为只有余数相同时才能保证后面都相同
            record[lNumerator] = ++index;
            ret += to_string(lNumerator / lDenominator);
            
        }
        return ret;
    }
};

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

149. 直线上最多的点数

暴力 枚举斜率
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int sz = points.size();
        int ret = 1;
        for(int i = 0; i < sz; ++i)
        {
            unordered_map<double, int> map;
            for(int j = 0; j < sz; ++j)
            {
                if(j == i)
                    continue;
                double grad = (points[i][1] - points[j][1]) * 1.0/ (points[i][0] - points[j][0]); // 浮点除以0是不确定行为，不应该保留
                ++map[grad];
                ret = max(map[grad] + 1, ret);
            }
        }
        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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int sz = points.size();
        if(sz <= 2)
            return sz;
        int ret = 0;
        for(int i = 0; i < sz; ++i)
        {
            // 优化方案
            // 剩下的点都不如ret多了，那接下来不管怎么弄都超不过ret了，所以没用了意义
            if(ret > sz - i || ret > sz / 2)
                break;
            // 答案中的数字太抽象，这里将二元组用string表示
            unordered_map<string, int> map;
            for(int j = i + 1; j < sz; ++j)
            {
                int x = points[j][0] - points[i][0];
                int y = points[j][1] - points[i][1];
                if(x == 0)
                    y = 1;
                else if(y == 0)
                    x = 1;
                else
                {
                    if(y < 0)
                    {
                        x = -x;
                        y = -y;
                    }
                    int gcdXY = gcd(abs(x), abs(y));
                    x /= gcdXY;
                    y /= gcdXY;
                }
                ++map[to_string(x) + ":" + to_string(y)];
            }
            int maxN = 0;
            for(auto& [_, num] : map)
                maxN = max(maxN, num + 1);
            ret = max(ret, maxN);
        }
        return ret;
    }
private:
    // 欧几里得算法求公约数
    int gcd(int a, int b)
    {
        return b ? gcd(b, a % b) : a; 
    }
};

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

140. 单词拆分 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
30
31
32
33
34
35
class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> set(wordDict.begin(), wordDict.end());
        vector<string> ret;
        vector<string> st;
        backTrack(s, s.size(), 0, set, ret, st);
        return ret;
    }
private:
    void backTrack(string& s, int sz, int start, unordered_set<string>& set, vector<string>& ret, vector<string>& st)
    {
        if(start == sz)
        {
            string r;
            for(auto& str : st)
                r += str + " ";
            r.pop_back();
            ret.push_back(r);
            return;
        }
        int end = start;
        while(end < sz)
        {
            auto cur = s.substr(start, end - start + 1);
            if(set.count(cur))
            {
                st.push_back(cur);
                backTrack(s, sz, end + 1, set, ret, st);
                st.pop_back();
            }
            ++end;
        }
    }
};
对回溯过程中进行记忆优化
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
class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        map = vector<vector<string>>(s.size() + 1);
        set = unordered_set<string>(wordDict.begin(), wordDict.end());
        backTrack(s, s.size(), 0);
        return map[0];
    }
private:
    unordered_set<string> set;
    vector<vector<string>> map; // 对于同一起始点的，使用这个map来记录，因为同一起始点开始的字符串的子一定一样，不用重新计算。
    void backTrack(string& s, int sz, int index)
    {
        if(!map[index].empty()) // 走过的就不用再走了
            return;
        if(index == sz) // 走到最后了，加入个空字符串，为了后面可以添加进去而不至于当作没走过。
        {
            map[index].push_back(""); 
            return;
        }
        for(int i = index; i < sz; ++i)
        {
            auto word = s.substr(index, i - index + 1);
            if(set.count(word))
            {
                backTrack(s, sz, i + 1); // 回溯，先把后面的计算完再用前面的加。
                for(auto& str : map[i + 1])
                    map[index].push_back(str.empty() ? word : word + " " + str);
            }
        }
    }
};

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

44. 通配符匹配

类似剑指 Offer 19. 正则表达式匹配 | Cinte's Leetcode Record

dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isMatch(string s, string p) {
        int length1 = s.size(), length2 = p.size();
        vector<vector<int>> dp(length1 + 1, vector<int>(length2 + 1, false));
        dp.back().back() = true;
        for(int i = length1; i >= 0; --i)
        {
            for(int j = length2 - 1; j >= 0; --j)
            {
                bool firstMatch = i < length1 && (s[i] == p[j] || p[j] == '?');
                if(p[j] == '*')
                    dp[i][j] = dp[i][j + 1] || (i < length1 && dp[i + 1][j]); // 如果我匹配你星号，那我要看看我前面的串能不能和你匹配。如果我拒绝你的星号，那我要看看我能不能和你前面的表达式匹配
                else if(i < length1)
                    dp[i][j] = firstMatch && dp[i + 1][j + 1];
            }
        }
        return dp[0][0];
    }
};

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

227. 基本计算器 II

先算优先级高的乘除再总体算加减。

主要是对这个presign的处理

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
class Solution {
public:
    int calculate(string s) {
        char preSign = '+';
        long num = 0;
        int sz = s.size();
        vector<int> st;
        for(int i = 0; i < sz; ++i)
        {
            auto ch = s[i];
            if(isdigit(ch))
                num = num * 10 + ch - '0';
            // 当是符号时候或者走到了最后一位
            if((!isdigit(ch) && ch != ' ') || i == sz - 1)
            {
                // 记录之前的符号
                switch(preSign)
                {
                    case '+':
                        st.push_back(num);
                        break;
                    case '-':
                        st.push_back(-num);
                        break;
                    case '*':
                        st.back() *= num;
                        break;
                    case '/':
                        st.back() /= num;
                }
                num = 0;
                preSign = ch;
            }
        }
        return accumulate(st.begin(), st.end(), 0);
    }
};

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

210. 课程表 II

参考(´∇｀) 被你发现啦~207. Course Schedule | Cinte's Leetcode Record

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
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        for(auto& prerequisite : prerequisites)
            // 注意这里的方向不能换，因为这种写法是往前找先决课程
            // 如果找到末尾的话说明找到了一个最基层的先决课程，需要最先学
            // 如果方向换的话就是从底层网上走，找到一个可以完成学习的课程，是最后的那一个课程
            // 为了结果返回的正确性，不能改变方向，反之207题中只是为了判断环路，所以可以返回方向。
            graph[prerequisite[0]].push_back(prerequisite[1]);
        vector<int> checked(numCourses, 0);
        vector<int> visited(numCourses, 0);
        vector<int> ret;
        ret.reserve(numCourses);
        for(int i = 0; i < numCourses; ++i)
            if(!dfs(ret, i, checked, visited, graph))
                return {};
        return ret;
    }
private:
    bool dfs(vector<int>& ret, int course, vector<int>& checked, vector<int>& visited, vector<vector<int>>& graph)
    {
        if(visited[course])
            return false;
        if(checked[course])
            return true;
        visited[course] = 1;
        for(auto& p : graph[course])
            if(!dfs(ret, p, checked, visited, graph))
                return false;
        checked[course] = 1;
        // 找到了一个没有被访问过的基层，加入返回列表中
        ret.push_back(course);
        visited[course] = 0;
        return true;
    }
};