Monthly Archives: June 2017

LeetCode Wiggle Sort II

LeetCode Wiggle Sort II
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].
Note:
You may assume all input has valid answer.
Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?


给定一个数组,对其进行wiggle排序,如果下标从0开始,则奇数下标的数都要大于其相邻两个数,即nums[0] < nums[1] > nums[2] < nums[3]....
普通解法是这样的,先给数组排序,然后设置首尾指针,分别取较小的数放到偶数位,较大的数放到奇数位。比如第一个样例排序之后是[1,1,1,4,5,6],i指向1,j指向6,开辟一个新数组,依次把nums[i++]和nums[j--]放到新数组中,形成[1,6,1,5,1,4],满足要求。
但是有一种情况会出问题,比如[4,5,5,6],按上面的方法,得到的数组是[4,6,5,5],最后的5,5不满足要求,究其原因,是因为随着i和j的推进,他们指向的数的差值越来越小,导致最后可能出现相等的情况。遇到这种情况,我们可以设置i从mid开始取,j从n-1开始取,这样i和j指向的数的差值始终是很大的,这样得到的结果就是[5,6,4,5]
因为题目说每个样例都有解,而wiggle sort的结果是先小后大,所以小数的个数总是大于等于大数的个数,比如1,2,1小数的个数大于大数的个数,1,2,1,2小数的个数等于大数的个数。所以我们i从mid开始时,如果数组有偶数个数,则中位数有两个,我们的mid应该是前一个中位数,这样能保证小数个数等于大数个数;如果数组有奇数个数,则中位数只有一个,我们的mid就从这个中位数开始,这样小数个数比大数个数多1。
所以第一个版本我们可以

class Solution {
private:
	//自己实现的快排程序
	void my_quick_sort(vector<int>& nums, int s, int t) {
		int i = s, j = t, pivot = s;
		if (i >= j)return;
		while (i <= j) {
			while (i <= j&&nums[i] <= nums[pivot])++i;
			if (i > j)break;
			while (i <= j&&nums[j] >= nums[pivot])--j;
			if (i > j)break;
			swap(nums[i++], nums[j--]);
		}
		swap(nums[pivot], nums[j]);
		my_quick_sort(nums, s, j - 1);
		my_quick_sort(nums, j + 1, t);
	}
public:
	void wiggleSort(vector<int>& nums) {
		int n = nums.size();
		my_quick_sort(nums, 0, n - 1);
		int i = (n & 1) == 0 ? n / 2 - 1 : n / 2, j = n - 1;
		vector<int> ans(n, 0);
		for (int k = 0; k < n; ++k) {
			ans[k] = (k & 1) == 0 ? nums[i--] : nums[j--];
		}
		nums = ans;
	}
};

手工写了快排程序,并手工根据n的奇偶性对i赋不同的值。本代码提交AC,用时569MS。自己写的快排是有多慢呀。
我们也可以这样

class Solution {
public:
	void wiggleSort(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int n = nums.size(), i = (n + 1) / 2, j = n;
		vector<int> ans(n, 0);
		for (int k = 0; k < n; ++k) {
			ans[k] = (k & 1) == 0 ? nums[--i] : nums[--j];
		}
		nums = ans;
	}
};

使用库中的sort,并且(n+1)/2相当于得到了偶数长的较大的中位数,或者奇数长中位数的下一个数,为了校准,进行了--i处理。本代码提交AC,用时86MS。
讨论区还有O(n)时间O(1)空间的解法,下回再战。

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 Implement Trie (Prefix Tree)

LeetCode Implement Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.


