当前位置:网站首页>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]
边栏推荐
- How to use the flutter framework to develop and run small programs
- Finding the nearest common ancestor of binary tree by recursion
- [groovy] compile time meta programming (AST syntax tree conversion with annotations | define annotations and use groovyasttransformationclass to indicate ast conversion interface | ast conversion inte
- esxi的安装和使用
- Four dimensional matrix, flip (including mirror image), rotation, world coordinates and local coordinates
- Comment faire votre propre robot
- VSphere implements virtual machine migration
- Novice entry depth learning | 3-6: optimizer optimizers
- The growth path of test / development programmers, the problem of thinking about the overall situation
- XML Configuration File
猜你喜欢
For a deadline, the IT fellow graduated from Tsinghua suddenly died on the toilet
Cf:c. the third problem
图解网络:TCP三次握手背后的原理,为啥两次握手不可以?
The inconsistency between the versions of dynamic library and static library will lead to bugs
免费的聊天机器人API
MCU通过UART实现OTA在线升级流程
Introduction to robotics I. spatial transformation (1) posture, transformation
Starting from 1.5, build a micro Service Framework - call chain tracking traceid
ubantu 查看cudnn和cuda的版本
MYSQL GROUP_ The concat function realizes the content merging of the same ID
随机推荐
[groovy] compile time metaprogramming (compile time method injection | method injection using buildfromspec, buildfromstring, buildfromcode)
【文件IO的简单实现】
ubantu 查看cudnn和cuda的版本
CTF daily question day44 rot
Logstash clear sincedb_ Path upload records and retransmit log data
云导DNS和知识科普以及课堂笔记
Introduction of motor
几百行代码实现一个 JSON 解析器
朝招金安全吗 会不会亏损本金
The third season of ape table school is about to launch, opening a new vision for developers under the wave of going to sea
Spark AQE
Spark DF增加一列
DD's command
Zhuhai laboratory ventilation system construction and installation instructions
I'm interested in watching Tiktok live beyond concert
Starting from 1.5, build a micro Service Framework - call chain tracking traceid
免费的聊天机器人API
vSphere实现虚拟机迁移
Anconda download + add Tsinghua +tensorflow installation +no module named 'tensorflow' +kernelrestart: restart failed, kernel restart failed
Keepalive component cache does not take effect