【俄罗斯套娃信封问题】【堆积木】

leetcode剑指offer

俄罗斯套娃信封问题

https://leetcode-cn.com/problems/russian-doll-envelopes/

 给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
说明:
 不允许旋转信封。
示例:
输入:
  envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出:
  3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

代码

思路1：动态规划
以envelopes =[[4,5],[4,6],[6,7],[2,3],[1,1]]为例；

  • 1.先将envelopes的长度进行从小到大排序，在长度相等的情况下，对它的宽度也进行从小到大排序得到 [1,1],[2,3],[4,5],[4,6],[4,7]

    Arrays.sort(envelopes, new Comparator<int[]>(){

       public int compare(int[] o1,int [] o2){

        //判断第一个元素是否相等

         if (o1[0] == o2[0]) {

          return o1[1] - o2[1];

         } else {

          return o1[0] - o2[0];

        }

        }

      });

  • 2.因为f[i]表示第i个信封可以嵌套的最大信封数,结果要求最多有多少个信封，最多信封为嵌套信封加本身的信封，故将其每个位置初始化为1。

  • 3.for语句嵌套，如果第i个信封的长度和宽度都大于第j个信封，则可以把它嵌套到i里面信封里面，所以此时第i个信封可以嵌套的最大信封数为f[i] = Math.max(f[i],f[j]+1);

  • 4.最多的信封数即为f[]里面存在的最大的数。返回结果。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public static int maxEnvelopes(int[][] envelopes) {
        // write your code here
        if(envelopes==null||envelopes.length==0){
            return 0;
        }
        //长度从小到大排序，在长度相等的情况下，高度从小到大排序
        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] o1,int [] o2){
                //判断第一个元素是否相等
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                } else {
                    return o1[0] - o2[0];
                }
            }
        });
        int n=envelopes.length;
        //f[i]表示第i个信封可以嵌套的最大信封数
        //5个信封的初始化
        int[] f=new int[n];
        int res=0;
        for(int i=0;i<n;i++){
            f[i]=1;
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                //第i个信封的长度和宽度都大于第j个信封，则可以把它嵌套到i里面信封里面
                if(envelopes[j][0]<envelopes[i][0]&&envelopes[j][1]<envelopes[i][1]){
                    f[i]=Math.max(f[i],f[j]+1);
                }
            }
            res=Math.max(res,f[i]);
        }
        return res;
    }
}

思路2：

  • 1.envelopes的长度进行从小到大排序，在长度相等的情况下，对它的宽度也进行从大到小排序得到 [1,1],[2,3],[4,6],[4,5],[4,7]，最后问题转换成求 1，3，6，5，7中的最大递增子序列
  • 2.定义一个ends数组。ends[i]代表遍历到目前为止，所有长度为i+1的递增子序列的最小结尾数。初始化ends[0] = 1;即1 ，3，6，5，7遍历到1的时候，长度为1的递增子序列的最小结尾数就是1。

  • 一次更新ends数组，for循环遍历1，3，6，5，7，从i=1遍历到尾部。在ends里面进行二分查找，查找此刻dots[i]在ends的哪个部分，如果是没更新到的地方则更新此时的ends[i];如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    for (int i = 1; i < dots.length; i++) {
         l = 0;
         r = right;
         //当要算以dots[i]结尾的最长递增子序列时，
         //二分查找去ends里面更新长度为i的最小结尾数
         while (l <= r) {
             mid = (l + r) / 2;
             if (dots[i].h > ends[mid]) {
                 l = mid + 1;
             } else {
                 r = mid - 1;
             }
         }
         right = Math.max(right, l);
         //更新最小结尾数
         ends[l] = dots[i].h;
     }

第一次遍历: i = 1; l = r =mid = 0; 
      dot[1].h = 3 > ends[0] = 1
      l = 1
      right = 1;ends[1] = 3;
第二次遍历: i = 2; l=0,r = 1,mid = 0;
      dot[2].h = 6 > ends[0] = 1
      l = 1
      mid = 1,l =2
      right = 2,end[2] = 6;
  …

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.Arrays;
import java.util.Comparator;

/**
 * Created by qiulig on 2019/7/29
 */
public class Main_354 {
    //执行用时 :33 ms, 在所有 Java 提交中击败了87.11%的用户
    //内存消耗 :47.1 MB, 在所有 Java 提交中击败了80.68%的用户
    public static void main(String[] args) {
        int[][] envelopes=new int[][]{{4,5},{4,6},{6,7},{2,3},{1,1}};
        System.out.print(maxEnvelopes(envelopes));
    }
        public static class Dot {
            public int w;
            public int h;

