Cinte's Leetcode Record
0%

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

206. 反转链表

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        while(head)
        {
            auto next = head->next;
            head->next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
};

递归 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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* reverseList(ListNode* head) {
        if(!head || !head->next)
            return head;
        auto h = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return h;
    }
};

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

357. 计算各个位数不同的数字个数

数学方法

第一位如果取0，那结果就是n=n-1时候的结果

第一位如果取1~9，第二位可以取0，所以有9种取法，第三位有8种，依此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n == 0)
            return 1;
        if(n > 10)
            return 0;
        int a = 10, pre = 9;
        for(int i = 2; i <= n; ++i)
            a += pre *= (11 - i);
        return a;
    }
};

dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n == 0)
            return 1;
        int a = 0, sum = 1, tmp = 0;
        for(int i = 2; i <= n; ++i)
        {
            a = a * 10 + (9 * sum - a) * (i - 1); // 每一种不重复的数字剩下有i-1位，这i-1种可能性
            sum *= 10;
            tmp += a;
        }
        return sum * 10 - tmp;
    }
};

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

77. 组合

回溯

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:
    vector<vector<int>> combine(int n, int k) {
        vector<int> tmp;
        vector<vector<int>> ret;
        backTrack(n, k, 1, tmp, ret);
        return ret;
    }
private:
    void backTrack(int n, int k, int start, vector<int>& tmp, vector<vector<int>>& ret)
    {
        if(n - start + 1 < k - tmp.size()) // 剪枝
            return;
        if(tmp.size() == k)
        {
            ret.push_back(tmp);
            return;
        }
        for(int i = start; i <= n; ++i)
        {
            tmp.push_back(i);
            backTrack(n, k, i + 1, tmp, ret);
            tmp.pop_back();
        }
    }
};

字典序法太烦了

引用@老黑不黑的评论

1
btw我又读了十几遍，总算搞清楚算法了。简单来说就是一开始把所有的1放在尾部，比如00111这样，然后按顺序把1往前移动。如果所有的1都在最前头了，比如11100，就留一位1，其余的全部移到末尾，比如10011，然后再重复这个操作，直到所有的1都“被”留在了最前面，即11100，便完成了全部穷举。其实是很直观的一个思路。不知道为什么，一加上数学语言的buf之后，就让我愣是横竖也看不懂过程了。LC-CN还算有良心，加了个小贴士 这个方法理解起来比「方法一」复杂，建议读者遇到不理解的地方可以在草稿纸上举例模拟这个过程。

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

375. 猜数字大小 II

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 getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        for(int i = n; i >= 1; --i)
        {
            dp[i][i] = 0;
            for(int j = i + 1; j <= n; ++j)
            {
                int minNum = INT_MAX;
                for(int k = i; k < j; ++k)
                {
                    // 注意方向，这里用到了i到k-1和k+1到j的数据，很显然都是i之后的数据，所以i的遍历需要从后面开始遍历
                    dp[i][j] = min(dp[i][j], max(dp[i][k - 1], dp[k + 1][j]) + k);
                }
                dp[i][j] = minNum;
            }
        }
        return dp[1][n];
    }
};

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

946. 验证栈序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int p = 0;
        for(auto num : pushed)
        {
            s.push(num);
            while(!s.empty() && s.top() == popped[p])
            {
                s.pop();
                ++p;
            }
        }
        return s.empty();
    }
};

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

341. 扁平化嵌套列表迭代器

第一次在类里面使用递归

答案中将原vector展开存储后再取数值不符合迭代器的思想，因此实现了一个在原数组上进行操作的迭代器

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
51
52
53
54
55
56
57
58
59
60
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */

class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) : list(nestedList), cur(list.begin()) {

    }

    int next() {
        if(cur->isInteger())
            return (cur++)->getInteger();
        else
            return it->next();
    }
    
    bool hasNext() {
        // while的作用是去除空list防止误导
        while(cur != list.end())
        {
            if(cur->isInteger())
                return true;
            if(!it)
                it = std::make_shared<NestedIterator>(cur->getList());
            if(!it->hasNext())
            {
                ++cur;
                it = nullptr;
            }
            else
                return true;
        }
        return cur != list.end();
    }
