当前位置:网站首页>Daily practice - February 13, 2022
Daily practice - February 13, 2022
2022-07-06 00:54:00 【Trabecula aixj】
List of articles
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 < = e n v e l o p e s . l e n g t h < = 5000 1 <= envelopes.length <= 5000 1<=envelopes.length<=5000
- e n v e l o p e s [ i ] . l e n g t h = = 2 envelopes[i].length == 2 envelopes[i].length==2
- 1 < = w i , h i < = 1 0 4 1 <= wi, hi <= 10^4 1<=wi,hi<=104
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
- − 1 0 4 < = x i , y i < = 1 0 4 -10^4 <= xi, yi <= 10^4 −104<=xi,yi<=104
- 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]
边栏推荐
- BiShe - College Student Association Management System Based on SSM
- 图解网络:TCP三次握手背后的原理,为啥两次握手不可以?
- Recoverable fuse characteristic test
- Kotlin core programming - algebraic data types and pattern matching (3)
- Installation and use of esxi
- 毕设-基于SSM高校学生社团管理系统
- 从 1.5 开始搭建一个微服务框架——调用链追踪 traceId
- 如何制作自己的機器人
- Ubantu check cudnn and CUDA versions
- Four commonly used techniques for anti aliasing
猜你喜欢
BiShe - College Student Association Management System Based on SSM
Keepalive component cache does not take effect
Installation and use of esxi
View class diagram in idea
Set data real-time update during MDK debug
免费的聊天机器人API
Spark AQE
Questions about database: (5) query the barcode, location and reader number of each book in the inventory table
[groovy] JSON string deserialization (use jsonslurper to deserialize JSON strings | construct related classes according to the map set)
Exciting, 2022 open atom global open source summit registration is hot
随机推荐
VSphere implements virtual machine migration
免费的聊天机器人API
Beginner redis
Arduino hexapod robot
Spark SQL null value, Nan judgment and processing
Problems and solutions of converting date into specified string in date class
Uniapp development, packaged as H5 and deployed to the server
Opencv classic 100 questions
[groovy] compile time meta programming (AST syntax tree conversion with annotations | define annotations and use groovyasttransformationclass to indicate ast conversion interface | ast conversion inte
Fibonacci number
Hundreds of lines of code to implement a JSON parser
esxi的安装和使用
Differences between standard library functions and operators
直播系统代码,自定义软键盘样式:字母、数字、标点三种切换
Ffmpeg captures RTSP images for image analysis
Getting started with devkit
Construction plan of Zhuhai food physical and chemical testing laboratory
Recursive method to realize the insertion operation in binary search tree
Building core knowledge points
XML Configuration File