KK's blog

LeetCode 312 Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

<pre> nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 315 + 358 + 138 + 181 = 167 </pre>

题目大意：

给定n个气球，下标为0到n-1。每个气球上都标有一个数字，用数组nums表示。你被要求扎破所有气球。扎破第i个气球可以获得nums[left] × nums[i] × nums[right]枚硬币。这里left和right是与i相邻的下标。扎破气球以后，left和right就变成相邻的了。 寻找最优策略下可以获得的硬币数。

注意： (1) 你可以假设nums[-1] = nums[n] = 1. 它们并非真实的因此不能扎破。 (2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

解题思路：

1. 此题遍历所有可能性，所以考虑用DP

2. 因为一个参数不足以描述问题，因为并不能固定nums左端或右端，所以考虑二元DP，左右边界为参数。DP流程一：定义函数f(i,j)为nums[i..j]之间的最大硬币数。

3. 下一步写递归式，由于这是二元DP，参考Floyd和矩阵链乘法算法，一遍要定义一个k，二分法得到两个子问题的解f(i,k)和f(k,j)，求解它们的关系是难点。先写几个例子培养下思路：
   2,3,4
   f([2,4])=2×3×4同时消去了3变成[2,4],再写一个
   2,3,4,5,6,7,8
   k=5, 数组变成[2,5,8]所以我们定义中忽略了一个重要事实，修改为f(i,j)为nums[i..j]之间的最大硬币数及其它们之间的元素已经消去。
   这样的话，关系就很明朗了，只要消去5就可以得到f([2,8])，k的定义要可以清晰了：最后一个消去的元素。
   f(i,j)=max{f(i,m)+ nums[i]×nums[m]×nums[j] +f(m,j)}, i<m<j，m为整数

4. 我们还要试试nums为单元素和双元素情况下是否适用。比如单元素5，根据题目意思首先前后补1
   1,5,1 -> f(1,5)+1×5×1+f(5,1)=5这是正确的因为f(x,y)默认为0.
   1,5,3,1, k=5, f(1,5)+1×5×1+f(5,1)=0+5+(5×3×1)=20 | k=3, f(1,3)+1×3×1+f(3,1)=(1×5×3)+3+0=18.所以也是正确，且f(x,y)默认为0没问题。

5. 遍历顺序。一开始我用i,j,m三重循环，但结果不对。主要因为这个计算过程与演算过程不一致，我们刚才的演算过程是先计算所有i和j之间的值。例如，
   1, 5, 3, 1
   i        j
   i            j
       i        j

   在第二次循环的时候f(i,j)已经计算出来很显然是不对的。

注意事项：

1. 二元DP([i,j],k的递归式)+二分法。 二元DP中k的引入参考Floyd按步长计算。nums[i] * nums[m] * nums[j]而不是nums[m-1] * nums[m] * nums[m+1]
2. 原数组前后补1，这样巧妙地让递归式适用于一个元素的情况，避免特别处理。因此步长可以k=2开始，i<m<j不取等号。dp数组以新数组为边界
3. 遍历顺序也类似于Floyd，先k(步长且至少为2)，再遍历矩阵i和j。特别注意i<n-k而不是i<n

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12

def maxCoins(self, nums: List[int]) -> int:
	ary = list(nums)
	ary.insert(0, 1)
	ary.append(1)
	N = len(ary)
	dp = [[0 for _ in range(N)] for _ in range(N)]
	for k in range(2, N):
		for i in range(0, N - k):
			j = i + k
			for m in range(i + 1, j):
				dp[i][j] = max(dp[i][j], dp[i][m] + ary[i] * ary[m] * ary[j] + dp[m][j])
	return dp[0][N - 1]

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public int maxCoins(int[] nums) {
	int n = nums.length+2;
	int[] coins = new int[n];
	
	for(int i=0;i<nums.length;i++)
		coins[i+1]=nums[i];
	coins[0] = coins[n-1] = 1;
	
	int[][] dp = new int[n][n];
	for(int k=2;k<n;k++)
		for(int i=0;i<n - k;i++){
			int j = i+k;
			for(int m=i+1;m<j;m++)
				dp[i][j] = Math.max(dp[i][j], dp[i][m]+coins[i]*coins[m]*coins[j] + dp[m][j]);
				
		}
	return dp[0][n-1];
}  

算法分析：

三重循环，时间复杂度为<code>O(n³)</code>，空间复杂度<code>O(n²)</code>。

LeetCode 2080 Range Frequency Queries

Design a data structure to find the frequency of a given value in a given subarray.

The frequency of a value in a subarray is the number of occurrences of that value in the subarray.

Implement the RangeFreqQuery class:

• RangeFreqQuery(int[] arr) Constructs an instance of the class with the given 0-indexed integer array arr.
• int query(int left, int right, int value) Returns the frequency of value in the subarray arr[left...right].

A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

Example 1:

<pre>Input ["RangeFreqQuery", "query", "query"] [[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]] Output [null, 1, 2]

Explanation RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]); rangeFreqQuery.query(1, 2, 4); // return 1. The value 4 occurs 1 time in the subarray [33, 4] rangeFreqQuery.query(0, 11, 33); // return 2. The value 33 occurs 2 times in the whole array. </pre>

