iT邦幫忙

2024 iThome 鐵人賽

DAY 10
0

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:
• You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
• Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
• Once you reach a tree with fruit that cannot fit in your baskets, you must stop.
Given the integer array fruits, return the maximum number of fruits you can pick.

你正拜訪了一個農場,農場中有一排果樹,由左至右排列。現在使用一個整數陣列代表這些果樹,fruits[i]代表果樹的品種。
你想要盡可能收集更多的水果,然而,農場的主人有一些規則需要你遵守:

  • 你只有兩個籃子,每個籃子只能裝同一種的水果,同一籃子內裝的水果數量並無限制
  • 你可以從任一棵果樹開始採集,一旦選擇第一顆樹後,只能往右側的方向接著採集接下來的每一棵果樹(包含第一棵果樹)
  • 一旦採集到第三種果樹、而不能將水果進籃子時,你必須停止採集
    基於以上規則,回傳你可以採集的水果最大數量。

https://ithelp.ithome.com.tw/upload/images/20240822/20168667pry61syRs7.png


如果使用暴力直覺破解法,一樣使用兩個迴圈,外層迴圈跑整個fruits,內層迴圈計算可以採集水果數量的總合。

【Concept】改使用Sliding window解題,先定義好window size跟pointer(a.k.a sliding window的起始點),並使用hash map記錄目前已經摘採的水果種類及數量,直到找出可以採集水果數量的最大值。

(1)設定map,記錄採集的水果種類與數量,可視為題目中的籃子
(2)設定window size,就是可以採集果樹的範圍
(3)設定sliding window的起始點start,也就是開始採集第一棵果樹的起點
(4)使用for loop開始迭代,從第一棵果樹的位置開始跑,這時將for loop裡面的end作為window的結束點,

  • (4-1)狀況一: 如果目前兩個籃子其中一個沒有裝水果 且 有裝水果的那個籃子裡也不是裝同種水果
    • (4-1-2)將水果裝進空的籃子,並且計算max與end的距離,取得目前採集的果樹最大範圍
  • (4-2)狀況二: 如果當前要採集的水果籃子裡面已經存在
    • (4-2-2)將水果裝進籃子,並且計算max與end的距離,取得目前採集的果樹最大範圍
  • (4-3)狀況三: 如果當前要採集的水果跟兩個籃子內裝的都不同
    • (4-3-1)清空其中一個籃子,重新把當前的水果裝進籃子,以及保留前一棵果樹的水果,把window的起點改為前一棵果樹
    • (4-3-2)為了排除前面幾棵果樹為同種的可能性,在這邊必須檢查,若相同品種則將window的起始點start往前移動到品種不同的果樹為止,這樣做的目的是為了確保可以採集到最大的範圍
    • (4-3-3)最後,一樣計算max與end的距離,取得目前採集的果樹最大範圍

(5)回傳可採集的範圍最大值

來解題吧

var totalFruit = function(fruits) {
    // Make a map for recording fruit types
    let map = new Map();
    // set sliding window size
    let max = 0;
    // set pointer
    let start = 0;
    // iterate the fruit trees
    for (let end = 0;end < fruits.length;end++){
        //if fruit type less than 2 types and not existed in Map
        if (map.size < 2 && !map.has(fruits[end])){
            // add to map
            map.set(fruits[end], true);
            // calculate window size
            max = Math.max(max, (end - start + 1));
        }
        //fruit type already existed
        else if(map.has(fruits[end])){
            max = Math.max(max, (end- start + 1));
        }
        //map size = 2, fruit type not existed in map
        else if (!map.has(fruits[end])){
            map.clear();
            map.set(fruits[end], true);
            map.set(fruits[end - 1], true);
            start = end - 1;
            //examine new start real index
            while(fruits[start] == fruits[start - 1]){
                start--;
            }
            max = Math.max(max, end - start +1);
        }
    }
    return max;
};

上一篇
[Day9]Maximum Average Subarray I
下一篇
[Day11] Pattern : K-way Merge
系列文
刷題筆記30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言