剑指offer（三）

以你之姓@ 2022-02-18 11:27 240阅读 0赞

剑指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