Tag Archives: 贪心

LeetCode Dota2 Senate

LeetCode Dota2 Senate
In the world of Dota2, there are two parties: the Radiant and the Dire.
The Dota2 senate consists of senators coming from two parties. Now the senate wants to make a decision about a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

  1. Ban one senator's right:
    A senator can make another senator lose all his rights in this and all the following rounds.
  2. Announce the victory:
    If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and make the decision about the change in the game.

Given a string representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party respectively. Then if there are n senators, the size of the given string will be n.
The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.
Suppose every senator is smart enough and will play the best strategy for his own party, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire.
Example 1:

Input: "RD"
Output: "Radiant"
Explanation: The first senator comes from Radiant and he can just ban the next senator's right in the round 1.
And the second senator can't exercise any rights any more since his right has been banned.
And in the round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2:

Input: "RDD"
Output: "Dire"
Explanation:
The first senator comes from Radiant and he can just ban the next senator's right in the round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And the third senator comes from Dire and he can ban the first senator's right in the round 1.
And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

Note:

  1. The length of the given string will in the range [1, 10,000].

Dota2中有两个党派,分别是Radiant和Dire,分别用R和D表示。给定一个长度为n的字符串s,表示n个人,如果s[i]='R',表示第i个人是Radiant党的人;如果s[i]='D',表示第i个人是Dire党的人。
投票过程是从1~n不断重复的,每个人可以禁止任何一个其他人投票。如果某个人投票之后,剩下的人都是同一个党派的,则该党派胜利。问最终是哪个党派的人胜利。
使用贪心的原则,因为是round-based的投票方式,为了获胜,第i个人肯定是禁止其后的第一个非本党人员投票。比如序列DRDRR:
第一个D如果杀其后的第一个R:

  1. DXDRR
  2. DXDXR
  3. XXDXR
  4. XXDXX

Dire胜利;第一个D如果杀其后的第二个R:

  1. DRDXR
  2. DRXXR
  3. XRXXR

Radiant胜利。
这其实很好理解,因为是round-based的投票方式,对于D来说,他必须首先把其后的第一个R杀掉,要不然很快就会轮到这个R杀己方人员了。
round-based的方式是用%n的方式实现,代码如下:

class Solution {
public:
	string predictPartyVictory(string senate) {
		int r_cnt = 0, d_cnt = 0, n = senate.size();
		for (int i = 0; i < n; ++i) {
			if (senate[i] == 'R')
				++r_cnt;
			else
				++d_cnt;
		}
		int pos = 0;
		while (r_cnt > 0 && d_cnt > 0) {
			if (senate[pos] == 'X') {
				pos = (pos + 1) % n;
				continue;
			}
			int pos_next = (pos + 1) % n;
			while (senate[pos_next] == senate[pos] || senate[pos_next] == 'X')
				pos_next = (pos_next + 1) % n;
			if (senate[pos_next] == 'R')
				--r_cnt;
			else
				--d_cnt;
			senate[pos_next] = 'X';
			pos = (pos + 1) % n;
		}
		return r_cnt == 0 ? "Dire" : "Radiant";
	}
};

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

LeetCode 4 Keys Keyboard

LeetCode 4 Keys Keyboard
Imagine you have a special keyboard with the following keys:
Key 1: (A): Prints one 'A' on screen.
Key 2: (Ctrl-A): Select the whole screen.
Key 3: (Ctrl-C): Copy selection to buffer.
Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.
Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.
Example 1:

Input: N = 3
Output: 3
Explanation:
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

Example 2:

Input: N = 7
Output: 9
Explanation:
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

Note:

  1. 1 <= N <= 50
  2. Answers will be in the range of 32-bit signed integer.

给定四个按键,有四种操作:

  • A: 打印一个字符A
  • Ctrl-A: 全选
  • Ctrl-C: 复制
  • Ctrl-V: 粘贴

问通过n次按键操作,最多可以打印出多少个字符。
稍微分析一下,增加字符比较快的方法是用Ctrl-V,连带着需要Ctrl-C和Ctrl-A的配合,所以要想快速增加字符,必须要以Ctrl-A, Ctrl-C, Ctrl-V结尾,这就需要3个操作。当n比较小时,这3个操作相对来说比较耗时,通过分析可知,当N<=6时,直接用N次Print(A)操作能得到最多的字符。
假设dp[i]表示使用i次操作能得到的最多字符,显然dp[i]=i,当i<=6时。
当i>6时,我们可以考虑用Ctrl-A, Ctrl-C, Ctrl-V,所以结尾我们至少要空出3个操作来使用技能,也就是我们最多只能在i-3的地方开始释放Ctrl-A, Ctrl-C, Ctrl-V技能,假设释放技能的位置是b,则b<=i-3;下界是我们可以在一开始只有一个字符时使用技能,即b>=1。所以我们遍历[1,i-3]的地方释放技能,则我们可以有i-b-2个Ctrl-V结尾,再加上释放技能的位置已经有一个dp[b]了,所以总字符数是dp[b]*(i-b-1)。使用贪心策略求最大值。
完整代码如下:

