Cinte's Leetcode Record
0%

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

384. 打乱数组

Fisher–Yates shuffle - Wikipedia

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
class Solution {
public:
    Solution(vector<int>& nums) : origin(nums), n(origin.size()) {

    }
    
    vector<int> reset() {
        return origin;
    }
    
    vector<int> shuffle() {
        vector<int> shuffled(origin);
        for(int i = 0; i < n; ++i)
        {
            int j = rand() % (n - i) + i;
            swap(shuffled[i], shuffled[j]);
        }
        return shuffled;
    }
private:
    vector<int> origin;
    int n;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * vector<int> param_1 = obj->reset();
 * vector<int> param_2 = obj->shuffle();
 */

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

395. 至少有 K 个重复字符的最长子串

对于一个字符串中计数长度<k的字符，他必定为分界，反之，当一个字符串中没有计数<k的字符，他就一定是符合条件的子串。

递归分治
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestSubstring(string s, int k) {
        return helper(s, 0, s.size() - 1, k);
    }
private:
    int helper(string& s, int lo, int hi, int k)
    {
        if(lo > hi)
            return 0;
        int memo[26]{ 0 };
        for(int i = lo; i <= hi; ++i)
            ++memo[s[i] - 'a'];
        for(int i = lo; i <= hi; ++i)
            if(memo[s[i] - 'a'] < k)
                return max(helper(s, lo, i - 1, k), helper(s, i + 1, hi, k));
        return hi - lo + 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int longestSubstring(string s, int k) {
        if(k == 1)
            return s.size();
        return helper(s, 0, s.size() - 1, k);
    }
private:
    int helper(string& s, int lo, int hi, int k)
    {
        if(lo > hi)
            return 0;
        int memo[26]{ 0 };
        bool split = false;
        for(int i = lo; i <= hi; ++i)
            ++memo[s[i] - 'a'];
        for(int i = lo; i <= hi; ++i)
            if(memo[s[i] - 'a'] < k)
            {
                split = true;
                break;
            }
        if(!split)
            return hi - lo + 1;
        int i = lo, start = lo;
        int ret = 0;
        while(i <= hi + 1)
        {
            if(i == hi + 1 || memo[s[i] - 'a'] < k)
            {
                ret = max(ret, helper(s, start, i - 1, k));
                start = i + 1;
            }
            ++i;
        }
        return ret;
    }
};
滑动窗口

对于每种子串的字符数进行枚举，如果当前字符数大于这个值，就移动左边界

维护一个less变量表示当前子串中还有几个个数未达到k。

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
class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.size();
        if(k == 1)
            return n;
        int ret = 0;
        for(int i = 1; i <= 26; ++i)
        {
            int memo[26]{ 0 };
            int total = 0;
            int less = 0;
            int begin = 0, end = 0;
            while(end < n)
            {
                if(++memo[s[end] - 'a'] == 1)
                {
                    ++total;
                    ++less;
                }
                if(memo[s[end] - 'a'] == k)
                    --less;
                while(total > i)
                {
                    if(--memo[s[begin] - 'a'] == 0)
                    {
                        --total;
                        --less;
                    }
                    if(memo[s[begin] - 'a'] == k - 1)
                        ++less;
                    ++begin;
                }
                if(less == 0)
                    ret = max(ret, end - begin + 1);
                ++end;
            }
        }
        return ret;
    }
};

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

28. 实现 strStr()

很暴力的匹配
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty())
            return 0;
        int n = haystack.size();
        int m = needle.size();
        for(int i = 0; i < n; ++i)
        {
            if(haystack[i] == needle[0])
            {
                int k = 1;
                for(; k < m && i + k < n && haystack[i + k] == needle[k]; ++k) {}
                if(k == m)
                    return i;
            }
        }
        return -1;
    }
};
kmp

回头看

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

326. 3的幂

递归
1
2
3
4
5
6
7
8
class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n < 3)
            return n == 1;    
        return n % 3 == 0 ? isPowerOfThree(n / 3) : false;
    }
};
循环
1
2
3
4
5
6
7
8
class Solution {
public:
    bool isPowerOfThree(int n) {
        while(n && n % 3 == 0)
            n /= 3;
        return n == 1;
    }
};
数学
1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};

在int范围内，3的幂的最大数是1162261467，且1162261467的所有约数都是3的幂，且包含所有情况，所以只需要判断n是不是1162261467的约束就可以

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

324. 摆动排序 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> A(nums.begin(), nums.begin() + (n + 1) / 2);
        vector<int> B(nums.begin() + (n + 1) / 2, nums.end());
        // 如果A,B中有重复数字的话，肯定是分别出现在A的结尾和B的开头，为了防止他们会合，必须让他们隔开来，所以2个都进行倒序遍历就可以隔开来了
        int pa = A.size() - 1, pb = B.size() - 1;
        for(int i = 0; i < n; i += 2)
        {
            nums[i] = A[pa--];
            if(pb >= 0)
                nums[i + 1] = B[pb--];
        }
    }
};

T(n): O(nlogn)

S(n): O(n)

