Cinte's Leetcode Record
0%

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

135. 分发糖果

两次遍历，先从左往右再从右往左。

从左往右遍历时候保证了只要是当前得分大于他左边的得分，他的值就会比他左边的大。从右往左，当遇见当前得分大于右边得分时候，对当前的值判断，如果本身就符合，那就无所谓，如果不符合，就是max(右边+1,本身)，所以不会破坏左边遍历的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> nums(n);
        nums[0] = 1;
        for(int i = 1; i < n; ++i)
            nums[i] = ratings[i] > ratings[i - 1] ? nums[i - 1] + 1 : 1;
        for(int i = n - 2; i >= 0; --i)
            if(ratings[i] > ratings[i + 1] && nums[i] <= nums[i + 1])
                nums[i] = nums[i + 1] + 1;
        return accumulate(nums.begin(), nums.end(), 0);
    }
};

O(1)空间复杂度

看题解

递减序列中就层层叠高。

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 candy(vector<int>& ratings) {
        int pre = 1, inc = 1 , dec = 0, ret = 1; // 要假设一开始是在升序的
        for(int i = 1, n = ratings.size(); i < n; ++i)
        {
            if(ratings[i] >= ratings[i - 1])
            {
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1; // 相等时候其实没影响，既不会像当前>左边导致当前要比左边高，也不会像当前>右边使得当前必须抬高来容纳右边
                ret += pre;
                inc = pre;
                dec = 0;
            }else
            {
                ++dec;
                if(dec == inc) // 不然再抬高就要把之前升序的末尾给超过了
                    ++dec;
                ret += dec;
                pre = 1; // 降序的末尾永远是1
            }
        }
        return ret;
    }
};

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

455. 分发饼干

排序后贪婪

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int i = 0, j = 0;
        int m = g.size(), n = s.size();
        while(j < n && i < m)
        {
            if(s[j] >= g[i])
                ++i;
            ++j;
        }
        return i;
    }
};

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

368. 最大整除子集

看题解

根据传递性，如果我能除以一个整除子集中的最大，那么其他所有的我都可以整除。

f[i]表示以下标i结尾的中的最长，g记录着每步的转移，g[i]=j，即这个序列走到i时候是有以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
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> f(n);
        vector<int> g(n);
        int maxSize = 1;
        int idx = 0;
        for(int i = 0; i < n; ++i)
        {
            int len = 1, prev = i;
            for(int j = 0; j < i; ++j)
            {
                if(nums[i] % nums[j] == 0 && f[j] + 1 > len)
                {
                    len = f[j] + 1;
                    prev = j;
                }
            }
            if(len > maxSize)
            {
                maxSize = len;
                idx = i;
            }
            f[i] = len;
            g[i] = prev;
        }
        vector<int> ret;
        for(int i = 0; i < maxSize; ++i)
        {
            ret.push_back(nums[idx]);
            idx = g[idx];
        }
        return ret;
    }
};

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

423. 从英文中重建数字

看题解

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:
    string originalDigits(string s) {
        int map[26]{ 0 };
        for(auto ch : s)
            ++map[ch - 'a'];
        int cnt[10];
        cnt[0] = map['z' - 'a'];
        cnt[6] = map['x' - 'a'];
        cnt[2] = map['w' - 'a'];
        cnt[8] = map['g' - 'a'];
        cnt[4] = map['u' - 'a'];
        cnt[5] = map['f' - 'a'] - cnt[4];
        cnt[3] = map['h' - 'a'] - cnt[8];
        cnt[7] = map['v' - 'a'] - cnt[5];
        cnt[1] = map['o' - 'a'] - cnt[0] - cnt[2] - cnt[4];
        cnt[9] = map['i' - 'a'] - cnt[5] - cnt[6] - cnt[8];
        string ret;
        for(int i = 0; i < 10; ++i)
            for(int j = 0; j < cnt[i]; ++j)
                ret += i + '0';
        return ret;
    }
};

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

67. 二进制求和

模拟

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 addBinary(string a, string b) {
        int m = a.size(), n = b.size();
        int i = m - 1, j = n - 1;
        string ret;
        int c = 0;
        while(i >= 0 && j >= 0)
        {
            int sum = a[i--] - '0' + b[j--] - '0' + c;
            c = sum / 2;
            ret += sum % 2 + '0';
        }
        while(c)
        {
            int sum;
            if(i >= 0)
                sum = a[i--] - '0' + c;
            else if(j >= 0)
                sum = b[j--] - '0' + c;
            else
                sum = c;
            c = sum / 2;
            ret += sum % 2 + '0';
        }
        reverse(ret.begin(), ret.end());
        if(i >= 0)
            ret = a.substr(0, i + 1) + ret;
        if(j >= 0)
            ret = b.substr(0, j + 1) + ret;
        return ret;
    }
};

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

