Python小白 Leetcode刷题历程 No.11-No.15 盛最多水的容器、整数转罗马字母、罗马数字转整数、最长公共前缀、三数之和
写在前面：
作为一个计算机院的大学生，总觉得仅仅在学校粗略的学习计算机专业课是不够的，尤其是假期大量的空档期，作为一个小白，实习也莫得路子，又不想白白耗费时间。于是选择了Leetcode这个平台来刷题库。编程我只学过基础的C语言，现在在自学Python，所以用Python3.8刷题库。现在我Python掌握的还不是很熟练，算法什么的也还没学，就先不考虑算法上的优化了，单纯以解题为目的，复杂程度什么的以后有时间再优化。计划顺序五个题写一篇日志，希望其他初学编程的人起到一些帮助，写算是对自己学习历程的一个见证了吧。
有一起刷LeetCode的可以关注我一下，我会一直发LeetCode题库Python3解法的，也可以一起探讨。
觉得有用的话可以点赞关注下哦，谢谢大家！
········································································································································································
题解框架：
1.题目，难度
2.题干,题目描述
3.题解代码（Python3（不是Python，是Python3））
4.或许有用的知识点（不一定有）
5.解题思路
6.优解代码及分析（当我发现有比我写的好很多的代码和思路我就会写在这里）
········································································································································································
No.11.盛最多水的容器
难度:中等
题目描述：
题解代码（Python3.8）
class Solution:
def maxArea(self, height: List[int]) -> int:
i,j,smax=0,len(height)-1,0
while i<j:
if height[i] < height[j]:
smax=max(smax,height[i]*(j-i))
i +=1
else:
smax=max(smax,height[j]*(j-i))
j -=1
return smax
或许有用的知识点：
这道题用双指针法，固定大边，移动小边，是可以证明正确性和安全性的，即略去的情况都必定不是最大值。
解题思路：
最简单的办法是两边for循环遍历所有可能，但这样太麻烦了，我们显然有更简单的方法。思考一下，我们可以设置两个指针，i代表左边的容器壁，j代表右边的容器壁。首先我们要while i<j 的情况下才进行运算，之后我们判断左边和右边哪个容器壁短，我们移动短的容器壁，然后记录最大面积即可。
No.12.整数转罗马字母
难度:中等
题目描述：
题解代码（Python3.8）
class Solution:
def intToRoman(self, num: int) -> str:
dic={'I':1,'IV':4,'V':5,'IX':9,'X':10,'XL':40,'L':50,'XC':90,'C':100,'CD':400,'D':500,'CM':900,'M':1000}
res=""
for val in sorted(dic.values())[::-1]:
if num==0:
break
tmp=num//val
if tmp==0:
continue
res +=(list (dic.keys()) [list (dic.values()).index (val)])*tmp
num -=val*tmp
return res
或许有用的知识点：
sorted(dic.values())[::-1]表示把字典的值从小到大排列，再倒序取出，其中若由键取值比较简单 value=dict[key],
而由值取键则需要key=list (dic.keys()) [list (dic.values()).index (val)]。
由键取值与代码健壮性的关系：
index函数：
解题思路：
显然这个题需要采用贪心算法，我们可以用字典的值和键分别表示罗马字母与数字，由题意通常情况是大数的罗马字母在前，因此我们只需要把特殊情况写进字典，就可以认为全部满足通常情况大数的罗马字母在前。字典的结构为：dict( key : value)这个题应该让key为数字，value为罗马字母比较好写，但是我开始写反了，就反着做了。我们采用贪心算法，从最大罗马字母开始循环，有的话就加载res上，有几个加几个，没有就继续循环。
No.13.罗马数字转整数
难度：简单
题目描述：
题解代码（Python3.8）
class Solution:
def romanToInt(self, s: str) -> int:
dic={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
ans=0
for i in range(len(s)):
if i<=len(s)-2 and dic[s[i]]<dic[s[i+1]]:
ans-=dic[s[i]]
else:
ans+=dic[s[i]]
return an
解题思路：
同上个题类似，还是先创建字典，这次不用考虑特殊情况，然后for循环遍历s中每个罗马字母，当这个字母不是最后一个，而且这个字母对应的字典值比下一个小，则这是出现了特殊情况，总和应减去这个值；其余的时候累加对应值就可以了。
NO.14.最长公共前缀
难度：简单
题目描述：
题解代码（Python3.8）
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs)==0:
return ""
if len(strs)==1:
return strs[0]
s=""
l=len(strs[0])
for i in range(1,len(strs)): #判断最短字符串长度
l=min(l,len(strs[i]))
for i in range(l): #在最短长度中
k=1
for j in range(1,len(strs)): #对第j个字符串的第i个字符
if strs[j][i]==strs[0][i]:
k +=1
else:
k=0
break
if k==0:
break
if k==len(strs):
s +=strs[1][i]
return s
或许有用的知识点：
解题思路：用一个for循环判断最短字符串长度，再用两个for循环判断第j个字符串的第i的字符是否跟第1个字符串的第i个字符相等，如果不相等就退出循环。
优解代码及分析：
优解代码（Python3.8）
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
res=""
for tmp in zip(*strs):
tmp_set=set(tmp)
if len(tmp_set)==1:
res +=tmp[0]
else:
break
return res
分析：
将多个字符串看成一个元组，利用zip（*tuple）对元组进行拆包，如果最短的字符串由n个字母组成，元组拆包就能得到tmps=[(各个字符串的第一个字母)，(各个字符串的第二个字母)，……，(各个字符串的第n个字母)]。提取res的第一个元素并使用set()函数去重，如果都一样，则长度len()==1，把该字母写入res中，当出现len()!=1，则退出。
NO.15.三数之和
难度：中等
题目描述：
题解代码（Python3.8）
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
l=len(nums) #特解
if l<3:
return []
res=[]
nums.sort()
for i in range(l-2):
if nums[i]>0: #最小数>0，跳出循环
break
if i>0 and nums[i]==nums[i-1]: #最小数与上一轮循环相同，防止重复解，跳过
continue
L=i+1
R=l-1
while L<R:
if nums[i]+nums[L]+nums[R] == 0:
res.append([nums[i],nums[L],nums[R]])
while L<R and nums[L]==nums[L+1]: #左指针向右跳过重复值，防止重复解
L +=1
while L<R and nums[R]==nums[R-1]: #右指针向左跳过重复值，防止重复解
R -=1
L +=1
R -=1
elif nums[i]+nums[L]+nums[R] > 0: #三数和>0，右指针大了，左移
R -=1
else: #三数和<0，左指针小了，右移
L +=1
return res
或许有用的知识点：
set(list)函数可以将list中重复元素过滤，set是无序的，Python不支持dict的key为set，list或dict类型，因为list和dict类型是unhashable（不可哈希）的；
不可哈希的list表，可通过if i not in list查重；
list.append(‘ ’)可以在list末尾添加元素，list.insert( i,’ ‘)可以在list的i处添加元素；list.pop()可以删除list末尾的元素，list.pop( i )可以删除list中i处的元素；
set.add(key)可以在set中添加元素，set.remove(key)可以在set中删除元素。
解题思路：
见到这个题第一反应是用三个for循环遍历数组，计算三数之和，但是后来发现超时了，显然不应该这样做。于是我将数组排序，第一个数也就是最小数一定小于零，否则可以退出循环；当我们确定了最小数，就只剩下中间数和最大数，我们用双指针法。最小数与上一轮循环相同，防止重复解，跳过；确定最小数后，判断最小数+左指针+右指针是否等于0，若等于零，左指针向右跳过重复值，防止重复解，右指针向左跳过重复值，防止重复解，之后左指针+1，右指针-1。若不等于0，判断，若三数和>0，右指针大了，应左移；若三数和<0，左指针小了，右移。
