Monthly Archives: June 2020

LeetCode Avoid Flood in The City

1488. Avoid Flood in The City

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake which is full of water, there will be a flood. Your goal is to avoid the flood in any lake.

Given an integer array rains where:

  • rains[i] > 0 means there will be rains over the rains[i] lake.
  • rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.

Return an array ans where:

  • ans.length == rains.length
  • ans[i] == -1 if rains[i] > 0.
  • ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.

If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.

Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4)

Example 1:

Input: rains = [1,2,3,4]
Output: [-1,-1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day full lakes are [1,2,3]
After the fourth day full lakes are [1,2,3,4]
There's no day to dry any lake and there is no flood in any lake.

Example 2:

Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day, we dry lake 2. Full lakes are [1]
After the fourth day, we dry lake 1. There is no full lakes.
After the fifth day, full lakes are [2].
After the sixth day, full lakes are [1,2].
It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.

Example 3:

Input: rains = [1,2,0,1,2]
Output: []
Explanation: After the second day, full lakes are  [1,2]. We have to dry one lake in the third day.
After that, it will rain over lakes [1,2]. It's easy to prove that no matter which lake you choose to dry in the 3rd day, the other one will flood.

Example 4:

Input: rains = [69,0,0,0,69]
Output: [-1,69,1,1,-1]
Explanation: Any solution on one of the forms [-1,69,x,y,-1], [-1,x,69,y,-1] or [-1,x,y,69,-1] is acceptable where 1 <= x,y <= 10^9

Example 5:

Input: rains = [10,20,20]
Output: []
Explanation: It will rain over lake 20 two consecutive days. There is no chance to dry any lake.

Constraints:

  • 1 <= rains.length <= 10^5
  • 0 <= rains[i] <= 10^9

给定一个数组rains,rains[i]表示第i天在第rains[i]的湖上下雨,湖被灌满,比如第四个例子,rains[0]=69表示第0天在第69号湖上下雨,第69号湖被灌满。如果rains[i]=0表示第i天不下雨,可以抽干某个湖。问每个不下雨的天,抽干哪个湖,能让任意一个湖都不至于出现水灾(被灌满之后又被下雨)。

很有意思的一个题,暴力方法是,每个不下雨的天,对于之前被灌满的湖,抽干未来第一个要下雨的湖。比如对于rains=[1,2,3,0,2,0,0],当遇到第一个0时,我们选择抽干2号湖,因为下一天马上要在2号湖上下雨,如果不抽干2号湖,则会发生水灾,所以要抽干未来第一个要出现水灾的湖。但是这种时间复杂度是O(n^2)。

参考讨论区,更好的做法是,先记录所有不下雨的天,然后对于每一个下雨天,如果要下雨的湖之前没被灌满,则不用管;如果之前被灌满了,则需要在之前被灌满那天之后找一个不下雨的天,把这个湖抽干。所以维护一个堆heap/set,记录之前不下雨的天,后续直接用lower_bound查找符合的天。

完整代码如下:

class Solution {
public:
	vector<int> avoidFlood(vector<int>& rains) {
		int n = rains.size();

		vector<int> ans;
		unordered_map<int, int> full_lakes;
		set<int> dry_days;

		for (int i = 0; i < n; ++i) {
			if (rains[i] == 0) {
				dry_days.insert(i);
				ans.push_back(1); // 先随便填一个数,后续会覆盖,填入真正要抽干的湖编号
			}
			else {
				if (full_lakes.find(rains[i]) != full_lakes.end()) { // 这个湖之前就满了,需要抽干
					int last_day = full_lakes[rains[i]];
					set<int>::iterator it = dry_days.lower_bound(last_day); //从之前满的那天往后选不下雨的一天抽干
					if (it == dry_days.end()) {
						return {}; // 失败
					}
					ans[*it] = rains[i];
					dry_days.erase(it);
				}
				full_lakes[rains[i]] = i; // 填入新的下雨日期
				ans.push_back(-1);
			}
		}

		return ans;
	}
};

本代码提交AC,用时1040MS。

LeetCode Making File Names Unique

1487. Making File Names Unique

Given an array of strings names of size n. You will create n folders in your file system such that, at the ith minute, you will create a folder with the name names[i].

Since two files cannot have the same name, if you enter a folder name which is previously used, the system will have a suffix addition to its name in the form of (k), where, k is the smallest positive integer such that the obtained name remains unique.

Return an array of strings of length n where ans[i] is the actual name the system will assign to the ith folder when you create it.

Example 1:

Input: names = ["pes","fifa","gta","pes(2019)"]
Output: ["pes","fifa","gta","pes(2019)"]
Explanation: Let's see how the file system creates folder names:
"pes" --> not assigned before, remains "pes"
"fifa" --> not assigned before, remains "fifa"
"gta" --> not assigned before, remains "gta"
"pes(2019)" --> not assigned before, remains "pes(2019)"

Example 2:

Input: names = ["gta","gta(1)","gta","avalon"]
Output: ["gta","gta(1)","gta(2)","avalon"]
Explanation: Let's see how the file system creates folder names:
"gta" --> not assigned before, remains "gta"
"gta(1)" --> not assigned before, remains "gta(1)"
"gta" --> the name is reserved, system adds (k), since "gta(1)" is also reserved, systems put k = 2. it becomes "gta(2)"
"avalon" --> not assigned before, remains "avalon"

Example 3:

Input: names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
Output: ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]
Explanation: When the last folder is created, the smallest positive valid k is 4, and it becomes "onepiece(4)".

