11. 二进制中1的个数

位与

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路很巧妙，可参考牛客二进制中1的个数讨论

class Solution:
    def NumberOf1(self, n):
        # write code here
        count=0
        if n < 0:
            n = n & 0xffffffff
        while n!=0:
            n=n&(n-1)
            count+=1
        return count

注意，使用java或者c++写时不需if判断，因为他两默认转的就是补码形式

而python不是，需要与0xffffffff位与才能变成补码形式

二进制计算

显然，一个很简单的思路是一个一个数

class Solution:
    def NumberOf1(self, n):
        # write code here
        if n<0:
            n=n&0xffffffff
        return bin(n).count("1")

12.数值的整数次方

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

调参划水

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        return pow(base,exponent)

累积相乘

显然，我们可以一个一个相乘，但是这个题的关键在于，每个数都是一样的，也就是说，1号和2号的乘积等于3号和4号的乘积
换言之，乘积可以复用，大大减少计算量

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        res=base
        flag=1
        if exponent<0:
            exponent*=-1
            flag=-1
        elif exponent==0:
            return 1
        while True:
            if exponent==1:
                res*=base
                break
            res*=res
            exponent=exponent//2
        return res if flag==1 else 1/res

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

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
一种简单的方法是两个for循环，再来一个list保存，或者碰到前后奇偶数就交换，就不写了

分别取出再拼接

注意.python中append(n)是添加n进入list，而extend(n)是添加n内部的对象进入list

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        ji,ou=[],[]
        for i in range(len(array)):
            if array[i]%2==1:
                ji.append(array[i])
            else:
                ou.append(array[i])
        ji.extend(ou)
        return ji

14.链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个结点。

快慢指针

快指针先往前走k步，注意判断边界，然后快慢一起走，当快指针为none的时候，慢指针走到了倒数第k个节点

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        slow,fast=head,head
        for i in range(k):
            if not fast:
                return None
            fast=fast.next
        while fast:
            slow=slow.next
            fast=fast.next
        return slow

15.反转链表

输入一个链表，反转链表后，输出新链表的表头。

直接反转

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        pre=None # 代表刚刚走过的节点
        while pHead: #为空跳出，刚刚走过的节点pre就是末节点
            next=pHead.next  #取出next
            pHead.next=pre   #将当前节点的next换为上个节点pre
            pre=pHead        #换完之后当前节点走过，pre更新
            pHead=next		 #当前节点更新
        return pre