private:
    vector<NestedInteger>& list;
    vector<NestedInteger>::iterator cur;
    std::shared_ptr<NestedIterator> it = nullptr;
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */

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

454. 四数相加 II

hash

求前2个数组的所有可能和和后2个数组的所有可能和，使问题退化为一个two sum问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> map;
        for(auto n1 : nums1)
            for(auto n2 : nums2)
                ++map[n1 + n2];
        int ret = 0;
        for(auto n3 : nums3)
            for(auto n4 : nums4)
                ret += map[-(n3 + n4)];
        return ret;
    }
};

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

329. 矩阵中的最长递增路径

回溯(超时)
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:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                backTrack(matrix, i, j, -1, 0);
        return ret;
    }
private:
    int ret = 0;
    void backTrack(vector<vector<int>>& matrix, int i, int j, int pre, int tmp)
    {
        if(i < 0 || j < 0 || i >= matrix.size() || j >= matrix[0].size() || matrix[i][j] <= pre || matrix[i][j] == -1)
            return;
        pre = matrix[i][j];
        ++tmp;
        ret = max(tmp, ret);
        matrix[i][j] = -1;
        backTrack(matrix, i + 1, j, pre, tmp);
        backTrack(matrix, i - 1, j, pre, tmp);
        backTrack(matrix, i, j + 1, pre, tmp);
        backTrack(matrix, i, j - 1, pre, tmp);
        matrix[i][j] = pre;
    }
};

优化，记忆化dfs

因为前面走过来的路必然是小于当前的数字的，而接下来可以走的路必然是大于当前数字的，因此不用担心会走回头路。

而对于记忆化来说，不用担心这个记忆化的结果是从那边走来的，只需要知道获取这个记忆化数据的这一格必然大于记忆化的这一格，所以不可能是之前走过的路

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:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        memo.resize(m, vector<int>(n));
        int ret = 0;
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                ret = max(ret, dfs(matrix, i, j, m, n));
        return ret;
    }
private:
    vector<vector<int>> memo;
    int dir[4][2]{ {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int dfs(vector<vector<int>>& matrix, int i, int j, int m, int n)
    {
        if(memo[i][j])
            return memo[i][j];
        ++memo[i][j];
        for(int k = 0; k < 4; ++k)
        {
            int nextI = i + dir[k][0], nextJ = j + dir[k][1];
            if(nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n && matrix[nextI][nextJ] > matrix[i][j])
                memo[i][j] = max(memo[i][j], dfs(matrix, nextI, nextJ, m, n) + 1);
        }
        return memo[i][j];
    }
};
dp，拓扑排序

从出度为0的点开始bfs，出度为0表示是矩阵中最大的点。然后往前bfs则表示往前一步走，当不能继续dfs时候就表示走到头了，具体看题解-方法二

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
class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int dir[4][2]{ {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        vector<vector<int>> outDegree(m, vector<int>(n));
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                for(int k = 0; k < 4; ++k)
                {
                    int newI = i + dir[k][0], newJ = j + dir[k][1];
                    if(newI >= 0 && newJ >= 0 && newI < m && newJ < n && matrix[newI][newJ] > matrix[i][j])
                        ++outDegree[i][j];
                }
            }
        }
        queue<pair<int, int>> q;
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(outDegree[i][j] == 0)
                    q.emplace(i, j);
        int ret = 0;
        while(!q.empty())
        {
            ++ret;
            for(int k = 0, sz = q.size(); k < sz; ++k)
            {
                auto [i, j] = q.front();
                q.pop();
                for(int l = 0; l < 4; ++l)
                {
                    int newI = i + dir[l][0], newJ = j + dir[l][1];
                    if(newI >= 0 && newJ >= 0 && newI < m && newJ < n && matrix[newI][newJ] < matrix[i][j])
                    {
                        if(--outDegree[newI][newJ] == 0)
                            q.emplace(newI, newJ);
                    }
                }
            }
        }
        return ret;
    }
};

