leetcode刷题：1-20

拼搏现实的明天。 2022-01-16 23:51 273阅读 0赞

### 文章目录 ###

*  1 Two Sum
 *  2 Add Two Numbers
 *  3 Longest Substring Without Repeating Characters
 *  4 寻找两个有序数组的中位数
 *  5 Longest Palindromic Substring
 *  6 ZigZag Conversion
 *  7 Reverse Integer 将给定的数字倒序输出.
 *  8 String to Integer(atoi)
 *  9 Palindrome Number
 *  10 正则表达式匹配
 *  11.求其中两条直线与x轴围成的容器的最大容量.
 *  12.Integer to Roman
 *  13.Roman to Integer
 *  14.Longest Common Prefix
 *  15.3Sum
 *  16.3Sum Closest
 *  17 电话号码的字母组合
 *  18.4Sum 找出list中所有相加等于target的4个数的list.
 *  19 删除链表的倒数第N个节点
 *  20 有效的括号

leetcode刷题：1-20

# 1 Two Sum #

在列表中找到两个数,使得它们的和等于某一给定值,返回这两个数的位置.时间复杂度:O(n),python中的字典其实就是哈希表的应用,所以我们通过字典用哈希表来降低查找的时间复杂度

def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {}
        
        for i, n in enumerate(nums):
            m = target - n
            if m in d:
                return [d[m], i]
            else:
                d[n] = i

# 2 Add Two Numbers #

将两个倒序存放在单链表里的数相加,将结果倒序存储在单链表里返回.思路非常简单,先将两个单链表中的数字分别提取出来求和,然后将=求得的和存入一个单链表,实际上相加这一步也可以直接在原链表中完成,只需要添加判断条件while(l1 or l2 or carry)即可.

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            
            node1 = l1
            node2 = l2
            l3 = ListNode(0)
            l3.next = ListNode(0)
            node3 = l3
            
            sum1 = 0
            coe = 1
            while not node1 is None:
                sum1 += node1.val * coe
                coe *= 10
                node1 = node1.next
                
            sum2 = 0
            coe = 1
            while not node2 is None:
                sum2 += node2.val * coe
                coe *= 10
                node2 = node2.next
                
            sum = sum1+sum2
            
            while sum > 0:
                node3.next = ListNode(sum % 10)
                node3 = node3.next
                sum //= 10
                
            return l3.next

# 3 Longest Substring Without Repeating Characters #

找到字符串中没有重复字符的最大子串.一开始没有想到用字典,而是直接用str来存储字串,时间复杂度是O(n^2),后来用字典将时间复杂度降到了O(n).注意到仅当字典中出现重复值且该重复值在strat区段里时才移动start.另外用了Sliding Window的思想,每次将strat移动到重复值的下一位置

class Solution:
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            start = 0
            max_length = 0
            substring = {}
            
            for i, c in enumerate(s):
                if c in substring and start <= sunstring[c]:
                    start = substring[c] + 1
                else:
                    max_length = max(max_length, i-start+1)
                substring[c] = i
                
            return max_length

# 4 寻找两个有序数组的中位数 #

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

