初始状态为 max[0] = min[0] = a[0]。代码如下：
/** * 最大连续子序列乘积 */ int maxMultipleOfContinuousSequence(int a[], int n) { int minSofar, maxSofar, max, i; int maxHere, minHere; max = minSofar = maxSofar = a[0]; <span>for</span>(i = 1; i < n; i++){ int maxHere = max3(maxSofar*a[i], minSofar*a[i], a[i]); int minHere = min3(maxSofar*a[i], minSofar*a[i], a[i]); maxSofar = maxHere, minSofar = minHere; <span>if</span>(max < maxSofar) max = maxSofar; } <span>return</span> max;}
复制代码
题： 给定一个正整数 n，判断该正整数是否是 2 的整数次幂。
解1： 一个基本的解法是设定 i=1 开始，循环乘以2直到 i>=n，然后判断 i 是否等于 n 即可。
解2： 还有一个更好的方法，那就是观察数字的二进制表示，如 n=101000，则我们可以发现n-1=100111。也就是说 n -> n-1 是将 n 最右边的 1 变成了 0，同时将 n 最右边的 1 右边的所有比特位由0变成了1。因此如果 n & (n-1) == 0 就可以判定正整数 n 为 2的整数次幂。
/** * 判断正整数是2的幂次 */ int powOf2(int n) { assert(n > 0); return !(n & (n-1)); } 复制代码2) 求一个整数二进制表示中1的个数题： 求整数二进制表示中1的个数，如给定 N=6，它的二进制表示为 0110，二进制表示中1的个数为2。
解1： 一个自然的方法是将N和1按位与，然后将N除以2，直到N为0为止。该算法代码如下：
int numOfBit1(int n) { int cnt = 0; while (n) { if (n & 1) ++cnt; n >>= 1; } return cnt; } 复制代码上面的代码存在一个问题，如果输入为负数的话，会导致死循环，为了解决负数的问题，如果使用的是JAVA，可以直接使用无符号右移操作符 >>> 来解决，如果是在C/C++里面，为了避免死循环，我们可以不右移输入的数字i。首先 i & 1，判断i的最低位是不是为1。接着把1左移一位得到2，再和i做与运算，就能判断i的次高位是不是1...，这样反复左移，每次都能判断i的其中一位是不是1。
/** * 二进制表示中1的个数-解法1 */ int numOfBit1(int n) { int cnt = 0; unsigned int flag = 1; while (flag) { if(n & flag) cnt++; flag = flag << 1; <span>if</span> (flag > n) <span>break</span>; } <span>return</span> cnt;}
复制代码
解2： 一个更好的解法是采用第一个题中类似的思路，每次 n&(n-1)就能把n中最右边的1变为0，所以很容易求的1的总数目。
/** * 二进制表示中1的个数-解法2 */ int numOfBit1WithCheck(int n) { int cnt = 0; while (n != 0) { n = (n & (n-1)); cnt++; } return cnt; } 复制代码3) 反转一个无符号整数的所有比特位题： 给定一个无符号整数N，反转该整数的所有比特位。例如有一个 8 位的数字 01101001，则反转后变成 10010110，32 位的无符号整数的反转与之类似。
解1： 自然的解法就是参照字符串反转的算法，假设无符号整数有n位，先将第0位和第n位交换，然后是第1位和第n-1位交换...注意一点就是交换两个位是可以通过异或操作 XOR 来实现的，因为 0 XOR 0 = 0, 1 XOR 1 = 0, 0 XOR 1 = 1, 1 XOR 0 = 1，使用 1 异或 0/1 会让其值反转。
/** * 反转比特位 */ uint swapBits(uint x, uint i, uint j) { uint lo = ((x >> i) & 1); // 取x的第i位的值 uint hi = ((x >> j) & 1); // 取x的第j位的值 if (lo ^ hi) { x ^= ((1U << i) | (1U << j)); // 如果第i位和第j位值不同，则交换i和j这两个位的值，使用异或操作实现 } return x; }/**
反转整数比特位-仿字符串反转
*/
uint reverseXOR(uint x)
{
uint n = sizeof(x) * 8;
uint i;
for (i = 0; i < n/2; i++) {
x = swapBits(x, i, n-i-1);
}
return x;
}
复制代码
解2： 采用分治策略，首先交换数字x的相邻位，然后再是 2 个位交换，然后是 4 个位交换...比如给定一个 8 位数 01101010，则首先交换相邻位，变成 10 01 01 01，然后交换相邻的 2 个位，得到 01 10 01 01，然后再是 4 个位交换，得到 0101 0110。总的时间复杂度为 O(lgN)，其中 N 为整数的位数。下面给出一个反转32位整数的代码，如果整数是64位的可以以此类推。
/** * 反转整数比特位-分治法 */ uint reverseMask(uint x) { assert(sizeof(x) == 4); // special case: only works for 4 bytes (32 bits). x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1); x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2); x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4); x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8); x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16); return x; } 复制代码系列文章目录0. 数据结构和算法面试题系列—C指针、数组和结构体
1. 数据结构和算法面试题系列—字符串
2. 数据结构和算法面试题系列—链表
3. 数据结构和算法面试题系列—栈
4. 数据结构和算法面试题系列—二叉堆
5. 数据结构和算法面试题系列—二叉树基础
6. 数据结构和算法面试题系列—二叉树面试题汇总
7. 数据结构和算法面试题系列—二分查找算法详解
8. 数据结构和算法面试题系列—排序算法之基础排序
9. 数据结构和算法面试题系列—排序算法之快速排序
10. 数据结构和算法面试题系列—随机算法总结
11. 数据结构和算法面试题系列—递归算法总结
12. 数据结构和算法面试题系列—背包问题总结
13. 数据结构和算法面试题系列—数字题总结
其他