Atopos's Blog

One step at a time!

0%

王牌面试学习计划[Leetcode 75]

发表于 更新于 分类于
本文字数： 14k 阅读时长 ≈ 13 分钟

day01：前缀和

题目1

一维数组的动态和

标签

数组、前缀和

题解

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        vector<int> arr;
        arr.push_back(nums[0]);
        for(int i = 1; i < nums.size(); i++){
            arr.push_back(arr[i - 1] + nums[i]);
        }
        return arr;
    }
};
  • 时间复杂度：O(n)，其中 n 为 nums 的大小
  • 空间复杂度：O(1)

执行用时：4 ms, 在所有 C++ 提交中击败了49.82%的用户

内存消耗：8.2 MB, 在所有 C++ 提交中击败了65.68%的用户

通过测试用例：53 / 53

题目2

寻找数组的中心下标

标签

数组、前缀和

思路

先求出前缀和数组，求解前可以将前缀和数组置为0，方便后续计算。遍历前缀和数组，i从1到n-1

  • 左边：arr[i] - arr[0]
  • 右边：arr[n - 1] - arr[i]

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        vector<int> arr;  // 保存前缀和
        arr.push_back(0);
        for(int i = 0; i < nums.size(); i++){
            arr.push_back(arr[i] + nums[i]);
        }
        int n = arr.size();
        for(int i = 1; i < arr.size(); i ++){
            int l = arr[i - 1] - arr[0];
            int r = arr[n - 1] - arr[i];
            if(l == r) return i - 1;
        }
        return -1;
    }
};
  • 时间复杂度：O(n)，其中 n 为 nums 的大小
  • 空间复杂度：O(n)，保存前缀和数组用到

执行用时：28 ms, 在所有 C++ 提交中击败了17.17%的用户

内存消耗：31.8 MB, 在所有 C++ 提交中击败了5.02%的用户

通过测试用例：745 / 745

day02：字符串

题目1

同构字符串

标签

字符串、哈希表

思路

使用哈希表unordered_map存储两个单词之间的映射关系即可。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, int> hsp;
        unordered_map<char, int> map;
        for(int i = 0; i < s.size(); i++){
            if(hsp[s[i]] == 0 && map[t[i]] == 0){
                hsp[s[i]] = t[i] - 'a' + 1;
                map[t[i]] = s[i] - 'a' + 1;
            }
            else if(hsp[s[i]] != t[i] - 'a' + 1 || map[t[i]] != s[i] - 'a' + 1){
                return false;
            }
        }
        return true;
    }
};
  • 时间复杂度：O(n)，其中 n 为 nums 的大小
  • 空间复杂度：O(2 \ n)*， 需要使用两个哈希表

执行用时：8 ms, 在所有 C++ 提交中击败了56.60%的用户

内存消耗：6.7 MB, 在所有 C++ 提交中击败了85.03%的用户

通过测试用例：43 / 43

题目2

判断子序列

标签

字符串、双指针、动态规划

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0;
        for(int j = 0; j < t.size(); j ++){
            if(i == s.size()) return true;
            else if(s[i] == t[j]){
                i ++;
            }
        }
        if(i == s.size()) return true;
        return false;
    }
};
  • 时间复杂度：O(n)，其中 n 为数组 t 的大小
  • 空间复杂度：O(1)

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.2 MB, 在所有 C++ 提交中击败了63.35%的用户

通过测试用例：17 / 17

day03：链表

题目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
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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *list = new ListNode(-1);
        ListNode *head = list;
        ListNode *p = list1;
        ListNode *q = list2;
        while(p && q){
            if(p -> val <= q -> val){
                ListNode *x = new ListNode(p->val);
                head->next = x;
                head = head->next;
                p = p->next;
            }
            else {
                ListNode *x = new ListNode(q->val);
                head->next = x;
                head = head->next;
                q = q->next;
            }
        }
        while(p){
            ListNode *x = new ListNode(p->val);
            head->next = x;
            head = head->next;
            p = p->next;
        }
        while(q){
            ListNode *x = new ListNode(q->val);
            head->next = x;
            head = head->next;
            q = q->next;
        }
        return list->next;
    }
};
  • 时间复杂度：O(n + m)，其中 n 为list1 的长度，m 是 list2 的长度
  • 空间复杂度：O(n + m)

