Interview algorithm questions

One 、 Here's an unsorted array of integers nums , Please find the smallest positive integer that doesn't appear in it

Answer key

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        m = 1
        n = len(nums)
        if n == 0:
            return m
        nums.sort()
        for i in nums:
            if i == m:
                m += 1
        return m

Two 、 How to use rand7 Generate rand10

def rand_10():
	r1 = rand_7()
	r2 = rand_7()
	r = (r1 - 1) * 7 + r2
	a = True
	while a:
		if 1 <= r <= 40:
			num = (r-1)%10 + 1
			a = False
	return num

3、 ... and 、 Given an array of non negative integers , Your task is to count the number of triples that can form three sides of a triangle .

Answer key

The condition for forming a triangle is that the sum of the two small sides is greater than the third side , Determine the idea after clarifying the conditions ：

• Sort the given array , Make the small side on the left , The big side is on the right
• from $nums[2]$ Start traversing array ,$i$ Point to the largest edge of this traversal range
• Position the left and right pointers , The left pointer initially points to $nums[0]$, The right pointer initially points to $nums[i-1]$
  • If left + Right <= Dabian ,$l+1$
  • If left + Right > Dabian , be $[l,r)$ Take any number in the range as $nums[l]$, Can achieve $nums[l]+nums[r]>nums[i]$,res += r - l

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        num = 0
        if n == 3:
            if nums[0] + nums[1] > nums[2]:
                return 1
            else:
                return 0
        else:
            for i in range(2, n):
                l, r = 0, i-1
                while l < r:
                    if nums[l] + nums[r] > nums[i]:
                        num += r - l
                        r -= 1
                    else:
                        l += 1
            return num 

Four 、 The closest sum of three

Given an include n Array of integers nums and A target value target. find nums Three integers in , Make their sum and target Nearest . Returns the sum of the three numbers . Assume that there is only one answer for each group of input .

Answer key

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n = len(nums)
        nums.sort()
        res = float('inf')
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            else:
                l, r = i+1, n-1
                while l < r:
                    cur_sum = nums[i] + nums[l] + nums[r]
                    if cur_sum == target:
                        return target
                    elif cur_sum < target:
                        l += 1
                    else:
                        r -= 1
                    if abs(cur_sum - target) < abs(res - target):
                        res = cur_sum
        return res