本题要求实现只包含26个小写字母的trie树。因为之前做过hihoCoder 1014-Trie树,所以实现起来并不费劲。
定义一个Node结构体,包含三个成员,char c表示该Node的字符,bool isWord表示以该Node结尾是否能构成一个单词,children表示该Node的26个孩子。
初始化的时候就初始化一个根节点。
插入一个单词时,不断从根节点往下创建节点,到最后一个字符所在节点时,标记isWord为true。
搜索一个单词时,也是不断从根节点往下搜索,如果到单词尾所在的Node的isWord为true,说明找到该单词,否则要么到不了最后一个字符,要么到了最后一个字符,isWord为false,都表示搜索失败。
搜索是否有某个前缀的单词存在,和搜索一个单词几乎一样,只不过最后返回时,不需要判断isWord是否为true,只要能到达prefix的最后一个字符的Node,说明后面肯定有以该字符串为前缀的单词存在。
完整代码如下:

const int MAXN = 26;
class Trie {
private:
	struct Node
	{
		char c;
		bool isWord;
		Node(char c_, bool isWord_) :c(c_), isWord(isWord_) {
			for (int i = 0; i < MAXN; ++i)children.push_back(NULL);
		};
		vector<Node*> children;
	};
	Node *root;
public:
	/** Initialize your data structure here. */
	Trie() {
		root = new Node(' ', true);
	}
	/** Inserts a word into the trie. */
	void insert(string word) {
		Node *cur = root;
		for (int i = 0; i < word.size(); ++i) {
			int idx = word[i] - 'a';
			if (cur->children[idx] == NULL)cur->children[idx] = new Node(word[i], false);
			cur = cur->children[idx];
		}
		cur->isWord = true;
	}
	/** Returns if the word is in the trie. */
	bool search(string word) {
		Node *cur = root;
		for (int i = 0; i < word.size(); ++i) {
			int idx = word[i] - 'a';
			if (cur->children[idx] == NULL)return false;
			cur = cur->children[idx];
		}
		return cur->isWord;
	}
	/** Returns if there is any word in the trie that starts with the given prefix. */
	bool startsWith(string prefix) {
		Node *cur = root;
		for (int i = 0; i < prefix.size(); ++i) {
			int idx = prefix[i] - 'a';
			if (cur->children[idx] == NULL)return false;
			cur = cur->children[idx];
		}
		return true;
	}
};

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

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 II

LeetCode Course Schedule II
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

click to show more hints.

Hints:

  1. This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.

LeetCode Course Schedule的基础上,要求输出一种拓扑排序结果。
因为已经知道拓扑排序的Kahn解法,即BFS解法,那么输出一种拓扑排序的结果是很简单的事。在BFS的过程中,存储在队列中的点肯定都是入度为0的点,也就是这些课程可以在这一阶段完成,所以我们只需要在每轮BFS的时候,保存一下这一轮的节点就好了。
完整代码如下:

class Solution {
public:
	vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
		vector<unordered_set<int>> pre(numCourses), next(numCourses);
		for (const auto& p : prerequisites) {
			pre[p.first].insert(p.second);
			next[p.second].insert(p.first);
		}
		vector<int> ans;
		queue<int> q;
		for (int i = 0; i < numCourses; ++i) {
			if (pre[i].empty())q.push(i);
		}
		int edges = prerequisites.size();
		while (!q.empty()) {
			int n = q.size();
			for (int i = 0; i < n; ++i) {
				int cur = q.front();
				ans.push_back(cur);
				q.pop();
				for (const auto& nxt : next[cur]) {
					pre[nxt].erase(cur);
					--edges;
					if (pre[nxt].empty())q.push(nxt);
				}
			}
		}
		if (edges > 0)return{};
		else return ans;
	}
};

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

LeetCode K-diff Pairs in an Array

LeetCode K-diff Pairs in an Array
Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.
Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Note:

  1. The pairs (i, j) and (j, i) count as the same pair.
  2. The length of the array won't exceed 10,000.
  3. All the integers in the given input belong to the range: [-1e7, 1e7].

