算法题

1. 大数取TOPK问题 堆：O(nlogk) 快速选择第K大的数，复杂度是O(N)。然后将比它小的全部拿出来，复杂度是O(N)。因此总复杂度是O(2N) = O(N)
2. 大数排序问题 分治+K路归并（K路归并可以用堆优化）

机器学习

相关资料

1. agging与boosting两种集成模型的偏差和方差的理解
2. 模型任何之——Bagging和Boostting的区别
3. 机器学习算法比较

相关题

1. 监督学习与无监督学习的区别
2. Xgboost与LightGBM
3. 判别式模型与生成模型

其它

数学相关

• 中心极限定理：在适当的条件下，大量相互独立随机变量的均值经适当标准化后依分布收敛于正态分布
• 大数定理：在试验不变的条件下，重复试验多次，随机事件的频率近似于它的概率
• 大数定律成立条件较宽松。

OSI七层模型

TCP

TCP是TCP/IP体系中一个非常复杂的协议。

1. TCP是面向连接的运输层 协议。面向连接的意思是：用之前，必须先建立TCP连接；用完后，必须释放连接。
2. TCP连接只能是点对点的。
3. TCP提供全双工通信，即允许通信双方在任何时候都能发送数据。（通过发送缓存和接受缓存来实现）
4. TCP连接的端点叫：套接字(socket) = (ip地址：端口号)
5. 滑动窗口是TCP的精髓：发送方每收到一个确认，就把发送窗口前滑一。
6. TCP首部20字节，后面4n字节是内容。

TCP三次握手：

• 第二次对话保证：乙能听懂甲
• 第三次对话保证：甲能听懂乙

TCP四次挥手

• 第一对FIN和ACK保证了乙知道了要关机；第二对FIN和ACK保证了乙已经关机；

Java内存泄漏

但是在Java中，我们不用（也没办法）自己释放内存，无用的对象由GC自动清理，这也极大的简化了我们的编程工作。但，实际有时候一些不再会被使用的对象，在GC看来不能被释放，就会造成内存泄露。

简单例子：

1
2
3
4
5
6
7

public class Simple {
    Object object;
    public void method1(){
        object = new Object();
        //...其他代码
    }
}

​ 这里的object实例，其实我们期望它只作用于method1()方法中，且其他地方不会再用到它，但是，当method1()方法执行完成后，object对象所分配的内存不会马上被认为是可以被释放的对象，只有在Simple类创建的对象被释放后才会被释放，严格的说，这就是一种内存泄露。解决方法就是将object作为method1()方法中的局部变量。当然，如果一定要这么写，可以改为这样：

1
2
3
4
5
6
7
8

public class Simple {
    Object object;
    public void method1(){
        object = new Object();
        //...其他代码
        object = null;
    }
}

解决的原则就是尽量减小对象的作用域（比如android studio中，上面的代码就会发出警告，并给出的建议是将类的成员变量改写为方法内的局部变量）以及手动设置null值。

参考文献

1. 通俗大白话来理解TCP协议的三次握手和四次分手
2. TCP协议中的三次握手和四次挥手(图解)

B树是为实现高效的磁盘存取而设计的多叉平衡搜索树。这个概念在文件系统，数据库系统中非常重要。

B树是一种查找树，我们知道，这一类树（比如二叉查找树，红黑树等等）最初生成的目的都是为了解决某种系统中，查找效率低的问题。B树也是如此，它最初启发于二叉查找树，二叉查找树的特点是每个非叶节点都只有两个孩子节点。然而这种做法会导致当数据量非常大时，二叉查找树的深度过深，搜索算法自根节点向下搜索时，需要访问的节点也就变的相当多。如果这些节点存储在外存储器中，每访问一个节点，相当于就是进行了一次I/O操作，随着树高度的增加，频繁的I/O操作一定会降低查询的效率。

这里有一个基本的概念，就是说我们从外存储器中读取信息的步骤，简单来分，大致有两步：

