Cinte's Leetcode Record
0%

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

剑指 Offer 35. 复杂链表的复制

参考138. Copy List with Random Pointer

建立新节点和老节点的映射
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 a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> map;
        Node* pre = new Node(0);
        Node* pseudoHead = pre;
        while(head)
        {
            auto node = new Node(head->val);
            pre->next = node;
            map[head] = node;
            pre = node;
            head = head->next;
        }
        for(auto& it : map)
        {
            if(it.first->random)
                it.second->random = map[it.first->random];
            else
                it.second->random = nullptr;
        }
        return pseudoHead->next;
    }
};

换个写法

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 Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* cur = head;
        unordered_map<Node*, Node*> map;
        while(cur)
        {
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        while(cur)
        {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        return map[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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)
            return nullptr;
        auto cur = head;
        while(cur)
        {
            auto next = cur->next;
            cur->next = new Node(cur->val);
            cur->next->next = next;
            cur = next;
        }
        cur = head;
        while(cur)
        {
            if(cur->random)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        cur = head;
        auto newL = head->next;
        auto ret = newL;
        while(newL->next)
        {
            cur->next = cur->next->next;
            newL->next = newL->next->next;
            cur = cur->next;
            newL = newL->next;
        }
        cur->next = nullptr;
        return ret;
    }
};

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

剑指 Offer 18. 删除链表的节点

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode* pre = new ListNode();
        ListNode* ret = pre;
        pre->next = head;
        while(head)
        {
            if(head->val == val)
            {
                pre->next = head->next;
                return ret->next;
            }
            pre = head;
            head = head->next;
        }
        return ret->next;
    }
};

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

剑指 Offer 24. 反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
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;
    }
};

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

剑指 Offer 19. 正则表达式匹配

虽然做过 但还是难

参考10. Regular Expression Matching

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
        dp.back().back() = true;
        for(int i = s.size(); i >= 0; --i)
        {
            for(int j = p.size() - 1; j >= 0; --j)
            {
                bool firstMatch = i < s.size() && (s[i] == p[j] || p[j] == '.');  // 空串是不可能和正则中的值匹配的，所以i==s.size()时匹配始终失败
                if(j <= p.size() - 2 && p[j + 1] == '*')
                    dp[i][j] = dp[i][j + 2] || (firstMatch && dp[i + 1][j]); // 这里可以处理到空串的情况
                else
                    dp[i][j] = firstMatch && dp[i + 1][j + 1];
            }
        }
        return dp[0][0];
    }
};

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

剑指 Offer 16. 数值的整数次方

二分法O(logn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    double myPow(double x, int n) {
        double ret = 1;
        long b = static_cast<long>(n);
        if(b < 0)
        {
            b = -b;   // 先反转成全是正数
            x = 1/x;  // 基准
        }
        while(b)
        {
            if(b & 1)
                ret *= x;  // 如果次数为奇数 那么先乘一个x, 如果结束前的一次迭代b = 2，那么会进入1，如果b = 1，那此时已经进入了，最后b=0时，因为0次方=1，所以没影响。
            x *= x; // 转为x^2
            b >>= 1; // 转为n/2
            // 操作过后 基准变为x^2，x^2成为了下一个x，而n/2成为了下一个n，由此迭代
        }
        return ret;
    }
};

当输入的次数n为奇数时

\[ X^n=X*(X^2)^{n/2}\]

当输入的次数n为偶数时

\[ X^n=(X^2)^{n/2}\]

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

剑指 Offer 22. 链表中倒数第k个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* runner = head, *walker = head;
        for(int i = 0; i < k; ++i)
            runner = runner->next;
        while(runner)
        {
            walker = walker->next;
            runner = runner->next;
        }
        return walker;
    }
};

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

剑指 Offer 15. 二进制中1的个数

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while(n)
        {
            ret += n & 1;
            n >>= 1;
        }
        return ret;
    }
};
骚方法（太优秀了
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while(n)
        {
            ++ret;
            n &= (n - 1);
        }
        return ret;
    }
};
1624447689192.png

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

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

首尾
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int end = nums.size() - 1;
        for(int i = 0; i < end; ++i)
        {
            while(i < end && nums[i] % 2 == 0)
                swap(nums[i], nums[end--]);
        }
        return nums;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int begin = 0, end = nums.size() - 1;
        while(begin < end)
        {
            if(nums[begin] & 1)
                ++begin;
            else if(!(nums[end] & 1))
                --end;
            else
                swap(nums[begin], nums[end]);
        }
        return nums;
    }
};
快慢
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        // 慢指针用来记录可以放奇数的位置，快指针用来搜索后面的所有奇数，如果是奇数，就把他换到前面去
        int walker = 0, runner = 0;
        while(runner < nums.size())
        {
            if(nums[runner] & 1)
                swap(nums[walker++], nums[runner]); // 从walker换过来是奇数是不可能的，因为之前已经处理过了
            ++runner;
        }
        return nums;
    }
};

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

剑指 Offer 20. 表示数值的字符串

常规思路
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
61
62
63
64
65
66
67
68
69
class Solution {
public:
    bool isNumber(string s) {
        int start = 0, end = s.size() - 1;
        while(start < end && s[start] == ' ')
            ++start;
        while(end > start && s[end] == ' ')
            --end;
        if(start > end)
            return false;
        if(s[start] == '+' || s[start] == '-')
            ++start;
        bool isMeetDigital = false;
        bool isMeetDot = false;
        bool isMeetE = false;
        for(int i = start; i <= end; ++i)
        {
            if(isDigital(s[i]))
            {
                isMeetDigital = true;
            }
            else if(s[i] == '.' && !isMeetDot)
            {
                if(isMeetE)
                    return false;
                isMeetDot = true;
                if(!isMeetDigital)
                {
                    if(i >= end)
                        return false;
                    else if(!isDigital(s[++i]))
                        return false;
                    else
                        isMeetDigital = true;
                }
            }else if(s[i] == 'e' || s[i] == 'E')
            {
                if(!isMeetDigital)
                    return false;
                if(!isMeetE)
                {
                    bool isSigned = false;
                    while(i < end && (s[++i] == '+' || s[i] == '-'))
                    {
                        if(isSigned)
                            return false;
                        isSigned = true;
                    }
                    if(i <= end && isDigital(s[i]))
                    {
                        isMeetE = true;
                        isMeetDigital = true;
                    }
                    else
                        return false;
                }else
                    return false;
            }
            else
                return false;
        }
        return true;
    }
private:
    bool isDigital(char& ch)
    {
        return ch <= '9' && ch >= '0';
    }
};
状态机

1624440075950.png 1624440089788.png

太烦了 不想做