给定一个数组,问数组中绝对差值为k的unique数对有多少个。
注意数对不能有重复,比如第一个样例,虽然有两个1,但是2-diff的数对(1,3)只能算一个。
我使用的方法非常简单直白。首先因为绝对误差肯定是非负数,所以如果k<0,则直接返回0对。
然后如果k==0,则说明数对中的两个数必须相等,所以对于k==0的情况,只需要统计一下数组中有多少个重复的数。
如果k>0,则对于每一个数num,如果num+k也在数组中,则找到一个k-diff的数对。
所以为了方便查找和统计,我们首先把数和频率统计到一个map中,边map,可以边统计重复数字个数repeated。
如果k==0,直接返回repeated。
否则把map的key放到一个新的vector中,根据map的性质,这个新的vector是sorted的。则遍历sorted数组,判断每个num+k是否在map中,在则++ans。最后返回ans。
完整代码如下:

class Solution {
public:
	int findPairs(vector<int>& nums, int k) {
		if (k < 0)return 0;
		int repeated = 0;
		map<int, int> count;
		for (const auto& num : nums) {
			++count[num];
			if (count[num] == 2)++repeated;
		}
		if (k == 0)return repeated;
		vector<int> sorted;
		for (const auto& it : count) {
			sorted.push_back(it.first);
		}
		int ans = 0;
		for (const auto& num : sorted) {
			if (count.find(num + k) != count.end())++ans;
		}
		return ans;
	}
};

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

LeetCode Next Greater Element III

LeetCode Next Greater Element III
Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.
Example 1:

Input: 12
Output: 21

Example 2:

Input: 21
Output: -1

给定一个数n,要求用和n一样的数字,重组成一个比n大的最小的数。如果不存在这样的数,输出-1。
比如样例1,n=12,则同样用数字1和2,重组出比12大的最小的数就是21。如果n本身等于21,则无法用数字1和2重组出比21更大的数了。
首先很容易想到无解的情况,比如n=76543210,因为n的数字从左到右是非升序的,所以n本身已经是最大的了,无法重组出比n更大的数。所以隐隐约约感觉可以从左往右找第一个上升的位置。
再来,n=76546743,如果从左往右找第一个上升的位置,则是i=3的数字4,4->6是上升的,所以可以考虑从4后面找比4大的最小的数,也就是6,交换4和6,变成76564743,因为原来为4的位置已经变成更大的6了,所以6后面最小即可,对6后面的数排序,变成了76563447。
但是76563447并不是比n大的最小的数,另外还有76547346,也就是不变4,而是变i=4的数字6。所以换一种思路,我们从右往左找第一个下降的位置,比如这里是i=5的数字7,然后从该位置往右找一个比i-1的数6大的最小的数7,交换他们的位置,同时把i-1右边的数从小到大排序。
再比如n=12443322,从右往左找第一个下降的位置是i=2,数字为4,从该位置找一个比i-1的数2大的最小的数是i=4的数3,交换他们n=1344222,再对i-1右边的数从小到大排序,得到n=1322244。
完整代码如下,另外需要注意结果不能超出int范围,所以先转换为long long,再和INT_MAX比较。

class Solution {
public:
	int nextGreaterElement(int n) {
		string s = to_string(n);
		int m = s.size();
		for (int i = m - 1; i > 0; --i) {
			if (s[i] > s[i - 1]) {
				int pos = i;
				for (int j = i; j < m; ++j) {
					if (s[j] > s[i - 1] && s[j] < s[pos]) {
						pos = j;
					}
				}
				swap(s[pos], s[i - 1]);
				sort(s.begin() + i, s.end());
				long long ans = stoll(s);
				if (ans <= INT_MAX)return ans;
				else return -1;
			}
		}
		return -1;
	}
};

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

LeetCode Design Excel Sum Formula

LeetCode Design Excel Sum Formula
Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions:
Excel(int H, char W): This is the constructor. The inputs represents the height and width of the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a character range from 'A' to 'Z'. It represents that the width is the number of characters from 'A' to W. The Excel form content is represented by a height * width 2D integer array C, it should be initialized to zero. You should assume that the first row of C starts from 1, and the first column of C starts from 'A'.
 
