Microsoft Word - 1的数目.doc

Transcription

1 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 1 的 数 目 给 定 一 个 十 进 制 正 整 数 N, 写 下 从 1 开 始, 到 N 的 所 有 整 数, 然 后 数 一 下 其 中 出 现 的 所 有 1 的 个 数 例 如 : N= 2, 写 下 1,2 这 样 只 出 现 了 1 个 1 N= 12, 我 们 会 写 下 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 这 样,1 的 个 数 是 5 问 题 是 : 1. 写 一 个 函 数 f(n), 返 回 1 到 N 之 间 出 现 的 1 的 个 数, 比 如 f(12) =5 2. 在 32 位 整 数 范 围 内, 满 足 条 件 f(n)= N 的 最 大 的 N 是 多 少?

2 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 分 析 与 解 法 问 题 1 的 解 法 一 这 个 问 题 看 上 去 并 不 是 一 个 困 难 的 问 题, 因 为 不 需 要 太 多 的 思 考, 我 想 大 家 都 能 找 到 一 个 最 简 单 的 方 法 来 计 算 f(n), 那 就 是 从 1 开 始 遍 历 到 N, 将 其 中 每 一 个 数 中 含 有 1 的 个 数 加 起 来, 自 然 就 得 到 了 从 1 到 N 所 有 1 的 个 数 的 和 写 成 程 序 如 下 : 代 码 清 单 2-9 ULONGLONG Count1InAInteger(ULONGLONG n) ULONGLONG inum = 0; while(n!= 0) inum += (n % 10 == 1)? 1 : 0; n /= 10; return inum; ULONGLONG f(ulonglong n) ULONGLONG icount = 0; for (ULONGLONG i = 1; i <= n; i++) icount += Count1InAInteger(i);

