Cinte's Leetcode Record
0%

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

剑指 Offer 56 - I. 数组中数字出现的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int x = 0, m = 1, n = 0;
        // 对于只有一个只出现一次的数字的情况，异或后结果就是那个值，而有两个的话，假设2个数字是x,y，则异或后结果为x^y
        for(auto& num : nums)
            n ^= num;
        // 设m为1，寻找x与y从左往右数不相同的第一个数字，异或中是相异为1，所以当m&n==1时，表示n的这位为1了，于是就找到了这个不相同的第一个数字，并保存到m
        while((m & n) == 0) // 注意 == 的优先级比 & 高
            m <<= 1;
        for(auto& num : nums)
        {
            if((num & m) == 0) // 当且仅当m为1的这一位的数字为1时，与的结果才为1，因此那两个单独的数字必定不可能同时通过这个if条件，所以将原数列分成了两个子序列
                x ^= num;
        }
        return {x, x ^ n}; // x ^ n = x ^ x ^ y = 0 ^ y = y
    }
};

优化技巧 

1
2
while((m & n) == 0)
    m <<= 1;
可以优化为 
1
m = n & (~n + 1);
~n将n的所有位取反，~n + 1则可以将~n的最低一个0变1，也就是把n的最低一个1标记出来，而其他的位~n保持与n相反，因此他们与之后的结果就是最低位的1保留，剩下全是0。

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

剑指 Offer 55 - I. 二叉树的深度

参考104. Maximum Depth of Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

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

剑指 Offer 51. 数组中的逆序对

用归并排序，顺便计算逆序对（tnl)
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:
    int reversePairs(vector<int>& nums) {
        merge(nums, 0, nums.size() - 1);
        return ret;
    }
private:
    int ret = 0;
    void merge(vector<int>& nums, int l, int r)
    {
        if(l >= r)
            return;
        int m = (l + r) >> 1; // 从中间截开来，划分
        merge(nums, l, m); // 递归排序左半边归并，排完后是从小到大的顺序
        merge(nums, m + 1, r); // 递归排序右半边归并，排完后是从小到大的顺序
        vector<int> tmp(nums.begin() + l, nums.begin() + r + 1); // 生成一个临时字符串，将排序区间内的内容复制进去
        int i = 0, j = m + 1 - l;
        for(int k = l; k <= r; ++k)
        {
            if(i == m + 1 - l) // 当i，也就是左半边的指针超过了中位数后，也就是说左半边元素用完了。那么把剩下的元素全都用右半边剩下的元素填充
                nums[k] = tmp[j++];
            else if(j == r + 1 - l) // 当右半边元素用完后，把剩下的空位全都用右半边元素填充
                nums[k] = tmp[i++];
            else if(tmp[i] <= tmp[j]) // 进行大小盘带按，填充较小的元素
                nums[k] = tmp[i++];
            else
            {
                nums[k] = tmp[j++]; // 填充较大的元素
                ret += m - i + 1 - l; // 当左边某个数>右边某个数时，由于左边序列是从小到大排列，那么左边从这个数到结尾的所有数与右边那个数都构成了逆序对，依次遍历。将所有逆序对加上。
            }
        }
    }
};
review
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:
    int reversePairs(vector<int>& nums) {
        aux = vector<int>(nums.size());
        sort(nums, 0, nums.size() - 1);
        return ret;
    }
private:
    vector<int> aux;
    int ret = 0;
    void sort(vector<int>& nums, int lo, int hi)
    {
        if(lo >= hi)
            return;
        int mid = lo + (hi - lo) / 2;
        sort(nums, lo, mid);
        sort(nums, mid + 1, hi);
        copy(nums.begin() + lo, nums.begin() + hi + 1, aux.begin() + lo); 
        int i = lo, j = mid + 1;
        for(int k = lo; k <= hi; ++k)
        {
            if(i > mid)
                nums[k] = aux[j++];
            else if(j > hi)
                nums[k] = aux[i++];
            else if(aux[i] <= aux[j]) // nums会在排序过程中改变，所以要用aux来比较
                nums[k] = aux[i++];
            else
            {
                nums[k] = aux[j++];
                ret += mid - i + 1;
            }
        }
    }
};

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

剑指 Offer 34. 二叉树中和为某一值的路径

BackTrack
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 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:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        vector<int> tmp;
        helper(root, target, 0, tmp);
        return ret;
    }
private:
    vector<vector<int>> ret;
    void helper(TreeNode* root, const int& target, int cur, vector<int>& tmp)
    {
        if(!root)
            return;
        cur += root->val;
        tmp.push_back(root->val);
        if(cur == target && !root->left && !root->right)
        {
            ret.push_back(tmp);
        }
        helper(root->right, target, cur, tmp);
        helper(root->left, target, cur, tmp);
        tmp.pop_back();
    }
};

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

剑指 Offer 50. 第一个只出现一次的字符

遍历两次
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    char firstUniqChar(string s) {
        int memo[26]{ 0 };
        for(auto& ch : s)
            memo[ch - 'a'] += 1;
        for(auto& ch : s)
            if(memo[ch - 'a'] == 1)
                return ch;
        return ' ';
    }
};
用vector记录插入的数据，在有大量重复的情况下会笔第一种快
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    char firstUniqChar(string s) {
        int memo[26]{ 0 };
        vector<char> v;
        for(auto& ch : s)
        {
            if(!memo[ch - 'a'])
                v.push_back(ch);
            memo[ch - 'a'] += 1;
        }
        for(auto& ch : v)
            if(memo[ch - 'a'] == 1)
                return ch;
        return ' ';
    }
};

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

剑指 Offer 33. 二叉搜索树的后序遍历序列

D&Q
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        return verify(postorder, 0, postorder.size() - 1);
    }
