当前位置: 首页 > news >正文

wordpress 移动版插件成都网站快速优化排名

wordpress 移动版插件,成都网站快速优化排名,个人帮忙做网站吗,山东做网站建设公司哪家好前置知识 数据结构-链表反转部分链表算法题的手写栈使用 难度: 初阶:使用容器, 难度中等。进阶:纯coding修改指针 ,难度中等,虽然leetcode是困难题。不过更加注重细节。 题目:反转 k 组中的…

前置知识

  • 数据结构-链表
  • 反转部分链表
  • 算法题的手写栈使用

难度:

  • 初阶:使用容器, 难度中等。
  • 进阶:纯coding修改指针 ,难度中等,虽然leetcode是困难题。不过更加注重细节。

题目:反转 k 组中的节点

给定一个单链表的头节点head, 实现一个调整单链表的函数, 要求每k个节点之间逆序, 如果不够k个节点,那么不调整。

输入: head = [1,2,3,4,5], k = 2
输出: [2,1,4,3,5]
其中, [1,2]为一组,[3,4]为一组,5不足则不调整。
[1,2]逆序[2,1], [3,4]逆序[4,3]

细节处理:

  1. 第一组逆转时, 整个链表的头节点从原来的1改成了2, 涉及换头逻辑处理。 题目也要求返回新链表的头节点。需要处理。
  2. 1 <= k <= n <= 5000, 力扣给定范围。考虑特殊数据的处理。 k<2的链表是不需要处理的。因为k<=0视为无效,k==1是对单个节点进行逆序,没有意义。因此,排除了1的处理。
  3. 由于我们逆序的是某个链表的局部, 这就涉及对整体链表与局部修改连接的维护。具体看code。

解法1:使用栈这个容器

事先声明, 这里采用的是全局静态数组充当栈的写法, 读者可根据需求自行改写成Java,C++内置栈的写法。
讲解在代码下面。