class Solution {
public:
	int maxA(int N) {
		if (N <= 6)return N;
		vector<int> dp(N + 1, 0);
		for (int i = 1; i <= 6; ++i)dp[i] = i;
		for (int i = 7; i <= N; ++i) {
			for (int b = i - 3; b >= 1; --b) {
				dp[i] = max(dp[i], dp[b] + dp[b] * (i - b - 2));
			}
		}
		return dp[N];
	}
};

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

LeetCode Maximum Length of Pair Chain

LeetCode Maximum Length of Pair Chain
You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.
Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.
Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.
Example 1:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

Note:

  1. The number of given pairs will be in the range [1, 1000].

如果两个数对(a,b)和(c,d)满足b<c,则(c,d)可以跟在(a,b)的后面。给定一系列数对(s,t),问从这些数对中最多能取出多少个数对满足连续满足这种条件。
解法1,使用DP。首先对所有数对(x,y)先按x排序,x相同再按y排序。然后遍历数对,对于每个数对,有两种选择,不要或者要,对应dp[i][0]和dp[i][1],表示到i时能选出来的最多的满足条件的数对。
则dp[i][0]=max(dp[i-1][0], dp[i-1][1]),因为第i个数对不选,所以肯定等于前i-1个能选出来的最大数对,也就是max(dp[i-1][0], dp[i-1][1])。
如果第i个数对选,则要往前找到一个和i不冲突的数对j,接在j的后面,所以dp[i][1]=dp[j][1]+1。
代码如下:

bool cmp(const vector<int>& p1, const vector<int>& p2) {
	return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);
}
class Solution {
public:
	int findLongestChain(vector<vector<int>>& pairs) {
		sort(pairs.begin(), pairs.end(), cmp);
		int n = pairs.size();
		vector<vector<int>> dp(n, vector<int>(2, 0));
		dp[0][0] = 0;
		dp[0][1] = 1;
		int ans = 1;
		for (int i = 1; i < n; ++i) {
			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
			dp[i][1] = 1;
			int j = i - 1;
			while (j >= 0 && pairs[i][0] <= pairs[j][1]) {
				--j;
			}
			if (j >= 0) {
				dp[i][1] = max(dp[i][1], dp[j][1] + 1);
			}
			ans = max(ans, dp[i][0]);
			ans = max(ans, dp[i][1]);
		}
		return ans;
	}
};

本代码提交AC,用时49MS。
我隐隐觉得这种解法有问题,就是在求dp[i][1]的时候,应该要找i前面所有和i不冲突的j,求max,即dp[i][1]=max(dp[j][1]+1)。
所以解法2是无懈可击的DP解法。设dp[i]表示以数对i结尾能得到的最长的链式数对,则初始的时候,所有dp[i]=1。然后对于第i个数对,遍历i前面所有数对j,只要i和j能够链起来,则求dp[i]=max(dp[j]+1)。时间复杂度O(n^2),代码如下:

class Solution {
public:
	int findLongestChain(vector<vector<int>>& pairs) {
		sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]); });
		int n = pairs.size(), ans = 1;
		vector<int> dp(n, 1);
		for (int i = 1; i < n; ++i) {
			for (int j = i - 1; j >= 0; --j) {
				if (pairs[i][0] > pairs[j][1]) {
					dp[i] = max(dp[i], dp[j] + 1);
				}
			}
			ans = max(ans, dp[i]);
		}
		return ans;
	}
};

