V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Breadykid
V2EX  ›  2018

CTO 让我们老人做做公司现在招聘的面试题,一个二维数组的题目, orz

  •  
  •   Breadykid · 2018-09-14 14:27:56 +08:00 · 2194 次点击
    这是一个创建于 2272 天前的主题,其中的信息可能已经有所发展或是发生改变。

    /**

    • 有若 7 个球框,每个球筐最多能放 3 个球,可以不放球。
    • 7 个球筐上依次写着[红球,橙球,黄球,蓝球,铁球,木球,玻璃球],
    • 表示这个球筐里对球的限定。现在有 20 个球,
    • 规格如下:
    • 红铁球 15g,红铁球 26g,
    • 橙铁球 25g,
    • 黄铁球 18g,黄铁球 13g,
    • 蓝铁球 33g,
    • 红木球 31g,红木球 36g,
    • 橙木球 11g,橙木球 25g,
    • 黄木球 7g,黄木球 18g,
    • 蓝木球 10g,
    • 红玻璃球 3g,
    • 橙玻璃球 21g,橙玻璃球 16g,
    • 黄玻璃球 45g,黄玻璃球 29g,
    • 蓝玻璃球 3g,蓝玻璃球 7g
    • 请问组成最大重量的 N 个球筐限定的组合是什么?
    • 请写出伪代码。 */

    我写了一半的代码,不知如何继续下去,求大佬

    public class Ball {
    	private Color color;
    	private Meterial meterial;
    	private int weight;
    }
    
    public enum Color {
    	YELLOW("YELLOW","黄色"),
    	ORANGE("ORANGE","橙色"),
    	RED("RED","红色"),
    	BLUE("BLUE","蓝色");
    }
    
    public enum Meterial {
    	IRON("IRON","铁"),
    	WOOD("WOOD","木"),
    	GLASS("GLASS","玻璃");
    }
        
    public void calculate(Ball[] balls) {
        int totalWeight = 0;
        List<Ball> red = new ArrayList<>();
        List<Ball> orange = new ArrayList<>();
        List<Ball> yellow = new ArrayList<>();
        List<Ball> blue = new ArrayList<>();
        List<Ball> iron = new ArrayList<>();
        List<Ball> wood = new ArrayList<>();
        List<Ball> glass = new ArrayList<>();
    
        HashMap<String,List<Ball>> basketsMap = new HashMap();
        basketsMap.put(Color.RED.getKey(),red);
        basketsMap.put(Color.ORANGE.getKey(),orange);
        basketsMap.put(Color.YELLOW.getKey(),yellow);
        basketsMap.put(Color.BLUE.getKey(),blue);
        basketsMap.put(Meterial.IRON.getKey(),iron);
        basketsMap.put(Meterial.WOOD.getKey(),wood);
        basketsMap.put(Meterial.GLASS.getKey(),glass);
    
        for (int i=0; i<balls.length; i++) {
            if (basketsMap.containsKey(balls[i].getColor().getKey())) {
                List<Ball> color = basketsMap.get(balls[i].getColor().getKey());
                if (color.size()<3) {
                    color.add(balls[i]);
                    totalWeight+=balls[i].getWeight();
                }
                else {
                    System.out.println(basketsMap.get(balls[i].getColor().getKey()).toArray().toString());
                    basketsMap.remove(balls[i].getColor().getKey());
                }
            }
    
            if (basketsMap.containsKey(balls[i].getMeterial().getKey())) {
                List<Ball> material = basketsMap.get(balls[i].getMeterial().getKey());
                if (material.size()<3) {
                    material.add(balls[i]);
                    totalWeight+=balls[i].getWeight();
                }
                else {
                    System.out.println(basketsMap.get(balls[i].getMeterial().getKey()).toArray().toString());
                    basketsMap.remove(balls[i].getColor().getKey());
                }
            }
        }
    
    16 条回复    2018-09-14 16:57:18 +08:00
    w0000
        1
    w0000  
       2018-09-14 14:35:32 +08:00
    这个题目是不是没描述完整? 表示这个球筐里对球的限定 是什么意思?限定的是个数?
    Breadykid
        2
    Breadykid  
    OP
       2018-09-14 14:45:38 +08:00
    @w0000 意思是:7 个球筐上依次写着[红球,橙球,黄球,蓝球,铁球,木球,玻璃球],表示这个球筐里对球的限定,就是写着红球的框里可以放有“红色”属性的球的意思,可以放红木球,红铁球,红玻璃球,这样
    bzw875
        3
    bzw875  
       2018-09-14 15:04:50 +08:00
    请问组成最大重量的 N 个球筐限定的组合是什么?
    这句话什么意思啊,7*3=21,每个框都有球啊,不能不放
    maichael
        4
    maichael  
       2018-09-14 15:06:34 +08:00
    @bzw875 不需要把所有球都放进去的意思。
    maichael
        5
    maichael  
       2018-09-14 15:07:08 +08:00
    @w0000 限定的是比如“红球”就只能放红球或者红玻璃球之类的。
    cigarzh
        6
    cigarzh  
       2018-09-14 15:08:11 +08:00 via iPhone
    背包问题加了点限定?
    maichael
        7
    maichael  
       2018-09-14 15:18:16 +08:00
    说个最简单的思路,一个个球遍历,先找到那个框可以存放这个球,再判断这个框什么已经满了,如果满了再判断这个球是否比这个框里面三个都要轻,如果都要轻就找有没另一个框可以换。被替换下来的球重新进入队列。
    Breadykid
        8
    Breadykid  
    OP
       2018-09-14 15:23:09 +08:00
    @maichael 昂,我试下
    Breadykid
        9
    Breadykid  
    OP
       2018-09-14 15:25:54 +08:00
    @cigarzh 确实像背包问题,但我不知道怎么搞
    maichael
        10
    maichael  
       2018-09-14 15:27:24 +08:00
    @Breadykid 如果球先根据重量做一次排序的话,应该效率会高点。
    Deville
        11
    Deville  
       2018-09-14 15:30:38 +08:00
    咦,这道题,似曾相识
    uleh
        12
    uleh  
       2018-09-14 16:06:19 +08:00
    lz 你的题目归结一下就是下面这个二位数组。
    算最重的时候,就按给定的框遍历一下可能的取值,把最大的取出来就行了。
    例如给 N=2 (红球框,铁球框),就是下面这个矩阵 X[红]遍历一下最大的 3 个(26,36,3),然后 X[铁]遍历剩下最大的 3 个

    |红 |橙|黄|蓝|
    ------------------
    铁 |15,26|...
    ------------------
    木 |31,36|...
    ------------------
    玻璃 |3 |...
    Breadykid
        13
    Breadykid  
    OP
       2018-09-14 16:07:40 +08:00
    我最后的实现哇,如果求得是这个意思得话


    public void calculate(Ball[] balls) {

    final String[] colorType = {Color.RED.getKey(),Color.ORANGE.getKey(),Color.YELLOW.getKey(),Color.BLUE.getKey()};
    final String[] materialType = {Meterial.IRON.getKey(),Meterial.WOOD.getKey(),Meterial.GLASS.getKey()};

    // 质量排序
    for (int i = 0; i < balls.length; i++) {
    for (int j = 1; j < balls.length; j++) {
    int a = balls[i].getWeight();
    int b = balls[j].getWeight();
    if (i<j && a<b) {
    Ball temp = balls[i];
    balls[i] = balls[j];
    balls[j] = temp;
    }
    }
    }

    // color
    for (int n=0; n<colorType.length; n++) {
    int totalWeight = 0;
    final int count = 3;
    List<Ball> color = new ArrayList<>();
    for (int i=0; i<balls.length; i++) {
    if (colorType[n].equals(balls[i].getColor().getKey())) {
    if (color.size()<count) {
    System.out.println(balls[i].toString());
    color.add(balls[i]);
    totalWeight+=balls[i].getWeight();
    }
    }
    }
    System.out.println(String.format("%s 总质量 %s",colorType[n],totalWeight));
    }

    // material
    for (int n=0; n<materialType.length; n++) {
    int totalWeight = 0;
    final int count = 3;
    List<Ball> material = new ArrayList<>();
    for (int i=0; i<balls.length; i++) {
    if (materialType[n].equals(balls[i].getMeterial().getKey())) {
    if (material.size()<count) {
    System.out.println(balls[i].toString());
    material.add(balls[i]);
    totalWeight+=balls[i].getWeight();
    }
    }
    }
    System.out.println(String.format("%s 总质量 %s",materialType[n],totalWeight));
    }
    }
    uleh
        14
    uleh  
       2018-09-14 16:07:51 +08:00
    #12 修改一下说法,不是二维数组,算是个矩阵。因为你这个球之间其实没有交叉,比传统的背包问题其实还简单些。
    Breadykid
        15
    Breadykid  
    OP
       2018-09-14 16:09:50 +08:00
    @uleh 有道理昂
    xiaoxinxiaobai
        16
    xiaoxinxiaobai  
       2018-09-14 16:57:18 +08:00 via Android
    题都读不懂。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1140 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 18:53 · PVG 02:53 · LAX 10:53 · JFK 13:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.