1. 找到存储这个数据所对应的磁盘页面，这个过程是机械化的过程，需要依靠磁臂的转动，找到对应磁道，所以耗时长。
2. 读取数据进内存，并实施运算，这是电子化的过程，相当快。

综上，对于外存储器的信息读取最大的时间消耗在于寻找磁盘页面。那么一个基本的想法就是能不能减少这种读取的次数，在一个磁盘页面上，多存储一些索引信息。B树的基本逻辑就是这个思路，它要改二叉为多叉，每个节点存储更多的指针信息，以降低I/O操作数。

本文回顾并总结了编程之美搜索引擎端的相关原理

非比较排序

插入排序、归并排序、堆排序、快速排序这四种排序算法，他们的运行时间上界不会超过O(nlgn)。这些算法都有一个有趣的性质：在排序的最终结果中，各元素的次序依赖于它们之间的比较。我们把这类排序算法称为比较排序。

可以证明，基于比较的排序算法在最坏情况下的时间下界是Ω(nlgn)。堆排序和归并排序的运行时间上界为O(nlgn)，因此这两种排序算法都是渐进最优的比较排序算法。

而非基于比较的排序，如计数排序，桶排序，和在此基础上的基数排序，则可以突破O(NlogN)时间下限，达到线性时间复杂度\[O(n)\]。但要注意的是，非基于比较的排序算法的使用都是有条件限制的，例如元素的大小限制，相反，基于比较的排序则没有这种限制(在一定范围内)。但并非因为有条件限制就会使非基于比较的排序算法变得无用，对于特定场合有着特殊的性质数据，非基于比较的排序算法则能够非常巧妙地解决。

基数排序：O(dn) (d次调用桶排序)，空间复杂度 O(k)

桶排序：O(n)时间复杂度，O(n)空间复杂度

计数排序：O(n)时间复杂度，O(k)空间复杂度，每一个元素都是整数，并且位于0到k - 1之间

计数排序

计数排序假设n个输入元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。当k=O(n)时，排序的运行时间为Θ(n)。

计数排序的思想是，对每一个输入元素，计算小于它的元素个数，如果有10个元素小于它，那么它就应该放在11的位置上，如果有17个元素小于它，它就应该放在18的位置上。当有几个元素相同时，这一方案要略做修改，因为不能把它们放在同一个输出位置上。下图展示了实际的运行过程。

计数排序

构造辅助数组C，C的长度为k。第一次遍历A后，得到[0,k)区间上每个数出现的次数，将这些次数写入C，得到图(a)的结果。然后把C中每个元素变成前面所有元素的累加和，得到图(b)的结果。接下来，再次从后向前遍历数组A，根据取出的元素查找C中对应下标的值，再把这个值作为下标找到B中的位置，即是该元素排序后的位置。例如，图中A的最后一个元素是3，找到C[3]是7，再令B[7]=3即可，然后顺便把C[3]减一，这是防止相同的数被放到同一个位置。

计数排序的时间代价可以这样计算，第一次遍历A并计算C所花时间是Θ(n)，C累加所花时间是Θ(k)，再次遍历A并给B赋值所花时间是Θ(n)，因此，总时间为Θ(k + n)。在实际中，当k=O(n)时，我们一般会采用计数排序，这时的运行时间为Θ(n)。

基数排序

对于一组数据，我们可以按照每一位对它们进行排序。比如，考虑下面一组十进制数 329 457 839 355

先按最后一位从小到大排序，得到 355 457 329 839

再按中间一位从小到大排序，得到 329 839 355 457

最后按第一位从小到大排序，得到 329 355 457 839

其中，对任何一位的排序算法必须是稳定的，即相同数字不能改变它们的前后顺序。

基数排序算法的运行时间很容易计算，对于n个k进制d位数，假如每一位的排序使用计数排序算法，则该位排序用时为Θ(n + k)，总共d位数，总排序用时就是Θ(d(n + k))。当d为常数且k=O(n)时，总排序时间为Θ(n)。

