力扣算法题解笔记

15. 三数之和

方法：双指针法
关键点：
i 去重：检查 nums[i] 是否与前一个元素相同，避免重复。
双指针循环：使用 while (j < k) 遍历。
j 和 k 去重：在找到有效三元组后，跳过重复的 j 和 k。

代码逻辑：

while j < k:
if sum == 0:
//处理结果并移动j和k
while j < k and nums[j] == nums[j+1]: j +=1
while j < k and nums[k] == nums[k-1]: k -=1
j +=1; k -=1

42. 接雨水

方法1：动态规划

步骤：

预计算左侧最大值数组 ldp 和右侧最大值数组 rdp。
对每个位置取 min(ldp[i], rdp[i]) - height[i] 累加。

方法2：双指针优化

关键点：
维护 lmax 和 rmax 分别表示左右遍历时的最大值。
当 height[left] <= height[right] 时处理左指针，反之处理右指针。
公式：ans += (lmax - height[left]) 或 ans += (rmax - height[right])。

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

方法：滑动窗口（Set实现）
关键点：
使用 set 记录当前窗口字符。
当遇到重复字符时，移动左指针并删除对应字符，直到无重复。
注意：用 while 循环处理重复字符的移除。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int j=0;
        int maxLength =0;
        unordered_set<char> charIndexSet;
        for(int i=0; i<s.size();i++){
            while(charIndexSet.find(s[i]) != charIndexSet.end()){
                charIndexSet.erase(s[j]);
                j++;
            }
            charIndexSet.insert(s[i]);
            maxLength =max(maxLength,i-j+1);
        }
        return maxLength;
    }
};

239. 滑动窗口最大值

方法：单调递减双端队列
步骤：

队列保存索引，且队列对应值单调递减。
窗口滑动时，移除超出窗口范围的队首元素。
新元素入队前，移除队尾小于它的元素。
当窗口形成后（i >= k-1），队首即为最大值。

76. 最小覆盖子串

方法：滑动窗口 + 哈希表
关键点：
用数组统计 t 中字符出现次数，维护窗口内字符覆盖状态。
扩展右指针直到覆盖 t，然后收缩左指针找最小窗口。
优化：用 count 变量记录匹配字符数，避免每次检查全表。

41. 缺失的第一个正数

方法：原地哈希
步骤：

遍历数组，将正整数 nums[i] 交换到索引 nums[i]-1 的位置。
再次遍历，找到第一个不满足 nums[i] == i+1 的位置。
边界：若全匹配，返回 n+1。

48. 旋转图像

方法：数学变换
步骤：

转置矩阵：交换 matrix[i][j] 与 matrix[j][i]。
水平翻转每行：交换 matrix[i][j] 与 matrix[i][n-j-1]。

17. 电话号码的字母组合

方法：回溯算法
关键点：
递归终止条件：路径长度等于数字串长度。
遍历当前数字对应的所有字母，回溯选择与撤销。
参数：index 表示当前处理的数字位置。

39. 组合总和

方法：回溯 + 剪枝
关键点：
允许重复选择元素，递归时 start 参数不变。
排序后剪枝：若当前候选数大于剩余和，提前终止。

79. 单词搜索

方法：DFS + 回溯
关键点：
终止条件：索引达到单词长度或字符不匹配。
标记已访问位置，递归后恢复状态。
注意：四个方向的DFS需处理越界问题。

74. 搜索二维矩阵

方法：二分查找
关键点：
将二维矩阵视为一维数组，计算中间元素的坐标：mid_val = matrix[mid//n][mid%n]。
根据 mid_val 与 target 的关系调整搜索范围。

20. 有效的括号

方法：栈
关键点：
遇到左括号入栈，右括号时检查栈顶是否匹配。
边界处理：栈为空时遇到右括号直接返回False。

394. 字符串解码

方法：双栈（数字栈 + 字符串栈）
步骤：

遇到数字时解析完整数值入数字栈。
遇到 [ 时，当前字符串入栈并重置。
遇到 ] 时，弹出数字和字符串，拼接后更新结果。

739. 每日温度

方法：单调栈
关键点：
栈保存温度递减的日期索引。
遍历时若当前温度大于栈顶温度，弹出并计算天数差。
结果数组：ans[stack.pop()] = i - idx

347. 前K个高频元素

方法：最小堆（优先队列）
步骤：

统计频率存入哈希表。
维护大小为 k 的最小堆，按频率排序。
遍历哈希表，堆满后弹出较小频率元素。

class Solution {

    struct myComparison{
        bool operator()(pair<int,int>&p1,pair<int,int>&p2){
            return p1.second>p2.second;//小顶堆是大于号
        }
    };

public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        for(int i=0; i<nums.size(); i++){
            map[nums[i]]++;  
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>,myComparison> pri_que;
        for(auto& it: map){
            pri_que.push(it);
            if(pri_que.size() >k){
                pri_que.pop();
            }
        }

        vector<int> res;
        while(!pri_que.empty()){
            res.emplace_back(pri_que.top().first);
            pri_que.pop();
        }
        return res;
    }
};

146 LRU缓存

方法：双向链表、哈希表
步骤:

设计一个双向链表，实现push_fornt函数、remove_node函数、get_node函数
push_fornt函数是在链表头部添加一个结点,实现操作如下所示： x->pre =dummy; x->next=dummy->next;x->pre->next =x;x->next->pre =x;
remove_node函数是删除一个结点，实现如下： x->pre->next = x->next;x->next->pre = x->pre;
get_node函数是获取key对应的节点，同时把该节点移动到链表头部，操作如下所示： 用hashmap通过key找到node，先remove结点node，然后再push_front结点
LRU的每次Put操作，需要先判断结点是否存在该hashmap中，存在则直接替换key对应的值，不存在则放到链表头部，如果hashmap的大小大于了LRU缓存大小，那么则删除hashmap中对应的key，删除链表中最后一个结点。注用DLinkedNode* back_node = dummy->pre;获取最后一个结点

struct Dlinked {
    int key, value;
    Dlinked *next, *pre;
    Dlinked(int _key, int _value) : key(_key), value(_value), next(nullptr), pre(nullptr) {}
};

class LRUCache {
private:
    int capacity;
    Dlinked* dummy;
    unordered_map<int, Dlinked*> key_to_node;

    void remove_node(Dlinked* x) {
        x->pre->next = x->next;
        x->next->pre = x->pre;
    }

    void push_front(Dlinked* x) {
        x->next = dummy->next;
        x->pre = dummy;
        x->pre->next = x;
        x->next->pre = x;
    }

    Dlinked* get_node(int key) {
        auto it = key_to_node.find(key);
        if (it == key_to_node.end()) return nullptr;
        Dlinked* node = it->second;
        remove_node(node);
        push_front(node);
        return node;
    }

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        dummy = new Dlinked(0, 0);
        dummy->pre = dummy;
        dummy->next = dummy;
    }

    int get(int key) {
        Dlinked* node = get_node(key);
        return node ? node->value : -1;
    }

    void put(int key, int value) {
        Dlinked* node = get_node(key);
        if (node) {
            node->value = value;
            return;
        }
        node = new Dlinked(key, value);
        key_to_node[key] = node;
        push_front(node);
        if (key_to_node.size() > capacity) {
            Dlinked* back_node = dummy->pre;
            remove_node(back_node);
            key_to_node.erase(back_node->key);
            delete back_node;
        }
    }
};

