ARTS 第18周

2019-08-08 本文已影响0人陈卧虫

ARTS 第18周分享

[TOC]

Algorithm

56. Merge Intervals

[medium]

[题目描述]

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

[解题思路]

通过观察可发现，相邻的两个区间存在以下特点才可合并：
- 左区间头元素大于右间头元素
- 左区间尾元素大于等于右区间头元素，同时左区间尾元素小于右区间尾元素

[参考代码]

func merge(intervals [][]int) [][]int {
    /*
    // 先将整个集合中的所有区间按从小到大排序，
    // 遍历整个区间集合
        // 判断相邻的两个区间：左边区间的结尾 与 右边区间的开始比较，
        // 如果 左结尾大于等于右开始，将两区间合并，存入一个新的集合，否则，直接存入
    // 返回新的集合
    */

    // 先将整个集合中的所有区间按从小到大排序，
    quickSortIntervals(intervals, 0, len(intervals)-1)

    //tmp := make([][]int, 0)
    // 遍历整个区间集合
    for i := 0; i < len(intervals)-1; {
        // 判断相邻的两个区间：左边区间的结尾 与 右边区间的开始比较，
        // 如果 左结尾大于等于右开始，将两区间合并，存入一个新的集合，否则，直接存入
        if intervals[i][1] >= intervals[i+1][0] {

            if intervals[i][1] <= intervals[i+1][1] {
                intervals[i+1][0] = intervals[i][0]
                intervals = append(intervals[:i], intervals[i+1:]...)
            } else {
                intervals = append(intervals[:i+1], intervals[i+2:]...)
            }
        } else {
            i++
        }
    }
    return intervals
}

func quickSortIntervals(intervals [][]int, left, right int) {
    // 选择一个主元，将大于移到主元的右边，小于的移动到右边
    // 将主元左边的元素再次进行排序操作， 左右两边为同一个元素
    if left >= right {
        return
    }
    mid := partition(intervals, left, right)

    // left
    quickSortIntervals(intervals, left, mid-1)
    quickSortIntervals(intervals, mid+1, right)
}

// 对半排序
func partition(intervals [][]int, left, right int) (mid int) {
    /*
    将最有一个元素当做主元，用一个指针从数组的倒数第二个开始遍历这个数组，用另一个指针指向数组的开头
    遍历整个数组，直到两个指针相交
    将主元置于中间
    */
    pivot := intervals[right][0]
    v := left
    r := right - 1

    for v <= r {
        if intervals[r][0] < pivot {
            intervals[v], intervals[r] = intervals[r], intervals[v]
            v++
        } else {
            r--
        }
    }

    intervals[v], intervals[right] = intervals[right], intervals[v]
    return v
}

57. Insert Interval

[hard]

[题目描述]

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

[解题思路]

从题意可得出，一共需要两部：先有序插入，再合并
- 有序插入：只需遍历数组，在合适的位置插入即可
- 合并：通过第57题的方法合并

[参考代码]

func insert(intervals [][]int, newInterval []int) [][]int {
    // 将新的端点插入到列表中，然后重新排序

    // 判断是否为空
    if len(intervals) == 0 {
        return append(intervals, newInterval)
    }

    // 将新端点有序的插入
    i := 0
    for i=0; i<len(intervals); i++ {
        if intervals[i][0] >= newInterval[0] {
            break
        }
    }
    rear := append([][]int{}, intervals[:]...)
    intervals = append(intervals[:i], newInterval)
    intervals = append(intervals, rear...)

    // 合并重复的元素: 将不重合的元素存入到新数组中，
    // 遍历所有元素，将当前遍历到的元素与新数组中的最后一个元素对比，如果重合就去重；如果不重合直接存入新数组中
    new := make([][]int, 0)
    new = append(new, intervals[0])
    for i:=1; i<len(intervals); i++ {
        if new[len(new)-1][1] >= intervals[i][0] {
            if new[len(new)-1][1] < intervals[i][1] {
                new[len(new)-1][1] = intervals[i][1]
            }
        } else {
            new = append(new, intervals[i])
        }
    }
    return new
}

Review

Tips

分库分表实践：https://mp.weixin.qq.com/s/cGJIjv3ep-6whkC0j6878A

什么时候适合分表：当某张表的数据量已经达到千万甚至上亿，同时日增数据量在 2% 以上。对这张表的写入和查询都已经影响到正常业务执行，比如查询速度明显下降，数据库整体 IO 居高不下等。
水平分表：将一张大表(table)数据通过某种路由算法将数据尽可能的均匀分配到 N 张小表中(table_1, table_2, table_3)。
分表策略：
- (range)第一种是按照范围划分：比如我们可以将某张表的创建时间按照日期划分存为月表
  - 好处是自带水平扩展，不需要过多干预。
  - 缺点是可能会出现数据不均匀的情况（比如某个月请求暴增）
