答案——腐烂的橘子算法题目

Nekron 发布于2019-08-23 15:54 / 3295人阅读

摘要：题目要求请戳假如一个格子的盒子里有个新鲜橘子，有个烂橘子。每隔一分钟我们去这个盒子里面数一数，直到烂橘子没有增加。没有新鲜的橘子，返回分钟数。如果这四个位置部分位置有新鲜的橘子，那么腐烂还会继续。

题目要求请戳

假如一个M x M 格子的盒子里有 n （n > 0）个新鲜橘子，有 m 个烂橘子。每隔一分钟我们去这个盒子里面数一数，直到烂橘子没有增加。结果就是：

1.并且还有新鲜的橘子，返回 -1。

2.没有新鲜的橘子，返回分钟数。

第一步将二维数组初始化为一维数组：

function initData(a){
  var 
    result = [],
    n = 0,
    m = 0,
    j = 0;
  for(j = 0; j < M; j++) {
    result[j * M + 0] = { status: a[j][0], willBletOthers: a[j][0] === 2 };
    result[j * M + 1] = { status: a[j][1], willBletOthers: a[j][1] === 2 };
    result[j * M + 2] = { status: a[j][2], willBletOthers: a[j][2] === 2 };

    if (a[j][0] == 1) {
      n += 1;
    }
    if (a[j][1] == 1) {
      n += 1;
    }
    if (a[j][2] == 1) {
      n += 1;
    }

    if (a[j][0] == 2) {
      m += 1;
    }
    if (a[j][1] == 2) {
      m += 1;
    }
    if (a[j][2] == 2) {
      m += 1;
    }
  }
  return {
    result: result,
    n: n,
    m: m
  };
}

每隔一分钟，一个放在 x 位置的格子的烂橘子，其他四个位置 x + 1、x - 1、x + M 、x - M，都会腐烂(注意边界)。如果这四个位置部分位置有新鲜的橘子，那么腐烂还会继续。然后继续观察其他位置，直到最后一个格子。下一分钟再来看

function blet(index, result){
    var bletNum = 0;
    if(-1< index + 1 && index + 1 < M*M && result[index + 1].status == 1){
        bletNum += 1;
        result[index + 1] = {status: 2, willBletOthers: false}
    }
    if(-1< index + M && index + M < M*M && result[index + M].status == 1){
        bletNum += 1;
        result[index + M] = {status: 2, willBletOthers: false}
    }
    
    if(-1< index - 1 && index - 1 < M*M && result[index - 1].status == 1){
        bletNum += 1;
        result[index - 1] = {status: 2, willBletOthers: true}
    }
    if(-1< index - M && index - M < M*M && result[index - M].status == 1){
        bletNum += 1;
        result[index - M] = {status: 2, willBletOthers: true}
    }
    return bletNum;
}
var 
  M = 3,
  rawData = [[2, 1, 1], [1, 1, 0], [0, 1, 1]];
  
function letGo(rawData){
    var data = initData(rawData),
        result = data.result,
        n = data.n,
        m = data.m,
        k,
        mins = 0,
        sum;

    if(m == 0 && n > 0){
        return -1;
    }
    if(m == 0 && n == 0){
        return 0;
    }
    while (n > 0 && m > 0) {
        mins += 1;
        sum = 0;
        for (k = 0; k < result.length; k++) {
            if (result[k].status == 2) {
                if (result[k].willBletOthers) {
                    sum += blet(k, result);
                } else {
                    result[k].willBletOthers = true;
                }
            }
        }

        if (sum === 0) {
            break;
        } else {
            n -= sum;
            m += sum;
        }
    }

    return mins;
}

console.log(letGo(rowData));

云服务器 GPU云服务器贪心算法的题目算法题目c语言算法导论答案最优化理论算法答案

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/102526.html

Java重构-策略模式、状态模式、卫语句

摘要：前言当代码中出现多重语句或者语句时。代替多重分支这个情况的代替方式是可以为晴天时处理逻辑下雨时处理逻辑阴天时处理逻辑策略模式使用策略模式可以代替多重和语句，让代码维护变得更加简单。状态模式允许一个对象在其内部状态改变的时候改变其行为。前言当代码中出现多重if-else语句或者switch语句时。弊端之一：如果这样的代码出现在多处，那么一旦出现需求变更，就需要把所有地方的if-els...

Sourcelink 2019-08-16 11:01 评论0 收藏0
从一个京东的实习生招聘题目讨论算法的选择

摘要：生日礼物题目来源京东实习生招聘原题链接可在线提交赛码网题目描述的生日快到了，这一次，小东决定为送一份特别的生日礼物为其庆生。小东计划送一个生日卡片，并通过特别的包装让永远难忘。最近2个月时间都比较忙，另外还有些其他的事情，几乎没有怎么做题和写文章了，害怕自己又开始懒散起来了，所以还是督促自己不断地学习和练习编码。最近还需要好好学下python面向对象的一些知识了。今天我们来分析一个J...

894974231 2019-07-25 12:02 评论0 收藏0
【周刊-2】三年大厂面试官-前端面试题（偏难）

摘要：前言在大厂工作了年，当了年的前端面试官，把大厂常问的面试题与答案汇总在我的中。第题如何劫持的请求，提供思路难度阿里腾讯很多人在上搜索前端面试详解，把答案倒背如流，但是问到如何劫持请求的时候就一脸懵逼，是因为还是停留在理论性阶段。前言在大厂工作了6年，当了3年的前端面试官，把大厂常问的面试题与答案汇总在我的Github中。希望对大家有所帮助，助力大家进入自己理想的企业。项目地址是：git...

silvertheo 2019-05-23 16:26 评论0 收藏0
【周刊-2】三年大厂面试官-前端面试题（偏难）

摘要：前言在大厂工作了年，当了年的前端面试官，把大厂常问的面试题与答案汇总在我的中。第题如何劫持的请求，提供思路难度阿里腾讯很多人在上搜索前端面试详解，把答案倒背如流，但是问到如何劫持请求的时候就一脸懵逼，是因为还是停留在理论性阶段。前言在大厂工作了6年，当了3年的前端面试官，把大厂常问的面试题与答案汇总在我的Github中。希望对大家有所帮助，助力大家进入自己理想的企业。项目地址是：...

madthumb 2019-08-23 16:56 评论0 收藏0