谷歌的扔鸡蛋问题

谷歌的扔鸡蛋问题本文链接: (AMP 移动加速版本) 这题据说是 GOOGLE的面试题,但是却真实的被一些软件公司拿来考应聘者。 题意是:给你两个鸡蛋,有个100层楼,你可以把鸡蛋从任意一层楼扔下,鸡蛋可能破,也可能不破,如果不破的话,你可以继续用这个鸡蛋扔。你需要用这两个鸡蛋来试出鸡蛋会破的最小楼层高度。这两个鸡蛋一模一样。问你采用什么策略可以使最坏情况下的尝试次数最少? 什么是最差情况?如果你只有一个鸡蛋,那么你最坏需要100次(需要从1层楼开始测试)才可以得到结论。 最直接的做法就是从第一层开始试,然后第二层以此类推,但是这种方法只需要用到1个鸡蛋即可。如果第N层鸡蛋没碎但是第N+1层碎了,答案就是N。这种情况下最坏需要尝试100次。 如果我们在第50层扔呢?如果鸡蛋碎了,那么答案就在第1到第49层,反之答案就在第51到第100。鸡蛋碎了,我们只有一个鸡蛋,就只能从1试到49,最坏情况下是 1 + 49次,这种情况比上面最直接的做法(49)还差。如果鸡蛋没碎,那么我们还有两个鸡蛋,但是层数只有50层了,这时候就是一个子问题了。 同样,再举个例子,如果我们第一次在第33层,鸡蛋碎了,我们需要最坏情况下再试32次,答案是32+1次。如果鸡蛋不碎,我们需要用两个鸡蛋试一下剩下的67层。 也就是说,如果我们用 f(n) 来表示在第 n 层扔鸡蛋最差情况下的次数,我们有两种可能,再试 n – 1 次或者在剩下 n – i 层里用两个鸡蛋(子问题)的次数的最大值。 所以,问题也就是找出所有情况下使 1 + …

编程练习题 – 如何合并两个有序的数组?

编程练习题 – 如何合并两个有序的数组?本文链接: (AMP 移动加速版本) 题意:合并两个已经排序好的数组。这也是合并排序的最后一步操作。还算比较简单的,你可以从数组的两端开始。一般来说从小到大合并会比较直观。 我们需要定义指向两个数组的下标,每次循环就把比较小的那个数字添加到结果中即可。当其中一个数组已经全部添加完后只需要把另一个数组剩下的元素依次添加到结果中即可。 复杂度是 O(A+B) ,其中A、B分别是两个数组的长度。 class Solution { public: /** * @param A: sorted integer array A * @param B: sorted integer array B …

PHP 是最好的语言,但是……

PHP 是最好的语言,但是……本文链接: (AMP 移动加速版本) 很久之前,我就说了,PHP是最好的语言,是宇宙中最好的语言,因为方便啊,PHP有几千个估计得上万个函数了: http://php.net/manual/en/indexes.functions.php 所以,生活工作上,我也会拿PHP来写些命令行的脚本,比如这个 <?php if ($argc < 2) { die(); } if (!is_file($argv)) { die(); } $offset = $argv ?? 0; // Search and Replace …

想知道CHROME到底有多占内存么?WINDOWS下批处理查看程序内存用量

想知道CHROME到底有多占内存么?WINDOWS下批处理查看程序内存用量本文链接: (AMP 移动加速版本) 我家里用的是HPZ800的服务器,所以长年不关机不重启,今天我看了CHROME好吃内存: 在 Processes 页,操作系统列出了每个程序的吃内存情况,我们可以看到CHROME很吃内存。 然而,我想着写一个小命令行工具,练练手。 Github: https://github.com/DoctorLai/BatchUtils/blob/master/mem.cmd @echo off REM Calculate Total Memory Consumption for a Process setlocal enabledelayedexpansion set prog=%1 if == ( echo Usage: …

围棋的走法和宇宙原子总量谁更多?

围棋的走法和宇宙原子总量谁更多?本文链接: (AMP 移动加速版本) 围棋的棋盘是19乘于19条线, 棋手在线交叉的位置上放棋子. 每个地方可以有三种状态: 白的, 红的, 或者为空. 所以不考虑棋子有效性, 围棋所有棋盘的数目是 3的361次方. 科学家们估计了宇宙中原子的数目大约在 10的78次方到10的82次方间 我们就姑且认为是 10的80次方吧. 问题来, 哪一个更多呢? 当然, 计算机可以先分别算出两个值的大小直接粗暴的比大小. 不过, 我们却不能. 相反, 我们可以简单的推算一下. 假定围棋状态数为M, 宇宙原子 数为N, 那么我们只需要比较M/N和1的大小即可. 取LOG …

给英国人办中华人民共和国旅行证

给英国人办中华人民共和国旅行证本文链接: (AMP 移动加速版本) 当初给两个孩子办英国护照也是无奈之策, 因为孩子在英国出生本身不需要签证, 但是要是回趟国再回英国就必须办签证. 如果给孩子办中国护照+英国签证, 那么等孩子拿永居就还要5年, 并且费用不菲(续签三次+NHS费用, 大概1万多英镑). 所以当初想着等孩子长大有本事了自己去拿中国护照, 换英国护照这件事作为父母的我们就替他们先做主了. 加入英国国籍+拿英国护照挺顺利, 不到三个月, 交了2000英镑, 两孩子的英国护照和英国国籍纸就寄到了. 虽然孩子的中国护照还未到期并没有注销(英国政府无权注销中国护照), 但是中国政府并不承认双重国籍, 所以拿中国护照回国然后拿英国护照再回英国的方案是行不通的. 给孩子办中国签证费用很贵, 两年有效期费用就得180英镑左右, 并且回国还得到当地公安局报备, 毕竟是以外国公民的身份回去的. 签证可能还会有其它限制, 比如每次入境不能超过6个月之类的, 对于想经常回国的海外华侨并不是很友好. 听朋友说, 可以尝试给孩子申请旅行证, 也就是 …