内容简介:ARTS 是陈浩(网名左耳朵耗子)在极客时间专栏里发起的一个活动,目的是通过分享的方式来坚持学习。每人每周写一个 ARTS:Algorithm 是一道算法题,Review 是读一篇英文文章,Technique/Tips 是分享一个小技术,Share 是分享一个观点。本周你将看到:
ARTS
ARTS 是陈浩(网名左耳朵耗子)在极客时间专栏里发起的一个活动,目的是通过分享的方式来坚持学习。
每人每周写一个 ARTS:Algorithm 是一道算法题,Review 是读一篇英文文章,Technique/Tips 是分享一个小技术,Share 是分享一个观点。
本周内容
本周你将看到:
- 二分查找类型题能还难到什么程度?
- 本周没有文章推荐;
- 本周也没有技巧可讲;
- 你真的在践行面向对象编程么?
Algorithm
本周的算法题是两道比较「高级」的二分查找题目:
LeetCode 378 Kth Smallest Element in a Sorted Matrix
LeetCode 719 Find K-th Smallest Pair Distance
其实二分查找这种题,在面试中经常扮演的角色是「一问就会,一写就错」。虽然算法的思想非常简单,但是要写出正确的代码还是有一些需要注意的地方,尤其是对于迭代过程中新的 mid 如何取值的问题。
我们先来看第一道题,求 排序 矩阵挣的第 K 小元素。当然,这题完全可以直接遍历矩阵然后给矩阵整体排序,最后直接返回排序数组的第 K 个数字。只不过这样的话就没用题目中给的两个条件:首先,矩阵中的行是从小到大排序的;其次,矩阵中的列也是从小到大排序的。这样排序的矩阵等效于从左上角到右下角大致是有序的。即,从左上角到右下角大致递增。
注意题目要求的是求第 K 小的数字,我们可以猜想某个数字(guess)就是要求的第 K 小数字,然后去矩阵中找不大于该数字的数字个数,这里记为 count. 如果 count >= k
那么就尝试让 guess 缩小,直到找到某个 guess 的值是最小的满足 count == k
的值。这时的 guess 就是我们要找的「第 K 小元素」。如果你做过「在排序数组中查找符合某种条件的下标」这类题目,那么你一定会觉得上面的过程非常熟悉,这就是二分查找的典型场景,只不过边界的判断依据变得复杂了一些。
下面是参考代码,最终利用到矩阵的特性之后时间复杂度下降到了 O(N*logN) 级别。
func kthSmallest(matrix [][]int, k int) int { d := len(matrix) mid, lo, hi := 0, matrix[0][0], matrix[d-1][d-1] for lo <= hi { mid = (lo + hi) / 2 curr := check(matrix, mid) // 下面两个条件其实可以合并成 curr <= k // 为了便于理解还是保持最原始的状态 if curr == k { if check(matrix, mid-1) < k { return mid } // if check(matrix, mid-1) == k hi = mid - 1 } else if curr > k { if check(matrix, mid-1) < k { return mid } hi = mid - 1 } else if curr < k { lo = mid + 1 } } return mid } func check(matrix [][]int, target int) int { d := len(matrix) count, i, j := 0, d-1, 0 // i = 0 只有在开始的时候,i<0 只有左下角都比 target 小才可能出现 for i >= 0 && j < d { // matrix[i][j] <= target 说明第 i 行第 j 列全都小于等于 target // count 增加列长:i+1 if matrix[i][j] <= target { count += i + 1 j++ } else { // matrix[i][j] > target 说明本行全部大于 target // 向上移动一行 i-- 再比较 i-- } } return count }
接着来看第二道题,求数组中第 K 小的「数字距离」。因为两道题目实在是太类似了,具体思维过程不再赘述。唯一需要注意的就是,题中的「距离」不包含每个数字和自己的「距离」。也就是寻找两个数字的差的过程中,两个指针需要指向不同的数字。下面上代码。
// 这道题和 378.kth-smallest-element-in-a-sorted-matrix 非常类似 // 只是在求 mid 满足要求的数量时稍微有点区别 // 看来二分查找类型的题难度提升只能在边界判断的位置做文章了 func smallestDistancePair(nums []int, k int) int { // 先给 nums 排序,测试例要求 nums 长度最少是 2, 不用做长度判断 sort.Slice(nums, func(i, j int) bool { return nums[i] < nums[j] }) mid, lo, hi := 0, 0, nums[len(nums)-1]-nums[0] for lo <= hi { mid = (lo + hi) / 2 c := shorterCount(nums, mid) if c >= k { if shorterCount(nums, mid-1) < k { return mid } hi = mid - 1 } else { lo = mid + 1 } } return mid } // 返回差值小于等于 guess 的数对的数量 // @guess 猜测的满足要求的数字 // 可以 AC 但是效率不高毕竟 O(n^2) // func shorterCount(nums []int, guess int) int { // var count int // for i := 0; i < len(nums)-1; i++ { // for j := i+1; j < len(nums); j++ { // if nums[j]-nums[i] <= guess { // count++ // } // } // } // return count // } // 返回差值小于等于 guess 的数对的数量 // @guess 猜测的满足要求的数字 // 复杂度应该介于 O(n) 和 O(n^2) 之间,但判题系统给出的时间提升很多 10% -> 90% func shorterCount(nums []int, guess int) int { left, count := 0, 0 for right := 1; right < len(nums); right++ { for left < len(nums) && nums[right] - nums[left] > guess { left += 1 } count += right - left } return count }
Review 文章推荐
本周因为实在太忙(lan),没有直的推荐的问题件。哭哭。
Tip 编程技巧
本周因为实在太忙(lan),没有收集到任何一个小技巧。又哭哭。
Share 灵光一闪
你能准确回答「面向对象的三个特征」是什么,以及用简短的代码给出一个例子吗?
我想对于刚工作时间不长的新人 码农 来说,这个问题不难回答。大家早已将「封装」「继承」「多态」背的滚瓜烂熟,将之前默写过几遍的著名「动物园」例子潇洒的写出来以证明自己深谙面向对象之禅。但是对于很多工作了几年,甚至五年以上的老(cai)鸟来说,不是每个人都能把上面的三点时常放在心上。
一切都要从这周五的一个功能开发说起,简单来说就是增加一个小小的数据备份任务。然后因为数据有若干种,每种数据需要使用不同的 struct 以及相对应的 DB 读写操作。这其实就是每个老鸟在菜鸟时期滚瓜烂熟的动物园模型的变型,至少可以用多态的方式减少绝大部分的重复代码。但我在项目里看到了从前年到今年,包括三四位同时在增加针对不同类型的数据备份时写的「重复代码」。这些重复代码如果 diff 一下的话,可能只有 logger 的参数和写入 DB 的表名不同而已,而我却看到那个目录里有这样几乎完全重复的十来个文件。这些文件完全可以被一个抽象的 interface 和以多态的方式使用上面 interface 的不同实现的两个文件取代,但是这些「自己复制自己」的代码就这样骄傲的罗列在项目里。
可能业务代码写太多连基本的抽象能力都丧失了,一个简单的「接口+实现」的抽象就能节省至少十个文件的代码量的事情,居然没有一个人想到。但是也可能事实是让代码看起来「多」会增加隐形 KPI.
本周阅读列表
- 极客时间 MySQL 专栏
索引 上
索引 下
全局锁
行锁 - reviewdog 曹春晖
Golang 代码检查工具,可以帮助提升项目质量,能检查出未处理的 error 以及 - 一个案例彻底弄懂如何正确使用 mysql inndb 联合索引
文章确实对联合索引的某些情况解释的很好,但是并不能「一文读懂」。文中的联合索引示例图确实很详细。看完之后还是有个疑问:为什么联合索引第一个字段作为范围条件时,联合索引中的第二个字段不能应用到索引中去(确实 explain 中可以看到 key_len = 4),而交换 status 和 audit 在联合索引中的顺序之后就可以应用到第二个索引字段? - A whirlwind tour of Go’s runtime environment variables
介绍 Go 的一些运行时相关的参数,比如 GOTRACEBACK GOMAXPROCS gctrace schedtrace 等等这些。
欢迎关注我们的微信公众号,每天学习Go知识
以上所述就是小编给大家介绍的《ARTS 第9周 LeetCode 378 二分法 | 面向对象三要素你还记得吗?》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Python Web开发:测试驱动方法
Harry J.W. Percival / 安道 / 人民邮电出版社 / 2015-10 / 99
本书从最基础的知识开始,讲解Web开发的整个流程,展示如何使用Python做测试驱动开发。本书由三个部分组成。第一部分介绍了测试驱动开发和Django的基础知识。第二部分讨论了Web开发要素,探讨了Web开发过程中不可避免的问题,及如何通过测试解决这些问题。第三部分探讨了一些高级话题,如模拟技术、集成第三方插件、Ajax、测试固件、持续集成等。本书适合Web开发人员阅读。一起来看看 《Python Web开发:测试驱动方法》 这本书的介绍吧!
JS 压缩/解压工具
在线压缩/解压 JS 代码
SHA 加密
SHA 加密工具