学妹和我讨论Py编程题后,我决定入坑LeetCode

学妹和我讨论Py编程题后,我决定入坑LeetCode

大概一周前,一位大数据学院的小学妹加了我好友,然后开始向我请教各种Python编程题虽然题目都很简单,但是我不禁感叹,大一刚进校就开始这么拼了么?我知道她问的题很多都是LeetCode上面的算法题,但是我都大三了,还没刷过LeetCode,有点惭愧。这篇文章主要是整理我给她讲过的题目的思路。提醒自己记得多刷算法题,不然以后都不敢给学妹讲题了orz。

这里我以给学妹讲题的顺序,将每道题依次贴出来。并简单记录一下我自己的思路和代码,我并未参考网上的解答,所以可能也不是最优解。

这是学妹问我的第一题,很简单。但是学妹问我她的代码是哪里有bug,然后我看了她的代码。

看完我差点想删好友了,看得我心里很难受,有这么复杂的吗?想了想是学妹,还是算了吧。于是我按照我的思路重新写了一段代码。

一行代码就解决了,但我想了想学妹肯定看不懂,所以我就简化了一下。并给代码加上了注释。

简单说一下我的思路。题目要求每一位对应乘以它所以位数的幂次方来表示,那怎么构造出这个幂次方呢?我想的就是巧妙利用每个字符的索引值,此时4的索引值就是0,但是并不是我们想要的。所以我们可以把列表倒序,此时4的索引值就是3了而10的3次方就是1000,其他位依次对应,就构造出来了。

因为字符串也是序列,但为了学妹能够理解,我就将它转化为列表,此时列表就是对应该数字的每一位。这里用到了enumerate() 函数,很多人可能用到比较少。

enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列,同时列出数据和数据下标,一般用在 for 循环当中。

所以为了学妹能看懂,我就没有发她上面的一行代码,稍微正常一些的。代码如下:

X = input('请输入一个十进制数:')
result = []
for a,b in enumerate(X[::-1]):
     result.append('{}*{}'.format(b,pow(10,a)))
print('X={}'.format('+'.join(result[::-1])))

这道题学妹给了她手写的代码。

虽然思路是对的,但是这明显不符合题目要求,两次同时不能重复利用同样的元素,所以我让学妹加上了判断i!=j,所以这道题我就没有写代码。

突然发现她打印的时候忘记把索引值放在列表中了,当时忘记提醒她了。

这道题是我觉得最有意思的一道题。我思索了一阵后,我的想法是打算找规律取巧。以罗马数字1-10为例,最特殊的是4和9。

因为4对应IV,9对应IX。

这两个罗马数字是由小的数字(I)放在前面,大的数字(V)放后面,我认为较为特殊。

而像8对应VIII这类都是大的(V)在前面,小的(V)在后面是常规的。

我是从字符串的角度来思考的。

VIII(8)可以看做V+I+I+I相加

而IV(4)却不能看做I+V相加

所以我们就可以把特殊取出来。其他的都拆分为单个字符相加,把对应的值放入列表中。如果遇到4和9就把他们替换为空,直接将其对应的值放入列表中。最后再列表求和。代码如下

num = input('请输入一个罗马数字(介于1-3999之间):')
nums = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
special ={'IV':4,'IX':9,'XL':40,'XC':90,'CD':400,'CM':900}
n = []
for i in special.items():
    if i[0] in num:
        num = num.replace(i[0], '')
        n.append(i[1])
for i in num:
    n.append(nums[i])
print(sum(n))

虽然我这样的解法,运行速度挺快的,但是我去leetcode上测了下占用的内存太大,算是用空间换时间了吧。

这道题也很简单,但是其中有一些需要注意的地方。以我的代码为例。

由于是从0开始的,但是字符串x拼接str(i),x也是从0开始的。

这也就是为什么x本来就是字符串,我还要用int(x)的缘故。

这里我还发现一个问题,format是默认字符串输出,所以直接int(x)用format输出也不会报错,不用str(int(x))。

这道题同样很简单,关键就是把列表中的字符串的带一个字作为判断依据。

所以我想了两个思路,一个是先遍历列表,把所有的直辖市给提取出来。再用set集合去重,根据对应的键值放入字典中。

但是这样并不是较好的解法,因为遍历了两次列表。所以我又思考了另一种,通过判断键值是否存在,直接添加。

这个思路更为优秀。

这道题学妹也发了她的代码。

虽然这样写没问题,可是也太复杂了吧,而且每个数都要计算和判断三次。

我还是喜欢取巧。因为是除以3判断余数,所以我想到的是通过浮点数来判断。我们知道任意一个整数除以3,它浮点数的第一位肯定是0,3,6这三个值。

大家发现规律了吗,我们可以通过小数点后的第一位来判断。代码如下

通过split将结果以点分为两部分,取出小数点后第一位。这样不仅减少计算和判断,也减少了代码量。

总结:目前上面这些题,都是学妹在qq上和我讨论的题目,还有一些学妹当面问我的题没有贴上来,之后会补充到上面的,算是自我总结吧。

虽然都是很简单的算法题,我也都能做出来。但是我也意识到了我在算法方面还存在很大的不足,以后的时间一定要抽时间刷LeetCode,提升思维能力,不然以后都不敢给学妹讲题了。

上面的这些题我没参考网上的解法,各位大佬如果对上面的题有什么更好的解法,欢迎留言和我讨论!

zgao

如果有什么技术上的问题,可以加我的qq 1761321396 一起交流。