LeetCode Day 07 Hash map (2/2)
Published:
Today is last day of hash map practice (2/2). Its little difficult.
Question 1
Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:
0 <= i, j, k, l < n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
The question looks like a maths question , but the output only requires the number of counts , no detailed result is needed , so the hash table can be used for counting.
Use dict to hold the number of nums1 and nums2, then iterate through nums3 and nums4 to find the number that can be cancelled out. If the result of 1 and 2 can be cancelled out by 3 and 4, then the count count is increased by 1. The value of count returned at the end is the result sought.
class Solution(object):
def fourSumCount(self, nums1, nums2, nums3, nums4):
hashmap = dict()
for n1 in nums1:
for n2 in nums2:
if n1 + n2 in hashmap:
hashmap[n1+n2] += 1
else:
hashmap[n1+n2] = 1
count = 0
for n3 in nums3:
for n4 in nums4:
key = - n3 - n4
if key in hashmap:
count += hashmap[key]
return count
Question 2
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
This question is a lot like 242. Valid Anagram
But N.B. Each letter in magazine can only be used once in ransomNote.
Therefore, on the basis of question 242, the final judgement condition is changed: if the last bit is greater than 0, output False, because there are words in ransom that are not covered by magazine.
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
record = [0] * 26
for i in ransomNote:
record[ord(i)-ord("a")] += 1
for i in magazine:
record[ord(i)-ord("a")] -= 1
for i in range(26):
if record[i] > 0:
return False
return True
Question 3
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
The difficulty with this question is that it is not possible to duplicate, and there is not much thought in using hashes
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
nums.sort()
for i in range(len(nums)):
if nums[i] > 0:
return result
if i > 0 and nums[i] == nums[i - 1]:
continue
left = i + 1
right = len(nums) - 1
while right > left:
sum_ = nums[i] + nums[left] + nums[right]
if sum_ < 0:
left += 1
elif sum_ > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
while right > left and nums[right] == nums[right - 1]:
right -= 1
while right > left and nums[left] == nums[left + 1]:
left += 1
right -= 1
left += 1
return result
Question 4
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n a, b, c, and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order.
This question is also a bit complex, with a similar idea to the third question, applying a for loop layer on top of the double pointer.
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
n = len(nums)
result = []
for i in range(n):
if nums[i] > target and nums[i] > 0 and target > 0:
break
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n):
if nums[i] + nums[j] > target and target > 0:
break
if j > i+1 and nums[j] == nums[j-1]:
continue
left, right = j+1, n-1
while left < right:
s = nums[i] + nums[j] + nums[left] + nums[right]
if s == target:
result.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 s < target:
left += 1
else:
right -= 1
return result