def findMedianSortedArrays( nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
    
        m = len(nums1)
        n = len(nums2)
    
        if m > n:
            nums1,nums2,m,n = nums2, nums1,n,m
        if n== 0:
            raise ValueError
    
        imin = 0
        imax = m
        half_len = (m+n+1) // 2
    
        while imin <= imax:
            i = (imin + imax) // 2
            j = half_len - i
            
            print(i,j)
    
            if i < m and nums2[j-1] > nums1[i]:
                imin = i + 1
                print("(imin)")
                print( imin)
                
            elif i > 0 and nums1[i-1] > nums2[j]:
                imax = i-1
                print("(imax)")
                print(imax)
            else:
                print("(else)")
    
                if i == 0:
                    max_of_left = nums2[j-1]
                elif j == 0:
                    max_of_left = nums1[i-1]
                else:
                    max_of_left = max(nums1[i-1], nums2[j-1])
                    
                print('max_of_left:')
                print(max_of_left)
    
                if (m+n) % 2 == 1:
                    return max_of_left
    
                if i == m:
                    min_of_right = nums2[j]
                elif j == n:
                    min_of_right = nums1[i]
                else:
                    min_of_right = min(nums1[i], nums2[j])
                    
                print('max_of_left,min_of_right:')
                print(max_of_left,min_of_right)
    
                return (max_of_left + min_of_right) / 2.0
            
    
        
                    
    
                    
    nums1 = [1, 3]
    nums2 = [2]
    
    #nums1 = [1, 2]
    #nums2 = [3,4]
    
    print(findMedianSortedArrays(nums1,nums2))

# 5 Longest Palindromic Substring #

最长回文子串问题,一开始我的思路如下:回文子串的特点是首尾字母相同,所以我对每一个字母都找到位于它后面的相同字母,利用切片判断这一段是否为回文子串(str\[i:j\]==str\[i:j\]\[::-1\]).虽然AC了但是时间复杂度很高,主要是因为str.find操作非常耗时.

后来看了Solution发现这是一道可以用动态规划解决的问题,思路是若s是回文字串,令s’=s加上s左右两侧的两个字母,如果这两个字母相同则s’也是回文字串.重写代码如下:

class Solution:
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            
            max = 0
            palindromic = '' if len(s) == 0 else s[0]
            for i in range(len(s)):
                length = 1
                while i - length >= 0 and i+length < len(s) and s[i-length] == s[i+length]:
                    
                    tmp = s[i-length : i+length+1]
                    print(i, tmp)
                    if len(tmp) > max:
                        max = len(tmp)
                        palindromic = tmp
                    length += 1
                length = 1
                
                while i-length+1 >=0 and i+length <len(s) and s[i-length+1] == s[i+length]:
                    tmp = s[i-length+1:i+length+1]
                    print(i, tmp)
                    if len(tmp) >max:
                        max = len(tmp)
                        palindromic = tmp
                    length += 1
            return palindromic
          
    solu = Solution()
    str1 = "babad"
    print(solu.longestPalindrome(str1))

# 6 ZigZag Conversion #

一道将字符串做之字形排列的题目.我们用n表示行数,将排列后得到的字符串分为完整竖列和折线两部分.每个完整竖列有n个数,每两个完整竖列之间的折线有n-2列,每列一个数,因此每两个完整竖列中同一行的数的间隔是n+n-2=2n-2.同时我们发现,除了第一行和最后一行之外的第i行都有折线,第i行的第一个折线是第2n-i个数.于是可以遍历输出每一行,判定条件是这一行我们要输出的数字是否超出了字符串的长度

class Solution:
        def convert(self, s, numRows):
            """
            :type s: str
            :type numRows: int
            :rtype: str
            """
            zigzag = ''
            
            if numRows == 1 or numRows == 0 or numRows >=len(s):
                return s
            
            space = 2*numRows-2
            for i in range(1, numRows+1):
                n=0
                if i==1 or i==numRows:
                    while i+n*space <= len(s):
                        zigzag += s[i+n*space-1]
                        n+=1
                else:
                    while i+n*space <= len(s):
                        zigzag += s[i+n*space-1]
                        if (2*numRows-i) + (n*space) <= len(s):
                            zigzag += s[(2*numRows-i)+(n*space)-1]
                        n+=1
                        
            return  zigzag

# 7 Reverse Integer 将给定的数字倒序输出. #

class Solution(object):
        def reverse(self, x):
            """
            :type x: int
            :rtype: int
            """
            tmp = abs(x)
            
            sum = 0
            while tmp > 0:
                sum = sum*10 + tmp%10
                tmp = tmp // 10
                
            sum = sum if x >=0 else -sum
            
            return sum if sum<2**31 and sum>-2**31 else 0

# 8 String to Integer(atoi) #

将给定字符串中符合条件的一串数字字符转化为int类型返回.我的思路是设定标志位start=0和符号位sign,遍历字符串,当start=0时遇到空格则continue,遇到+则记录sign=1,遇到-则记录sign=-1,遇到数字则记录数字;当strat=1时代表已经找到了第一个数字或符号位,此时遇到除数字之外的字符都break,遇到数字则继续记录数字.注意我们得到的整数值不能超过INT\_MAX和INT\_MIN.后来发现其实用str.strip()函数来去除字符串头尾的空格会更方便

class Solution(object):
        def myAtoi(self, str):
            """
            :type str: str
            :rtype: int
            """
            
            ans = 0
            start = 0
            sign = 0
            if str.isspace() is True:
                print(0)
            for i in str:
                if start == 0:
                    if i.isspace() is True:
                        continue
                    if i == '+':
                        sign = 1
                    elif i == '-':
                        sign = -1
                    elif i.isdigit() is True:
                        sign = 1
                        ans = ans*10 + int(i)
                    else:
                        break
                    start = 1
                else:
                    if i.isdigit() is True:
                        ans = ans*10+int(i)
                    else:
                        break
                        
            ans = sign*ans
            if ans >= 2147483647:
                return 2147483647
            elif ans <= -2147483648:
                return -2147483648
            
            return ans

# 9 Palindrome Number #

判断一个数字是否是回文数.题目要求不能用额外的空间,否则可以利用python的字符串切片轻松解决.我的思路是求出该整数的位数,判断第一位数和最后一位数是否相同,如果相同则将位数/100,然后将原数字的首尾两个数删除,最后如果位数<1说明是回文数.

def isPalindrome( x):
        """
        :type x: int
        :rtype: bool
        """
    
        if x<0:
            return False
    
        high = 1
        while x/high >= 10:
            high *= 10
        print(high)    
        
        while x // high == x%10:
            x = x%high//10
            print(x)
            high /= 100
            print(high)
            if high < 1:
                return True
    
        return False

# 10 正则表达式匹配 #

给定一个字符串 (s) 和一个字符模式 §。实现支持 ‘.’ 和 ‘\*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符。 ‘\*’ 匹配零个或多个前面的元素。 匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 \*。 示例 1:

输入: s = “aa” p = “a” 输出: false 解释: “a” 无法匹配 “aa” 整个字符串。 示例 2:

输入: s = “aa” p = “a” 输出: true 解释: ‘’ 代表可匹配零个或多个前面的元素, 即可以匹配 ‘a’ 。因此, 重复 ‘a’ 一次, 字符串可变为 “aa”。

if len(p) == 0: return len(s) == 0
            
            if len(p) == 1:
                return len(s) == 1 and (s[0] == p[0] or p[0] == '.')
            
            if p[1] != '*':
                if len(s) == 0: return False
                return (s[0] == p[0] or p[0] == '.') and self.isMatch(s[1:], p[1:])
            
            while (len(s) != 0 and (s[0] == p[0] or p[0] == '.')):
                if self.isMatch(s,p[2:]): 
                    return True
                s=s[1:]
                
            return self.isMatch(s,p[2:])

执行用时 :2056 ms, 在所有Python提交中击败了7.75%的用户  
内存消耗 :11.6 MB, 在所有Python提交中击败了41.60%的用户

# 11.求其中两条直线与x轴围成的容器的最大容量. #

Container With Most Water 给定许多条与y轴平行的直线,求其中两条直线与x轴围成的容器的最大容量.

这道题用到了双指针的思想.我们在数轴的两端分别放置一个left指针和right指针,因为容器容量=较短边\*两边位置之差,所以如果移动较大的那个指针,那么容量必定在减小.因此我们不断往中间移动较小的指针才有可能使容量变大,直到两指针相遇为止.

对于算法合理性的逻辑推理:我们假设在best\_left和best\_right位置取到最大容量,那么left指针到达best\_left位置或right指针到达best\_right位置至少有一种会发生.不妨令left指针到达best\_left位置,此时right指针的位置有三种可能:

位于best\_right位置左侧.这说明best\_right位置已经被计算过,成立. 位于best\_right位置,同上. 位于best\_right位置右侧.因为left指针移动的条件是right指针所在边大于left指针所在边,如果符合此条件,且right指针在best\_right右侧,那么当前容量一定大于假设中的最大容量,与假设矛盾.所以left指针必定会一路移动至best\_right位置.

class Solution(object):
        def maxArea(self, height):
            """
                :type height: List[int]
                :rtype: int
                """
            left = 0
            right = len(height) - 1
    
            maxArea = 0
            while left != right:
                h = min(height[left], height[right])
                maxArea = max(maxArea, h * (right-left))
    
                if height[left] < height[right]:
                    left += 1
                else:
                    right -= 1
    
            return maxArea

执行用时 :144 ms, 在所有Python提交中击败了55.27%的用户  
内存消耗 :13.2 MB, 在所有Python提交中击败了8.60%的用户

# 12.Integer to Roman #

将十进制数字转化为罗马数字.比较简单的一道题.我的思路是判断当前位数,改变代表1/5/10的字符然后逐位输出.也可以直接将每位上的各种字符表示存在列表里,然后直接取出.

def intToRoman(num):
        """
        :type num: int
        :rtype: str
        """
        
        carry = 1
        roman = ''
        
        while num!= 0:
            n = num % 10
            num //= 10
            if carry == 1:
                numeral_1 = 'I'
                numeral_5 = 'V'
                numeral_10 = 'X'
            elif carry == 10:
                numeral_1 = 'X'
                numeral_5 = 'L'
                numeral_10 = 'C'
            elif carry == 100:
                numeral_1 = 'C'
                numeral_5 = 'D'
                numeral_10 = 'M'
            else:
                numeral_1 = 'M'
                numeral_5 = ''
                numeral_10 = ''
                
            if 1<= n <=3:
                roman = numeral_1*n + roman
            elif n==4:
                roman = numeral_1+numeral_5 + roman
            elif 5<=n<=8:
                roman = numeral_5 + numeral_1*(n-5)+roman
            elif n==9:
                roman = numeral_1+numeral_10+roman
                
            carry *= 10
            
        return roman
                
    intToRoman(48)

执行用时 :32 ms, 在所有Python提交中击败了97.90%的用户  
内存消耗 :11.7 MB, 在所有Python提交中击败了33.80%的用户

# 13.Roman to Integer #

将罗马数字转化为十进制数字.非常无聊的一道题.比较简单的方法是写非常多的if语句来判断,或者将罗马数字与对应的十进制数字存入字典来转换.下面是我在discuss里看到的一个方案,巧妙利用了罗马数字"大数前面的小数用来减,大数后面的小数用来加"这个特点.

def romanToInt( s):
        """
        :type s: str
        :rtype: int
        """
        roman_map = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
        }
        
        
        result = 0
        last_num = None
        for char in s:
            current_num = roman_map[char]
            if last_num is None or last_num >= current_num:
                result += current_num
            elif last_num < current_num:
                result += current_num - 2 * last_num
            last_num = current_num
        return result
    
    
    romanToInt('XLVIII')

