题意就是判断一个整数的二进制表达式里是否有连续两个1. 比如13的二进制是1101那么有两个连续的1而9的二进制是1001, 则没有两个连续的1. 我们知道 我们可以用 x & (-x) 来获取一个整数二进制表示里最右边的那个1. 那么我们就可以写一个循环不停的返回最右边的那个1的值, 并且我们记录了上一个1的值, 这样只要有连续两个1, 那么这两个1的值的关系就是两倍. C代码看下面, 复杂度是 O(log N) 因为最多需要 log N 次就可以把一个整数的二进制位过一遍. int inspect_bits(unsigned int number) { int cur, prev …
2018年7月19日
ACM题解, 学习笔记, 数学, 数据结构与算法, 有意思的, 程序员, 程序设计, 算法, 编程, 计算机, 软件工程, 面试
这题据说是 GOOGLE的面试题, 但是却真实的被一些软件公司拿来考应聘者. 比如我在前几年面试剑桥的博通公司/Broadcom, 在第二轮也被问到了这个问题. 题意是: 给你两个鸡蛋, 有个100层楼, 你可以把鸡蛋从任意一层楼扔下, 鸡蛋可能破, 也可能不破, 如果不破的话, 你可以继续用这个鸡蛋扔. 你需要用这两个鸡蛋来试出鸡蛋会破的最小楼层高度. 这两个鸡蛋一模一样. 问你采用什么策略可以使最坏情况下的尝试次数最少? 什么是最差情况? 如果你只有一个鸡蛋, 那么你最坏需要100次(需要从1层楼开始测试)才可以得到结论. 最直接的做法就是从第一层开始试, 然后第二层以此类推, 但是这种方法只需要用到1个鸡蛋即可. 如果第N层鸡蛋没碎但是第N+1层碎了, 答案就是N. 这种情况下最坏需要尝试100次. 如果我们在第50层扔呢? 如果鸡蛋碎了, 那么答案就在第1到第49层, 反之答案就在第51到第100. …
题意: 合并两个已经排序好的数组. 这也是合并排序的最后一步操作. 还算比较简单的, 你可以从数组的两端开始. 一般来说从小到大合并会比较直观. 我们需要定义指向两个数组的下标, 每次循环就把比较小的那个数字添加到结果中即可. 当其中一个数组已经全部添加完后只需要把另一个数组剩下的元素依次添加到结果中即可. 复杂度是 O(A+B) , 其中A, B分别是两个数组的长度. class Solution { public: /** * @param A: sorted integer array A * @param B: …
很久之前, 我就说了, PHP是最好的语言, 是宇宙中最好的语言, 因为方便啊, PHP有几千个估计得上万个函数了: http://php.net/manual/en/indexes.functions.php 所以, 生活工作上, 我也会拿PHP来写些命令行的脚本, 比如这个 <?php if ($argc < 2) { die(); } if (!is_file($argv)) { die(); } $offset = $argv ?? 0; …
我家里用的是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 == …
围棋的棋盘是19乘于19条线, 棋手在线交叉的位置上放棋子. 每个地方可以有三种状态: 白的, 红的, 或者为空. 所以不考虑棋子有效性, 围棋所有棋盘的数目是 3的361次方. 科学家们估计了宇宙中原子的数目大约在 10的78次方到10的82次方间 我们就姑且认为是 10的80次方吧. 问题来, 哪一个更多呢? 当然, 计算机可以先分别算出两个值的大小直接粗暴的比大小. 不过, 我们却不能. 相反, 我们可以简单的推算一下. 假定围棋状态数为M, 宇宙原子 数为N, 那么我们只需要比较M/N和1的大小即可. 取LOG 10为底 lg(M/N), 转换一下变成 …
