[ 剑 指 offer] 面 试 题 43:n 个 骰 子 的 点 数 (Java) 题 目 : 把 n 个 骰 子 扔 在 地 上, 所 有 骰 子 朝 上 一 面 的 点 数 之 和 为 S 输 入 n, 打 印 出 S 的 所 有 可 能 的 值 出 现 的 概 率 分 析 : 一 般 来 说 骰 子 只 有 6 面, 点 数 为 1~6, n 个 骰 故 子 的 最 小 和 为 n, 最 大 和 为 6*n, 则 n 个 骰 子 的 点 数 之 和 出 现 的 频 数 可 以 用 一 个 数 组 来 保 存, 大 小 为 6*n-n 思 路 1: 最 直 接 的 方 法 是 求 出 n 个 骰 子 点 数 的 全 排 列, 然 后 一 一 计 算 其 和 值, 统 计, 最 后 算 出 每 个 和 值 的 概 率, 这 里 使 用 基 于 递 归 的 方 法 来 求 各 和 值 的 频 数. 先 把 n 个 骰 子 分 为 两 堆 : 第 一 堆 只 有 一 个, 另 一 个 有 n-1 个 单 独 的 那 一 个 有 可 能 出 现 从 1 到 6 的 点 数 我 们 需 要 计 算 从 1 到 6 的 每 一 种 点 数 和 剩 下 的 n-1 个 骰 子 来 计 算 点 数 和 接 下 来 把 剩 下 的 n-1 个 骰 子 还 是 分 成 两 堆, 第 一 堆 只 有 一 个, 第 二 堆 有 n-2 个 我 们 把 上 一 轮 那 个 单 独 骰 子 的 点 数 和 这 一 轮 单 独 骰 子 的 点 数 相 加, 再 和 剩 下 的 n-2 个 骰 子 来 计 算 点 数 和 Java 实 现 代 码 : public class PrintSumProbabilityOfDices { private int gmaxvalue = 6; public void probility(int orignal, int current, int sum, int[] probilities){ if(current == 1){
probilities[sum - orignal]++; else{ for(int i=1; i<= gmaxvalue; i++){ probility(orignal, current - 1, sum + i, probilities); public void probility(int number, int[] probilities){ for(int i=1; i<= gmaxvalue; i++){ probility(number,number, i,probilities); public void printprobability(int number){ if(number < 1) return; int maxsum = number * gmaxvalue; int[] probilities = new int[maxsum - number + 1]; probility(number, probilities); double total = Math.pow(gMaxValue, number); for(int i=number; i<= maxsum; i++){ double ratio = probilities[i - number] / total; System.out.println(i + ": " + ratio); public static void main(string[] args){ int number = 5; new PrintSumProbabilityOfDices().printProbability(number); 思 路 2: 基 于 循 环 求 骰 子 的 点 数, 这 样 避 免 了 很 多 重 复 的 计 算, 时 间 性 能 要 好 我 们 可 以 考 虑 用 两 个 数 组 来 存 储 骰 子 点 数 每 一 总 数 出 现 的 次 数 在 一 次 循 环 中, 第 一 个 数 组 中 的 第 n 个 数 字 表 示 骰 子 和 为 n 出 现 的 次 数 那 么 在 下 一 循 环 中, 我 们 加 上 一 个 新 的 骰 子 那 么 此 时 和 为 n 的 骰 子 出 现 的 次 数, 应 该 等 于 上 一 次 循 环 中 骰 子 点 数 和 为 n-1 n-2 n-3 n-4 n-5 与 n-6 的 总 和
Java 实 现 代 码 : public void printprobability_2(int number){ if(number < 1) return; int maxsum = gmaxvalue * number + 1; int[][] probilities = new int[2][maxsum]; int flag = 0; for(int i=1; i<=gmaxvalue; i++) probilities[flag][i] = 1; for(int i=2; i<= number; i++){ for(int j = 0; j<i; j++) probilities[1-flag][j] = 0; for(int j = i; j<=gmaxvalue * i; j++){ probilities[1-flag][j] = 0; for(int k=1; k<=j && k<=gmaxvalue; k++) probilities[1-flag][j] += probilities[flag][j-k]; flag = 1 - flag; double total = Math.pow(gMaxValue, number); for(int i=number; i< maxsum; i++){ double ratio = probilities[flag][i] / total; System.out.println(i + ": " + ratio); 考 点 总 结 :1. 考 察 数 学 建 模 能 力 能 否 想 到 用 数 组 建 立 一 个 简 单 的 哈 希 表 来 存 储 骰 子 点 数 和 值 的 频 数 2. 考 察 对 递 归 和 循 环 程 序 性 能 的 理 解 参 考 资 料 : 1. Offer 剑 指 名 企 面 试 官 精 讲 典 型 编 程 题 P223~226
[ 剑 指 offer] 面 试 题 42: 翻 转 单 词 顺 序 VS 左 旋 转 字 符 串 (Java) 题 目 : 输 入 一 个 英 文 句 子, 翻 转 句 子 中 单 词 的 顺 序, 但 单 词 内 字 符 的 顺 序 不 变 为 简 单 起 见, 标 点 符 号 和 普 通 字 母 一 样 处 理 例 如 输 入 字 符 串 I am a student., 则 输 出 "student. a am I". 实 现 代 码 public void reverse(char[] str, int start, int end){ System.out.println("tag XX"); if(str == null str.length < 2) return; int left = start; int right = end; while(left < right){ char tmp = str[right]; str[right--] = str[left]; str[left++] = tmp; public void reversesentence(char[] str){ if(str == null str.length < 2) return; reverse(str, 0, str.length - 1); int left = 0; int right = 0;
[ 剑 指 offer] 面 试 题 41: 和 while(left < str.length){ if(str[left] == ' '){ left++; right++; else if(str[right] == ' ' right == str.length - 1){ System.out.println("left:" + left + ",right:" + right); reverse(str, left, (right == str.length -1)?right:(right-1)); left = right + 1; right++; else{ right++; 其 实 这 道 题 如 果 只 是 打 印 出 翻 转 后 的 句 子, 或 者 允 许 使 用 O(n) 的 空 间, 那 么 可 以 使 用 递 归 或 者 分 配 栈 来 完 成 会 更 加 简 便 至 于 左 旋 转 字 符 串, 其 实 有 了 反 转 句 子 的 基 础, 解 答 起 来 就 十 分 简 单 了 为 s 的 两 个 数 字 VS 和 为 s
的 连 续 序 列 题 目 一 : 输 入 一 个 递 增 排 序 的 数 组 和 一 个 数 s, 字 在 数 组 中 查 找 两 个 数, 使 得 他 们 的 和 正 好 是 s, 如 果 有 多 对 数 字 的 和 等 于 s, 输 出 任 意 一 对 即 可 但 凡 搜 索 题, 一 般 都 可 以 通 过 暴 力 找 出 答 案, 但 那 样 的 解 往 往 会 令 不 会 帮 助 你 拿 到 心 仪 的 offer, 但 从 另 一 个 层 面 上 反 应 了 一 个 人 思 维 的 反 应 能 力, 在 输 入 规 模 较 少 的 情 况 下, 暴 力 也 不 是 不 能 解 决 问 题 这 道 题 的 暴 力 解 法 就 是 直 接 两 重 循 环, 遍 历 所 有 的 解, 时 间 复 杂 度 O(n^2) 能 O(n) 解 的 问 题,O(n^2) 的 解 法 显 然 无 法 得 到 面 试 官 的 青 睐 要 学 会 善 于 挖 掘 题 中 给 出 的 信 息, 递 增 排 序 的 数 组, 这 就 是 一 个 及 其 有 价 值 的 信 息 在 排 序 的 数 组 中, 一 般 会 想 到 二 分 来 搜 索 解, 因 为 二 分 的 解 法 可 能 只 会 需 要 O(logN) 的 时 间 的 复 杂 度 但 是 本 题 求 解 的 问 题 是 两 个 数 的 求 和, 也 可 能 不 会 只 有 一 个 解, 所 有 只 要 求 第 一 个 解, 这 样 不 宜 使 用 二 分, 而 是 使 用 双 指 针 来 解 答 这 道 题 思 路 是 定 义 两 个 指 针 ( 其 实 就 是 数 组 的 下 标 )left,right,left 指 向 开 始,right 指 向 数 组 最 后 一 个 元 素, 向 着 靠 拢 的 方 向 搜 索 第 一 个 可 能 的 解, 这 种 解 法 的 时 间 复 杂 度 是 O(n) 具 体 的 实 现 代 码 如 下 : index){ public boolean findnumberwithsum(int[] nums, int sum, int[] if(nums == null nums.length <2 index.length <2) return false; boolean tag = false; int left = 0; int right = nums.length - 1; while(left < right){ int s = nums[left] + nums[right]; if(s == sum){
index[0] = nums[left]; index[1] = nums[right]; tag = true; break; else if(s > sum){ right --; else{ left++; return tag; 题 二 : 输 入 一 个 正 数 s, 打 印 出 所 有 和 为 s 的 连 续 正 整 数 序 列 ( 至 少 含 有 两 个 数 字 ), 例 如 15, 由 于 1+2+3+4+5 = 4+5+6 = 7+8 = 连 续 序 列 1~5,4~6,7~8 作 为 题 一 的 变 型 题, 难 度 有 所 提 高, 但 是 在 题 一 的 启 发 下, 也 不 难 想 出 解 法, 题 目 的 求 解 可 以 转 化 为 在 含 有 n 个 无 重 复 元 素 的 有 序 数 组 里 求 解 问 题, 那 么 同 样 可 以 使 用 双 指 针 来 求 解 注 意 本 题 的 关 键 在 于 解 是 连 续 的 整 数 序 列, 所 有 我 们 从 数 组 ( 假 设 出 来 的, 其 实 不 存 在 ) 的 一 端 移 动 两 个 指 针 (left,right, left<=right), 相 当 于 在 两 个 指 针 之 间 维 护 了 一 个 长 度 可 变 的 窗 口, 然 后 根 据 窗 口 内 各 元 素 的 和 值 去 移 动 两 个 指 针, 显 然 left 指 针 不 能 大 于 (n+1)/2 实 现 代 码 如 下 : public List<List<Integer>> findcontinuoussequence(int sum){ List<List<Integer>> res = new ArrayList<List<Integer>>(); if(sum < 3) return res;
int rear = 1; int front = 2; int tsum = rear + front; int mid = (sum + 1) / 2; while(rear < mid){ if(tsum == sum){ List<Integer> tmp = new ArrayList<Integer>(); for(int i = rear; i<= front; i++){ tmp.add(i); res.add(tmp); front++; rear++; tsum += (front - rear + 1); else if(tsum > sum){ tsum -= rear; rear++; else{ front ++; tsum += front; return res;