Leetcode-hot-100

Link:https://leetcode.cn/studyplan/top-100-liked/

此帖用来记录力扣上面hot100的解题思路，也借此复习下常见的数据结构和算法，巩固基础知识。
尽量使用多种语言解题，可以熟悉其他语言的语法。
同时也尽量使用多种方法解题，锻炼思维能力。

Link:https://leetcode.cn/studyplan/top-100-liked/

哈希

两数之和

哈希判断target-x在不在哈希表中即可

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        unordered_map<int, int> h;
        for(int i = 0; i<nums.size(); ++i){
            if(h.contains(target-nums[i]))
                return {i, h[target-nums[i]]};
            h[nums[i]] = i;
        }
        return {};
    }
};

字母异位词分解

哈希表存储字符串，需要支持hash运算符

最长连续序列

1.并查集有一点麻烦，特殊值0比较难搞

2.使用哈希的话，考虑如果x-1在哈希表中，就不用作为左端点，如果有答案的话，那么一定有他的x-1不存在的，以此为左端点，一直向右遍历，直到右端点不存在。

时间复杂度O(N), 每个元素最多遍历两次

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int ans{0};
        unordered_set<int> st(nums.begin(), nums.end());

        for(int x : st){
            if(st.contains(x-1)) continue;
            int l = x+1;
            while(st.contains(l)){
                l++;
            }
            ans = max(ans, (l-x));
        }
        return ans;
    }
};

双指针

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

双指针： 为了保持非0元素的相对顺序，我们这一题使用同向双指针

左边指针i寻找0，右边的指针j寻找非0，然后交换两者即可，这样可以保证非零元素的顺序，例如

0， 1， 2，0 ，0， 12

-> 0 和 1 交换 ： 1， 0， 2， 0， 0， 12

-> 0 和 2 交换： 1，2， 0， 0， 0， 12

-> i指向下表2的0， j一直往后找知道12不为0， 然后交换两者，就是最后的答案

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        if(n < 2) return;

        int i{0}, j{1};
        while(j < n){
            if(nums[i] == 0){
                while(j < n && nums[j] == 0) j++;
                if(j == n) break;
                swap(nums[i], nums[j]);
            }
            i++;
            j++;
        }
    }
};

盛水最多的容器

双指针经典例题：

左边柱子的高度写作L， 右边柱子的高度写作R

• 如果L和R相等， 更新完答案这两个柱子就都可以舍弃了，因为他们两个不会产生更大的答案了，为什么？因为比他们低的，不可能使答案更大，比他们大的也没有意义，木桶效应，所以两边都可以向内走
• 如果L更高，更新完答案舍弃右边的柱子，右边继续往前遍历有可能有更高的柱子使答案更优
• 如果R更高，和第二点同理，舍弃当前左边的柱子，继续向后遍历。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans{INT_MIN};
        int l{0}, r = height.size() - 1;
        while(l < r){
            ans = max(ans, min(height[l], height[r]) * (r-l));
            if(height[l] == height[r]){
                ++l;
                --r;
            }else if(height[l] < height[r]){
                ++l;
            }else {
                --r;
            }
        }
        return ans;
    }
};

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

思考过程：

1. 因为是求i+j+k = 0，所以如果我们固定一位的话，就变成两数之和的问题了，复杂度是O(n*n)
2. 固定哪一位呢？中间这一位？ 写完后发现解决重复答案比较难处理, [0, 0, 0, 0] 这个case
3. 固定第一位呢？可行，只要我们找到答案之后将j和k相同的元素都过滤掉，当前的i就不会有重复的答案了

思考过程：

1. 因为是求i+j+k = 0，所以如果我们固定一位的话，就变成两数之和的问题了，复杂度是O(n*n)
2. 固定哪一位呢？中间这一位？ 写完后发现解决重复答案比较难处理, [0, 0, 0, 0] 这个case
3. 固定第一位呢？可行，只要我们找到答案之后将j和k相同的元素都过滤掉，当前的i就不会有重复的答案了

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(begin(nums), end(nums));
        int n = nums.size();
        vector<vector<int>> ans;
        for(int k = 0; k<n-2; ++k){
            int i = k+1, j = n-1;;
            while(i < j){
                if(nums[i] + nums[j] > -nums[k]) --j;
                else if(nums[i] + nums[j] < -nums[k]) ++i;
                else {
                    ans.emplace_back(std::vector<int>{nums[i], nums[k], nums[j]});
                    while(i < j && nums[i+1] == nums[i]) ++i;
                    while(j > i && nums[j] == nums[j-1]) --j;
                    ++i;
                    --j;
                }
            }
             while(k < n -1 && nums[k] == nums[k+1]) k++;
             if(k >= n - 1) break;
        }
        return ans;
    }
};

接雨水

滑动窗口

无重复字符的最长子串

不定长滑动窗口

1.滑入窗口

2.是否造成条件不满足，不满足的话不停滑出左端口

