力扣题11~20
题11（中等）：
思路：
这种题目第一眼就是双循环，但是肯定不行滴，o(n^2)这种肯定超时，很难接受。
所以要另辟蹊径，我们先用俩指针（标志位）在最左端和最右端，我们知道这个容器的最大容积是看最短的那条（木桶效应嘛）。如果我们让长的那一条再怎么大，都影响不了容积，所以我们加上底不变的话，要找最大容积，肯定要变短边嘛，动长边又改变不了什么，也就是说这个时候移动长边得到的一定不是。思路打开就写代码
python代码
class Solution:
def maxArea(self, height: List[int]) -> int:
left=0
right=len(height)-1
max_area=0
while left<right:
h=min(height[left],height[right])
w=right-left
area=h*w
max_area=max_area if max_area>area else area
if height[left]<height[right]:
left+=1
else:
right-=1
return max_area
题12（中等）：
思路：
作为爬虫玩家，这种东西直接给个关系映射就好了啊，谁会去思考4,9特殊情况啊
python代码：
class Solution:def intToRoman(self, num: int) -> str:Roman_str=''tran_json={1:'I',4:'IV',5:'V',9:'IX',10:'X',40:'XL',50:'L',90:'XC',100:'C',400:'CD',500:'D',900:'CM',1000:'M',}i=10while 1:if num<1:break#获得在各个位的数字h_num=num%10num=int(num/10)if h_num==0:i*=10elif h_num<4:Roman_str=h_num*tran_json[i/10]+Roman_stri*=10elif h_num==4:Roman_str=tran_json[4*i/10]+Roman_stri*=10elif h_num<9:Roman_str=tran_json[5*i/10]+(h_num-5)*tran_json[i/10]+Roman_stri*=10elif h_num==9:Roman_str=tran_json[9*i/10]+Roman_stri*=10return Roman_str
题13（简单）：
思路：
和上面一样，不想那么多，直接用json存下换算规则，就像处理爬虫的字体加密一样，不想什么方法，直接字体识别出键值对来就套用，懒得看什么先转unicode啥的
python代码：
class Solution:
def romanToInt(self, s: str) -> int:
R_cout=0
tran_json={
'I':1,
'V':5,
'X':10,
'L':50,
'C':100,
'D':500,
'M':1000
}
ts_json={
'IV':4,
'IX':9,
'XL':40,
'XC':90,
'CD':400,
'CM':900
}
for key,value in ts_json.items():
s=s.replace(key,'|'+str(value))
for key,value in tran_json.items():
s=s.replace(key,'|'+str(value))
R_cout=sum(list(map(int,s.strip('|').split('|'))))
return R_cout
题14（简单）：
思路：
双for循环直接解决了
python代码：
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
pub_str=''
for i in range(min([len(s) for s in strs])):
k=strs[0][i]
for j in range(1,len(strs)):
if k!=strs[j][i]:
return pub_str
pub_str+=k
return pub_str
题15（中等）：
思路：
和前面一个容器的那个一样，用双指针法，我们将nums排好序，固定一个起始的话，如果大的话移动右指针，小的话移动左指针。
python代码：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result=[]
n_len=len(nums)
for i in range(len(nums)):
pos=i
if nums[i] > 0:
break
# 跳过可能重复的数字，避免重复的三元组
if i > 0 and nums[i] == nums[i-1]:
continue
left=pos+1
right=n_len-1
#预处理，如果前两个加最后一个都大的话，就删了最后一个
while left<right:
if nums[pos]+nums[left]+nums[right]>0:
right-=1
n_len-=1
else:
break
while left<right:
total = nums[i] + nums[left] + nums[right]
if total==0:
result.append([nums[pos],nums[left],nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total>0:
right-=1
else:
left+=1
return result
题16（中等）：
思路：
双指针法，和15题差不多，就是要排除了，如果total<target则排除了更小的（left右移），如果total>target则排除了更大的（right左移）
python代码：
class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:nums.sort()sum=nums[0]+nums[1]+nums[2]for i in range(len(nums)):if i>0 and nums[i]==nums[i-1]:continueleft = i + 1right = len(nums) - 1while left < right:total=nums[i]+nums[left]+nums[right]if abs(target-total)<abs(target-sum):sum=totalif total<target:left+=1elif total>target:right-=1else:return targetreturn sum
题17（中等）：
思路：
枚举列出来就好了，能过就行，虽然时间复杂度有点
python代码：
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if digits=='':
return []
btn_json={
'1':'',
'2':'abc',
'3':'def',
'4':'ghi',
'5':'jkl',
'6':'mno',
'7':'pqrs',
'8':'tuv',
'9':'wxyz',
}
res_list=['']
for i in digits:
res=btn_json[i]
tmp_list=res_list
res_list=[n+j for n in tmp_list for j in res]
return res_list
题18（中等）：
思路：
两数和，三数和，三数接近，这几题好玩吧，没尽兴就又来了一个4数和，一样的
python代码
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
res_list=[]
for i in range(len(nums)):
if i>0 and nums[i]==nums[i-1]:
continue
tmp_target=target-nums[i]
for j in range(i+1,len(nums)):
if j>i+1 and nums[j]==nums[j-1]:
continue
left=j+1
right=len(nums)-1
while left<right:
total=nums[left]+nums[right]+nums[j]
if total==tmp_target:
res_list.append([nums[i],nums[j],nums[left],nums[right]])
while left<right and nums[left]==nums[left+1]:
left+=1
while left<right and nums[right]==nums[right-1]:
right-=1
left+=1
right-=1
elif total<tmp_target:
left+=1
else:
right-=1
return res_list
题19（中等）：
思路：
这个用c应该比较容易理解
python代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
n_len=1
p=head
while 1:
if p.next!=None:
n_len+=1
p=p.next
else:
break
pos=n_len-n
p=head
if pos==0:
head=head.next
return head
for i in range(pos-1):
p=p.next
p.next=p.next.next
return head
题20（简单）：
思路：
这个就是金典的栈的运用啊，我之前还有一个文章是表达式的转换来着
python代码：
class Solution:
def isValid(self, s: str) -> bool:
s_stack=[]
for i in s:
if i=='(' or i=='{' or i=='[':
s_stack.append(i)
elif i==')':
if len(s_stack)!=0 and s_stack[-1]=='(':
s_stack.pop()
else:
return False
elif i == '}':
if len(s_stack)!=0 and s_stack[-1] == '{':
s_stack.pop()
else:
return False
elif i == ']':
if len(s_stack)!=0 and s_stack[-1] == '[':
s_stack.pop()
else:
return False
if len(s_stack)==0:
return True
else:
return False