Ea5ter's Bolg

一天一道lintcode

字数统计: 1.3k阅读时长: 5 min
2018/07/12 Share

写在前面

lintcode一个在线刷题网站。因为不支持c语言,那就只有用相对熟悉的python了。争取每天做一道来提升自己的编程能力,顺带学习下python。

做题笔记

1、A+B problem


简而言之就是不用’+’来算加法。
不用加法自然就想到了位运算,现列举几个要使用的位运算符。

1
2
3
4
and:同为1得1
or :有1得1
xor:相异得1
<< :左移,左移x位相当于乘以2的x次方

先来找规律,从简到繁。
A = 1, B = 2
A: 0001
B: 0010
2: 0011
2 == A ^ B
当A+B没有产生进位时,通过异或运算(^)是可以得到正确结果的。但如果有进位呢?
A = 1, B = 3
A: 0001
B: 0011
4: 0100
4 != A ^ B
可以看到A^B=0010是不等于4的,因为左边第一位的两个1相加产生了进位。既然产生了进位,那就得把进的数给加起来。所以1+3的运算流程应该是:
1、A^B=0010。因为最左一位产生了进位,所以将最左一位向左移一位(0010),再于A^B相加。
2、(A^B) ^ ((A&B)<<1) = 0000, 因为左二位产生了进位,所以将最左二位向左移一位(0100),再之相加。
3、最后 0000 ^ 0100 = 0100 得到正确答案。
通用流程就应该为:
1、A&B判断有无进位(因为只用1+1才会产生进位,当没有进位时A&B就为0)。
2、如果没有进位则A^B得出答案。
3、如果产生了进位,则用A&B将要进的位取出来左移一位,再和A^B重复这一过程。
先通过C来实现这一过程:

1
2
3
4
5
6
7
8
9
int A_plus_B(int a, int b)
{
if ((a & b) == 0)
return a ^ b;
else
{
return A_plus_B(a ^ b, (a & b) << 1);
}
}

再转换为python代码:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
"""
@param a: An integer
@param b: An integer
@return: The sum of a and b
"""
def aplusb(self, a, b):
if ((a&b) == 0):
return a^b
else:
return self.aplusb(a^b,(a&b)<<1)

但代码在python上运行却产生了一个问题,就是当两数给相反(只有相反)时算不出结果,并会报错:

经查询这个错误RuntimeError: maximum recursion depth exceeded in cmp是递归深度不够造成的。python的默认递归深度是998,那么运行一个1-1要递归多少次呢?
通过给之前的C代码加上这么一行,来测试我们递归的深度:

1
2
3
4
5
6
7
8
9
10
11
12
int A_plus_B(int a, int b)
{
static int i = 0;
i++;
printf("%d\n", i);
if ((a & b) == 0)
return a ^ b;
else
{
return A_plus_B(a ^ b, (a & b) << 1);
}
}

结果…真是让人头皮发麻。

最后我在py代码中加了一行判断,也算是得到了正确答案。但为什么会产生递归深度不够这个错误,还得请求其他大佬的帮助了。

2、尾部的零

先上题目:

看似简单的问题通常隐藏了很大的麻烦,想用普通的方法肯定是不行的,因为限制了时间复杂度。
先考虑什么情况会尾部会得到0,首先5乘以一个偶数会产生0,而偶数的个数肯定是大于五的,所以可以通过判断5倍数的个数来判断0的个数。
但25它乘以偶数会产生两个0,这是因为它的因数中含有两个5。这样的数还有50、75……
所以判断100!尾数的0的方法
1、100/5算出有多少个5的倍数。
2、因为25的倍数会多产生一个,所以再加上100/25。
由此可推知,如果还有125(5的三次方)的倍数。就还得加n/215。最后写出代码:

1
2
3
4
5
6
7
8
9
def trailingZeros(self, n):
a = 5
i = 2
count = 0
while a < n:
count += n / a
a = 5 ** i
i += 1
return count

3、合并排序数组II


简而言之合并两个数组排序,但数组是排好序的数组。
看要求比较简单,应该是考算法的速度。不过我也不追求这些了,就当学习下python的数组操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def mergeSortedArray(self, A, B):
C = []
while True:
if A[0] >= B[0]:
C.append(B.pop(0)) #append()方法,用于在列表后添加一个对象
elif A[0] < B[0]:
C.append(A.pop(0)) #pop()方法,在列表中抽取一个对象
if len(A) == 0 or len(B) == 0 :
if len(A) == 0 :
C = C + B #python'+'即可连接两个列表或字符串
elif len(B) == 0 :
C = C + A
else:
break
break
return C

然后发现了个更简单的方法,用列表操作中的sort()方法可以直接排序,代码如下:

1
2
3
4
C = []
C = A + B
C.sort()
return C

4、旋转字符串


也是很简单的,自己想的是用两个字符串。一个把偏移量个数的尾部截下来,一个把偏移量个数的尾部截出去。再把两个字符串粘,但实现的代码更简单。

1
2
3
def rotateString(self, str, offset):
str = str[-offset:] + str[:-offset]
return str

本地测试没问题,但在网上测试就要报错:Using config file /etc/pylintrc。没查到什么解决方案,世界未解之谜+1

CATALOG
  1. 1. 写在前面
  2. 2. 做题笔记
    1. 2.1. 1、A+B problem
    2. 2.2. 2、尾部的零
    3. 2.3. 3、合并排序数组II
    4. 2.4. 4、旋转字符串