剑指offer（三）

剑指offer（11-15）。

二进制中1的个数

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

思路
如果是负数，先获取它的补码形式，然后统一为正数处理。发现，当一个数大于0时，不停让它与它的前一位进行按位与操作，即可获得其二进制表示中1的个数。

代码实现

class Solution:
    def NumberOf1(self, n):
        # write code here
        count = 0
        if n < 0:
            n = n & 0xffffffff      #负数的补码表示
        while n:
            count += 1
            n = (n - 1) & n         #按位与操作，都为1则为1，否则为0
        return count

''' 输入一个整数，输出该数二进制表示中0的个数。 其中负数用补码表示。 '''
#将上述代码中的n = (n - 1) & n 改为 n = n|(n+1) 

数值的整数次方

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

思路

1. 直接调用函数pow，但非常不推荐这种方法。
2. 累乘，考虑指数的3种情况（小于0，大于0和等于0）
3. 位运算代替递归，同样减少乘法运算，但效率更高（python未实现）

代码实现

#方法一，直接调用库函数，在线刷题可以这样，但是如果是面试编程，千万不要这样
class Solution:
    def Power(self, base, exponent):
        return (pow(base, exponent))

#方法二，累乘，考虑指数的3种情况，26ms，5836k
class Solution2:
    def Power(self, base, exponent):
        # write code here
        if exponent < 0:
            return 1 / self.Power(base, -exponent)
        elif exponent == 0:
            return 1
        else:
            res = [base]
            for i in range(1, exponent):
                res.append(res[i - 1] * base)
            return res[-1]

#方法三，位运算代替递归，同样减少乘法运算，但效率更高，才3ms，内存也少，536k
# class Solution {
# public:
# double Power(double base, int exponent) {
# long long p = abs((long long)exponent);
# double r = 1.0;
# while(p){
# if(p & 1) r *= base;
# base *= base;
# p >>= 1;
# }
# return exponent < 0 ? 1/ r : r;
# }
# };

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

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

思路

1. 遍历，两个列表分别存储奇数和偶数，最后再相链接
2. 排序，前偶数后奇数就交换

代码实现

#方法一，两个列表分别存储奇数和偶数，最后再相链接，取余操作也可以按位与操作
class Solution:
    def reOrderArray(self, array):
        jishu=[]
        oushu=[]
        for number in array:
            if number%2!=0:
            #if number&1==1: #按位与
                jishu.append(number)
            else:
                oushu.append(number)
        return jishu+oushu

#方法二，类似冒泡算法，前偶后奇数就交换
class Solution2:
    def reOrderArray(self, array):
        for i in range(0,len(array)):
            j = len(array) - 1
            while(j>i):
                if(array[j]%2==1 and array[j-1]%2==0):
                    array[j],array[j-1]=array[j-1],array[j]
                j-=1
        return array

#方法三，如果不考虑稳定排序，可以采取类似快排的方法
class Solution3:
    def reOrderArray(self, array):
        i=0
        j=len(array)-1
        while i<j:
            while (i<j and array[i]%2==0):
                i+=1
            while (i<j and array[j]%2==1):
                j-=1
            array[i],array[j]=array[j],array[i]
        return array

链表中倒数第k个结点

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

思路

1. 借助一个列表，不断取链表结点存入列表，取列表倒数第k个值
2. 设置两个指针，p1，p2，先让p2走k-1步， 然后再一起走，直到p2为最后一个 时，p1即为倒数第k个节点

代码实现

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
#方法一，借助一个列表，不断取链表结点存入列表，取列表倒数第k个值
class Solution:
    def FindKthToTail(self, head, k):
        result=[]
        while head!=None:
            result.append(head)
            head=head.next
        if(k>len(result)or k<1):
            return
        return result[-k]

#方法二，设置两个指针，p1，p2，先让p2走k-1步，
# 然后再一起走，直到p2为最后一个 时，p1即为倒数第k个节点

class Solution2:
    def FindKthToTail(self, head, k):
        # write code here
        if head==None or k<=0:
            return None
        #设置两个指针，p2指针先走（k-1）步，然后再一起走，当p2为最后一个时，p1就为倒数第k个 数
        p2=head
        p1=head
        #p2先走，走k-1步，如果k大于链表长度则返回 空，否则的话继续走
        while k>1:
            if p2.next!=None:
                p2=p2.next
                k-=1
            else:
                return None
#两个指针一起 走，一直到p2为最后一个,p1即为所求
        while p2.next!=None:
            p1=p1.next
            p2=p2.next
        return p1

反转链表

题目描述
输入一个链表，反转链表后，输出新链表的表头。

思路

1. 非递归
2. 递归

代码实现

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
#方法一，非递归方法
class Solution:
    def ReverseList(self, pHead):
        pre=None
        if pHead==None or pHead.next==None: #如果当前结点为空或者其后继结点为空，则返回当前结点
            return pHead
        while pHead!=None:
            tmp=pHead.next   #tmp保存当前结点的下一个结点
            pHead.next=pre   #当前结点指向前一个结点，反转指针
            pre=pHead        #当前结点变成下一轮的前一个结点
            pHead=tmp        #当前结点后移一位
        return pre

#方法二，递归方法
class Solution2:
    def ReverseList(self, pHead):
        pre=None
        if pHead==None or pHead.next==None: #如果当前结点为空或者其后继结点为空，则返回当前结点
            return pHead
        p_new=self.ReverseList(pHead.next) #先反转后面的链表，走到链表的末端结点
        pHead.next.next=pHead              #再将当前结点设置为后面结点的后继结点
        pHead.next=None
        return p_new