private:
    bool verify(vector<int>& nums, int i, int j)
    {
        if(i >= j)
            return true;
        int p = i;
        // 此处无需p<j这个条件，因为nums[j]==nums[j]，所以必定不会导致越界
        while(nums[p] < nums[j]) ++p;
        int m = p;
        while(nums[p] > nums[j]) ++p;
        return p == j && (verify(nums, i, m - 1) && verify(nums, m, j - 1));
    }
};

对于一个序列，根在最右边，然后左边的左半边是左子树，右半边是右子树，他们的分界就是左子树全小于根，右子树全大于根，所以只需要通过一个个判断，就可以判断出其中的左子树和右子树，再对子树递归就可以判断了

单调栈+倒序

真的难，还是没想透为什么不管升序要管降序

因为要找大于当前节点中最小的来做parent，所以使用单增栈

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
class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        stack<int> s;
        int parent = INT_MAX;
        for(int i = postorder.size() - 1; i >= 0; --i)
        {
            // 如果升序，压栈，倒序，那么这个节点肯定是某个节点的左节点
            while(!s.empty() && postorder[i] < s.top()) // 因为栈是递增的，所以找到一个刚刚好大于他本身的节点就是他的父亲节点。
            {
                parent = s.top();
                s.pop();
            }
            if(postorder[i] > parent)  
            // 注意这个parent只有在遇到递减数列时候才会赋值，那么有几种情况。
            1. 当当前节点是左子节点，那么parent是这个左子节点的父亲，由上面栈的关系必定可以保证。
            2. 当当前节点是右子节点，那么parent具有几种情况(在倒序情况下是根-右-左)
                1、parent是某个左子节点的父亲，那么他必定大于节点 
                2、往回走，栈逐渐压入，那么parent成为当前节点所在树的某个祖先节点，并且由后序遍历的顺序，这个树肯定在parent的左边。依旧必定大于节点
                return false;
            s.push(postorder[i]);
        }
        return true;
    }
};

SmartSelect_20220706-103930_Samsung Notes.jpg 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        stack<int> s;
        s.push(INT_MIN);
        int parent = INT_MAX;
        for(int i = postorder.size() - 1; i >= 0; --i)
        {
            while(postorder[i] < s.top())
            {
                parent = s.top();
                s.pop();
            }
            if(postorder[i] > parent)
                return false;
            s.push(postorder[i]);
        }
        return true;
    }
};

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

剑指 Offer 32 - III. 从上到下打印二叉树 III

双向队列
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        vector<vector<int>> ret;
        deque<TreeNode*> dq;
        bool left = false;
        dq.push_front(root);
        while(!dq.empty())
        {
            vector<int> tmp;
            for(int i = 0, j = dq.size(); i < j; ++i)
            {
                if(left)
                {
                    auto p = dq.back();
                    dq.pop_back();
                    tmp.push_back(p->val);
                    if(p->right)
                        dq.push_front(p->right);
                    if(p->left)
                        dq.push_front(p->left);
                }else
                {
                    auto p = dq.front();
                    dq.pop_front();
                    tmp.push_back(p->val);
                    if(p->left)
                        dq.push_back(p->left);
                    if(p->right)
                        dq.push_back(p->right);
                }
            }
            ret.push_back(tmp);
            left = !left;
        }
        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
51
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        vector<vector<int>> ret;
        deque<TreeNode*> dq;
        bool left = false;
        dq.push_front(root);
        while(!dq.empty())
        {
            vector<int> tmp2;
            for(int i = 0, j = dq.size(); i < j; ++i)
            {
                auto p = dq.front();
                dq.pop_front();
                tmp2.push_back(p->val);
                if(p->left)
                    dq.push_back(p->left);
                if(p->right)
                    dq.push_back(p->right);
            }
            ret.push_back(tmp2);
            if(dq.empty())
                break;
            vector<int> tmp;
            for(int i = 0, j = dq.size(); i < j; ++i)
            {
                auto p = dq.back();
                dq.pop_back();
                tmp.push_back(p->val);
                if(p->right)
                    dq.push_front(p->right);
                if(p->left)
                    dq.push_front(p->left);
            }
            ret.push_back(tmp);
        }
        return ret;

    }
};

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

剑指 Offer 44. 数字序列中某一位的数字

又是一道数学的找规律类型的题，好烦
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findNthDigit(int n) {
        long digit = 1, count = 9, start = 1;
        while(count < n)
        {
            n -= count;
            start *= 10;
            ++digit;
            count = 9 * digit * start;
        }
        // 0的时候直接计算出来是0，不会影响结果
        int num = (n - 1) / digit + start;
        return to_string(num)[(n - 1) % digit] - '0';
    }
};

1625218647824.png 1625218657922.png 1625218664563.png

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

189. Rotate Array

第三种方法太复杂了，只会第四种
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1); 
    }
private:
    void reverse(vector<int>& nums, int start, int end)
    {
        while(start < end)
            swap(nums[start++], nums[end--]);
    }
};
1
2
an=bk
b走的步长为k，所以走了一圈后b*k是n的倍数，所以需要求a
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if((k %= n) == 0)
            return;
        int count = gcd(n, k);
        for(int i = 0; i < count; ++i)
        {
            int prev = nums[i];
            int cur = i;
            do
            {
                int next = (cur + k) % n;
                swap(prev, nums[next]);
                cur = next;
            }while(cur != i);
        }
    }
};

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

剑指 Offer 32 - I. 从上到下打印二叉树

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        queue<TreeNode*> q;
        vector<int> ret;
        q.push(root);
        while(!q.empty())
        {
            auto p = q.front();
            q.pop();
            ret.push_back(p->val);
            if(p->left)
                q.push(p->left);
            if(p->right)
                q.push(p->right);
        }
        return ret;
    }
};