剑指Offer-Python(11-15)

11、二进制中1的个数

链接：https://www.nowcoder.com/questionTerminal/8ee967e43c2c4ec193b040ea7fbb10b8?answerType=1&f=discussion

来源：牛客网

如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，

原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。

举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，

而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。

这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。

如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.

那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

class Solution:

    def NumberOf1(self, n):

        count = 0

        if n < 0:

            '''

            对于负数，最高位为1，而负数在计算机是以补码存在的，往右移，符号位不变，符号位1往右移，

            最终可能会出现全1的情况，导致死循环。与0xffffffff相与(成为符数的补码形式)，就可以消除负数的影响

            '''

            n = n & 0xffffffff

        while n:

            count = count + 1

            n = n & (n - 1)

        return count

s = Solution()

print(s.NumberOf1(5))

print(bin(5))

print(s.NumberOf1(-5))

print(bin(-5))

12、数值的整数次方

注意负数次方的处理即可

class Solution:

    def Power(self, base, exponent):

        # write code here

        mul = 1

        if exponent == 0:

            return 1

        if base == 0:

            return 0

        else:

            if exponent > 0:

                for i in range(0, exponent):

                    mul = mul * base

                return mul

            else:

                # print("指数为负数")

                for i in range(0, abs(exponent)):

                    mul = mul * base

                # print(mul)

                return 1/mul

s = Solution()

b = 2.1

e = -3

r = s.Power(b, e)

print(r)

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

# -*- coding:utf-8 -*-

class Solution1:

    # 开辟新数组

    def reOrderArray(self, array):

        # write code here

        rst = []

        for i in array:

            if i % 2 == 1:

                rst.append(i)

        for i in array:

            if i % 2 == 0:

                rst.append(i)

        return rst

class Solution2:

    # 利用冒泡排序相对位置不变

    def reOrderArray(self, array):

        l = len(array)

        flag = True

        while l and flag:

            flag = False

            for i in range(len(array) - 1):

                if array[i] % 2 == 0 and array[i + 1] % 2 == 1:

                    t = array[i]

                    array[i] = array[i + 1]

                    array[i + 1] = t

                    flag = True

            l -= 1

        return array

s = Solution2()

t = [1, 2, 3, 4, 5, 6, 7, 8, 9]

print(s.reOrderArray(t))

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

利用快慢节点就可以找到倒数第k个节点

# -*- coding:utf-8 -*-

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

class Solution:

    def FindKthToTail(self, head, k):

        # write code here

        t = head

        for i in range(k):

            if not t:

                # print("越界")

                return None

            t = t.next

        h = head

        while t:

            t = t.next

            h = h.next

        return h

head = ListNode(1)

t1 = ListNode(2)

head.next = t1

t2 = ListNode(3)

t1.next = t2

t3 = ListNode(4)

t2.next = t3

t4 = ListNode(5)

t3.next = t4

s = Solution()

r = s.FindKthToTail(head, 6)

print(r.val)

15、反转列表

# -*- coding:utf-8 -*-

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

class Solution:

    # 返回ListNode

    def ReverseList(self, pHead):

        # write code here

        if not pHead or not pHead.next:

            return pHead

        h = pHead

        p = pHead.next

        q = pHead.next.next

        while q:

            p.next = h

            h = p

            p = q

            q = q.next

        p.next = h

        pHead.next = None

        return p

head = ListNode(1)

head.next =None

# t1 = ListNode(2)

# head.next = t1

# t2 = ListNode(3)

# t1.next = t2

# t3 = ListNode(4)

# t2.next = t3

# t4 = ListNode(5)

# t3.next = t4

# t4.next = None

s = Solution()

h = s.ReverseList(head)

print(h.val)

巴特西

剑指Offer-Python(11-15)

11、二进制中1的个数

12、数值的整数次方

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

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

15、反转列表

最新文章

热门文章