hihocoder.com Offer收割赛 #23

Presentation on theme: "hihocoder.com Offer收割赛 #23"— Presentation transcript:

1 hihocoder.com Offer收割赛 #23
2017 August 20 Offer收割赛 #23 程序员通过编程找工作的平台

2 Offer收割赛 #23 H国的身份证号码I 枚举、搜索 合并子目录 字符串、树 H国的身份证号码II 静态统计 观光旅行 并查集、平衡树

3 H国的身份证号码I 问题描述 寻找所有符合条件的𝑵位数 第一位不为0 每一位均≤𝐾 相邻两位的乘积≤𝐾 𝟏≤𝑵≤𝟗 𝟏≤𝑲≤𝟓

4 H国的身份证号码I 样例解释 𝑁=2,𝐾=4 10 11 12 13 14 20 21 22 30 31 40 41 共12种

5 H国的身份证号码I 主要问题 基本思路 时间复杂度 寻找所有符合条件的数字 依次枚举所有的𝑁位数 判断是否合法 𝑶 𝟏 𝟎 𝑵 ∗𝑵

6 H国的身份证号码I 常规思路 剪枝 枚举完一个完整的𝑁位数字之后 判断其是否合法 在枚举𝑁位数字的过程中 一旦发现当前枚举的数字不合法
优化思路 常规思路 枚举完一个完整的𝑁位数字之后 判断其是否合法 剪枝 在枚举𝑁位数字的过程中 一旦发现当前枚举的数字不合法 停止当前策略的进一步拓展

7 H国的身份证号码I 伪代码 𝑛𝑢𝑚𝑏𝑒𝑟𝑠 , 𝑑𝑓𝑠 𝑖 { 𝑖𝑓 𝑖>𝑁 𝑝𝑟𝑖𝑛𝑡(𝑛𝑢𝑚𝑏𝑒𝑟𝑠) 𝑓𝑜𝑟 𝑛𝑢𝑚𝑏𝑒𝑟𝑠 𝑖 =0~ min 𝑘,𝟗 𝑖𝑓 𝒏𝒖𝒎𝒃𝒆𝒓𝒔 𝒊−𝟏 ∗𝒏𝒖𝒎𝒃𝒆𝒓𝒔 𝒊 ≤𝒌 𝑑𝑓𝑠(𝑖+1) }

8 合并子目录 题目描述 对于给出的𝑁个文件路径 将其中单个的文件夹与其父文件夹合并后输出 𝑁≤10000 总长度≤5∗ 10 5

9 合并子目录 hihocoder game offer22 challenge30 moba solutions
样例解释 hihocoder offer22 solutions p1 challenge30 Test game moba dota uninstall /hihocoder/offer22-solutions/p1 /hihocoder/challenge30-p1/test /game-moba-dota2/uninstall

10 合并子目录 主要问题 基本思路 对于一个文件树 寻找其中仅有单个子结点的结点 按照输入数据建树 遍历整棵树，寻找符合条件的结点，合并路径
这个子结点不能是叶子结点 这个结点不能是根节点 基本思路 按照输入数据建树 遍历整棵树，寻找符合条件的结点，合并路径 按照原来的顺序输出