题解中思考题的回答

  1. 「方法一」中使用了记忆化存储和深度优先搜索，这里的深度优先搜索可以替换成广度优先搜索吗？

    不能，因为需要记录的是最长路径，而广度优先搜索只能记录一个层次的值

  2. 「方法二」中基于拓扑排序对排序后的有向无环图做了层次遍历，如果没有拓扑排序直接进行广度优先搜索会发生什么？

    拓扑排序决定了dp的顺序，dp上一步决定下一步的值

  3. 「方法二」中如果不使用拓扑排序，而是直接按照矩阵中元素的值从大到小进行排序，并依此顺序进行状态转移，那么可以得到正确的答案吗？如果是从小到大进行排序呢？

    可以，但慢，时间复杂度O(MNlog(MN))

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

315. 计算右侧小于当前元素的个数

归并排序

参考剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode） (leetcode-cn.com)

重点是被排序过程中的数字下标的对应，这里取了一个index数列，在排序的同时进行移动，从而保证下标对应

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
51
52
53
54
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        tmp.resize(n);
        index.resize(n);
        indextmp.resize(n);
        ret.resize(n);
        for(int i = 0; i < n; ++i)
            index[i] = i;
        mergeSort(nums, 0, n - 1);
        return ret;
    }
private:
    vector<int> ret;
    vector<int> tmp;
    vector<int> index;
    vector<int> indextmp;
    void mergeSort(vector<int>& nums, int lo, int hi)
    {
        if(lo >= hi)
            return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);
        copy(nums.begin() + lo, nums.begin() + hi + 1, tmp.begin() + lo);
        copy(index.begin() + lo, index.begin() + hi + 1, indextmp.begin() + lo);
        int i = lo, j = mid + 1, k = lo;
        while(k <= hi)
        {
            if(i == mid + 1)
            {
                nums[k] = tmp[j];
                index[k] = indextmp[j++];
            }else if(j == hi + 1)
            {
                ret[indextmp[i]] += j - mid - 1; // 当i这个数要进去坐牢，j这边已经进去的数都比他小，所以共j-mid-1个，当前j是hi+1，所以不包含j
                nums[k] = tmp[i];
                index[k] = indextmp[i++];
            }
            else if(tmp[i] <= tmp[j])
            {
                ret[indextmp[i]] += j - mid - 1; // 当i这个数要进去坐牢，j这边已经进去的数都比他小，所以共j-mid-1个，当前这边大于等于i那边的数，所以不包含j
                nums[k] = tmp[i];
                index[k] = indextmp[i++];
            }else
            {
                nums[k] = tmp[j];
                index[k] = indextmp[j++];
            }
            ++k;
        }
    }
};
离散化树状数组

迟点看 https://www.cnblogs.com/xenny/p/9739600.html

https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/solution/shu-zhuang-shu-zu-by-liweiwei1419/

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

334. 递增的三元子序列

维护一个牌堆，和之前一题差不多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        vector<int> bucket;
        for(auto num : nums)
        {
            auto loc = lower_bound(bucket.begin(), bucket.end(), num);
            if(loc == bucket.end())
                bucket.push_back(num);
            else
                *loc = num;
        }
        return bucket.size() >= 3;
    }
};

最坏情况下是O(n^2)

大佬的O(n)解法

small记录最小的那个数，mid记录中间的那个数

如果出现一个数大于mid，说明递增三元序列出现了，返回true

如果一个数大于small但小于等于mid，那么把mid替换为这个数，small和mid依旧可以构成一个递增序列，而且宽容度更高。

如果出现一个数小于small，就把small给替换掉

这里可以替换是因为在更新mid时，表明前面已经有个二元子序列了，也就是说mid本身就可以记录着一个二元子序列。

而更新后，可以使后面的宽容度加大，mid代表之前的一个序列，而small代表新的序列的开头，如果后面把mid给更新掉了，说明这个数比mid小，也就是说如果后面碰到一个数满足更新前的mid，这个数也必然满足更新后的mid。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int small = INT_MAX, mid = INT_MAX;
        for(auto num : nums)
        {
            if(num <= small)
                small = num;
            else if(num <= mid)
                mid = num;
            else 
                return true;
        }
        return false;
    }
};