面试问的一些算法
# 给定一个 1-7随机数生成器 如何生成1-10随机数并验证？
力扣上有一样的题目 470. 用 Rand7() 实现 Rand10() - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
我们可以使用拒绝采样的方法，我们可以搞一个7*7的矩阵，然后按照顺序从1到10，最后会剩下9个，如果结果是9个中的一个的话，我们就再次随机生成一个。
java的实例代码如下：
class Solution extends SolBase {
public int rand10() {
int row, col, idx;
do {
row = rand7();
col = rand7();
idx = col + (row - 1) * 7;
} while (idx > 40);
return 1 + (idx - 1) % 10;
}
}
2
3
4
5
6
7
8
9
10
11
# 最长公共子串和子序列
这里需要注意一下，子串是连续的，子序列是不连续的。
我们先来求子串
我们首先需要了解下面这张图，如果两个字符串相等，那么当前最长子串就是[i-1][j-1]和+1，因为我们比较的是两个字符串，两个字符串都要移动。
还有就是这里可能会有误解，这样计算的是对其的情况，要是这两个字符串不对齐呢，其实我们计算了所有的情况，因为我们用的是一个矩阵，里面就包含了所有组合情况
func getLCS(a string,b string) int {
m,n:=len(a),len(b)
// 创建dp数组
dp:=make([][]int,m+1)
for i := 0; i < m+1; i++ {
dp[i] = make([]int,n+1)
}
// 最大值max
max:=0
// 计算dp数组
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
// 如果两个字符串相等，那么当前dp数组为上一个+1
if a[i] == b[j] {
dp[i+1][j+1] = dp[i][j] + 1
max = Max(max,dp[i+1][j+1])
}
}
}
return max
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
最长公共子序列
其实代码和上面的最长子串非常相似，但是因为我们的子序列可以不连续。所以我们需要加上 dp[i+1][j+1] = Max(dp[i][j+1],dp[i+1][j]) 来进行判断，原理就是如果不相等时，当前字符串的最大子序列要么是a少一个字符串，要么是b少一个字符串中两个子序列中的一个，我们就取最大的那个就行了
func getLCS2(a string,b string) int {
m,n:=len(a),len(b)
// 创建dp数组
dp:=make([][]int,m+1)
for i := 0; i < m+1; i++ {
dp[i] = make([]int,n+1)
}
// 计算dp数组
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
// 如果两个字符串相等，那么当前dp数组为上一个+1
if a[i] == b[j] {
dp[i+1][j+1] = dp[i][j] + 1
} else {
// 不相等那么我们就复用上一个的情况
dp[i+1][j+1] = Max(dp[i][j+1],dp[i+1][j])
}
}
}
return dp[m][n]
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
动态规划：最长公共子串 & 最长公共子序列_阿飞的博客-CSDN博客_动态规划最长公共子串 (opens new window)
# TOPK问题
从arr[1, n]这n个数中，找出最大的k个数，这就是经典的TopK问题。
一般来说，我们有下面几种解法
直接进行排序，因为，本质上是找最大的几个数，我们可以对所有的数据进行排序，然后找出这几个值即可
但是这个方法不推荐，因为需要全局排序，所以非常耗费性能
局部排序
这个我们就可以使用冒泡排序了，因为冒泡排序，每趟排序都是找出最大值，所以我们只需要走k趟就行了
堆排序
使用堆排序，每次也可以取出最大的值
分布式
我们可以将数据分散在多台机器中，然后每台机器并行计算各自的 TopK 数据，最后汇总，再计算得到最终的 TopK 数据
参考：
# 海量数据中寻找中位数
只有2G内存的pc机，在一个存有10G个整数的文件，从中找到中位数，写一个算法。有下面几种解法
外排序（排序-归并）
外排序就是由于数据量太大不能一次性加载到内存，所以需要先暂时用外存储器（硬盘）将数据存起来，然后依次读入一部分数据到内存，排序之后，生成临时文件存储到硬盘，最后再对这些临时文件进行一个归并，得到最后的排序结果（在合并的过程中虽然不需要多大内存，但是会产生频繁的IO操作，频繁的读磁盘和写磁盘）
先将这10G的数据等分成5份存储到硬盘中，然后依次读入一份到内存里面，进行排序，然后将这5份数据进行归并得到最后的排序结果，然后找出中位数第5G大
堆排序（转换为求前5G大的元素）
我们知道利用堆排序处理海量数据的topK是非常合适不过了，因为它不用将所有的元素都进行排序，只需要比较和根节点的大小关系就可以了，同时也不需要一次性将所有的数据都加载到内存；对于海量数据而言，要求前k小/大的数，我们只需要构建一个k个大小的堆，然后将读入的数依次和根节点比较就行了（当然这里的前提是内存需要存的下k个数）最大堆求前n小，最小堆求前n大。
对于10G的数据，它的中位数就是第5G个元素，按常理来说我们需要构建一个5G大小的堆，但是允许的内存只有两个G，所以我们先构建一个1G大小的大顶堆，然后求出第1G个元素（根节点），然后利用该元素构建一个新的1G大小的堆，求出第2G大的元素，依次类推，求出第5G大的元素
每次构建一个堆求第几G大的元素，都需要重新遍历完所有10G的数据，相当于要遍历5 * 10G次，这需要频繁的IO操作，需要不断的从硬盘中读取数据
分而治之：基于二进制位映射分割
基于二进制位将10G数据映射到不同的文件中，利用快速排序的分割思想寻找中位数。
依次读入一部分数据到内存，根据数据的最高位将数据映射到不同的文件中，然后判断中位数可能存在于于哪个文件然后再继续对哪个文件进行分割，直到能够将数据读入内存直接排序
基数排序（计数排序）
桶排序
bitmap位图算法
这些东西待补充
参考：
# 手写一个LRU算法
力扣上有一道类似的题
146. LRU 缓存机制 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
type LRUCache struct {
// 设置缓存的容量
cap int
// 保存map数据
cache map[int]int
// key的顺序
order []int
}
// 构造函数，用于初始化
func Constructor(capacity int) LRUCache {
// 我们初始化返回数据结构
return LRUCache{cap: capacity,cache: map[int]int{},order: []int{}}
}
// 获取数据
func (this *LRUCache) Get(key int) int {
// 数据是否存在
if data,ok:=this.cache[key];!ok {
return -1
} else {
// 获取了数据后我们设置为最近使用
this.makeRecently(key)
// 返回数据
return data
}
}
// 放置数据
func (this *LRUCache) Put(key int, value int) {
// 首先需要判断数据是否存在
if _,ok:=this.cache[key];ok{
// 存在我们就修改一下key
this.cache[key] = value
// 设置为最近调用
this.makeRecently(key)
return
}
// 判断大小是否超出了
if len(this.cache) >= this.cap {
// 这里我们就找出那个最久没使用的
delete(this.cache,this.order[0])
// 更新order
this.order = append(this.order[1:])
}
// 添加新的key
this.cache[key] = value
// 添加时记录位置
this.order = append(this.order, key)
}
// 设置最近使用
func (this *LRUCache) makeRecently(key int) {
data := this.cache[key]
// 删除key
delete(this.cache, key)
// 删除当前key
for k,v:=range this.order{
if v == key {
// 判断一下k是否是最后一个
if k == 0 {
this.order = append(this.order[1:])
} else if k == len(this.order)-1 {
this.order = append(this.order[:k-1])
} else {
this.order = append(this.order[:k-1], this.order[k+1:]...)
}
break
}
}
// 重新放入当前值
this.cache[key] = data
this.order = append(this.order, key)
}
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
# 凑硬币问题
322. 零钱兑换 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
# 贪心算法
go的实现如下
// 凑硬币问题
func coinChange(coins []int, amount int) int {
if amount < 1 {
return 0
}
data:=make([]int,amount)
return aux(coins,amount,data)
}
// 定义一个辅助函数来凑零钱
// 我们传入硬币数，需要凑齐金钱数，以及我们定义的一个记忆函数
func aux(coins []int,rem int,count []int) int {
// 如果我们要凑的数目小于0，那么就直接返回-1
if rem < 0 {
return -1
}
// 如果为0，我们直接返回0
if rem == 0 {
return 0
}
// 如果数组中已经记忆了这个值，我们就直接返回即可
if count[rem-1]!=0 {
return count[rem-1]
}
// 如果没有的话，我们就直接计算
min:=math.MaxInt32
// 我们遍历硬币数来进行拼凑
// 这里就是遍历所有的硬币，找到一个结果最小的情况
for _,v:=range coins{
res := aux(coins,rem-v,count)
if res >= 0 && res < min {
min = res+1
}
}
// 如果找到了那么我们就直接返回，否则返回-1表示不存在
if min == math.MaxInt32 {
count[rem-1] = -1
} else {
count[rem-1] = min
}
return count[rem-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
# 合并有序数组和链表
参考这个