编程导航讨论话题讨论

讨论

19 参与
分享

快来分享你的内容吧~

点击登录,快来和大家讨论吧~
表情
图片
话题
打卡
综合
交流
文章
问答

一个简单的问题我糊涂了很久才搞好,这是我的一些解题思路,希望大神们指点,指导我更好的解答。

<html> <head></head> <body> <div class="content ql-editor"> <p><br></p> <p>这是一个数组<u>原地去重</u>的问题,最多保留k个重复元素,然后返回原地去重后新数组的大小。</p> <p>我的思路是这么发展的:</p> <p>原文链接如下:<a href="http://t.csdn.cn/8tU72" target="_blank">http://t.csdn.cn/8tU72</a></p> <p><br></p> <p>LeetCode26:给你一个有序数组nums,请你原地删除重复出现的元素,使每个元素只出现一次,返回删除后数组的新长度。不要使用额外的数组空间,你必须原地修改数组,在空间复杂度O1的情况下完成。</p> <p><br></p> <p>这个题的思路在于需要保存重复元素的值。如果我能保存重复元素的值,那么负责遍历数组的元素就能做出判断,如果是重复元素值就继续前进,直到不是该值为止。在加上算法通关村这章是双指针,所以这里我使用了双指针:</p> <p><br></p> <p><strong>slow代表去重后的有效元素,[0,slow]是去重的结果区间;fast用于遍历数组。</strong></p> <p><br></p> <p>如下图所示,刚开始slow==fast==0,然后fast不断前进直到不是该重复值(此处为1)为止。然后slow++,并将fast遍历到的新值赋给arr[slow],这样arr[fast]根据是否==arr[slow]继续前进,直到不是arr[slow]的值为止。此时arr[fast]就是一个新值,再赋给arr[++slow]。这样每有一个新的不同值就存储在[0,slow]区间中,从而实现了去重。</p> <p><br></p> <p>这类问题要处理边界情况,用for循环是更好的。</p> <p><br></p> <p>public static int deleteDuplicate(int[] arr){</p> <p>int slow = 0;</p> <p>for (int fast = 0; fast &lt; arr.length; fast++) {</p> <p>if (arr[fast] != arr[slow]){</p> <p>slow++;</p> <p>arr[slow] = arr[fast];</p> <p>}</p> <p>//每次循环fast都前进一步,如果不等于arr[slow](找到新值)了,就赋值给arr[++slow]</p> <p>//如果等于arr[slow](是重复值)了,那么slow不做任何改变,fast继续++判断下一个元素</p> <p>}</p> <p>return slow + 1;</p> <p>}</p> <p>可以看到,每次循环fast只走一步,最后退出循环时刚好是arr.length-1索引,就不用纠结越界问题了,因为该for循环中不会出现越界。</p> <p><br></p> <p><br></p> <p>但如果每个元素可以出现一次或两次,也就是最多可以出现两次,又该如何应对呢? (LeetCode80)例:输入【1,1,1,2,2,3】 输出【1,1,2,2,3】</p> <p><br></p> <p><strong>我认为这类问题的核心实际上是:fast指针在遍历数组时,判断哪些值可以放进[0,slow]结果区间。</strong></p> <p><br></p> <p>在前面的去重问题中,只有当arr[fast] != arr[slow]时,arr[fast]才能放入arr[++slow]中,这样才能确保重复元素只保留一个。</p> <p><br></p> <p>那么最多保留2个的时候,哪些值可以放进结果区间呢?</p> <p><br></p> <p>答案是:<strong>1.新值</strong>,即arr[fast] != arr[slow]的可以放入[0,slow]的区间。</p> <p><br></p> <p><strong>2.重复值的第二个元素</strong>,即arr[fast] == arr[slow],但是arr[fast]是第二个重复值时,这种情况也可以放入[0,slow]区间。如下图,fast遍历至第二个2时arr[slow]已经==2,但这个2是可以加入[0,slow]区间的。</p> <p><br></p> <p><img src="https://pic.code-nav.cn/planet_post_image/1696318504921309185/vdzi5uym.jpeg"></p> <p><br></p> <p>以此类推,如果最多保留K个元素,那么这些值可以放进结果区间:是新值的,和是第2~第K个重复值的。第K+1个重复值及以上不能放入结果区间。</p> <p><br></p> <p>那么现在我们注重编码的点,就落在了如何确定当前元素是第二到第K个重复元素上。</p> <p><br></p> <p><strong>思路一:arr[fast-k] != arr[fast] 有何不妥?</strong></p> <p><br></p> <p>不瞒大家,我最开始想到的其实是这个。也许你也这么想,如果限制只能是第二到第K个元素,那么因为第二到第K个重复值的元素,往前K个就是原数组中不同值的元素了,两者值不等;而第K+1个元素,往前K个就是第一个重复元素,值相等。所以限制条件应该是:</p> <p><br></p> <p>arr[slow] != arr[fast] || fast &lt; k || (arr[slow] == arr[fast] &amp;&amp; arr[fast-k] != arr[fast] )</p> <p><br></p> <p>乍一看,这不是很对吗?</p> <p><br></p> <p>但是问题在这:经过对arr[slow]的赋值,[0,slow]区间的元素已经发生改变,不再是有序的。此时如果还认为第K个重复值元素往前K个的值是不同的,可能会出问题。</p> <p><br></p> <p>如下图,是最多保留2个重复元素(k==2)的情况,里面就出现了问题。</p> <p><br></p> <p><img src="https://pic.code-nav.cn/planet_post_image/1696318504921309185/zx6gea02.jpeg"></p> <p><br></p> <p>如图,k==2,所以第三个2被舍弃了,同时fast移动到第一个3,是新值,所以把原来第三个2的位置(slow所指的位置)赋值成了3。你发现了没有,3的个数改变了。此时原本的第2个3,也就是第二张图中fast指向的元素,居然变成《第3个》3了。再进行arr[fast-k] != arr[fast] 时,就离谱地判false了,而它本应该加入[0,slow]结果区间的。</p> <p><br></p> <p><strong>这就是原地修改的弊病:给arr[slow]赋值时修改了原数组前面的值,使前面的元素偏离了初始值。</strong></p> <p><br></p> <p><strong>所以我自己总结出一个结论:在进行双指针的原地修改时,fast指针不能回头看。</strong></p> <p><br></p> <p>也就是不能用arr[fast-k]的意思,不知“回头”这两个字你是否理解透彻了呢?</p> <p><br></p> <p>思路二:正确做法是什么?</p> <p><br></p> <p>如果fast不能回头的话,从一开始我们就不应该往后看,而是应该设定一个变量,记录当前元素是重复值的第几个。代码如下:</p> <p><br></p> <p>public static int deleteDuplicateButSaveMostK(int[] arr,int k){</p> <p>int slow = 0;</p> <p>int repeatCount = 1;</p> <p>//repeatCount是当前值的重复次数,我们从第二个元素开始遍历,此时第一个元素重复次数为1次。</p> <p>//第一个元素可看做新值,看做已放入[0,slow]结果区间中,此时slow == 0指向该新值</p> <p>for (int fast = 1; fast &lt; arr.length; fast++) {//fast==1,从第二元素开始遍历</p> <p>if (arr[fast] != arr[slow]){//arr[fast]是新值就将当前值重复次数置为1次,然后赋值</p> <p>repeatCount = 1;</p> <p>arr[++slow] = arr[fast];</p> <p>}else {</p> <p>//是重复值就把重复次数++,如果重复次数&lt;=k就赋给arr[++slow]</p> <p>repeatCount++;</p> <p>if (repeatCount &lt;= k){</p> <p>arr[++slow] = arr[fast];</p> <p>}</p> <p>//如果重复次数&gt;=k+1就不做处理,fast继续++直到找到新值为止。</p> <p>}</p> <p>}</p> <p>return slow+1;</p> <p>}</p> <p><br></p> <p>最多保留重复元素个数,从1到K,全部可以用这个方法处理。</p> <p><br></p> <p>菜鸟初出茅庐,希望大神们指点更简单的做法。</p> <p><br></p> </div> </body> </html>

