编程珠玑习题集锦
需积分: 12 55 浏览量
2018-03-18
08:21:20
上传
评论
收藏 25KB DOCX 举报
二
．给定的最多包含 亿个随机排列的 位整数的顺序文件，找出一个不在文件中的
位整数。在足够的内存空间情况下，如何解决问题？如果有几个外部的临时文件可用，但
仅有几百字节的内存，又该如何解决？?
方法 ：，条件是内存无限制，约
对 亿整数进行位图映射，对应位为 的即为缺失的。
方法 ：二分法
根据整数二进制位是 还是 将数分为两类，选择缺失数的那一泪在进行分类，最终可以
找到一个缺失的数。?
注：若找重复的数，也可用位图，若每个数出现不多于 次，可以用 表示一个数。?
．?将一个 元一维向量向左旋转 个位置，例如当 ， 时，向量 旋转为
。简单的代码使用一个 元的中间向量在 步内完成该工作。你能否仅使用额外
字节的存储空间，在正比于 的时间内完成向量的旋转。
方法 ：也是最简单的，把前 个元素复制到一个临时数组中，然后将余下的 个元素依
次前移，再把临时数组中的 个元素复制到剩余的位置。但是这样用了大量的额外空间。
方法 ：实现一个可以每次旋转 个位置的函数，调用 次，但是时间又很消耗。
方法 ：首先，将 移动到临时变量 中，然后移动 到 到 移动到
依次类推，直到取到 时，结束。当 等大于 时，要对 取模。只用了一个
临时变量的额外空间。
方法 ：旋转向量 其实就是把 变成 可以把 分成 ，交换 跟 ，那么就变成
了 还剩下交换 就变成了，可以利用递归。
方法 ：求逆。先对 求逆，再对 求逆，在对整体求逆， 的逆 的逆）的逆。（翻
手）
．变位词集合!兄弟单词
标识单词根据标识排序输出集合
哈希的方法
七
粗略估算：" 法则，用于指数过程的增长
假设以年利率 #投资一笔钱 $ 年，则当 %$" 时，钱差不多翻一倍。
&' 定律：队列中物体的平均数量为进入速率与平均停留时间的乘积；
八
给定一个向量，求和最大的子向量
方法：用扫描法效率最高
【算法设计中常用：分治法，保存状态，避免重复计算，将信息与处理至数据结构中】
后缀数组
后缀数组：?后缀数组?()是一个一维数组，它保存?的某个排列?()，
()，?……?，?()，并且保证?(*+ (),-(*+ ().,，?/-。
也就是将 ( 的 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺
次放入 () 中。
名次数组：名次数组 01保存的是 (*+ ,在所有后缀中从小到大排列的“名次”。
简单的说，后缀数组是“排第几的是谁？”，名次数组是“你排第几？”。
后缀数组和名次数组为互逆运算。
数组：定义 2*+ (),和 2*+ (),的最长公共前缀，也就是排名相邻的
评论0
最新资源