答案——腐爛的橘子算法題目

Nekron 發布于2019-08-23 15:54 / 3296人閱讀

摘要：題目要求請戳假如一個格子的盒子里有個新鮮橘子，有個爛橘子。每隔一分鐘我們去這個盒子里面數一數，直到爛橘子沒有增加。沒有新鮮的橘子，返回分鐘數。如果這四個位置部分位置有新鮮的橘子，那么腐爛還會繼續。

題目要求請戳

假如一個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語言算法導論答案最優化理論算法答案

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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