Cinte's Leetcode Record
0%

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

1545. 找出第 N 个二进制字符串中的第 K 位

\[ len_n = len_{n-1} * 2 + 1 \\ = (len_{n - 2} * 2 + 1) * 2 + 1 \\ = ... \\ = ((len_1 * 2 + 1) * 2 + 1) * 2... \\ = 2^{n - 1} + 1 + 2 * 1 + 2 * 2 * 1 + ... 2^{n - 2} \\ = 2^{n - 1} + \frac{1*(1 - 2^{n - 1})}{1 - 2} \\ = 2^{n - 1} + 2^{n - 1} - 1 \\ = 2^n - 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
class Solution {
public:
    // S_n的长度为2^n - 1，因此S_n是由2^(n - 1) - 1 + 1 + 2^(n - 1) - 1构成的。所以中间放'1'的地方是2^(n-1)
    char findKthBit(int n, int k) {
        // 当k为1时，恒为0，如果没有这一行，当n = 1,k = 1时会判定为1
        if(k == 1)
            return '0';
        // 中间值，是当前字符串放'1'的位置
        int mid = 1 << (n - 1);
        if(mid == k)
            return '1';
        else
        {
            // 如果k<mid，在前半字符串中递归搜索
            if(k < mid)
                return findKthBit(n - 1, k);
            else
                // 如果k > mid，在前半字符串的反转中搜索，等效为将k变换后搜索新的k
                return invert(findKthBit(n - 1, mid * 2 - k));
        }
    }
private:
    char invert(char ch)
    {
        return (char)('1' - ch + '0'); // 虽然条件传送可以避免后续步骤中的分支预测错误惩罚，但当前分支依旧会有惩罚，因此使用算数运算可以避免这种分支预测错误带来的惩罚。
        // return ch == '0' ? '1' : '0';
    }
};

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

881. 救生艇

如果最轻的人可以和任何人配对，那么它也可以和最重的人配对。而如果不行，那最重的人无论如何都只能一个人做了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int begin = 0, end = people.size() - 1;
        int ret = 0;
        while(begin <= end) // 当相等时表示最后只有1个人了，无论什么情况都需要再加一艘船。
        {
            if(people[begin] + people[end] <= limit)
                ++begin;
            --end;
            ++ret;
        }
        return ret;
    }
};

最重的走的时候，如果能带，一定要带个人走，这才是合理的，否则，例如【1,3】，limit = 4，这种，3先自己坐船走，1只能再乘一条船。显然不合理。 那最终的走的时候，带谁走呢，显然是最轻的（当然他也可能能够次轻的同乘一条船），反证下，如果因为它带了最轻的，导致次轻的无法跟其他人同船，那么次轻的也一定无法跟最重的乘船。如果次轻的可以跟其他人同船，则反正同船了，跟谁效果都一样。所以 不会因为最重的选择了最轻的同船，导致后面的配对结果更坏。

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

231. 2 的幂

非正数的整数和0一定不是2的幂

正数的整数中只有2进制只有一个1才是2的幂

1
2
3
4
5
6
7
8
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n <= 0)
            return false;
        return (n & (n - 1)) == 0; // 也可以使用 n & (-n) == n，因为-n在计算机中表示为取反再加一
    }
};

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

122. 买卖股票的最佳时机 II

如果之前持有股票，那今天可以卖出或者不卖出。卖出后状态变为今天没持有股票。

如果之前没有股票，今天可以买入或不买入，买入就变成了今天持有了股票。

dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int have = -prices[0];
        int nothave = 0;
        int sz = prices.size();
        for(int i = 1; i < sz; ++i)
        {
            auto price = prices[i];
            have = max(have, nothave - price);
            nothave = max(have + price, nothave); // 这里之所以不用怕have受到上面的have影响是因为。假如受到了影响，就说明nothave-price比have要大，所以nothave要大于have+price，而此时have+price=nothave,所以不会影响结果
        }
        return nothave;
    }
};
直接计算所有的上坡，贪心
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ret = 0;
        int sz = prices.size();
        for(int i = 0; i < sz - 1; ++i)
            ret += max(prices[i + 1] - prices[i], 0);
        return ret;
    }
};

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

89. 格雷编码

挨个遍历，傻方法

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:
    vector<int> grayCode(int n) {
        if(n == 0)
            return { 0 };
        vector<int> ret{ 0 };
        vector<int> set(1 << n, 0);
        set[0] = 1;
        helper(n, ret, set);
        return ret;
    }   
private:
    void helper(int n, vector<int>& ret, vector<int>& set)
    {
        if(ret.size() == 1 << n)
            return;
        int preNum = ret.back();
        for(int i = 0; i < n; ++i)
        {
            auto tmp = preNum ^ (1 << i);
            if(!set[tmp])
            {
                set[tmp] = 1;
                ret.push_back(tmp);
                helper(n, ret, set);
            }
        }
    }
};
大佬的仙法

镜像构造

贴题解