- (hash) hash+mod 的组合,将我们需要分表的字段进行一次散列运算，使得经过散列的数据尽可能的均匀并且不重复。
分表数量选择: 至少需要保证分好之后的小表在业务发展的几年之内都不会出现单表数据量过大（比如达到千万级），和 HashMap 一样，也建议得是 2^n
Range + Hash: 可以在 Mod 分表的基础上再分为月表，借助于 Range 自身的扩展性
数据迁移：
- 分表改造上线后，所有新产生的数据写入分表，但对历史数据的操作还走老表，这样就少了数据迁移这一步骤。
- 只是需要在操作数据之前做一次路由判断，当新数据产生的足够多时（我们是两个月时间），几乎所有的操作都是针对于分表，再从库启动数据迁移，数据迁移完毕后将原有的路由判断去掉。
- 最后所有的数据都从分表产生和写入。

什么是CDN：https://mp.weixin.qq.com/s/msmYsB_tviixfbWMKlvu8g

CDN: Content Delivery Network ,内容分发网络
当我们访问某一个网站时，就是将请求包通过网络传输给一台特定的服务器。
- 首先就需要解析出该域名所对应的的IP地址，这就需要通过DNS服务器帮助
- 然后将Http请求包通过网络路由到IP地址所对应的服务器
域名解析：
- 将一个域名解析为一个IP地址
- 将一个域名解析为另外一个域名（该域名的一个CNAME）
如果这个域名对应的是IP地址，则返回这个IP地址；如果这个域名对应的是CNAME，则继续查找CNAME域名的IP地址，然后将该地址返回给请求发送者，CNAME实际上在域名解析的过程中承担了中间人（或者说代理）的角色，这是CDN实现的关键。
为了提高访问速度，在全国各地都部署一模一样的服务器就行了，专业一点叫冗余。
CDN是为了改善互联网的服务质量的。通俗一点说其实就是提高访问速度。将资源分配到各台服务器
服务器上的资源分为两种：静态资源与动态资源。
静态资源：这种资源通常是很少变动的，比如图片，视频，css，javascript等等
动态资源：这种资源不同用户不同时刻访问通常是不一样的，比如ftl，jsp等等。
静态资源通常不涉及到数据库，所以成本也比较低，而且也能提高用户的访问速度，所以通常在每个服务器上只部署静态资源。
需要一个特殊的DNS服务器，这个特殊DNS需要知道：
- 用户当前所在位置：直接从用户请求里提取出用户的ip地址
- 还需要知道用户现在访问的这个域名对应哪些IP地址，以及这个IP地址分别在哪?：
CDN提供商肯定知道他们公司在哪些地方部署了机器以及它们的IP地址，所以这个问题只能有CDN提供商来解决，CDN提供商会提供这个特殊的DNS服务器，我们叫做 CDN专用DNS服务器。
普通DNS服务器发现该域名对应的也是一个DNS服务器，那么会将域名解析工作转交给该DNS服务器，该DNS服务器就是CDN专用DNS服务器。

缓存雪崩和缓存击穿的区别：

「缓存雪崩」的根本问题是：缓存由于某些原因未起到预期的缓冲效果，导致请求全部流转到数据库，造成数据库压力过重。
「缓存穿透」指的是所需的数据在DB中一直不存在的情况（老师傅也不会修）。并且，由于DB中数据不存在，所以自然每次从缓存中也找不到
「缓存穿透」和「缓存雪崩」最终产生的效果是一样的，就是因为大量请求流到DB后，把DB拖垮
「缓存雪崩」问题只要数据从db中找到并放入缓存就能恢复正常（徒弟休假归来）
缓存雪崩解决方法：缓存空对象，哪怕从db中取出的数据是“空（null）”，也把它丢失到缓存中。这样一来，虽然缓存中存在着一个value为空的数据，但是至少他能表示“数据库里也没有不用找了”。

本周阅读

第五周：1, 2, 3, 5
如何找到两个数组的中位数: https://mp.weixin.qq.com/s/OE4lHO8-jOIxIfWO_1oNpQ
数据库软件架构，到底要设计些什么？: https://mp.weixin.qq.com/s/yyh013dDNfaiT0wtBihCLQ
分库分表实践: https://mp.weixin.qq.com/s/cGJIjv3ep-6whkC0j6878A
Go module的使用: https://mp.weixin.qq.com/s/1GbOOJ0UdbvanObLGKbzfg
一次使用 Go 语言编写脚本的经历: https://mp.weixin.qq.com/s/57vCEHqiLC_V6Re4J0M0YQ

清晰胜过聪明: https://mp.weixin.qq.com/s/rhlr_l4o2py87kS3PIuZVg
搞明白CDN: https://mp.weixin.qq.com/s/msmYsB_tviixfbWMKlvu8g
分布式系统关注点——缓存背后的“毁灭种子”: https://mp.weixin.qq.com/s/q-R7kv4696LooHy3Hn-H1A
什么叫 CQRS: https://mp.weixin.qq.com/s/YBzq1vobSaIQkxnYhKWQIQ
Linux是怎么来的？https://mp.weixin.qq.com/s/HiPFE34P7AkNBNdRkLti4A

并发用户数与TPS之间的关系: https://www.cnblogs.com/qmfsun/p/5511557.html
多账户的统一登录方案：https://mp.weixin.qq.com/s/rI5XGtsBGISLgJvSrcHkGg
Zookeeper请求处理原理分析： https://mp.weixin.qq.com/s/At0dcl97ywcY0uLsEuuX1A

华为得到的，小米坚持的，拼多多的真正红利: https://mp.weixin.qq.com/s/DsfG7ZWqjhphkr4kvmFDSw