{"id":3977,"date":"2018-09-15T20:15:31","date_gmt":"2018-09-16T03:15:31","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3977"},"modified":"2018-09-15T20:26:42","modified_gmt":"2018-09-16T03:26:42","slug":"leetcode-904-fruit-into-baskets","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-904-fruit-into-baskets\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 904. Fruit Into Baskets"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

In a row of trees, the\u00a0i<\/code>-th tree\u00a0produces\u00a0fruit with type\u00a0tree[i]<\/code>.<\/p>\n

You\u00a0start at any tree\u00a0of your choice<\/strong>, then repeatedly perform the following steps:<\/p>\n

    \n
  1. Add one piece of fruit from this tree to your baskets.\u00a0 If you cannot, stop.<\/li>\n
  2. Move to the next tree to the right of the current tree.\u00a0 If there is no tree to the right, stop.<\/li>\n<\/ol>\n

    Note that you do not have any choice after the initial choice of starting tree:\u00a0you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.<\/p>\n

    You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.<\/p>\n

    What is the total amount of fruit you can collect with this procedure?<\/p>\n

    Example 1:<\/strong><\/p>\n

    Input: <\/strong>[1,2,1]<\/span>\r\nOutput: <\/strong>3<\/span>\r\nExplanation: <\/strong>We can collect [1,2,1].\r\n<\/pre>\n
    \n
    Example 2:<\/strong><\/p>\n
    Input: <\/strong>[0,1,2,2]<\/span>\r\nOutput: <\/strong>3\r\n<\/span>Explanation: <\/strong>We can collect [1,2,2].\r\nIf we started at the first tree, we would only collect [0, 1].\r\n<\/pre>\n
    \n
    Example 3:<\/strong><\/p>\n
    Input: <\/strong>[1,2,3,2,2]<\/span>\r\nOutput: <\/strong>4\r\n<\/span>Explanation: <\/strong>We can collect [2,3,2,2].\r\nIf we started at the first tree, we would only collect [1, 2].\r\n<\/pre>\n
    \n
    Example 4:<\/strong><\/p>\n
    Input: <\/strong>[3,3,3,1,2,1,1,2,3,3,4]<\/span>\r\nOutput: <\/strong>5\r\n<\/span>Explanation: <\/strong>We can collect [1,2,1,1,2].\r\nIf we started at the first tree or the eighth tree, we would only collect 4 fruits.\r\n<\/pre>\n<\/div>\n<\/div>\n<\/div>\n
    Note:<\/strong><\/p>\n
      \n
    1. 1 <= tree.length <= 40000<\/code><\/li>\n
    2. 0 <= tree[i] < tree.length<\/code><\/li>\n<\/ol>\n
      Solution: Hashtable + Sliding window<\/strong><\/h1>\n
      Time complexity: O(n)<\/p>\n
      Space complexity: O(1)<\/p>\n
      Keep track of the last index of each element. If a third type of fruit comes in, the new window starts after the fruit with smaller last index. Otherwise extend the current window.<\/p>\n
      [1 3 1 3 1 1] 4 1 4 … <- org window, 3 has a smaller last index than 1.<\/p>\n
      1 3 1 3 [1 1 4] 1 4 … <- new window<\/p>\n
      \n
      C++<\/h2>\n
      \n\n
      \/\/ Author: Huahua, 144 ms\r\nclass Solution {\r\npublic:\r\n  int totalFruit(vector<int>& tree) {        \r\n    map<int, int> idx; \/\/ {fruit -> last_index}\r\n    int ans = 0;\r\n    int cur = 0;\r\n    for (int i = 0; i < tree.size(); ++i) {\r\n      int f = tree[i];\r\n      if (!idx.count(f)) {\r\n        if (idx.size() == 2) {\r\n          auto it1 = begin(idx);\r\n          auto it2 = next(it1);\r\n          if (it1->second > it2->second) swap(it1, it2);\r\n          cur = i - it1->second - 1;          \r\n          idx.erase(it1);          \r\n        }       \r\n      }      \r\n      idx[f] = i;      \r\n      ans = max(++cur, ans);\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      Problem In a row of trees, the\u00a0i-th tree\u00a0produces\u00a0fruit with type\u00a0tree[i]. You\u00a0start at any tree\u00a0of your choice, then repeatedly perform the following steps: Add one piece…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[82,215],"class_list":["post-3977","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-sliding-window","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3977","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3977"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3977\/revisions"}],"predecessor-version":[{"id":3983,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3977\/revisions\/3983"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3977"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3977"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3977"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}