3 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 return icount; 这 个 方 法 很 简 单, 只 要 学 过 一 点 编 程 知 识 的 人 都 能 想 到, 实 现 也 很 简 单, 容 易 理 解 但 是 这 个 算 法 的 致 命 问 题 是 效 率, 它 的 时 间 复 杂 度 是 log 2 N) O(N) 计 算 一 个 整 数 数 字 里 面 1 的 个 数 的 复 杂 度 = O(N * 如 果 给 定 的 N 比 较 大, 则 需 要 很 长 的 运 算 时 间 才 能 得 到 计 算 结 果 比 如 在 笔 者 的 机 器 上, 如 果 给 定 N= , 则 算 出 f (N) 大 概 需 要 40 秒 的 时 间, 计 算 时 间 会 随 着 N 的 增 大 而 线 性 增 长 看 起 来 要 计 算 从 1 到 N 的 数 字 中 所 有 1 的 和, 至 少 也 得 遍 历 1 到 N 之 间 所 有 的 数 字 才 能 得 到 那 么 能 不 能 找 到 快 一 点 的 方 法 来 解 决 这 个 问 题 呢? 要 提 高 效 率, 必 须 摈 弃 这 种 遍 历 1 到 N 所 有 数 字 来 计 算 f(n) 的 方 法, 而 应 采 用 另 外 的 思 路 来 解 决 这 个 问 题 问 题 1 的 解 法 二 仔 细 分 析 这 个 问 题, 给 定 了 N, 似 乎 就 可 以 通 过 分 析 小 于 N 的 数 在 每 一 位 上 可 能 出 现 1 的 次 数 之 和 来 得 到 这 个 结 果 让 我 们 来 分 析 一 下 对 于 一 个 特 定 的 N, 如 何 得 到 一 个 规 律 来 分 析 在 每 一 位 上 所 有 出 现 1 的 可 能 性, 并 求 和 得 到 最 后 的 f(n) 先 从 一 些 简 单 的 情 况 开 始 观 察, 看 看 能 不 能 总 结 出 什 么 规 律

4 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 先 看 1 位 数 的 情 况 如 果 N = 3, 那 么 从 1 到 3 的 所 有 数 字 :1 2 3, 只 有 个 位 数 字 上 可 能 出 现 1, 而 且 只 出 现 1 次, 进 一 步 可 以 发 现 如 果 N 是 个 位 数, 如 果 N>=1, 那 么 f(n) 都 等 于 1, 如 果 N=0, 则 f(n) 为 0 再 看 2 位 数 的 情 况 如 果 N=13, 那 么 从 1 到 13 的 所 有 数 字 : , 个 位 和 十 位 的 数 字 上 都 可 能 有 1, 我 们 可 以 将 它 们 分 开 来 考 虑, 个 位 出 现 1 的 次 数 有 两 次 :1 和 11, 十 位 出 现 1 的 次 数 有 4 次 : 和 13, 所 以 f(n)=2+4=6 要 注 意 的 是 11 这 个 数 字 在 十 位 和 个 位 都 出 现 了 1, 但 是 11 恰 好 在 个 位 为 1 和 十 位 为 1 中 被 计 算 了 两 次, 所 以 不 用 特 殊 处 理, 是 对 的 再 考 虑 N=23 的 情 况, 它 和 N=13 有 点 不 同, 十 位 出 现 1 的 次 数 为 10 次, 从 10 到 19, 个 位 出 现 1 的 次 数 为 1 11 和 21, 所 以 f(n)=3+10=13 通 过 对 两 位 数 进 行 分 析, 我 们 发 现, 个 位 数 出 现 1 的 次 数 不 仅 和 个 位 数 字 有 关, 还 和 十 位 数 有 关 : 如 果 N 的 个 位 数 大 于 等 于 1, 则 个 位 出 现 1 的 次 数 为 十 位 数 的 数 字 加 1; 如 果 N 的 个 位 数 为 0, 则 个 位 出 现 1 的 次 数 等 于 十 位 数 的 数 字 而 十 位 数 上 出 现 1 的 次 数 不 仅 和 十 位 数 有 关, 还 和 个 位 数 有 关 : 如 果 十 位 数 字 等 于 1, 则 十 位 数 上 出 现 1 的 次 数 为 个 位 数 的 数 字 加 1; 如 果 十 位 数 大 于 1, 则 十 位 数 上 出 现 1 的 次 数 为 10 f(13) = 个 位 出 现 1 的 个 数 + 十 位 出 现 1 的 个 数 = = 6; f(23) = 个 位 出 现 1 的 个 数 + 十 位 出 现 1 的 个 数 = = 13; f(33) = 个 位 出 现 1 的 个 数 + 十 位 出 现 1 的 个 数 = = 14; f(93) = 个 位 出 现 1 的 个 数 + 十 位 出 现 1 的 个 数 = = 20; 接 着 分 析 3 位 数

5 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 如 果 N = 123: 个 位 出 现 1 的 个 数 为 13:1, 11, 21,, 91, 101, 111, 121 十 位 出 现 1 的 个 数 为 20:10~19, 110~119 百 位 出 现 1 的 个 数 为 24:100~123 f(23)= 个 位 出 现 1 的 个 数 + 十 位 出 现 1 的 个 数 + 百 位 出 现 1 的 次 数 = = 57; 同 理 我 们 可 以 再 分 析 4 位 数 5 位 数 读 者 朋 友 们 可 以 写 一 写, 总 结 一 下 各 种 情 况 有 什 么 不 同 根 据 上 面 的 一 些 尝 试, 下 面 我 们 推 导 出 一 般 情 况 下, 从 N 得 到 f(n) 的 计 算 方 法 : 假 设 N=abcde, 这 里 a b c d e 分 别 是 十 进 制 数 N 的 各 个 数 位 上 的 数 字 如 果 要 计 算 百 位 上 出 现 1 的 次 数, 它 将 会 受 到 三 个 因 素 的 影 响 : 百 位 上 的 数 字, 百 位 以 下 ( 低 位 ) 的 数 字, 百 位 ( 更 高 位 ) 以 上 的 数 字 如 果 百 位 上 的 数 字 为 0, 则 可 以 知 道, 百 位 上 可 能 出 现 1 的 次 数 由 更 高 位 决 定, 比 如 , 则 可 以 知 道 百 位 出 现 1 的 情 况 可 能 是 100~199,1 100~1 199,2 100~2 199,,11 100~11 199, 一 共 有 个 也 就 是 由 更 高 位 数 字 (12) 决 定, 并 且 等 于 更 高 位 数 字 (12) 当 前 位 数 (100)

6 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 如 果 百 位 上 的 数 字 为 1, 则 可 以 知 道, 百 位 上 可 能 出 现 1 的 次 数 不 仅 受 更 高 位 影 响, 还 受 低 位 影 响, 也 就 是 由 更 高 位 和 低 位 共 同 决 定 例 如 对 于 , 受 更 高 位 影 响, 百 位 出 现 1 的 情 况 是 100~ 199,1 100~1 199,2 100~2 199,,11 100~11 199, 一 共 个, 和 上 面 第 一 种 情 况 一 样, 等 于 更 高 位 数 字 (12) 当 前 位 数 (100) 但 是 它 还 受 低 位 影 响, 百 位 出 现 1 的 情 况 是 ~12 113, 一 共 114 个, 等 于 低 位 数 字 (123)+1 如 果 百 位 上 数 字 大 于 1( 即 为 2~9), 则 百 位 上 可 能 出 现 1 的 次 数 也 仅 由 更 高 位 决 定, 比 如 , 则 百 位 出 现 1 的 可 能 性 为 :100~199,1 100~1 199,2 100~2 199,,11 100~11 199, ~12 199, 一 共 有 个, 并 且 等 于 更 高 位 数 字 +1(12+1) 当 前 位 数 (100) 通 过 上 面 的 归 纳 和 总 结, 我 们 可 以 写 出 如 下 的 更 高 效 算 法 来 计 算 f(n): 代 码 清 单 2-10 LONGLONG Sum1s(ULONGLONG n) ULONGLONG icount = 0; ULONGLONG ifactor = 1; ULONGLONG ilowernum = 0; ULONGLONG icurrnum = 0;

7 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 ULONGLONG ihighernum = 0; while(n / ifactor!= 0) ilowernum = n - (n / ifactor) * ifactor; icurrnum = (n / ifactor) % 10; ihighernum = n / (ifactor * 10); + 1; switch(icurrnum) case 0: icount += ihighernum * ifactor; break; case 1: icount += ihighernum * ifactor + ilowernum break; default: icount += (ihighernum + 1) * ifactor; break; ifactor *= 10; return icount; 这 个 方 法 只 要 分 析 N 就 可 以 得 到 f(n), 避 开 了 从 1 到 N 的 遍 历, 输 入 长 度 为 Len 的 数 字 N 的 时 间 复 杂 度 为 O(Len), 即 为 O(ln(n)/ln(10)+1) 在 笔 者 的 计 算 机 上, 计 算 N= ,

8 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 相 对 于 第 一 种 方 法 的 40 秒 时 间, 这 种 算 法 不 到 1 毫 秒 就 可 以 返 回 结 果, 速 度 至 少 提 高 了 倍

9 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 问 题 2 的 解 法 要 确 定 最 大 的 数 N, 满 足 f(n)=n 我 们 通 过 简 单 的 分 析 可 以 知 道 ( 仿 照 上 面 给 出 的 方 法 来 分 析 ): 9 以 下 为 : 1 个 ; 99 以 下 为 : =20 个 ; 999 以 下 为 : =300 个 ; 9999 以 下 为 : =4000 个 ; 以 下 为 : 个 ; 以 下 为 : 个 容 易 从 上 面 的 式 子 归 纳 出 :f(10 n-1 )= n * 10 n-1 通 过 这 个 递 推 式, 很 容 易 看 到, 当 n = 9 时 候,f(n) 的 开 始 值 大 于 n, 所 以 我 们 可 以 猜 想, 当 n 大 于 某 一 个 数 N 时,f(n) 会 始 终 比 n 大, 也 就 是 说, 最 大 满 足 条 件 在 0~N 之 间, 亦 即 N 是 最 大 满 足 条 件 f (n)= n 的 一 个 上 界 如 果 能 估 计 出 这 个 N, 那 么 只 要 让 n 从 N 往 0 递 减, 每 个 分 别 检 查 是 否 有 f(n)= n, 第 一 个 满 足 条 件 的 数

10 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 就 是 我 们 要 求 的 整 数 因 此, 问 题 转 化 为 如 何 证 明 上 界 N 确 实 存 在, 并 估 计 出 这 个 上 界 N 证 明 满 足 条 件 f(n)= n 的 数 存 在 一 个 上 界 首 先, 用 类 似 数 学 归 纳 法 的 思 路 来 推 理 这 个 问 题 很 容 易 得 到 下 面 这 些 结 论 ( 读 者 朋 友 可 以 自 己 试 着 列 举 验 证 一 下 ): 当 n 增 加 10 时,f(n) 至 少 增 加 1; 当 n 增 加 100 时,f(n) 至 少 增 加 20; 当 n 增 加 时,f(n) 至 少 增 加 300; 当 n 增 加 时,f(n) 至 少 增 加 4 000; 当 n 增 加 10 k 时,f(n) 至 少 增 加 k*10 k - 1 首 先, 当 k>=10 时,k*10 k - 1 > 10 k, 所 以 f(n) 的 增 加 量 大 于 n 的 增 加 量 其 次,f( )=10 10 > 如 果 存 在 N, 当 n = N 时,f(N) -N> 成 立 时, 此 时 不 管 n 增 加 多 少,f(n) 的 值 将 始 终 大 于 n 具 体 来 说, 设 n 的 增 加 量 为 m: 当 m 小 于 时, 由 于 f (N)-N> , 因 此 有 f(n + m)> f(n)> N > N + m, 即 f(n) 的 值 仍 然 比 n 的 值 大 ; 当 m 大 于 等 于 时,f (n)

11 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 的 增 量 始 终 比 n 的 增 量 大, 即 f(n + m)- f(n)>(n+m)- N, 也 就 是 f(n + m)> f(n)+ m > N m > N + m, 即 f(n) 的 值 仍 然 比 n 的 值 大 因 此, 对 于 满 足 f(n)- N > 成 立 的 N 一 定 是 所 求 该 数 的 一 个 上 界 求 出 上 界 N 又 由 于 f( )= n * , 不 妨 设 N = 10 K-1, 有 f(10 K-1 ) -(10 K-1 )> , 即 K*10 K-1 -(10 K-1 )> , 易 得 K > =11 时 候 均 满 足 所 以, 当 K = 11 时,N= 即 为 最 小 一 个 上 界 计 算 这 个 最 大 数 n 令 N = = , 让 n 从 N 往 0 递 减, 每 个 分 别 检 查 是 否 有 f(n)= n, 第 一 满 足 条 件 的 就 是 我 们 要 求 的 整 数 很 容 易 解 出 n = 是 满 足 f(n)= n 的 最 大 整 数 扩 展 问 题 对 于 其 他 进 制 表 达 方 式, 也 可 以 试 一 试, 看 看 有 什 么 规 律 例 如 二 进 制 : f(1)= 1 f(10)= 10( 因 为 01, 10 有 两 个 1) f(11)= 100( 因 为 01, 10, 11 有 四 个 1)

12 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 读 者 朋 友 可 以 模 仿 我 们 的 分 析 方 法, 给 出 相 应 的 解 答

13

14 题 目 1-12 NIM 拈 游 戏 分 析 1 NIM 拈 游 戏 分 析 问 题 有 N 块 石 头 和 两 个 玩 家 A 和 B, 玩 家 A 先 将 石 头 分 成 若 干 堆, 然 后 按 照 BABA 的 顺 序 不 断 轮 流 取 石 头, 能 将 剩 下 的 石 头 一 次 取 光 的 玩 家 获 胜 每 次 取 石 头 时, 每 个 玩 家 只 能 从 若 干 堆 石 头 中 任 选 一 堆, 取 这 一 堆 石 头 中 任 意 数 目 ( 大 于 1) 个 石 头 请 问 : 玩 家 A 有 必 胜 策 略 吗? 要 怎 么 分 配 和 取 石 头 才 能 保 证 自 己 有 把 握 取 胜? 解 法 与 分 析 据 说, 该 游 戏 起 源 于 中 国, 英 文 名 字 叫 做 NIM, 是 由 广 东 话 拈 ( 取 物 之 意 ) 音 译 而 来, 经 由 当 年 到 美 洲 打 工 的 华 人 流 传 出 去, 这 个 游 戏 一 个 常 见 的 变 种 是 将 十 二 枚 硬 币 分 三 列 排 成 [3,4,5] 再 开 始 玩 我 们 这 里 讨 论 的 是 一 般 意 义 上 的 拈 游 戏 言 归 正 传, 在 面 试 者 咄 咄 逼 人 的 目 光 下, 你 要 如 何 着 手 解 决 这 个 问 题? 在 面 试 中, 面 试 者 考 察 的 重 点 不 是 what 能 否 记 住 某 道 题 目 的 解 法, 某 件 历 史 事 件 发 生 的 确 切 年 代,C++ 语 言 中 关 于 类 的 继 承 的 某 个 规 则 的 分 支 等 面 试 者 很 想 知 道 的 是 how 应 聘 者 是 如 何 思 考 和 学 习 的 所 以, 应 聘 者 得 展 现 自 己 的 思 路 解 答 这 类 问 题 应 从 最 基 本 的 特 例 开 始 分 析 我 们 用 N 表 示 石 头 的 堆 数,M 表 示 总 的 石 头 数 目 当 N=1 时, 即 只 有 一 堆 石 头 显 然 无 论 你 放 多 少 石 头, 你 的 对 手 都 能 一 次 全 拿 光, 你 不 能 这 样 摆 当 N=2 时, 即 有 两 堆 石 头, 最 简 单 的 情 况 是 每 堆 石 头 中 各 有 一 个 石 子 (1,1) 先 让 对 手 拿, 无 论 怎 样 你 都 可 以 获 胜 我 们 把 这 种 在 双 方 理 性 走 法 下, 你 一 定 能 够 赢 的 编 程 之 美 微 软 技 术 面 试 心 得

15 2 第 1 章 游 戏 之 美 局 面 叫 作 安 全 局 面 当 N = 2,M > 2 时, 既 然 (1, 1) 是 安 全 局 面, 那 么 (1, X) 都 不 是 安 全 局 面, 因 为 对 手 只 要 经 过 一 次 转 换, 就 能 把 (1, X) 变 成 (1, 1), 然 后 该 你 走, 你 就 输 了 既 然 (1, X) 不 安 全, 那 么 (2, 2) 如 何? 经 过 分 析,(2,2) 是 安 全 的, 因 为 它 不 能 一 步 变 成 (1,1) 这 样 的 安 全 局 面 这 样 我 们 似 乎 可 以 推 理 (3, 3) (4, 4), 一 直 到 (X, X) 都 是 安 全 局 面 于 是 我 们 初 步 总 结, 如 果 石 头 的 数 目 是 偶 数, 就 把 它 们 分 为 两 堆, 每 堆 有 同 样 多 的 数 目 这 样 无 论 对 手 如 何 取, 你 只 要 保 证 你 取 之 后 是 安 全 局 面 (X, X), 你 就 能 赢 好, 如 果 石 头 数 目 是 奇 数 个 呢? 当 M=3 的 时 候, 有 两 种 情 况,(2, 1) (1, 1, 1), 这 两 种 情 况 都 会 是 先 拿 者 赢 当 M=5 的 时 候, 和 M=3 类 似 无 论 你 怎 么 摆, 都 会 是 先 拿 者 赢 若 M=7 呢? 情 况 多 起 来 了, 头 有 些 晕 了, 好 像 也 是 先 拿 者 赢 我 们 在 这 里 得 到 一 个 很 重 要 的 阶 段 性 结 论 : 当 摆 放 方 法 为 (1, 1,, 1) 的 时 候, 如 果 1 的 个 数 是 奇 数 个, 则 先 拿 者 赢 ; 如 果 1 的 个 数 是 偶 数 个, 则 先 拿 者 必 输 当 摆 放 方 法 为 (1, 1,, 1, X)( 多 个 1, 加 上 一 个 大 于 1 的 X) 的 时 候, 先 拿 者 必 赢 因 为 : 如 果 1 有 奇 数 个, 先 拿 者 可 以 从 (X) 这 一 堆 中 一 次 拿 走 X-1 个, 剩 下 偶 数 个 1 接 下 来 动 手 的 人 必 输 如 果 有 偶 数 个 1, 加 上 一 个 X, 先 拿 者 可 以 一 次 把 X 都 拿 光, 剩 下 偶 数 个 1 接 下 来 动 手 的 人 也 必 输 当 然, 游 戏 是 两 个 人 玩 的, 还 有 其 他 的 各 种 摆 法, 例 如 当 M = 9 的 时 候, 我 们 可 以 摆 为 (2, 3, 4) (1, 4, 4) (1, 2, 6), 等 等, 这 么 多 堆 石 头, 它 们 既 互 相 独 立, 又 互 相 牵 制, 那 如 何 分 析 得 出 致 胜 策 略 呢? 关 键 是 找 到 在 这 一 系 列 变 化 过 程 中 有 没 有 一 个 特 性 始 终 决 定 着 输 赢 这 个 时 候, 就 得 考 验 一 下 真 功 夫 了, 我 们 要 想 想 大 学 一 年 级 数 理 逻 辑 课 上 学 的 异 或 (XOR) 运 算 异 或 运 算 规 则 如 下 : 编 程 之 美 微 软 技 术 面 试 心 得

16 题 目 1-12 NIM 拈 游 戏 分 析 3 XOR(0, 0)= 0 XOR(1, 0)= 1 XOR(1, 1)= 0 首 先 我 们 看 整 个 游 戏 过 程, 我 们 从 N 堆 石 头 (M 1, M 2,, M n ) 开 始, 双 方 斗 智 斗 勇, 石 头 一 直 递 减 到 全 部 为 零 (0, 0,, 0) 当 M 为 偶 数 的 时 候, 我 们 的 取 胜 策 略 是 把 M 分 成 相 同 的 两 份, 这 样 就 能 取 胜 开 始 :(M 1, M 1 ) 它 们 异 或 的 结 果 是 XOR(M 1, M 1 )= 0 中 途 :(M 1, M 2 ) 对 手 无 论 怎 样 从 这 堆 石 头 中 取,XOR(M 1, M 2 )!= 0 我 方 :(M 2, M 2 ) 我 方 还 是 把 两 堆 变 相 等 XOR(M 2, M 2 )= 0 最 后 :(M 2, M 2 ) 我 方 取 胜 类 似 的, 若 M 为 奇 数, 我 们 把 石 头 分 成 (1, 1,,1) 奇 数 堆 的 时 候,XOR(1, 1,,1) [ 奇 数 个 ]!=0 而 这 时 候, 对 方 可 以 取 走 一 整 堆,XOR(1, 1,, 1) [ 偶 数 个 ]=0, 如 此 下 去, 我 方 必 输 我 们 推 广 到 M 为 奇 数, 但 是 每 堆 石 头 的 数 目 不 限 于 1 的 情 况, 看 看 XOR 值 的 规 律 : 开 始 :(M 1, M 2,, M n ) XOR(M 1, M 2, M n )=? 中 途 :(M 1, M 2, M n ) XOR(M 1, M 2, M n )=? 最 后 :(0, 0,, 0) XOR(0,0, 0)=0 不 幸 的 是, 可 以 看 出, 当 有 奇 数 个 石 头 时, 无 论 你 如 何 分 堆,XOR(M 1, M 2, M n ) 总 是 不 等 于 0! 因 为 必 然 会 有 奇 数 堆 有 奇 数 个 石 头 ( 二 进 制 表 示 最 低 位 为 1), 异 或 的 结 果 最 低 位 肯 定 为 1 [ 结 论 1] 再 不 幸 的 是, 还 可 以 证 明, 当 XOR(M 1, M 2, M n )!= 0 时, 我 们 总 是 只 需 要 改 变 一 个 M i 的 值, 就 可 以 让 XOR(M 1, M 2, M i, M n )= 0 [ 结 论 2] 更 不 幸 的 是, 又 可 以 证 明, 当 XOR(M 1, M 2, M n )= 0 时, 对 任 何 一 个 M 值 的 改 变 ( 取 走 石 头 ), 都 会 让 XOR(M 1, M 2, M i, M n )! = 0 [ 结 论 3] 编 程 之 美 微 软 技 术 面 试 心 得

17 4 第 1 章 游 戏 之 美 有 了 这 三 个 不 幸 的 结 论, 我 们 不 得 不 承 认, 当 M 为 奇 数 时, 无 论 怎 样 分 堆, 总 是 先 动 手 的 人 赢 还 不 信? 那 我 们 试 试 看 : 当 M=9, 随 机 分 堆 为 (1,2,6) 开 始 :(1,2,6) 1= = =1 1 0 XOR=1 0 1 即 XOR(1,2,6)!=0 B 先 手 :(1, 2, 3), 即 从 第 三 堆 取 走 三 个, 得 到 (1,2,3) 1= = =0 1 1 XOR=0 0 0 A 方 :(1, 2, 2)XOR(1, 2, 2)!=0 B 方 :(0, 2, 2)XOR (0, 2, 2)=0 A 方 继 续 顽 抗 B 方 最 后 :(0, 0, 0),XOR(0, 0, 0)= 0 所 以,XOR(1,2,3)=0 好 了, 通 过 以 上 的 分 析, 我 们 不 但 知 道 了 这 类 问 题 的 答 案, 还 知 道 了 游 戏 的 规 律, 以 及 如 何 才 能 赢 XOR, 这 个 我 们 很 早 就 学 过 的 运 算, 在 这 里 帮 了 大 忙 1 我 们 应 该 对 XOR 说 Orz 才 对! 有 兴 趣 的 读 者 可 以 写 一 个 程 序, 返 回 当 输 入 为 (M 1, M 2,, M n ) 的 时 候, 到 底 如 2 何 取 石 头, 才 能 有 赢 的 可 能 比 如, 当 输 入 为 (3, 4, 5) 的 时 候, 程 序 返 回 (1, 4, 5) 这 样 就 转 败 为 胜 了! 扩 展 问 题 1. 如 果 规 定 相 反, 取 光 所 有 石 头 的 人 输, 又 该 如 何 控 制 局 面? 1 温 馨 提 示 : 你 还 记 得 教 我 们 XOR 运 算 的 老 师 么? 这 门 课 一 定 比 较 枯 燥 吧, 如 果 当 时 能 玩 NIM 这 个 游 戏 就 好 了 2 提 一 句, 这 是 一 个 不 明 智 的 分 堆 办 法, 不 如 分 为 (6, 6), 这 样 必 赢 无 疑 编 程 之 美 微 软 技 术 面 试 心 得

18 题 目 1-12 NIM 拈 游 戏 分 析 5 2. 如 果 每 次 可 以 挑 选 任 意 K 堆, 并 从 中 任 意 取 石 头, 又 该 如 何 找 到 必 胜 策 略 呢? 编 程 之 美 微 软 技 术 面 试 心 得

19 1.1 让 CPU 占 用 率 曲 线 听 你 指 挥 1 编 程 之 美 微 软 技 术 面 试 心 得 编 程 之 美 微 软 技 术 面 试 心 得 ( 是 微 软 亚 洲 研 究 院 技 术 创 新 组 研 发 主 管 邹 欣 继 移 山 之 道 VSTS 软 件 开 发 指 南 后 的 最 新 力 作 它 传 达 给 读 者 : 微 软 重 视 什 么 样 的 能 力, 需 要 什 么 样 的 人 才 但 它 更 深 层 的 意 义 在 于 引 导 读 者 思 考, 提 倡 一 种 发 现 问 题 解 决 问 题 的 思 维 方 式, 充 分 挖 掘 编 程 的 乐 趣, 展 示 编 程 之 美 本 书 3 月 份 上 市 网 上 讨 论 和 解 答 在 : 题 目 让 CPU 占 用 率 曲 线 听 你 指 挥 问 题 写 一 个 程 序, 让 用 户 来 决 定 Windows 任 务 管 理 器 (Task Manager) 的 CPU 占 用 率 程 序 越 精 简 越 好, 计 算 机 语 言 不 限 例 如, 可 以 实 现 下 面 三 种 情 况 : 1. CPU 的 占 用 率 固 定 在 50%, 为 一 条 直 线 ; 2. CPU 的 占 用 率 为 一 条 直 线, 但 是 具 体 占 用 率 由 命 令 行 参 数 决 定 ( 参 数 范 围 1~ 100); 编 程 之 美 微 软 技 术 面 试 心 得

20 2 1.1 让 CPU 占 用 率 曲 线 听 你 指 挥 3. CPU 的 占 用 率 状 态 是 一 个 正 弦 曲 线 1 分 析 与 解 法 有 一 名 学 生 写 了 如 下 的 代 码 : while (true) if (busy) i++; else 然 后 她 就 陷 入 了 苦 苦 思 索 :else 干 什 么 呢? 怎 么 才 能 让 电 脑 不 做 事 情 呢?CPU 使 用 率 为 0 的 时 候, 到 底 是 什 么 东 西 在 用 CPU? 另 一 名 学 生 花 了 很 多 时 间 构 想 如 何 深 入 内 核, 以 控 制 CPU 占 用 率 可 是 事 情 真 的 有 这 么 复 杂 么? MSRA TTG(Microsoft Research Asia, Technology Transfer Group) 的 一 些 实 习 生 写 了 各 种 解 法, 他 们 写 的 简 单 程 序 可 以 达 到 如 图 1-1 所 示 的 效 果 图 1-1 编 码 控 制 CPU 占 用 率 呈 现 正 弦 曲 线 形 态 看 来 这 并 不 是 不 可 能 完 成 的 任 务 让 我 们 仔 细 地 回 想 一 下 写 程 序 时 曾 经 碰 到 的 问 题, 如 1 作 者 注 : 当 面 试 的 同 学 听 到 这 个 问 题 的 时 候, 很 多 人 都 有 点 意 外 我 把 我 的 笔 记 本 电 脑 交 给 他 们 说, 这 是 开 卷 考 试, 你 可 以 上 网 查 资 料, 干 什 么 都 可 以 大 部 分 面 试 者 在 电 脑 上 的 第 一 个 动 作 就 是 上 网 搜 索 CPU 控 制 50% 这 样 的 关 键 字, 当 然 没 有 找 到 什 么 直 接 的 结 果 不 过 这 本 书 出 版 以 后, 情 况 可 能 就 不 一 样 了 编 程 之 美 微 软 技 术 面 试 心 得

21 1.1 让 CPU 占 用 率 曲 线 听 你 指 挥 3 果 我 们 不 小 心 写 了 一 个 死 循 环,CPU 占 用 率 就 会 跳 到 最 高, 并 且 一 直 保 持 100% 我 们 也 可 以 打 开 任 务 管 理 器 2, 实 际 观 测 一 下 它 是 怎 样 变 动 的 凭 肉 眼 观 察, 它 大 约 是 1 秒 钟 更 新 一 次 一 般 情 况 下,CPU 使 用 率 会 很 低 但 是, 当 用 户 运 行 一 个 程 序, 执 行 一 些 复 杂 操 作 的 时 候,CPU 的 使 用 率 会 急 剧 升 高 当 用 户 晃 动 鼠 标 时,CPU 的 使 用 率 也 有 小 幅 度 的 变 化 那 当 任 务 管 理 器 报 告 CPU 使 用 率 为 0 的 时 候, 谁 在 使 用 CPU 呢? 通 过 任 务 管 理 器 的 进 程 (Process) 一 栏 可 以 看 到,System Idle Process 占 用 了 CPU 空 闲 的 时 间 这 时 候 大 家 该 回 忆 起 在 操 作 系 统 原 理 这 门 课 上 学 到 的 一 些 知 识 了 吧 系 统 中 有 那 么 多 进 程, 它 们 什 么 时 候 能 闲 下 来 呢? 答 案 很 简 单, 这 些 程 序 或 者 在 等 待 用 户 的 输 入, 或 者 在 等 待 某 些 事 件 的 发 生 (WaitForSingleObject()), 或 者 进 入 休 眠 状 态 ( 通 过 Sleep() 来 实 现 ) 在 任 务 管 理 器 的 一 个 刷 新 周 期 内,CPU 忙 ( 执 行 应 用 程 序 ) 的 时 间 和 刷 新 周 期 总 时 间 的 比 率, 就 是 CPU 的 占 用 率, 也 就 是 说, 任 务 管 理 器 中 显 示 的 是 每 个 刷 新 周 期 内 CPU 占 用 率 的 统 计 平 均 值 因 此, 我 们 写 一 个 程 序, 让 它 在 任 务 管 理 器 的 刷 新 期 间 内 一 会 儿 忙, 一 会 儿 闲, 然 后 通 过 调 节 忙 / 闲 的 比 例, 就 可 以 控 制 任 务 管 理 器 中 显 示 的 CPU 占 用 率 解 法 一 简 单 的 解 法 步 骤 1 要 操 纵 CPU 的 usage 曲 线, 就 需 要 使 CPU 在 一 段 时 间 内 ( 根 据 Task Manager 的 采 样 率 ) 跑 busy 和 idle 两 个 不 同 的 loop, 从 而 通 过 不 同 的 时 间 比 例, 来 获 得 调 节 CPU Usage 的 效 果 步 骤 2 Busy loop 可 以 通 过 执 行 空 循 环 来 实 现,idle 可 以 通 过 Sleep() 来 实 现 问 题 的 关 键 在 于 如 何 控 制 两 个 loop 的 时 间, 方 法 有 二 : Sleep 一 段 时 间, 然 后 以 for 循 环 n 次, 估 算 n 的 值 那 么 对 于 一 个 空 循 环 for(i = 0; i < n; i++); 又 该 如 何 来 估 算 这 个 最 合 适 的 n 值 呢? 我 们 都 知 道 CPU 执 行 的 是 机 器 指 令, 而 最 接 近 于 机 器 指 令 的 语 言 是 汇 编 语 言, 所 以 我 们 可 以 先 把 这 个 空 循 环 简 单 地 写 成 如 下 汇 编 代 码 后 再 进 行 分 析 : loop: mov dx i ; 将 i 置 入 dx 寄 存 器 inc dx ; 将 dx 寄 存 器 加 1 mov i dx ; 将 dx 中 的 值 赋 回 i cmp i n ; 比 较 i 和 n jl loop ;i 小 于 n 时 则 重 复 循 环 假 设 这 段 代 码 要 运 行 的 CPU 是 P4 2.4Ghz(2.4 * 10 的 9 次 方 个 时 钟 周 期 每 秒 ) 现 代 CPU 每 个 时 钟 周 期 可 以 执 行 两 条 以 上 的 代 码, 那 么 我 们 就 取 平 均 值 两 条, 于 是 让 ( * 2)/5= ( 循 环 / 秒 ), 也 就 是 说 CPU 1 秒 钟 可 以 运 行 这 个 空 循 环 次 不 过 我 们 还 是 不 能 简 单 地 将 n = , 然 后 Sleep(1000) 了 事 如 果 我 们 让 CPU 工 2 如 果 应 聘 者 从 来 没 有 琢 磨 过 任 务 管 理 器, 那 还 是 不 要 在 简 历 上 说 精 通 Windows 为 好 编 程 之 美 微 软 技 术 面 试 心 得

22 4 1.1 让 CPU 占 用 率 曲 线 听 你 指 挥 作 1 秒 钟, 然 后 休 息 1 秒 钟, 波 形 很 有 可 能 就 是 锯 齿 状 的 先 达 到 一 个 峰 值 ( 大 于 >50%), 然 后 跌 到 一 个 很 低 的 占 用 率 我 们 尝 试 着 降 低 两 个 数 量 级, 令 n = , 而 睡 眠 时 间 相 应 改 为 10 毫 秒 (Sleep(10)) 用 10 毫 秒 是 因 为 它 不 大 也 不 小, 比 较 接 近 Windows 的 调 度 时 间 片 如 果 选 得 太 小 ( 比 如 1 毫 秒 ), 则 会 造 成 线 程 频 繁 地 被 唤 醒 和 挂 起, 无 形 中 又 增 加 了 内 核 时 间 的 不 确 定 性 影 响 最 后 我 们 可 以 得 到 如 下 代 码 : 代 码 清 单 1-1 int main() for(;;) for(int i = 0; i < ; i++); Sleep(10); return 0; 在 不 断 调 整 的 参 数 后, 我 们 就 可 以 在 一 台 指 定 的 机 器 上 获 得 一 条 大 致 稳 定 的 50% CPU 占 用 率 直 线 使 用 这 种 方 法 要 注 意 两 点 影 响 : 1. 尽 量 减 少 sleep/awake 的 频 率, 如 果 频 繁 发 生, 影 响 则 会 很 大, 因 为 此 时 优 先 级 更 高 的 操 作 系 统 内 核 调 度 程 序 会 占 用 很 多 CPU 运 算 时 间 2. 尽 量 不 要 调 用 system call( 比 如 I/O 这 些 privilege instruction), 因 为 它 也 会 导 致 很 多 不 可 控 的 内 核 运 行 时 间 该 方 法 的 缺 点 也 很 明 显 : 不 能 适 应 机 器 差 异 性 一 旦 换 了 一 个 CPU, 我 们 又 得 重 新 估 算 n 值 有 没 有 办 法 动 态 地 了 解 CPU 的 运 算 能 力, 然 后 自 动 调 节 忙 / 闲 的 时 间 比 呢? 请 看 下 一 个 解 法 解 法 二 使 用 GetTickCount() 和 Sleep() 我 们 知 道 GetTickCount() 可 以 得 到 系 统 启 动 到 现 在 的 毫 秒 值, 最 多 能 够 统 计 到 49.7 天 另 外, 利 用 Sleep() 函 数, 最 多 也 只 能 精 确 到 1 毫 秒 因 此, 可 以 在 毫 秒 这 个 量 级 做 操 作 和 比 较 具 体 如 下 : 利 用 GetTickCount() 来 实 现 busy loop 的 循 环, 用 Sleep() 实 现 idle loop 伪 代 码 如 下 : 代 码 清 单 1-2 int busytime = 10; //10 ms int idletime = busytime; //same ratio will lead to 50% cpu usage 编 程 之 美 微 软 技 术 面 试 心 得

23 1.1 让 CPU 占 用 率 曲 线 听 你 指 挥 5 Int64 starttime = 0; while (true) starttime = GetTickCount(); // busy loop 的 循 环 while ((GetTickCount() - starttime) <= busytime) ; //idle loop Sleep(idleTime); 这 两 种 解 法 都 是 假 设 目 前 系 统 上 只 有 当 前 程 序 在 运 行, 但 实 际 上, 操 作 系 统 中 有 很 多 程 序 都 会 在 不 同 时 间 执 行 各 种 各 样 的 任 务, 如 果 此 刻 其 他 进 程 使 用 了 10% 的 CPU, 那 我 们 的 程 序 应 该 只 能 使 用 40% 的 CPU( 而 不 是 机 械 地 占 用 50%), 这 样 可 达 到 50% 的 效 果 怎 么 做 呢? 我 们 得 知 道 当 前 CPU 占 用 率 是 多 少, 这 就 要 用 到 另 一 个 工 具 来 帮 忙 Perfmon.exe Perfmon 是 从 Windows NT 开 始 就 包 含 在 Windows 服 务 器 和 台 式 机 操 作 系 统 的 管 理 工 具 组 中 的 专 业 监 视 工 具 之 一 ( 如 图 1-2 所 示 ) Perfmon 可 监 视 各 类 系 统 计 数 器, 获 取 有 关 操 作 系 统 应 用 程 序 和 硬 件 的 统 计 数 字 Perfmon 的 用 法 相 当 直 接, 只 要 选 择 您 所 要 监 视 的 对 象 ( 比 如 : 处 理 器 RAM 或 硬 盘 ), 然 后 选 择 所 要 监 视 的 计 数 器 ( 比 如 监 视 物 理 磁 盘 对 象 时 的 平 均 队 列 长 度 ) 即 可 还 可 以 选 择 所 要 监 视 的 实 例, 比 如 面 对 一 台 多 CPU 服 务 器 时, 可 以 选 择 监 视 特 定 的 处 理 器 图 1-2 系 统 监 视 器 (Perfmon) 我 们 可 以 写 程 序 来 查 询 Perfmon 的 值,Microsoft.Net Framework 提 供 了 PerformanceCounter() 这 一 类 型, 从 而 可 以 方 便 地 拿 到 当 前 各 种 计 算 机 性 能 数 据, 包 括 CPU 的 使 用 率 例 如 下 面 这 个 程 序 解 法 三 能 动 态 适 应 的 解 法 编 程 之 美 微 软 技 术 面 试 心 得

24 6 1.1 让 CPU 占 用 率 曲 线 听 你 指 挥 代 码 清 单 1-3 //C# code static void MakeUsage(float level) PerformanceCounter p = new PerformanceCounter("Processor", "% Processor Time", "_Total"); while (true) if (p.nextvalue() > level) System.Threading.Thread.Sleep(10); 可 以 看 到, 上 面 的 解 法 能 方 便 地 处 理 各 种 CPU 使 用 率 参 数 这 个 程 序 可 以 解 答 前 面 提 到 的 问 题 2 有 了 前 面 的 积 累, 我 们 应 该 可 以 让 任 务 管 理 器 画 出 优 美 的 正 弦 曲 线 了, 见 下 面 的 代 码 解 法 四 正 弦 曲 线 代 码 清 单 1-4 //C++ code to make task manager generate sine graph #include "Windows.h" #include "stdlib.h" #include "math.h" const double SPLIT = 0.01; const int COUNT = 200; const double PI = ; const int INTERVAL = 300; int _tmain(int argc, _TCHAR* argv[]) DWORD busyspan[count]; //array of busy times DWORD idlespan[count]; //array of idle times int half = INTERVAL / 2; double radian = 0.0; for(int i = 0; i < COUNT; i++) busyspan[i] = (DWORD)(half + (sin(pi * radian) * half)); idlespan[i] = INTERVAL - busyspan[i]; radian += SPLIT; DWORD starttime = 0; int j = 0; while (true) j = j % COUNT; starttime = GetTickCount(); while ((GetTickCount() - starttime) <= busyspan[j]) ; Sleep(idleSpan[j]); j++; return 0; 编 程 之 美 微 软 技 术 面 试 心 得

25 1.1 让 CPU 占 用 率 曲 线 听 你 指 挥 7 讨 论 如 果 机 器 是 多 CPU, 上 面 的 程 序 会 出 现 什 么 结 果? 如 何 在 多 个 CPU 时 显 示 同 样 的 状 态? 例 如, 在 双 核 的 机 器 上, 如 果 让 一 个 单 线 程 的 程 序 死 循 环, 能 让 两 个 CPU 的 使 用 率 达 到 50% 的 水 平 么? 为 什 么? 多 CPU 的 问 题 首 先 需 要 获 得 系 统 的 CPU 信 息 可 以 使 用 GetProcessorInfo() 获 得 多 处 理 器 的 信 息, 然 后 指 定 进 程 在 哪 一 个 处 理 器 上 运 行 其 中 指 定 运 行 使 用 的 是 SetThreadAffinityMask() 函 数 另 外, 还 可 以 使 用 RDTSC 指 令 获 取 当 前 CPU 核 心 运 行 周 期 数 在 x86 平 台 上 定 义 函 数 : inline int64 GetCPUTickCount() asm rdtsc; 在 x64 平 台 上 定 义 : #define GetCPUTickCount() rdtsc() 使 用 CallNtPowerInformation API 得 到 CPU 频 率, 从 而 将 周 期 数 转 化 为 毫 秒 数, 例 如 : 代 码 清 单 1-5 _PROCESSOR_POWER_INFORMATION info; CallNTPowerInformation(11, //query processor power information NULL, //no input buffer 0, //input buffer size is zero &info, //output buffer Sizeof(info)); //outbuf size int64 t_begin = GetCPUTickCount(); //do something int64 t_end = GetCPUTickCount(); double millisec = ((double)t_end (double)t_begin)/(double)info.currentmhz; RDTSC 指 令 读 取 当 前 CPU 的 周 期 数, 在 多 CPU 系 统 中, 这 个 周 期 数 在 不 同 的 CPU 之 间 基 数 不 同, 频 率 也 有 可 能 不 同 用 从 两 个 不 同 的 CPU 得 到 的 周 期 数 作 计 算 会 得 出 没 有 意 义 的 值 如 果 线 程 在 运 行 中 被 调 度 到 了 不 同 的 CPU, 就 会 出 现 上 述 情 况 可 用 SetThreadAffinityMask 避 免 线 程 迁 移 另 外,CPU 的 频 率 会 随 系 统 供 电 及 负 荷 情 况 有 所 调 整 总 结 能 帮 助 你 了 解 当 前 线 程 / 进 程 / 系 统 效 能 的 API 大 致 有 以 下 这 些 : 编 程 之 美 微 软 技 术 面 试 心 得

26 8 1.1 让 CPU 占 用 率 曲 线 听 你 指 挥 1. Sleep() 这 个 方 法 能 让 当 前 线 程 停 下 来 2. WaitForSingleObject() 自 己 停 下 来, 等 待 某 个 事 件 发 生 3. GetTickCount() 有 人 把 Tick 翻 译 成 嘀 嗒, 很 形 象 4. QueryPerformanceFrequency() QueryPerformanceCounter() 让 你 访 问 到 精 度 更 高 的 CPU 数 据 5. timegetsystemtime() 是 另 一 个 得 到 高 精 度 时 间 的 方 法 6. PerformanceCounter 效 能 计 数 器 7. GetProcessorInfo()/SetThreadAffinityMask() 遇 到 多 核 的 问 题 怎 么 办 呢? 这 两 个 方 法 能 够 帮 你 更 好 地 控 制 CPU 8. GetCPUTickCount() 想 拿 到 CPU 核 心 运 行 周 期 数 吗? 用 用 这 个 方 法 吧 了 解 并 应 用 了 上 面 的 API, 就 可 以 考 虑 在 简 历 中 写 上 精 通 Windows 了 编 程 之 美 微 软 技 术 面 试 心 得

27 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 不 要 被 阶 乘 吓 倒 阶 乘 (Factorial) 是 个 很 有 意 思 的 函 数, 但 是 不 少 人 都 比 较 怕 它, 我 们 来 看 看 两 个 与 阶 乘 相 关 的 问 题 : 1. 给 定 一 个 整 数 N, 那 么 N 的 阶 乘 N! 末 尾 有 多 少 个 0 呢? 例 如 :N=10,N!= , N! 的 末 尾 有 两 个 0 2. 求 N! 的 二 进 制 表 示 中 最 低 位 1 的 位 置

28 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 分 析 与 解 法 有 些 人 碰 到 这 样 的 题 目 会 想 : 是 不 是 要 完 整 计 算 出 N! 的 值? 如 果 溢 出 怎 么 办? 事 实 上, 如 果 我 们 从 哪 些 数 相 乘 能 得 到 10 这 个 角 度 来 考 虑, 问 题 就 变 得 简 单 了 首 先 考 虑, 如 果 N!= K 10 M, 且 K 不 能 被 10 整 除, 那 么 N! 末 尾 有 M 个 0 再 考 虑 对 N! 进 行 质 因 数 分 解,N!=(2 x ) (3 y ) (5 z ), 由 于 10 = 2 5, 所 以 M 只 跟 X 和 Z 相 关, 每 一 对 2 和 5 相 乘 可 以 得 到 一 个 10, 于 是 M = min(x, Z) 不 难 看 出 X 大 于 等 于 Z, 因 为 能 被 2 整 除 的 数 出 现 的 频 率 比 能 被 5 整 除 的 数 高 得 多, 所 以 把 公 式 简 化 为 M = Z 根 据 上 面 的 分 析, 只 要 计 算 出 Z 的 值, 就 可 以 得 到 N! 末 尾 0 的 个 数 问 题 1 的 解 法 一 要 计 算 Z, 最 直 接 的 方 法, 就 是 计 算 i(i =1, 2,, N) 的 因 式 分 解 中 5 的 指 数, 然 后 求 和 : 代 码 清 单 2-6 ret = 0; for(i = 1; i <= N; i++) j = i; while(j % 5 ==0) ret++; j /= 5; 问 题 1 的 解 法 二 公 式 :Z = [N/5] +[N/5 2 ] +[N/5 3 ] + ( 不 用 担 心 这 会 是 一 个 无 穷 的 运 算, 因 为 总 存 在 一 个 K, 使 得 5 K > N,[N/5 K ]=0 ) 公 式 中,[N/5] 表 示 不 大 于 N 的 数 中 5 的 倍 数 贡 献 一 个 5,[N/5 2 ] 表 示 不 大 于 N 的 数 中 5 2 的 倍 数 再 贡 献 一 个 5, 代 码 如 下 : ret = 0; while(n) ret += N / 5; N /= 5; 问 题 2 要 求 的 是 N! 的 二 进 制 表 示 中 最 低 位 1 的 位 置 给 定 一 个 整 数 N, 求 N! 二 进 制 表 示 的 最 低 位 1 在 第 几 位? 例 如 : 给 定 N = 3,N!= 6, 那 么 N! 的 二 进 制 表 示 (1 010) 的 最 低 位 1 在 第 二 位

29 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 为 了 得 到 更 好 的 解 法, 首 先 要 对 题 目 进 行 一 下 转 化 首 先 来 看 一 下 一 个 二 进 制 数 除 以 2 的 计 算 过 程 和 结 果 是 怎 样 的 把 一 个 二 进 制 数 除 以 2, 实 际 过 程 如 下 : 判 断 最 后 一 个 二 进 制 位 是 否 为 0, 若 为 0, 则 将 此 二 进 制 数 右 移 一 位, 即 为 商 值 ( 为 什 么 ); 反 之, 若 为 1, 则 说 明 这 个 二 进 制 数 是 奇 数, 无 法 被 2 整 除 ( 这 又 是 为 什 么 ) 所 以, 这 个 问 题 实 际 上 等 同 于 求 N! 含 有 质 因 数 2 的 个 数 即 答 案 等 于 N! 含 有 质 因 数 2 的 个 数 加 1 问 题 2 的 解 法 一 由 于 N! 中 含 有 质 因 数 2 的 个 数, 等 于 N/2 + N/4 + N/8 + N/16 + 1, 根 据 上 述 分 析, 得 到 具 体 算 法, 如 下 所 示 : 代 码 清 单 2-7 int lowestone(int N) int Ret = 0; while(n) N >>= 1; Ret += N; return Ret; 问 题 2 的 解 法 二 N! 含 有 质 因 数 2 的 个 数, 还 等 于 N 减 去 N 的 二 进 制 表 示 中 1 的 数 目 我 们 还 可 以 通 过 这 个 规 律 来 求 解 下 面 对 这 个 规 律 进 行 举 例 说 明, 假 设 N = 11011, 那 么 N! 中 含 有 质 因 数 2 的 个 数 为 N/2 + N/4 + N/8 + N/16 + 即 : =( ) +( ) +(10 + 1) + 1 =( )+( )+ 1 = =( )+(1000-1)+(10-1)+(1-1) 1 这 个 规 律 请 读 者 自 己 证 明 ( 提 示 N/k, 等 于 1, 2, 3,, N 中 能 被 k 整 除 的 数 的 个 数 )

30 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 = N 二 进 制 表 示 中 1 的 个 数 小 结 任 意 一 个 长 度 为 m 的 二 进 制 数 N 可 以 表 示 为 N = b[1] + b[2] * 2 + b[3] * b[m] * 2 (m-1), 其 中 b [ i ] 表 示 此 二 进 制 数 第 i 位 上 的 数 字 (1 或 0) 所 以, 若 最 低 位 b[1] 为 1, 则 说 明 N 为 奇 数 ; 反 之 为 偶 数, 将 其 除 以 2, 即 等 于 将 整 个 二 进 制 数 向 低 位 移 一 位 相 关 题 目 给 定 整 数 n, 判 断 它 是 否 为 2 的 方 幂 ( 解 答 提 示 :n>0&&((n&(n-1))==0))

31 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 中 国 象 棋 将 帅 问 题 下 过 中 国 象 棋 的 朋 友 都 知 道, 双 方 的 将 和 帅 相 隔 遥 远, 并 且 它 们 不 能 照 面 在 象 棋 残 局 中, 许 多 高 手 能 利 用 这 一 规 则 走 出 精 妙 的 杀 招 假 设 棋 盘 上 只 有 将 和 帅 二 子 ( 如 图 1-3 所 示 )( 为 了 下 面 叙 述 方 便, 我 们 约 定 用 A 表 示 将,B 表 示 帅 ): 图 1-3 A B 二 子 被 限 制 在 己 方 3 3 的 格 子 里 运 动 例 如, 在 如 上 的 表 格 里,A 被 正 方 形 d 10, f 10, d 8, f 8 包 围, 而 B 被 正 方 形 d 3, f 3, d 1, f 1 包 围 每 一 步,A B 分 别 可 以 横 向 或 纵 向 移 动 一 格, 但 不 能 沿 对 角 线 移 动 另 外,A 不 能 面 对 B, 也 就 是 说,A 和 B 不 能 处 于 同 一 纵 向 直 线 上 ( 比 如 A 在 d 10 的 位 置, 那 么 B 就 不 能 在 d 1 d 2 以 及 d 3 ) 请 写 出 一 个 程 序, 输 出 A B 所 有 合 法 位 置 要 求 在 代 码 中 只 能 使 用 一 个 变 量

32 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 分 析 与 解 法 问 题 的 本 身 并 不 复 杂, 只 要 把 所 有 A B 互 相 排 斥 的 条 件 列 举 出 来 就 可 以 完 成 本 题 的 要 求 由 于 本 题 要 求 只 能 使 用 一 个 变 量, 所 以 必 须 首 先 想 清 楚 在 写 代 码 的 时 候, 有 哪 些 信 息 需 要 存 储, 并 且 尽 量 高 效 率 地 存 储 信 息 稍 微 思 考 一 下, 可 以 知 道 这 个 程 序 的 大 体 框 架 是 : 遍 历 A 的 位 置 遍 历 B 的 位 置 判 断 A B 的 位 置 组 合 是 否 满 足 要 求 如 果 满 足, 则 输 出 因 此, 需 要 存 储 的 是 A B 的 位 置 信 息, 并 且 每 次 循 环 都 要 更 新 为 了 能 够 进 行 判 断, 首 先 需 要 创 建 一 个 逻 辑 的 坐 标 系 统, 以 便 检 测 A 何 时 会 面 对 B 这 里 我 们 想 到 的 方 法 是 用 1~9 的 数 字, 按 照 行 优 先 的 顺 序 来 表 示 每 个 格 点 的 位 置 ( 如 图 1-4 所 示 ) 这 样, 只 需 要 用 模 余 运 算 就 可 以 得 到 当 前 的 列 号, 从 而 判 断 A B 是 否 互 斥 图 1-4 用 1~9 的 数 字 表 示 A B 的 坐 标 第 二, 题 目 要 求 只 用 一 个 变 量, 但 是 我 们 却 要 存 储 A 和 B 两 个 子 的 位 置 信 息, 该 怎 么 办 呢? 可 以 先 把 已 知 变 量 类 型 列 举 一 下, 然 后 做 些 分 析 对 于 bool 类 型, 估 计 没 有 办 法 做 任 何 扩 展 了, 因 为 它 只 能 表 示 true 和 false 两 个 值 ; 而 byte 或 者 int 类 型, 它 们 能 够 表 达 的 信 息 则 更 多 事 实 上, 对 本 题 来 说, 每 个 子 都 只 需 要 9 个 数 字 就 可 以 表 达 它 的 全 部 位 置 一 个 8 位 的 byte 类 型 能 够 表 达 2 8 =256 个 值, 所 以 用 它 来 表 示 A B 的 位 置 信 息 绰 绰 有 余, 因 此 可 以 把 这 个 字 节 的 变 量 ( 设 为 b) 分 成 两 部 分 用 前 面 的 4 bit 表 示 A 的 位 置, 用 后 面 的 4 bit 表 示 B 的 位 置, 那 么 4 个 bit 可 以 表 示 16 个 数, 这 已 经 足 够 了 问 题 在 于 : 如 何 使 用 bit 级 的 运 算 将 数 据 从 这 一 byte 变 量 的 左 边 和 右 边 分 别 存 入 和 读 出 下 面 是 做 法 : 将 byte b( ) 的 右 边 4 bit(0101) 设 为 n(0011): 首 先 清 除 b 右 边 的 bits, 同 时 保 持 左 边 的 bits:

33 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 (LMASK) & (b) 然 后 将 上 一 步 得 到 的 结 果 与 n 做 或 运 算 (LMASK & b) ^ (n) 将 byte b( ) 左 边 的 4 bit(1010) 设 为 n(0011): 首 先, 清 除 b 左 边 的 bits, 同 时 保 持 右 边 的 bits: (RMASK) & (b) 现 在, 把 n 移 动 到 byte 数 据 的 左 边 n << 4 = 然 后 对 以 上 两 步 得 到 的 结 果 做 或 运 算, 从 而 得 到 最 终 结 果 (RMASK & b) ^ (n << 4)

34 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 得 到 byte 数 据 的 右 边 4 bits 或 左 边 4 bits(e.g 中 的 1010 以 及 0101): 清 除 b 左 边 的 bits, 同 时 保 持 右 边 的 bits (RMASK) & (b) 清 除 b 的 右 边 的 bits, 同 时 保 持 左 边 的 bits (LMASK) & (b) 将 结 果 右 移 4 bits >> 4 = 最 后 的 挑 战 是 如 何 在 不 声 明 其 他 变 量 约 束 的 前 提 下 创 建 一 个 for 循 环 可 以 重 复 利 用 1byte 的 存 储 单 元, 把 它 作 为 循 环 计 数 器 并 用 前 面 提 到 的 存 取 和 读 入 技 术 进 行 操 作 还 可 以 用 宏 来 抽 象 化 代 码, 例 如 : for (LSET(b, 1); LGET(b) <= GRIDW * GRIDW; LSET(b, (LGET(b) + 1))) 解 法 一 代 码 清 单 1-6 #define HALF_BITS_LENGTH 4 // 这 个 值 是 记 忆 存 储 单 元 长 度 的 一 半, 在 这 道 题 里 是 4bit #define FULLMASK 255 // 这 个 数 字 表 示 一 个 全 部 bit 的 mask, 在 二 进 制 表 示 中, 它 是 #define LMASK (FULLMASK << HALF_BITS_LENGTH) // 这 个 宏 表 示 左 bits 的 mask, 在 二 进 制 表 示 中, 它 是 #define RMASK (FULLMASK >> HALF_BITS_LENGTH) // 这 个 数 字 表 示 右 bits 的 mask, 在 二 进 制 表 示 中, 它 表 示 #define RSET(b, n) (b = ((LMASK & b) ^ n)) // 这 个 宏, 将 b 的 右 边 设 置 成 n #define LSET(b, n) (b = ((RMASK & b) ^ (n << HALF_BITS_LENGTH))) // 这 个 宏, 将 b 的 左 边 设 置 成 n #define RGET(b) (RMASK & b) // 这 个 宏 得 到 b 的 右 边 的 值 #define LGET(b) ((LMASK & b) >> HALF_BITS_LENGTH) // 这 个 宏 得 到 b 的 左 边 的 值 #define GRIDW 3 // 这 个 数 字 表 示 将 帅 移 动 范 围 的 行 宽 度 #include <stdio.h> #define HALF_BITS_LENGTH 4 #define FULLMASK 255 #define LMASK (FULLMASK << HALF_BITS_LENGTH) #define RMASK (FULLMASK >> HALF_BITS_LENGTH) #define RSET(b, n) (b = ((LMASK & b) ^ n)) #define LSET(b, n) (b = ((RMASK & b) ^ (n << HALF_BITS_LENGTH))) #define RGET(b) (RMASK & b) #define LGET(b) ((LMASK & b) >> HALF_BITS_LENGTH) #define GRIDW 3

35 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 int main() unsigned char b; for(lset(b, 1); LGET(b) <= GRIDW * GRIDW; LSET(b, (LGET(b) + 1))) for(rset(b, 1); RGET(b) <= GRIDW * GRIDW; RSET(b, (RGET(b) + 1))) if(lget(b) % GRIDW!= RGET(b) % GRIDW) printf("a = %d, B = %d\n", LGET(b), RGET(b)); return 0; 输 出 格 子 的 位 置 用 N 来 表 示,N = 1, 2,, 8, 9, 依 照 行 优 先 的 顺 序, 如 图 1-5 所 示 : 将 (A) 的 格 子 帅 (B) 的 格 子 图 1-5

36 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 A = 1, B = 2 A = 1, B = 3 A = 1, B = 5 A = 1, B = 6 A = 1, B = 8 A = 1, B = 9 A = 2, B = 1 A = 2, B = 3 A = 2, B = 4 A = 2, B = 6 A = 2, B = 7 A = 2, B = 9 A = 3, B = 1 A = 3, B = 2 A = 3, B = 4 A = 3, B = 5 A = 3, B = 7 A = 3, B = 8 A = 4, B = 2 A = 4, B = 3 A = 4, B = 5 A = 4, B = 6 A = 4, B = 8 A = 4, B = 9 A = 5, B = 1 A = 5, B = 3 A = 5, B = 4 A = 5, B = 6 A = 5, B = 7 A = 5, B = 9 A = 6, B = 1 A = 6, B = 2 A = 6, B = 4 A = 6, B = 5 A = 6, B = 7 A = 6, B = 8 A = 7, B = 2 A = 7, B = 3 A = 7, B = 5 A = 7, B = 6 A = 7, B = 8 A = 7, B = 9 A = 8, B = 1 A = 8, B = 3 A = 8, B = 4 A = 8, B = 6 A = 8, B = 7 A = 8, B = 9 A = 9, B = 1 A = 9, B = 2 A = 9, B = 4 A = 9, B = 5 A = 9, B = 7 A = 9, B = 8 考 虑 了 这 么 多 因 素, 总 算 得 到 了 本 题 的 一 个 解 法, 但 是 MSRA 里 却 有 人 说, 下 面 的 一 小 段 代 码 也 能 达 到 同 样 的 目 的 : BYTE i = 81; while(i--) if(i / 9 % 3 == i % 9 % 3) continue; printf( A = %d, B = %d\n, i / 9 + 1, i % 9 + 1); 但 是 很 快 又 有 另 一 个 人 说 他 的 解 法 才 是 效 率 最 高 的 :

37 代 码 清 单 1-7 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 struct unsigned char a:4; unsigned char b:4; i; for(i.a = 1; i.a <= 9; i.a++) for(i.b = 1; i.b <= 9; i.b++) if(i.a % 3 == i.b % 3) printf( A = %d, B = %d\n, i.a, i.b); 读 者 能 自 己 证 明 一 下 么? 1 1 这 一 题 目 由 微 软 亚 洲 研 究 院 工 程 师 Matt Scott 提 供, 他 在 学 习 中 国 象 棋 的 时 候 想 出 了 这 个 题 目, 后 来 一 位 应 聘 者 给 出 了 比 他 的 正 解 简 明 很 多 的 答 案, 他 们 现 在 成 了 同 事

38 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 子 数 组 的 最 大 乘 积 给 定 一 个 长 度 为 N 的 整 数 数 组, 只 允 许 用 乘 法, 不 能 用 除 法, 计 算 任 意 (N-1) 个 数 的 组 合 乘 积 中 最 大 的 一 组, 并 写 出 算 法 的 时 间 复 杂 度 我 们 把 所 有 可 能 的 (N-1) 个 数 的 组 合 找 出 来, 分 别 计 算 它 们 的 乘 积, 并 比 较 大 小 由 于 总 共 有 N 个 (N-1) 个 数 的 组 合, 总 的 时 间 复 杂 度 为 O(N 2 ), 但 显 然 这 不 是 最 好 的 解 法

39 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 分 析 与 解 法 解 法 一 在 计 算 机 科 学 中, 时 间 和 空 间 往 往 是 一 对 矛 盾 体, 不 过, 这 里 有 一 个 优 化 的 折 中 方 法 可 以 通 过 空 间 换 时 间 或 时 间 换 空 间 的 策 略 来 达 到 优 化 某 一 方 面 的 效 果 在 这 里, 是 否 可 以 通 过 空 间 换 时 间 来 降 低 时 间 复 杂 度 呢? 计 算 (N-1) 个 数 的 组 合 乘 积, 假 设 第 i 个 (0 i N-1) 元 素 被 排 除 在 乘 积 之 外 ( 如 图 2-13 所 示 ) 图 2-13 组 合 示 意 图 设 array[] 为 初 始 数 组,s[i] 表 示 数 组 前 i 个 元 素 的 乘 积, 其 中 1 i N,s[0] = 1( 边 界 条 件 ), 那 么 s[i]= s[i-1] array[i-1], 其 中 i = 1, 2,, N-1, N; 设 t[i] 表 示 数 组 后 (N-i) 个 元 素 的 乘 积, 其 中 1 i N,t[N+1]=1 ( 边 界 条 件 ), 那 么 t[i]=t[i+1] array[i], 其 中 i=1, 2,, N-1, N; 那 么 设 p[i] 为 数 组 除 第 i 个 元 素 外, 其 他 N-1 个 元 素 的 乘 积, 即 有 : p[i]=s[i-1] t[i+1] 由 于 只 需 要 从 头 至 尾, 和 从 尾 至 头 扫 描 数 组 两 次 即 可 得 到 数 组 s[] 和 t[], 进 而 线 性 时 间 可 以 得 到 p[] 所 以, 很 容 易 就 可 以 得 到 p[] 的 最 大 值 ( 只 需 遍 历 p[] 一 次 ) 总 的 时 间 复 杂 度 等 于 计 算 数 组 s[] t[] p[] 的 时 间 复 杂 度 加 上 查 找 p[] 最 大 值 的 时 间 复 杂 度 等 于 O(N)

40 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 解 法 二 其 实, 还 可 以 通 过 分 析, 进 一 步 减 少 解 答 问 题 的 计 算 量 假 设 N 个 整 数 的 乘 积 为 P, 针 对 P 的 正 负 性 进 行 如 下 分 析 ( 其 中,A N-1 表 示 N-1 个 数 的 组 合,P N-1 表 示 N-1 个 数 的 组 合 的 乘 积 ): 1. P 为 0 那 么, 数 组 中 至 少 包 含 有 一 个 0 假 设 除 去 一 个 0 之 外, 其 他 N-1 个 数 的 乘 积 为 Q, 根 据 Q 的 正 负 性 进 行 讨 论 : Q 为 0 说 明 数 组 中 至 少 有 两 个 0, 那 么 N-1 个 数 的 乘 积 只 能 为 0, 返 回 0; Q 为 正 数 返 回 Q, 因 为 如 果 以 0 替 换 此 时 A N-1 中 的 任 一 个 数, 所 得 到 的 P N-1 为 0, 必 然 小 于 Q; Q 为 负 数 如 果 以 0 替 换 此 时 A N-1 中 的 任 一 个 数, 所 得 到 的 P N-1 为 0, 大 于 Q, 乘 积 最 大 值 为 0 2. P 为 负 数 根 据 负 负 得 正 的 乘 法 性 质, 自 然 想 到 从 N 个 整 数 中 去 掉 一 个 负 数, 使 得 P N-1 为 一 个 正 数 而 要 使 这 个 正 数 最 大, 这 个 被 去 掉 的 负 数 的 绝 对 值 必 须 是 数 组 中 最 小 的 我 们 只 需 要 扫 描 一 遍 数 组, 把 绝 对 值 最 小 的 负 数 给 去 掉 就 可 以 了

41 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 3. P 为 正 数 类 似 P 为 负 数 的 情 况, 应 该 去 掉 一 个 绝 对 值 最 小 的 正 数 值, 这 样 得 到 的 P N-1 就 是 最 大 的 上 面 的 解 法 采 用 了 直 接 求 N 个 整 数 的 乘 积 P, 进 而 判 断 P 的 正 负 性 的 办 法, 但 是 直 接 求 乘 积 在 编 译 环 境 下 往 往 会 有 溢 出 的 危 险 ( 这 也 就 是 本 题 要 求 不 使 用 除 法 的 潜 在 用 意 ), 事 实 上 可 做 一 个 小 的 转 变, 不 需 要 直 接 求 乘 积, 而 是 求 出 数 组 中 正 数 (+) 负 数 (-) 和 0 的 个 数, 从 而 判 断 P 的 正 负 性, 其 余 部 分 与 以 上 面 的 解 法 相 同 在 时 间 复 杂 度 方 面, 由 于 只 需 要 遍 历 数 组 一 次, 在 遍 历 数 组 的 同 时 就 可 得 到 数 组 中 正 数 (+) 负 数 (-) 和 0 的 个 数, 以 及 数 组 中 绝 对 值 最 小 的 正 数 和 负 数, 时 间 复 杂 度 为 O(N)

42 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 寻 找 发 帖 水 王 Tango 是 微 软 亚 洲 研 究 院 的 一 个 试 验 项 目 研 究 院 的 员 工 和 实 习 生 们 都 很 喜 欢 在 Tango 上 面 交 流 灌 水 传 说,Tango 有 一 大 水 王, 他 不 但 喜 欢 发 贴, 还 会 回 复 其 他 ID 发 的 每 个 帖 子 坊 间 风 闻 该 水 王 发 帖 数 目 超 过 了 帖 子 总 数 的 一 半 如 果 你 有 一 个 当 前 论 坛 上 所 有 帖 子 ( 包 括 回 帖 ) 的 列 表, 其 中 帖 子 作 者 的 ID 也 在 表 中, 你 能 快 速 找 出 这 个 传 说 中 的 Tango 水 王 吗?

43 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 分 析 与 解 法 首 先 想 到 的 是 一 个 最 直 接 的 方 法, 我 们 可 以 对 所 有 ID 进 行 排 序 然 后 再 扫 描 一 遍 排 好 序 的 ID 列 表, 统 计 各 个 ID 出 现 的 次 数 如 果 某 个 ID 出 现 的 次 数 超 过 总 数 的 一 半, 那 么 就 输 出 这 个 ID 这 个 算 法 的 时 间 复 杂 度 为 O(N * log 2 N + N) 如 果 ID 列 表 已 经 是 有 序 的, 还 需 要 扫 描 一 遍 整 个 列 表 来 统 计 各 个 ID 出 现 的 次 数 吗? 如 果 一 个 ID 出 现 的 次 数 超 过 总 数 N 的 一 半 那 么, 无 论 水 王 的 ID 是 什 么, 这 个 有 序 的 ID 列 表 中 的 第 N/2 项 ( 从 0 开 始 编 号 ) 一 定 会 是 这 个 ID( 读 者 可 以 试 着 证 明 一 下 ) 省 去 重 新 扫 描 一 遍 列 表, 可 以 节 省 一 点 算 法 耗 费 的 时 间 如 果 能 够 迅 速 定 位 到 列 表 的 某 一 项 ( 比 如 使 用 数 组 来 存 储 列 表 ), 除 去 排 序 的 时 间 复 杂 度, 后 处 理 需 要 的 时 间 为 O(1) 但 上 面 两 种 方 法 都 需 要 先 对 ID 列 表 进 行 排 序, 时 间 复 杂 度 方 面 没 有 本 质 的 改 进 能 否 避 免 排 序 呢? 如 果 每 次 删 除 两 个 不 同 的 ID( 不 管 是 否 包 含 水 王 的 ID), 那 么, 在 剩 下 的 ID 列 表 中, 水 王 ID 出 现 的 次 数 仍 然 超 过 总 数 的 一 半 看 到 这 一 点 之 后, 就 可 以 通 过 不 断 重 复 这 个 过 程, 把 ID 列 表 中 的 ID 总 数 降 低 ( 转 化 为 更 小 的 问 题 ), 从 而 得 到 问 题 的 答 案 新 的 思 路, 避 免 了 排 序 这 个 耗 时 的 步 骤, 总 的 时 间 复 杂 度 只 有 O(N), 且 只 需 要 常 数 的 额 外 内 存 伪 代 码 如 下 : 代 码 清 单 2-8 Type Find(Type* ID, int N) Type candidate; int ntimes, i; for(i = ntimes = 0; i < N; i++) if(ntimes == 0) candidate = ID[i], ntimes = 1; else if(candidate == ID[i]) ntimes++; else ntimes--; return candidate; 在 这 个 题 目 中, 有 一 个 计 算 机 科 学 中 很 普 遍 的 思 想, 就 是 如 何 把 一 个 问 题 转 化 为 规 模 较 小 的 若 干 个 问 题 分 治 递 推 和 贪 心 等 都 是 基 于 这 样 的 思 路 在 转 化 过 程 中, 小 的 问 题 跟 原 问 题 本 质 上 一 致 这 样, 我 们 可 以 通 过 同 样 的 方 式 将 小 问 题 转 化 为 更 小 的 问 题 因 此, 转 化 过 程 是 很 重 要 的 像 上 面 这 个 题 目, 我 们 保 证 了 问 题 的 解 在 小 问 题 中 仍 然 具 有 与 原 问 题 相 同

44 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 的 性 质 : 水 王 的 ID 在 ID 列 表 中 的 次 数 超 过 一 半 转 化 本 身 计 算 的 效 率 越 高, 转 化 之 后 问 题 规 模 缩 小 得 越 快, 则 整 体 算 法 的 时 间 复 杂 度 越 低 扩 展 问 题 随 着 Tango 的 发 展, 管 理 员 发 现, 超 级 水 王 没 有 了 统 计 结 果 表 明, 有 3 个 发 帖 很 多 的 ID, 他 们 的 发 帖 数 目 都 超 过 了 帖 子 总 数 目 N 的 1/4 你 能 从 发 帖 ID 列 表 中 快 速 找 出 他 们 的 ID 吗?

45 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 寻 找 最 大 的 K 个 数 在 面 试 中, 有 下 面 的 问 答 : 问 : 有 很 多 个 无 序 的 数, 我 们 姑 且 假 定 它 们 各 不 相 等, 怎 么 选 出 其 中 最 大 的 若 干 个 数 呢? 答 : 可 以 这 样 写 :int array[100] 问 : 好, 如 果 有 更 多 的 元 素 呢? 答 : 那 可 以 改 为 :int array[1000] 问 : 如 果 我 们 有 很 多 元 素, 例 如 1 亿 个 浮 点 数, 怎 么 办? 答 : 个, 十, 百, 千, 万 那 可 以 写 :float array [ ] 问 : 这 样 的 程 序 能 编 译 运 行 么? 答 : 嗯 我 从 来 没 写 过 这 么 多 的 0

46 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 分 析 与 解 法 解 法 一 当 学 生 们 信 笔 写 下 float array [ ], 他 们 往 往 没 有 想 到 这 个 数 据 结 构 要 如 何 在 电 脑 上 实 现, 是 从 当 前 程 序 的 栈 (Stack) 中 分 配, 还 是 堆 (Heap), 还 是 电 脑 的 内 存 也 许 放 不 下 这 么 大 的 东 西? 我 们 先 假 设 元 素 的 数 量 不 大, 例 如 在 几 千 个 左 右, 在 这 种 情 况 下, 那 我 们 就 排 序 一 下 吧 在 这 里, 快 速 排 序 或 堆 排 序 都 是 不 错 的 选 择, 他 们 的 平 均 时 间 复 杂 度 都 是 O(N * log 2 N) 然 后 取 出 前 K 个,O(K) 总 时 间 复 杂 度 O (N * log 2 N)+ O(K) = O(N * log 2 N) 你 一 定 注 意 到 了, 当 K=1 时, 上 面 的 算 法 也 是 O(N * log 2 N) 的 复 杂 度, 而 显 然 我 们 可 以 通 过 N-1 次 的 比 较 和 交 换 得 到 结 果 上 面 的 算 法 把 整 个 数 组 都 进 行 了 排 序, 而 原 题 目 只 要 求 最 大 的 K 个 数, 并 不 需 要 前 K 个 数 有 序, 也 不 需 要 后 N-K 个 数 有 序 怎 么 能 够 避 免 做 后 N-K 个 数 的 排 序 呢? 我 们 需 要 部 分 排 序 的 算 法, 选 择 排 序 和 交 换 排 序 都 是 不 错 的 选 择 把 N 个 数 中 的 前 K 大 个 数 排 序 出 来, 复 杂 度 是 O(N * K) 那 一 个 更 好 呢?O(N * log 2 N) 还 是 O(N * K)? 这 取 决 于 K 的 大 小, 这 是 你 需 要 在 面 试 者 那 里 弄 清 楚 的 问 题 在 K(K < = log 2 N) 较 小 的 情 况 下, 可 以 选 择 部 分 排 序 在 下 一 个 解 法 中, 我 们 会 通 过 避 免 对 前 K 个 数 排 序 来 得 到 更 好 的 性 能 解 法 二 回 忆 一 下 快 速 排 序, 快 排 中 的 每 一 步, 都 是 将 待 排 数 据 分 做 两 组, 其 中 一 组 的 数 据 的 任 何 一 个 数 都 比 另 一 组 中 的 任 何 一 个 大, 然 后 再 对 两 组 分 别 做 类 似 的 操 作, 然 后 继 续 下 去 在 本 问 题 中, 假 设 N 个 数 存 储 在 数 组 S 中, 我 们 从 数 组 S 中 随 机 找 出 一 个 元 素 X, 把 数 组 分 为 两 部 分 S a 和 S b S a 中 的 元 素 大 于 等 于 X,S b 中 元 素 小 于 X 这 时, 有 两 种 可 能 性 :

47 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 1. S a 中 元 素 的 个 数 小 于 K,S a 中 所 有 的 数 和 S b 中 最 大 的 K- S a 个 元 素 ( S a 指 S a 中 元 素 的 个 数 ) 就 是 数 组 S 中 最 大 的 K 个 数 2. S a 中 元 素 的 个 数 大 于 或 等 于 K, 则 需 要 返 回 S a 中 最 大 的 K 个 元 素 这 样 递 归 下 去, 不 断 把 问 题 分 解 成 更 小 的 问 题, 平 均 时 间 复 杂 度 O(N * log 2 K) 伪 代 码 如 下 : 代 码 清 单 2-11 Kbig(S, k): if(k <= 0): return [] // 返 回 空 数 组 if(length S <= k): return S (Sa, Sb) = Partition(S) return Kbig(Sa, k).append(kbig(sb, k length Sa) Partition(S): Sa = [] // 初 始 化 为 空 数 组 Sb = [] // 初 始 化 为 空 数 组 // 随 机 选 择 一 个 数 作 为 分 组 标 准, 以 避 免 特 殊 数 据 下 的 算 法 退 化 // 也 可 以 通 过 对 整 个 数 据 进 行 洗 牌 预 处 理 实 现 这 个 目 的 // Swap(S[1], S[Random() % length S]) p = S[1] for i in [2: length S]: S[i] > p? Sa.Append(S[i]) : Sb.Append(S[i]) // 将 p 加 入 较 小 的 组, 可 以 避 免 分 组 失 败, 也 使 分 组 更 均 匀, 提 高 效 率 length S a < length S b? S a.append(p) : S b.append(p) return (S a, S b ) 解 法 三 寻 找 N 个 数 中 最 大 的 K 个 数, 本 质 上 就 是 寻 找 最 大 的 K 个 数 中 最 小 的 那 个, 也 就 是 第 K 大 的 数 可 以 使 用 二 分 搜 索 的 策 略 来 寻 找 N 个 数 中 的 第 K 大 的 数 对 于 一 个 给 定 的 数 p, 可 以 在 O(N) 的 时 间 复 杂 度 内 找 出 所 有 不 小 于 p 的 数 假 如 N 个 数 中 最 大 的 数 为 V max, 最 小 的 数 为 V min, 那 么 这 N 个 数 中 的 第 K 大 数 一 定 在 区 间 [V min, V max ] 之 间 那 么, 可 以 在 这 个 区 间 内 二 分 搜 索 N 个 数 中 的 第 K 大 数 p 伪 代 码 如 下 :

48 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 代 码 清 单 2-12 while(vmax Vmin > delta) Vmid = Vmin + (Vmax - Vmin) * 0.5; if(f(arr, N, Vmid) >= K) Vmin = Vmid; else Vmax = Vmid; 数 伪 代 码 中 f(arr, N, V mid ) 返 回 数 组 arr[0,, N-1] 中 大 于 等 于 V mid 的 数 的 个 上 述 伪 代 码 中,delta 的 取 值 要 比 所 有 N 个 数 中 的 任 意 两 个 不 相 等 的 元 素 差 值 之 最 小 值 小 如 果 所 有 元 素 都 是 整 数,delta 可 以 取 值 0.5 循 环 运 行 之 后, 得 到 一 个 区 间 (V min, V max ), 这 个 区 间 仅 包 含 一 个 元 素 ( 或 者 多 个 相 等 的 元 素 ) 这 个 元 素 就 是 第 K 大 的 元 素 整 个 算 法 的 时 间 复 杂 度 为 O(N * log 2 ( V max - V min /delta)) 由 于 delta 的 取 值 要 比 所 有 N 个 数 中 的 任 意 两 个 不 相 等 的 元 素 差 值 之 最 小 值 小, 因 此 时 间 复 杂 度 跟 数 据 分 布 相 关 在 数 据 分 布 平 均 的 情 况 下, 时 间 复 杂 度 为 O(N * log 2 (N)) 在 整 数 的 情 况 下, 可 以 从 另 一 个 角 度 来 看 这 个 算 法 假 设 所 有 整 数 的 大 小 都 在 [0, 2 m-1 ] 之 间, 也 就 是 说 所 有 整 数 在 二 进 制 中 都 可 以 用 m bit 来 表 示 ( 从 低 位 到 高 位, 分 别 用 0, 1,, m-1 标 记 ) 我 们 可 以 先 考 察 在 二 进 制 位 的 第 (m-1) 位, 将 N 个 整 数 按 该 位 为 1 或 者 0 分 成 两 个 部 分 也 就 是 将 整 数 分 成 取 值 为 [0, 2 m-1-1] 和 [2 m-1, 2 m -1] 两 个 区 间 前 一 个 区 间 中 的 整 数 第 (m-1) 位 为 0, 后 一 个 区 间 中 的 整 数 第 (m-1) 位 为 1 如 果 该 位 为 1 的 整 数 个 数 A 大 于 等 于 K, 那 么, 在 所 有 该 位 为 1 的 整 数 中 继 续 寻 找 最 大 的 K 个 否 则, 在 该 位 为 0 的 整 数 中 寻 找 最 大 的 K-A 个 接 着 考 虑 二 进 制 位 第 (m-2) 位, 以 此 类 推 思 路 跟 上 面 的 浮 点 数 的 情 况 本 质 上 一 样 对 于 上 面 两 个 方 法, 我 们 都 需 要 遍 历 一 遍 整 个 集 合, 统 计 在 该 集 合 中 大 于 等 于 某 一 个 数 的 整 数 有 多 少 个 不 需 要 做 随 机 访 问 操 作, 如 果 全 部 数 据 不 能 载 入 内 存, 可 以 每 次 都 遍 历 一 遍 文 件 经 过 统 计, 更 新 解 所 在 的 区 间 之 后, 再 遍 历 一 次 文 件, 把 在 新 的 区 间 中 的 元 素 存 入 新 的 文 件 下 一 次 操 作 的 时 候, 不 再 需 要 遍 历 全 部 的 元 素 每 次 需 要 两 次 文 件 遍 历, 最 坏 情 况 下, 总 共 需 要 遍 历 文 件 的 次 数 为 2 * log 2 ( V max - V min /delta) 由 于 每 次 更 新 解 所 在 区 间 之 后, 元 素 数 目 会 减 少 当 所 有 元 素 能 够 全 部 载 入 内 存 之 后, 就 可 以 不 再 通 过 读 写 文 件 的 方 式 来 操 作 了

49 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 此 外, 寻 找 N 个 数 中 的 第 K 大 数, 是 一 个 经 典 问 题 理 论 上, 这 个 问 题 存 在 线 性 算 法 不 过 这 个 线 性 算 法 的 常 数 项 比 较 大, 在 实 际 应 用 中 效 果 有 时 并 不 好 解 法 四 我 们 已 经 得 到 了 三 个 解 法, 不 过 这 三 个 解 法 有 个 共 同 的 地 方, 就 是 需 要 对 数 据 访 问 多 次, 那 么 就 有 下 一 个 问 题, 如 果 N 很 大 呢,100 亿?( 更 多 的 情 况 下, 是 面 试 者 问 你 这 个 问 题 ) 这 个 时 候 数 据 不 能 全 部 装 入 内 存 ( 不 过 也 很 难 说, 说 知 道 以 后 会 不 会 1T 内 存 比 1 斤 白 菜 还 便 宜 ), 所 以 要 求 尽 可 能 少 的 遍 历 所 有 数 据 不 妨 设 N > K, 前 K 个 数 中 的 最 大 K 个 数 是 一 个 退 化 的 情 况, 所 有 K 个 数 就 是 最 大 的 K 个 数 如 果 考 虑 第 K+1 个 数 X 呢? 如 果 X 比 最 大 的 K 个 数 中 的 最 小 的 数 Y 小, 那 么 最 大 的 K 个 数 还 是 保 持 不 变 如 果 X 比 Y 大, 那 么 最 大 的 K 个 数 应 该 去 掉 Y, 而 包 含 X 如 果 用 一 个 数 组 来 存 储 最 大 的 K 个 数, 每 新 加 入 一 个 数 X, 就 扫 描 一 遍 数 组, 得 到 数 组 中 最 小 的 数 Y 用 X 替 代 Y, 或 者 保 持 原 数 组 不 变 这 样 的 方 法, 所 耗 费 的 时 间 为 O(N * K) 进 一 步, 可 以 用 容 量 为 K 的 最 小 堆 来 存 储 最 大 的 K 个 数 最 小 堆 的 堆 顶 元 素 就 是 最 大 K 个 数 中 最 小 的 一 个 每 次 新 考 虑 一 个 数 X, 如 果 X 比 堆 顶 的 元 素 Y 小, 则 不 需 要 改 变 原 来 的 堆, 因 为 这 个 元 素 比 最 大 的 K 个 数 小 如 果 X 比 堆 顶 元 素 大, 那 么 用 X 替 换 堆 顶 的 元 素 Y 在 X 替 换 堆 顶 元 素 Y 之 后,X 可 能 破 坏 最 小 堆 的 结 构 ( 每 个 结 点 都 比 它 的 父 亲 结 点 大 ), 需 要 更 新 堆 来 维 持 堆 的 性 质 更 新 过 程 花 费 的 时 间 复 杂 度 为 O(log 2 K) 图 2-1

50 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 图 2-1 是 一 个 堆, 用 一 个 数 组 h[] 表 示 每 个 元 素 h[i], 它 的 父 亲 结 点 是 h[i/2], 儿 子 结 点 是 h[2 * i + 1] 和 h[2 * i + 2] 每 新 考 虑 一 个 数 X, 需 要 进 行 的 更 新 操 作 伪 代 码 如 下 : 代 码 清 单 2-13 if(x > h[0]) h[0] = X; p = 0; while(p < K) q = 2 * p + 1; if(q >= K) break; if((q < K 1) && (h[q + 1] < h[q])) q = q + 1; if(h[q] < h[p]) t = h[p]; h[p] = h[q]; h[q] = t; p = q; else break; 因 此, 算 法 只 需 要 扫 描 所 有 的 数 据 一 次, 时 间 复 杂 度 为 O(N * log 2 K) 这 实 际 上 是 部 分 执 行 了 堆 排 序 的 算 法 在 空 间 方 面, 由 于 这 个 算 法 只 扫 描 所 有 的 数 据 一 次, 因 此 我 们 只 需 要 存 储 一 个 容 量 为 K 的 堆 大 多 数 情 况 下, 堆 可 以 全 部 载 入 内 存 如 果 K 仍 然 很 大, 我 们 可 以 尝 试 先 找 最 大 的 K 个 元 素, 然 后 找 第 K +1 个 到 第 2 * K 个 元 素, 如 此 类 推 ( 其 中 容 量 K 的 堆 可 以 完 全 载 入 内 存 ) 不 过 这 样, 我 们 需 要 扫 描 所 有 数 据 ceil 1 (K/K ) 次 解 法 五 上 面 类 快 速 排 序 的 方 法 平 均 时 间 复 杂 度 是 线 性 的 能 否 有 确 定 的 线 性 算 法 呢? 是 否 可 以 通 过 改 进 计 数 排 序 基 数 排 序 等 来 得 到 一 个 更 高 效 的 算 法 呢? 答 案 是 肯 定 的 但 算 法 的 适 用 范 围 会 受 到 一 定 的 限 制 1 ceil(ceiling, 天 花 板 之 意 ) 表 示 大 于 等 于 一 个 浮 点 数 的 最 小 整 数

51 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 如 果 所 有 N 个 数 都 是 正 整 数, 且 它 们 的 取 值 范 围 不 太 大, 可 以 考 虑 申 请 空 间, 记 录 每 个 整 数 出 现 的 次 数, 然 后 再 从 大 到 小 取 最 大 的 K 个 比 如, 所 有 整 数 都 在 (0, MAXN) 区 间 中 的 话, 利 用 一 个 数 组 count[maxn] 来 记 录 每 个 整 数 出 现 的 个 数 (count[i] 表 示 整 数 i 在 所 有 整 数 中 出 现 的 个 数 ) 我 们 只 需 要 扫 描 一 遍 就 可 以 得 到 count 数 组 然 后, 寻 找 第 K 大 的 元 素 : 代 码 清 单 2-14 for(sumcount = 0, v = MAXN 1; v >= 0; v--) sumcount += count[v]; if(sumcount >= K) break; return v; 极 端 情 况 下, 如 果 N 个 整 数 各 不 相 同, 我 们 甚 至 只 需 要 一 个 bit 来 存 储 这 个 整 数 是 否 存 在 当 实 际 情 况 下, 并 不 一 定 能 保 证 所 有 元 素 都 是 正 整 数, 且 取 值 范 围 不 太 大 上 面 的 方 法 仍 然 可 以 推 广 适 用 如 果 N 个 数 中 最 大 的 数 为 V max, 最 小 的 数 为 V min, 我 们 可 以 把 这 个 区 间 [V min, V max ] 分 成 M 块, 每 个 小 区 间 的 跨 度 为 d =(V max V min ) /M, 即 [V min, V min +d], [V min + d, V min + 2d], 然 后, 扫 描 一 遍 所 有 元 素, 统 计 各 个 小 区 间 中 的 元 素 个 数, 跟 上 面 方 法 类 似 地, 我 们 可 以 知 道 第 K 大 的 元 素 在 哪 一 个 小 区 间 然 后, 再 对 那 个 小 区 间, 继 续 进 行 分 块 处 理 这 个 方 法 介 于 解 法 三 和 类 计 数 排 序 方 法 之 间, 不 能 保 证 线 性 跟 解 法 三 类 似 地, 时 间 复 杂 度 为 O ((N+M)* log 2 M( V max - V min /delta)) 遍 历 文 件 的 次 数 为 2 * log 2 M( V max - V min /delta) 当 然, 我 们 需 要 找 一 个 尽 量 大 的 M, 但 M 取 值 要 受 内 存 限 制 在 这 道 题 中, 我 们 根 据 K 和 N 的 相 对 大 小, 设 计 了 不 同 的 算 法 在 实 际 面 试 中, 如 果 一 个 面 试 者 能 针 对 一 个 问 题, 说 出 多 种 不 同 的 方 法, 并 且 分 析 它 们 各 自 适 用 的 情 况, 那 一 定 会 给 人 留 下 深 刻 印 象 注 : 本 题 目 的 解 答 中 用 到 了 多 种 排 序 算 法, 这 些 算 法 在 大 部 分 的 算 法 书 籍 中 都 有 讲 解 掌 握 排 序 算 法 对 工 作 也 会 很 有 帮 助 扩 展 问 题

52 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 3. 如 果 需 要 找 出 N 个 数 中 最 大 的 K 个 不 同 的 浮 点 数 呢? 比 如, 含 有 10 个 浮 点 数 的 数 组 (1.5, 1.5, 2.5, 2.5, 3.5, 3.5, 5, 0, -1.5, 3.5) 中 最 大 的 3 个 不 同 的 浮 点 数 是 (5, 3.5, 2.5) 4. 如 果 是 找 第 k 到 m(0 < k < = m < = n) 大 的 数 呢? 5. 在 搜 索 引 擎 中, 网 络 上 的 每 个 网 页 都 有 权 威 性 权 重, 如 page rank 如 果 我 们 需 要 寻 找 权 重 最 大 的 K 个 网 页, 而 网 页 的 权 重 会 不 断 地 更 新, 那 么 算 法 要 如 何 变 动 以 达 到 快 速 更 新 (incremental update) 并 及 时 返 回 权 重 最 大 的 K 个 网 页? 提 示 : 堆 排 序? 当 每 一 个 网 页 权 重 更 新 的 时 候, 更 新 堆 还 有 更 好 的 方 法 吗? 6. 在 实 际 应 用 中, 还 有 一 个 精 确 度 的 问 题 我 们 可 能 并 不 需 要 返 回 严 格 意 义 上 的 最 大 的 K 个 元 素, 在 边 界 位 置 允 许 出 现 一 些 误 差 当 用 户 输 入 一 个 query 的 时 候, 对 于 每 一 个 文 档 d 来 说, 它 跟 这 个 query 之 间 都 有 一 个 相 关 性 衡 量 权 重 f (query, d) 搜 索 引 擎 需 要 返 回 给 用 户 的 就 是 相 关 性 权 重 最 大 的 K 个 网 页 如 果 每 页 10 个 网 页, 用 户 不 会 关 心 第 1000 页 开 外 搜 索 结 果 的 精 确 度, 稍 有 误 差 是 可 以 接 受 的 比 如 我 们 可 以 返 回 相 关 性 第 大 的 网 页, 而 不 是 第 9999 大 的 在 这 种 情 况 下, 算 法 该 如 何 改 进 才 能 更 快 更 有 效 率 呢? 网 页 的 数 目 可 能 大 到 一 台 机 器 无 法 容 纳 得 下, 这 时 怎 么 办 呢? 提 示 : 归 并 排 序? 如 果 每 台 机 器 都 返 回 最 相 关 的 K 个 文 档, 那 么 所 有 机 器 上 最 相 关 K 个 文 档 的 并 集 肯 定 包 含 全 集 中 最 相 关 的 K 个 文 档 由 于 边 界 情 况 并 不 需 要 非 常 精 确, 如 果 每 台 机 器 返 回 最 好 的 K 个 文 档, 那 么 K 应 该 如 何 取 值, 以 达 到 我 们 返 回 最 相 关 的 90%*K 个 文 档 是 完 全 精 确 的, 或 者 最 终 返 回 的 最 相 关 的 K 个 文 档 精 确 度 超 过 90%( 最 相 关 的 K 个 文 档 中

53 写 书 评, 赢 取 编 程 之 美 -- 微 软 技 术 面 试 心 得 90% 以 上 在 全 集 中 相 关 性 的 确 排 在 前 K), 或 者 最 终 返 回 的 最 相 关 的 K 个 文 档 最 差 的 相 关 性 排 序 没 有 超 出 110%*K 7. 如 第 4 点 所 说, 对 于 每 个 文 档 d, 相 对 于 不 同 的 关 键 字 q 1, q 2,, q m, 分 别 有 相 关 性 权 重 f(d, q 1 ),f(d, q 2 ),, f(d, q m ) 如 果 用 户 输 入 关 键 字 q i 之 后, 我 们 已 经 获 得 了 最 相 关 的 K 个 文 档, 而 已 知 关 键 字 q j 跟 关 键 字 q i 相 似, 文 档 跟 这 两 个 关 键 字 的 权 重 大 小 比 较 靠 近, 那 么 关 键 字 q i 的 最 相 关 的 K 个 文 档, 对 寻 找 q j 最 相 关 的 K 个 文 档 有 没 有 帮 助 呢?

54 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 求 二 叉 树 中 节 点 的 最 大 距 离 如 果 我 们 把 二 叉 树 看 成 一 个 图, 父 子 节 点 之 间 的 连 线 看 成 是 双 向 的, 我 们 姑 且 定 义 距 离 为 两 个 节 点 之 间 边 的 个 数 写 一 个 程 序 求 一 棵 二 叉 树 中 相 距 最 远 的 两 个 节 点 之 间 的 距 离 如 图 3-11 所 示, 粗 箭 头 的 边 表 示 最 长 距 离 : 图 3-11 树 中 相 距 最 远 的 两 个 节 点 A,B

55 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 分 析 与 解 法 我 们 先 画 几 个 不 同 形 状 的 二 叉 树,( 如 图 3-12 所 示 ), 看 看 能 否 得 到 一 些 启 示 图 3-12 几 个 例 子 从 例 子 中 可 以 看 出, 相 距 最 远 的 两 个 节 点, 一 定 是 两 个 叶 子 节 点, 或 者 是 一 个 叶 子 节 点 到 它 的 根 节 点 ( 为 什 么?) 解 法 一 根 据 相 距 最 远 的 两 个 节 点 一 定 是 叶 子 节 点 这 个 规 律, 我 们 可 以 进 一 步 讨 论 对 于 任 意 一 个 节 点, 以 该 节 点 为 根, 假 设 这 个 根 有 K 个 孩 子 节 点, 那 么 相 距 最 远 的 两 个 节 点 U 和 V 之 间 的 路 径 与 这 个 根 节 点 的 关 系 有 两 种 情 况 : 1. 若 路 径 经 过 根 Root, 则 U 和 V 是 属 于 不 同 子 树 的, 且 它 们 都 是 该 子 树 中 到 根 节 点 最 远 的 节 点, 否 则 跟 它 们 的 距 离 最 远 相 矛 盾 这 种 情 况 如 图 3-13 所 示 : 图 3-13 相 距 最 远 的 节 点 在 左 右 最 长 的 子 树 中

56 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 2. 如 果 路 径 不 经 过 Root, 那 么 它 们 一 定 属 于 根 的 K 个 子 树 之 一 并 且 它 们 也 是 该 子 树 中 相 距 最 远 的 两 个 顶 点 如 图 3-14 中 的 节 点 A: 图 3-14 相 距 最 远 的 节 点 在 某 个 子 树 下 因 此, 问 题 就 可 以 转 化 为 在 子 树 上 的 解, 从 而 能 够 利 用 动 态 规 划 来 解 决 设 第 K 棵 子 树 中 相 距 最 远 的 两 个 节 点 :U k 和 V k, 其 距 离 定 义 为 d(u k, V k ), 那 么 节 点 U k 或 V k 即 为 子 树 K 到 根 节 点 R k 距 离 最 长 的 节 点 不 失 一 般 性, 我 们 设 U k 为 子 树 K 中 到 根 节 点 R k 距 离 最 长 的 节 点, 其 到 根 节 点 的 距 离 定 义 为 d(u k, R) 取 d(u i, R)(1 i k) 中 最 大 的 两 个 值 max1 和 max2, 那 么 经 过 根 节 点 R 的 最 长 路 径 为 max1+max2+2, 所 以 树 R 中 相 距 最 远 的 两 个 点 的 距 离 为 :maxd(u 1, V 1 ),, d(u k, V k ),max1+max2+2 采 用 深 度 优 先 搜 索 如 图 3-15, 只 需 要 遍 历 所 有 的 节 点 一 次, 时 间 复 杂 度 为 O( E )= O ( V -1), 其 中 V 为 点 的 集 合,E 为 边 的 集 合 图 3-15 深 度 遍 历 示 意 图 示 例 代 码 如 下, 我 们 使 用 二 叉 树 来 实 现 该 算 法 代 码 清 单 3-11 // 数 据 结 构 定 义

57 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 struct NODE NODE* pleft; NODE* pright; int nmaxleft; int nmaxright; char chvalue; ; // 左 孩 子 // 右 孩 子 // 左 子 树 中 的 最 长 距 离 // 右 子 树 中 的 最 长 距 离 // 该 节 点 的 值 int nmaxlen = 0; // 寻 找 树 中 最 长 的 两 段 距 离 void FindMaxLen(NODE* proot) // 遍 历 到 叶 子 节 点, 返 回 if(proot == NULL) return; // 如 果 左 子 树 为 空, 那 么 该 节 点 的 左 边 最 长 距 离 为 0 if(proot -> pleft == NULL) proot -> nmaxleft = 0; // 如 果 右 子 树 为 空, 那 么 该 节 点 的 右 边 最 长 距 离 为 0 if(proot -> pright == NULL) proot -> nmaxright = 0; // 如 果 左 子 树 不 为 空, 递 归 寻 找 左 子 树 最 长 距 离 if(proot -> pleft!= NULL) FindMaxLen(pRoot -> pleft); // 如 果 右 子 树 不 为 空, 递 归 寻 找 右 子 树 最 长 距 离 if(proot -> pright!= NULL) FindMaxLen(pRoot -> pright); // 计 算 左 子 树 最 长 节 点 距 离 if(proot -> pleft!= NULL) int ntempmax = 0; if(proot -> pleft -> nmaxleft > proot -> pleft -> nmaxright) ntempmax = proot -> pleft -> nmaxleft; else ntempmax = proot -> pleft -> nmaxright; proot -> nmaxleft = ntempmax + 1; // 计 算 右 子 树 最 长 节 点 距 离 if(proot -> pright!= NULL)

58 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 int ntempmax = 0; if(proot -> pright -> nmaxleft > proot -> pright -> nmaxright) ntempmax = proot -> pright -> nmaxleft; else ntempmax = proot -> pright -> nmaxright; proot -> nmaxright = ntempmax + 1; // 更 新 最 长 距 离 if(proot -> nmaxleft + proot -> nmaxright > nmaxlen) nmaxlen = proot -> nmaxleft + proot -> nmaxright; 扩 展 问 题 在 代 码 中, 我 们 使 用 了 递 归 的 办 法 来 完 成 问 题 的 求 解 那 么 是 否 有 非 递 归 的 算 法 来 解 决 这 个 问 题 呢? 总 结 对 于 递 归 问 题 的 分 析, 笔 者 有 一 些 小 小 的 体 会 : 1. 先 弄 清 楚 递 归 的 顺 序 在 递 归 的 实 现 中, 往 往 需 要 假 设 后 续 的 调 用 已 经 完 成, 在 此 基 础 之 上, 才 实 现 递 归 的 逻 辑 在 该 题 中, 我 们 就 是 假 设 已 经 把 后 面 的 长 度 计 算 出 来 了, 然 后 继 续 考 虑 后 面 的 逻 辑 ; 2. 分 析 清 楚 递 归 体 的 逻 辑, 然 后 写 出 来 比 如 在 上 面 的 问 题 中, 递 归 体 的 逻 辑 就 是 如 何 计 算 两 边 最 长 的 距 离 ; 3. 考 虑 清 楚 递 归 退 出 的 边 界 条 件 也 就 说, 哪 些 地 方 应 该 写 return 注 意 到 以 上 3 点, 在 面 对 递 归 问 题 的 时 候, 我 们 将 总 是 有 章 可 循

59 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 求 二 进 制 数 中 1 的 个 数 对 于 一 个 字 节 (8bit) 的 变 量, 求 其 二 进 制 表 示 中 1 的 个 数, 要 求 算 法 的 执 行 效 率 尽 可 能 地 高

60 写 书 评, 赢 取 编 程 之 美 微 软 技 术 面 试 心 得 分 析 与 解 法 大 多 数 的 读 者 都 会 有 这 样 的 反 应 : 这 个 题 目 也 太 简 单 了 吧, 解 法 似 乎 也 相 当 地 单 一, 不 会 有 太 多 的 曲 折 分 析 或 者 峰 回 路 转 之 处 那 么 面 试 者 到 底 能 用 这 个 题 目 考 察 我 们 什 么 呢? 事 实 上, 在 编 写 程 序 的 过 程 中, 根 据 实 际 应 用 的 不 同, 对 存 储 空 间 或 效 率 的 要 求 也 不 一 样 比 如 在 PC 上 的 程 序 编 写 与 在 嵌 入 式 设 备 上 的 程 序 编 写 就 有 很 大 的 差 别 我 们 可 以 仔 细 思 索 一 下 如 何 才 能 使 效 率 尽 可 能 地 高 解 法 一 可 以 举 一 个 八 位 的 二 进 制 例 子 来 进 行 分 析 对 于 二 进 制 操 作, 我 们 知 道, 除 以 一 个 2, 原 来 的 数 字 将 会 减 少 一 个 0 如 果 除 的 过 程 中 有 余, 那 么 就 表 示 当 前 位 置 有 一 个 1 以 为 例 ; 第 一 次 除 以 2 时, 商 为 , 余 为 0 第 二 次 除 以 2 时, 商 为 , 余 为 1 因 此, 可 以 考 虑 利 用 整 型 数 据 除 法 的 特 点, 通 过 相 除 和 判 断 余 数 的 值 来 进 行 分 析 于 是 有 了 如 下 的 代 码 代 码 清 单 2-1 int Count(int v) int num = 0; while(v) if(v % 2 == 1) num++; v = v/ 2; return num; 解 法 二 使 用 位 操 作 前 面 的 代 码 看 起 来 比 较 复 杂 我 们 知 道, 向 右 移 位 操 作 同 样 也 可 以 达 到 相 除 的 目 的 唯 一 不 同 之 处 在 于, 移 位 之 后 如 何 来 判 断 是 否 有 1 存 在 对 于 这 个 问 题, 再 来 看 看 一 个 八 位 的 数 字 : 在 向 右 移 位 的 过 程 中, 我 们 会 把 最 后 一 位 直 接 丢 弃 因 此, 需 要 判 断 最 后 一 位 是 否 为 1, 而 与 操 作 可 以 达 到 目 的 可 以 把 这 个 八 位 的 数 字 与 进 行 与 操 作 如 果 结 果 为 1, 则 表 示 当 前 八 位 数 的 最 后 一 位 为 1, 否 则 为 0 代 码 如 下 : 代 码 清 单 2-2