二叉树解决俄罗斯套娃的尝试
BIGBIGGUAI 人气:0给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：
输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/russian-doll-envelopes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
package leetcode;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/*
Author：Samba
Time ：2021年3月5日
Data：下午4:40:45
*/
public class t354_2 {
public static void main(String[] args) {
int[][] envelopes ={{46,89},{50,53},{52,68},{72,45},{77,81}};
Solution s = new Solution();
//s.maxEnvelopes(envelopes);
System.out.println(s.maxEnvelopes(envelopes));
}
}
class Solution {
Map<int[], int[][]> Map;
int[] MaxInt ={Integer.MAX_VALUE,Integer.MAX_VALUE};
public int maxEnvelopes(int[][] envelopes) {
Map = new HashMap<>();
int[][] envelopes1 = Arrays.copyOf(envelopes,envelopes.length);
int[][] envelopes2 = Arrays.copyOf(envelopes,envelopes.length);
envelopes1 = sort1(envelopes1);envelopes2 = sort2(envelopes2);
//envelopes2 = sort2(envelopes);
//构建节点的左节点
for (int i=0;i<envelopes1.length;i++) {
int[][] temp = new int[3][2];
int[] o = {0,0};
temp[2] = o;
if(i == envelopes1.length-1) {
temp[0] = null;
}else {
temp[0] = envelopes1[i+1];
}
Map.put(envelopes1[i], temp);
}
//构建节点的右节点
for (int i=0;i<envelopes2.length;i++) {
int[][] temp = Map.get(envelopes2[i]);
if(i == envelopes2.length-1) {
temp[1] = null;
}else {
temp[1] = envelopes2[i+1];
}
Map.remove(envelopes2[i]);
Map.put(envelopes2[i], temp);
}
int max = findMax(envelopes1[0],1,MaxInt);
return max;
}
public int findMax(int[] index,int max,int[] remain) {
int[][] temp = Map.get(index);
int[] t = Arrays.copyOf(index,index.length);
int max1,max2;
if(remain!=MaxInt) {
index = remain;
}
if(temp[0]==null||temp[2][0] == 1||temp[2][1] == 1) {
max1 = max;
}else {
temp[2][0] = 1;
Map.put(t, temp);
if(index[1]<temp[0][1]&&index[0]<temp[0][0]){
max1 = findMax(temp[0], max+1,MaxInt);
}else {
max1 = findMax(temp[0], max,index);
temp[2][0] = 0;
Map.put(t, temp);
}
}
if(temp[1]==null||temp[2][1] == 1||temp[2][0] == 1||temp[0] == temp[1]) {
max2 = max;
}else {
temp[2][1] = 1;Map.put(t, temp);
if(index[0]<temp[1][0]&&index[1]<temp[1][1]) {
max2 = findMax(temp[1], max+1,MaxInt);
}else {
max2 = findMax(temp[1], max,index);
temp[2][1] = 0;Map.put(t, temp);
}
}
if(max1>max2) {
return max1;
}else {
return max2;
}
}
public static int[][] sort1(int[][] arrs){
for(int i = 0; i < arrs.length - 1 ; i++){
int min = i; // 遍历的区间最小的值
for (int j = i + 1; j < arrs.length ;j++){
if(arrs[j][0] < arrs[min][0]||
(arrs[j][0] == arrs[min][0]&& arrs[j][1] < arrs[min][1])){
// 找到当前遍历区间最小的值的索引
min = j;
}
}
if(min != i){
// 发生了调换
int[] temp = arrs[min];
arrs[min] = arrs[i];
arrs[i] = temp;
}
}
return arrs;
}
public static int[][] sort2(int[][] arrs){
for(int i = 0; i < arrs.length - 1 ; i++){
int min = i; // 遍历的区间最小的值
for (int j = i + 1; j < arrs.length ;j++){
if(arrs[j][1] < arrs[min][1]||
(arrs[j][1] == arrs[min][1]&& arrs[j][0] < arrs[min][0])){
// 找到当前遍历区间最小的值的索引
min = j;
}
}
if(min != i){
// 发生了调换
int[] temp = arrs[min];
arrs[min] = arrs[i];
arrs[i] = temp;
}
}
return arrs;
}
}
虽然码了好久还是失败了，但是也不是没有收获，抽丝剥茧的乐趣还是不错的
用Map构建数据结构，浅克隆和深克隆问题，设置标记防止死循环...
顺便熟悉了一下debug...
加载全部内容