诡异的上单
2021-03-07 21:53 Java
关注
第四题是图论 + 记忆化搜索
建图：
时间复杂度取决于建图，n = 25000，若a 可以指向 b，则可以a对b连一条有向的边，如果直接暴力枚举时间复杂度是O(n^2)，首先将所有单词存入哈希表中，然后枚举所有的单词，假设枚举到单词是s，下标是a，计算出s可以连接的所有单词，添加最多次数是16 * 26左右，删除16左右，插入16左右，若计算出来的单词在哈希表中存在，对应下标是b，则a对b连一条有向边即可，大概时间复杂度上限400 * 25000次左右
记忆化搜索：
计算出所有的点x，从x点出发能到达的最大长度，去最大值即可
查看原帖
2 2
相关推荐
点赞 评论 收藏
转发
点赞 评论 收藏
转发
04-03 23:24
江西理工大学 自动化类 点赞 评论 收藏
转发
牛客热帖
- 1... 想来字节技术实习，看我这篇就够了！——保姆级面经大放送2.2W
- 2... 外卖员面试经验1.8W
- 3... 25届第一份实习怎么找？1.7W
- 4... 0实习经验上岸字节，分享一下过程经验1.6W
- 5... 【奖】休息放松or学习提升，五一假期和牛牛一起“充充电”🔋1.5W
- 6... 【0429快问快答】99%牛油的疑惑解答（更新至38个问题1.5W
- 7... 准备去参加自己的婚礼1.1W
- 8... 美团后端日常实习一二面（已oc）9411
- 9... 【💰有奖征集】非技术岗位笔面经邀你来分享！攒人品时间到！7829
- 10... 阿里国际 笔试 04296347
正在热议
# 牛友的五一计划 #
15457次浏览 332人参与
# 晒一晒我的offer #
2822667次浏览 49911人参与
# 牛客帮帮团来啦！有问必答 #
396502次浏览 7805人参与
# 如何看待offer收割机的行为 #
193862次浏览 2981人参与
# 无实习如何秋招上岸 #
172494次浏览 2718人参与
# 如何一边实习一边秋招 #
201165次浏览 3994人参与
# 春招别灰心，我们一人来一句鼓励 #
21169次浏览 305人参与
# 非技术岗薪资爆料 #
8240次浏览 152人参与
# 在国企工作的人，躺平了吗？ #
72764次浏览 880人参与
# 硬件人的春招flag #
14540次浏览 199人参与
# 女生做医疗销售有前景吗 #
3854次浏览 48人参与
# 字节跳动工作体验 #
53134次浏览 1523人参与
# 聊聊这家公司值得去吗 #
62913次浏览 1224人参与
# 第一次面试 #
17150次浏览 263人参与
# 来聊聊机械薪资天花板是哪家 #
22556次浏览 178人参与
# 机械人，你的秋招第一份简历被谁挂了 #
26955次浏览 491人参与
# 你更愿意参加线上面试还是线下面试？ #
6902次浏览 94人参与
# 华为求职进展汇总 #
441640次浏览 4434人参与
# 如何KTV领导 #
7489次浏览 72人参与
# 机械制造2024笔面经 #
278500次浏览 4664人参与