            public Dot(int weight, int hight) {
                w = weight;
                h = hight;
            }
        }
        //长度从小到大排序，在长度相等的情况下，高度从大到小排序
        public static class DotComparator implements Comparator<Dot> {
            @Override
            public int compare(Dot o1, Dot o2) {
                if (o1.w != o2.w) {
                    return o1.w - o2.w;
                } else {
                    return o2.h - o1.h;
                }
            }
        }
        public static int maxEnvelopes(int[][] es) {
            if (es == null || es.length == 0 || es[0] == null || es[0].length != 2) {
                return 0;
            }
            Dot[] dots = new Dot[es.length];
            for (int i = 0; i < es.length; i++) {
                dots[i] = new Dot(es[i][0], es[i][1]);
            }
            //排序之后长度w： 1  2  4  4  6
            //    对应高度h： 1  3  6  5  7
            //最后问题转换成求 1  3  6  5  7中的最大递增子序列
            Arrays.sort(dots, new DotComparator());
            //ends[i]代表遍历到目前为止，所有长度为i+1的递增子序列的最小结尾数
            int[] ends = new int[es.length];
            //代表第一个信封的长度为1的最小结尾数是dots[0].h
            ends[0] = dots[0].h;

            int right = 0;
            int l = 0;
            int r = 0;
            int mid = 0;
            for (int i = 1; i < dots.length; i++) {
                l = 0;
                r = right;
                //当要算以dots[i]结尾的最长递增子序列时，
                //二分查找去ends里面更新长度为i的最小结尾数
                while (l <= r) {
                    mid = (l + r) / 2;
                    if (dots[i].h > ends[mid]) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                right = Math.max(right, l);
                //更新最小结尾数
                ends[l] = dots[i].h;
            }
            return right + 1;
        }
    }

如果信封可旋转，则我们可以把输入稍微定死，输入[w,h]定死了大的数的代表的是信封的长，小的数代表的是信封的宽，即如果输入w<h，则把他们互换一下位置。

搭积木

https://www.nowcoder.com/questionTerminal/55371b74b2f243e3820e57ee4c7b5504

 小明有一袋子长方形的积木，如果一个积木A的长和宽都不大于另外一个积木B的长和宽，则积木A可以搭在积木B的上面。好奇的小明特别想知道这一袋子积木最多可以搭多少层，你能帮他想想办法吗？ 定义每一个长方形的长L和宽W都为正整数，并且1 <= W <= L <= INT_MAX, 袋子里面长方形的个数为N, 并且 1 <= N <= 1000000. 假如袋子里共有5个积木分别为 (2, 2), (2, 4), (3, 3), (2, 5), (4, 5), 则不难判断这些积木最多可以搭成4层, 因为(2, 2) < (2, 4) < (2, 5) < (4, 5)。

  • 同如上思路2，先将宽度进行排序，将问题转化成求长度的最大递增子序列。

    1
    2
    >   
    >

package 拼多多;
import java.util.*;
public class Main_3{
static class Rectangle{
private int Weight; //宽度
private int Len; //长度
public Rectangle(int x, int y){
Weight = x;
Len = y;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList list = new ArrayList<>();
for(int i = 0; i < n; i++){
int x = sc.nextInt();
int y = sc.nextInt();
Rectangle r = new Rectangle(x, y);
list.add(r);
}
//排序，宽度从小到大，在宽度一样的情况下，长度从小到大
Collections.sort(list, new Comparator(){
@Override
public int compare(Rectangle o1, Rectangle o2) {
if(o1.Weight == o2.Weight)
return o1.Len - o2.Len;
else
return o1.Weight -o2.Weight;
}
});
//最后问题转换成求长度的最大递增子序列
//用于代表遍历到目前为止，所有长度为i+1的递增子序列的最小结尾数
int[] arr = new int[n];
int max = 1;
arr[0] = list.get(0).Len;
for(int i = 1; i < n; i++){
if(list.get(i).Len >= arr[max-1]){
arr[max++] = list.get(i).Len;
}else{
int left = 0;
int right = max -1;
int L = list.get(i).Len;
while(left < right){
int mid = (left + right) >> 1;
if(arr[mid] == L){
left = mid;
break;
}else if(arr[mid] > L){
right–;
}else
left++;
}
arr[left] = L;
}
}
System.out.println(max);
}
}

在这里插入图片描述

拼多多学霸批的堆积木

已知N个积木的长度，当堆积木的时候，要求每层积木的长度严格比其下方的积木小，而且每块积木只能承受自身重量的7倍，问可以堆多高的积木
给了个测试用例
输入：
10
1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 10
输出：9

  • 个人思路觉得这题还是上面堆积木，俄罗斯套信封题一样，只是积木的长度 = 俄罗斯信封的长度，积木的重量*7 = 俄罗斯信封的高度。应该是这样子叭叭叭~~~~~~小菜鸟不知了。。。。。。。

本文标题:【俄罗斯套娃信封问题】【堆积木】

文章作者:qiulig

发布时间:2019-07-30, 18:40:48

最后更新:2019-07-30, 18:47:32

文章字数:2.3k

原始链接:http://blogs.qiulig.website/2019/07/【俄罗斯套娃信封问题】【堆积木】/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 俄罗斯套娃信封问题
  2. 2. 代码
  3. 3. 搭积木
  4. 4. 拼多多学霸批的堆积木
| 139.6k