//提交代码, 将类名ReverseGroup -> Solution
public class ReverseGroup {//题目给定k最大5000,那么5001肯定足够了。 实测1201也可以public static int MAX = 5001;//类静态数组充当栈public static ListNode[] stack = new ListNode[MAX];//记录栈的大小, size == 0意味栈空。public static int size;//主方法public ListNode reverseKGroup(ListNode head, int k) {//排除无效数据if(k < 2) {return head;}//重置size,防止被上组数据污染, 实现空间复用。size = 0;return f(head,k);//调用辅助方法}/*** * @param head 原链表头节点* @param k 每k个逆序* @return 返回新链表的头节点*/private ListNode f(ListNode head, int k) {ListNode newHead = head, cur = head, prev = null, next = null;while(cur != null) {next = cur.next;//压栈stack[size++] = cur;while(size==k) {//满足则执行逆序prev = reversePart(prev,next);//调整newHead为修改后链表的头节点。newHead = newHead == head?cur: newHead;}cur = next;}return newHead;}/*** * @param left 修改局部链表头节点的前驱* @param right	修改局部链表尾节点的后继* @return 返回下一对修改局部链表的前驱节点。*/private ListNode reversePart(ListNode left, ListNode right) {ListNode cur = stack[--size];if(left != null) {left.next = cur;}ListNode next = null;while(size > 0) {next = stack[--size];cur.next = next;cur = next;}cur.next = right;return cur;}
}
private ListNode f(ListNode head, int k) {ListNode newHead = head, cur = head, prev = 					null, next = null;while(cur != null) {next = cur.next;//压栈stack[size++] = cur;while(size==k) {//满足则执行逆序prev = reversePart(prev,next);//调整newHead为修改后链表的头节点。newHead = newHead == head?cur: newHead;}cur = next;}return newHead;}
  1. newHead:修改后链表的新头节点。从逻辑上有两种可能, 如果发生第一组的调整, 那么newHead一定不是原先的head, 那么你可以看到内层while循环内部newHead = newHead == head?cur: newHead;, 就是第一组逆序, newHead应该指向cur的节点。
    比如,[1,2,3,4,5], k=2, cur在应该指向2这个节点,刚好第一组逆序[2,1,3,4,5], cur指向节点就是修改后的新头节点。
  2. cur指向的就是当前要入栈的节点,压栈 stack[size++] = cur;cur还充当外部循环遍历链表的作用。
  3. next: 修改局部链表尾节点的后继, 当发生逆序过程时,next指向那一组尾节点的后继。比如[1,2]逆序时,next指向2的后继3。因为只有进入循环, next始终是cur.next。
  4. prev:修改局部链表头节点的前驱, 第一组修改时为null,所以初始化为null,后续组的前驱节点交给reversePart函数返回值维护。
  5. size==k,当前栈大小满足k时需要逆序这组。reversePart(prev,next)这个函数,接受这组的前驱和后继,比如[1,2,3,4,5], k=2, 先逆序[1,2],就需要传入null前驱,3后继。因为函数内部逻辑要维护局部修改和整体的连接。reversePart(prev,next),这个函数还需要返回下一组(如果不存在那么用不上了)的前驱节点。比如[2,1,3,4,5]完成了1,2之间的逆序,那么还要返回下一对[3,4]的前驱1。那么下一次调用就传入1前驱和5后继来逆序3,4。
private ListNode reversePart(ListNode left, ListNode right) {ListNode cur = stack[--size];if(left != null) {left.next = cur;}ListNode next = null;while(size > 0) {next = stack[--size];cur.next = next;cur = next;}cur.next = right;return cur;}
  • 先出栈, 出栈节点就是局部链表的头结点, left(不为空)连接该节点。
  • 循环出栈连接逻辑
  • 最后出栈的结点连接后继right。
  • 返回下一组的前驱节点就是当前cur的节点。自行画图理解。
    在这里插入图片描述
    时间复杂度: O ( n ) O(n) O(n)
    空间复杂度: O ( k ) O(k) O(k)

解法2:原链表调整

//提交时,注意修改函数名public ListNode reverseKGroup1(ListNode head, int k) {// 特殊输入判断if (k < 2) {return head;}ListNode cur = head, start = null, prev = null, next = null;int count = 1;// 计数变量。while (cur != null) {next = cur.next;// 后继始终跟着循环更新。if (count == k) {start = prev == null ? head : prev.next;// 获得当前逆序对开始节点head = prev == null ? cur : head;// 第一组逆序需要修改头节点reversePart2(prev, start, cur, next);// (prev,next),[start,end]prev = start;// 更新前驱范围count = 0;// 重置}++count;// 自增cur = next;// cur跟着next。}return head;// head指向的更新后的头节点或者原先的头节点。}private void reversePart2(ListNode left, ListNode start, ListNode end,ListNode right) {//反转部分链表一样的逻辑 ListNode prev = start,next = null, cur = start.next;while(cur != right){next = cur.next;cur.next = prev;prev = cur;cur = next;}if(left!=null) {left.next = end;}start.next = right;}

在这里插入图片描述
每日两题结束。

http://www.hengruixuexiao.com/news/55691.html

相关文章:

  • 怎样申请免费网站平面设计正规培训机构
  • c 做动态网站可以吗seo属于什么职位类型
  • 网站建设方案有哪几种关键词指数
  • zara网站建设需求分析企业关键词优化推荐
  • 自我介绍ppt模板免费seo软文代写
  • 什么网站做兼职可靠营销网站建设推广
  • 宁波网站推广软件百度一下你就知道了百度一下
  • 专做logo网站叫什么企业门户网站的设计与实现
  • 百度收录好的网站排名市场推广计划方案
  • 网站制作需要学习什么西安百度推广开户多少钱
  • wordpress怎么使用插件搜索引擎优化方案
  • 旅游网站开发系统关键词搜索引擎
  • 网上做实验的网站金华网站建设
  • 视频上传网站建设线上卖货平台有哪些
  • 网站行业新闻怎么做seo建站营销
  • 建设工程有限公司 网站网络舆情优化公司
  • 怎么弄免费的php空间做网站seo排名工具
  • 陕西电商b2c网站建设公司石嘴山网站seo
  • 短链接在线生成官网免费南宁seo手段
  • 做感恩网站的图片素材竞价排名的服务模式是
  • 定制网站 北京免费行情软件网站下载
  • 建设银行兰州分行网站百度竞价在哪里开户
  • 织梦做的网站如何上线青山seo排名公司
  • 重庆发布微信公众号seo企业推广案例
  • 哈尔滨网站设计公司灯塔网站seo
  • 做平面资源比较好的网站青岛网站建设制作推广
  • 免费psd素材网站小程序推广
  • 手机网站开发技巧防恶意点击软件
  • wordpress网站专题网站建设服务
  • 做网站的过程中有哪些问题怎么做电商新手入门