حل سوالات استخدامی سایت leetcode.com
Task: No. 16. 3Sum Closest #medium
Condition:
Given an integer array nums of length n and an integer target, find the three integers in nums whose sum is closest to the target. Returns the sum of three integers. You can assume that each input will have exactly one solution.
Solution:
Explanation:
Sort an array:
First we sort the num array. This will allow us to use two pointers to find the closest sum.
Initializing the result:
We initialize the result variable with the sum of the first three elements of the sorted array. This will be our starting closest amount.
Traversing the array:
We use a for loop to iterate through the array. For each element we use two pointers j and k:
j starts immediately after the current element i.
k starts from the end of the array.
Two pointers:
Inside the while loop, while j is less than k, we calculate the sum of the elements num[i], num[j] and num[k].
If sum equals target, then we return sum since we found an exact match.
Result update:
If the current sum sum is closer to target than the previous closest sum result, update result.
Pointer shift:
If sum is less than target, move pointer j to the right to increase the sum.
If sum is greater than target, shift pointer k to the left to decrease the sum.
Return result:
After completing all iterations, we return result, which will contain the sum of three numbers closest to target.
Time and space complexity:
Time complexity: O(n^2), where n is the length of the array. Sorting takes O(n log n) and the basic algorithm with two pointers runs in O(n^2).
Space complexity: O(1) since we only use a few additional variables, and do not use additional memory depending on the size of the input data.
#interview #LeetCode
🆔 @Python4all_pro
Task: No. 16. 3Sum Closest #medium
Condition:
Given an integer array nums of length n and an integer target, find the three integers in nums whose sum is closest to the target. Returns the sum of three integers. You can assume that each input will have exactly one solution.
Solution:
def threeSumClosest(self, num, target):
num.sort()
result = num[0] + num[1] + num[2]
for i in range(len(num) - 2):
j, k = i+1, len(num) - 1
while j < k:
sum = num[i] + num[j] + num[k]
if sum == target:
return sum
if abs(sum - target) < abs(result - target):
result = sum
if sum < target:
j += 1
elif sum > target:
k -= 1
else:
return result
return result
Explanation:
Sort an array:
First we sort the num array. This will allow us to use two pointers to find the closest sum.
Initializing the result:
We initialize the result variable with the sum of the first three elements of the sorted array. This will be our starting closest amount.
Traversing the array:
We use a for loop to iterate through the array. For each element we use two pointers j and k:
j starts immediately after the current element i.
k starts from the end of the array.
Two pointers:
Inside the while loop, while j is less than k, we calculate the sum of the elements num[i], num[j] and num[k].
If sum equals target, then we return sum since we found an exact match.
Result update:
If the current sum sum is closer to target than the previous closest sum result, update result.
Pointer shift:
If sum is less than target, move pointer j to the right to increase the sum.
If sum is greater than target, shift pointer k to the left to decrease the sum.
Return result:
After completing all iterations, we return result, which will contain the sum of three numbers closest to target.
Time and space complexity:
Time complexity: O(n^2), where n is the length of the array. Sorting takes O(n log n) and the basic algorithm with two pointers runs in O(n^2).
Space complexity: O(1) since we only use a few additional variables, and do not use additional memory depending on the size of the input data.
#interview #LeetCode
🆔 @Python4all_pro
حل سوالات استخدامی سایت leetcode.com
Task: No. 17. Letter Combinations of a Phone Number #medium
Condition:
Given a string containing the numbers 2 to 9 inclusive, return all possible combinations of letters that the number can represent. Return the answer in any order. The correspondence between numbers and letters (as on telephone buttons) is given below. Note that 1 does not match any letters.
Solution:
Explanation:
Sorting:
First we sort the nums array. Sorting makes it easy to handle duplicates because similar items will be placed next to each other.
Recursive dfs method:
The dfs method is used to recursively construct all possible subsets. In dfs, path represents the current subset, and res is a list of all subsets.
Adding a subset to the result:
At each level of recursion, we add the current subset of path to the result of res.
Handling duplicates:
Before continuing the recursion, we check whether the current element nums[i] is a duplicate of the previous element. If so, skip it to avoid adding identical subsets to res.
Recursive construction of subsets:
For each element in nums, starting at the current index, we call dfs on the next elements of the array (nums[i+1:]). This means that we consider subsets that include the current element, and continue to build subsets without the current element.
Path (path) and compartment (nums):
Each time dfs is called, a new subset is created by adding the current element to path. This new list is then passed to the next level of recursion, allowing all possible subsets to be constructed.
Time and space complexity:
Time complexity: O(2^n), where n is the number of elements in nums. This is because there are 2^n subsets for an array of n elements.
Space complexity: O(2^n * n), since each of the 2^n possible subsets may require up to n elements to store.
#interview #LeetCode
🆔 @Python4all_pro
Task: No. 17. Letter Combinations of a Phone Number #medium
Condition:
Given a string containing the numbers 2 to 9 inclusive, return all possible combinations of letters that the number can represent. Return the answer in any order. The correspondence between numbers and letters (as on telephone buttons) is given below. Note that 1 does not match any letters.
Solution:
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
nums.sort()
self.dfs(nums, [], res)
return res
def dfs(self, nums, path, res):
res.append(path)
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
self.dfs(nums[i+1:], path + [nums[i]], res)
Explanation:
Sorting:
First we sort the nums array. Sorting makes it easy to handle duplicates because similar items will be placed next to each other.
Recursive dfs method:
The dfs method is used to recursively construct all possible subsets. In dfs, path represents the current subset, and res is a list of all subsets.
Adding a subset to the result:
At each level of recursion, we add the current subset of path to the result of res.
Handling duplicates:
Before continuing the recursion, we check whether the current element nums[i] is a duplicate of the previous element. If so, skip it to avoid adding identical subsets to res.
Recursive construction of subsets:
For each element in nums, starting at the current index, we call dfs on the next elements of the array (nums[i+1:]). This means that we consider subsets that include the current element, and continue to build subsets without the current element.
Path (path) and compartment (nums):
Each time dfs is called, a new subset is created by adding the current element to path. This new list is then passed to the next level of recursion, allowing all possible subsets to be constructed.
Time and space complexity:
Time complexity: O(2^n), where n is the number of elements in nums. This is because there are 2^n subsets for an array of n elements.
Space complexity: O(2^n * n), since each of the 2^n possible subsets may require up to n elements to store.
#interview #LeetCode
🆔 @Python4all_pro
حل سوالات استخدامی سایت leetcode.com
Problem: No. 18. 4Sum #medium
Condition:
Given an array nums of n integers, return an array of all unique quadruples [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n
a, b, c and d are different.
nums[a] + nums[b] + nums[c] + nums[d] == target
You can return the response in any order.
Solution:
Explanation:
Sorting:
First the nums array is sorted. Sorting makes it easier to handle duplicates and speeds up execution using binary search.
Recursive function findNsum:
The findNsum function recursively finds combinations whose sum is equal to the given target. Depending on the value of N, it handles different cases:
For N = 2: This is the "Two Sum" subtask. We use two pointers (l and r) to find pairs of numbers in the array that add up to target.
If the current pair of numbers nums[l] and nums[r] sums to target, add this pair to the results.
We move the pointers left and right, skipping duplicates to avoid repeated combinations.
For N > 2: The function calls itself recursively, decrementing N by 1 and continuing to search for combinations among the remaining elements of the array. We also check if the current element and its combinations are within a valid range (for optimization).
Conditions for exiting recursion:
If the length of the array is less than N or N is less than 2, the function terminates execution, since there is no point in further searching for combinations.
We use conditions to stop execution if the current element is too large or too small to achieve the target value for a given number of elements (N).
Unique combinations:
To avoid duplicates, we check whether the current element is unique compared to previous ones.
Collection of results:
The results for each call to the findNsum function are added to the results list.
#interview #LeetCode
🆔 @Python4all_pro
Problem: No. 18. 4Sum #medium
Condition:
Given an array nums of n integers, return an array of all unique quadruples [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n
a, b, c and d are different.
nums[a] + nums[b] + nums[c] + nums[d] == target
You can return the response in any order.
Solution:
nums.sort()
results = []
self.findNsum(nums, target, 4, [], results)
return results
def findNsum(self, nums, target, N, result, results):
if len(nums) < N or N < 2: return
# solve 2-sum
if N == 2:
l,r = 0,len(nums)-1
while l < r:
if nums[l] + nums[r] == target:
results.append(result + [nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while r > l and nums[r] == nums[r + 1]:
r -= 1
elif nums[l] + nums[r] < target:
l += 1
else:
r -= 1
else:
for i in range(0, len(nums)-N+1): # careful about range
if target < nums[i]*N or target > nums[-1]*N: # take advantages of sorted list
break
if i == 0 or i > 0 and nums[i-1] != nums[i]: # recursively reduce N
self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
return
Explanation:
Sorting:
First the nums array is sorted. Sorting makes it easier to handle duplicates and speeds up execution using binary search.
Recursive function findNsum:
The findNsum function recursively finds combinations whose sum is equal to the given target. Depending on the value of N, it handles different cases:
For N = 2: This is the "Two Sum" subtask. We use two pointers (l and r) to find pairs of numbers in the array that add up to target.
If the current pair of numbers nums[l] and nums[r] sums to target, add this pair to the results.
We move the pointers left and right, skipping duplicates to avoid repeated combinations.
For N > 2: The function calls itself recursively, decrementing N by 1 and continuing to search for combinations among the remaining elements of the array. We also check if the current element and its combinations are within a valid range (for optimization).
Conditions for exiting recursion:
If the length of the array is less than N or N is less than 2, the function terminates execution, since there is no point in further searching for combinations.
We use conditions to stop execution if the current element is too large or too small to achieve the target value for a given number of elements (N).
Unique combinations:
To avoid duplicates, we check whether the current element is unique compared to previous ones.
Collection of results:
The results for each call to the findNsum function are added to the results list.
#interview #LeetCode
🆔 @Python4all_pro
حل سوالات استخدامی سایت leetcode.com
Problem: No. 19. Remove Nth Node From End of List #medium
Condition:
Given the header of a linked list, remove the nth node from the end of the list and return its header
Solution:
Explanation:
Determining the list size:
First we go through the entire list to find its size. This is necessary to determine which node needs to be removed.
The size variable keeps track of the number of nodes in the list.
Removing the first node:
If n is equal to the size of the list, it means the first node should be removed. In this case, we return the next node from the head of the list.
Search for a node before the one you want to delete:
If n is not equal to the size of the list, we need to find the node that comes before the nth node from the end. We do this by moving size-n-1 nodes forward in the list.
Removing a node:
We set the next node for the found node so that it points to the next node after the next one, effectively bypassing the node to be deleted.
Returning a new header:
Returning the head of the list. If the first node was deleted, the new header will be the starting node of the list after the delete.
Time and space complexity:
Time complexity: O(L), where L is the length of the list. We go through the list twice: once to count nodes and again to remove a node.
Space complexity: O(1) because we use a constant amount of extra space independent of the size of the input data.
#Code
#interview #LeetCode
🆔 @Python4all_pro
Problem: No. 19. Remove Nth Node From End of List #medium
Condition:
Given the header of a linked list, remove the nth node from the end of the list and return its header
Solution:
# class ListNode:
# def init(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if head.next == None:
return None
tmp = head
size = 0
# find the size of the linked list
while tmp:
size += 1
tmp = tmp.next
tmp = head
#if we have to remove the first node:
if n == size:
return head.next
for i in range(size-n-1):
tmp = tmp.next
tmp.next = tmp.next.next
return head
Explanation:
Determining the list size:
First we go through the entire list to find its size. This is necessary to determine which node needs to be removed.
The size variable keeps track of the number of nodes in the list.
Removing the first node:
If n is equal to the size of the list, it means the first node should be removed. In this case, we return the next node from the head of the list.
Search for a node before the one you want to delete:
If n is not equal to the size of the list, we need to find the node that comes before the nth node from the end. We do this by moving size-n-1 nodes forward in the list.
Removing a node:
We set the next node for the found node so that it points to the next node after the next one, effectively bypassing the node to be deleted.
Returning a new header:
Returning the head of the list. If the first node was deleted, the new header will be the starting node of the list after the delete.
Time and space complexity:
Time complexity: O(L), where L is the length of the list. We go through the list twice: once to count nodes and again to remove a node.
Space complexity: O(1) because we use a constant amount of extra space independent of the size of the input data.
#Code
#interview #LeetCode
🆔 @Python4all_pro