Hot100总结

215. 数组中的第K个最大元素

利用堆或者sort进行排序

可以直接利用Cpp当中的优先级队列即最大堆，或者将数组排序后取就行，不过实现的时间复杂度为 $O(nlogn)$,不符合题目要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> que;
        for(int num:nums){
            que.push(num);
        }
        for(int i=0;i<k-1;i++){
            que.pop();
        }
        return que.top();
    }
};

快速选择

首先理解一下快速排序，如下代码为最简版的快排代码(取数组第一个元素作为基准，分为左右两个数组，逐渐递归当数组长度为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
#include <iostream>
#include <vector>
using namespace std;

vector<int> quickSort(vector<int>& nums) {
    if (nums.size() <= 1) return nums; // 递归出口

    int pivot = nums[0];  // 基准
    vector<int> left, right;

    // 分区
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] < pivot)
            left.push_back(nums[i]);
        else
            right.push_back(nums[i]);
    }

    // 递归排左右
    vector<int> sortedLeft = quickSort(left);
    vector<int> sortedRight = quickSort(right);

    // 合并结果
    sortedLeft.push_back(pivot);
    sortedLeft.insert(sortedLeft.end(), sortedRight.begin(), sortedRight.end());

    return sortedLeft;
}

int main() {
    vector<int> nums = {5, 2, 9, 1, 5, 6};
    vector<int> result = quickSort(nums);

    for (int num : result) cout << num << " ";
    return 0;
}

如果要实现原地分区的操作，需要用到双指针来进行操作(先设置指针i为-1，j为0，取pivot为数组最后一个数，将j从0遍历到pivot前一个,途中如果数字小于pivot就将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
31
32
33
34
35
36
#include <iostream>
#include <vector>
using namespace std;

// 分区函数
int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right];  // 选择最后一个元素作为基准
    int i = left - 1;         // i 表示小于 pivot 的区间的最后一个位置

    for (int j = left; j < right; j++) {
        if (nums[j] < pivot) {
            i++;
            swap(nums[i], nums[j]); // 把小的放到前面
        }
    }
    swap(nums[i + 1], nums[right]); // 最后把 pivot 放到正确位置
    return i + 1;  // 返回 pivot 的索引
}

// 快排函数
void quickSort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int pivotIndex = partition(nums, left, right); // 得到基准索引
        quickSort(nums, left, pivotIndex - 1);  // 排左边
        quickSort(nums, pivotIndex + 1, right); // 排右边
    }
}

int main() {
    vector<int> nums = {5, 2, 9, 1, 5, 6};
    quickSort(nums, 0, nums.size() - 1);

    for (int num : nums) cout << num << " ";
    return 0;
}

与快速排序不同，本题可以直接先将数组分区，接着让大于基准的分区长度与k进行比较从而进行挑选，编写函数quickselect，其作用是选取数组当中第k大的元素。

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 {
private:
    int quickselect(vector<int>&nums, int k){
        int pivot = nums[rand() % nums.size()];
        vector<int> small;
        vector<int> equal;
        vector<int> large;
        for(int num:nums){
            if(num>pivot){
                large.push_back(num);
            }
            else if(num==pivot){
                equal.push_back(num);
            }
            else{
                small.push_back(num);
            }
        }
        if(large.size()>=k){
            return quickselect(large,k);
        }
        else if(k>large.size()+equal.size()){
            return quickselect(small,k-large.size()-equal.size());
        }
        else{
            return pivot;
        }
    }

public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickselect(nums,k);
    }
};

169. 多数元素（摩尔投票）

本题可以用哈希表统计法或者排序后取中点的方法，他们的时间复杂度和空间复杂度分别为 $O(n)$ 和 $O(n)$，以及 $O(nlogn)$ 和 $O(1)$.

其中哈希表实现的代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> umap;
        for(int num:nums){
            umap[num]++;
        }
        int max_value = -INT_MAX;
        int result = 0;
        for(auto &[k,v]:umap){
            if(v>max_value){
                result = k;
                max_value = v;
            }
        }
        return result;
    }
};

若需要实现时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$,需要采用摩尔投票算法，算法原理：首先选第一个元素作为众数，从头开始遍历，若遇到与众数相同的数，则count++，不同则count–，当count为0时并且当前数不同时，result变为当前数，count置为1.

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 majorityElement(vector<int>& nums) {
        int count = 0;
        int result = nums[0];
        for(int i=0;i<nums.size();i++){
            if(nums[i]==result){
                count++;
            }
            else{
                if(count==0){
                    result = nums[i];
                    count = 1;
                }
                else{
                    count--;
                }
            }
        }
        return result;
    }
};

238. 除自身以外数组的乘积