桶排序

桶排序假设输入是由一个随机过程产生，该过程将元素均匀、独立地分布在[0,1)区间上。

我们将[0,1)区间划分为n个相同大小的子区间，称为桶。然后将输入数据分别放到各个桶中。如果数据分布得很均匀，每个桶中的数据就不会太多，都会维持在常数量级。我们先对每个桶中的元素排序，然后把所有桶中的元素顺序列出来即可。下图为n=10的一个案例。

桶排序.png

创建一个长度也为10的数组，将A中的元素按照大小找到B中合适的位置，插入链表。之后，分别对B中每个链表中的元素执行插入排序。最后将B中的所有元素依次取出即可。

现在分析桶排序的时间代价。将A中元素放入B用时Θ(n)，B中每个链表执行插入排序的用时，可以证明是O(2 - 1/n)，于是总用时就是Θ(n) + n * O(2 - 1/n) = Θ(n)。具体证明过程比较难理解，这里我想给出一个容易理解的解释，虽然不一定对，但还是可以帮助理解为什么总用时是Θ(n)。n个数放入n个桶，平均下来每个桶只有一个数，在实际中，可能有的多有的少，但都不会差得太离谱。因此我们可以认为每个桶中只有常数个数，那么对常数个数执行插入排序所用的时间当然也就是O(1)了。于是n个桶总用时就是O(n)，加上前面的Θ(n)，桶排序总用时就是Θ(n)了。

Leetcode题

Jump Game II

给一个数组[2,3,1,1,4]，每个元素代表当前可以跳跃的步数。求问最少跳多少次可以从idx = 0跳到idx = n - 1

dp超时，只能用贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int jump(int[] nums) {
    int end = 0;
    int endGlobal = 0;
    int start = 0;
    int step = 0;
    while (endGlobal < nums.length - 1){
        for(int i = start; i <= end; ++i){
            endGlobal = Math.max(endGlobal, i + nums[i]);
        }
        start = end;
        end = endGlobal;
        ++step;
    }
    return step;
}

Remove K Digits

给一个str代表一个数字。给一个k。求删掉k个字符后，能够变成的最小数字。

