V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Knuth
V2EX  ›  LeetCode

Leetcode 刷题记录

  •  
  •   Knuth · 2022-07-29 21:37:42 +08:00 · 2115 次点击
    这是一个创建于 608 天前的主题,其中的信息可能已经有所发展或是发生改变。
    迫于...遂在此记录苦逼刷题生活
    18 条回复    2023-02-08 17:00:23 +08:00
    god
        1
    god  
       2022-07-29 21:53:27 +08:00 via iPad   ❤️ 2
    Knuth 也要刷题了^-^

    —-讲个冷笑话
    Knuth
        2
    Knuth  
    OP
       2022-07-29 23:21:07 +08:00
    Day 1
    3. 无重复字符的最长子串:哈希表、滑动窗口
    Knuth
        3
    Knuth  
    OP
       2022-07-30 15:53:53 +08:00
    Day2
    239. 滑动窗口最大值
    优先队列 /单调队列
    Knuth
        4
    Knuth  
    OP
       2022-07-31 12:13:38 +08:00
    Day3
    76. 最小覆盖子串
    滑动窗口,收缩左边界
    一个小技巧,对于哈希表 key 为 char 类型,value 为 int 类型,可以直接使用数组,int[128]。

    通过这三道题对滑动窗口的题有了一定的理解

    以后一周更新两次,题目坚持每天刷
    Knuth
        5
    Knuth  
    OP
       2022-08-04 21:39:14 +08:00
    2020/8/4:
    最近做了链表、回溯
    链表
    21. 合并两个有序链表
    25. K 个一组翻转链表
    92.反转链表 II
    206.反转链表
    链表题 dummy 节点可以节省好多工作
    回溯
    注意有重复元素时,先排序,在回溯过程中注意树层剪枝即 nums[i] == nums[i-1]&&used[i-1]=false 时跳过,此时代表 i-1 已经被选过了
    46/47.全排列
    78/90.子集
    Knuth
        6
    Knuth  
    OP
       2022-08-04 23:04:22 +08:00
    @Knuth #5 排列问题通过 used 数组标识已使用元素,子集通过 start 参数来过滤已使用元素
    Knuth
        7
    Knuth  
    OP
       2022-08-06 23:11:20 +08:00
    工作不顺心,刷题继续

    146. LRU 缓存
    这题用两个 unordered_map+list 也能实现 O(1),明天在学习双向链表
    Knuth
        8
    Knuth  
    OP
       2022-08-07 00:33:08 +08:00
    @Knuth 补一个快速选择算法
    215. 数组中的第 K 个最大元素-看 CLRS9.2 证明
    Knuth
        9
    Knuth  
    OP
       2022-08-07 13:44:39 +08:00
    2022/8/7
    做点简单的
    1. 两数之和 哈希表一次遍历
    167. 两数之和 II - 输入有序数组 双指针
    Knuth
        10
    Knuth  
    OP
       2022-08-07 23:01:12 +08:00
    2020/8/7
    快速排序
    关于边界条件 https://www.acwing.com/solution/content/16777/
    这篇题解讲的很不错,个人喜欢用 j 做边界,所以 pivot=nums[l],对于用 i 做边界,则需要同 j 的情况取反。对于数据增强的情况下 pivot 取 nums[(l+r)/2]或随机化加快速度
    ``` cpp
    void quick_sort(vector<int>& nums, int l, int r) {
    if(l >= r) {
    return ;
    }
    // int pivot = (r + l) / 2;
    int pivot = l + rand() % (r - l + 1);
    // 注意基准元素应当取出来比较
    int x = nums[pivot];
    int i = l - 1;
    int j = r + 1;
    while(i < j) {
    // x 不能用 nums[pivot]代替,因为 swap 会破坏 nums[pivot]
    while(nums[++i] < x);
    while(nums[--j] > x);
    if(i < j) {
    swap(nums[i], nums[j]);
    }
    }
    quick_sort(nums, l, j);
    quick_sort(nums, j+1, r);
    }
    ```
    归并排序
    堆排序
    (改天在学
    快速选择算法
    思路:直接 k-1 寻找排序后第 k-1 个元素的位置,因为每次只递归一边,所以期望复杂度时 O(n),具体证明算导(看不懂 x

    ``` cpp
    class Solution {
    public:
    int findKthLargest(vector<int>& nums, int k) {
    return quick_select(nums, 0, nums.size() - 1, k - 1);
    }

    int quick_select(vector<int>& nums, int l, int r, int k) {
    if(l >= r) {
    return nums[l];
    }
    int i = l - 1;
    int j = r + 1;
    // int pivot = l + rand() % (r - l + 1);
    int pivot = (l + r) / 2;
    // int pivot = l;
    int x = nums[pivot];
    while(i < j) {
    while(nums[++i] > x);
    while(nums[--j] < x);
    if(i < j) {
    swap(nums[i], nums[j]);
    }
    }
    //
    // int sl = j - l + 1;
    if(k <= j) {
    return quick_select(nums, l, j, k);
    }
    return quick_select(nums, j + 1, r, k);

    }
    };
    ```

    15. 三数之和
    首先排序
    对于 nums[i] > 0,可以直接 break ,后面不会有符合题意的三元组
    注意 i 去重,jk 在取到目标三元组也需要去重,
    103. 二叉树的锯齿形层序遍历
    flag 标记奇 /偶
    Knuth
        11
    Knuth  
    OP
       2022-08-08 23:48:46 +08:00
    300. 最长递增子序列
    1. dp O(n^2)
    2. DP+贪心+二分下界
    一个坑,二分算法边界理解又有问题了,https://www.acwing.com/solution/content/107848/
    Knuth
        12
    Knuth  
    OP
       2022-08-09 23:21:27 +08:00
    2022/8/9
    今天好累,回顾一道题
    5. 最长回文子串
    法一:dp
    法二:中心扩展法 分奇偶
    Knuth
        13
    Knuth  
    OP
       2022-08-10 23:10:30 +08:00
    2022/8/10
    1143. 最长公共子序列
    dp
    遗留问题:输出最长公共子序列
    Knuth
        14
    Knuth  
    OP
       2022-08-15 23:29:08 +08:00
    236. 二叉树的最近公共祖先
    后续遍历
    if(root == NULL || root == p || root == q) {
    return root;
    }
    @Knuth @god
    Knuth
        15
    Knuth  
    OP
       2022-08-17 21:40:01 +08:00
    今日新词
    head count × head cut √
    Knuth
        16
    Knuth  
    OP
       2022-08-20 12:21:42 +08:00
    2022/8/20
    今日学习单调栈
    42.接雨水
    496.下一个更大元素 I
    503.下一个更大元素 II
    739.每日温度
    2830446056
        17
    2830446056  
       2022-10-27 00:59:44 +08:00 via Android
    怎么不做了呀
    Knuth
        18
    Knuth  
    OP
       2023-02-08 17:00:23 +08:00
    又得重启流浪力扣计划了!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5942 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 42ms · UTC 02:05 · PVG 10:05 · LAX 19:05 · JFK 22:05
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.