共计 3545 个字符,预计需要花费 9 分钟才能阅读完成。
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 等等这些。