3.满足条件更新答案

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans{0}, left{0};
        int cnt[128]{};
        for(auto i = 0u; i<s.size(); ++i){
            cnt[s[i]]++;
            while(cnt[s[i]] > 1){
                cnt[s[left++]]--;
            }
            ans = max(1u*ans, i-left + 1);
        }
        return ans;
    }
};

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

思路1：
我们需要从k个数字中快速拿到最大的数字，容易想到堆（优先队列），但是窗口前面的元素滑出去了怎么办，优先队列不支持删除指定元素，
这里我们可以借助一个map来做延迟删除，因为我们只有在添加答案之前才需要从队列中获取最大值，那么在这个时候取到的元素如果是要被删掉的，我们就删除队头，重新取，直到队头的元素是合法的，所以我们只需要用一个map记录下队列中剩余每个元素的数量即可。

运行耗时：150ms

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        using namespace std;
        priority_queue<int> q;
        unordered_map<int, int> mp;
        vector<int> ans(nums.size() - k + 1);
        int left = 0, right = 0, i = 0;

        for(; right < nums.size(); ++right) {
            q.push(nums[right]);
            mp[nums[right]]++;
            if(right - left + 1 < k) continue;
            while(1) {
                if(q.empty()) break;
                int t = q.top();
                if(mp[t] == 0) {
                    q.pop();
                }else{
                    break;
                }
            }
            //cout << left << " " << right << " " << q.size() << " " << mp[9] << endl;
            mp[nums[left++]] --;
            if(!q.empty())
              ans[i++] = q.top();
        }

        return ans;
    }
};

运行耗时：40ms

思路2：
解法一的常数会大一些，并且用了额外的数据结构存储信息。
有没有什么数据结构还能支持快速拿到最大值呢？
容易想到-单调栈，并且是单调递减（这里可以稍微思考下为什么？）
但是栈只能一端操作，如果我们要删除栈底的最大元素怎么办呢？ 支持双端操作的单调栈？
对，我们只需要用双端队列来模拟单调栈即可，这样，队列前面的元素（栈底的元素）也可以O（1）的删除。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        using namespace std;
        priority_queue<int> q;
        unordered_map<int, int> mp;
        vector<int> ans(nums.size() - k + 1);
        int left = 0, right = 0, i = 0;

        for(; right < nums.size(); ++right) {
            q.push(nums[right]);
            mp[nums[right]]++;
            if(right - left + 1 < k) continue;
            while(1) {
                if(q.empty()) break;
                int t = q.top();
                if(mp[t] == 0) {
                    q.pop();
                }else{
                    break;
                }
            }
            //cout << left << " " << right << " " << q.size() << " " << mp[9] << endl;
            mp[nums[left++]] --;
            if(!q.empty())
              ans[i++] = q.top();
        }

        return ans;
    }
};

找到字符串中所有字母异位词

定长滑动窗口

1.滑入窗口，直到达到窗口固定长度

2.判断当前窗口是否满足答案，满足则更新答案

3.滑出窗口最左边的元素，后面每次遍历对应一进一出

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans{};
        int n = s.size(), m = p.size();

        int left{0}, right{0};
        int cm[26]{};
        int nm[26]{};
        for(char ch : p) cm[ch-'a']++;
        for(; right<n; ++right){
            nm[s[right]-'a']++;
            if(right - left + 1 < m) continue;
            int j{0};
            for(; j<26; ++j){
                if(nm[j] != cm[j]) break;
            }
            if(j == 26) ans.push_back(left);
            nm[s[left++]-'a']--;
        }
        return ans;
    }
};

子串

和为K的子数组

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

前缀和，子数组是一段连续序列，所以k肯定是可以由一个从第一个元素开始的子数组的前缀和减去某段较短的前缀和得到的，所以我们可以维护一个哈希表，记录每个前缀和出现的次数，再维护一个从第一个元素开始累加的总和sum，如果sum-k出现在哈希表中，那么就可以组成答案了！

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int ans{0}, sum{0};
        unordered_map<int, int> h;
        h[0] = 1;
        for(int i = 0; i<n; ++i){
            sum += nums[i];
            ans += h[sum-k];
            ++h[sum];
        }
        return ans;
    }
};

图论

腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

思路：
类似二叉树的层序便利，一层一层往外扩展，每一天将前一天被污染的橘子都遍历一下，我们可以用队列来模拟。
这里用模板实现了一个简洁的队列。

template<class T>
class Queue{
public:
    struct Node{
        T val{};
        Node* next{nullptr};
        Node(const T& v = T{}) {
            val = v;
        }
    };

    Queue() {
        head = new Node();
        cur = head;
    }

    ~Queue() {
        delete head;
    }

    const T& front() const {
        return head->next->val;
    }

    void push(const T& v) {
        Node* node = new Node(v);
        cur->next = node;
        cur = cur->next;
        cnt++;
    }

    size_t size() const{
        return cnt;
    }

    void pop() {
        if(!size()) return;
        auto tmp = head->next;
        if(tmp == cur) {
            cur = head;
        }
        head->next = head->next->next;
        delete tmp;
        cnt--;
    }
    
