更新：此题解 markdown 源文件已放到 Github https://github.com/bytetopia/offer-coding-interviews-python (opens new window)，欢迎前去给个小星星鸭！

---

二进制中1的个数

问题

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路

一个技巧。转换为二进制以后， n 和 n-1 做按位与的话，总是相当于抹掉了n转换成二进制后最右边的一个1.

比如二进制1101最右边是1，1101 & 1100 得到 1100 ，把最右边的1抹掉了；如果是二进制1100这种最右边不是1的情况，将其减1的话必然要从最靠右的1那里去借位，所以 1100 & 1001 得到 1000页成功抹掉了。

按照这种思路，只要一直减去1，就逐个从右边抹掉了1， 当整个数 = 0 时说明抹完了，循环次数就是1的个数。

代码

class Solution:
    def NumberOf1(self, n):
        count = 0
        # python特别注意
        if n < 0:
            n = n & 0xffffffff
        while n:
            n = (n-1) & n
            count += 1
        return count

对于使用python编程的同学，要特别注意一个特殊的处理。具体原因可参考 https://www.zhihu.com/question/314455297 (opens new window)。简言之，由于python无限扩容不管溢出，所以对于负数来说需要进行一步手动转换才可以。

扩展回顾 关于原码、反码和补码：https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/computercode.html (opens new window)

正数的原、反、补码都是本身。对负数来说，例如8bit二进制数，原码是第一位0表示正数，1表示负数，后面7bit表示数值。反码则是第一位不变，后面各位取反。补码则在原码的基础上加1。简言之存储补码是为了便于做加减计算。

数值的整数次方

问题

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

解决

1）愚蠢方法

# 一行代码……
class Solution:
    def Power(self, base, exponent):
        return base ** exponent

当然本题原意是不要调用库，自己来实现。可以参考https://blog.nowcoder.net/n/65b43f8b94dc4a30a9750491b5bd51fa?f=comment (opens new window)

2）暴力方法 循环n次将base跟自己相乘，需要注意特殊处理一下 exponent是负数的情况，可将base变为 1/base，exp变为正数

3. 递归方法 如果exp是偶数的话，x^8 = (x^4)^2，所以不需要循环n次，只要logn次就可以啦；如果是奇数的话，特殊处理成 1 + (n-1), n-1就是偶数次了。

代码

搬运题解写法，递归：

class Solution {
public:
    double q_power(double b, int n) {
        if (n == 0) return 1.0;
        double ret = q_power(b, n/2);
        if (n&1) { // 奇数
            return ret * ret * b;
        }
        else {
            return ret * ret;
        }
    }
    double Power(double b, int n) {
        if (n < 0) {
            b = 1 / b;
            n = -n;
        }
        return q_power(b, n);
    }
};

自己写一个python非递归：

class Solution:
    def Power(self, base, exponent):
        # write code here
        if base == 0:
            return 0
        if exponent == 0:
            return 1
        # 处理exp是负数的情况,转换为正数
        if exponent < 0:
            base = 1/base
            exponent *= -1
        # 处理exp是奇数的情况
        loo = 1
        if exponent % 2 != 0:
            loo = base
            exponent -= 1
        # 现在exp是偶数正数了，进行计算
        ret = base
        while exponent != 1:
            ret = ret * ret 
            exponent /= 2
        ret = ret * loo 
        return ret

4. 快速幂 不多赘述，参考牛客题解吧。

打印1到最大的n位数

问题

给定n，要按顺序打印从1到最大的n位数，例如，n=3，则打印1,2,3.....999.

思路

（1）先求出最大的n位数，例如n=3，最大的是 10^3 - 1 = 999，然后循环从1开始打印 问题：如果n稍微大一点点，例如20，一般的整数类型就溢出了!

(2) 用字符串的形式，模拟手工加法进位的操作

（3）转换思路，其实就是输出n个0-9的全排列，按递归的方法，从高位逐个递归深入下去，就能实现按照从小到大的顺序逐个输出了！

好吧，这个题主要就是要提醒注意n的范围，也就是说，要仔细思考给定的输入值是不是0？正数？负数？会不会过大？采取的数据类型有没有问题？

O(1)的时间删除链表某节点

问题

单向链表，给定头指针和指向某个节点的指针，要求O(1)时间删除该节点

思路

常规的做法是，从头开始沿着链表向后遍历，直到找到目标节点，然后修改目标的前一个节点的指针，让next指向目标的后一个节点，释放空间，完成删除。

这种复杂度是O(n)，主要就是因为必须遍历才能找到目标节点的前一个节点！

另辟蹊径，可以O(1)找到目标的后一个节点，将后一个节点的内容复制到目标上，这样问题就转换成删除目标的后一个节点了！无需从头遍历!

需要特别注意！处理一些特殊情况，例如单节点链表、目标是尾节点等。

代码

简述一下结构吧

• 判断链表头和目标是否指针为空，不空才能继续
• 目标不是尾节点，可以操作，将目标的下一节点的内容和next指针复制过来，删掉下一节点
• 如果链表只有一个节点，则直接将头指针next置空，释放目标节点
• 如果链表不是只有一个节点，而且目标是尾节点，则必须从头遍历找到目标的上一节点，然后按正常方式释放。

补充：（想这么多还能不能愉快的编程了！简直有点神经质啊！！）以上基于假设是目标一定在链表中，如果目标节点不在链表中，就gg了……

调整数组顺序，使奇数位于偶数前面

问题

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路

需要注意到保证奇数和奇数、偶数和偶数的相对位置不变。

如果是允许做数组的delete和append操作，或者说允许建新数组的话： 1）另开两个数组，扫一遍分别存偶数和奇数，然后将偶数连接到奇数后面 2）扫一遍统计奇数的个数，新建一个等长的数组，奇数从头往后加，偶数从奇数长度下标处往后加（当允许另开空间时，此方法较好） 3）扫一遍，遇到偶数就从列表中删除，然后追加到列表末端。需注意结束扫描的条件

如果只允许在原数组上做交换操作： 4）利用冒泡排序的思想，从前往后扫，遇到奇数就往前冒泡（或者从后往前扫，遇到偶数往后冒泡），不开辟额外空间

代码

上面（1）用python的简洁写法：

def reOrderArray(self, array):
        # write code here
        odd,even=[],[]
        for i in array:
            odd.append(i) if i%2==1 else even.append(i)
        return odd+even

再写一下上面（4）的代码：

class Solution:
    def reOrderArray(self, array):
        # 冒泡思想。从前往后扫，遇到奇数就往前冒泡。
        last_odd = -1
        for i in range(0, len(array)):
            if array[i] % 2 == 1:
                for j in range(i, last_odd+1, -1):
                    array[j], array[j-1] = array[j-1], array[j]
                    print(array)
                last_odd += 1
        return array     

扩展

如果不要求奇数和偶数的相对位置不变，只要能奇数在前，偶数在后。

1）从前往后扫，遇到偶数，就记下，把它之后的内容往前挪一位，把偶数放在最后的空位（需要留意何时停止）

2）维护两个指针，一个从头部往后，一个从尾部往前，如果第一个指向偶数，第二个指向奇数，就交换，当第二个位于第一个前面时说明交换完成。