若使用两个for循环会超时，且不能用除法来得到结果，题目要求时间复杂度为 $O(n)$，可以通过前缀后缀积来进行求解，比如有10个元素，要求第3个元素的ans，可以先得到1-2个元素的积以及右侧4-10个元素的积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n,1); //前缀积，left[i]表示下标为i前面的数字的积（不包括i)，i的范围为0到n-1
        vector<int> right(n,1); //后缀积,right[i]表示下表为i后面的数字的积
        vector<int> ans;
        for(int i=1;i<n;i++){
            left[i] = nums[i-1]*left[i-1];
        }
        for(int i = n-2;i>=0;i--){
            right[i] = nums[i+1]*right[i+1];
        }
        for(int i=0;i<n;i++){
            ans.push_back(left[i]*right[i]);
        }
        return ans;
    }
};

如果需要将空间复杂度优化，则直接将left作为ans数组即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n,1);
        for(int i=1;i<n;i++){
            ans[i] = nums[i-1]*ans[i-1];
        }
        int right = 1;
        for(int i = n-1;i>=0;i--){
            ans[i] *=right;
            right*=nums[i];
        }
        return ans;
    }
};

148. 排序链表（归并排序）

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表，同时要求时间复杂度为 $O(nlogn)$, 空间复杂度 $O(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
class Solution {
public:
    ListNode* sortList(ListNode* head) { //这个递归函数的输入为头节点，返回头节点，输入的链表进行排序
        if(!head || !head->next) return head; //递归函数的终止条件，当链表的节点只有一个或者没有时返回
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next&&fast->next->next){  //寻找链表的中间节点
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* second = slow->next; //第二条链表的头为中间节点的下一个节点
        slow->next = nullptr; //切断链表
        first = sortList(head);  // first为左边排序好的链表
        second = sortList(second); //second为右边排序号的链表
        ListNode* result = merge(first,second); //将两个有序链表进行组合，当为两个单独节点时，就可以将其进行排序
        return result;
    }
    ListNode* merge(ListNode* first,ListNode* second){ //合并两个有序链表 leetcode21.合并两个有序链表
        ListNode* dummy_head = new ListNode(0);
        ListNode* tail = dummy_head;
        while(first!=nullptr&&second!=nullptr){
            if(first->val<second->val){
                tail->next = first;
                first = first->next;
            }
            else{
                tail->next = second;
                second = second->next;
            }
            tail = tail->next;
        }
        if(first){
            tail->next = first;
        }
        if(second){
            tail->next = second;
        }
        return dummy_head->next;
    }
};

136. 只出现一次的数字(位运算)

题目要求用常量空间以及线性时间复杂度，因为排除实用哈希表。采用异或来进行计算，由于异或对于相同数字运算后为0，并且由于异或可以进行交换律，因此所有相同的两个数字都会运算为0，剩下的数字和0进行异或，最终结果就是答案。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for(int num:nums){
            result^=num;
        }
        return result;
    }
};

中心扩展法

对于判断回文串问题，一般来说需要 $O(n)$时间复杂度，暴力遍历每一个字串，需要$O(n^2)$ 的时间复杂度，总体上来说就是 $O(n^3)$，太慢了。

对于子串 abcba，最左边和最右边的字母都是 a，如果明确中间的 bcb 是回文串，那么我们就能 $O(1)$ 地知道 abcba 是回文串。对于子串 bcb 来说，最左边和最右边的字母都是 b，如果中间的 c 是回文串，那么我们就能 $O(1)$ 地知道 bcb 是回文串。显然 c 是回文串，所以 bcb 是回文串，所以 abcba 是回文串。

5. 最长回文子串

可以编写一个函数，记录中心的left和right，对于奇数回文串，选择一个点，对于偶数串，可以选取两个点。遍历每一个点作为中心，将其作为中心时的最长串进行比较，首先奇偶进行比较，然后在与全局长度进行比较，最终得到结果。

特别注意，当记录最长回文串时，其起始位置start不管是奇数还是偶数的结果都是一样的，都是当前中心减去(len-1)/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
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n<=1) return s;
        
        int start = 0;
        int maxlen = 1;

        for(int i=0;i<n;i++){
            int len1 = expand(s,i,i); //奇数
            int len2 = expand(s,i,i+1); //偶数长度中心
            int len = max(len1,len2);
            if(len>maxlen){
                maxlen = len;
                start = i - (len-1)/2;
            }
        }
        return s.substr(start,maxlen);
    }

    int expand(string& s,int left,int right){
        int L = left;
        int R = right;
        int n = s.size();
        while(L>=0&&R<n&&s[L]==s[R]){
            L--;
            R++;
        }
        return R-L-1;
    }
};

647. 回文子串

与上题相同，只不过每一次中心扩展的时候，分别记录以点i为中心时的奇串和偶串当中回文串的数目，将其加起来则可以得到以点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
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        if(n==1) return 1;
        int cnt = 0;
        for(int i=0;i<n;i++){
            int cnt1 = expand(s,i,i);
            int cnt2 = expand(s,i,i+1); 
            cnt +=cnt1;
            cnt +=cnt2;
        }
        return cnt;
    }

    int expand(const string& s,int left,int right){
        int n = s.size();
        int count = 0;
        int L = left;
        int R = right;
        while(L>=0&&R<n&&s[L]==s[R]){
            count++;
            L--;
            R++;
        }
        return count;
    }
};

