牛客刷题题解暂记

warning: 这篇文章距离上次修改已过473天,其中的内容可能已经有所变动。

地址:算法篇题目
记录一下刷题时的问题,待晚上整理题解报告

  • BM1 反转链表:核心思想就是将插入的位置改一下,从链表头部插入就成了逆序
  • BM2 指定反转:核心思想是标记一个反转区间的前驱指针(插入位置),后续插入的将从这里插入
  • BM3 每k组反转:核心思想是利用一个慢指针指向第i组的第一个元素,然后扫描到最后一个元素,再利用尾指针进行逆序插入(需要维护好尾指针),最后将剩余不足一组的元素进行顺序插入到尾部。
  • BM4 简单的合并,比较大小合并。然后将剩余的直接加入链表尾部即可。
  • BM5 暴力挨个合并(或者拆分数组,每次折半合并),也可以考虑全部取出来进行排序
  • BM6 利用两倍步进(走二进一)的快慢指针,当快指针追上慢指针时说明有环,否则快指针必然会走到null的链表尾部
  • BM7 利用BM5的结论,推理得到当他们相遇时一定是两倍关系(前提是快指针必须是走满两步后碰到的慢指针,比如快指针走了第一步就遇见了慢指针这种情况不算),因此能够得出l + x = nH的结论(l为不为环的长度包括入环的点,H表示环的长度,x表示入环位置到第一次快慢指针相遇的距离)
  • BM8 利用快慢指针,当快指针步进达到k时,慢指针开始同步移动直到快指针走完。
  • BM9 利用快慢指针,当快指针步进达到 n + 1时,慢指针开始同步移动,最终指向倒数第 n + 1个元素(定义一个前驱指针指向head),然后删除第n个元素即可,需要处理删的是head的情况。
  • BM10 利用l1 + l2长度一致, 让指针遍历两条链,相交的点就是第一个公共节点(nil就说明跑到头了都没碰到),因为相同速度,相同距离,肯定会相遇的(将两条链拼起来对比就看出来了)
  • BM11 大模拟,反转两条链表,然后带进位的进行大数加法的模拟,最后把结果链反转一下
  • BM12 链表上进行快排超时了,使用归并排序没问题。(还有一种方式就是利用数组辅助进行快排)
  • BM13 反转链表之后判断一遍即可
  • BM14 利用两个指针,一个指向奇数位的尾部,一个指向偶数位的尾部。每次插值往这两个中的一个插入即可,偶数位再第一次要赋值未奇数位(因为奇数位肯定是第一个节点)
  • BM15 挨个判断下一个是否相等即可,相等就删除。注意空链表的情况
  • BM16 找到下一个不相等的元素,如果距离大于1,就删除这个区间的所有节点。所以需要一个删除的起始点指针,当没有相等元素时就跟随指针移动。
none
最后修改于:2023年03月01日 16:48

评论已关闭