LeetCode高频100【0】

目录

【0】

	#	Title	Acceptance	Difficulty
	1	Two Sum	40.2%	Easy
	2	Add Two Numbers	30.4%	Medium
	3	Longest Substring Without Repeating Characters	26.1%	Medium
	4	Median of Two Sorted Arrays	25.3%	Hard
	5	Longest Palindromic Substring	26.4%	Medium
	10	Regular Expression Matching	24.9%	Hard
	11	Container With Most Water	42.1%	Medium
	15	3Sum	23.2%	Medium
	17	Letter Combinations of a Phone Number	40.1%	Medium
	19	Remove Nth Node From End of List	33.9%	Medium

1. Two Sum （Easy）

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

# 考察数组和哈希表（哈希表即python中的[字典]）
# Approach 3: One-pass Hash Table ,T(n)=O(n), S(n)=O(1)
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i, num in enumerate(nums):
            if target - num in dic:
                return [dic[target - num], i]
            dic[num] = i      

2. Add Two Numbers（Medium）

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

# 考察数学和单链表
# Approach 1: Elementary Math, T(n)=O(max(m,n)), S(n)=O(max(m,n))

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        l3 = head = ListNode(-1)
        k = 0
        while l1 and l2:
            l3.next =  ListNode((l1.val+l2.val+k)%10)
            k = (l1.val+l2.val+k)//10
            l1,l2,l3 = l1.next,l2.next,l3.next
        res = l1 or l2
        while res:
            l3.next = ListNode((res.val+k)%10)
            k = (res.val+k)//10
            res,l3 = res.next,l3.next
        if k:
            l3.next = ListNode(k)
        return head.next   

3. Longest Substring Without Repeating Characters（Medium）

Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

# 考察 双指针 字符串 哈希表
# Approach 3: Sliding Window Optimized, T(n)=O(n), S(n)=O(n)
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        start,ans = 0,0
        for i,item in enumerate(s):
            if item in dic:
                start = max(start,dic[item]+1)
            dic[item] = i
            ans = max(ans,i-start+1)
        return ans

4. Median of Two Sorted Arrays（Hard）

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

# 考察 数组、二分查找、分治算法
# Approach 1: Recursive Approach，T(n)=O(log(min(m,n))), S(n)=O(1)
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1),len(nums2)
        if m>n:
            nums1,nums2,m,n=nums2,nums1,n,m
        if n==0:
            raise ValueError
        imin,imax=0,m
        while imin<=imax:
            i = (imin+imax)//2
            j = (m+n+1)//2 - i
            if i<m and nums2[j-1]>nums1[i]:
                # i is too small,must increase it
                imin=i+1
            elif i>0 and nums1[i-1]>nums2[j]:
                # i is too big
                imax=i-1
            else:
                if i==0:
                    maxleft=nums2[j-1]
                elif j==0:
                    maxleft=nums1[i-1]
                else:
                    maxleft=max(nums1[i-1],nums2[j-1])
                if (m+n)%2==1:
                    return maxleft/1.0
                if i==m:
                    minright=nums2[j]
                elif j==n:
                    minright=nums1[i]
                else:
                    minright=min(nums1[i],nums2[j])
                return (maxleft+minright)/2.0
        
