“【Leetcode】15-21"
[toc]
15. [Array] 3Sun
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]
]
python solution:
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
r = []
if len(nums)<3:
return r
l = sorted(nums)
for i in range(len(nums)):
if l[i]>0:
return r
if i>0 and l[i] == l[i-1]:
continue
L = i+1
R = len(nums)-1
while L<R:
if l[i]+l[L]+l[R] == 0:
r.append([l[i],l[L],l[R]])
while L<R and l[L]==l[L+1]:
L +=1
while L<R and l[R]==l[R-1]:
R -=1
L +=1
R -=1
elif l[i]+l[L]+l[R]<0:
L +=1
else:
R -= 1
return r
16. [Array]3Sum Closest
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
python solution :
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
n = len(nums)
closest = float('inf')
l = sorted(nums)
for i in range(n):
L = i+1
R = n-1
while L < R:
if abs(target-(l[i]+l[L]+l[R]))<abs(target-closest):
closest = l[i]+l[L]+l[R]
if L<R and l[i]+l[L]+l[R] < target:
L += 1
else:
R -= 1
return closest
18. [Array] 4Sum
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target Note:The solution set must not contain duplicate quadruplets.
Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
python solution 1:
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
r = []
if len(nums)<4:
return r
c_nums = sorted(nums)
for j in range(len(c_nums)):
if j>0 and c_nums[j]==c_nums[j-1]:
continue
c_target = target - c_nums[j]
l = c_nums[j+1:len(c_nums)]
for i in range(len(l)):
if i>0 and l[i] == l[i-1]:
continue
L = i+1
R = len(l)-1
while L<R:
if l[i]+l[L]+l[R] == c_target:
r.append([c_nums[j],l[i],l[L],l[R]])
while L<R and l[L]==l[L+1]:
L +=1
while L<R and l[R]==l[R-1]:
R -=1
L +=1
R -=1
elif l[i]+l[L]+l[R]<c_target:
L +=1
else:
R -= 1
return r
Note:
类似于3Sum这道题,需要注意的是第8行和第13行的去重
python solution 2
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len(nums)
if n < 4: return []
nums.sort()
res = []
for i in range(n-3):
# 防止重复 数组进入 res
if i > 0 and nums[i] == nums[i-1]:
continue
# 当数组最小值和都大于target 跳出
if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
break
# 当数组最大值和都小于target,说明i这个数还是太小,遍历下一个
if nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target:
continue
for j in range(i+1,n-2):
# 防止重复 数组进入 res
if j - i > 1 and nums[j] == nums[j-1]:
continue
# 同理
if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
break
# 同理
if nums[i] + nums[j] + nums[n-1] + nums[n-2] < target:
continue
# 双指针
left = j + 1
right = n - 1
while left < right:
tmp = nums[i] + nums[j] + nums[left] + nums[right]
if tmp == target:
res.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 tmp > target:
right -= 1
else:
left += 1
return res
Note:
此解题方式是先固定两个值,一步一步缩小范围,再进行判断,时间上比上一种方法快了10倍以上
20. Valid Parentheses
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
python solution
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
# The stack to keep track of opening brackets.
stack = []
# Hash map for keeping track of mappings. This keeps the code very clean.
# Also makes adding more types of parenthesis easier
mapping = {")": "(", "}": "{", "]": "["}
# For every bracket in the expression.
for char in s:
# If the character is an closing bracket
if char in mapping:
# Pop the topmost element from the stack, if it is non empty
# Otherwise assign a dummy value of '#' to the top_element variable
top_element = stack.pop() if stack else '#'
# The mapping for the opening bracket in our hash and the top
# element of the stack don't match, return False
if mapping[char] != top_element:
return False
else:
# We have an opening bracket, simply push it onto the stack.
stack.append(char)
# In the end, if the stack is empty, then we have a valid expression.
# The stack won't be empty for cases like ((()
return not stack
note:
- 选择运算符:
在C或Java中选择运算符的格式一般为判断式?变量1:变量2,而python中则为变量1 if 判断式 else 变量2