594. 最长和谐子序列

排序后滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findLHS(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int begin = 0, end = 1, n = nums.size();
        int ret = 0;
        while(end < n)
        {
            while(nums[end] - nums[begin] > 1)
                ++begin;
            if(nums[end] - nums[begin] != 0)
                ret = max(ret, end - begin + 1); 
            ++end;
        }
        return ret;
    }
};

O(NlogN)

哈希表，把x和x+1的出现个数加上去，厉害啊

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> map;
        int ret;
        for(auto num : nums)
            ++map[num];
        for(auto [num, time] : map)
            if(map.count(num + 1))
                ret = max(ret, time + map[num + 1]);
        return ret;
    }
};

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

397. 整数替换

记忆化搜索

如果替换成vector，vector需要n的空间，不行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int integerReplacement(int n) {
        if(n == 1)
            return 0;
        if(memo[n])
            return memo[n];
        int tmp;
        if(n & 1)
            tmp = min(integerReplacement(n / 2), integerReplacement(n / 2 + 1)) + 2; // 重点，看解释
        else
            tmp = integerReplacement(n / 2) + 1;
        memo[n] = tmp;
        return tmp;
    }
private:
    unordered_map<int, int> memo;
};

时间复杂度：O(logn) 空间复杂度: O(logn)

原因在于这里每一步都会将原数/2

上述重点语句。对于n为奇数来说，n-1和n+1都必然会带来一个偶数，如果是偶数就不是1而且只能除以2，所以把这个操作合并为一次完成就是(n-1)/2或(n+1)/2。

但是考虑到溢出的问题，由于(n-1)/2就是n/2向下取整，而(n+1)/2就是n/2向上取整，因此他们可以表示为n/2和n/2+1。

dp超内存，空间复杂度是O(N)

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

318. 最大单词长度乘积

位运算来判断是否有重复数字

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 maxProduct(vector<string>& words) {
        int n = words.size();
        vector<int> memo;
        memo.reserve(n);
        size_t ret = 0;
        for(auto& str : words)
        {
            int tmp = 0;
            for(auto ch : str)
                tmp |= 1 << (ch - 'a');
            memo.push_back(tmp);
        }
        for(int i = 0; i < n; ++i)
            for(int j = 1 + 1; j < n; ++j)
                if((memo[i] & memo[j]) == 0)
                    ret = max(ret, words[i].size() * words[j].size());
        return ret;
    }
};

O(n^2 + 所有字符串长度)

优化空间，记录有相同字母的字符串的最大长度

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 maxProduct(vector<string>& words) {
        int n = words.size();
        unordered_map<int, int> memo;
        int ret = 0;
        for(auto& str : words)
        {
            int tmp = 0;
            for(auto ch : str)
                tmp |= 1 << (ch - 'a');
            memo[tmp] = max(memo[tmp], int(str.size()));
        }
        for(auto i = memo.begin(); i != memo.end(); ++i)
        {
            auto j = i;
            ++j;
            for(; j != memo.end(); ++j)
                if((i->first & j->first) == 0)
                    ret = max(ret, i->second * j->second);
        }
        return ret;
    }
};

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

143. 重排链表

切成前半部分和后半部分，后半部分反转

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
/**
 * 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:
    void reorderList(ListNode* head) {
        ListNode* walker = head, *runner = head;
        ListNode* pre = nullptr;
        while(runner->next && runner->next->next) 
        {
            walker = walker->next;
            runner = runner->next->next;
        }  
        auto l1 = walker->next;
        walker->next = nullptr;
        while(l1)
        {
            auto next = l1->next;
            l1->next = pre;
            pre = l1;
            l1 = next;
        }
        runner = head;
        while(pre)
        {
            auto next = runner->next;
            runner->next = pre;
            auto t = pre->next;
            pre->next = next;
            pre = t;
            runner = next;
        }
    }
};

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

319. 灯泡开关

迭代

1
2
3
4
5
6
class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n + 0.5);
    }
};

看官解