您好!欢迎来到爱源码

爱源码

热门搜索: 抖音快手短视频下载   

开启算法之路,还原问题,用debug调试了解每个问题! {互站网}

  • 时间:2022-06-24 00:17 编辑: 来源: 阅读:273
  • 扫一扫,手机访问
摘要:开启算法之路,还原问题,用debug调试了解每个问题! {互站网}
简介在这篇文章里,根据我个人的刷图计划,我会参考三个关于链表的简单级算法问题(不过感觉还是不简单)图片,不过没关系。从这篇文章开始,我会写出关于这个问题的统一代码,并以debug的形式整理出每一步。 通过还原题目场景,调试分析,印象更加深刻。 在这篇文章中有三个主题。 图片,合并两个有序链表图片1.1题目分析看到这个问题,你的第一反应是先合并两个链表,然后再排序。 啊 别想了。绝对暴力。 或者循环两个链表,然后两两比较,比如:for () {for () {if () {}}好吧,其实这个问题的本质就是可以用递归。这 我们来做个草图简单描述一下。 步骤1:比较两个链表的第一个节点。图片如果两个节点相等,比较L2链表[1]和L1链表[2]。注意:在L1节点[1]和L2节点[1]之间的比较完成之后,1.next指针需要被修改以指向它的下一个节点。 步骤2:现在我们已经得到了L2链表[1],它的下一个指针指向谁呢?即L2链表[1]与L1链表[2]相比较 图像比较完成后,L2链表[1]的下一个指向L1链表[2],以此类推。 比较L2链表[3]和L1链表[4] 最后,将图像L1链表[4]与L2链表[4]进行比较 图像比较完成后,整个链表已经排序完毕。 图像递归的方式是比较两个节点。当其中一个链表为空时,意味着其中一个链表已经被遍历,需要终止递归,返回比较结果。 也许这只是一个简单的不容易理解的图。我们用代码debug来分析一下。请耐心往下看。 图1.2代码分析需要根据问题的含义创建两个单链表。具体的创建方法,可以参考我的第一篇文章《手写单链表的添加、删除和检查基础!附加链接列表标题" 事不宜迟,首先初始化节点对象。 类ListNode {/** *数据字段*/int val;/* * *下一个节点指针*/ListNode next;ListNode(){ } ListNode(int val){ this . val = val;} ListNode(int val,list node next){ this . val = val;this.next = next} @ Override public String toString(){ return " ListNode { "+" val = "+val+' } ';}}定义一个添加链表的新方法。 公共节点add (listnodenode) {//1定义辅助指针ListNode temp = nodeHead// 2、先判断当前节点是否可以是最后一个节点if (null == temp.next) {//当前节点是最后一个节点temp.next = node返回nodeHead} // 3,遍历节点。如果当前节点的下一个节点不为空,则表示有后续节点while (null!= temp.next) {//否则将指针后移temp = temp.next} // 4、遍历后将最后一个节点的指针指向新添加的节点temp.next = node返回nodeHead.next}然后创建两个链表。 /* * *定义L1链表*/ListNode l11 = new ListNode(1);ListNode l12 =新的ListNode(2);ListNode l13 =新的ListNode(4);MergeLinkedList L1 = new MergeLinkedList();L1 . add(l11);L1 . add(l12);/* * *返回新添加的L1链表*/list node add 1 = L1 . add(l13);/* * *定义L2链表*/ListNode l21 = new ListNode(1);ListNode l22 =新的ListNode(3);ListNode l23 =新的ListNode(4);MergeLinkedList L2 = new MergeLinkedList();L2 . add(l21);L2 . add(l22);/* * *返回L2链表*/list node add 2 = L2 . add(l23);先贴上图中的递归代码。 公共节点mergetwolits(listnode L1,listnode L2) {/* *如果L1链表为空,则终止递归*/If(L1 = = null){ return L2;} if(L2 = = null){ return L1;}/* * *根据图中描述,比较节点*/if (l1.val < = l2.val) {/** * l1的节点比l2的小,根据图,需要比较的是L1链表中的下一个节点。* l1.next意味着在比较了节点大小之后,需要修改指针的引导,将整个链表串联起来*/L1。next = mergetwolits(L1。接下来,L2);返回L1;} else {/** *同理,与上一个if判断相同*/L2 . next = mergetowlists(L1,L2 . next);返回L2;} }}1.3 debug调试1.3.1 L1链表已经创建,L2也是。 图1.3.2比较两个链表的第一个节点图注:l1.next指的是递归的方法,也就是上图中我们描述的l1链表[1]指向l2链表[1],但是L2链表[1]指向谁呢?开始递归1.3.3如上图所示,开始比较L2链表[1]和L1链表[2]的2】图1.3.4。L1链表[2]和L2链表[3]图1.3.5后面的操作是一样的。这里将直接显示最后两个节点的比较。 在该图中,首先遍历L1链表,需要终止递归以返回L2链表。 为什么返回L2链表?直接看图 由于图像的最后一步比较了L1链表[4]和L2链表[4],也就是说,L2链表[4]是最后一个节点。如果L1链表被返回,L2链表[4]将被丢弃。请参考上图最后一个。 重点来了!!!重点来了!!!重点来了!!!遍历L1链表,触发递归,逐一返回比较结果。 这是我们最后一个l1链表[4]和L2链表[4]比较的步骤吗?很显著吗?l1.next指向l1节点[4],L1节点是它的最后一个节点[4],就是我们上图中最后一个结论的图像。 Image然后执行下一步返回。 [3]的L2链表指向[4]的L1链表。同理,按照之前的递归结果返回即可。我们来看看最终的排序结果。 第二,删除排序链表中的重复元素。图2.1题目分析第一次看这个问题好像挺简单的。这不是之前个人写的第一篇文章吗,删除链表节点!其实这个问题更容易仔细考察。由于在问题中已经说明了是排序链表,我们只需要比较当前节点和下一个节点,如果相等就可以直接修改下一个指针。 图2.1代码分析也是链表的定义,和上面第一个问题中的创建是一样的,只是我们需要重新创建一个单链表。 ListNode l1 =新的ListNode(1);ListNode l2 =新的ListNode(1);ListNode l3 =新的ListNode(3);ListNode l4 = new ListNode(4);ListNode l5 =新的ListNode(4);ListNode l6 =新的ListNode(5);NodeFun NodeFun = new NodeFun();nodefun . add(L1);nodefun . add(L2);nodefun . add(L3);nodefun . add(l4);nodefun . add(l5);ListNode ListNode = node fun . add(l6);创建完成后,看看重复的代码。 public node delete duplicates(ListNode head){/* * *定义了二级指针*/ListNode temp = head;/* * *判断当前节点和下一个节点不能为空,因为需要比较当前节点和下一个节点*/ while (temp!= null & amp& amp临时工下一个。= null) {/** *如果节点值相同*/If(temp . val = = temp . next . val){/* * *如果当前节点的值与下一个节点的值相同,则移动指针*/temp . next = temp . next . next;} else {/** *指针必须移动,否则会产生无限循环*/temp = temp . next;} }返回头;}}2.2 debug调试图2.2.1根据初始化的链表,应该是第一个节点[1]和第二个节点[1]进行比较。 不用说,两个节点图像相等,那么接下来就是进入if判断,也就是修改指针的指向。 此时,image的第二个节点[1]还没有被next引导,将被GC回收。 2.2.2下一步是比较节点[1]和节点[3]。如果两个节点不相等,则输入else并将辅助指针移动到下一个节点。 那么对图像的其余节点的判断是相同的。最后来看看打印出来的结果。 图,循环链表图3.1主题分析如果这个链表中有环,其中一个节点必须被指针引导一次或重复一次(如果有多个环) 所以个人当时简单的做法就是遍历链表,将遍历过的节点对象保存在HashSet中,每次遍历下一个节点时在HashSet中进行比较,节点的存在表示有环。 而且这个问题没有设置太多要求,只要有环返回布尔即可。 还有一种巧妙的写法,利用快慢指针的思想。 这种方式大致意思是,快慢指针就像龟兔赛跑。兔子跑得很快。如果有圈,兔子会比乌龟先跑到圈里。 然后它们会在某个节点相遇,也就是说链表有一个循环。 所以,形象,你的问题来了吗?这不公平。【兔子】跑得比【乌龟】快,那为什么兔子先跑? 想象一下,如果它们都运行在一个节点上,那么它们从一开始就相遇了,因为我们设定如果它们相遇在一个节点上,就意味着链表是循环的。 所以,这不是“不打自招”!形象的开始,这个【兔大哥】有点猛,一下子跑了两个节点。 够了,恋人结婚了,他们相遇了。 3.2代码分析这次创建链表时,不能只是单个链表,还得加一个环。 imageListNode L1 = new ListNode(3);ListNode l2 =新的ListNode(2);ListNode l3 =新的ListNode(0);ListNode l4 =新的ListNode(-4);/* * *给主角加个环*/l4 . next = L2;NodeFun NodeFun = new NodeFun();nodefun . add(L1);nodefun . add(L2);nodefun . add(L3);ListNode ListNode = node fun . add(l4);我们一起去找戒指吧。 public boolean has cycle(ListNode head){ ListNode temp = head;If(null == head){ // Empty表示没有循环返回false} // 1,集合集合存储遍历的节点。如果新节点已经在集合中,则意味着有一个环。// 2、利用慢指针//的思想定义慢指针ListNode slow = head//定义快速指针ListNode fast = head.next//循环,只要2个指针不重合,就保持循环while(慢!= fast){ //如果两个指针都到达尾节点,则没有环If(fast = = null | | fast . next = = null){ return false;}//否则移动指针slow = slow.nextfast = fast . next . next;}返回true}3.3 debug调试那么,尴尬的事情来了,这个东西调试不了。 如果有环,那么while循环就不会进来。 形象,只看结果。 如果image把戒指拿掉了呢?形象,你还得猜?没有气场。一定是 作者:奋进样本参考链接:https://www.cnblogs.com/fenjyang/p/14426665.html


  • 全部评论(0)
资讯详情页最新发布上方横幅

联系我们
Q Q:375457086
Q Q:526665408
电话:0755-84666665
微信:15999668636
联系客服
企业客服1 企业客服2 联系客服
86-755-84666665
手机版
手机版
扫一扫进手机版
返回顶部