xdm,不想学习应该怎么办?😱今天感觉没什么想学习的心思 闲聊

拜托,来个大佬骂我吧

<html> <head></head> <body> <div class="content ql-editor"> <p>本人是专升本,本科还有不到一年的时间就要毕业实习了,不打算考研的</p> <p>本人很容易纠结和焦虑,</p> <p>目前学习到SpringBoot、Mybatis-plus,最近正在进行用户中心项目 进度慢。</p> <p>最近在学习上有纠结:</p> <p>对于完成用户中心项目之后,要如何继续学习?下面是我纠结的两条路</p> <p>1、要深度学习技术,运用到项目中或者开启新项目?:</p> <p>复习Redis(忘了差不多了),然后再跟着视频做一个Redis项目 ==&gt; 黑马的Redis</p> <p>啃写过的项目,尽量吃透,好在面试的时候能够对付</p> <p>学习MySQL进阶</p> <p>学习算法</p> <p>复习JVM</p> <p>有时间就把Spring源码也学一学</p> <p><br></p> <p>2、还是要广泛的学习新技术?:</p> <p>RabbitMQ 消息队列</p> <p>Nginx</p> <p>微服务</p> <p>Docker 容器</p> <p>Netty 网络编程</p> <p>学习并发编程、分布式、高可用、高并发、搜索引擎等</p> <p>目前对这些技术都不了解,对照鱼皮大佬的路线</p> <p><br></p> <p>来个大佬骂我:"就该xxx这样还用问ヽ(•ω•ゞ)" 或者有更好的路线 或者还有哪些知识必学?</p> </div> </body> </html>

很羡慕一直加班,还能保持大脑活跃度的人,我加完班后,大脑就是宕机状态了,一点转不动,还会影响第二天,如何做到天天加班还高强度的工作呢?

好焦虑。好慌。 大家都是因为什么学习编程的呢。为了钱?还是真的为了技术?[流泪]

#提问# 自己英语一般般,每次变量起名都很痛苦,尤其是一些多表关联相关的,大家有没有好用的起名器啊

星球里面有没有背单词狂魔。。求教,现在我10个要二十多分钟。[流泪]

求助,人事面都会问些啥啊,说是不会再问到技术。

问个问题:如果暑假才能去实习,是要等到暑假时才开始投简历面试,还是4,5月就要开始面试了?[流泪] 经验 #求职# 职场 提问 Java

计算机二级对计算机专业的学生有用吗[疑问]

下载 APP