void Set(int row, char column, int val): Change the value at C(row, column) to be val.
 
int Get(int row, char column): Return the value at C(row, column).
 
int Sum(int row, char column, List of Strings : numbers): This function calculate and set the value at C(row, column), where the value should be the sum of cells represented by numbers. This function return the sum result at C(row, column). This sum formula should exist until this cell is overlapped by another value or another sum formula.
numbers is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format : ColRow. For example, "F7" represents the cell at (7, F).
If the string represent a range of cells, then it has the following format : ColRow1:ColRow2. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.
 
Example 1:

Excel(3,"C");
// construct a 3*3 2D array with all zero.
//   A B C
// 1 0 0 0
// 2 0 0 0
// 3 0 0 0
Set(1, "A", 2);
// set C(1,"A") to be 2.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0
Sum(3, "C", ["A1", "A1:B2"]);
// set C(3,"C") to be the sum of value at C(1,"A") and the values sum of the rectangle range whose top-left cell is C(1,"A") and bottom-right cell is C(2,"B"). Return 4.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4
Set(2, "B", 2);
// set C(2,"B") to be 2. Note C(3, "C") should also be changed.
//   A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6

Note:

  1. You could assume that there won't be any circular sum reference. For example, A1 = sum(B1) and B1 = sum(A1).
  2. The test cases are using double-quotes to represent a character.
  3. Please remember to RESET your class variables declared in class Excel, as static/class variables are persisted across multiple test cases. Please see here for more details.

本题要求设计一个简单的Excel表格求和功能。主要实现三个接口:

  • Get(int row, char column),获取坐标为(row,column)的cell的值
  • Set(int row, char column, int val),把坐标为(row,column)的值设置为val
  • Sum(int row, char column, List of Strings : numbers),numbers表示一系列求和公式,把公式计算结果填入坐标(row,column)中,并且当公式中的格子更新时,该公式计算出来的值也要更新。

本题的难点是,如果C3=A1+B2,如果更新了B2,下次get(C3)时,得到的结果也必须是用更新过的B2的值。而且还有可能A1的值也是用某个公式计算出来的。
当时比赛的时候,有一些思路,但是逻辑不是很清晰,后来参考这个题解,逻辑很清楚
Excel包含两个成员,二维矩阵matrix表示一个excel表格,hashmap formula的key为某个格子,value为该格子对应的求和公式。如果某个格子的值是实实在在的值,不是用公式计算出来的,则不在这个hashmap中。

  • 对于get,如果坐标不在formula中,说明该格子是实实在在的值,直接返回matrix中的值。否则需要从formula中取出求和公式进行计算。
  • 对于set,直接把matrix对应坐标设置为value就好,注意的是,因为set之后就变成了实实在在的值,所以要清空formula中该格子的公式(如果有的话)。
  • 对于sum,计算字符串公式的值,把结果填入对应的格子,然后在formula中设置该格子的公式。

问题的难点是怎样对一个公式求值。说穿了其实就是不停的递归调用get函数,因为get函数如果该cell没有在formula中,则返回实实在在的值,否则递归计算formula的值。想象一下,就是不停的对一个坐标递归求值,直到不能递归时,返回matrix中的值,然后递归累加起来。想明白了其实很简单,代码注意把公共的计算部分抽象出来。
完整代码如下:

