本文共 3042 字，大约阅读时间需要 10 分钟。

jz11 二进制中1的个数

题目描述

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

思路分析：

1.利用一个结论：一个二进制数n减1后与原二进制数进行&运算( 即n&(n-1) )会消去最右边的1。

• 假设二进制数101进行减1运算，刚好最右边是1，则得到100，此时用100跟101做&运算，得到的是100，故消去了101左右边的1。
• 100减1呢？最低位是0,跟十进制减法一样啊，向高位借。(可以脑补一下十进制100减1的过程)

所以二进制100减1的运算过程如下：

• 最右边的0向右数第二位借1得：2-1=1，
• 右数第二位还是0，却要借给最右边那位1，所以它也得向高位借。
• 这样右数第三位的1借给它1之后变成0，右数第二位借1得：2-1=1。
• 所以得到新数为011。

观察一下刚刚的运算过程可以发现：

• 如果最右边刚好是1(如101)，进行减1运算就不用向高位借，直接得0，高位则保持原样不变(得100)。
  -再把减1后得到的数与原数&运算(即101&100=100)可知高位都不变那就是消去最右边的1！(由这可能还不太明显是消去最右边的1，继续看下面的)
• 如果最右边是0(如100)，进行减1运算，则需要像高位借，而最终会导致最近的高位1因为被借走1而变0，而比它高的高位保持原样不变(得011),再跟原来的数进行&运算(即100&011=000)；
• 所以由以上两点可知二进制数每次减1后与原数进行&运算会消去最右边的1。

# -*- coding:utf-8 -*-class Solution:    def NumberOf1(self, n):        # write code here        count=0        if n<0:            n=n&0xffffffff#负数用补码表示        while n:            n=(n-1)& n#按位与运算符            count+=1        return count

jz12 数值的整数次方

题目描述

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

保证base和exponent不同时为0

分情况讨论，特殊情况特殊讨论。

# -*- coding:utf-8 -*-class Solution:    def Power(self, base, exponent):        # write code here        if exponent==0:            return 1        elif base==0:            return 0        else:            exponent!=0 and base!=0            return base**exponent

jz13 调整数组顺序使奇数位于偶数之前

题目描述

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

思路分析：

1、新建两空列表1，2

• 如果数字为奇数就放在列表1
• 如果数字为偶数就放在列表2

3、将列表1，2合并起来，并且列表2在后半部分。

【代码实现】：

# -*- coding:utf-8 -*-class Solution:    def reOrderArray(self, array):        # write code here        list1=[]        list2=[]        for value in array:            if value%2 == 1:#%:求余                list1.append(value)            else:                list2.append(value)        return (list1+list2)#合并两列表

jz14 链表中倒数第K个节点

题目描述

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

1、遍历链表，将每一元素添加到一列表中

【代码实现】：

# -*- coding:utf-8 -*-# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def FindKthToTail(self, head, k):        # write code here        list1=[]        while head!=None:            list1.append(head)            head=head.next        if k>len(list1) or k<1:            return        return list1[-k]

jz15 反转链表

题目描述

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

思路分析：

初始化：3个指针

• pre指针指向已经反转好的链表的最后一个节点，最开始没有反转，所以指向空
• cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向head即头指针
• nex指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存

接下来，执行下面的循环：

当待反转链表的节点不为空时:

循环结束后，cur当然为nullptr，所以返回pre，即为反转后的头结点

【代码实现】

# -*- coding:utf-8 -*-# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    # 返回ListNode    def ReverseList(self, pHead):        # write code here        pre=None        cur=pHead        nex=None        while cur:            nex=cur.next            cur.next=pre            pre=cur            cur=nex        return pre

时间复杂度：O(n) 因要遍历整个链表