当前位置:网站首页>Huawei machine test: folding books
Huawei machine test: folding books
2022-07-22 12:49:00 【Xiao Zhu, Xiao Zhu will never admit defeat】
【 Programming topics |200 branch 】 Fold books 【2021 H1,H2, 2022 H1 Examination questions 】
Title Description :
Given the length and width of a set of books , And only when the length and width of one book are smaller than the length and width of another book , Two books can be stacked together , Ask how many books in this group can be stacked together .
Input
[[20,16],[15,11],[10,10],[9,10]]
Output
3
explain
The first three books can be stacked together .
Thought analysis
This problem is related to leetcode:354. The envelope problem of Russian Dolls It's the same type of topic , The prototype of this kind of problem is the longest increasing subsequence problem .
The topic should be in 2 On dimensions ( I.e. long + wide ) At the same time, keep strictly increasing . Then we can arrange one of the dimensions in order , To ensure that it keeps increasing in one dimension ( This is not strictly incremental ); Then you can focus on another dimension .
Sort the length and width first , Long ascending order , Look the same , Arrange in wide descending order , Here you can use a two-dimensional array lambda Expression writing .
Then we calculate the longest increasing subsequence . The length has been in ascending order , Just judge the width . To deal with the problem of width is to deal with the problem of the longest increasing subsequence .
Related series of topics can be referred to :【Leetcode】 The longest increasing subsequence problem and its application
Method 1 : Dynamic programming
The current element is larger than the previous element ,dp[i] = Math.max(dp[i], dp[j] + 1);
notes : Dynamic programming problems may have timeout problems when there is a large amount of data .
Method 2 : greedy + Two points search
Every time you select the next incremental element , Choose smaller endings . Use binary search , Go find this smaller .
such as {1, 5, 3, 4, 7} 5 and 3 Choose between 3 As the end element of the current incremental sequence .
dp[i]: All lengths are i+1 In the increasing subsequence of , The mantissa of the smallest sequence .
Iterate over arrays , Judge each number in turn num Insert it into dp The corresponding position of the array :
- num > dp[res], Express num Greater than the mantissa of all known increasing sequences , take num Add in dp An array of the tail , And increase the length of the longest sequence res Add 1
- dp[i-1] < num <= dp[i], Update only the corresponding dp[i]
Longest increasing subsequence reference :【Leetcode】 Calculate longest series ( Dynamic programming )
Reference code
Method 1 : Dynamic programming
import java.util.Arrays;
import java.util.Scanner;
public class dieShu {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine().replaceAll("\\[", "").replaceAll("\\]", "");
String[] str = s.split(",");
int[][] nums = new int[str.length / 2][2];
for (int i = 0; i < nums.length; i++) {
nums[i][0] = Integer.parseInt(str[i * 2]);
nums[i][1] = Integer.parseInt(str[i * 2 + 1]);
}
Arrays.sort(nums, (a, b) -> (a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]));
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int res = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i][1] > nums[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(dp[i], res);
}
System.out.println(res);
}
}
Method 2 : greedy + Two points search
import java.util.Arrays;
import java.util.Scanner;
public class dieShu {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine().replaceAll("\\[", "").replaceAll("\\]", "");
String[] str = s.split(",");
int[][] nums = new int[str.length / 2][2];
for (int i = 0; i < nums.length; i++) {
nums[i][0] = Integer.parseInt(str[i * 2]);
nums[i][1] = Integer.parseInt(str[i * 2 + 1]);
}
Arrays.sort(nums, (a, b) -> (a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]));
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int res = 0;
for (int[] num : nums) {
int left = 0, right = res;
while (left < right) {
int mid = (right - left ) / 2 + left;
if (dp[mid] < num[1]) {
left = mid + 1;
} else{
right = mid;
}
}
dp[left] = num[1];
if (left == res) {
res++;
}
}
System.out.println(res);
}
}
Welcome to comment and leave your own more concise method .
边栏推荐
- Shell入门3
- Multifunctional embedded decoding software (1)
- 微软SDL 2022年最新版学习笔记
- The sandbox and tower team jointly launched the tower defense game creation competition
- 线程池配置 异步编排 CompletableFuture
- 红队具体怎么进行测试工作开展的
- What do U.S. officials think of Web3?
- STM32 minimum system design
- 80% 应聘者都不及格的 JS 面试题
- [FPGA tutorial case 34] communication case 4 - QPSK modulation signal generation based on FPGA, and its constellation is tested by MATLAB
猜你喜欢
小程序毕设作品之微信酒店预订小程序毕业设计(4)开题报告
Spark Learning Notes (I) -- simulating distributed computing
[PHP environment setup /wamp/ interpreter / download]
Chrome插件开发教程
Detailed explanation of C language pointer
How to realize the bottom pop-up box encapsulation of wechat applet
爱可可AI前沿推介(7.21)
JS Console Alert REPL 报错 变量 变量声明提升 数据类型 typeof
[FPGA tutorial case 34] communication case 4 - QPSK modulation signal generation based on FPGA, and its constellation is tested by MATLAB
阿里云技术专家杨泽强:弹性计算云上可观测能力构建
随机推荐
Detailed analysis process of lapsus stealing Microsoft Bing source code
等额本金和等额本息还款方式的差异分析
BGP routing principles
Unlock the correct combination method of CNN and transformer, and ByteDance proposes an effective next-generation visual transformer
Programming skills │ amazing syntax of advanced markdown editor
深层递归的优化
不同实现方式的球幕投影都有哪些特点
Multifunctional embedded decoding software (1)
PHP json_decode 用法
YLearn因果学习开源项目「贡献者计划」精彩来袭!
网络安全风险评估-电信行业落地实践最佳案例
解锁CNN和Transformer正确结合方法,字节跳动提出有效的下一代视觉Transformer
C#通过字符串分割字符串Split
代码评审中用好7招,成功建立起你的反对同盟
121. 买卖股票的最佳时机
The sandbox and tower team jointly launched the tower defense game creation competition
Md5&Md5盐值加密
STM32 FSMC usage notes
小程序毕设作品之微信酒店预订小程序毕业设计(3)后台功能
[golang | grpc] use grpc to realize the watch function