本代码提交AC,用时122MS。
解法3,首先还是对所有数对排序,然后把这题看成类似于求最长上升子序列。即设dp[k]=构成链条长度为k时最小的结束时间。那么来了一个数对之后,如果该数对的开始时间大于dp末尾的结束时间,则说明该数对可以追加到dp中,链条长度加1,dp[k+1]=该数对的结束时间。否则,如果该数对的开始时间不大于dp末尾的结束时间,则需要像LIS一样,把该数对插入到dp中,因为dp是排好序的,所以二分插入即可。
该思路请参考:https://discuss.leetcode.com/topic/96814/python-straightforward-with-explanation-n-log-n/2。比较有意思的是,正如第一个评论人所说,因为提前对数对按结束时间排序了,所以后面的数对肯定是大于等于dp末尾的数对的,所以新来的数对只可能追加到dp的末尾,不可能插入到dp的其他位置,所以就可以省略二分插入的过程。完整代码简洁如下:

class Solution {
public:
	int findLongestChain(vector<vector<int>>& pairs) {
		sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[1] < p2[1]; });
		int ans = 0;
		for (int i = 0, j = 0; j < pairs.size(); ++j) {
			if (j == 0 || pairs[j][0] > pairs[i][1]) {
				++ans;
				i = j;
			}
		}
		return ans;
	}
};

本代码提交AC,用时45MS。
这个题可以把每个数对看成一个活动的开始和结束时间,把问题转换为从所有活动中选出尽量多的不重叠的活动,求最多的活动个数。活动选择问题可以用贪心求解,详细介绍和证明请看维基百科

LeetCode Remove K Digits

LeetCode Remove K Digits
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:

  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

给定一个数字字符串,要求从中删除k个数字,使得最终结果最小,返回最小的数字字符串。
使用栈和贪心的思路。为了使结果尽量小,我们从左往右扫描字符串,把字符存到一个栈中,如果当前字符比栈顶小,则可以把栈顶数字删掉,这样相当于用当前字符代替栈顶字符所在位置,使得结果更小了。否则把当前字符压栈,注意此时不能把当前字符删掉,因为可能后面还有更大的字符出现。
如果这样过了一遍之后,还是没删够k个字符,此时,字符串从左往右肯定是非降序的。所以我们依次弹栈,把栈顶的元素删掉,直到删够k个字符。
最后还要判断一下剩余字符串是否为空,并删除前导零。完整代码如下:

class Solution {
public:
	string removeKdigits(string num, int k) {
		if (k >= num.size())return "0";
		string ans = "";
		for (const auto& c : num) {
			if (ans.empty() || k == 0)ans.push_back(c);
			else {
				while (!ans.empty() && ans.back() > c) {
					ans.pop_back();
					if (--k == 0)break;
				}
				ans.push_back(c);
			}
		}
		while (k-- > 0 && !ans.empty()) ans.pop_back();
		while (!ans.empty() && ans[0] == '0')ans.erase(ans.begin());
		return ans.empty() ? "0" : ans;
	}
};

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

LeetCode Coin Change

LeetCode Coin Change
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note:
You may assume that you have an infinite number of each kind of coin.


给定一堆硬币数组coins和一个总数amount,问最少用多少个硬币能凑齐这amount的钱数。每种面值的硬币数量无限。
一开始想到用贪心,即为了使硬币数最少,我们总是用小于等于amount的最大面值的硬币去凑。但是这样得到的结果不是最优的,而且有时候还可能得不到结果。比如coins=[2,5,7,8], amount=19,如果用贪心的思路,首先取8,amount=19-8=11;再取8,amount=11-8=3;再取2,amount=3-2=1;没有硬币可取了,这样就凑不齐19。但是如果不取8,而是取19=7+7+5,则可以用3枚硬币凑齐。
一般不能用贪心得到全局最优解的时候,用DP总是能得到全局最优解的。
假设dp[i]表示凑齐钱数为i最少需要的硬币数,则dp[i]=min(dp[i-coins[j]]+1, dp[i])。这个递推式的意思是说,如果要凑齐钱数i,我们看看能不能用第j个硬币,如果能的话,用之前需要凑齐i-coins[j]的钱数,所以总的硬币数就是凑齐i-coins[j]的硬币数加上1,这个1就是j这个硬币。我们需要遍历所有j求最小。最后dp[amount]就是全局最优解。
完整代码如下:

class Solution {
public:
	int coinChange(vector<int>& coins, int amount) {
		int mmax = amount + 1, ans = mmax;
		vector<int> dp(amount + 1, mmax);
		dp[0] = 0;
		for (int i = 1; i <= amount; ++i) {
			for (int j = 0; j < coins.size(); ++j) {
				if (i - coins[j] >= 0) {
					dp[i] = min(dp[i], dp[i - coins[j]] + 1);
				}
			}
		}
		return dp[amount] >= mmax ? -1 : dp[amount];
	}
};

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

LeetCode Course Schedule III

