每周一道算法题，提升自己的逻辑思维
不知不觉已经是第三周了，我知道你们其实都并不爱看每周的这道算法题，既枯燥还无趣，所以每次写这文的时候，都会穿插些别的内容，来中和一下这种枯燥乏味的算法题
今天啰嗦点什么呢？先聊聊，为什么要写这个每周算法题系列，后面写算法题的时候再说说面试时遇见算法题时的解题思路
为什么写这个系列
LeetCode的题库，现在共有1020道题，把easy与hard难度的题目去掉，只留下medium难度的都还有608道题，按咱们这个进度，每周一道题，一年52周，单独就是写中等难度的，我要写近12年才能写完！
所以，写这个系列的目的并不是为了让我们把每一个题都刷一遍，然后大家都面试无忧，而是希望通过这个系列的文章，每周都能锻炼一下大家解决问题的能力
LeetCode上的题目有一个好处，大多数的题目不是为了解题而解题，基本都影射着具体的使用场景，而有些时候为了不然题目过于简单，所以故意提了一些性能要求，比如时间复杂度，空间复杂度的限制，其实这样也是更好的锻炼我们对代码性能的掌控力
我们绝大多数的码农都是在写业务代码，CTRL+C、CTRL+V用的不亦乐乎，包括我自己
所以平时的工作用不到太多的「算法」去解决问题，所以偶尔遇到一次时，就化身为Stack Overflow或者Github的搬运工，实在不行就乱七八糟的写个一大通，晦涩难懂的同时还性能低下
每周看看算法题这样的好处很明显，可以长期的保持我们的思维活跃，当遇到问题的时候，我们很容易的能找到思路，当有思路后，就算实现不出来，再去Google或者百度，效率比不知从何下手要高十倍不止
我希望你也能与我一起思考如何解决，因为我并不是算法工程师，只是一个跟你一样的普通人，我在文中写的解决方案并不是最好的，如果你有更好的解决思路，不妨加我好友一起沟通交流一下
现在这个公众号还没有留言功能，现在在开发一个留言小程序，用于提高我们的互动，到时候上线了，大家有更好的解题思路也能更方便的交流了
算法题的思路来源
本周算法题是LeetCode题号#80，名字为Remove Duplicates from Sorted Array II
题目要求跟上周相比还是稍微加大了一点难度，毕竟上周为了介绍Go语言，所以就选了个Easy的题目
本周的算法题可以说是上周的算法题的变形，加大了一点难度
先来看看题目要求
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
这次还是把英文原介绍丢上来比较好，毕竟单纯的由我自己来说，有可能就变味了
不信？那我用自己的话给你们介绍一遍
给你一个已经排序好的数组，返回一个新的数组长度，在这个长度内，同一个值最多存在2次。要求：不能使用额外的数组空间。
是吧，我良心的把所有复杂的描述都给你去掉了，但是为了能够让你们能更好的理解原意，以后我还是不丢开英语原话了
好了，看完描述，再来看看几个example，加深一下理解，毕竟解决问题之前，总得需要深刻理解我们要干嘛
example1：
给你数组：nums = [1,1,1,2,2,3]，返回length=5，并且前5个元素为：1，1，2，2，3
example2：
给你数组：nums = [0,0,1,1,1,1,2,3,3]，返回length = 7，并且前7个元素为：0，0，1，1，2，3，3
看完这两个示例，我想大家都心里有数了
不要着急往下看我的思路，先在这停留2分钟，想想自己面试时，遇到这道题时该如何处理
遇见算法题时的思路
首先理解题目，抓住给的重要条件
1、已经排好序的数组
题目给的已知条件就这一条，然后再来看一下我们要达到的目的
1、返回新数组的长度
2、新数组在这个长度里，同一个元素不能出现2次以上
3、不允许使用额外的数组空间
知道了现在有什么，知道了要达到什么目的，接下来要做的就是怎么才能到达目的地
如果是使用JS，那么找到重复次数2次以上的数，当第三次出现的时候直接移除就OK了
如果使用Go语言，因为无法直接对数组里的元素进行删除操作，那么我们就只能像上周那样，将整个数组重新整合，把后面的数据移动到前面来
不管是将重复2次以上的数据删除，还是移动元素，我们现在面临的问题都是如何找到重复了2次以上的数字
找到阻拦我们去目的地的障碍是什么之后，现在要做的就是解决路上的拦路石，怎么做呢？当然是从已知的条件里去找，看有没有什么能用上的。
已知的信息就相当于我们出远门身上带的炸药包，路上遇到打劫的山贼，不拿出来使使，那些山贼们怎么会知道咱们的厉害呢？
现在我们知道已知条件是「已排序好的数组」，既然已经排好序了，那么排好序有什么作用呢？现在是递增排序，那排好序后的数组特性就是，后面的数比前面的数要大，如果后面的数是重复的数字，就意味着后面的数等于前面的数
所以，只要当后面的数等于前面的数时，我们就知道这个数重复了。你可能会说，那也只是知道重复了一次啊，怎么判断重复了2次呢？
这就是一个思维定势了，谁告诉你只能找后面一个数的？我就不能找后面2个数了？也就是说，当我nums[0]==nums[2]时，不就代表nums[0]的值已经出现3次了？所以nums[2]以及它后面同样的数值，都是我们要抛弃的东西
所以，在解决问题时，要充分的发挥已知条件的作用。
好了，思路已经理的差不多了，接下来的思路就是要进行Code实现，Code实现，不同的语言就有着不同的实现方式，这次咱们还是老规矩，说两种语言
咱们来看看代码实现，代码实现的思路讲解我放在了代码注释里
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function (nums) {
let j = 0, i = 2;// 间隔1个元素
for (; i < nums.length; i++) {
// nums[i]与nums[j]，中间间隔了一个nums[i-1]
if (nums[j] === nums[i]) {
// 当nums[j]==nums[i]时，代表这个数已经是第三次出现，所以要删除
nums.splice(i, 1);
// 删除一个元素后，用于遍历的游标i要-1
// 意味着被删除的元素后面的内容要往前面移动一位，所以游标只要保持不动，就能找到下一位数
i--;// i-- 只是为了抵消for 循环的 i++
} else {
j++;
}
}
return i;
};
下图是JS代码提交的返回结果，拿来娱乐娱乐
看来这次我的JS解法写的还不错，容我膨胀一下，看来我的这个思路比大多数人的方案都要优秀呀
好了，老规矩，用你们熟悉的JS写了之后，咱们来复习复习Go语言的使用
Go语言的实现我稍稍优化了一下下，虽然没点luan用
func removeDuplicates(nums []int) int {
// 因为最多元素可重复2次，所以前2个数不用管
if len(nums) < 3 {
return len(nums)
}
// 定义2个游标 i,j
j, i := 2, 2，// i 用于遍历数组，j 用于记录长度
for ; i < len(nums); i++ {
if nums[j-2] != nums[i] {
// 因为不相等就意味着不重复
// 直接将后面的值替换到前面来就好了
nums[j] = nums[i]
j++
}
}
return j
}
之所以再用Go语言来写一遍，是因为Go语言与JS的实现思路略有不同，所以这次我觉得还是写的有点价值的
毕竟在语言没有直接删除数组元素的方法的情况下，这道题的难度又略微增加了一点
有心的读者应该会发现，这次我没有使用range来迭代数组，就是不同的写法能让你们对Go语言能有个不同的印象
写在最后
好了，这周的算法题就说到这了，今天啰嗦的内容有点多，说了这个「每周算法题」的用处，也说了「面试时遇见算法题」该怎么找思路。思路对了，逻辑顺畅了，就算最后没实现出来，依然能给面试官留下一个不错的印象
有些人问我为什么不画个流程图什么的便于你们理解，我想说，以后就不要再问我为什么不画个图让你们更好的理解了。
第一，画图你们是看的爽了，可我就苦逼了。
第二，我画的图，你们看了也就看了，其实是真没学会，别问我怎么知道的，我之前看人家的画图看了一年，每次都是以为懂了，结果自己实现的时候才发现自己屁都不知道
第三，要是真有兴趣想提高一下自己，自己要是想不通，拿着Code去Debug跑一跑，然后自己拿个笔和纸，画一画，比看我画的图收获要大的多。
Go语言的环境难搭建，难道跑JS的环境还不好搭建么？
成长总是很累的，知识都是一点一滴积累起来的。要想别人的知识变成自己的知识，只有实践过，印象才深刻。
祝大家能在金三银四里顺利的找到合适又高薪的工作，远离996，远离ICU
网友评论