LeetCode day14
Diffculty: Medium
11. Container With Most Water
Topic: Array, Two Pointer
Given n non-negative integers a_1, a_2, …, a_n , where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) 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: 49Approach1
def maxArea(height: List[int]) -> int:
i, j, res = 0, len(height) - 1, 0
while i < j:
if height[i] < height[j]:
res = max(res, height[i] * (j - i))
i += 1
else:
res = max(res, height[j] * (j - i))
j -= 1
return res时间复杂度 O(N)，双指针遍历一次底边宽度 N 空间复杂度 O(1)，指针使用常数额外空间
15. 3Sum
Topic: Array, Two pointer
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]
]Approach1
- 特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []
- 对数组进行排序
遍历排序后数组：
- 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果
- 对于重复元素：跳过，避免出现重复解
令左指针 L=i+1，右指针 R=n-1，当 L<R 时，执行循环：
- 当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解. 并同时将 L,R 移到下一位置，寻找新的解
- 若和大于 0，说明 nums[R] 太大，R 左移
若和小于 0，说明 nums[L] 太小，L 右移
def threeSum(nums: List[int]) -> List[List[int]]: n=len(nums) res=[] if(not nums or n<3): return [] nums.sort() res=[] for i in range(n): if(nums[i]>0): return res if(i>0 and nums[i]==nums[i-1]): continue L=i+1 R=n-1 while(L<R): if(nums[i]+nums[L]+nums[R]==0): # 3sums == 0 res.append([nums[i],nums[L],nums[R]]) while(L<R and nums[L]==nums[L+1]): # 判断左界是否和下一位置重复，去除重复解. L=L+1 while(L<R and nums[R]==nums[R-1]): # 判断右界是否和下一位置重复，去除重复解. R=R-1 L=L+1 R=R-1 elif(nums[i]+nums[L]+nums[R]>0): # 3sums > 0 R=R-1 else: # 3sums < 0 L=L+1 return res
时间复杂度：O(n^2)，数组排序 O(nlogn)，遍历数组 O(n)，双指针遍历 O(n)，总体 (nlogn)+O(n)*O(n) => O(n^2) 空间复杂度：O(1)
Approach2
my, overtime
def threeSum(nums: List[int]) -> List[List[int]]:
if(not nums or len(nums)<3):
return []
nums.sort()
res = set()
for i in range(len(nums)-2):
remain1 = 0 - nums[i]
for j in range(i+1,len(nums)-1):
remain2 = remain1 - nums[j]
if remain2 in nums[j+1:]:
res.add((nums[i],nums[j],remain2))
return list(res)17. Letter Combinations of a Phone Number
Topic: String, Backtracking
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"].Note:
- Although the above answer is in lexicographical order, your answer could be in any order you want.
Approach1
def letterCombinations(digits: str) -> List[str]:
conversion = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
if len(digits)==0:
return []
product=['']
for k in digits:
product=[i+j for i in product for j in conversion[k]]
return productApproach2
题目中出现“所有组合”等类似字眼时，第一感觉就要想到用回溯.
def letterCombinations(digits: str) -> List[str]:
if not digits: return []
phone = {'2':['a','b','c'],
'3':['d','e','f'],
'4':['g','h','i'],
'5':['j','k','l'],
'6':['m','n','o'],
'7':['p','q','r','s'],
'8':['t','u','v'],
'9':['w','x','y','z']}
def backtrack(combination, nextdigit):
if len(nextdigit) == 0:
res.append(combination)
else:
for letter in phone[nextdigit[0]]:
backtrack(combination + letter, nextdigit[1:])
res = []
backtrack('',digits)
return res时间复杂度：O(3^M × 4^N). M 是对应三个字母的数字个数，N 是对应四个字母的数字个数 空间复杂度：O(3^M × 4^N). 一共要生成 3^M × 4^N个结果
19. Remove Nth Node From End of List
Topic: Linked list, Two pointer
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.
Follow up:
- Could you do this in one pass?
Approach1
my, 两次遍历, 第一次找到位置的index, 第二次找到位置并next.next
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
node = head
cnt = 0
while node:
node = node.next
cnt += 1
# print(cnt,'ori') # 5
cnt -= n+1 # 定位到要移除的前一个位置
# print(cnt,'aft') # 2
node = head
if cnt == -1:
head = head.next
else:
while cnt:
node= node.next
cnt -= 1
node.next = node.next.next
return headApproach2
recurrent
def removeNthFromEnd(head, n):
global i
if head is None:
i=0
return None
head.next = self.removeNthFromEnd(head.next,n)
i+=1
return head.next if i==n else headApproach3
翻转链表
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
node1=head
reverse1=None
#翻转链表
while node1:
temp=node1.next
node1.next=reverse1
reverse1=node1
node1=temp
node2=reverse1
#删除链表
if n==1:
reverse1=reverse1.next
elif n==2:
reverse1.next=reverse1.next.next
else:
for i in range(n-2):
node2=node2.next
node2.next=node2.next.next
reverse2=None
#把删除后的链表翻转回来
while reverse1:
temp=reverse1.next
reverse1.next=reverse2
reverse2=reverse1
reverse1=temp
return reverse2Approach4
双指针
- 定义一个头结点，指向链表的第一个结点
- 快慢指针指向头结点
- 快指针先走n步
- 快慢指针一起走，直到快指针走到链表尾
- 慢指针后一位连接为其后一位的后一位（实现截断连接）
返回头结点的后一位结点
def removeNthFromEnd(head: ListNode, n: int) -> ListNode: Node = ListNode(None) Node.next = head fast,slow = Node,Node for i in range(n): fast = fast.next while fast.next != None: fast = fast.next slow = slow.next slow.next = slow.next.next return Node.next