Constraints:

• 1 <= arr.length <= 10<sup>5</sup>
• 1 <= arr[i], value <= 10<sup>4</sup>
• 0 <= left <= right < arr.length
• At most 10<sup>5</sup> calls will be made to query

题目大意：

设计数据结构，支持在指定的子数组中某target的频数。

解题思路：

这题有意思，有望成为经典题。第一种方法写用以每个字母为结尾的frequency_dict作为数据结构，query只需要用frequency_dict[right]-frequency_dict[left-1]，
空间复杂度为<code>O(n²)</code>得到TLE。第二种方法用bucket sort，就是将值作为key存到dict中，而value是下标List，query时候得到对应List，遍历
一次即可，但仍然得到TLE。第三种方法改进用Binary search得到下标List的左右界。二分法用greater_or_equal_position以及small_or_equal_position.
所以最终方案采取bucket sort + binary search

解题步骤：

1. dict记录值到下标列表的映射
2. 二分法找left和right的index从而求个数

注意事项：

1. Binary search用greater_or_equal_position以及small_or_equal_position.

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

class RangeFreqQuery:
	
    def __init__(self, arr: List[int]):
        self.frequency_dict = {}

        for i, n in enumerate(arr):
            if n not in self.frequency_dict:
                self.frequency_dict[n] = [i]
            else:
                self.frequency_dict[n].append(i)

    def query(self, left: int, right: int, value: int) -> int:
        if value not in self.frequency_dict:
            return 0
        index_list = self.frequency_dict[value]
        '''
        count = 0
        for index in index_list:
            if left <= index <= right:
                count += 1
        '''
        left_pos = self.greater_or_equal_position(index_list, left)
        right_pos = self.smaller_or_equal_position(index_list, right)
        if left_pos == -1 or right_pos == -1:
            return 0
        return right_pos - left_pos + 1

    def greater_or_equal_position(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if target > nums[mid]:
                start = mid
            elif target < nums[mid]:
                end = mid
            else:
                start = mid
        if nums[start] >= target:
            return start
        if nums[end] >= target:
            return end
        return -1

    def smaller_or_equal_position(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if target > nums[mid]:
                start = mid
            elif target < nums[mid]:
                end = mid
            else:
                end = mid
        if nums[end] <= target:
            return end
        if nums[start] <= target:
            return start
        return -1

用defaultdict(list)和bisect来优化程序

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def __init__(self, arr: List[int]):
	self.frequency_dict = collections.defaultdict(list)

	for i, n in enumerate(arr):
		self.frequency_dict[n].append(i)

def query(self, left: int, right: int, value: int) -> int:
	index_list = self.frequency_dict[value]
	left_pos = bisect.bisect(index_list, left - 1)
	right_pos = bisect.bisect(index_list, right)
	return right_pos - left_pos

算法分析：

时间复杂度为O(logn)，空间复杂度O(n)。

LeetCode 347 Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

题目大意：

给定一个非空整数数组，返回其前k个出现次数最多的元素。

注意： 你可以假设k总是有效的，1 ≤ k ≤ 独立元素的个数。 你的算法时间复杂度必须优于O(n log n)，其中n是数组的长度。

解题思路：

这是经典题，解法是HeapSelect：求最大k个数，就先对前k个元素建最小堆，然后遍历k到最后一个数，若它大于栈顶就替换且做minHeapify。最后结果是
最大的k个数在数组的前k个位置且堆顶（数组第一个数）为k个数的最小。堆并没有排序。 结果并不需要从大到小输出。

1. 统计词频
2. 建key-value数组
3. heapSelect
4. 把数组前k个数加入到结果集中

注意事项：

1. 如果需要按大到小输出结果，需要对result进行排序O(klogk)，数组第一个也就是最小堆堆顶是这k个数中最小。
2. key-pair版堆选择算法。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

from heapq import heapreplace, heappush

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
	dict = {}
	for i in range(len(nums)):
		if nums[i] not in dict:
			dict[nums[i]] = 1
		else:
			dict[nums[i]] += 1

	freq_dict = [(v, k) for k, v in dict.items()]
	res = []
	for i in range(len(freq_dict)):
		heappush(res, freq_dict[i])
		if len(res) > k:
			heappop(res)

	return [k for v, k in res]

统计词频部分可以用Counter优化。freq_dict有两个作用：将key和频率互换，还可以将dict转换成list方便和k比较

1
2
3
4
5
6
7
8
9
10
11
12

from heapq import heapreplace, heappush
from collections import Counter

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
	dict = Counter(nums)
	freq_dict = [(v, k) for k, v in dict.items()]
	res = []
	for i in range(len(freq_dict)):
		heappush(res, freq_dict[i])
		if len(res) > k:
			heappop(res)
	return [k for v, k in res]

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

public List<Integer> topKFrequent(int[] nums, int k) {
	List<Integer> result = new ArrayList<Integer>();
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	for(int i=0;i<nums.length;i++){
		if(map.containsKey(nums[i]))
			map.put(nums[i], map.get(nums[i])+1);
		else
			map.put(nums[i], 1);
	}
	Node[] f = new Node[map.size()];
	Iterator it = map.entrySet().iterator();
	int j=0;
	while(it.hasNext()){
		Map.Entry pair = (Map.Entry)it.next();
		Node node = new Node((int)pair.getKey(), (int)pair.getValue());
		f[j++] = node;
	}
	hselect(f, k);
	for(int i=0;i<k;i++)
		result.add(f[i].key);
	return result;
}
  
public void hselect(Node a[], int k){
	// min heap with size=k
	for (int i = k / 2; i >= 0; i--) {
		minHeapify(a, i, k);
	}
	for (int i = k; i < a.length; i++) {
		if (a[i].value > a[0].value) {
			swap(a, i, 0);
			minHeapify(a, 0, k);
		}
	}
}

public void minHeapify(Node[] arr, int i, int n) {
	int smallest = i;
	int l = left(i);
	int r = l + 1;
	if (l < n && arr[l].key < arr[smallest].key)
		smallest = l;
	if (r < n && arr[r].key < arr[smallest].key)
		smallest = r;
	if (smallest != i) {
		swap(arr, i, smallest);
		minHeapify(arr, smallest, n);
	}
}

private int left(int i) {
	return 2 * i + 1;
}

private void swap(Node[] arr, int index1, int index2) {
	Node tmp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = tmp;
}

class Node {
	int key;
	int value;
	public Node(int k, int v){
		key = k;
		value = v;
	}
	
	public String toString(){
		return "("+key+","+value+")";
	}
}

算法分析：

时间复杂度为O(nlogk)，空间复杂度O(1)。时间复杂度是O(n)+O(nlogk),空间复杂度为O(m)+O(1),m为不重复的元素个数(unique element)。

算法II解题思路：

此题关于数组频数，所以考虑用桶排序(bucket sort)

1. 统计词频（元素->频数）
2. 桶排序：n+1个桶（n为原数组大小），把元素放入频数对应的桶号（频数->元素），用List把这些元素串起来。
3. 逆序（从大到小）遍历不为空的桶，输入结果直至k个。 与上面算法不同的是结果是从大到小输出。数据类型有两个HashMap存储元素对应的频数，而List数组List<Integer>[]反过来存储频数对应的元素。

注意事项：

1. 桶排序要用List串联起元素，例如[1,2],k=2，频数为1的元素有两个，所以桶的内容应该是List。Python用[[] for _ in range(len(nums) + 1)]
2. 桶数量为原数组大小+1，例如一个元素[1], 它的频数为1，而频数为0是不会出现。
3. 逆序遍历所有桶，只要结果集个数为k，就停止循环。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

from collections import Counter

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
	di = Counter(nums)
	freq = [[] for _ in range(len(nums) + 1)]
	for key, val in di.items():
		freq[val].append(key)
	res = []
	for i in range(len(freq) - 1, 0, -1):
		for n in freq[i]:
			if k > 0:
				res.append(n)
				k -= 1
	return res

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public List<Integer> topKFrequent2(int[] nums, int k) {
	 List<Integer> result = new ArrayList<Integer>();
	 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	 for(int i=0;i<nums.length;i++){
		if(map.containsKey(nums[i]))
			map.put(nums[i], map.get(nums[i])+1);
		else
			map.put(nums[i], 1);
	 }
	 List<Integer>[] f = new List[nums.length+1];
	 Iterator it = map.entrySet().iterator();
	 while(it.hasNext()){
		 Map.Entry pair = (Map.Entry)it.next();
		 if(f[(int)pair.getValue()]==null)
			 f[(int)pair.getValue()] = new ArrayList();
		 f[(int)pair.getValue()].add((int)pair.getKey());
	 }
	 for(int i=f.length-1;i>0 && result.size()<k;i--)
		 if(f[i]!=null){
			 result.addAll(f[i]);
		 }
	 return result;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。时间复杂度是O(n)+O(n),空间复杂度为O(m)+O(n),m为不重复的元素个数(unique element)。

Follow-up:

1. 题目可以包装成：给定一个文档，返回其前k个出现次数最多的单词。
   Given a document, return the k most frequent words. Assume punctuation are removed.
   Given a non-empty array of strings, return the k most frequent elements.
2. 如果写出了桶排序，可以考虑假设机器memory有限，只够O(m)，不能一次性读出整个文档，也就是不能用桶排序，只能用堆选择。
3. 如果写出了堆选择，可以考虑k比较大，如果进一步提高时间复杂度，也就是只能O(n),符合这个要求就只有计数排序，基数排序和桶排序。

这是priorityQueue实现的Heap（对于基本数据类型默认是最小堆，但由于Node是自定义，必须实现Comparator），由于PQ需要额外空间，所以
较少用。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public List<Integer> topKFrequent3(int[] nums, int k) {
	 List<Integer> result = new ArrayList<Integer>();
	 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	 for(int i=0;i<nums.length;i++){
		if(map.containsKey(nums[i]))
			map.put(nums[i], map.get(nums[i])+1);
		else
			map.put(nums[i], 1);
	 }
	 Node[] f = new Node[map.size()];
	 Iterator it = map.entrySet().iterator();
	 int j=0;
	 while(it.hasNext()){
		Map.Entry pair = (Map.Entry)it.next();
		Node node = new Node((int)pair.getKey(), (int)pair.getValue());
		f[j++] = node;
	 }
	 
	 PriorityQueue<Node> minHeap = new PriorityQueue<Node>(k,
			new Comparator<Node>() {
				@Override
				public int compare(Node o1, Node o2) {
					return o1.value - o2.value;
				}
			}
	);

	for (int i = 0; i < f.length; i++) {
		if (i < k) {
			minHeap.offer(f[i]);
		} 
		else {
			Node minNode = minHeap.peek();
			if (f[i].value > minNode.value) {
				minHeap.poll();
				minHeap.offer(f[i]);
			}
		}
	}

	while(!minHeap.isEmpty())
		result.add(minHeap.poll().key);
	return result;
 }

LeetCode 001 Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

<pre>Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. </pre>

题目大意：

给定一个整数数组，从中找出两个数的下标，使得它们的和等于一个特定的数字。可以假设题目有唯一解。

解题思路：

1. 最简单的思路是暴力法，两重循环试遍所有组合。
2. 先排序，再用两指针法，若指针指向的数和小于target则左指针右移，反之亦然。注意，为了保持原数组的下标，要预先保留下标及值对到Node中。
3. 遍历数组，同时查看target-该数是否在HashMap中，否则加入到HashMap中。

Python代码：

1
2
3
4
5

def twoSum(self, nums: List[int], target: int) -> List[int]:
	for i in range(len(nums)):
		for j in range(i + 1, len(nums)):
			if nums[i] + nums[j] == target:
				return [i, j]

1
2
3
4
5
6
7
8
9
10

def twoSum(self, nums: List[int], target: int) -> List[int]:
	temp.sort()
	i, j = 0, len(temp) - 1
	while i < j:
		if temp[i][0] + temp[j][0] < target:
			i += 1
		elif temp[i][0] + temp[j][0] > target:
			j -= 1
		else:
			return [temp[i][1], temp[j][1]]

1
2
3
4
5
6

def twoSum(self, nums: List[int], target: int) -> List[int]:
	nums_dict = {}
	for i, n in enumerate(nums):
		if target - n in nums_dict:
             return [nums_dict[target - n], i]
		nums_dict[n] = i

第二种方法，Python的tuple相当于Java的自定义Node，但节省了很多代码。每种方法都大概节省了2/3的代码。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

public int[] twoSum0(int[] nums, int target) {
	int[] re = new int[2];
	for(int i=0;i<nums.length;i++)
		for(int j=i+1;j<nums.length;j++){
			if(nums[i]+nums[j]==target){
				re[0] = i;
				re[1] = j;
				return re;
			}
				
		}
	return re;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public int[] twoSum2(int[] nums, int target) {
	Node[] ary = new Node[nums.length];
	for(int i=0;i<nums.length;i++){
		ary[i] = new Node(i, nums[i]);
	}
	
	Arrays.sort(ary, new Comparator<Node>() {
		@Override
		public int compare(Node o1, Node o2) {
			return o1.value - o2.value;
		}
	});
	int[] re = new int[2];
	int start=0, end=nums.length-1;
	while(start<end){
		if(ary[start].value+ary[end].value==target){
			re[0] = ary[start].index;
			re[1] = ary[end].index;
			return re;
		}
		else if(ary[start].value+ary[end].value<target)
			start++;
		else
			end--;
	}
	return re;
}

class Node {
	Node(int i, int v){
		this.index = i;
		this.value = v;
	}
	int index;
	int value;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int[] twoSum(int[] nums, int target) {
	HashMap<Integer,Integer> h  = new HashMap<Integer,Integer>();
	
	int[] re = new int[2];
	for(int i=0;i<nums.length;i++){
		Integer index = h.get(target-nums[i]);
		if(index!=null){
			re[0]=index;
			re[1]=i;
			return re;
		}
		h.put(nums[i],i);
	}
	return re;
}

算法分析：

1. 时间复杂度为<code>O(n²)</code>，空间复杂度O(1)。
2. 时间复杂度为O(nlogn)，空间复杂度O(n)。
3. 时间复杂度为O(n)，空间复杂度O(n)。

LeetCode 2079 Watering Plants

You want to water n plants in your garden with a watering can. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the i<sup>th</sup> plant is located at x = i. There is a river at x = -1 that you can refill your watering can at.

Each plant needs a specific amount of water. You will water the plants in the following way:

• Water the plants in order from left to right.
• After watering the current plant, if you do not have enough water to completely water the next plant, return to the river to fully refill the watering can.
• You cannot refill the watering can early.

You are initially at the river (i.e., x = -1). It takes one step to move one unit on the x-axis.

Given a 0-indexed integer array plants of n integers, where plants[i] is the amount of water the i<sup>th</sup> plant needs, and an integer capacity representing the watering can capacity, return the number of steps needed to water all the plants.

Example 1:

<pre>Input: plants = [2,2,3,3], capacity = 5 Output: 14 Explanation: Start at the river with a full watering can:

• Walk to plant 0 (1 step) and water it. Watering can has 3 units of water.
• Walk to plant 1 (1 step) and water it. Watering can has 1 unit of water.
• Since you cannot completely water plant 2, walk back to the river to refill (2 steps).
• Walk to plant 2 (3 steps) and water it. Watering can has 2 units of water.
• Since you cannot completely water plant 3, walk back to the river to refill (3 steps).
• Walk to plant 3 (4 steps) and water it. Steps needed = 1 + 1 + 2 + 3 + 3 + 4 = 14. </pre>

Example 2:

<pre>Input: plants = [1,1,1,4,2,3], capacity = 4 Output: 30 Explanation: Start at the river with a full watering can:

• Water plants 0, 1, and 2 (3 steps). Return to river (3 steps).
• Water plant 3 (4 steps). Return to river (4 steps).
• Water plant 4 (5 steps). Return to river (5 steps).
• Water plant 5 (6 steps). Steps needed = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30. </pre>

Example 3:

<pre>Input: plants = [7,7,7,7,7,7,7], capacity = 8 Output: 49 Explanation: You have to refill before watering each plant. Steps needed = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49. </pre>

Constraints:

• n == plants.length
• 1 <= n <= 1000
• 1 <= plants[i] <= 10<sup>6</sup>
• max(plants[i]) <= capacity <= 10<sup>9</sup>

题目大意：

x坐标上分别是浇每棵植物需要的水量，用数组plants表示，-1上为河水可以打水，capacity是容器大小。若发现水不够，就要回到河里将容器打满水。问浇完所有植物的总步数

解题思路：

此题类似于Leetcode 2073，可以按部就班按每个plant计算，但是为了提高效率，一般采取归结为更高一层次计算。
这题更高层次是每次去洒水再回去河边作为一个循环。最后一个循环不用回河边所以是单程。

解题步骤：

1. 计算一次来回的距离，条件为剩余的水不够浇该次的植物
2. 退出循环后，计算单程距离

注意事项：

1. 如果满足capacity也要递归到下一轮再计算，也就是Line 5取等号

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def wateringPlants(self, plants: List[int], capacity: int) -> int:
	sum, steps = 0, 0
	for i, n in enumerate(plants):
		sum += plants[i]
		if sum <= capacity:
			continue
		steps += i * 2  # back to river
		sum = plants[i]
	if sum > 0:
		steps += len(plants)
	return steps

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。