2024.03.18_学习日记

Posted on In Views:

天气：晴
学习地点：学校
学习时长：8h

学习内容

  1. KMP
    KMP用一个next数组，next数组记录前一个位置的前后缀相等的长度，0位置是-1，1位置是0，后面就依次根据前面得出。具体看视频。
  2. lc452
    alt text
    alt text
    这个题就是看交集，先排序，按照第一个数字排序，start,end表示交集的两边，每次更新交集就行，遍历的时候如果左边的边大于end，那么start,end就变成遍历到的那个区间，并且res+1，否则，更新区间，左边界=原始左边界和遍历到位置的左边界的最大值，右边=原始右边界和遍历到位置的右边界的最小值，最后res还要+1，因为最后一个区间还没加上。
  3. lc886
    alt text
    这个题用并查集，并查集模板记住，一个find，一个union。然后初始化p数组，每个p的值就是本身，然后设置g数组defaultdict(list)，对每个dislike的数组都分别把g对应的加上，表示每个位置对应的不喜欢的人。然后遍历所有位置，并且看每个位置的不喜欢的值遍历一下，看其父亲节点是不是相等，相等就false，然后对每个j的父节点的父节点设成对应数组里的g【i】【0】的父节点。
  4. 优先级队列（从小到大排序，插入和删除都可以重新排序）
    alt text
  5. 所有排序
  6. 大顶堆
    alt text
    py只能实现heapq的小顶堆，大顶堆可以取相反数放进去heapify，然后当遇到比堆顶大的数，实际是比堆顶小的数，那就弹出堆顶，最后返回res。
    alt text
  7. 搜索二叉树
    alt text
    alt text