LeetCode Course Schedule III
There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.
Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.
Example:

Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3
Explanation:
There're totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Note:

  1. The integer 1 <= d, t, n <= 10,000.
  2. You can't take two courses simultaneously.

给定一系列课程,每门课有持续时间以及该课程关闭时间。从0时刻开始,问最多能完成多少门课程。注意不能同时上多门课程。
使用贪心的思路, 首先根据经验,越早结束的课程,越早选修并结束该课程越好,因为这样可以留出更多的时间选修其他课程。所以我们首先对所有课程按关闭时间从小到大排序,每次我们贪心的选择最早关闭的课程。
如果now+duration<=closed,即当前时间加该课程的持续时间不超过课程的关闭时间,则贪心选修该课程,并且把该课程的持续时间插入到一个优先队列中(最大堆)。
如果不能选修该课程,且优先队列中堆顶的持续时间比当前课程还大,则可以把堆顶课程删掉,换成该门课程,这样该门课程肯定可以选修并完成,同时使得新的now比之前的now要小,更有利于选修更多的课程。
举个例子,假设已经按关闭时间排序了[3,8],[7,10],[5,14],[8,17],now=0。

  1. 选修第一门课程,now=3<8,优先队列堆顶为3
  2. 选修第二门课程,now=3+7=10<=10,优先队列堆顶为7
  3. 选修第三门课程,now=10+5=15>14,失败;发现堆顶课程的持续时间是7,大于当前课程的持续时间5,所以可以把堆顶课程换成该门课程,则新的now=10-7+5=8,堆顶为5。因为该门课程的持续时间比堆顶短,且关闭时间已排序,所以大于堆顶的关闭时间,所以把堆顶课程换成该课程,该课程肯定能过完成。且新的now=8比先前的now=10要小,使得可以完成第四门课程。
  4. 选修第四门课,now=8+8=16<17,优先队列为8。

完整代码如下:

class Solution {
public:
	int scheduleCourse(vector<vector<int>>& courses) {
		auto cmp = [](vector<int>& c1, vector<int>& c2) {return c1[1] < c2[1]; };
		sort(courses.begin(), courses.end(), cmp);
		int now = 0, ans = 0;
		priority_queue<int> pq;
		for (const auto& c : courses) {
			if (now + c[0] <= c[1]) {
				++ans;
				now += c[0];
				pq.push(c[0]);
			}
			else if (!pq.empty() && c[0] < pq.top()) {
				now = now - pq.top() + c[0];
				pq.pop();
				pq.push(c[0]);
			}
		}
		return ans;
	}
};

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

LeetCode Gas Station

LeetCode Gas Station
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.


给定一个圆环,环上有n个加油站,每个加油站有gas[i]升油,一辆车从第i个加油站走到第i+1个加油站需要耗费cost[i]升油。问该车能否绕行圆环一周,如果能给出起点。

  1. 对于某个点i,如果gas[i]-cost[i]>=0,则车能从i走到i+1。
  2. 如果从A出发,无法到达B(但能到达B-1),则所有在A、B之间的起点都无法到达B。反证法,想象一下,如果A,B之间有一起点C能到达B,则说明C到B之间总的gas大于中的cost,又因为C在A,B之间,A能到达C,说明A到C之间中的gas大于cost。那么,既然A能到C,C能到B,则A能到B,和前提假设矛盾,所以原命题成立。
  3. 如果圆环上中的gas大于总的cost,则一定有一个解。
  4. 假设解的起点为i,则从i肯定能到达环上的任意一点。

基于以上的讨论,本题的解法是这样的:

  1. 从0开始走,如果能到达i,但无法到达i+1,则所有0~i的点都不是起点,因为根据讨论2,0~i的点都无法到达i+1,而根据讨论4,0~i的点不可能是解。
  2. 所以尝试起点为i+1,继续往前走。
  3. 最后,如果满足3,因为其他所有点都不可能是正确答案,且根据题目,解是唯一的,所以上述过程找到的起点就是正确解。

完整代码如下:

class Solution {
public:
	int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
		int gasSum = 0, costSum = 0, tank = 0, start = 0;
		for (int i = 0; i < gas.size(); ++i) {
			gasSum += gas[i];
			costSum += cost[i];
			tank += (gas[i] - cost[i]);
			if (tank < 0) {
				start = i + 1;
				tank = 0;
			}
		}
		if (gasSum < costSum)return -1;
		else return start;
	}
};

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

LeetCode Longest Uncommon Subsequence II

