Find -- collision pointer

Find – collision pointer

Give an integer array nums and return the index values I and j of the two numbers in the array, so that nums[i] + nums[j] is equal to a given target value, and the two indexes cannot be equal.

For example: num = [2,7,11,15], target = 9
Return [0,1]

Idea:

  1. Whether the start array is in order;
  2. Is the index calculated from 0 or 1?
  3. What should I do without a solution?
  4. What if there are multiple solutions? There is guaranteed to be a unique solution.

First try to force the solution, O(n2) traversal

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        len_nums = len(nums)
        for i in range(len_nums):
            for j in range(i+1,len_nums):
                if nums[i] + nums[j] == target:
                    return [i,j]

Try Optimization: use sorting + pointer collision (O(n) + O(nlogn) = O(nlogn))

Because the problem itself is not ordered, you need to sort the original array once. After sorting, you can solve it with O(n) pointer collision.
Because the index value is returned, the index value corresponding to the number should be stored before sorting

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = dict()
        nums_copy = nums.copy()
        sameFlag = True;
        nums.sort()
        l,r = 0,len(nums)-1
        while l < r:
            if nums[l] + nums[r] == target:
                break
            elif nums[l] + nums[r] < target:
                l += 1
            else:
                r -= 1
        res = []
        for i in range(len(nums)):
            if nums_copy[i] == nums[l] and sameFlag:
                res.append(i)
                sameFlag = False
            elif nums_copy[i] == nums[r]:
                res.append(i)
        return res

More Python IC implementations:
Start binding subscripts and values through list(enumerate(nums)), without special copy and bool judgment.

class Solution:
  nums = list(enumerate(nums))
  nums.sort(key = lambda x:x[1])
  i,j = 0, len(nums)-1
  while i < j:
    if nums[i][1] + nums[j][1] > target:
        j -= 1
    elif nums[i][1] + nums[j][1] < target:
        i += 1
    else:
        if nums[j][0] < nums[i][0]:
            nums[j],nums[i] = nums[i],nums[j]
        return num[i][0],nums[j][0]

Copy array + bool type auxiliary variable
Lookup table – O(n)
In the process of traversing the array, when traversing the element V, you can only see whether the element in front of V contains the element of target-v.

  1. If the search is successful, the solution is returned;
  2. If the search is not successful, put v in the lookup table and continue to find the next solution.
    Even if v is placed in the previous lookup table and overwrites v, the lookup of the current v element is not affected. Because you only need to find two elements, you only need
    Just find another element of target-v.
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = dict()
        for i in range(len(nums)):
            complement = target - nums[i]
            # This value has been found in the previous dictionary
            if record.get(complement) is not None:
                res = [i,record[complement]]
                return res
            record[nums[i]] = i

Title Description
Give an integer array and find all the different triples (a,b,c) in it so that a+b+c=0
Note: the answer cannot contain duplicate triples.
For example: num = [- 1, 0, 1, 2, - 1, - 4],
The result is: [- 1, 0, 1], [- 1, - 1, 2]]

Problem solving ideas

  1. Arrays are not ordered;
  2. The returned result is all solutions. Should the order of multiple solutions be considered There is no need to consider order
  3. What is a different triplet? Are indexes different or values different Different values are defined as triples
  4. How to return when there is no solution Empty list
class Solution:
    def threeSum(self, nums: [int]) -> [[int]]:
        nums.sort()
        res = []
        for i in range(len(nums)-2):
            # Because it is a sorted array, if the smallest is greater than 0, it can be excluded directly
            if nums[i] > 0: break
            # Exclude duplicate values of i
            if i > 0 and nums[i] == nums[i-1]: continue
            l,r = i+1, len(nums)-1
            while l < r:
                sum = nums[i] + nums[l] + nums[r]
                if sum == 0:
                    res.append([nums[i],nums[l],nums[r]])
                    l += 1
                    r -= 1
                    #Prevent duplication
                    while l < r and nums[l] == nums[l-1]: l += 1
                    while l < r and nums[r] == nums[r+1]: r -= 1
                elif sum < 0:
                    l += 1
                else:
                    r -= 1
        return res

Small routine

  1. Three indexes are processed in the form of for + while;
  2. When the array is not ordered, you should pay attention to the characteristics of order and what methods can be used to solve it? What's the inconvenience if it's out of order
    Inside?
  3. Collision pointer routine:
# Colliding pointer routine
l,r = 0, len(nums)-1
while l < r:
    if nums[l] + nums[r] == target:
        return nums[l],nums[r]
    elif nums[l] + nums[r] < target:
        l += 1
    else:
        r -= 1`

Routine for handling duplicate values: first convert to an ordered array, and then recycle to determine whether it is duplicate with the previous value:

# 1.
for i in range(len(nums)):
    if i > 0 and nums[i] == nums[i-1]: continue
# 2.
while l < r:
    while l < r and nums[l] == nums[l-1]: l += 1

Title Description
Given an integer array, find all the different quads (a,b,c,d) in it, so that a+b+c+d is equal to a given number target.

For example:
nums = [1, 0, -1, 0, -2, 2],target = 0

The result is:
[[-1, 0, 0, 1],[-2, -1, 1, 2],[-2, 0, 0, 2]]

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []
        if len(nums) < 4: return res
        if len(nums) == 4 and sum(nums) == target:
            res.append(nums)
            return res
        for i in range(len(nums)-3):
            if i > 0 and nums[i] == nums[i-1]: continue
            for j in range(i+1,len(nums)-2):
                if j > i+1 and nums[j] == nums[j-1]: continue
                l,r = j+1, len(nums)-1
                while l < r:
                    sum_value = nums[i] + nums[j] + nums[l] + nums[r]
                    if sum_value == target:
                        res.append([nums[i],nums[j],nums[l],nums[r]])
                        l += 1
                        r -= 1
                        while l < r and nums[l] == nums[l-1]: l += 1
                        while l < r and nums[r] == nums[r+1]: r -= 1
                    elif sum_value < target:
                        l += 1
                    else:
                        r -= 1
        return res

You can also use combinations(nums, 4) to fully arrange the four elements in the original array. After starting sort, set and de duplicate the arranged elements. However, the implementation using combinations alone will time out.

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        from itertools import combinations
        res = []
        for i in combinations(nums, 4):
            if sum(i) == target:
                res.append(i)
        res = set(res)
        return res

Title Description

Give an integer array and find the three elements a, B and C, so that the value of a+b+c is closest to another given number target.

For example: given array num = [- 1, 2, 1, - 4], and target = 1

The sum of the three numbers closest to target is 2 (-1 + 2 + 1 = 2).

analysis
Judge whether the sum of the three numbers is equal to the target value. If it is equal to the target value, return the three values directly. If it is not equal to the target value, compare the difference between the sum of the three numbers in the array and the target, and return the three numbers with the smallest difference.

nums.sort()
res = []
for i in range(len(nums)-2):
    l,r = i+1, len(nums)-1
    while l < r:
        sum = nums[i] + nums[l] + nums[r]
        if sum == 0:
            res.append([nums[i],nums[l],nums[r]])
        elif sum < 0:
            l += 1
        else:
            r -= 1
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        diff = abs(nums[0]+nums[1]+nums[2]-target)
        res = nums[0] + nums[1] + nums[2]
        for i in range(len(nums)):
            l,r = i+1,len(nums)-1
            t = target - nums[i]
            while l < r:
                if nums[l] + nums[r] == t:
                    return nums[i] + t
                else:
                    if abs(nums[l]+nums[r]-t) < diff:
                        diff = abs(nums[l]+nums[r]-t)
                        res = nums[i]+nums[l]+nums[r]
                    if nums[l]+nums[r] < t:
                        l += 1
                    else:
                        r -= 1
        return res

Title Description

Give four shaping arrays a, B, C and D, and find how many combinations of I, J, K and l there are, so that A[i]+B[j]+C[k]+D[l]=0. his
In, a, B, C and d all contain the same number of elements N, and 0 < = N < = 500;

Input:

A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output: 2

Analysis and Implementation
This problem is also a variant of the Sum class problem. It changes the conditions of the same array into four arrays, which can still be realized with the idea of look-up table.
First, you can consider putting the elements in the D array into the lookup table, and then traverse the first three arrays to judge whether the value of target minus each element exists in the lookup table. If so, add 1 to the result value. Then the data structure of the lookup table uses dict to store duplicate elements. The final result value plus the value of the corresponding key of dict is as follows:

from collections import Counter
record = Counter()
# First create a lookup table for array D
`for i in range(len(D)):
    record[D[i]] += 1
res = 0 
for i in range(len(A)):
    for j in range(len(B)):
        for k in range(len(C)):
            num_find = 0-A[i]-B[j]-C[k]
            if record.get(num_find) != None:
                res += record(num_find)
return res

At this time, because the time complexity of traversing the three layers is O (N3), n < = 500, if n is too large, the consumption of the algorithm is still too large. Optimization:

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: 
List[int]) -> int:
        from collections import Counter
        record = Counter()
        for i in range(len(A)):
            for j in range(len(B)):
                record[A[i]+B[j]] += 1
        res = 0
        for i in range(len(C)):
            for j in range(len(D)):
                find_num = 0 - C[i] - D[j]
                if record.get(find_num) != None:
                    res += record[find_num]
        return res 