执行用时 :52 ms, 在所有Python提交中击败了85.13%的用户  
内存消耗 :11.6 MB, 在所有Python提交中击败了32.99%的用户

# 14.Longest Common Prefix #

找最长公共前缀字符串.我的思路是找出列表中最短的字符串,然后对最短字符串的每个字符都在列表中遍历,直到出现不同或者遍历结束为止.在discuss里看到很多方法利用了python中的sort(),min(),max()这些内置方法对字符串排序,会使时间快很多.

def longestCommonPrefix( strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        
        prefix = ''
        
        if strs == []:
            return prefix
        
        mininum = float("inf")
        for s in strs:
            mininum = min(len(s), mininum)
            
        print(mininum)
            
        i=0
        for j in range(mininum):
            for i in range(len(strs)):
                while strs[i][j] != strs[0][j]:
                    print(prefix)
                    return prefix
            prefix = prefix + strs[0][j]
            
        return prefix
    
    T = ['abc','abcd','abfg','abopfge']
    longestCommonPrefix( T)

执行用时 :40 ms, 在所有Python提交中击败了25.81%的用户  
内存消耗 :11.9 MB, 在所有Python提交中击败了23.86%的用户

# 15.3Sum #

给定一个数组,找到其中三个数的和为零的所有可能,以列表形式返回.这道题的基本思路是先将数组排序,从左往右遍历一次.在遍历每个数的过程中设立两个指针,如果三个数的和大于零则左移右指针,如果三个数的和小于零则右移左指针,直到两个指针相遇.注意我们用的是set()来存储找到的结果,可以避免list中出现重复.在此基础上,我增加了一个对排序过的数组的操作,即当最左边两个数与最右边一个数的和大于零时删去最右边的数,当最左边一个数与最右边两个数的和小于零时删去最左边的数.这个操作大大提升了运行速度.

def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        zeros = set()
        nums.sort()
        
        if len(nums) < 3:
            return []
        
        if nums.count(0) > len(nums) -2:
            return [[0,0,0]]
        
        while len(nums) > 3 and (nums[0] + nums[1] + nums[-1] > 0 or nums[-1]+nums[-2]+nums[0] < 0):
            if nums[0] + nums[1] + nums[-1] > 0 :
                nums.remove(nums[-1])
            else:
                nums.remove(nums[0])
                
        for i in range(len(nums)-2):
            if nums[i] > 0:
                break
            j = i+1
            k = len(nums) -1
            while j < k:
                sum = nums[i] + nums[j] + nums[k]
                if sum == 0:
                    zeros.add((nums[i], nums[j], nums[k]))
                    j += 1
                    continue
                elif sum < 0:
                    j += 1
                else:
                    k -= 1
                    
        return list(map(list,zeros))

执行用时 :1044 ms, 在所有Python提交中击败了21.21%的用户  
内存消耗 :16.9 MB, 在所有Python提交中击败了5.55%的用户

# 16.3Sum Closest #

给定一个数组和一个目标值,找到数组中的三个数,使得这三个数之和与目标值之间的差距最小,返回它们的和.

这题的思路与15题类似,也是利用双指针,只不过判定条件从三个数之和是否为零改成了三个数之和是

否比目前已有的closest值更接近目标

def threeSum(self, nums, target):
        """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
        
        closest = nums[0] + nums[1] + nums[2]
        nums.sort()
        length = len(nums)
        for i in range(length):
            l = i+1
            r = length - 1
            while l < r:
                tmp = nums[i] + nums[l] + nums[r]
                if tmp == target:
                    closest = target
                    break
                elif tmp < target:
                    if target - tmp < abs(target - closest):
                        closest = tmp
                    l += 1
                elif tmp > target:
                    if tmp - target < abs(target - closest):
                        closest = tmp;
                    r -= 1
        return closest

# 17 电话号码的字母组合 #

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

\[外链图片转存失败(img-SdYneUnS-1566218841880)(attachment:image.png)\]

示例:

输入：“23”  
输出：\[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”\].

class Solution(object):
        def letterCombinations(self, digits):
            """
            :type digits: str
            :rtype: List[str]
            """
            
            if not digits:
                return []
            
            digit2char = {
                '2':'abc',
                '3':'def',
                '4':'ghi',
                '5':'jkl',
                '6':'mno',
                '7':'pqrs',
                '8':'tuv',
                '9':'wxyz',
            }
            
            res = [ i for i in digit2char[digits[0]] ]
            
            result = []
            for i in digits[1:]:
                for m in res:
                    for n in digit2char[i]:
                        res = m+n
                        result.append(res)
                        #print(res)
                        
            return result
            
            
    solu =  Solution()
    tmp = '23'
    print(solu.letterCombinations(tmp))

# 18.4Sum 找出list中所有相加等于target的4个数的list. #

一开始我的思路是令new\_target=target-num1,然后转换为一个3Sum问题,但这种做法的时间复杂度太高了.查看Solution后发现这道题要使用hash的思想,在python中对应的实现就是使用先dict存储list中的两数之和和它们在list中的位置,然后对于这个dict中的value,寻找一个key=target-value,然后将他们对应的数字存入list即可.需要注意的是python中的list,set,dict是不可哈希的,int,float,str,tuple是可哈希的.

def fourSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            d = dict()
            
            for i in range(len(nums)):
                for j in range(i+1, len(nums)):
                    sum2 = nums[i] + nums[j]
                    if sum2 in d:
                        d[sum2].append((i,j))
                    else:
                        d[sum2] = [(i,j)]
                        
            result = []
            for key in d:
                value = target - key
                if value in d:
                    list1 = d[key]
                    list2 = d[value]
                    for(i,j) in list1:
                        for(m,n) in list2:
                            if i != m and i != n and j != m and j != n:
                                flist = [nums[i], nums[j],nums[m],nums[n]]
                                flist.sort()
                                if flist not in result:
                                    result.append(flist)
            return result

# 19 删除链表的倒数第N个节点 #

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

# Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def removeNthFromEnd(self, head, n):
            """
            :type head: ListNode
            :type n: int
            :rtype: ListNode
            """
            res = ListNode(0)
            res.next = head
            list1 = res
            list2 = res
            for i in range(n):
                list1 = list1.next
            while list1.next:
                list1 = list1.next
                list2 = list2.next
            list2.next = list2.next.next
            return res.next

# 20 有效的括号 #

给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1:

输入: “()” 输出: true 示例 2:

输入: “()\[\]\{\}” 输出: true

class Solution(object):
        def isValid(self, s):
            """
            :type s: str
            :rtype: bool
            """
            result = []
            
            samples = ['[]','{}','()']
            
            for i in range(len(s)):
                result.append(s[i])
                
                if len(result) >= 2 and result[-2] + result[-1] in samples:
                    result.pop()
                    result.pop()
                    
                    
            return len(result) == 0
            
    solu = Solution()
    ss = "{
       {[}]}"
    
    print(solu.isValid(ss))