昨天利用一天的时间, 在 leetCode 上面刷了三道题, 现在做下总结, 涉及到的题目:
A) 移除元素
B) 搜索插入位置
C) 螺旋矩阵 II
过程记录
A) 移除元素:
给定一个数组 nums 和一个值 val, 从数组中找出跟 val 一样的值, 并且删除掉, 然后返回数组中剩余元素的个数。
这道题目一开始就有了思路, 先把符合条件的元素设置为零, 然后在用排序算法把剩余元素放到前面, 最后返回剩余元素的个数就可以了。
但紧接着我就犯蒙了, 如果给定的数组是一个自然数, 数组中本来就有 0 怎么办? 幸好它做了一个条件限制, 数组中的所有元素都大于等于零。
B) 搜索插入位置
给定一个已经排序的数组, 和一个值, 查找该值可以在数组中插入的位置， 要求该位置上的数值大于等于给定的值。
一开始我以为很简单, 其实他也很简单, 但自己就是没有思考完全, 一开始心想, 不就是 for 循环查找, 只要发现大于等于该值就可以了, 不简单吗? 但是提交还是报错了， 一看, 数组只有一个元素的时候 报错了, 于是就添加一个判读条件, 紧接着又报错了, 给定的值大于数组中所有元素的值的时候报错了, 这种情况自己能够感知到, 但报错的原因是数组下标越界, 经过几轮折腾, 终于形成清晰的判断:
1） 给定值小于数组元素值
2) 给定值等于数组元素值
3) 给定值大于数组元素值
终于, 提交通过。
但话说回来, 这个题目自己的代码, 从性能的角度来将, 他不是最优的, 因为没有使用到二分查找算法。
C) 螺旋矩阵 II
给定一个数字 n, 画出 n*n 的螺旋矩阵, 形式如:
01 02 03 04
12 12 14 05
11 16 15 06
10 09 08 07
看出来了吗? 如果看不出来, 我在用箭头画一下:
⍈ ⍈ ⍈ ↴
⍐ ⍈ ↴ ⍗
⍐ ⍐ ↵ ⍗
⍇ ⍇ ⍇ ↵
这个形状就好像是写回字型, 外面是一圈, 里面是一圈， 里面的圈比外面的那一圈要小。
说实在, 刚开始我真不知道怎么去写这个代码, 犹豫了很久, 仍然不知道怎么办, 于是就开始摸索他的规律, 先由左到右， 然后是上到下， 在然后是右到左， 最后是下到上， 就这样循环。
到那里开始转弯, 这个点如何判断? 心里面知道是以 n 为依据来做判断, 代码敲着敲着就发现不对劲, 里面那一圈比外面的小, 因此， 长度已经不是 n 了, 这时候需要做递减处理, 但是左右边两头都需要处理， 上下也是一样。
原先使用 for 语句循环, 这个时候只能改用 while 循环了, 那什么时候结束呢？ 判断的依据是累加数字大于等于 n*n 就可以, 敲完了代码, 就运行了, 发现超时, 一开始还不知道已经进入死循环, 还以为服务器那边做时间限制, 一段折腾后, 实在没则, 就到本地执行， 一点一滴的修改， debug, 终于完成了！
问题在哪里? 对边界值的判断不准, 主要有:
1） 一圈的长度是多少
2） 拐弯处的判断, 这个时候判断不准就会把已经画好的点重画, 看到的形状就是乱七八糟。
3） 什么时候结束? 虽说大于等于 n*n 是一个精确的判断, 但如果不知道要画多少圈的情况下, 就不知道在哪一圈结束, 判读出错, 然后就进入死循环, 运行超时。
运行通过后我看了别人的方法, 其实记起来就很简单， 这个螺旋矩阵, 规律有:
1） 每一圈的画法, 都是先从左到右, 接着从上到下， 然后右到左， 最后是下往上。
2) 每一圈的起点, 都是从左上角开始, 只要把握住这个点就可以了
3) 每一圈的每一个方向, 其长度是多少? 最外面一层是n, 每进入一层, 就要减 2, 比如上面的 4・4 矩阵, 里面那一圈的长度就比外面的相差 2.
4） 什么时候需要画多少圈? n/2 + n%2, 这是 java的写法, 记起来就是， 如果 n 是奇数, 就是除于 2 再加 1, 如果是偶数, 直接除于 2 就可以了。
总结
每一道算法题, 都需要考虑边界, 平时写代码也一样, 前面和后面, 开始和结束, 都需要考虑。
面向对象的思想, 就是要找出符合事物运行的规律, 因此当自己迷惑的时候, 不妨琢磨这个对象有什么特征吧， 不妨琢磨它有什么规律吧, 琢磨出来后, 往往得到的是表面的东西, 清晰明确的规律还需要进一步的思考, 就好比上面提到的螺旋矩阵, 一开始的琢磨只能得出最初浅的认识, 从上到下, 从左到右, 要想得到后面的规律, 起始点和边长, 需要进一步的思考。
如果数据已经排序， 查找的时候, 直接使用二分法吧, 他肯定是最高效的。
如果您觉得这篇文章对您的学习很有帮助, 请您也分享它, 让它能再次帮助到更多的需要学习的人. 您的支持将鼓励我继续创作 !