DailyPractice.2023.10.12

1.[1. 两数之和]

1. 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        if (nums.size() == 0) return {0,0};
        unordered_map<int,int> mp;
        for (int i = 0; i < nums.size(); i++) {
            auto it = mp.find(target - nums[i]);
            if (it != mp.end()) {
                return {it -> second,i};
            }
            mp[nums[i]] = i;
        }
        return {-1,-1};

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

2.[49. 字母异位词分组]

49. 字母异位词分组

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 遍历每个字符串，对于每个字符串，得到该字符串所在的一组字母异位词的标志，将当前字符串加入该组字母异位词的列表中。
        // 遍历全部字符串之后，哈希表中的每个键值对即为一组字母异位词。

        vector<vector<string>> res;
        unordered_map<string,vector<string>> mp;
        if (strs.size() == 0) return res;
        for (auto str : strs) {
            string key = str;
            sort(key.begin(),key.end());
            mp[key].push_back(str);
        }
        for (auto it = mp.begin(); it != mp.end(); it ++) {
            res.emplace_back(it -> second);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 时间复杂度：$O(nklogk)$，其中 n是 strs中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串，对于每个字符串，需要 O(klog⁡k)的时间进行排序以及 O(1)的时间更新哈希表，因此总时间复杂度是 O(nklog⁡k)。

• 空间复杂度：$O(nk)$，其中 n 是 strs 中的字符串的数量，k 是 strs中的字符串的的最大长度。需要用哈希表存储全部字符串。

3.[128. 最长连续序列]

128. 最长连续序列

// 对于匹配的过程，暴力的方法是 O(n) 遍历数组去看是否存在这个数，但其实更高效的方法是用一个哈希表存储数组中的数，这样查看一个数是否存在即能优化至 O(1) 的时间复杂度
// 那么怎么判断是否跳过呢？由于我们要枚举的数 x 一定是在数组中不存在前驱数x−1的，不然按照上面的分析我们会从 x−1 开始尝试匹配，因此我们每次在哈希表中检查是否存在 x−1即能判断是否需要跳过了。
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> mp;
        if (nums.size() == 0) return 0;
        for (const int& num : nums) {
            mp.insert(num);
        }
        int longest = 0;
        for (auto num : mp) {
            if (!mp.count(num - 1)) {
                int curNum = num;
                int curStreak = 1;
                while (mp.count(curNum + 1)) {
                    curNum += 1;
                    curStreak += 1;
                }
                longest = max(longest,curStreak);
            }
            
        }
        return longest;
    }
};
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

• 时间复杂度：$O(n)$，其中 n 为数组的长度。具体分析已在上面正文中给出。
• 空间复杂度：$O(n)$，哈希表存储数组中所有的数需要$O(n)$的空间。

4.[283. 移动零]

283. 移动零
两次遍历：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        if(nums.size() == 0) return;
        int fast = 0,slow = 0;
        while (fast < nums.size()) {
            if (nums[fast] != 0) {
                nums[slow ++] = nums[fast];
            }
            fast ++;
        }
        for (int i = slow; i < nums.size(); i++) {
            nums[i] = 0;
        }
       
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

一次遍历：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        // 注意到以下性质：
        // 左指针左边均为非零数；
        // 右指针左边直到左指针处均为零。
        // 因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。
        // 非0，交换数据，左右指针都往右移
        // 0，右指针右移
        int n = nums.size(),left = 0,right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left ++],nums[right]);
            }
            right ++;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

5.[11. 盛最多水的容器]

