当前位置:网站首页>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]
边栏推荐
- Yolov5, pychar, Anaconda environment installation
- Five challenges of ads-npu chip architecture design
- Questions about database: (5) query the barcode, location and reader number of each book in the inventory table
- Building core knowledge points
- Exciting, 2022 open atom global open source summit registration is hot
- 图解网络:TCP三次握手背后的原理,为啥两次握手不可以?
- Zhuhai laboratory ventilation system construction and installation instructions
- Spark DF adds a column
- ADS-NPU芯片架构设计的五大挑战
- The detailed page returns to the list and retains the original position of the scroll bar
猜你喜欢
MCU通过UART实现OTA在线升级流程
从 1.5 开始搭建一个微服务框架——调用链追踪 traceId
Finding the nearest common ancestor of binary search tree by recursion
Fibonacci number
Building core knowledge points
Extension and application of timestamp
The growth path of test / development programmers, the problem of thinking about the overall situation
vSphere实现虚拟机迁移
Convert binary search tree into cumulative tree (reverse middle order traversal)
Recoverable fuse characteristic test
随机推荐
[groovy] JSON serialization (convert class objects to JSON strings | convert using jsonbuilder | convert using jsonoutput | format JSON strings for output)
朝招金安全吗 会不会亏损本金
从 1.5 开始搭建一个微服务框架——调用链追踪 traceId
免费的聊天机器人API
BiShe - College Student Association Management System Based on SSM
【第30天】给定一个整数 n ,求它的因数之和
Logstash clear sincedb_ Path upload records and retransmit log data
DD's command
KDD 2022 | EEG AI helps diagnose epilepsy
What is the most suitable book for programmers to engage in open source?
cf:D. Insert a Progression【关于数组中的插入 + 绝对值的性质 + 贪心一头一尾最值】
Gartner发布2022-2023年八大网络安全趋势预测,零信任是起点,法规覆盖更广
NLP basic task word segmentation third party Library: ICTCLAS [the third party library with the highest accuracy of Chinese word segmentation] [Chinese Academy of Sciences] [charge]
[groovy] compile time meta programming (compile time method interception | method interception in myasttransformation visit method)
Overview of Zhuhai purification laboratory construction details
猿桌派第三季开播在即,打开出海浪潮下的开发者新视野
95后CV工程师晒出工资单,狠补了这个,真香...
cf:H. Maximal AND【位运算练习 + k次操作 + 最大And】
新手入门深度学习 | 3-6:优化器optimizers
STM32按键消抖——入门状态机思维