剑指offer的Python实现(三)
位运算:
11.二进制中1的个数
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
思路:先判断整数二进制表示中最右边一位是不是1,接着把输入的整数右移一位,再判断是不是1.这样每次移动一位,直到整个整数变成0为止。现在的问题是怎么判断一个整数的最右边是不是1.
只要把整合和1做位于运算看结果是不是0.如果结果是1,则该位数为1,否则为0.
但是,上边的方法如果输入负整数就会出现问题,可能会出现死循环。
新想法:
首先把整数n与1做与运算,判断n的最低位是不是1.接着把1左移一位得到2,再和n做与运算,就能判断n的次低位是不是1…这样反复左移,每次都能判断i的其中一位是不是1.
最好的方法:
把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变为0.那么一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。
# -*- coding:utf-8 -*-
class Solution:
# def NumberOf1(self, n):
# write code here
# count = 0
# flag = 1
# while(flag):
# if (n & flag):
# count += 1
# flag = flag << 1
# return count
def NumberOf1(self, n):
# write code here
count = 0
if n < 0:
n = n & 0xffffffff
while n:
count += 1
n = (n - 1) & n
return count
12.数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
考虑问题要全面,如果指数是负数,是0的情况,如果底数是0,指数是负数的情况。
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
result = 1
if base == 0:
return 0
if exponent == 0:
return 1
if exponent < 0:
for i in range(-exponent):
result = result * base
return (1/result)
for i in range(exponent):
result = result * base
return result
13.调整数组顺序使奇数位于偶数前面
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
# write code here
odd, even = [],[]
for i in array:
if i%2 == 1:
odd.append(i)
else:
even.append(i)
return odd + even
14.链表中倒数第K个结点
输入一个链表,输出该链表中倒数第k个结点。
可以定义连个指针。第一个指针从链表的头指针开始遍历向前走K-1,第二个指针保持不动;从第K步开始,第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在K-1,当第一个指针到达链表的尾结点时,第二个指针正好是倒数第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
if head == None or k <= 0:
return None
p2 = head
p1 = head
while k>1:
if p2.next != None:
p2 = p2.next
k -= 1
else:
return None
while p2.next != None:
p1 = p1.next
p2 = p2.next
return p1
15.反转链表
输入一个链表,反转链表后,输出新链表的表头。
1.错误的
# -*- 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 pHead == None:
return None
if p2.next == None:
return pHead
while(p1 != None):
p3 = p2.next
p2.next = p1
p1 = p2
p2 = p3
return p3
2.正确运行出来的
# -*- 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
last = None
while pHead:
tmp = pHead.next
pHead.next = last
last = pHead
pHead = tmp
return last
3# -*- 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 pHead==None or pHead.next==None:
return pHead
pre = None
cur = pHead
while cur!=None:
(1) tmp = cur.next (1)要断开连接的后边那个保存起来,在第(4)步时候付给cur,实现指针往后走,同时pre赋值为cur,也在往后走,
(2)cur.next = pre
(3)pre = cur
(4)cur = tmp
return pre