[Swift]LeetCode904.水果成篮|FruitIntoBaskets

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10608277.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

In a row of trees, the i-th tree produces fruit with type tree[i].

You start at any tree of your choice, then repeatedly perform the following steps:

Add one piece of fruit from this tree to your baskets. If you cannot, stop.
Move to the next tree to the right of the current tree. If there is no tree to the right, stop.

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

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.

What is the total amount of fruit you can collect with this procedure?

Example 1:

Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].

Example 2:

Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].

Example 3:

Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].

Example 4:

Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.

Note:

1 <= tree.length <= 40000
0 <= tree[i] < tree.length

在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：

把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
移动到当前树右侧的下一棵树。如果右边没有树，就停下来。

请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。

你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
用这个程序你能收集的水果总量是多少？

示例 1：

输入：[1,2,1]
输出：3
解释：我们可以收集 [1,2,1]。

示例 2：

输入：[0,1,2,2]
输出：3
解释：我们可以收集 [1,2,2].
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。

示例 3：

输入：[1,2,3,2,2]
输出：4
解释：我们可以收集 [2,3,2,2].
如果我们从第一棵树开始，我们将只能收集到 [1, 2]。

示例 4：

输入：[3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：我们可以收集 [1,2,1,1,2].
如果我们从第一棵树或第八棵树开始，我们将只能收集到 4 个水果。

提示：

1 <= tree.length <= 40000
0 <= tree[i] < tree.length

720ms

 1 class Solution {
 2     func totalFruit(_ tree: [Int]) -> Int {
 3         var one = Int.min
 4         var two = Int.min
 5         var lastIndex = Int.min
 6         var last = Int.min
 7         var maxv = 0
 8         var cur = 0
 9         for i in tree.indices {
10             if one == Int.min {
11                 one = tree[i]
12                 lastIndex = i
13                 last = one
14                 cur = 1
15                 continue
16             }
17             if tree[i] == one {
18                 if last != one {
19                     last = one
20                     lastIndex = i
21                 }
22                 cur += 1
23                 continue
24             }
25 
26             if two == Int.min {
27                 two = tree[i]
28                 last = two
29                 lastIndex = i
30                 cur += 1
31                 continue
32             }
33 
34             if two == tree[i] {
35                 if last != two {
36                     last = two
37                     lastIndex = i
38                 }
39                 cur += 1
40                 continue
41             }
42 
43             maxv = max(maxv, cur)
44             cur = i - lastIndex + 1
45             if last == one {
46                 two = tree[i]
47             }
48             else {
49                 one = tree[i]
50             }
51             lastIndex = i
52             last = tree[i]
53 
54         }
55 
56         return max(maxv, cur)
57     }
58 }

728ms

 1 class Solution {
 2     func totalFruit(_ tree: [Int]) -> Int {
 3         guard tree.count >= 3 else {
 4             return tree.count
 5         }
 6         
 7         var minIndex = 0
 8         var maxIndex = minIndex
 9         var maxValue = 0
10         
11         for i in 0..<tree.count where !(tree[i] == tree[minIndex] || tree[i] == tree[maxIndex]) {
12             maxValue = max(maxValue, i - minIndex)
13             minIndex = i - 1
14             
15             while minIndex > 0 && tree[minIndex - 1] == tree[minIndex] {
16                 minIndex -= 1
17             }
18             
19             maxIndex = i
20         }
21         
22         return max(maxValue, tree.count - minIndex)
23     }
24 }

Runtime: 744 ms

Memory Usage: 19.3 MB

 1 class Solution {
 2     func totalFruit(_ tree: [Int]) -> Int {
 3         var box1 = 0
 4         var box2 = 0
 5         var sum = 0
 6         var count = 0
 7         var start = 0
 8         while start < tree.count - sum {
 9             box1 = tree[start]
10             box2 = -1
11             count = 0
12             count += 1
13             for i in (start + 1)..<tree.count {
14                 if tree[i] == box1 {
15                     count += 1
16                     continue
17                 }
18                 if box2 < 0 {
19                     box2 = tree[i]
20                     count += 1
21                     start = i
22                     continue
23                 } else if box2 == tree[i] {
24                     count += 1
25                     continue
26                 }
27                 break
28             }
29             sum = max(sum, count)
30         }
31         return sum
32     }
33 }

Runtime: 752 ms

Memory Usage: 19.4 MB

 1 class Solution {
 2     func totalFruit(_ tree: [Int]) -> Int {
 3         var res:Int = 0
 4         var cur:Int = 0
 5         var count_b:Int = 0
 6         var a:Int = 0
 7         var b:Int = 0
 8         for c in tree
 9         {
10             cur = c == a || c == b ? cur + 1 : count_b + 1
11             count_b = c == b ? count_b + 1 : 1
12             if b != c
13             {
14                 a = b
15                 b = c
16             }
17             res = max(res, cur)
18         }
19         return res       
20     }
21 }

768ms

 1 class Solution {
 2     func totalFruit(_ tree: [Int]) -> Int {
 3         var tempMax = 0
 4         var left = 0, right = 0, lastA = 0, lastB = 0
 5         let count = tree.count
 6         guard count > 0 else {
 7             return 0
 8         }
 9         var typeA = tree[0]
10         var typeB:Int?  
11         while right < count {
12             let type = tree[right]
13             if type == typeA {
14                 lastA = right
15                 tempMax = max(right - left + 1, tempMax)
16                 right += 1
17             }else if let _ = typeB {
18                 if typeB == type {
19                     lastB = right
20                     tempMax = max(right - left + 1, tempMax)
21                     right += 1
22                 }else{
23                     if typeA == tree[right - 1] {
24                         typeB = type
25                         left = lastB + 1
26                     }else{
27                         typeA = type
28                         left = lastA + 1
29                     }
30                 }
31             }else{
32                 typeB = type
33                 lastB = right
34                 tempMax = max(right - left + 1, tempMax)
35                 right += 1
36             }
37         }  
38         return tempMax
39     }
40 }

776ms

 1 class Solution {
 2     func totalFruit(_ tree: [Int]) -> Int {
 3         var s = Set<Int>()
 4         var ans = 0
 5         var pre = 0
 6         for idx in 0..<tree.endIndex {
 7             s.insert(tree[idx])
 8             if s.count > 2 {
 9                 pre = idx - 1
10                 while pre > 0, tree[pre - 1] == tree[pre] {
11                     pre -= 1
12                 }
13                 s.remove(tree[pre - 1])
14             } else {
15                 ans = max(ans, idx - pre + 1)
16             }
17         }
18         return ans 
19     }
20 }

788ms

 1 class Solution {
 2     func totalFruit(_ tree: [Int]) -> Int {
 3         var prev = [-1, 0]
 4         var curr = [-1, 0]
 5         var maxFruits = 0
 6         
 7         for f in tree {
 8             if f == curr[0] {
 9                 curr[1] += 1
10             } else {
11                 (curr, prev) = (prev, curr)
12                 if f == curr[0] {
13                     prev[1] += curr[1]
14                 } else {
15                     maxFruits = max(maxFruits, prev[1] + curr[1])
16                 }
17                 curr = [f, 1]
18             }
19         }
20         return max(maxFruits, prev[1] + curr[1])        
21     }
22 }

792ms

 1 class Solution {
 2     func totalFruit(_ tree: [Int]) -> Int {
 3         if tree.count <= 1 {
 4             return tree.count
 5         }
 6         var distance = [Int]()
 7         distance.append(1)
 8         for i in 1..<tree.count {
 9             if tree[i] == tree[i - 1] {
10                 distance.append(distance[i - 1] + 1)
11             } else {
12                 distance.append(1)
13             }
14         }
15         var result = 1
16         var pair: Set<Int> = [tree[0]]
17         var maxCollect = Int.min
18         for i in 1..<tree.count {
19             pair.insert(tree[i])
20             if pair.count <= 2 {
21                 result += 1
22             } else {
23                 result = distance[i - 1] + 1
24                 pair = [tree[i], tree[i - 1]]
25             }
26             maxCollect = max(maxCollect, result)
27         }
28         return maxCollect
29     }
30 }