class Excel {
private:
	vector<vector<int>> matrix;
	unordered_map<int, vector<string>> formula;
	// 把坐标hash成一个int
	int id(int r, char c) {
		return r * 27 + c - 'A' + 1;
	}
	void parse(string& s, int& r, char& c) {
		c = s[0];
		r = stoi(s.substr(1));
	}
	int get_cell(string& s) {
		int r;
		char c;
		parse(s, r, c);
		return get(r, c);
	}
	int get_range(string& s) {
		size_t pos = s.find(':');
		string s1 = s.substr(0, pos), s2 = s.substr(pos + 1);
		int r1, r2;
		char c1, c2;
		parse(s1, r1, c1);
		parse(s2, r2, c2);
		int ans = 0;
		for (int i = r1; i <= r2; ++i) {
			for (char c = c1; c <= c2; ++c) {
				ans += get(i, c);
			}
		}
		return ans;
	}
	int get_cells(vector<string>& strs) {
		int ans = 0;
		for (auto& s : strs) {
			if (s.find(':') == string::npos)
				ans += get_cell(s);
			else
				ans += get_range(s);
		}
		return ans;
	}
public:
	Excel(int H, char W) {
		matrix.clear();
		formula.clear();
		for (int i = 0; i <= H; ++i) {
			matrix.push_back(vector<int>(W - 'A' + 1, 0));
		}
	}
	void set(int r, char c, int v) {
		matrix[r] = v;
		formula.erase(id(r, c)); // caution
	}
	int get(int r, char c) {
		if (formula.find(id(r, c)) == formula.end())return matrix[r];
		return get_cells(formula[id(r, c)]);
	}
	int sum(int r, char c, vector<string> strs) {
		int ans = get_cells(strs);
		matrix[r] = ans;
		formula[id(r, c)] = strs;
		return ans;
	}
};

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

LeetCode K Inverse Pairs Array

LeetCode K Inverse Pairs Array
Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.
We define an inverse pair as following: For ith and jth element in the array, if i < j and a[i] > a[j] then it's an inverse pair; Otherwise, it's not.
Since the answer may very large, the answer should be modulo 109 + 7.
Example 1:

Input: n = 3, k = 0
Output: 1
Explanation:
Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pair.

Example 2:

Input: n = 3, k = 1
Output: 2
Explanation:
The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

Note:

  1. The integer n is in the range [1, 1000] and k is in the range [0, 1000].

给定一个长度为n的,包含1~n这n个数的数组,问使得逆序对有k个的数组排列有多少种。
使用DP求解。假设dp[n][k]表示长度为n的数组,有k个逆序对的排列数,则:
dp[n+1][k]=dp[n][k]+dp[n][k-1]+dp[n][k-2]+...+dp[n][k-n]
要求n+1长有k个逆序对的排列数,可以在

  • 长度为n,且有k个逆序对的基础上,把第n+1个数放到原序列的末尾,则不增加逆序对,+dp[n][k],xxxx*(xxxx表示原长度为n的序列,*表示新加入的数)
  • 长度为n,且有k-1个逆序对的基础上,把第n+1个数插入到原序列倒数第一个空位上,xxx*x,因为插入的*是最大的数,和最后一个x形成一个逆序对,使得新的长度为n+1的序列的逆序对=k-1+1=k,所以+dp[n][k-1]
  • 类似的,xx*xx,+dp[n][k-2]
  • x*xxx,+dp[n][k-3]
  • *xxxx,+dp[n][k-4]

因为远序列长度为n,所以插入的*最多只能增加n个逆序对,即上面的最后一种情况,所以原序列至少需要k-n个逆序对,这样插入*之后,才能达到k-n+n=k个逆序对。即以上递推式的最后一项是dp[n][k-n]。
完整代码如下,注意代码中i其实是n+1,所以m的下界是k-n=j-(i-1)=j-i+1,所以m>j-i。

const int kMOD = 1000000007;
class Solution {
public:
	int kInversePairs(int n, int k) {
		vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));
		dp[1][0] = 1; // 长度为1,逆序对为0,只有一种情况
		for (int i = 2; i <= n; ++i) {
			for (int j = 0; j <= k; ++j) {
				for (int m = j; m >= 0 && m > j - i; --m) {
					dp[i][j] += dp[i - 1][m];
				}
				dp[i][j] %= kMOD;
			}
		}
		return dp[n][k];
	}
};

本代码提交AC,用时1065MS。时空都还可以优化。
参考:https://discuss.leetcode.com/topic/93710/java-dp-thank-you-so-much-gardenaaa-for-your-advice

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。