LintCode题解|Hulu 面试题:Weighing Problem

1,083 阅读1分钟

九章算法 | Hulu 面试题:Weighing Problem


题目描述

给出 n 个金币,每个金币重 10g,但是有一个金币的重量是 11g。现在有一个能够精确称重的天平,问最少称几次,能够确保找出那一个重量 11g 的金币?


思路点拨

根据贪心的思想,每次尽可能大地缩小下次称量金币的个数。故每次可以将金币尽可能均匀地分成三份:若 n % 3 = 0,则分成 n/3、n/3、n/3,任意取两份进行比较。若 n % 3 = 1,则分成 n/3、n/3、 n/3 + 1,取个数为 n/3 的两份进行比较。若 n % 3 = 2,则分成 n/3 + 1、n/3。


考点分析

本题为简单的热身题,主要考察贪心的思想,做到 bug free 即可。


九章参考程序

www.jiuzhang.com/solution/we…


/**
* 本参考程序来自九章算法,由 @华助教 提供。版权所有,转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作,教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括:九章算法班,系统设计班,算法强化班,Java入门与基础算法班,Android 项目实战班,
* - Big Data 项目实战班,算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站:http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    /**
     * @param n: The number of coins
     * @return: The Minimum weighing times int worst case
     */
    public int minimumtimes(int n) {
        // Write your code here
        int ans;
        ans = 0;
    	if (n % 3 == 0 ) {
            n = n - 1;
        }
        while (n > 0) {
            n = n / 3;
            ans++;
        }
   		return ans;
    }
}