Example 4:

Input: names = ["wano","wano","wano","wano"]
Output: ["wano","wano(1)","wano(2)","wano(3)"]
Explanation: Just increase the value of k each time you create folder "wano".

Example 5:

Input: names = ["kaido","kaido(1)","kaido","kaido(1)"]
Output: ["kaido","kaido(1)","kaido(2)","kaido(1)(1)"]
Explanation: Please note that system adds the suffix (k) to current name even it contained the same suffix before.

Constraints:

  • 1 <= names.length <= 5 * 10^4
  • 1 <= names[i].length <= 20
  • names[i] consists of lower case English letters, digits and/or round brackets.

给定一个字符串数组,表示每次创建的文件名,如果新的文件名和之前的文件名重名,则需要在后面加上最小的(k)重命名。问最终创建的文件名数组是怎样的。

使用hash表记录每个文件名前缀出现的次数,如果之前没出现,则直接合法;如果之前出现了,则合法的(k)至少是之前出现次数之后的k,枚举找到最小的k。代码如下:

class Solution {
public:
	vector<string> getFolderNames(vector<string>& names) {
		vector<string> ans;
		unordered_map<string, int> show_times;
		for (int i = 0; i < names.size(); ++i) {
			if (show_times.find(names[i]) == show_times.end()) {
				ans.push_back(names[i]);
				show_times[names[i]] = 1;
			}
			else {
				int k = show_times[names[i]];
				string next_name = names[i] + "(" + to_string(k) + ")";
				while (show_times.find(next_name) != show_times.end()) {
					show_times[names[i]] = ++k;
					next_name = names[i] + "(" + to_string(k) + ")";
				}
				ans.push_back(next_name);
				show_times[next_name] = 1;
			}
		}
		return ans;
	}
};

本代码提交AC,用时424MS。

LeetCode XOR Operation in an Array

1486. XOR Operation in an Array

Given an integer n and an integer start.

Define an array nums where nums[i] = start + 2*i (0-indexed) and n == nums.length.

Return the bitwise XOR of all elements of nums.

Example 1:

Input: n = 5, start = 0
Output: 8
Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8.
Where "^" corresponds to bitwise XOR operator.

Example 2:

Input: n = 4, start = 3
Output: 8
Explanation: Array nums is equal to [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8.

Example 3:

Input: n = 1, start = 7
Output: 7

Example 4:

Input: n = 10, start = 5
Output: 2

Constraints:

  • 1 <= n <= 1000
  • 0 <= start <= 1000
  • n == nums.length

给定start和n,将所有的start+2i进行异或。简单题,直接照做:

class Solution {
public:
	int xorOperation(int n, int start) {
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			ans ^= (start + 2 * i);
		}
		return ans;
	}
};

本代码提交AC,用时0MS。

LeetCode Minimum Number of Days to Make m Bouquets

5455. Minimum Number of Days to Make m Bouquets

Given an integer array bloomDay, an integer m and an integer k.

We need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

Example 1:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

Example 2:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.

Example 3:

Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation: We need 2 bouquets each should have 3 flowers.
Here's the garden after the 7 and 12 days:
After day 7: [x, x, x, x, _, x, x]
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
After day 12: [x, x, x, x, x, x, x]
It is obvious that we can make two bouquets in different ways.

Example 4:

Input: bloomDay = [1000000000,1000000000], m = 1, k = 1
Output: 1000000000
Explanation: You need to wait 1000000000 days to have a flower ready for a bouquet.

Example 5:

Input: bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
Output: 9

Constraints:

  • bloomDay.length == n
  • 1 <= n <= 10^5
  • 1 <= bloomDay[i] <= 10^9
  • 1 <= m <= 10^6
  • 1 <= k <= n

花园里有n朵花,告诉你每朵花在第几天开花。现在要扎m束花,每束花必须由相邻的k朵花组成,问要完成这个任务,最少需要等多少天。

