华为机试：叠书

【编程题目 |200分】叠书【2021 H1,H2, 2022 H1 考试题】

题目描述：

给定一组书的长宽，并且只有当一本书的长宽同时小于另一本书的长宽时，两书才能叠放在一起，求该组书中最多能有多少本书叠放在一起。

输入

[[20,16],[15,11],[10,10],[9,10]]

输出

3

解释

前三本可叠放在一起。

思路分析

这道题与leetcode：354. 俄罗斯套娃信封问题是一样类型的题目，这类题目的原型都是最长递增子序列问题。

题目要求在2个维度上(即长 + 宽)同时保持严格递增。那么我们可以先将其中一个维度排好序，以保证在一个维度上保持递增（此时并非严格递增）；之后就可以专注于处理另一个维度。

先对长宽排序，长升序排列，长相同，宽降序排列，这里可以使用二维数组的lambda表达式写法。

之后就是计算最长递增子序列。长已经按升序了，只需要判断宽。处理宽的问题就是处理最长递增子序列的问题。

相关系列题目可参考：【Leetcode】最长递增子序列问题及应用

方法一：动态规划

当前元素比之前的元素大，dp[i] = Math.max(dp[i], dp[j] + 1);

注：动态规划问题在数据量大的时候可能会出现超时问题。

方法二：贪心+二分查找

每次选择下一个递增元素的时候，都选择更小的结尾。使用二分查找，去找到这个更小的。

比如 {1, 5, 3, 4, 7} 5和3之间选择3作为当前递增序列的结尾元素。

dp[i]: 所有长度为i+1的递增子序列中, 最小的那个序列尾数。

对数组进行迭代, 依次判断每个数num将其插入dp数组相应的位置:

1. num > dp[res], 表示num比所有已知递增序列的尾数都大, 将num添加入dp数组尾部, 并将最长递增序列长度res加1
2. dp[i-1] < num <= dp[i], 只更新相应的dp[i]

最长递增子序列参考：【Leetcode】计算最长系列（动态规划）

参考代码

方法一：动态规划

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);}
}

方法二：贪心+二分查找

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);}
}

欢迎在评论区指正以及留下自己的更简洁的方法。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！