The complexity of the algorithm is O(n2)

The optimized functions and python are generated as follows:

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: 
List[int]) -> int:
        record = collections.Counter(a + b for a in A for b in B)
        return sum(record.get(- c - d, 0) for c in C for d in D)

Title Description

Give an array of strings that group all words that can produce the same result by reversing the character order.

Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output: ["ate", "eat", "tea"], ["nat", "tan"], ["bat"]]

explain:
All inputs are lowercase letters.
The order in which answers are output is not considered.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        from collections import defaultdict
        strs_dict = defaultdict(list)
        res = []
        for str in strs:
            key = ''.join(sorted(list(str)))
            strs_dict[key] += str.split(',')
        for v in strs_dict.values():
            res.append(v)
        return res

Then replace the places that can be replaced by list generation. The code is as follows:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        from collections import defaultdict
        strs_dict = defaultdict(list)
        for str in strs:
            key = ''.join(sorted(list(str)))
            strs_dict[key] += str.split(',')
        return [v for v in strs_dict.values()]

Title Description
Given n points on a plane, find how many triples (i,j,k) composed of these points exist, so that the distance between I and j is equal to the distance between I and K.
Where n is up to 500, and the range of all point coordinates is [- 1000010000].

Input:
[[0,0],[1,0],[2,0]]

Output:
2
Explanation:
The two results are: [[1,0], [0,0], [2,0]] and [[1,0], [2,0], [0,0]]

distance
For the calculation of distance value, if it is calculated according to the European distance method, it is easy to produce floating-point numbers. You can remove the root sign and compare the distance with the sum of squares of the difference.
The implementation code is as follows:

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        res = 0
        from collections import Counter
        for i in points:
            record = Counter()
            for j in points:
                if i != j:
                    record[self.dis(i,j)] += 1
            for k,v in record.items():
                res += v*(v-1)
        return res
    def dis(self,point1,point2):
        return (point1[0]-point2[0]) ** 2 + (point1[1]-point2[1]) ** 2

optimization
Optimize the implemented Code:

  1. Change the for loop traversal to list generation;
  2. For the operation of sum + = consider using the sum function.
  3. Use closure to embed different functions;
class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        from collections import Counter
        def f(x1, y1):
            # Sum the distance values of J and K under an i
            d = Counter((x2 - x1) ** 2 + (y2 - y1) ** 2 for x2, y2 in 
points)
            return sum(t * (t-1) for t in d.values())
        # Sum the distances of each i
        return sum(f(x1, y1) for x1, y1 in points)

Title Description
Given a two-dimensional plane with n points, find the maximum number of points on the same line.

Example 1:
Input: [1,1], [2,2], [3,3]]
Output: 3

Example 2:
Input: [1,1], [3,2], [5,3], [4,1], [2,3], [1,4]]
Output: 4

Analysis and Implementation
The requirement of this topic is to see how many points are on the same straight line, so judging whether the points are on the same straight line is actually equivalent to judging whether the slope of I and j is equal to the slope of I and K.
Review the requirements in the previous 447 topic: make the distance between I and j equal to the distance between I and K. here, directly consider using the lookup table, that is, find the number of key s with the same slope, value.
In the previous question, i and j, J and i are two different situations, but in this question, they belong to the same two points. Therefore, when traversing each i to find a point with the same slope as i, we can no longer count the result number res + +, but should take the maximum value in the lookup table. If two slopes are the same, 3 points should be returned, so the result number + 1 is returned.

class Solution:
    def maxPoints(self,points):
        if len(points) <= 1:
           return len(points)
        res = 0
        from collections import defaultdict
        for i in range(len(points)):
            record = defaultdict(int)
            samepoint = 0
            for j in range(len(points)):
                if points[i][0] == points[j][0] and points[i][1] == points[j][1]:
                    samepoint += 1
                else:
                    record[self.get_Slope(points,i,j)] += 1
            for v in record.values():
                res = max(res, v+samepoint)
            res = max(res, samepoint)
        return res
    def get_Slope(self,points,i,j):
        if points[i][1] - points[j][1] == 0:
            return float('Infinite')
        return (points[i][0] - points[j][0]) / (points[i][1] - points[j][1])

The time complexity of the solution is O(n2) and the space complexity is O(n)

Tags: Python Algorithm

Posted by steven21 on Fri, 20 May 2022 16:49:37 +0300