LeetCode Longest Uncommon Subsequence II
Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.
A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.
The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn't exist, return -1.
Example 1:

Input: "aba", "cdc", "eae"
Output: 3

Note:

  1. All the given strings' lengths will not exceed 10.
  2. The length of the given list will be in the range of [2, 50].

给定一个字符串数组,问这些字符串的最长非公共子序列的长度是多少。非公共子序列是指任意一个字符串的子序列,不是其他所有字符串的子序列。要求这样的子序列的最大长度。
首先非公共子序列不可能来自那些出现过多次的字符串,比如数组中有两个字符串都是"abcd",那么其中一个"abcd"的任意一个子序列,必定是另一个"abcd"的子序列,不满足非公共子序列的定义。所以我们首先对所有字符串及其出现频率hash一下,只考察那些出现一次的字符串的子序列。
另一个观察是,如果存在非公共子序列,则最长的非公共子序列肯定是某个完整的字符串,这一点从LeetCode Longest Uncommon Subsequence I可知。
所以,我们首先把字符串按长度从大到小排序,排序完之后,遍历每个字符串s,如果s出现的频率大于1,直接不考虑;否则,采用贪心策略,我们在比s更长的那些字符串中判断s是否是他们的子序列,如果是,s不是非公共子序列;否则s是非公共子序列,因为后面都是比s更短的字符串,s肯定也不是他们的子序列,又我们根据字符串长度排序了。所以s的长度就是非公共子序列的最大长度。
完整代码如下:

class Solution {
private:
	// 判断child是否是par的子序列
	bool isSubSeq(const string& par, const string& child) {
		int i = 0, j = 0, m = par.size(), n = child.size();
		while (i < m&&j < n) {
			if (par[i] == child[j])++j;
			++i;
		}
		return j == n;
	}
public:
	int findLUSlength(vector<string>& strs) {
		unordered_map<string, int> hash;
		for (const auto& s : strs)++hash[s];
		sort(strs.begin(), strs.end(), [](const string& s1, const string& s2) {return s1.size() > s2.size(); });
		for (int i = 0; i < strs.size(); ++i) {
			if (hash[strs[i]] > 1)continue;
			bool isSub = false;
			for (int j = i - 1; j >= 0; --j) {
				if (isSubSeq(strs[j], strs[i])) {
					isSub = true;
					break;
				}
			}
			if (!isSub)return strs[i].size();
		}
		return -1;
	}
};

本代码提交AC,用时3MS。
参考:http://bookshadow.com/weblog/2017/04/03/leetcode-longest-uncommon-subsequence-ii/

LeetCode Can Place Flowers

LeetCode Can Place Flowers
Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.
Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.
Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:

  1. The input array won't violate no-adjacent-flowers rule.
  2. The input array size is in the range of [1, 20000].
  3. n is a non-negative integer which won't exceed the input array size.

今天第一次做Leetcode的weekly contest,AC了三题,最后一题看起来好繁琐,没A。
第一题,简单贪心即可,从第0个位置开始,检查每个位置的前后是否为1,如果不为1,说明该位置可以种花,填上1,最后统计新填上的1的个数和n的关系。
代码如下:

class Solution {
public:
	bool canPlaceFlowers(vector<int>& flowerbed, int n) {
		int m = flowerbed.size();
		for (int i = 0; i < m; ++i) {
			if (flowerbed[i] == 0) {
				if (i - 1 >= 0 && flowerbed[i - 1] == 1)continue;
				if (i + 1 < m&&flowerbed[i + 1] == 1)continue;
				flowerbed[i] = 1;
				--n;
			}
		}
		return n <= 0;
	}
};

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

LeetCode Array Partition I

LeetCode Array Partition I
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1:

Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4.

Note:

  1. n is a positive integer, which is in the range of [1, 10000].
  2. All the integers in the array will be in the range of [-10000, 10000].

给定一个长度为2n的数组,要求把数组分成n组,即(a1, b1), (a2, b2), ..., (an, bn) ,使得每组的最小值之和最大。
使用贪心策略,比如样例中,4和3肯定不能和1配对,因为1肯定是最小的,不能拿很大的数和1陪葬,所以只拿2和1配对;然后3、4配对。所以规律就是对数组排序,从小到大每两个配对。那么每组最小值之和就是第0、2、4...个数之和。
代码如下:

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
    	sort(nums.begin(), nums.end());
    	int ans = 0;
    	for(int i = 0; i < nums.size(); i += 2) ans += nums[i];
    	return ans;
    }
};

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