Daily practice - February 13, 2022

---

One , The envelope problem of Russian Dolls

1, Program Introduction

Here's a two-dimensional array of integers envelopes , among envelopes[i] = [wi, hi] , It means the first one i The width and height of each envelope .

When the width and height of another envelope are larger than this one , This envelope can be put into another envelope , Like Russian Dolls .

Please calculate How many at most Envelopes can form a group “ Russian Dolls ” The envelope （ You can put one envelope in another ）.

Be careful ：

• It is not allowed to rotate the envelope .

Example 1：

• Input ：envelopes = [[5,4],[6,4],[6,7],[2,3]]
• Output ：3
• explain ： The maximum number of envelopes is
  3, Combination for :
  [2,3] => [5,4] => [6,7].

Example 2：

• Input ：envelopes = [[1,1],[1,1],[1,1]]
• Output ：1

Tips ：

• $1<=envelopes.length<=5000$
• $envelopes[i].length==2$
• $1<=wi,hi<=10^4$

2, Program code

# -*- coding: utf-8 -*-
""" Created on Sun Feb 13 21:48:03 2022 Function:  The envelope problem of Russian Dolls  @author:  Trabecula aixj """
class Solution:
    def maxEnvelopes(self, envelopes) -> int:
        """ :param envelopes: List[List[int]] :return: int """
        n = len(envelopes)
        if not n:
            return 0
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if envelopes[j][1] < envelopes[i][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

Two , The most points on the line

1, Program Introduction

Give you an array points , among points[i] = [xi, yi] Express X-Y A point on the plane . Find out how many points are in the same line at most .

Example 1：

• Input ：points = [[1,1],[2,2],[3,3]]
• Output ：3

Example 2：

• Input ：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
• Output ：4

Tips ：

• 1 <= points.length <= 300
• points[i].length == 2
• $-10^4<=xi,yi<=10^4$
• points All the points in Different from each other

2, Program code

# -*- coding: utf-8 -*-
""" Created on Sun Feb 13 21:48:24 2022 Function:  The most points on the line  @author:  Trabecula aixj """
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        if len(points) <= 2:
            return len(points)
        maxNum = 0
        for i in range(len(points)):
            maxNum = max(maxNum, self.find(points[i], points[:i] + points[i + 1 :]))
        return maxNum + 1
    def find(self, point, pointList):
        memories = {
    }
        count = 0
        inf = float("inf")
        for curPoint in pointList:
            if curPoint[1] == point[1] and curPoint[0] != point[0]:
                memories[inf] = memories.get(inf, 0) + 1
            elif curPoint[1] == point[1] and curPoint[0] == point[0]:
                count += 1
            else:
                slope = (curPoint[0] - point[0]) / (curPoint[1] - point[1])
                memories[slope] = memories.get(slope, 0) + 1
        if memories:
            return count + max(memories.values())
        else:
            return count

3、 ... and , Look for the minimum value in the rotation sort array II

1, Program Introduction

We know a length of n Array of , In ascending order in advance , Through 1 To n Time rotate after , Get the input array . for example , Original array nums = [0,1,4,4,5,6,7] After the change may get ：

• If you rotate 4 Time , You can get [4,5,6,7,0,1,4]
• If you rotate 7 Time , You can get [0,1,4,4,5,6,7]

Be careful , Array [a[0], a[1], a[2], …, a[n-1]] Rotate once The result is an array [a[n-1], a[0], a[1], a[2], …, a[n-2]] .

Give you a chance to exist repeat An array of element values nums , It turns out to be an ascending array , According to the above situation, we have made many rotations . Please find and return the The smallest element .

Example 1：

• Input ：nums = [1,3,5]
• Output ：1

Example 2：

• Input ：nums = [2,2,2,0,1]
• Output ：0

Tips ：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums It turns out to be an ascending array , And carried on 1 to n Second rotation

Advanced ：

• The question is Look for the minimum value in the rotation sort array (https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/description/) The extended topic of .
• Does allowing repetition affect the time complexity of the algorithm ？ How will it affect , Why? ？

2, Program code

# -*- coding: utf-8 -*-
""" Created on Sun Feb 13 21:49:48 2022 Function:  Look for the minimum value in the rotation sort array  II @author:  Trabecula aixj """
class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] == nums[right]:
                right -= 1
            else:
                right = mid
        return nums[left]