首先看看需要的总花数m*k是否>n,如果是的话,即使所有花都开了也无法完成任务。

对于能够完成的任务,要求最少等待天数。暴力方法是,枚举bloomDay数组中所有unique的天数,对于每一天,都看看能否完成任务,方法是把数组中相邻的开的花每k多组成一束,看看能否组成m束。

但是暴力方法超时,一个改进的方法是二分。因为天数是递增的,而且每增加一天,开花的总数也是递增的,相当于能组成的花束也是递增的(严格来说是非递减的),这就为二分搜索创造了条件。

维护两个数组,days存储了unique的天数,递增排序(map自动递增有序了);num_bloomed表示在当前天数下,开花的总数,随着days的增大, num_bloomed 存储的开花总数也是递增的。在构造 num_bloomed 的过程中,可以求到最小的可能的开始天数left,然后在left和right中二分搜索合法的最小天数。

完整代码如下:

class Solution {
	bool IsValid(vector<int>& bloomDay, int day, int m, int k) {
		int bouquets = 0, n = bloomDay.size();
		int i = 0, good = 0;
		while (i < n) {
			while (i<n&&bloomDay[i]>day)++i;
			if (i >= n)break;

			int j = i;
			while (j < n&&bloomDay[j] <= day)++j;
			// [i,j) 都开花了

			good += (j - i) / k;

			i = j;
		}
		return good >= m;
	}
public:
	int minDays(vector<int>& bloomDay, int m, int k) {
		int n = bloomDay.size();
		if (m*k > n)return -1;

		map<int, int> hash;
		for (int i = 0; i < n; ++i)++hash[bloomDay[i]];
		if (m*k == n)return (--hash.end())->first; // 最后一天

		int unique_day = hash.size();
		vector<int> days(unique_day, 0);
		vector<int> num_bloomed(unique_day, 0);

		int d = 0, nb = 0;
		int left = 0, right = unique_day - 1, found_left = false;
		for (map<int, int>::iterator it = hash.begin(); it != hash.end(); ++it) {
			nb += it->second;
			if (nb >= m * k && !found_left) {
				left = d;
				found_left = true;
			}

			days[d] = it->first;
			num_bloomed[d] = nb;
			
			++d;
		}

		while (left <= right) {
			int mid = left + (right - left) / 2;
			bool valid = IsValid(bloomDay, days[mid], m, k);
			if (valid)right = mid - 1;
			else left = mid + 1;
		}

		return days[right + 1];
	}
};

本代码提交AC,用时1316MS。

Leetcode Least Number of Unique Integers after K Removals

5454. Least Number of Unique Integers after K Removals

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

Constraints:

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^9
  • 0 <= k <= arr.length

给定一个数组,问从中删掉K个数后,剩余数中unique数的个数最少是多少。

要让剩余的unique数最少,则删掉的数必须是频率最低的数。举个例子,原数组是[1,2,3,3,3],如果删掉两个数,肯定是删掉1,2,这样剩余是[3,3,3],unique数只有3这一个数。如果删掉两个3,则剩余[1,2,3],unique数有3个。

所以,对所有数按其频率从小到大排序,然后删掉频率最低的前几个数即可。完整代码如下:

class Solution {
public:
	int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
		int n = arr.size();
		vector<pair<int, int>> num_counts;
		unordered_map<int, int> hash;
		for (int i = 0; i < n; ++i)++hash[arr[i]];
		for (unordered_map<int, int>::iterator it = hash.begin(); it != hash.end(); ++it) {
			num_counts.push_back(make_pair(it->second, it->first));
		}
		sort(num_counts.begin(), num_counts.end());
		int m = num_counts.size(), sum = 0;

		if (k == 0)return m;
		else if (k == n)return 0;

		for (int i = 0; i < m; ++i) {
			sum += num_counts[i].first;
			if (sum == k)return m - i - 1;
			else if (sum > k)return m - i;
		}

		return 0;
	}
};

本代码提交AC,用时792MS。

Leetcode Running Sum of 1d Array

5453. Running Sum of 1d Array

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2:

Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3:

Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]

Constraints:

  • 1 <= nums.length <= 1000
  • -10^6 <= nums[i] <= 10^6

给定一个数组,求出数组的前缀和。简单题,代码如下:

class Solution {
public:
	vector<int> runningSum(vector<int>& nums) {
		int n = nums.size();
		vector<int> ans(n, 0);
		ans[0] = nums[0];
		for (int i = 1; i < n; ++i)ans[i] = ans[i - 1] + nums[i];
		return ans;
	}
};

本代码提交AC,用时12MS。