Hexo
0%

leetcode刷题笔记

发表于 分类于

leetcode刷题笔记

数组

二分查找

关键：循环条件，先想好题目所求元素所在区间是左闭右开还是全闭
比如说:

  1. target在[left,right]里，则当left=right时，[left,right]有效，所以循环条件为left<=right
  2. target在[left,right)里，则当left=right时，[left,right)无效，所以循环条件为left<right

移除元素

双指针法

  1. 移除、移动元素，返回前n位，两个指针cur和end
  2. 有序数组的平方：从两边开始找当前最大值

区间和

前缀和：涉及计算区间和的问题

——p[i] 表示 下标 0 到 i 的 vec[i] 累加 之和

求2~5的区间和 =p[5] - p[1]

链表

链表设计

struct ListNode
dummy：做题也常用

链表相交

  1. 求两链长度
  2. 长链和断链末尾对齐后遍历
  3. 相遇处即为相交点

环形链表

  1. 快慢指针从头出发，快指针走两步，慢指针走一步，相遇则有环
  2. ptr1从头出发，ptr2从相遇点出发，一次走一步
  3. 再次相遇点——环入口

哈希表

哈希表理论基础

解决问题：快速查询

哈希碰撞

  1. 拉链法：发生冲突的元素存储在链表里
    • 选择适当的哈希表的大小，不会因为数组空值浪费大量内存，也不会因为链表太长在查找上浪费时间
  2. 线性探测法：遇到冲突向下找一个空位存放冲突元素
    • 保证tableSize>dataSize

常见的三种哈希结构

  1. 数组

  2. set

    • set：红黑树，增删查改：O(log n)

    • multiset：红黑树，增删查改：O(log n)

      key不可以修改，只能增加和删除

    • unordered_set：哈希表，增删查改：O(1)

  3. map

总结：当需要快速判断一个元素是否出现在集合里，考虑哈希法

——牺牲空间换取时间

有效的字母异位词

  • 数组是简单的哈希表，当遇到元素范围固定，可以考虑用数组作为哈希表，比如26个字母——使用数组来做哈希的题目，都限制了数值的大小

  • 如果数据分散、跨度比较大，使用数组容易造成空间的浪费

  • 直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的——如果数值范围固定，优先考虑用数组

快乐数

  • 取位数

    1
    2
    3
    4
    5
    6
    7
    8
    int getSum(int num){
        int sum;
        while(num!=0){
            int bit=num%10;
            num/=10;
            sum+=bit;
        }
    }

  • 循环/成环问题

    • 使用哈希判断是否存在重复元素
    • 使用快慢指针：快指针一次走两步，慢指针一次走一步，快慢指针相遇——快指针比慢指针多走了一个循环周期

总结：map vs set vs 数组

  1. 数组：大小受限，数据分散会浪费内存空间
  2. set：只能存放key，同等情况下性能不如数组，因为取哈希值也要耗时
  3. map：需要存放两个值，什么作为key取决于需要查询什么

不要求key有序的时候，使用unordered_map/set

四数之和II

给出四个数组，求四个数和为0，不要求去重

使用hashmap，两数之和：两数之和出现的次数，再去遍历另外两个数组

三数之和

可以使用双指针法

  • 将数组排序

当返回值是具体数值，可以使用双指针法，如果要求返回的是下标，不能对数组排序，也就不能使用双指针法

四数之和

当求几个数之和时，要求返回的元组不能重复，使用双指针法

不管是求几个数之和，以前i-2个数作为标准，剩下两个数用双指针确定

时间复杂度从O(n^i)降为O(n^(i-1))

字符串

翻转字符串里的单词

  • 移除不必要的空格 = 移除元素 ——>双指针法
  • 翻转：先整体翻转后局部翻转——先翻转整个字符串，再翻转单词

右旋转字符串

字符串尾部的若干个字符转移到字符串的前面

解决方法：先整体翻转后局部翻转——先翻转整个字符串，再分别翻转左部和右部

KMP算法

解决问题：字符串匹配

eg：文本串：aabaabaaf 模式串：aabaaf

  • 暴力解法：O(M*N)

  • KMP

    1. 第一次匹配

      a a b a a b a a f
      a a b a a f

    2. 第二次匹配

      a a b a a b a a f
      a a b a a f

      思路：文本串指针不变，模式串指针回转

  • next数组构造思路

    1. 初始化next数组
    2. 处理不相等情况
    3. 处理相等情况
    4. 更新next的值

重复的子字符串

  1. 暴力解法

    分别以1~n/2的字符结尾，判断能否构成字符串

  2. 移除匹配

    如果 s 是重复字符串，则 s+s 去除首尾仍能检测出中间含 s

  3. KMP算法

    如果字符串str能用子字符串substr重复组成，则

    len(str)=m*len(substr)

    len(presuf)=(m-1)*len(substr)

    → len(substr)=len(str)-len(presuf)

    → len(str)%[len(str)-len(presuf)]=0

栈和队列

栈与队列的理论基础

  • 栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供**迭代器(iterator)**。 不像是set 或者map 提供迭代器iterator来遍历所有元素
  • 栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）
  • STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）
  • 栈的内部结构，栈的底层实现可以是vector，deque，list
    • SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构：deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。
    • 指定vector为栈的底层实现： stack<int,vector<int>> stack;
  • 队列是先进先出的数据结构，同样不允许有遍历行为，不提供迭代器
  • 可以使用deque和list对queue初始化，而vector因其缺少pop_front()，不能用于queue
    • SGI STL中队列一样是以deque为缺省情况下的底部结构
    • 指定list 为队列的底层实现：queue<int,list<int>> queue

用栈实现队列

  • 双栈
  • 进队：进栈in
  • 出队：栈in全部弹出到栈out，从栈out弹出

用队列实现栈

  • 一个队列
  • 进栈：进队
  • 出栈：队列头部不断出队移到队尾，直到最后一个元素到队头 → 出队

有效的括号

  • 括号匹配问题，使用栈实现

删除字符串中的所有相邻重复项

  • 删除重复项也可以用栈实现
  • 输出的时候记得翻转

逆波兰表达式求值

  • 逆波兰表达式：一种后缀表达式，运算符放在后面
  • 适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中

滑动窗口最大值

  • 单调队列：使用容器 deque 出口→入口
  • 实现接口：
    • front：队头——最大值
    • pop(int val)：离开窗口的值 val如果比队头小，本来就不在队列里，不用处理；而队头已经是窗口内最大值了，所以 val也不可能比队头大。所以只有队列不为空并且弹出 val==队头，才弹出
    • push(int val): 如果push的值比队尾大，那么单调性被破坏，弹出直到队列为空或者队尾比push的值大→ 维护单调性

前k个高频元素

  • 容器适配器：优先级队列
    • 披着队列外衣的堆，缺省情况下是大根堆——以vector为表现形式的完全二叉树
    • 要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素