1 Two Sum
#Example:
#Given nums = [2, 7, 11, 15], target = 9,
#Because nums[0] + nums[1] = 2 + 7 = 9,
#return [0, 1].
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums)
result = []
mapping = {}
for i in range(n):
mapping[nums[i]] = i
for i in range(n):
gap = target - nums[i]
if (gap in mapping.keys()) and (mapping[gap] > i):
result.append(i)
result.append(mapping[gap])
break
return result
2 Add Two Numbers
#Example:
#Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
#Output: 7 -> 0 -> 8
#Explanation: 342 + 465 = 807.
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
res = []
cnt = 0
while l1 and l2:
value = l1.val + l2.val + cnt
if value >= 10:
cnt = 1
res.append(value % 10)
else:
cnt = 0
res.append(value)
l1 = l1.next
l2 = l2.next
if l1:
while l1:
if (l1.val + cnt) >= 10:
res.append((l1.val + 1) % 10)
cnt = 1
else:
res.append(l1.val + cnt)
cnt = 0
l1 = l1.next
elif l2:
while l2:
if (l2.val + cnt) >= 10:
res.append((l2.val + 1) % 10)
cnt = 1
else:
res.append(l2.val + cnt)
cnt = 0
l2 = l2.next
else:
if cnt == 1:
res.append(1)
return res
if cnt == 1:
res.append(1)
return res
3 Longest Substring Without Repeating Characters
#Example:
#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.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 维护 left right 以及一个 set
if len(s) == 0:
return 0
if len(s) == 1:
return 1
left, right = 0, 1
chars = set()
chars.add(s[0])
res = 1
while left < len(s) and right < len(s):
if s[right] in chars:
if s[left] in chars:
chars.remove(s[left])
left += 1
else:
chars.add(s[right])
right += 1
#res = max(res, right-left+1)
res = max(res, len(chars))
return res
4 Median of Two Sorted Arrays
#Example:
#nums1 = [1, 2]
#nums2 = [3, 4]
#The median is (2 + 3)/2 = 2.5
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 有一个数组为空
if len(nums1) == 0 and len(nums2) > 0:
return nums2[int(len(nums2)/2)] if len(nums2) % 2 == 1 else (nums2[int(len(nums2)/2)-1]+nums2[int(len(nums2)/2)])/2.0
if len(nums2) == 0 and len(nums1) > 0:
return nums1[int(len(nums1)/2)] if len(nums1) % 2 == 1 else (nums1[int(len(nums1)/2)-1]+nums1[int(len(nums1)/2)])/2.0
# 保证n > m
if len(nums1) > len(nums2):
return self.findMedianSortedArrays(nums2, nums1)
m, n = len(nums1), len(nums2)
imin, imax = 0, m
'''
用i,j分别将两个数组随机分成两部分(这里取中间)，nums1长度m,nums2为n
分别为nums1_left,nums1_right,nums2_left,nums2_right
我们再将nums1_left,nums2_left归为nums_left
将nums1_right,nums2_right归为nums_right
只要我们确保：
1.len(nums_left) = len(nums_right)
2.max(nums_left) <= min(nums_right)
那么中值就为:(max(nums_left)+min(nums_left))/2
为了满足条件1，需使得i+j = m-i+n-j+1 则 j = (m+n+1)/2
为了满足条件2，需使得：
nums1[i-1] <= nums2[j]
nums2[j-1] <= nums1[i]
所以，我们只要找到满足条件的i的位置即可
'''
while imin <= imax:
i = int((imin+imax)/2)
j = int((m+n+1)/2) - i
# i太小增加i
if i < m and j > 0 and nums1[i] < nums2[j-1]:
imin = i + 1
# i太大减少i
elif i > 0 and j < n and nums1[i-1] > nums2[j]:
imax = i-1
else:
# i或j为边界值
if (i == 0):
max_left = nums2[j-1]
elif (j == 0):
max_left = nums1[i-1]
else:
max_left = nums1[i-1] if nums1[i-1] > nums2[j-1] else nums2[j-1]
break
# 数组大小和奇数
if (m+n) % 2 == 1:
return max_left
if i == m:
min_right = nums2[j]
elif j == n:
min_right = nums1[i]
else:
min_right = nums1[i] if nums1[i] < nums2[j] else nums2[j]
return (max_left+min_right)/2.0
5 Longest Palindromic Substring
#最长回文子串 暴力求解
class Solution:
def longestPalindrome(self, s):
res = ''
for i in range(len(s)):
# odd
tmp = self.helper(s, i, i)
if len(tmp) > len(res):
res = tmp
# even
tmp = self.helper(s, i, i+1)
if len(tmp) > len(res):
res = tmp
return res
def helper(self, s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return s[l+1:r]
# manacher算法
6 ZigZag Conversion
class Solution:
def convert(self, s: str, numRows: int) -> str:
#(1)第一行和最后一行下标间隔都是interval = n*2-2 = 8
#(2)中间行的间隔是周期性的,第i行的间隔是: interval–2*i, 2*i, interval–2*i, 2*i, interval–2*i, 2*i
if numRows == 1:
return s
length = len(s)
interval = numRows*2 - 2
k = 0
res = []
for j in range(0, length, interval):
res.append(s[j])
#print('第一行',res)
for i in range(1, numRows-1):
inter = 2 * i
j = i
while j < length:
res.append(s[j])
inter = interval - inter
j += inter
#for j in range(i, length, interval - inter):
#res.append(s[j])
#print('中间行',res)
for j in range(numRows-1, length, interval):
res.append(s[j])
#print('最后行',res)
return ''.join(res)
11 Container With Most Water
image
#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.
class Solution:
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
l = 0
r = len(height)-1
max_value = 0
tmp = 0
while l<r :
tmp = min(height[l], height[r]) * (r-l)
max_value = max(tmp, max_value)
if min(height[l], height[r]) == height[l]:
l += 1
else:
r -= 1
return max_value
15 3Sum
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
if len(nums) < 3:
return result
nums.sort()
for i in range(len(nums)-2):
j = i+1
k = len(nums) - 1
if i>=1 and nums[i] == nums[i-1]:
continue
while j < k:
if nums[i] + nums[j] + nums[k] > 0:
k -= 1
while k>j and nums[k] == nums[k+1]:
k -= 1
elif nums[i] + nums[j] + nums[k] < 0:
j += 1
while k>j and nums[j] == nums[j-1]:
j += 1
else:
result.append([nums[i],nums[j],nums[k]])
j += 1
k -= 1
while k>j and nums[j] == nums[j-1] and nums[k] == nums[k+1]:
j += 1
return result
16 3Sum Closest
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
if len(nums) < 3:
return []
nums=sorted(nums)
triple=nums[0]+nums[1]+nums[-1]
diff = abs(triple - target)
for i in range(0, len(nums)-2):
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
d = abs(s - target)
if d < diff:
diff = d
triple = s
if s == target:
return target
elif s < target:
l += 1
else:
r -= 1
return triple
18 4Sum
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if len(nums) < 4:
return []
res = []
nums = sorted(nums)
twosum = dict()
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
sum_ = nums[i] + nums[j]
pairs = (i, j)
if sum_ not in twosum.keys():
twosum[sum_] = []
twosum[sum_].append(pairs)
for key in twosum.keys():
listA = twosum[key]
if (target - key) in twosum.keys():
listB = twosum[target - key]
if listA != [] and listB != []:
for pairA in listA:
a0 = pairA[0]
a1 = pairA[1]
for pairB in listB:
b0 = pairB[0]
b1 = pairB[1]
if a1 < b0:
tmp = [nums[a0], nums[a1], nums[b0], nums[b1]]
if tmp not in res:
res.append(tmp)
return res
31 Next Permutation
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 从尾部向前寻找升序序列， 并把最后一个的前一个标记为partition；
# 然后再从尾端寻找另一个大于partition的元素，并与partition指向的元素交换，
#然后将partition后的元素（不包括partition指向的元素）逆序排列
if len(nums) == 1:
return
partition = -1
for i in range(len(nums)-2, -1, -1):
if nums[i] < nums[i+1]:
partition = i
break
if partition == -1:
nums.reverse()
return
else:
for i in range(len(nums)-1, partition, -1):
if nums[i] > nums[partition]:
nums[i],nums[partition] = nums[partition],nums[i]
break
left = partition+1; right = len(nums)-1
while left < right:
nums[left],nums[right] = nums[right],nums[left]
left+=1; right-=1
return
33 Search in Rotated Sorted Array
#You may assume no duplicate exists in the array.
class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums)-1
while l <= r:
mid = (l+r)//2
if nums[mid] == target:
return mid
if nums[mid] < nums[r]:
if nums[mid] < target and target <= nums[r]:
l = mid + 1
else:
r = mid - 1
else:
if nums[mid] > target and target >= nums[l]:
r = mid - 1
else:
l = mid + 1
return -1
41 First Missing Positive
'''
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
'''
class Solution:
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
self.bucket_sort(nums)
for i in range(len(nums)):
if nums[i] != i + 1:
return i + 1
return len(nums) + 1
def bucket_sort(self, A):
n = len(A)
for i in range(n):
while A[i] != i + 1:
if A[i] <= 0 or A[i] > n or A[i] == A[A[i] - 1]:
break
A[i], A[A[i] - 1] = A[A[i] - 1], A[i]
42 Trapping Rain Water
image
'''
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1].
In this case, 6 units of rain water (blue section) are being trapped.
'''
class Solution:
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
lmax = 0
dp = [0] * n
for i in range(n):
dp[i] = lmax
lmax = max(lmax, height[i])
rmax = 0
res = 0
for i in range(n-1, -1, -1):
dp[i] = min(rmax, dp[i])
rmax = max(rmax, height[i])
if dp[i] > height[i]:
res += dp[i] - height[i]
return res
'''
基于以上的理解，我们就可以使用动态规划的思路，将每一个位置点左侧的最大高
度存起来，然后将每个位置点右侧的最大高度存起来，这样，该位置的最大存水量
为min(maxleft[i], maxright[i])-height[i] 得到，最后将所有位置相加即可，为了提高空
间复杂度方面的性能，我们只需要将所有位置对应的左侧最大高度存在一个数组
中，然后每算出一个右侧最大高度，就将该位置对应的存水量算出来，接着进行下
一位的计算。
'''
50 Pow(x, n)
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1.0
if n < 0:
x = 1/x
n = abs(n)
y = x * x
return self.myPow(y, n//2) if n%2==0 else x * self.myPow(y, n//2)
53 Maximum Subarray
class Solution:
def maxSubArray(self, nums: 'List[int]') -> 'int':
if not nums:
return 0
curSum = 0
maxSum = nums[0]
for num in nums:
if curSum < 0:
curSum = 0
curSum += num
maxSum = max(maxSum, curSum)
return maxSum
81 Search in Rotated Sorted Array II
'''
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
'''
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
n = len(nums)
begin = 0
end = n - 1
while begin <= end:
mid = begin + (end - begin) // 2
if nums[mid] == target:
return True
while begin < mid and nums[begin] == nums[mid]:
begin += 1
if nums[begin] <= nums[mid]:
if nums[begin] <= target < nums[mid]:
end = mid - 1
else:
begin = mid + 1
else:
if nums[mid] < target <= nums[end]:
begin = mid + 1
else:
end = mid - 1
return False
128 Longest Consecutive Sequence
'''
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
'''
class Solution:
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
visited = {}
n = len(nums)
for i in nums:
visited[i] = False
longest = 0
for i in nums:
if visited[i]:
continue
visited[i] = True
length = 1
j = i + 1
while j in visited.keys():
visited[j] = True
length += 1
j += 1
j = i - 1
while j in visited.keys():
visited[j] = True
length += 1
j -= 1
longest = max(longest, length)
return longest
154 Find Minimum in Rotated Sorted Array II
'''
Input: [1,3,5]
Output: 1
Input: [2,2,2,0,1]
Output: 0
'''
class Solution:
# def findMin(self, nums: List[int]) -> int:
# l = 0
# r = len(nums)-1
# while l < r:
# mid = (l+r)//2
# if nums[mid] < nums[r]:
# r = mid
# elif nums[mid] > nums[r]:
# l = mid+1
# else:
# return min(self.findMin(nums[:mid+1]), self.findMin(nums[mid+1:]))
# return nums[l]
def findMin(self, nums: List[int]) -> int:
l = 0
r = len(nums) - 1
if nums[l] < nums[r]:
return nums[l]
while l < r:
mid = (l+r)//2
if nums[mid] > nums[r]:
l = mid + 1
elif nums[mid] < nums[r]:
r = mid
else:
r = r-1
return nums[l]
347 Top K Frequent Elements
'''
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
'''
class Solution:
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
dic = {}
for n in nums:
if n not in dic:
dic[n] = 1
else:
dic[n] += 1
maxfreq = 0
freq = {}
for key, v in dic.items():
if v not in freq.keys():
freq[v] = [key]
else:
freq[v].append(key)
maxfreq = max(maxfreq, v)
res = []
for cnt in range(maxfreq,-1,-1):
if cnt in freq:
res += freq[cnt]
if len(res) >= k:
return res
网友评论