执行用时：12 ms, 在所有 C++ 提交中击败了9.40%的用户

内存消耗：14.5 MB, 在所有 C++ 提交中击败了15.85%的用户

通过测试用例：208 / 208

题目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
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head; 
        ListNode* l = head;  // 指向头节点
        ListNode* r = head;  // 指向尾节点
        while(r->next){
            r = r->next;
        }
        ListNode* p = head;
        ListNode* q= head->next;
        ListNode* k = head->next->next;

        while(k){  // 节点指针反转
            q->next = p;
            p = q;
            q = k;
            k = k->next;
        }
        q->next = p; // 最后两个节点进行交换

        head = r;
        l ->next = nullptr;
        return head;

    }
};
  • 时间复杂度：O(n)，其中 n 为head 的长度
  • 空间复杂度：O(1)

执行用时：8 ms, 在所有 C++ 提交中击败了49.83%的用户

内存消耗：8 MB, 在所有 C++ 提交中击败了71.06%的用户

通过测试用例：28 / 28

day04：链表、双指针

题目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
/**
 * 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* middleNode(ListNode* head) {
        int nums = 0;
        ListNode *p = head;
        while(p){
            nums++;
            p = p->next;
        }
        int a = nums / 2;
        p = head;
        while(a --){
            p = p->next;
        }
        return p;
    }
};
  • 时间复杂度：O(n)，其中 n 为head 的长度
  • 空间复杂度：O(1)

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.8 MB, 在所有 C++ 提交中击败了81.83%的用户

通过测试用例：36 / 36

题目2

环形链表 II

标签

链表、哈希表、双指针

题解

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 *detectCycle(ListNode *head) {
        unordered_set<ListNode *> visited;
        while(head != NULL){
            if(visited.count(head)){
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        return NULL;
    }
};
  • 时间复杂度：O(n)，其中 n 为head 的长度
  • 空间复杂度：O(n)，使用哈希表

执行用时：16 ms, 在所有 C++ 提交中击败了8.32%的用户

内存消耗：9.4 MB, 在所有 C++ 提交中击败了6.32%的用户

通过测试用例：16 / 16

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:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr) {
            slow = slow->next;
            if (fast->next == nullptr) {
                return nullptr;
            }
            fast = fast->next->next;
            if (fast == slow) {
                ListNode *ptr = head;
                while (ptr != slow) {
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr;
    }
};
  • 时间复杂度：O(n)，其中 n 为head 的长度
  • 空间复杂度：O(1)

执行用时：8 ms, 在所有 C++ 提交中击败了73.20%的用户

内存消耗：7.3 MB, 在所有 C++ 提交中击败了97.45%的用户

通过测试用例：16 / 16

day05：

题目1

买卖股票的最佳时机

标签

数组、动态规划

题解

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int inf = 1e9;
        int minprice = inf, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};
  • 时间复杂度：O(n)，其中 n 为 prices 数组的大小
  • 空间复杂度：O(1)

执行用时：104 ms, 在所有 C++ 提交中击败了61.28%的用户

内存消耗：91 MB, 在所有 C++ 提交中击败了85.19%的用户

通过测试用例：211 / 211

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for(int i = 0; i < prices.size() - 1; i++){
            for(int j = i + 1; j < prices.size(); j++){
                res = max(res, prices[j] - prices[i]);
            }
        }
        return res;
    }
};
  • 时间复杂度：O(n ^ 2)，其中 n 为 prices 数组的大小
  • 空间复杂度：O(1)

执行用时：104 ms, 在所有 C++ 提交中击败了61.28%的用户

内存消耗：91 MB, 在所有 C++ 提交中击败了85.19%的用户

通过测试用例：211 / 211

题目2

最长回文串

标签

贪心、哈希表、字符串

题解

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:
    int longestPalindrome(string s) {
        unordered_map<char, int> hsp;
        for(int i = 0; i < s.size(); i++){
            hsp[s[i]] ++;
        }
        bool flag = false;
        int res = 0;
        for(unordered_map<char, int>::iterator it = hsp.begin(); it != hsp.end(); it++){
            if(it->second %  2!=0){
                flag = true;
                res += (it->second - 1);
            }
            else{
                res += it->second;
            }
        }
        if(flag) res += 1;
        return res;
    }
};
  • 时间复杂度：O(n)，其中 n 为 s 的大小
  • 空间复杂度：O(n)，用哈希表

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.6 MB, 在所有 C++ 提交中击败了14.52%的用户

通过测试用例：95 / 95

day06：树

题目1

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
34
35
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> res;
    void dfs(Node* root){
        if(root == NULL) return ;
        res.push_back(root->val);
        for(int i = 0; i < root->children.size(); i ++){
            dfs(root->children[i]);
        }
    }
    vector<int> preorder(Node* root) {
        dfs(root);
        return res;
    }
};
  • 时间复杂度：O(n)，其中 n 为N 叉树的节点，每个节点恰好被遍历一次。
  • 空间复杂度：O(n)

执行用时：16 ms, 在所有 C++ 提交中击败了67.73%的用户

内存消耗：11.1 MB, 在所有 C++ 提交中击败了82.02%的用户

通过测试用例：38 / 38

题目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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 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:
    queue<TreeNode*> que;
    vector<vector<int>> res;
    int num = 0;
    void dfs(TreeNode* root){
        if(que.empty()) return ; 
        vector<int> arr;
        int npc = 0;
        while(!que.empty() && num > 0){
            TreeNode* top = que.front();
            que.pop();
            num--;
            arr.push_back(top->val);
            if(top->left){
                que.push(top->left);
                npc ++;
            }
            if(top->right){
                que.push(top->right);
                npc ++;
            }
        }
        res.push_back(arr);
        num = npc;
        dfs(root);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr) return res;
        que.push(root);
        num ++;
        dfs(root);
        return res;
    }
};
  • 时间复杂度：O(n)，其中 n 为 2 叉树的节点，每个节点恰好被遍历一次。
  • 空间复杂度：O(n)，需要使用队列。

执行用时：8 ms, 在所有 C++ 提交中击败了22.90%的用户

内存消耗：12.9 MB, 在所有 C++ 提交中击败了8.27%的用户

通过测试用例：34 / 34

day07：二分查找

题目1

二分查找

标签

数组、二分查找

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = (l + r + 1) >> 1;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        if(nums[l] != target) return -1;
        return l;
    }
};
  • 时间复杂度：O(logn)，其中 n 为数组的长度
  • 空间复杂度：O(1)。

执行用时：20 ms, 在所有 C++ 提交中击败了98.15%的用户

内存消耗：26.9 MB, 在所有 C++ 提交中击败了54.09%的用户

通过测试用例：47 / 47

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target)
                r = mid;
            else
                l = mid + 1;
        }
        if(nums[l] != target) return -1;
        return l;
    }
};
  • 时间复杂度：O(logn)，其中 n 为数组长度
  • 空间复杂度：O(1)。

执行用时：48 ms, 在所有 C++ 提交中击败了7.34%的用户

内存消耗：27 MB, 在所有 C++ 提交中击败了5.73%的用户

通过测试用例：47 / 47

题目2

第一个错误的版本

标签

二分查找、交互

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while(l < r){
            int mid = (l >> 1) + (r >> 1);  //  防止计算时溢出，两个过大的数相加溢出
            if(isBadVersion(mid)) r = mid; 
            else l = mid + 1;
        }
        return l;
    }
};
  • 时间复杂度：O(logn)，其中 n 为给定版本的数量。
  • 空间复杂度：O(1)。

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：5.8 MB, 在所有 C++ 提交中击败了47.59%的用户

通过测试用例：23 / 23

day08：二叉搜索树⭐

题目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
/**
 * 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:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stack;
        long long inorder = (long long)INT_MIN - 1;

        while (!stack.empty() || root != nullptr) {
            while (root != nullptr) {
                stack.push(root);
                root = root -> left;
            }
            root = stack.top();
            stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root -> val <= inorder) {
                return false;
            }
            inorder = root -> val;
            root = root -> right;
        }
        return true;
    }
};
  • 时间复杂度：O(n)，其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次，因此时间复杂度为O(n)
  • 空间复杂度：O(n)，其中 n 为二叉树的节点个数。栈最多存储 n 个节点，因此需要额外的 O(n) 的空间。。

执行用时：4 ms, 在所有 C++ 提交中击败了97.63%的用户

内存消耗：21.1 MB, 在所有 C++ 提交中击败了59.44%的用户

通过测试用例：80 / 80

题目2

二叉搜索树的最近公共祖先

标签

树、深度优先搜索、二叉搜索树、二叉树

思路

题解思路

  • 二次遍历

每次遍历都记录从根节点到节点p或者节点q的路径。然后挨个比对，最后一个两个位置的节点相同的节点，则该节点是两个节点的公共祖先节点。

  • 一次遍历

题解

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
/**
 * 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<TreeNode *> findPath(TreeNode* root, TreeNode* target){
        vector<TreeNode* > path;
        TreeNode *node = root;
        
        while(node != target){
            path.push_back(node);
            if(node->val < target->val)
                node = node->right;
            else 
                node = node->left;
        }
        path.push_back(node);
        return path;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode *> path_p = findPath(root, p);
        vector<TreeNode *> path_q = findPath(root, q);
        TreeNode* res;
        for(int i = 0; i < path_p.size() && i < path_q.size(); i++){
            if(path_p[i] == path_q[i])
                res = path_p[i];
        }
        return res;
    }
};
  • 时间复杂度：O(n)，其中 n 为二叉搜索树中的节点个数。
  • 空间复杂度：O(n)，需要存储储根节点到 p 和 q 的路径。和上面的分析方法相同，在最坏的情况下，路径的长度为 Θ(n)，因此需要 Θ(n) 的空间。

执行用时：44 ms, 在所有 C++ 提交中击败了5.53%的用户

内存消耗：22.7 MB, 在所有 C++ 提交中击败了75.57%的用户

通过测试用例：27 / 27

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
/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* ancestor = root;
        while (true) {
            if (p->val < ancestor->val && q->val < ancestor->val) {
                ancestor = ancestor->left;
            }
            else if (p->val > ancestor->val && q->val > ancestor->val) {
                ancestor = ancestor->right;
            }
            else {
                break;
            }
        }
        return ancestor;
    }
};

作者：LeetCode-Solution
  • 时间复杂度：O(n)，其中 n 为二叉搜索树中的节点个数。
  • 空间复杂度：O(1)。

执行用时：28 ms, 在所有 C++ 提交中击败了66.76%的用户

内存消耗：22.6 MB, 在所有 C++ 提交中击败了98.27%的用户

通过测试用例：27 / 27

day09：Dfs/Bfs⭐

题目1

图像渲染

标签

深度优先搜索、广度优先搜索、数组、矩阵

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    // pass:初始[sr,sc]位置的值
    void dfs(vector<vector<int>>& image, int sr, int sc, int color, int pass){
        int r = image.size(), c = image[0].size();
        if(sr < 0 || sr >= r || sc < 0 || sc >= c || image[sr][sc] != pass){  //出口
            return ;
        }
        image[sr][sc] = color;
        dfs(image, sr + 1, sc, color, pass);
        dfs(image, sr - 1, sc, color, pass);
        dfs(image, sr, sc + 1, color, pass);
        dfs(image, sr, sc - 1, color, pass);
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if(image[sr][sc] == color) return image;
        dfs(image, sr, sc, color, image[sr][sc]);
        return image;
    }
};
  • 时间复杂度：O(n \ m)，其中 n 和 m* 分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。
  • 空间复杂度：O(1)，

执行用时：4 ms, 在所有 C++ 提交中击败了97.02%的用户

内存消耗：13.4 MB, 在所有 C++ 提交中击败了97.95%的用户

通过测试用例：277 / 277

题目2

岛屿数量

标签

深度优先搜索、广度优先搜索、并查集、数组、矩阵

题解

正在加载今日诗词....