128. 最长连续序列

本题要求时间复杂度为 $O(n)$,因此无法使用排序算法以及堆实现排序的方法。因此可以用哈希表来进行查找。

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 longestConsecutive(vector<int>& nums) {
        if(nums.size()==0) return 0;
        unordered_set<int> uset;
        for(int num:nums){
            uset.insert(num);
        }
        int result = 0;
        for(int cur:uset){  //需要遍历set而不是nums，若一个数组的第一个序列元素有很多如[1,1,1,1,1,1,1,1,1,2,3,4]，则需要多次判断，会超时
            if(uset.find(cur-1)==uset.end()){ //这一步很重要，对于每一个cur需要判断他是不是起始点，不然复杂度会退化到n^2
                int len = 1;
                while(uset.find(cur+1)!=uset.end()){
                    len++;
                    cur++;
                }
                result = max(result,len);
            }
        }
        return result;
    }
};

438. 找到字符串中所有字母异位词(滑动窗口)

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
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if(s.size()<p.size()) return {};
        vector<int> result;
        vector<int> count(26,0);
        vector<int> win_count(26,0);
        for(char c:p){
            count[c-'a']++;
        }
        for(int i=0;i<p.size();i++){
            win_count[s[i]-'a']++;
        }
        int left = 0;
        int right = p.size()-1;
        while(right!=s.size()-1){
            if(win_count==count) result.push_back(left);
            win_count[s[left]-'a']--;
            left++;
            right++; //需要先把窗口移过去
            win_count[s[right]-'a']++;
        }
        if (win_count == count) result.push_back(left);
        return result;
    }
};

437. 路径总和 III(双dfs||哈希表+前缀和)

先写一个dfs递归函数，他的作用为:返回从node节点出发(必须包含node),路径和等于目标的路径数目。

因此对于经过node的路径，若node本身等于目标，则路径+1，结果在加上以node->left为起点以及right为起点出发的路径数，三者和为目前节点出发的总路径数。

但是答案需要返回的是所有满足的路径，可以不包含根节点，因此需要得到以所有节点出发的路径数目和。因此最后的结果为（以root节点出发的路径数）+（以root->left为节点出发以及其下所有节点出发的路径数）+（以root->right为节点出发以及其下所有节点出发的路径数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
private:
    int dfs(TreeNode* node,long long target){ //以node节点出发的路径数目
        if(node==nullptr) return 0;
        int cnt = 0;
        if(node->val==target) cnt++; //node单一节点
        int left = dfs(node->left,target-node->val); //以node出发左边的
        int right = dfs(node->right,target-node->val);
        cnt+=left;
        cnt+=right;
        return cnt;
    }
public:
    int pathSum(TreeNode* root, int targetSum) {
        if(root==nullptr) return 0;
        return dfs(root,targetSum) + pathSum(root->left,targetSum) + pathSum(root->right,targetSum);
    }
};

560. 和为 K 的子数组（哈希表+前缀和）

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> umap;
        umap[0] = 1; // 前缀和为0出现一次，处理从头开始的子数组情况
        int pre = 0, count = 0;

        for (int num : nums) {
            pre += num; // 当前前缀和
            if (umap.find(pre - k) != umap.end()) {
                count += umap[pre - k];
            }
            umap[pre]++; // 记录当前前缀和
        }

        return count;
    }
};

239.滑动窗口的最大值(单调队列)

比如对于[2,1,4,2,3,2]，k=3的输入，首先当i>=2即k-1时开始将结果加入到res当中

i=0时，队列为空，将下标i=0加入，当i=1时，nums[1]=1，小于2，因此可以将其加入到队列尾部(因为我们不确定i>1后面的数字是不是一直递减的，如果一直递减，则1一定会成为最大值)

当i=2,即nums[2]=4时，将队列中下标对应的2和1全部pop(),将i=2加入队列。以此类推，队列头部的下标对应的数字一定大于后面的数字。

队列当中保存下标的原因：当遍历到i的位置可以和目前队列头部的下标直接比较，当距离超出窗口长度时，可以直接将队列头部的下标pop()

随后不断将队列头部的结果push到结果当中即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> res;
        for(int i=0;i<nums.size();i++){
            while(!dq.empty()&&nums[dq.back()]<nums[i]) dq.pop_back(); //使队列单调
            dq.push_back(i);
            if(i-k>=dq.front()){  //当队列头部下标没被窗口包括时将其pop
                dq.pop_front();
            }
            if(i>=k-1){ //当长度到达后开始push结果
                res.push_back(nums[dq.front()]);
            }
        }
        return res;
    }
};

封面

封面