    bool empty() {
        return cnt == 0;
    }
private:
    size_t cnt{0};
    Node* head{nullptr};
    Node* cur{nullptr};
};

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};
        
        Queue<pair<int, int>> q;
        int normal_org{0}, bad_org{0};
        int n = grid.size(), m = grid[0].size();
        for(int i = 0; i<n; ++i) {
            for(int j = 0; j<m; ++j) {
                if(grid[i][j] == 1) normal_org ++;
                if(grid[i][j] == 2) {
                    q.push({i, j});
                    bad_org ++;
                }
            }
        }

        int ans = 0;
        while(!q.empty()) {
            int now = q.size();
            int cur_normal_org = normal_org;
            while(now --) {
                const auto [x, y] = q.front();
                q.pop();
                for(int k = 0; k<4; ++k) {
                    int tx = x + dx[k];
                    int ty = y + dy[k];
                    if(tx < 0 || tx >= n || ty < 0 || ty >= m) continue;
                    if(grid[tx][ty] != 1) continue;
                    grid[tx][ty] = 2;
                    q.push({tx, ty});
                    normal_org --;
                }
            }
            if(cur_normal_org > normal_org)
                ans ++;
        }
        return normal_org != 0 ? -1 : ans;
    }
};

栈

有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

class Solution {
public:
    bool isValid(string s) {
        stack<char> sk;
        for(char ch : s){
            if(ch == ')'){
                if(sk.empty() || sk.top() != '(') return false;
                sk.pop();
            }else if(ch == ']'){
                if(sk.empty() || sk.top() != '[') return false;
                sk.pop();
            }else if(ch == '}'){
                if(sk.empty() || sk.top() != '{') return false;
                sk.pop();
            }else{
                sk.push(ch);
            }
        }
        if(!sk.empty()) return false;
        return true;
    }
};

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

辅助最小栈，维护一个从栈底到栈顶非递增的序列，这样getmin就是这个辅助栈的栈顶元素了

辅助最小栈，维护一个从栈底到栈顶非递增的序列，这样getmin就是这个辅助栈的栈顶元素了

class MinStack {
    stack<int> sk;
    stack<int> min_sk;
public:
    MinStack() {
        
    }
    
    void push(int val) {
        sk.push(val);
        if(min_sk.empty()){
            min_sk.push(val);
            return ;
        }
        if(val <= min_sk.top()){
            min_sk.push(val);
        }
    }
    
    void pop() {
        int t = sk.top();
        sk.pop();
        if(t == min_sk.top()){
            min_sk.pop();
        }
    }
    
    int top() {
        return sk.top();
    }
    
    int getMin() {
        return min_sk.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

链表

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

思路
如果我们知道两个链表的长度a和b，
那么长度较长的链表先从头结点向后移动max(a, b)-min(a, b)步，
然后两个节点一起向后移动，他们到达末尾的时间是一样的，如果在移动的过程中他们同时指向了一个内存，那就是有交点。

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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lena := 0
    tmpa := headA
    for tmpa != nil {
        tmpa = tmpa.Next
        lena ++
    }
    lenb := 0
    tmpb := headB
    for tmpb != nil {
        tmpb = tmpb.Next
        lenb ++
    }
    tmpa = headA
    tmpb = headB
    need_to_go := max(lena, lenb) - min(lena, lenb)

    if lena > lenb {
        for need_to_go > 0 {
            tmpa = tmpa.Next
            need_to_go--
        }
    }else{
        for need_to_go > 0 {
            tmpb = tmpb.Next
            need_to_go --
        }
    }

    for tmpa != nil && tmpb != nil {
        if tmpa == tmpb {
            return tmpa
        }
        tmpa = tmpa.Next
        tmpb = tmpb.Next
    }
    return nil
}

合并k个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

根据数据范围，我们可以想到用优先队列来处理，把每个链表的头放在小根堆中，
每次都将队头元素放入到队列中，如果当前加入队头元素还有下一个元素，将其将入队列中排序。
一直到队列为空，一定遍历了所有的链表节点。

时间复杂度： O(NLogm) N为所有链表节点数之和， m为lists的长度即链表的个数
空间复杂度： O(m), 堆中一开始保存了m个节点

/**
 * 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* mergeKLists(vector<ListNode*>& lists) {
        using namespace std;
        struct cmp {
            bool operator()(const ListNode* l, const ListNode* r) const {
                if(nullptr == l || nullptr == r) return false;
                return l->val > r->val;
            }
        };
        priority_queue<ListNode*, std::vector<ListNode*>, cmp> q;
        
        ListNode tmp{};
        ListNode* new_head = &tmp;
        ListNode* cur = new_head;
        for(auto& i : lists) {
            if(!i) continue;
            q.push(i);
        }
        while(!q.empty()) {
            ListNode* tmp = q.top();
            q.pop();
            if(tmp->next) {
                q.push(tmp->next);
            }
            cur->next = tmp;
            cur = cur->next;
        }
        return new_head->next;
    }
};