面试题07-09

知道了 InnoDB 的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在 InnoDB 中不是个好主意，因为 InnoDB 数据文件本身是一颗 B+Tree ，非单调的主键会造成在插入新记录时数据文件为了维持 B+Tree 的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

MySQL 索引的底层逻辑-腾讯云开发者社区-腾讯云

噢耶！字节跳动后端Offer，拿到了！

给定n个骰子，和为k的概率，不能用回溯。

. - 力扣（LeetCode）

1.一共n个骰子，每次从1-6选择一个数，一共投n次，每次n-1，递归。

n = 0 时记录结果，执行超时。

func statisticsProbability(num int) []float64 {
    result = make(map[int]int)
total := 1
for i := 0; i < num; i++ {
total *= 6
}
ret := make([]float64, 0)
doStatisticsProbability(num, 0)
for i := num; i <= num*6; i++ {
f := math.Round(float64(result[i])/float64(total)*100000) / 100000
ret = append(ret, f)
}
return ret
}

var result = make(map[int]int)

func doStatisticsProbability(num int, sum int) {
if num == 0 {
result[sum]++
return
}

for i := 1; i <= 6; i++ {
newSum := sum + i
doStatisticsProbability(num-1, newSum)
}

}

2.可以想象成每个节点有6个叉的树，问题在于很多节点是重复的。

推翻之前的逻辑，从底开始算，保存中间的结果。

func statisticsProbability(num int) []float64 {

tmp := make(map[int]map[int]int)
for i := 1; i <= num; i++ {
tmp[i] = make(map[int]int)
if i == 1 {
for j := 1; j <= 6; j++ {
tmp[i][j] = 1
}
} else {
for j := 1; j <= 6; j++ {
for t := range tmp[i-1] {
tmp[i][t+j] += tmp[i-1][t]
}
}
}
}

result := tmp[num]
fmt.Println(result)
total := 1
for i := 0; i < num; i++ {
total *= 6
}
ret := make([]float64, 0)
for i := num; i <= num*6; i++ {
f := math.Round(float64(result[i])/float64(total)*100000) / 100000
ret = append(ret, f)
}
fmt.Println(ret)
return ret
}

看题解，使用动态规划。看到另一个文章，很详细。

看一遍就理解：动态规划详解-腾讯云开发者社区-腾讯云

. - 力扣（LeetCode）

原文地址：https://blog.csdn.net/zaimeiyeshicengjing/article/details/140291108

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！