5 最长回子串

方法一：中心拓展法(偶数拓展，奇数拓展)
步骤:
1. 编写一个从中心拓展的回文字符串判断。
2. 从头遍历，i作为中心点往外拓展，可以以奇数个拓展，也可以以偶数个拓展。
3. 存储并且比较每次中心的的偶数、奇数拓展长度，返回最长回文子串

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

    string longestPalindrome(string s) {
        
        int start = 0,end = 0;
        for (int i = 0; i < s.size(); i++) {
            auto [left1, right1] = expandFormCenter(s, i, i);
            auto [left2, right2] = expandFormCenter(s, i, i + 1);
            
            int len1 = right1 - left1 + 1;
            int len2 = right2 - left2 + 1;
            int curr_len = end - start + 1; 
    
            if (left1 <= right1 && len1 > curr_len) {
                start = left1;
                end = right1;
            }
            if (left2 <= right2 && len2 > curr_len) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start,end-start + 1);
    }

方法二：动态规划

4 寻找两个有序数组的中位数

方法：二分法
步骤:
1. 就是要转换成从两个有序数组中找出第k个大的元素。
2. 需要每次判断A[K/2-1]与B[K/2-1]的值，判断完后就可以舍弃k/2个值，更新k的值。然后再将舍弃后的值进行判断。
3. 最后如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 k 小的元素。如果 k=1，我们只要返回两个数组首元素的最小值即可。

class Solution {
    public:
        int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
            /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
             * 这里的 "/" 表示整除
             * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
             * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
             * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
             * 这样 pivot 本身最大也只能是第 k-1 小的元素
             * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
             * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
             * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
             */
    
            int m = nums1.size();
            int n = nums2.size();
            int index1 = 0, index2 = 0;
    
            while (true) {
                // 边界情况
                if (index1 == m) {
                    return nums2[index2 + k - 1];
                }
                if (index2 == n) {
                    return nums1[index1 + k - 1];
                }
                if (k == 1) {
                    return min(nums1[index1], nums2[index2]);
                }
    
                // 正常情况
                int newIndex1 = min(index1 + k / 2 - 1, m - 1);
                int newIndex2 = min(index2 + k / 2 - 1, n - 1);
                int pivot1 = nums1[newIndex1];
                int pivot2 = nums2[newIndex2];
                if (pivot1 <= pivot2) {
                    k -= newIndex1 - index1 + 1;
                    index1 = newIndex1 + 1;
                }
                else {
                    k -= newIndex2 - index2 + 1;
                    index2 = newIndex2 + 1;
                }
            }
        }
    
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int totalLength = nums1.size() + nums2.size();
            if (totalLength % 2 == 1) {
                return getKthElement(nums1, nums2, (totalLength + 1) / 2);
            }
            else {
                return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
            }
        }
}

2 两数相加

方法：链表
需要注意的点:
1. 要用一个数字carry来记录进位；
2. 注意判断循环终止条件；

class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            ListNode* dummy = new ListNode(0);
            ListeNode* cur = dummy;
            int carry = 0;
            while(l1 || l2 || carry){
                int sum = carry;
                sum += l1 ? l1->val:0;
                sum += l2 ? l2->val:0;
                if(l1) l1=l1->next;
                if(l2) l2=l2->next;
                carry = sum /10;
                cur->next = new ListNode(sum % 10);
                cur = cur->next;
            }
        }
}

快速排序

void quickSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int pivot = arr[left];
    int i = left + 1;
    int j = right;

    while (i <= j) {
        while (i <= j && arr[i] <= pivot) i++;
        while (i <= j && arr[j] >= pivot) j--;
        if (i < j) std::swap(arr[i], arr[j]);
    }
    std::swap(arr[left], arr[j]);

    quickSort(arr, left, j - 1);
    quickSort(arr, j + 1, right);
}

归并排序

void merge(std::vector<int>& arr, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    for (i = left, k = 0; i <= right; ++i, ++k) {
        arr[i] = temp[k];
    }
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

堆排序

void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}