C编程练习题: 翻转整数位
题意: 给定两个整数, 计算从一个整数需要翻转几个位才能到另一个整数. 比如: 给定29 二进制为11101 和 15, 二进制是01111, 则答案是2次. 这题的关键就是用 XOR 异或来获得两个整数不同位. 因为只有当两个位不一样的时候 异或的结果才是1. 所以我们可以写成以下循环, 每次向右移1位, 累计 c & 1 int bitSwapRequired(int a, int b) { int count …
Tag: 程序设计
C++编程练习题: 对两单向链表求和
这题难度中等, 原因就是在实现的时候细节很多, 不容易一次性搞对. 还好这两个列表表示的整数是反过来的, 所以实现上可以边遍历边相加, 只需要在累加每一位的时候记得记住进位即可. C++单向列表定义如下: struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; 当然, 还有更笨的方法, 就是先把每个列表转换成数字, 然后想加再把结果换成列表. 我们需要创建一个dummy结点, 记住, 在函数返回的时候返回 dummy.next …
C编程练习题: 判断整数是否有连续两个1
题意就是判断一个整数的二进制表达式里是否有连续两个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 …
PHP 是最好的语言, 但是……
很久之前, 我就说了, PHP是最好的语言, 是宇宙中最好的语言, 因为方便啊, PHP有几千个估计得上万个函数了: http://php.net/manual/en/indexes.functions.php 所以, 生活工作上, 我也会拿PHP来写些命令行的脚本, 比如这个 <?php if ($argc < 2) { die(); } if (!is_file($argv)) { die(); } $offset = $argv ?? 0; …
想知道CHROME到底有多占内存么? WINDOWS下批处理查看程序内存用量
我家里用的是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 == …
C++ 刷题坑: 二分查找也没有那么容易写出来
最近在刷题, 刷了一道比较简单的二分搜索, 但是却让我刷了好几次才过(果真是很久没刷 能力立马下降许多) 题意就是 不允许使用 sqrt 或者 pow 之类的函数来判断一个整数是否是平方数. 比如 4, 16, 64, 25 就是平方数而 3, 7, 11 不是. 很容易想到可以用二分搜索来解决, 算法复杂度是 O(log n), 答案如下: typedef unsigned long long …
ACM题解 – 经典0/1背包问题
0/1背包问题是非常经典的算法问题. 要求是: 给定 n 个物件, 每个物件的重量(或体积)是 A 那么请问一个最多装重(或体积) m 的背包最多可以装下多少这些物件. 如果用数学表示这个问题: max(sum(j * A)) subject to: j = {0, 1} and sum(j * A) <= m where 0 =< …