力扣题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