11 合并子目录 伪代码 𝑓𝑜𝑟 𝑝𝑎𝑡ℎ :𝑝𝑎𝑡ℎ𝑠 { 𝑡=𝑟𝑜𝑜𝑡 𝑓𝑜𝑟 𝑓𝑖𝑙𝑒 :𝑝𝑎𝑡ℎ { 𝑖𝑓 𝒕.𝒄𝒉𝒊𝒍𝒅𝒓𝒆𝒏 𝒇𝒊𝒍𝒆 =𝒏𝒖𝒍𝒍 { // 𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛可以用𝑠𝑡𝑙中的𝑚𝑎𝑝 𝒕→𝒄𝒉𝒊𝒍𝒅𝒓𝒆𝒏 𝒇𝒊𝒍𝒆 =𝒏𝒆𝒘 𝑵𝒐𝒅𝒆() } 𝒕=𝒕→𝒄𝒉𝒊𝒍𝒅𝒓𝒆𝒏 𝒇𝒊𝒍𝒆

12 合并子目录 伪代码 𝑐𝑢𝑟𝑟𝑒𝑛𝑡=[] 𝑡𝑟𝑎𝑣𝑒𝑟𝑠𝑎𝑙 𝑡 { 𝑖𝑓 𝑡.𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛.𝑠𝑖𝑧𝑒=0 { 𝑝𝑟𝑖𝑛𝑡 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 } 𝑓𝑜𝑟 𝑐 𝑖𝑛 𝑡.𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 { 𝒊𝒇 𝒕.𝒄𝒉𝒊𝒍𝒅𝒓𝒆𝒏.𝒔𝒊𝒛𝒆=𝟏 𝒂𝒏𝒅 𝒄.𝒄𝒉𝒊𝒍𝒅𝒓𝒆𝒏.𝒔𝒊𝒛𝒆>𝟎 𝒂𝒏𝒅 𝒄𝒖𝒓𝒓𝒆𝒏𝒕.𝒔𝒊𝒛𝒆>𝟎 𝒄𝒖𝒓𝒓𝒆𝒏𝒕.𝒍𝒂𝒔𝒕+= “−”+𝒄.𝒇𝒊𝒍𝒆𝒏𝒂𝒎𝒆 𝑒𝑙𝑠𝑒 𝒄𝒖𝒓𝒓𝒆𝒏𝒕.𝒑𝒖𝒔𝒉 “/”+𝒄.𝒇𝒊𝒍𝒆𝒏𝒂𝒎𝒆 𝒕𝒓𝒂𝒗𝒆𝒓𝒔𝒂𝒍 𝒄 // 𝒓𝒆𝒄𝒐𝒗𝒆𝒓 𝒄𝒖𝒓𝒓𝒆𝒏𝒕

13 合并子目录 易错点 “/file” 边界情况处理 “/1/2/3/4/5/…/100000” 目录少 单个目录长

14 H国的身份证号码II 题目描述 寻找所有符合条件的𝑵位数 第一位不为0 每一位均≤𝐾 相邻两位的乘积≤𝐾 𝟏≤𝑵≤𝟏 𝟎 𝟏𝟐 𝟏≤𝑲≤𝟖𝟏

15 H国的身份证号码II 朴素算法 优化思路 𝑶 𝟏 𝟎 𝑵 ∗𝑵 显然无法解决 在依次枚举每位数字的过程中，除了最后一位都不会对决策产生影响
基本思路 朴素算法 𝑶 𝟏 𝟎 𝑵 ∗𝑵 显然无法解决 优化思路 在依次枚举每位数字的过程中，除了最后一位都不会对决策产生影响 所以可以将最后一位相同的枚举合并 𝒇 𝒊 𝒋 表示最后一位为𝒋的合法𝒊位数有多少个？

16 H国的身份证号码II 𝒇 𝒊 𝒋 表示最后一位为𝒋的合法𝒊位数有多少个？ 𝒇 𝟏 𝟏…𝟗 =𝟏
边界状态与转移 𝒇 𝒊 𝒋 表示最后一位为𝒋的合法𝒊位数有多少个？ 𝒇 𝟏 𝟏…𝟗 =𝟏 𝒇 𝒊 𝒋≤𝒌 = 𝒋∗𝒍≤𝒌,𝒍≤𝒌 𝒇 𝒊−𝟏 𝒍 时间复杂度 状态𝑂 𝑁∗10 转移𝑂 10 𝑶(𝟏𝟎𝟎∗𝑵)，能够通过𝟓𝟎%的数据

17 H国的身份证号码II 𝒇 𝟏 𝟏…𝟗 =𝟏 𝒇 𝒊 𝒋≤𝒌 = 𝒋∗𝒍≤𝒌,𝒍≤𝒌 𝒇 𝒊−𝟏 𝒍
矩阵乘法 𝒇 𝟏 𝟏…𝟗 =𝟏 𝒇 𝒊 𝒋≤𝒌 = 𝒋∗𝒍≤𝒌,𝒍≤𝒌 𝒇 𝒊−𝟏 𝒍 记𝑭 𝒊 =𝒇 𝒊 𝟎..𝟗 ，即看做一个向量 不难发现𝑭 𝒊 =𝑨∗𝑭 𝒊−𝟏 其中 𝑨 𝒊𝒋 = 𝟏,𝒊∗𝒋≤𝒌且𝒊≤𝒌且𝒋≤𝒌 𝟎,𝒐𝒕𝒉𝒆𝒓𝒘𝒊𝒔𝒆 𝑭 𝑵 = 𝑨 𝑵−𝟏 ∗𝑭 𝟏 ∗ =

18 H国的身份证号码II 𝑨 𝑵−𝟏 = 𝑨 𝑵−𝟏 𝟐 𝟐 ,(𝑵−𝟏)为偶数 𝑨 𝑵−𝟏 𝟐 𝟐 ∗𝑨，(𝑵−𝟏)为奇数 …… 时间复杂度
快速幂 𝑨 𝑵−𝟏 = 𝑨 𝑵−𝟏 𝟐 𝟐 ,(𝑵−𝟏)为偶数 𝑨 𝑵−𝟏 𝟐 𝟐 ∗𝑨，(𝑵−𝟏)为奇数 …… 时间复杂度 𝑶 𝑨 𝟑 𝒍𝒐𝒈𝑵

19 H国的身份证号码II 𝑓𝑜𝑟 𝑖=0~ min 𝑘,9 𝑓𝑜𝑟 𝑗=0~ min 𝑘,9 𝑖𝑓 𝑖∗𝑗≤𝑘 𝐴 𝑖 𝑗 =1
伪代码 𝑓𝑜𝑟 𝑖=0~ min 𝑘,9 𝑓𝑜𝑟 𝑗=0~ min 𝑘,9 𝑖𝑓 𝑖∗𝑗≤𝑘 𝐴 𝑖 𝑗 =1 𝐴= 𝐴 𝑁−1 𝑎𝑛𝑠=0 𝑓𝑜𝑟 𝑗=1~ min 𝑘,9 𝑎𝑛𝑠=𝑎𝑛𝑠+𝐴 𝑖 𝑗

20 观光旅行 𝑵个点，𝑴条边的无向图，每条边的费用均不同 对于每条边 𝒆 𝒊 𝑵,𝑴≤𝟐∗ 𝟏𝟎 𝟓
问题描述 𝑵个点，𝑴条边的无向图，每条边的费用均不同 对于每条边 𝒆 𝒊 找到一组点对𝒔≤𝒕，满足𝒔到𝒕的最小瓶颈路的瓶颈为 𝒆 𝒊 对于多组满足条件的𝑠<𝑡，输出其中𝑠最大的，如果有多组𝑠相同的，输出𝑡最小的 𝑵,𝑴≤𝟐∗ 𝟏𝟎 𝟓

21 观光旅行 1−2⇒(0,0) 1−3⇒ 1,3 2−3⇒(3,4) 2−4⇒ 2,4 3−6⇒ 0,0 3−5⇒ 5,6 4−5⇒(4,6)
样例解释 1−2⇒(0,0) 1−3⇒ 1,3 2−3⇒(3,4) 2−4⇒ 2,4 3−6⇒ 0,0 3−5⇒ 5,6 4−5⇒(4,6) 2 9 1 3 6 6 3 8 4 2 4 5 1

22 观光旅行 主要问题 基本思路 对于每一条边 𝑒 𝑖 寻找符合条件的𝑠,𝑡 计算所有𝑠<𝑡的最小瓶颈路𝑒
用𝑠,𝑡更新𝑒当前维护的最优的 𝑠 𝑒 , 𝑡 𝑒 𝑂 𝑁 3

23 观光旅行 伪代码 𝑓𝑜𝑟 𝑘=1~𝑁 𝑓𝑜𝑟 𝑖=1~𝑁 𝑓𝑜𝑟 𝑗=1~𝑁 𝒊𝒇 𝐦𝐚𝐱 𝒇 𝒊 𝒌 ,𝒇 𝒌 𝒋 <𝒇 𝒊 𝒋 𝒇 𝒊 𝒋 = 𝐦𝐚𝐱 𝒇 𝒊 𝒌 ,𝒇 𝒌 𝒋 𝑓𝑜𝑟 𝑗=𝑖~𝑁 𝒖𝒑𝒅𝒂𝒕𝒆 𝒆 𝒇 𝒊 𝒋 , 𝒊, 𝒋

24 观光旅行 观察所有边中费用最大的边 𝒆 𝒎 𝒔 𝒎 , 𝒕 𝒎 考虑没有 𝑒 𝑚 这条边时，如果 𝒔 𝒎 , 𝒕 𝒎 已经连通
优化 观察所有边中费用最大的边 𝒆 𝒎 𝒔 𝒎 , 𝒕 𝒎 考虑没有 𝑒 𝑚 这条边时，如果 𝒔 𝒎 , 𝒕 𝒎 已经连通 对于任意一条路径𝒔→𝒕，如果其包含 𝒆 𝒎 ，那么将 𝒆 𝒎 替换掉，瓶颈只会变小 替换路径即此时 𝑠 𝑚 , 𝑡 𝑚 连通的路径 𝒆 𝒎 一定不属于任意点对的最小瓶颈路 ⇒ 𝑨𝒏𝒔𝑺 𝒆 𝒎 =𝟎,𝑨𝒏𝒔 𝑻 𝒆 𝒎 =𝟎 𝑠 𝑚 𝑡 𝑚 𝑒 𝑚

25 观光旅行 观察所有边中费用最大的边 𝒆 𝒎 𝒔 𝒎 , 𝒕 𝒎 考虑没有 𝑒 𝑚 这条边时，如果 𝒔 𝒎 , 𝒕 𝒎 尚未连通
优化 观察所有边中费用最大的边 𝒆 𝒎 𝒔 𝒎 , 𝒕 𝒎 考虑没有 𝑒 𝑚 这条边时，如果 𝒔 𝒎 , 𝒕 𝒎 尚未连通 把 𝑠 𝑚 所属的连通块记作𝑆，把 𝑡 𝑚 所属的连通块记作𝑇 对于任意𝒔∈𝑺,𝒕∈𝑻 𝒔到𝒕的最小瓶颈路的瓶颈均为 𝒆 𝒎 所有其他点对的最小瓶颈路的瓶颈均不为 𝒆 𝒎 𝑠 𝑚 𝑡 𝑚 𝑒 𝑚

26 观光旅行 推广 将 𝑒 𝑚 从图中删去，考虑 𝑒 𝑚−1 并以此类推 𝑠 𝑚−1 𝑡 𝑚−1 𝑒 𝑚−1 𝑠 𝑚−1 𝑡 𝑚−1 𝑒 𝑚−1

27 观光旅行 依次处理每一条边 𝒆 𝒊 判断在所有费用小于 𝒆 𝒊 的边构成的图中 𝒔 𝒊 , 𝒕 𝒊 是否连通？ 核心问题
优化算法 依次处理每一条边 𝒆 𝒊 判断在所有费用小于 𝒆 𝒊 的边构成的图中 𝒔 𝒊 , 𝒕 𝒊 是否连通？ 如果连通， 𝑨𝒏𝒔𝑺 𝒊 =𝟎,𝑨𝒏𝒔 𝑻 𝒊 =𝟎 如果不连通 记所有与 𝑠 𝑖 连通的点的集合为 𝑁 1 ，所有与 𝑡 𝑖 连通的点的集合为 𝑁 2 从 𝑵 𝟏 , 𝑵 𝟐 中任取𝒔,𝒕，都满足𝒔到𝒕的最小瓶颈路的瓶颈为 𝒆 𝒊 不妨设𝑚𝑎𝑥 𝑁 1 <𝑚𝑎𝑥 𝑁 2 𝑨𝒏𝒔 𝑺 𝒊 =𝒎𝒂𝒙 𝑵 𝟏 𝑨𝒏𝒔 𝑻 𝒊 =𝒎𝒊𝒏 𝒕∈ 𝑵 𝟐 𝒕>𝑨𝒏𝒔 𝑺 𝒊 核心问题 对于每一条边，判断所有费用小于 𝑒 𝑖 的边构成的图中， 𝑠 𝑖 , 𝑡 𝑖 是否连通？ 寻找图中某个连通块的最大值以及大于某个值的最小值 𝑠 𝑖 𝑡 𝑖 𝑒 𝑖

28 观光旅行 数据结构：并查集 按费用从小到大依次处理每条边 𝑒 𝑖 判断 𝑒 𝑖 所连的两个集合𝑆𝑒𝑡 𝑠 𝑖 和𝑆𝑒𝑡 𝑡 𝑖 是否相同
核心问题的解决 数据结构：并查集 按费用从小到大依次处理每条边 𝑒 𝑖 判断 𝑒 𝑖 所连的两个集合𝑆𝑒𝑡 𝑠 𝑖 和𝑆𝑒𝑡 𝑡 𝑖 是否相同 如果不同，则合并 对于每一个集合，维护一个平衡树 也可以使用𝑠𝑡𝑙如𝑠𝑒𝑡 在并查集的过程中维护 问题转化成 平衡树的最大值 平衡树中大于某个值的最小值

29 观光旅行 示例 𝟐−𝟒 𝟐 , 𝟒 ⇒ 𝟐,𝟒 𝟏−𝟑 𝟏 , 𝟑 ⇒ 𝟏,𝟑 𝟐−𝟑 𝟏,𝟑 , 𝟐,𝟒 ⇒ 𝟑,𝟒 𝟒−𝟔 𝟏,𝟐,𝟑,𝟒 , 𝟔 ⇒ 𝟒,𝟔 𝟏−𝟐 𝟏,𝟐,𝟑,𝟒,𝟔 , 𝟏,𝟐,𝟑,𝟒,𝟔 ⇒ 𝟎,𝟎 𝟑−𝟓 𝟏,𝟐,𝟑,𝟒,𝟔 , 𝟓 ⇒ 𝟓,𝟔 𝟑−𝟔 𝟏,𝟐,𝟑,𝟒,𝟓,𝟔 , 𝟏,𝟐,𝟑,𝟒,𝟓,𝟔 ⇒(𝟎,𝟎) 2 9 1 3 6 6 3 8 4 2 4 5 1

30 观光旅行 伪代码 𝑓𝑜𝑟 𝑒 𝑖𝑛 𝐸𝑑𝑔𝑒𝑠 { 𝑠=𝑓𝑖𝑛𝑑𝑓𝑎𝑡ℎ𝑒𝑟 𝑒.𝑠 𝑡=𝑓𝑖𝑛𝑑𝑓𝑎𝑡ℎ𝑒𝑟 𝑒.𝑡 𝒊𝒇 𝒔≠𝒕 { 𝑖𝑓 𝑠𝑒𝑡 𝑠 .𝑚𝑎𝑥𝑉<𝑠𝑒𝑡 𝑡 .𝑚𝑎𝑥𝑉 𝒂𝒏𝒔𝒔 𝒆.𝒊𝒏𝒅𝒆𝒙 =𝒔𝒆𝒕 𝒔 .𝒎𝒂𝒙𝑽, 𝒂𝒏𝒔𝒕 𝒆.𝒊𝒏𝒅𝒆𝒙 =𝒔𝒆𝒕 𝒕 .𝒖𝒑𝒑𝒆𝒓𝑩𝒐𝒖𝒏𝒅 𝒔𝒆𝒕 𝒔 .𝒎𝒂𝒙𝑽 𝑒𝑙𝑠𝑒 … 𝒊𝒇 (𝒔𝒆𝒕 𝒔 .𝒔𝒊𝒛𝒆>𝒔𝒆𝒕 𝒕 .𝒔𝒊𝒛𝒆) 𝒔𝒘𝒂𝒑(𝒔,𝒕) 𝒇𝒂𝒕𝒉𝒆𝒓 𝒔 =𝒕 𝒔𝒆𝒕 𝒕 .𝒊𝒏𝒔𝒆𝒓𝒕(𝒔𝒆𝒕 𝒔 ) }

31 提问时间