Gray Code （镜像反射法，图解） - 格雷编码 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> grayCode(int n) {
        int head = 1;
        vector<int> ret{ 0 };
        for(int i = 1; i <= n; ++i)
        {
            for(int j = ret.size() - 1; j >= 0; --j) // 倒序是为了确保相邻只有一个不同
                ret.push_back(ret[j] ^ head);
            head <<= 1;
        }
        return ret;
    }
};
公式

格雷码的每一位

B是指正常的二进制编码

G(i) = Bi ^ (Bi + 1)换言之就是G(i) = Bi ^ (Bi >> 1)

对于一位如此，对于所有位都如此。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ret;
        for(int i = 0; i < (1 << n); ++i)
            ret.push_back(i ^ (i >> 1));
        return ret;
    }
};

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

61. 旋转链表

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
/**
 * 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* rotateRight(ListNode* head, int k) {
        if(!head)
            return nullptr;
        int length = 0;
        ListNode* point = head;
        ListNode* tail = nullptr;
        while(point)
        {
            ++length;
            tail = point;
            point = point->next;
        }
        k %= length;
        if(!k)
            return head;
        k = length - k - 1;
        point = head;
        for(int i = 0; i < k; ++i)
        {
            point = point->next;
        }
        auto ret = point->next;
        point->next = nullptr;
        tail->next = head;
        return ret;
    }
};

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

316. 去除重复字母

前置知识：

​ 对于一个字符串，如果要从中去除一个字符使得字符串的字典序最小。那么需要去除的是最靠左边的一个s[i] > s[i + 1]的字符串，因为最前面的最字典序影响最大。这个s[i]称为关键字符。

本题不能打乱原来的顺序，且每个字母只出现一次，因为所需的是从头开始遍历，处理遍历到的所有的关键字符。

维护一个栈

  1. 当栈顶>当前字符时候，删除栈顶。但是因为每个字母都要出现一次，因此当后面这个栈顶字母不再出现时，就不能删除。
  2. 当栈顶<当前字符时候，压入栈，但由于不能重复，所以如果栈中已有同个字符，就不压入。
  3. 当相等时，不能压入，因为不能重复。

为什么要用栈呢

为了维护字符间以及字符删除后的相邻关系以及字符删除后继续维持原来的顺序，栈是一个非常适合的数据结构。

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
class Solution {
public:
    string removeDuplicateLetters(string s) {
        int visited[26]{ 0 };
        int num[26]{ 0 };
        int sz = s.size();
        for(auto& ch : s)
            ++num[ch - 'a'];
        stack<char> st;
        for(auto& ch : s)
        {
            if(!visited[ch - 'a']) // 如果前面有了，就不加了，加入假设前面这个万一会被丢掉，那现在加的也绝对会被丢，如果前面那个是个有效的，那说明现在这个一定会被丢，因为肯定重复或者构成了逆序。
            {
                while(!st.empty() && st.top() > ch && num[st.top() - 'a'] != 1)
                {
                    --num[st.top() - 'a'];
                    visited[st.top() - 'a'] = 0;
                    st.pop();
                }
                st.push(ch);
                visited[ch - 'a'] = 1;
            }else // 直接错过了都没机会去栈里待待
                --num[ch - 'a'];
        }
        string ret(st.size(), ' ');
        int index = st.size() - 1;
        while(!st.empty())
        {
            ret[index--] = st.top();
            st.pop();
        }
        return ret;
    }
};

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

43. 字符串相乘

字符串加法模拟出字符串乘法
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
class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1.size() > num2.size())
            swap(num1, num2);
        string ret = "";
        for(int i = num1.size() - 1; i >= 0; --i)
        {
            int c = 0;
            int x = num1[i] - '0';
            string tmp;
            for(int b = num2.size() - 1; b >= 0; --b)
            {
                int t = (num2[b] - '0') * x + c;
                tmp += char(t % 10 + '0');
                c = t / 10;
            }
            if(c != 0)
                tmp += char(c + '0');
            while(tmp.size() > 1 && tmp.back() == '0')
                tmp.pop_back();
            reverse(tmp.begin(), tmp.end());
            num2 += '0';
            ret = add(ret, tmp);
        }
        return ret;
    }
private:
    string add(string& num1, string& num2)
    {
        int c = 0;
        int a = num1.size() - 1, b = num2.size() - 1;
        string ret;
        while (a >= 0 || b >= 0 || c)
        {
            int i = 0;
            if(a >= 0)
                i += num1[a--] - '0';
            if(b >= 0)
                i += num2[b--] - '0';
            i += c;
            c = i / 10;
            i %= 10;
            ret += char(i + '0');
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};
转成数组存储每一位的计算结果，最后把数组转成字符串

c++中字符串可以直接当作数组 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0") // 如果有0，返回0
            return "0";
        int m = num1.size(), n = num2.size();
        string ret(m + n, '0'); // 乘积大小不会大于m+n位，具体看题解的证明
        for(int i = m - 1; i >= 0; --i)
            for(int j = n - 1; j >= 0; --j)
            {
                int tmp = (num1[i] - '0') * (num2[j] - '0') + ret[i + j + 1] - '0';
                ret[i + j + 1] = tmp % 10 + '0'; // 第i位和第j位的两个字符串乘法结果到第i+j+1位上
                ret[i + j] = (ret[i + j] - '0' + tmp / 10) + '0'; // 进位存在前一位，由于是从大到小处理，所以不用担心溢出，后续会处理。
            }
        // 去掉开头0
        for(int i = 0; i < m + n; ++i)
            if(ret[i] != '0') 
                return ret.substr(i, m + n - i);
        return "0";
    }
};

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

415. 字符串相加

效率很低的模拟方法
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:
    string addStrings(string num1, string num2) {
        int c = 0;
        int a = num1.size() - 1, b = num2.size() - 1;
        string ret;
        while (a >= 0 && b >= 0)
        {
            int i = num1[a--] + num2[b--] - '0' - '0' + c;
            c = i / 10;
            i %= 10;
            ret = char(i + '0') + ret;
        }
        while (c != 0 && (a >= 0 || b >= 0))
        {
            int i;
            if (a >= 0)
                i = num1[a--] - '0' + c;
            else
                i = num2[b--] - '0' + c;

            c = i / 10;
            i %= 10;
            ret = char(i + '0') + ret;
        }
        if (c != 0)
            ret = char(c + '0') + ret;
        if (a >= 0 || b >= 0)
            ret = a >= 0 ? num1.substr(0, a + 1) + ret : num2.substr(0, b + 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
class Solution {
public:
    string addStrings(string num1, string num2) {
        int c = 0;
        int a = num1.size() - 1, b = num2.size() - 1;
        string ret;
        while (a >= 0 || b >= 0 || c)
        {
            int i = 0;
            if(a >= 0)
                i += num1[a--] - '0';
            if(b >= 0)
                i += num2[b--] - '0';
            i += c;
            c = i / 10;
            i %= 10;
            ret += char(i + '0');
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

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

109. 有序链表转换二叉搜索树

转为数组后再转

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
/**
 * 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) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> nodes;
        while(head)
        {
            nodes.push_back(head->val);
            head = head->next;
        }
        return build(nodes, 0, nodes.size() - 1);
    }
private:
    TreeNode* build(vector<int>& nodes, int lo, int hi)
    {
        if(lo > hi)
            return nullptr;
        auto mid = lo + ((hi - lo) >> 1);
        TreeNode* node = new TreeNode(nodes[mid]);
        node->left = build(nodes, lo, mid - 1);
        node->right = build(nodes, mid + 1, hi);
        return node;
    }
};

T(n) : O(n)

S(n) : O(n) + O(logn)(递归栈)

直接使用链表
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
/**
 * 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) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        return build(head, nullptr);
    }
private:
    TreeNode* build(ListNode* begin, ListNode* end)
    {
        // 如果mid的右边没有元素，那是不可能的，因为这说明walker走到了最右边，不可能
        // 如果mid的右边只有一个元素，在下次取右半边时候，由于取mid—>next，则右边会返回nullptr
        // 如果右边两个元素及以上，正常走
        // 如果左边没有元素，则下一回合左边begin==end，返回nullptr
        // 如果左边只有一个，下一回合会取左边那个元素，然后下一回合后的符合上述的情况
        // 如果左边两个元素及以上，正常走
        if(begin == end)
            return nullptr;
        auto mid = getMid(begin, end);
        TreeNode* node = new TreeNode(mid->val);
        node->left = build(begin, mid);
        // 重点处理 : 由于当begin和end相邻时会倾向于取begin这个元素，所以为了避免重复取，需要使mid右移一个。
        node->right = build(mid->next, end);
        return node;
    }
    // 借用链表取下一个元素方便的特性，设置为左闭右开，即无论什么情况下都不可能取到最右边的元素。
    ListNode* getMid(ListNode* begin, ListNode* end)
    {
        ListNode* walker = begin;
        ListNode* runner = begin;
        while(runner != end && runner->next != end)
        {
            runner = runner->next->next;
            walker = walker->next;
        }
        return walker;
    }
};

T(n) : O(nlogn)

S(n) : O(logn)(递归栈)

中序遍历+填充
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
/**
 * 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) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        return build(head, 0, getLength(head) - 1);
    }
private:
    int getLength(ListNode* head)
    {
        int ret = 0;
        for(; head; ++ret, head = head->next);
        return ret;
    }
    TreeNode* build(ListNode*& head, int lo, int hi)
    {
        if(lo > hi)
            return nullptr;
        auto mid = lo + (hi - lo) / 2;
        TreeNode* node = new TreeNode();
        node->left = build(head, lo, mid - 1);
        node->val = head->val;
        head = head->next;
        node->right = build(head, mid + 1, hi);
        return node;
    }
};