快速选择+三分+穿插
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:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1)
            return;
        auto midPtr = nums.begin() + (n + 1) / 2;
        nth_element(nums.begin(), midPtr, nums.end());
        int midNum = *midPtr;
        int i = 0, j = 0, k = n - 1;
        // 因为nth_element只能使第n小的数字在n处，如果有重复数字的情况下，其他和中位数相等的数字是无法确定他们和中位数相邻的，所以需要进行三分，把原数组划为小于中位数，等于中位数，大于中位数三个部分。
        // i表示小于中位数的指针，j表示遍历用的指针，也指向中位数，k表示大于中位数部分的指针
        // 以下while表示三分算法，T(n)为O(n)
        // 所以当nums[j] > midNum时，说明j走到了大于中位数的区块，这时缓过来的nums[k]有可能还大于中位数，所以j不能++，要留给下一步再判断
        // 当nums[j] < midNum，说明j在小于中位数的区块行走，此时，当nums[j]等于中位数时，j会加一，而i停留，由此，所有小于中位数的数都会交换到前面，而等于中位数的数会逐渐被挤到中间。
        while(j < k)
        {
            if(nums[j] > midNum)
                swap(nums[j], nums[k--]);
            else if(nums[j] < midNum)
                // 这里j可以++是因为换过来的nums[i]必然是等于中位数的数，否则j和i就是同步走的了
                swap(nums[j++], nums[i++]);
            else
                ++j;
        }
        vector<int> A(nums.begin(), midPtr);
        vector<int> B(midPtr, nums.end());
        for(int i = A.size() - 1, j = 0; i >= 0; j += 2, --i)
            nums[j] = A[i];
        for(int i = B.size() - 1, j = 1; i >= 0; j += 2, --i)
            nums[j] = B[i];
    }
};

T(n) : O(n)

S(n): O(n)

nth_element进行自己的实现

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
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1)
            return;
        quickSort(nums, 0, n - 1, (n + 1) / 2);
        auto midPtr = nums.begin() + (n + 1) / 2;
        int midNum = *midPtr;
        int i = 0, j = 0, k = n - 1;
        while(j < k)
        {
            if(nums[j] > midNum)
                swap(nums[j], nums[k--]);
            else if(nums[j] < midNum)
                swap(nums[j++], nums[i++]);
            else
                ++j;
        }
        vector<int> A(nums.begin(), midPtr);
        vector<int> B(midPtr, nums.end());
        for(int i = A.size() - 1, j = 0; i >= 0; j += 2, --i)
            nums[j] = A[i];
        for(int i = B.size() - 1, j = 1; i >= 0; j += 2, --i)
            nums[j] = B[i];
    }
private:
    // 本质就是快速排列，然后只取一部分，所以舍去了
    void quickSort(vector<int>& nums, int lo, int hi, int n)
    {
        if(lo > hi)
            return;
        auto pivot = rand() % (hi - lo + 1) + lo;
        swap(nums[pivot], nums[lo]);
        int c = nums[lo];
        int i = lo, j = hi + 1;
        while(i < j)
        {
            while(i < hi && nums[++i] <= c) {}
            while(j > lo && nums[--j] >= c) {}
            if(i >= j)
                break;
            swap(nums[i], nums[j]);
        }
        swap(nums[lo], nums[j]);
        if(j < n)
            quickSort(nums, j + 1, hi, n);
        else if(j > n)
            quickSort(nums, lo, j - 1, n);
        else
            return;
    }
};

关于nth_element的时间复杂度分析

假设k次迭代终止，假设迭代平衡

T(n) = T(n / 2) + n = T(n / 4) + n / 2 + n...

当迭代次数趋于无穷的时候

T(n) = n

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

27. 移除元素

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int pt = 0;
        for(auto& num : nums)
            if(num != val)
                nums[pt++] = num;
        return pt;
    }
};

最坏情况下,pt也需要同时遍历一遍nums

考虑到题目中说元素的顺序可以改变，所以针对这一个条件进行优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0, right = nums.size(); // right需要设定为size而不是size-1,否则当只有一个数字时候不会进入循环
        // right比原来大一可以让left多走一步
        while(left < right)
        {
            if(nums[left] == val)
                nums[left] = nums[right-- - 1];
            else
                ++left;
        }
        return left;
    }
};

review

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if(nums.empty())
            return 0;
        int n = nums.size();
        int i = 0, j = n - 1;
        while(i <= j)
        {
            while(i <= j && nums[i] == val)
                swap(nums[i], nums[j--]);
            ++i;
        }
        return j + 1;
    }
};

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

804. 唯一摩尔斯密码词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int uniqueMorseRepresentations(vector<string>& words) {
        string code[26]{".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        unordered_set<string> set;
        for(auto& word : words)
        {
            string tmp;
            for(auto ch : word)
                tmp += code[ch - 'a'];
            set.emplace(tmp);
        }
        return set.size();
    }
};

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

328. 奇偶链表

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* oddEvenList(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* eh = even;
        ListNode* pt = even->next;
        while(pt)
        {
            odd->next = pt;
            odd = pt;
            pt = pt->next;
            if(!pt)
                break;
            even->next = pt;
            even = pt;
            pt = pt->next;
        }
        even->next = nullptr;
        odd->next = eh;
        return 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
/**
 * 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* oddEvenList(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* eh = even;
        // 因为先处理的是even->next，所以只要even->next非空，odd在下面就不会是空
        // 当长度为奇数时候，在最后一个循环中，odd会走到最末尾的节点，然后even->next就是nullptr
        // 当长度为偶数时候，在最后一个循环中，odd走到倒数第二个节点，然后even走到最后一个节点，这样的话even->next本来就是nullptr
        // 这里顺序不能调换，因为even是在odd后面的节点
        while(even && even->next)
        {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = eh;
        return head;
    }
};

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

26. 删除有序数组中的重复项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty())
            return 0;
        int point = 1, length = nums.size();
        for(int i = 1; i < length; ++i)
        {
            if(nums[i] == nums[i - 1])
                continue;
            nums[point++] = nums[i];
        }
        return point;
    }
};