方法一，dp(超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

String[][] memo;
String num;
int n;
private String helper(int idx, int k){
    if(idx == -1){
        return "";
    }
    if(memo[idx][k] != null) return memo[idx][k];
    String min = num;
    for(int i = idx; i + 1 >= k; --i){
        String temp = helper(i - 1, k - 1) + num.substring(i + 1, idx + 1);
        if(temp.compareTo(min) < 0){
            min = temp;
        }
    }
    memo[idx][k] = min;
    return min;
}
public String removeKdigits(String num, int k) {
    this.num = num;
    this.n = num.length();
    memo = new String[n][k+1];
    for(int i = 0; i < n; ++i){
        memo[i][0] = num.substring(0, i + 1);
        if(i < k)memo[i][i+1] = ""; // k == i+1时，必须把前k个全部删掉才可以
    }
    String result = helper(n - 1, k);
    if(result.length() == 0) result = "0";
    // 去掉前导零
    int i = 0;
    for(i = 0; i < result.length() - 1; ++i){
        if(result.charAt(i) == '0') continue;
        else break;
    }
    return result.substring(i);
}

方法二，贪心

假设数字abcdef ，从左到右看。如果c > a ，那么明显删掉c比删掉a合适。

那么就要存下来之前遇到的最大值，然后如果之前的比较大，就把之前的删掉。如果当前大，就把当前删掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public String removeKdigits(String num, int k) {
        if(k == 0) return num;
        char[] stack = new char[num.length()];
        Arrays.fill(stack, '0');
        int stackTail = -1;
        int digit = num.length() - k;
        for(int i = 0; i < num.length(); ++i){
            while(k > 0 && stackTail >= 0 &&num.charAt(i) < stack[stackTail]) {
                --k; // 如果遇到之前那个值大于后面的值，那就把它删掉
                --stackTail;
            }
            stack[++stackTail] = num.charAt(i);
        }
        // 去掉前导0
        int stackHead = 0;
        while (stackHead < digit && stack[stackHead] == '0') ++stackHead;
        if(stackHead == digit) return "0";
        else return new String(stack, stackHead, digit - stackHead);
    }

例如goo.gl

系统设计常见误区

以下几个是误区

• 系统一定巨大无比 —— ×
• 必须用NoSQL —— ×
• 必须是分布式 —— ×

不可以扔关键词，必须一步步分析。

4S分析法

1. 提问：分析功能/需求/QPS/存储容量——Scenario
2. 画图：根据分析结果设计“可行解”—— Service+Storage
3. 进化：研究可能遇到的问题，优化系统 —— Scale

分析需求

需求有两个：

• 根据长URL生成短URL
• 根据短URL还原长URL

QPS?

假设这个是用来给微博做短网址的跳转。那么QPS能有多少？

1. 询问微博日活用户 —— 约100M
2. 推算产生一条Tiny URL的QPS
   • 假设每个用户平均每天发0.1条微博，
   • 平均写QPS = 100M * 0.1 / 86400 ~ 100
   • 峰值QPS = 100 * 2 = 200
3. 推算点击一条Tiny URL的QPS
   • 假设每个用户平均点1个Tiny URL
   • 平均读QPS = 100M * 1 / 86400 ~ 1k
   • 峰值QPS = 2k
4. 推算每天产生的新的 URL 所占存储
   • 100M * 0.1 ~ 10M 条
   • 每一条 URL 长度平均 100 算，一共1G
   • 1T 的硬盘可以用 3 年

前3点：2k QPS ，一台SSD支持的MySQL完全可以搞定！

服务——逻辑块聚类与接口设计

TinyUrl只有一个UrlService

• 本身就是一个小Application
• 无需关心其他的

函数设计

• UrlService.encode(long_url)
• UrlService.decode(short_url)

访问端口设计

• GET /<short_url>
  • return a Http redirect response
• POST /data/shorten/
  • Data = {url: http://xxxx }
  • Return short url

数据存取

两个步骤：

• 选择存储结构
• 细化数据表

选择存储结构

SQL vs NoSQL

• 是否需要支持 Transaction（事务）？
  • NoSQL不支持Transaction
  • 是否需要丰富的 SQL Query？
• NoSQL的SQL Query不是太丰富
  • 也有一些NoSQL的数据库提供简单的SQL Query支持
• 是否想偷懒？
  • 大多数 Web Framework 与 SQL 数据库兼容得很好
  • 用SQL比用NoSQL少写很多代码
• 是否需要Sequential ID？
  • SQL 为你提供了 auto-increment 的 Sequential ID。也就是1,2,3,4,5 …
  • NoSQL的ID并不是 Sequential 的
• 对QPS的要求有多高？
  • NoSQL 的性能更高
• 对Scalability的要求有多高？
  • SQL 需要码农自己写代码来 Scale
  • 还记得Db那节课中怎么做 Sharding，Replica 的么？
• NoSQL 这些都帮你做了

选择

• 是否需要支持 Transaction？——不需要。NoSQL +1
• 是否需要丰富的 SQL Query？——不需要。NoSQL +1
• 是否想偷懒？——Tiny URL 需要写的代码并不复杂。NoSQL+1
• 对QPS的要求有多高？—— 经计算，2k QPS并不高，而且2k读可以用Cache，写很少。SQL +1
• 对Scalability的要求有多高？—— 存储和QPS要求都不高，单机都可以搞定。SQL+1
• 是否需要Sequential ID？—— 取决于你的算法是什么 : 如何将Long URL 转化为 Short URL

如何将Long URL 转化为 Short URL

算法1 使用哈希函数 Hash Function（不可行）

比如取 Long Url 的 MD5 的最后 6 位——这个方法肯定是有问题的 • 优点：快 • 缺点：难以设计一个没有冲突的哈希算法

算法2：随机生成 + 数据库去重

随机一个 6 位的 ShortURL，如果没有被用过，就绑定到该 LongURL • 伪代码如下： • 优点：实现简单 • 缺点：生成短网址的长度随着短网址越来越多变得越来越慢 • 可行性：其实能凑合用。在生活中有很多随机编码的，例如机票码、酒店码，是不可重复的，就是用这种方法弄的。

算法3：进制转换 Base62

• Base62
  • 将6位的short url看成一个62进制的数（0-9,a-z,A-Z）
  • 每个short url对应到一个整数
  • 该整数对应数据库表的主键——Sequential ID
• 6位可以表示不同的URL有多少？
  • 5位 = \(62^5\) = 9亿
  • 6位 = \(62^6\) = 570亿
  • 7位 = \(62^7\) = 35000亿
• 优缺点
  • 优点：效率高
  • 缺点：依赖于全局的自增ID

算法2与3的比较

• 基于随机生成的方法 需要根据 Long 查询 Short，也需要根据 Short 查询 Long。基本上work solution如下图所示： 如果选择用 SQL 型数据库，表结构如下： 并且需要对shortKey和longURL分别建索引 • 什么是索引？ • 索引的原理？ 也可以选用 NoSQL 数据库，但是需要建立两张表（大多数NoSQL数据库不支持二级索引）。以 Cassandra 为例子 第一张表：根据 Long 查询 Short row_key=longURL, column_key=ShortURL, value=null or timestamp 第二张表：根据 Short 查询 Long row_key=shortURL, column_key=LongURL, value=null or timestamp
• 基于进制转换的方法 因为需要用到自增ID（Sequential ID），因此只能选择使用 SQL 型数据库。表单结构如下，shortURL 可以不存储在表单里，因为可以根据 id 来进行换算

优化

读操作的优化

既然读操作比较多，那么可以用cache的方式去提速。

• cache里存什么？
  • long to short(生成新short url时需要)
  • short to long(查询short url时需要)
• 查询的流程图：

如何提速

• 利用地理位置信息加速
• 优化服务器速度
  • 不同地区，使用不同Web服务器
  • 通过DNS解析不同地区的用户到不同的服务器
• 优化数据访问速度
  • 使用Centralized MySQL + Distributed Memcached
  • 一个MySQL配多个Memcached, Memcached跨地区分布 ​

如何扩展机器

• 什么时候需要多台服务器？

  • Cache资源不够
  • 写操作越来越多
  • 请求太多，无法通过Cache满足

• 增加多台数据库可以优化什么？

  • 解决存不下的问题——Storage角度（TinyURL一般遇不到这种问题）
  • 解决忙不过来的问题——QPS角度
  • TinyURL主要是什么问题？？——忙不过来的问题

• 如何解决忙不过来的问题？

  拆分 ：

  • 纵向切分？不同列放不同数据库？不可行！
  • 横向拆分？一个表放多个机器？ 就将不同的short key放到不同的机器上，能解决short 2 long问题。但此时如果要解决long 2 short问题，就不好搞了。可能需要遍历每一个机器。但是回过来问，long 2 short这个问题的意义是什么。没有必要根据long查询short哇。一个long可以对应多个short，因此没必要一个long对应一个short。

• 如果最开始shortkey为6位，那就增加一位前置位：

  • AB1234 --> 0AB1234（该前置位由hash(long_url)%62得到（可以用consistent hash算法），因此是唯一的。这个前置位可以作为机器的ID等）
  • 另一种做法，把第一位单独留出来做sharding key，总共还是6位

那么当前的架构就变成了：

还有优化的地方吗

网站服务器 (Web Server) 与 数据库服务器 (Database) 之间的通信问题。

中心化的服务器集群（Centralized DB set）与 跨地域的 Web Server 之间通信较慢。比如中国的服务器需要访问美国的数据库那么何不让中国的服务器访问中国的数据库？

如果数据是重复写到中国的数据库，那么如何解决一致性问题？——很难解决

中国的用户访问时，会被DNS分配中国的服务器，这非常的慢。

而中国的用户访问的网站一般都是中国的网站，所以我们可以按照网站的地域信息进行 Sharding。（如何获得网站的地域信息？只需要将用户比较常访问的网站弄一张表就好了）

中国的用户访问美国的网站怎么办？那就让中国的服务器访问美国的数据好了，反正也不会慢多少。中国访问中国是主流需求，优化系统就是要优化主要的需求

能不能提供个性化的URL?

就是把后面的短url个性化。可以的，只要与其它short不重复就行了。如下所示：

1
2
3

shortURL   longURL
1234AB     www.baidu.com
bd         www.baidu.com

但最好不要新开一列custom。因为这样很浪费空间。

我们常常使用 JDK 提供的迭代接口进行 Java 集合的迭代。

1
2
3
4
5

Iterator iterator = list.iterator();
        while(iterator.hasNext()){
            String string = iterator.next();
            //do something
        }

迭代其实我们可以简单地理解为遍历，是一个标准化遍历各类容器里面的所有对象的方法类，它是一个很典型的设计模式。Iterator 模式是用于遍历集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来，从而避免向客户端暴露集合的内部结构。 在没有迭代器时我们都是这么进行处理的。如下：

对于数组我们是使用下标来进行处理的:

1
2
3
4
5
6

int[] arrays = new int[10];
   for(int i = 0 ; i < arrays.length ; i++){
       int a = arrays[i];
       //do something
   }

对于 ArrayList 是这么处理的:

1
2
3
4
5
6

List<String> list = new ArrayList<String>();
   for(int i = 0 ; i < list.size() ;  i++){
      String string = list.get(i);
      //do something
   }

对于这两种方式，我们总是都事先知道集合的内部结构，访问代码和集合本身是紧密耦合的，无法将访问逻辑从集合类和客户端代码中分离出来。同时每一种集合对应一种遍历方法，客户端代码无法复用。 在实际应用中如何需要将上面将两个集合进行整合是相当麻烦的。所以为了解决以上问题， Iterator 模式腾空出世，它总是用同一种逻辑来遍历集合。使得客户端自身不需要来维护集合的内部结构，所有的内部状态都由 Iterator 来维护。客户端从不直接和集合类打交道，它总是控制 Iterator，向它发送”向前”，”向后”，”取当前元素”的命令，就可以间接遍历整个集合。

上面只是对 Iterator 模式进行简单的说明，下面我们看看 Java 中 Iterator 接口，看他是如何来进行实现的。

经典扫描线

经典问题：数飞机问题

给一些飞机飞行的时间区间。求天上最多有多少个飞机同时在飞。

例如给

1
2
3
4
5

[1,3]
[2,4]
[5,6]

求天上同时有多少架飞机

思路一，细粒度扫描

遍历每个时刻粒度，检测每个时刻有多少个飞机

思路二，扫描线！

不需要检测每一时刻，只需要检测起点或者终点的位置！（交点变化的位置只有起点或者终点）

1. 将数据拆成二元组 [起点/终点标识，时刻]
2. 按照时刻排序
3. 依次扫描

素数

判断n是素数

解法一，暴解

如果n是素数，那么n不能被任何数（1和n除外）的数字整除。暴力的方法就是从2~n-1进行探测，探测\(\frac{n}{k}, k = 2,3,...,n-1\) 是否是整数

1
2
3
4
5
6
7

private boolean ifPrime(int n){
  if(n < 2) return false;
  for(int k = 2; k < n; ++k){
    if(n % k == 0) return false;
  }
  return true;
}

解法二，优化

事实上，如果n不是素数，那么一定存在\(n = a \times b\) ，而a和b的可能性有：

我们发现，a和b有重复计算的部分，即如果a < sqrt(n) , 那么b > sqrt(n) 。因此a只用探测到sqrt(n)即可。

1
2
3
4
5
6
7
8

private boolean ifPrime(int n){
  if(n < 2) return false;
  int sqrt = (int)Math.sqrt(n);
  for(int k = 2; k < sqrt; ++k){
    if(n % k == 0) return false;
  }
  return true;
}

解法三，素数筛——生成素数序列：埃拉托斯特尼筛法

素数筛能非常高效地生成素数序列。原理是剔除所有可被素数整除的非素数。

1. 列出2~max所有的数字
2. 剔除所有2的倍数（2保留）
3. 剔除下一个没有被划掉的倍数
4. 循环直到max

1
2
3
4
5
6
7
8
9
10
11
12
13

public int countPrimes(int n) {
       boolean[] notPrime = new boolean[n]; // notPrime[i]==true代表i-1不是素数
       int counter = 0;
       for(int i = 2; i <= n; ++i){
           if(notPrime[i] == false){
               ++counter;
               for(int k = 2; k*i < n; ++k){
                   notPrime[k*i] = true;
               }
           }
       }
       return counter;
   }

面积问题

Perfect Rectangle

假设一个矩形有四个数表示[a,b,c,d] 。其中[a,b] 代表left bottom角的坐标，[c,d] 表示right top的坐标。给一堆矩形，判断它是否能刚刚好（不重合也不漏缺）地构成一个大的矩形

这道题耗费了较长时间。因为没想通。

核心思想就是:能够正好围成一个矩形的情况就是: 有且只有:

• 最左下 最左上 最右下 最右上 的四个点只出现过一次,其他肯定是成对出现的(保证完全覆盖)
• 上面四个点围成的面积,正好等于所有子矩形的面积之和(保证不重复)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

class Pair{
    int x;
    int y;
    Pair(int x, int y){
        this.x = x;
        this.y = y;
    }

    public boolean equals(Object oo){
        Pair o = (Pair)oo;
        return this.x == o.x && this.y == o.y;
    }
    public int hashCode(){ //在使用HashSet（contains也是调用HashMap中的方法）、HashMap等集合时，如果用到contains系列方法时，记得需同时重写equals与hashCode方法。
        return x + y*10;
    }
    public String toString(){
        return  "["+ x + "," + y + "]";
    }
}
int left = 0, bottom = 1, right = 2, top = 3;
public boolean isRectangleCover(int[][] rectangles) {
    // 能够成矩形的条件：
    // 1. 最边上的四个点只到达了一次
    // 2. 其余的所有点到达了两次
    // 3. 最大矩阵面积 = 所有面积的和 // 这个很容易忽略
    HashMap<Pair,Integer> memo = new HashMap<>();

    int[] corner = new int[4];
    for(int i = 0; i < rectangles[0].length; ++i){
        corner[i] = rectangles[0][i];
    }
    int area = 0;
    int[][] corners4 = {{left, bottom},{right,top}, {left,top},{right,bottom}};
    for(int[] rectangle : rectangles){
        corner[left] = Math.min(rectangle[left], corner[left]);
        corner[bottom] = Math.min(rectangle[bottom], corner[bottom]);
        corner[top] = Math.max(rectangle[top],corner[top]);
        corner[right] = Math.max(rectangle[right], corner[right]);
        for(int[] cor : corners4){
            Pair pair = new Pair(rectangle[cor[0]], rectangle[cor[1]]);
            memo.put(pair, memo.getOrDefault(pair, 0) + 1);
        }
        area += (rectangle[2] -rectangle[0])*(rectangle[3] - rectangle[1]);
    }
    // 检查面积
    if(area != (corner[2] - corner[0])*(corner[3] - corner[1])) return false;
    // 检查四个角是否只到达了一次
    for(int[] cor : corners4){
        Pair pair = new Pair(corner[cor[0]], corner[cor[1]]);
        if(memo.getOrDefault(pair,0) != 1) return false;
        memo.remove(pair);
    }
    // 检查其余节点是否都是两次
    for(Map.Entry<Pair, Integer> entry : memo.entrySet()){
        if(entry.getValue() != 2 && entry.getValue() != 4) return false;
    }
    return true;
}

Perfect Number

定义完美数字为：除了它自己以外的所有除数相加都等于它本身。判断一个数是不是一个完美数字。

与上面的类似解法

1
2
3
4
5
6
7
8
9
10
11
12
13

public boolean checkPerfectNumber(int num) {
        if(num == 1) return false;
        // 寻找所有的除数
        int sum = 1;
        int max = (int)Math.sqrt(num);
        for(int i = 2; i <= max; ++i){
            if(num % i == 0){
                sum += i;
                sum += num/i;
            }
        }
        return sum == num;
    }

组合数学

环形染色问题

如果把一个圆环分成n个区域\(A_n\)。用m种不同颜色为这n个区域染色。要求相邻两个区域\(A_i\) 和 \(A_{i+1}\) 颜色不同，则不同的染色方式有多少种？

• 对于区域\(A_1\) ，有m种染色法；
• 对于区域\(A_2,...,A_{n-1}\) ，分别有m-1种染色法
• 假设暂时不考虑\(A_n\) 与\(A_1\) ，那么对于区域\(A_n\) ，有\(m-1\) 种染法。
  • 如果\(A_n\) 与\(A_1\) 同色，那么就将这两个看成同一个区域，这就退化成了n-1个区域的染色种类，即\(a_{n-1}\)
• 因此有\[a_n + a_{n-1} = m(m-1)^{n-1}\]

接下来通过数列递推公式求通项公式：

由于对上式两边同时减去\((m-1)^n\)：

\[a_n + a_{n-1} - (m-1)^n = m(m-1)^{n-1} - (m-1)^n\] ，递推可得：

因此，环形染色问题的解为：

\[a_n = (m-1)^n + (-1)^n(m-1)\]

计算几何

Valid Square

验证给定的四个点是否能组成正方形。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    public boolean validSquare(int[] a, int[] b, int[] c, int[] d) {
        
        /** 矩形: 对角线一定相等且垂直且平分
        **/
        if(diagonal(a,b,c,d) && equal(a,b,c,d) && divideEqual(a,b,c,d)) return true;
        if(diagonal(a,c,b,d) && equal(a,c,b,d) && divideEqual(a,c,b,d)) return true;
        if(diagonal(a,d,c,b) && equal(a,d,c,b) && divideEqual(a,d,c,b)) return true;
        return false;
    }
    // 判断ab与cd互相平分
    private boolean divideEqual(int[] a, int[] b, int[] c, int[] d){
        int[] media_ab = {a[0] + b[0], a[1] + b[1]};
        int[] media_cd = {c[0] + d[0], c[1] + d[1]};
        return media_ab[0] == media_cd[0] && media_ab[1] == media_cd[1];
    }
    /**判断ab与cd两直线相等**/
    private boolean equal(int[] a, int[] b, int[] c, int[] d){
        return dist(a,b) != 0 && dist(a,b) == dist(c,d);
    }
    private int dist(int[] a, int[] b){
        return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]);
    }
    /**
    判断ab与cd两直线是否垂直
    **/
    private boolean diagonal(int[] a, int[] b, int[] c, int[] d){
        int[] vector_ab = {a[0] - b[0], a[1] - b[1]};
        int[] vector_cd = {c[0] - d[0], c[1] - d[1]};
        
        // dot
        int dot = vector_ab[0]*vector_cd[0] + vector_ab[1]*vector_cd[1];
        return dot == 0;
    }
}

在之前的 系统设计-缓存算法 一文里我用到了LinkedHashMap。这是最近刚接触到的一个新的数据结构。在此进行原理的探究。

LinkedHashMap 是 HashMap 的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用 LinkedHashMap。

LinkedHashMap 实现与 HashMap 的不同之处在于，LinkedHashMap 维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。

注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。

根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用 get 方法)的链表。默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。