算法

给定一个长度为100万的数组和一个大小为k的滑动窗口，要求输出窗口每次移动后的最大值。最直观的做法是：对每个窗口位置，遍历窗口内的所有元素找出最大值——总的时间复杂度是$O(n \times k)$。当k接近n时，这退化成了$O(n^2)$。 ...

假设你需要从一个装满金条的宝库中选择带走一些金条，但背包容量有限。每根金条有重量和价值，如何在不超过背包容量的前提下，使带走的价值最大？这个看似简单的选择问题，实际上蕴含着动态规划最核心的思想——如何在约束条件下做出最优决策。 ...

假设你需要在一段百万字的文本中搜索一个关键词。最直观的方法是：将关键词与文本的每个位置逐一比较——时间复杂度 $O(nm)$，其中n是文本长度，m是关键词长度。当文本达到百万级别时，这个算法可能需要数秒甚至更长。 ...

假设你需要统计小于1000万的整数中有多少个素数。最直观的想法是：对每个数逐一判断是否为素数——时间复杂度 $O(n\sqrt{n})$，当数据量达到千万级别时，程序可能需要运行数秒甚至数分钟。但如果换一个思路：用一个布尔数组标记所有合数，剩下的就是素数——时间复杂度骤降至 $O(n \log \log n)$，千万级数据量下只需几十毫秒。 ...

假设你需要统计一个整数二进制表示中1的个数。最直观的想法是：转成二进制字符串，遍历统计每个字符——代码大概十行左右。但如果告诉你，用一行循环就能搞定，甚至不需要字符串转换呢？ ...

假设你在搜索引擎输入框里键入"goog"，下拉列表立刻弹出"google"、“google maps”、“google translate"等一系列建议。这些结果是怎么在毫秒级时间内出现的？如果用哈希表存储所有可能的搜索词，每次按键都需要遍历整个哈希表来找出以当前输入为前缀的词——当词库达到百万级别时，这种做法显然不可行。 ...

假设你正在开发一个社交网络应用，需要实时回答"用户A和用户B是否在同一个社交圈内"这类查询——用户之间可以通过好友关系不断形成更大的圈子。每添加一个好友关系，圈子就可能合并；每查询一次，就需要判断两个用户是否已经连通。如果用传统的图遍历方法，每次查询都可能需要遍历整个图，当用户量达到百万级别时，系统会变得极其缓慢。 ...