二进制中1的个数
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路
如果是负数，先获取它的补码形式，然后统一为正数处理。发现，当一个数大于0时，不停让它与它的前一位进行按位与操作，即可获得其二进制表示中1的个数。
代码实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class 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次方。
思路
- 直接调用函数
pow，但非常不推荐这种方法。 - 累乘，考虑指数的3种情况（小于0，大于0和等于0）
- 位运算代替递归，同样减少乘法运算，但效率更高（python未实现）
代码实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#方法一，直接调用库函数，在线刷题可以这样，但是如果是面试编程，千万不要这样
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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#方法一，两个列表分别存储奇数和偶数，最后再相链接，取余操作也可以按位与操作
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个结点。
思路
- 借助一个列表，不断取链表结点存入列表，取列表倒数第k个值
- 设置两个指针，p1，p2，先让p2走k-1步， 然后再一起走，直到p2为最后一个 时，p1即为倒数第k个节点
代码实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38class 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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class 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
