总结三道算法题

28次阅读

共计 1115 个字符,预计需要花费 3 分钟才能阅读完成。

今天给大家总结几道算法题,其中用到了一些不常用的技巧,希望大家和我一样,也能收获一些新东西。

有一个集合,其任意一个元素的对称元素也一定存在于这个集合中,现随机取出一个元素,求这个元素是谁

刚看到这个题的时候我就想,肯定不能用 for 循环的方式,否则这个题基本上是无意义的,那么问题来了,我该用什么方式,然后因为是集合所以我脑子里又想出来用差集的方式。代码如下:
s = {2, 4, 6, -6, -4, -2}
s1 = s.copy()
s1.pop() # 这里就是删除一个元素,再删除一个一样的操作
el = (s – s1)*-1
这样子行吗,我自己都怀疑我自己,不知道会不会这么简单或者不会这么复杂,然后的然后我没想出来其他的方式,不过后来又知道了一种解法,代码如下:

s = {2, 4, 6, -6, -4, -2}
s1 = s.copy()
s1.pop()
el = sum(s)*-1 # 根据对称特性,相加等于零,那么就这么解答出来了
亲测了一下两个的执行效率,几乎是差不多的,不过求差集还会更快些。

在一个列表中只有一个元素存在次数为 1,其他都为 2,求这个元素

是不是又想到了 for,虽然这种问题 for 可以解决,但是和上一个问题一样,我也觉得使用 for 是无意义的,那么我们应该怎么解?请看代码:
l = [1,2,1,3,4,5,3,4,5]

from functools import reduce
reduce(lambda x,y:x^y, l)

reduce 的使用方式很简单:第一个参数是一个函数(这个函数只能有两个参数),用来处理第二个参数(可迭代对象),第一次执行将第二个参数中前两个元素作为实参参入,然后接下来进入一个循环,将第一次的结果和第三个元素作为实参传入,依此类推 …
^ 这个表示异或,对左右两侧数的二进制操作,最低位对其,相对的位如何数字不同 (1 对应 0,或者 0 对应 1) 那么结果为 1,否则为 0,所以自身异或自身为 0,利用这个特性完成了此题。还有逻辑与,逻辑或,逻辑与就是两个二进制数据相对的位相同为 1,不同为 0;逻辑或就是两个二进制数据相对的位不同为 1,相同为 0

一层楼有 10 级台阶,可以 1 次 1 级,2 级,或 3 级的方式上楼,请问走完这 10 级台阶有几种方式?

这个问题我是有印象的,和斐波那契类似,我把他归为斐波那契变形,当然其实这种问题是属于 dp(动态规划)的,我是不懂,所以过程提供给大家:
l = [1,1,2]
for i in range(3,11):
l.append(l[i-1]+l[i-2]+l[i-3]) # 这种思维是不是和斐波那契类似呢,你们可以对比一下

l[10] # 274

通过每个题都让我学到了一种思维,很不错,有些问题我们需要更多的去思索,查找最优方式,这样才能锻炼我们的大脑,一起加油。

正文完
 0