# Approach 2: 暴力遍历，T(n)<=O(m+n)，，，太慢
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums=[]
        while nums1 and nums2:
            if nums1[0]<nums2[0]:
                nums.append(nums1[0])
                del nums1[0]
            else:
                nums.append(nums2[0])
                del nums2[0]
        nums.extend(nums1 or nums2)
        if len(nums)%2:
            return nums[len(nums)//2]/1.0
        else:
            return (nums[len(nums)//2]+nums[len(nums)//2-1])/2.0 

5. Longest Palindromic Substring（Medium）

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

# 考察 字符串、动态规划
# 第一种时间复杂度太高。。。第二种来自官版4-java

# Approach 1：we could solve it in O(n^2) time using only constant space.
class Solution:
    def longestPalindrome(self, s: str) -> str:
        ans = ""
        for left in range(len(s)):
            for right in range(len(s),left,-1):
                if len(ans)>right-left:
                    break
                elif s[left:right]==s[left:right][::-1]:
                    ans = s[left:right]
                    break
        return ans

/**
In fact, We observe that a palindrome mirrors around its center. 
Therefore, a palindrome can be expanded from its center,
and there are only 2n - 1 such centers.
You might be asking why there are 2n - 1 but not n centers? 
The reason is the center of a palindrome can be in between two letters. 
Such palindromes have even number of letters (such as "abba") 
and its center are between the two 'b's.
*/
# Approach 2: Expand Around Center O(2n-1) 
class Solution:
    def longestPalindrome(self, s: str) -> str:
            start=end=0
            for i in range(len(s)):
                len1 = expandAround(s,i,i)
                len2 = expandAround(s,i,i+1)
                l = max(len1,len2)
                if l > end-start:
                    start = i-(l-1)//2
                    end = i+l//2
            return s[start:end+1]
    def expandAround(s:str,left:int,right:int) -> int:
        L,R = left,right
        while L>=0 and R<len(s) and s[L]==s[R]:
            L-=1
            R+=1
        return R-L-1

10. Regular Expression Matching（Hard）

Given an input string (s) and a pattern (p), implement regular expression matching with support for . and *.
. Matches any single character.
* Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *
Example :
Input:
s = "aa" p = "a"
Output: false

Approach 1: Recursion

If a star is present in the pattern, it will be in the second position pattern[1]. Then, we may ignore this part of the pattern, or delete a matching character in the text. If we have a match on the remaining strings after any of these operations,then the initial inputs matched.

# Hard
# 考察 字符串 动态规划 回溯算法
# Approach 1: Recursion
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p:
            return not s
        first_match = bool(s) and p[0] in {s[0], '.'}
        if len(p) >= 2 and p[1] == '*':
            return (self.isMatch(s, p[2:]) or \
                    first_match and self.isMatch(s[1:], p))
        else:
            return first_match and self.isMatch(s[1:], p[1:])

Approach 2: Dynamic Programming
Intuition
As the problem has an optimal substructure, it is natural to cache intermediate results. We ask the question dp(i, j): does text[i:] and pattern[j:] match? We can describe our answer in terms of answers to questions involving smaller strings.
Algorithm
We proceed with the same recursion as in Approach 1, except because calls will only ever be made to match(text[i:], pattern[j:]), we use dp(i, j) to handle those calls instead, saving us expensive string-building operations and allowing us to cache the intermediate results.

# Top-Down Variation
def isMatch(s, p):
    memo = {}
    def dp(i, j):
        if (i, j) not in memo:
            if j == len(p):
                ans = i == len(s)
            else:
                first_match = i < len(s) and p[j] in {s[i], '.'}
                # If a star is present in the pattern, 
                # it will be in the second position pattern[1]. 
                # Then, we may ignore this part of the pattern, 
                # or delete a matching character in the text. 
                if j+1 < len(p) and p[j+1] == '*':
                    ans = dp(i, j+2) or first_match and dp(i+1, j)
                else:
                    ans = first_match and dp(i+1, j+1)
            # cache intermediate results
            memo[i, j] = ans
        return memo[i, j]
    return dp(0, 0)

11. Container With Most Water（Medium）

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49

# Approach 1: Brute Force T(n)=O(n^2), S(n)=O(1)
class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans,n = 0,len(height)
        if n<2:
            return ans
        for i in range(n):
            for j in range(i,n):
                h=min(height[i],height[j])
                ans=max(ans,h*(j-i))
        return ans

# Approach 2: Two Pointer Approach T(n)=O(n), S(n)=O(1)
# Runtime: 64 ms, faster than 73.30% 
class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans,l,r = 0,0,len(height)-1
        if r<1:
            return ans
        while l<r:
            h=min(height[l],height[r])
            ans=max(ans,h*(r-l))
            if height[l] < height[r]:
                l+=1
            else:
                r-=1
        return ans

15. 3Sum（Medium）

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

# Approach: Two Pointer Approach, T(n)=O(n^2), S(n)=O(n)
# Runtime: 700 ms, faster than 91.69%
/** 
For time complexity，Sorting takes O(NlogN)
We iterate through the 'nums' once,
and each time we iterate the whole array again by a while loop
So it is O(NlogN+N^2)~=O(N^2)

For space complexity
We didn't use extra space except the 'res'
Since we may store the whole 'nums' in it
So it is O(N)
N is the length of 'nums'
**/
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans=[]
        for i,a in enumerate(nums):
            if nums[i]>0: 
                break
            if i>0 and nums[i]==nums[i-1]: 
                continue
            target,l,r = 0-a,i+1,len(nums)-1
            while l<r:
                if nums[l]+nums[r]<target:
                    l+=1
                elif nums[l]+nums[r]>target:
                    r-=1
                else:
                    ans.append([a,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
        return ans

17. Letter Combinations of a Phone Number（Medium）

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

# Approach 1: Backtracking, T(n)=O(3^N*4^M), O(n)=O(3^N*4^M)
# Time complexity : O(3^N*4^M) 
# N is the number of digits in the input that maps to 3 letters (e.g. 2,3,4,5,6,8) 
# M is the number of digits in the input that maps to 4 letters (e.g. 7,9), 
# N+M is the total number digits in the input.
# Space complexity :O(3^N * 4^M)since one has to keep 3^N*4^M solutions.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phone={'2':'abc',
         '3':'def',
         '4':'ghi',
         '5':'jkl',
         '6':'mno',
         '7':'pqrs',
         '8':'tuv',
         '9':'wxyz'}
        ans=[]
        def backtrack(combination,digits):
            # if there is no more digits to check
            if len(digits)==0:
                # the combination is done
                ans.append(combination) # 每条路径停止条件
            else:
                for letter in phone[digits[0]]: # 深度搜索
                    backtrack(combination+letter,digits[1:])
        if digits:
            backtrack("",digits)
        return ans

19. Remove Nth Node From End of List（Medium）

Given a linked list, remove the n-th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:Given n will always be valid.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Approach 0: my solution ,T(n)=O(L), S(n)=O(1)
# Runtime: 36 ms, faster than 99.26% of Python3
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        len=0
        p=q=head
        while p:
            len+=1
            p=p.next
        left=len-n
        # if del the first node
        if left==0:
            return head.next
        while left>1:
            left-=1
            q=q.next
        q.next=q.next.next
        return head

# Approach 1: Two pass algorithm,T(n)=O(L), S(n)=O(1)
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # compute the length of list
        len,p = 0,head
        while p:
            len+=1
            p=p.next
        left=len-n
        # consider removing the first node
        dummy=ListNode(0)
        dummy.next=head
        p=dummy
        # move to the target node
        while left>0:
            left-=1
            p=p.next
        # delete the target node
        p.next=p.next.next
        return dummy.next
    
# Approach 2: One pass algorithm, use two pointer , T(n)=O(L), S(n)=O(1)
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0);
        dummy.next = head;
        p=q=dummy
        # maintaining n nodes between p and q
        while n>=0:
            p=p.next
            n-=1
        while p:
            p=p.next
            q=q.next
        q.next=q.next.next
        return dummy.next