乐趣区

ARTS-第9周-LeetCode-378-二分法-面向对象三要素你还记得吗

jiezi

ARTS

ARTS 是陈浩（网名左耳朵耗子）在极客工夫专栏里发动的一个流动，目标是通过分享的形式来保持学习。

每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。

本周内容

本周你将看到：

  1. 二分查找类型题能还难到什么水平？
  2. 本周没有文章举荐；
  3. 本周也没有技巧可讲；
  4. 你真的在践行面向对象编程么？

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 等等这些。
退出移动版