11. 盛最多水的容器

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0,j = height.size() - 1;

        // S(i,j) = min(h[i],h[j]) * (j - i);

        // 在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 −1 变短：
        // 因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。
        int res = 0;
        while (i < j) {
            res = height[i] < height[j] ?
                max(res,(j - i) * height[i ++]) :
                 max(res,(j - i) * height[j --]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 时间复杂度：$O(N)$,双指针遍历一次底边宽度 N。
• 空间复杂度：$O(1)$,变量 i , j , res 使用常数额外空间。

6.[15. 三数之和]

15. 三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        if (nums.size() == 0) return res;
        for (int k = 0; k < nums.size() - 2; k ++) {
            if (nums[k] > 0) break;
            if (k > 0 && nums[k] == nums[ k - 1]) continue;
            int i = k + 1,j = nums.size() - 1;
            while (i < j) {
                int sum = nums[k] + nums[i] + nums[j];
                if (sum < 0) {
                    while (i < j && nums[i] == nums[++i]);
                }
                else if(sum > 0) {
                    while (i < j && nums[j] == nums[--j]);
                }
                else {
                    res.push_back(vector<int>{nums[k], nums[i], nums[j]});
                    while(i < j && nums[i] == nums[++i]);
                    while(i < j && nums[j] == nums[--j]);
                }
            }
        }
        return res;
    }
};
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

• 时间复杂度：$O(N^2)$,其中固定指针k循环复杂度$O(N)$，双指针 i，j 复杂度 $O(N)$
• 空间复杂度：$O(1)$,指针使用常数大小的额外空间。

7.[3. 无重复字符的最长子串]

3. 无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> dic;
        int i = -1, res = 0, len = s.size();
        for (int j = 0; j < len; j ++) {

            // 哈希表 dic 统计： 指针 j 遍历字符 s ，哈希表统计字符 s[j] 最后一次出现的索引 。
            if (dic.find(s[j]) != dic.end()) {
                i = max(i,dic.find(s[j]) -> second);
            }
            dic[s[j]] = j; // 哈希表记录
            res = max(res, j - i); // 更新结果
        }
        return res;
        //时间复杂度 O(N) ： 其中 N 为字符串长度.
        //空间复杂度 O(1) ： 字符的 ASCII 码范围为 000 ~ 127 ，哈希表 dic 最多使用 O(128)=O(1)大小的额外空间。

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 时间复杂度 O(N) ： 其中 N 为字符串长度.
• 空间复杂度 O(1) ： 字符的 ASCII 码范围为 000 ~ 127 ，哈希表 dic 最多使用 O(128)=O(1)大小的额外空间。

8.[206. 反转链表]

206. 反转链表

/**
 * 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) return nullptr;
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* temp = nullptr;
        while (cur) {
            temp = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};
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

• 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。

• 空间复杂度：O(1)。

9.[141. 环形链表]

141. 环形链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head -> next == nullptr) {
            return false;
        }
        // 理解成公倍数，两个正整数一定会有一个最小公倍数，这个地方就是重合点
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast && fast -> next) {
            fast = fast -> next -> next;
            slow = slow -> next;
            if (slow == fast) 
            return true;
        }
         return false;
    }
};
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

• 时间复杂度：O(N)，其中 N是链表中的节点数。
  当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
  当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。

• 空间复杂度：O(1)。我们只使用了两个指针的额外空间。

10.[160. 相交链表]

160. 相交链表

考虑构建两个节点指针 A​ , B 分别指向两链表头节点 headA , headB ，做如下操作：

指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：
a+(b−c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：
b+(a−c)

如下式所示，此时指针 A , B 重合，并有两种情况：
若两链表 有 公共尾部 (即 c>0) ：指针 A , B 同时指向「第一个公共节点」node 。
若两链表 无 公共尾部 (即 c=0 ) ：指针 A , B 同时指向 null 。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr) return headB;
        if (headB == nullptr) return headA;
        ListNode* p1 = headA;
        ListNode* p2 = headB;
        while (p1 != p2) {
            if (p1 == nullptr) p2 = headB;
            else p1 = p1 -> next;
            if (p2 == nullptr) p1 = headA;
            else p2 = p2 -> next;
        }
        return p1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 时间复杂度 O(a+b) ： 最差情况下（即 ∣a−b∣=1| , c=0 ），此时需遍历 a+b个节点。
• 空间复杂度 O(1)) ： 节点指针 A , B 使用常数大小的额外空间。