Tag Archives: 堆栈

LeetCode Exclusive Time of Functions

LeetCode Exclusive Time of Functions
Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.
Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.
A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0.
Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function's exclusive time. You should return the exclusive time of each function sorted by their function id.
Example 1:

Input:
n = 2
logs =
["0:start:0",
 "1:start:2",
 "1:end:5",
 "0:end:6"]
Output:[3, 4]
Explanation:
Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.
Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.
Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.
So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.

Note:

  1. Input logs will be sorted by timestamp, NOT log id.
  2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
  3. Two functions won't start or end at the same time.
  4. Functions could be called recursively, and will always end.
  5. 1 <= n <= 100

给定一个单核单线程的CPU,并且给出了该CPU跑不同函数的开始时间和结束时间,问每个函数单独运行的时间是多少。因为有些函数可能会调用其他函数,还可能递归调用自己,所以需要去掉调用其他函数的时间,只给出该函数自己运行的时间。
用Node记录每一个记录,Node包含四个属性:function_id,start_or_end,timestamp和exclude_time,前三个就是题目中描述的属性,最后一个exclude_time是指该函数调用其他函数花费的时间,需要减去的时间。
考虑到递归调用,递归返回之类的,马上想到函数调用的时候需要用堆栈保存现场,所以这里也用堆栈保存所有递归调用的函数。每次遇到新函数的start时,压栈,遇到end时,和栈顶求一下时间差,弹栈,并把时间差记录到结果数组中。同时,需要把这个函数用掉的时间累加到栈顶(也就是主调函数)Node的exclude_time中,这一点非常重要。
最后,因为一个函数可能出现多次,所以不论是对结果数组的赋值还是对exclude_time的赋值,都用+=,不能用赋值,否则会覆盖掉之前的数据。
完整代码如下:

class Solution {
private:
	struct Node {
		int id_;
		bool start_;
		int timestamp_;
		int exclude_time_;
	};
	void ParseLog(const string& log, Node& node) {
		size_t colon_pos = log.find(':');
		node.id_ = stoi(log.substr(0, colon_pos));
		if (log[colon_pos + 1] == 's')
			node.start_ = true;
		else
			node.start_ = false;
		colon_pos = log.find(':', colon_pos + 1);
		node.timestamp_ = stoi(log.substr(colon_pos + 1));
		node.exclude_time_ = 0;
	}
public:
	vector<int> exclusiveTime(int n, vector<string>& logs) {
		vector<int> ans(n);
		stack<Node> stk;
		for (const auto& log : logs) {
			Node node;
			ParseLog(log, node);
			if (node.start_) {
				stk.push(node);
			} else {
				Node start_node = stk.top();
				stk.pop();
				int cur_time = node.timestamp_ - start_node.timestamp_ + 1 - start_node.exclude_time_; // caution
				ans[node.id_] += cur_time; // caution
				if (!stk.empty())stk.top().exclude_time_ += cur_time + start_node.exclude_time_; // caution
			}
		}
		return ans;
	}
};

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

LeetCode Smallest Range

LeetCode Smallest Range
You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists.
We define the range [a,b] is smaller than range if b-a < d-c or a < c if b-a == d-c.
Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:

  1. The given list may contain duplicates, so ascending order means >= here.
  2. 1 <= k <= 3500
  3. -105 <= value of elements <= 105.
  4. For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.

给定k个升序数组,求一个整数区间,该区间能至少包括所有数组的一个元素,且该区间最小。最小的定义是区间长度最小,如果区间长度相同,则区间起始点小则小。
参考Find smallest range containing elements from k lists这篇博客,突然发现GeeksforGeeks网站上的题比Leetcode上的多好多,而且都有详细题解和代码,好棒。
要求区间最小,则区间只包括每个数组的一个元素最好,所以我们要找k个数组中的k个数,使得这k个数的最大值和最小值的差最小,那么这个区间的两个端点就是这个最大值和最小值。
所以我们对k个数组维护k个指针,初始时都指向每个数组的首元素,然后找到这k个数的最大值和最小值,得到一个区间及其长度。然后我们不断循环:向前移动k个指针中的最小者,在新的k个数中求最大值和最小值及其区间长度。直到某个数组遍历结束,则返回得到的最小区间。
以样例为例。

  1. i,j,k分别指向三个数组的开头,即i=j=k=0,相当于在[4,0,5]中找最大值和最小值,构成区间[0,5],长度为5。
  2. 最小值为j所在数组,所以++j,在新的数组[4,9,5]中找最大值和最小值,构成区间[4,9],长度为5。
  3. 最小值为i所在数组,所以++i,在新的数组[10,9,5]中找最大值和最小值,构成区间[5,10],长度为5。
  4. ++k,新数组[10,9,18],区间[9,18],长度为9。
  5. ++j,新数组[10,12,18],区间[10,18],长度为8。
  6. ++i,新数组[15,12,18],区间[12,18],长度为6。
  7. ++j,新数组[15,20,18],区间[15,20],长度为5。
  8. ++i,新数组[24,20,18],区间[18,24],长度为6。
  9. ++k,新数组[24,20,22],区间[20,24],长度为4。
  10. ++j,第二个数组遍历完毕,结束,遍历过程中,得到的长度最短的区间是[20,24]。

完整代码如下:

class Solution {
public:
	vector<int> smallestRange(vector<vector<int>>& nums) {
		int ansmin = 0, ansmax = 0, ansrange = INT_MAX, k = nums.size();
		vector<int> ptr(k, 0);
		while (true) {
			bool done = false;
			int curmin = INT_MAX, curmax = INT_MIN, minid = 0;
			for (int i = 0; i < k; ++i) {
				if (ptr[i] >= nums[i].size()) {
					done = true;
					break;
				}
				if (nums[i][ptr[i]] < curmin) {
					curmin = nums[i][ptr[i]];
					minid = i;
				}
				if (nums[i][ptr[i]] > curmax) {
					curmax = nums[i][ptr[i]];
				}
			}
			if (done)break;
			if (curmax - curmin < ansrange) {
				ansrange = curmax - curmin;
				ansmin = curmin;
				ansmax = curmax;
			}
			++ptr[minid];
		}
		return{ ansmin,ansmax };
	}
};

本代码提交AC,用时1016MS。
因为每一轮都需要从k个数组中找最大值和最小值,线性查找的复杂度为O(k)。最坏情况下,需要遍历k个数组的每个元素,假设k个数组所有元素个数为n,则总的时间复杂度为O(nk)。
求k个数组的最大值和最小值的过程,可以用大小为k的优先队列(最小堆)来优化,复杂度可以降为O(nlgk)。代码如下:

class Solution {
private:
	struct Node {
		int value;
		int idx;
		int nxt;
		Node(int v, int i, int n) :value(v), idx(i), nxt(n) {};
		bool operator<(const Node& nd) const {
			return value > nd.value;
		}
		bool operator>(const Node& nd) const {
			return value < nd.value;
		}
	};
public:
	vector<int> smallestRange(vector<vector<int>>& nums) {
		int ansmin = INT_MAX, ansmax = INT_MIN, ansrange = INT_MAX, k = nums.size();
		priority_queue<Node> pq;
		for (int i = 0; i < k; ++i) {
			pq.push(Node(nums[i][0], i, 1));
			if (nums[i][0] < ansmin) {
				ansmin = nums[i][0];
			}
			ansmax = max(ansmax, nums[i][0]);
		}
		int curmax = ansmax;
		while (true) {
			int curmin = pq.top().value;
			int minidx = pq.top().idx;
			int minnxt = pq.top().nxt;
			pq.pop();
			if (curmax - curmin < ansrange) {
				ansrange = curmax - curmin;
				ansmin = curmin;
				ansmax = curmax;
			}
			if (minnxt < nums[minidx].size()) {
				curmax = max(curmax, nums[minidx][minnxt]);
				pq.push(Node(nums[minidx][minnxt], minidx, minnxt + 1));
			}
			else break;
		}
		return{ ansmin,ansmax };
	}
};

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

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 Basic Calculator II

LeetCode Basic Calculator II
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.


本题是LeetCode Basic Calculator的简化版,去掉了括号,增加了乘除法。但是算法都是一模一样的,先把中缀转换为后缀,然后用栈求值。
代码如下:

// 优先级
unordered_map<string, int> priority = { {"+", 1},{"-", 1},{"*", 2},{"/", 2} };
class Solution {
private:
	void push(stack<string> &numbers, stack<string> &opers, const string& numOrop) {
		if (isdigit(numOrop[0])) {
			numbers.push(numOrop);
		}
		else {
			if (numOrop == ")") {
				while (opers.top() != "(") {
					numbers.push(opers.top());
					opers.pop();
				}
				opers.pop();
			}
			else if (numOrop == "(") {
				opers.push(numOrop);
			}
			else if (opers.empty() || opers.top() == "(") {
				opers.push(numOrop);
			}
			else if (priority[numOrop] > priority[opers.top()]) {
				opers.push(numOrop);
			}
			else {
				while (!opers.empty() && opers.top() != "(" && priority[numOrop] <= priority[opers.top()]) {
					numbers.push(opers.top());
					opers.pop();
				}
				opers.push(numOrop);
			}
		}
	}
	// 中缀转后缀表达式
	list<string> in2post(const string& s) {
		stack<string> numbers, opers;
		int start = 0, end = 1, n = s.size();
		while (start < n) {
			while (start < n&&s[start] == ' ')++start;
			if (start >= n)break;
			if (isdigit(s[start])) {
				end = start + 1;
				while (end < n&&isdigit(s[end]))++end;
				string num = s.substr(start, end - start);
				push(numbers, opers, num);
				start = end;
			}
			else {
				string op = string(1, s[start]);
				push(numbers, opers, op);
				++start;
			}
		}
		while (!opers.empty()) {
			numbers.push(opers.top());
			opers.pop();
		}
		list<string> ans;
		while(!numbers.empty()) {
			ans.push_front(numbers.top());
			numbers.pop();
		}
		return ans;
	}
	// 求值后缀表达式的值
	int eval(list<string>& post) {
		int ans = 0;
		stack<int> numbers;
		for (const auto& s : post) {
			if (priority.find(s) != priority.end()) {
				int num2 = numbers.top();
				numbers.pop();
				int num1 = numbers.top();
				numbers.pop();
				if (s == "+")numbers.push(num1 + num2);
				else if (s == "-")numbers.push(num1 - num2);
				else if (s == "*")numbers.push(num1*num2);
				else numbers.push(num1 / num2);
			}
			else numbers.push(stoi(s));
		}
		return numbers.top();
	}
public:
	int calculate(string s) {
		list<string> ans = in2post(s);
		return eval(ans);
	}
};

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

LeetCode Basic Calculator

LeetCode Basic Calculator
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.


给定一个字符串表达式,要求求解该表达式的值。
使用栈解决。我们通常看到的表达式称为中缀表达式,需要把它转换为后缀表达式,比如1+((2+3)×4)-5转换为1 2 3 + 4 × + 5 -。我们可以很容易用栈求解后缀表达式,只需要遍历后缀表达式,把遇到的操作数压栈,只要遇到运算符,就从栈中弹出两个操作数,进行运算,再把运算结果压栈。最后栈中只能得到一个值,就是整个表达式的值。
所以问题的关键就是怎样把中缀表达式转换为后缀表达式。
使用两个栈,一个栈保存操作数numbers,另一个栈保存运算符opers。遍历原字符串,按如下规则进行压栈和弹栈:

  • 如果是操作数,直接压入numbers
  • 如果是操作符op:
    1. 如果op为左括号“(”,则直接把op压入opers
    2. 如果op为右括号“)”,则把opers的运算符不断弹栈并压入numbers,直到栈顶为左括号“(”,此时将这一对括号丢弃
    3. 如果opers为空,或者opers栈顶为左括号“(”,则直接把op压入opers
    4. 此时,栈顶肯定不可能是括号了,如果op的优先级高于opers栈顶的优先级,则直接把op压入opers
    5. 否则,把opers栈顶的运算符不断弹栈并压入numbers,直到栈顶为左括号,或者op的优先级高于opers栈顶的优先级。把op压入opers

如果是操作符op,下面的1~5的判断规则是有先后顺序的,需要先判断是否为括号,再判断是否是一般的运算符。
运算符的优先级是,+-优先级相同,*/优先级相同,且+-的优先级低于*/。
得到中缀表达式的后缀表达式之后,再用开头提到的栈求解。后缀表达式的求值就非常简单了。
完整代码如下:

// 优先级
unordered_map<string, int> priority = { {"+", 1},{"-", 1},{"*", 2},{"/", 2} };
class Solution {
private:
	void push(stack<string> &numbers, stack<string> &opers, const string& numOrop) {
		if (isdigit(numOrop[0])) {
			numbers.push(numOrop);
		}
		else {
			if (numOrop == ")") {
				while (opers.top() != "(") {
					numbers.push(opers.top());
					opers.pop();
				}
				opers.pop();
			}
			else if (numOrop == "(") {
				opers.push(numOrop);
			}
			else if (opers.empty() || opers.top() == "(") {
				opers.push(numOrop);
			}
			else if (priority[numOrop] > priority[opers.top()]) {
				opers.push(numOrop);
			}
			else {
				while (!opers.empty() && opers.top() != "(" && priority[numOrop] <= priority[opers.top()]) {
					numbers.push(opers.top());
					opers.pop();
				}
				opers.push(numOrop);
			}
		}
	}
	// 中缀转后缀表达式
	list<string> in2post(const string& s) {
		stack<string> numbers, opers;
		int start = 0, end = 1, n = s.size();
		while (start < n) {
			while (start < n&&s[start] == ' ')++start;
			if (start >= n)break;
			if (isdigit(s[start])) {
				end = start + 1;
				while (end < n&&isdigit(s[end]))++end;
				string num = s.substr(start, end - start);
				push(numbers, opers, num);
				start = end;
			}
			else {
				string op = string(1, s[start]);
				push(numbers, opers, op);
				++start;
			}
		}
		while (!opers.empty()) {
			numbers.push(opers.top());
			opers.pop();
		}
		list<string> ans;
		while(!numbers.empty()) {
			ans.push_front(numbers.top());
			numbers.pop();
		}
		return ans;
	}
	// 求值后缀表达式的值
	int eval(list<string>& post) {
		int ans = 0;
		stack<int> numbers;
		for (const auto& s : post) {
			if (priority.find(s) != priority.end()) {
				int num2 = numbers.top();
				numbers.pop();
				int num1 = numbers.top();
				numbers.pop();
				if (s == "+")numbers.push(num1 + num2);
				else if (s == "-")numbers.push(num1 - num2);
				else if (s == "*")numbers.push(num1*num2);
				else numbers.push(num1 / num2);
			}
			else numbers.push(stoi(s));
		}
		return numbers.top();
	}
public:
	int calculate(string s) {
		list<string> ans = in2post(s);
		return eval(ans);
	}
};

本代码提交AC,用时92MS。
参考:http://blog.csdn.net/antineutrino/article/details/6763722

LeetCode Mini Parser

LeetCode Mini Parser
Given a nested list of integers represented as a string, implement a parser to deserialize it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Note: You may assume that the string is well-formed:

  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9, [, - ,, ].

Example 1:

Given s = "324",
You should return a NestedInteger object which contains a single integer 324.

Example 2:

Given s = "[123,[456,[789]]]",
Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

给定一个嵌套的字符串,要求把它解析成一个NestedInteger。
解法1,使用栈。遇到左括号时,增加一个空的NestedInteger实例,压栈。遇到逗号时,把前面的数add到栈顶的NestedInteger中。遇到右括号时,把栈顶的NestedInteger弹栈,并add到新的栈顶(相当于前一个)NestedInteger中。最后栈顶只有一个元素,返回该元素即可。
代码如下:

class Solution {
public:
	NestedInteger deserialize(string s) {
		auto isnumber = [](char c) {return c == '-' || isdigit(c); };
		stack<NestedInteger> stk;
		stk.push(NestedInteger());
		for (auto it = s.begin(); it != s.end();) {
			if (isnumber(*it)) {
				auto it2 = find_if_not(it, s.end(), isnumber);
				int v = stoi(string(it, it2));
				stk.top().add(NestedInteger(v));
				it = it2;
			}
			else {
				if (*it == '[') {
					stk.push(NestedInteger());
				}
				else if (*it == ']') {
					NestedInteger tmp = stk.top();
					stk.pop();
					stk.top().add(tmp);
				}
				++it;
			}
		}
		return stk.top().getList().front();
	}
};

本代码提交AC,用时19MS。
解法2,递归法。如果当前的字符串是一个裸的整数的话,类似于样例1,则直接返回以该数为参数的NestedInteger;否则剥掉左括号[,递归反序列化,把递归的结果add到当前的NestedInteger中。
代码如下:

class Solution {
private:
	NestedInteger deserialize(istringstream &in) {
		int number;
		if (in >> number)
			return NestedInteger(number);
		in.clear();
		in.get();
		NestedInteger list;
		while (in.peek() != ']') {
			list.add(deserialize(in));
			if (in.peek() == ',')in.get();
		}
		in.get();
		return list;
	}
public:
	NestedInteger deserialize(string s) {
		istringstream in(s);
		return deserialize(in);
	}
};

本代码提交AC,用时19MS。
参考1,栈:https://discuss.leetcode.com/topic/54904/c-non-recursive-one-pass-solution-using-stack-a-possible-implementation-of-nestedinteger
参考2,递归:https://discuss.leetcode.com/topic/54258/python-c-solutions/10

LeetCode Find K Pairs with Smallest Sums

LeetCode Find K Pairs with Smallest Sums
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u,v) which consists of one element from the first array and one element from the second array.
Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.
Example 1:

Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3
Return: [1,2],[1,4],[1,6]
The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

Given nums1 = [1,1,2], nums2 = [1,2,3],  k = 2
Return: [1,1],[1,1]
The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

Given nums1 = [1,2], nums2 = [3],  k = 3
Return: [1,3],[2,3]
All possible pairs are returned from the sequence:
[1,3],[2,3]

给定两个从小到大排列的数组,要求选出k个数对(u_i,v_i),其中u_i来自第一个数组nums1,v_i来自第二个数组v_i,使得这k个数对的和最小。
要使得k各数对的和最小,那么这k个数对本身肯定是前k个最小的。遇到要选前k个最小或者最大的问题,一般都用优先队列(堆)来做,比如维护一个大小为k的大顶堆,当堆中元素大于k时,弹出堆顶的最大的元素,也就是堆中维护的一直是当前最小的前k个元素。当所有元素都遍历完时,返回堆中所有元素即可。
优先队列采用STL中的priority_queue,需要自定义比较运算符。
完整代码如下:

class Solution {
private:
	struct P {
		int x, y;
		P(int x_, int y_) :x(x_), y(y_) {};
		bool operator<(const P& p) const{
			return (this->x + this->y) < (p.x + p.y);
		}
		bool operator>(const P& p) const {
			return (this->x + this->y) > (p.x + p.y);
		}
	};
public:
	vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
		priority_queue<P> pq; // 大顶堆
		for (int i = 0; i < nums1.size(); ++i) {
			for (int j = 0; j < nums2.size(); ++j) {
				P p(nums1[i], nums2[j]);
				pq.push(p);
				if (pq.size() > k)pq.pop(); // 弹出最大元素
			}
		}
		vector<pair<int, int>> ans;
		while (!pq.empty()) { // 保留的都是最小元素
			ans.push_back(pair<int, int>(pq.top().x, pq.top().y));
			pq.pop();
		}
		return ans;
	}
};

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

LeetCode Tag Validator

LeetCode Tag Validator
Given a string representing a code snippet, you need to implement a tag validator to parse the code and return whether it is valid. A code snippet is valid if all the following rules hold:

  1. The code must be wrapped in a valid closed tag. Otherwise, the code is invalid.
  2. A closed tag (not necessarily valid) has exactly the following format : <TAG_NAME>TAG_CONTENT</TAG_NAME>. Among them, <TAG_NAME> is the start tag, and </TAG_NAME> is the end tag. The TAG_NAME in start and end tags should be the same. A closed tag is valid if and only if the TAG_NAME and TAG_CONTENT are valid.
  3. A valid TAG_NAME only contain upper-case letters, and has length in range [1,9]. Otherwise, the TAG_NAME is invalid.
  4. A valid TAG_CONTENT may contain other valid closed tags, cdata and any characters (see note1) EXCEPT unmatched <, unmatched start and end tag, and unmatched or closed tags with invalid TAG_NAME. Otherwise, the TAG_CONTENT is invalid.
  5. A start tag is unmatched if no end tag exists with the same TAG_NAME, and vice versa. However, you also need to consider the issue of unbalanced when tags are nested.
  6. A < is unmatched if you cannot find a subsequent >. And when you find a < or </, all the subsequent characters until the next > should be parsed as TAG_NAME (not necessarily valid).
  7. The cdata has the following format : <![CDATA[CDATA_CONTENT]]>. The range of CDATA_CONTENT is defined as the characters between <![CDATA[ and the first subsequent]]>.
  8. CDATA_CONTENT may contain any characters. The function of cdata is to forbid the validator to parse CDATA_CONTENT, so even it has some characters that can be parsed as tag (no matter valid or invalid), you should treat it as regular characters.

Valid Code Examples:

Input: "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: True
Explanation:
The code is wrapped in a closed tag : <DIV> and </DIV>.
The TAG_NAME is valid, the TAG_CONTENT consists of some characters and cdata.
Although CDATA_CONTENT has unmatched start tag with invalid TAG_NAME, it should be considered as plain text, not parsed as tag.
So TAG_CONTENT is valid, and then the code is valid. Thus return true.
Input: "<DIV>>>  ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>"
Output: True
Explanation:
We first separate the code into : start_tag|tag_content|end_tag.
start_tag -> "<DIV>"
end_tag -> "</DIV>"
tag_content could also be separated into : text1|cdata|text2.
text1 -> ">>  ![cdata[]] "
cdata -> "<![CDATA[<div>]>]]>", where the CDATA_CONTENT is "<div>]>"
text2 -> "]]>>]"
The reason why start_tag is NOT "<DIV>>>" is because of the rule 6.
The reason why cdata is NOT "<![CDATA[<div>]>]]>]]>" is because of the rule 7.

Invalid Code Examples:

Input: "<A>  <B> </A>   </B>"
Output: False
Explanation: Unbalanced. If "<A>" is closed, then "<B>" must be unmatched, and vice versa.
Input: "<DIV>  div tag is not closed  <DIV>"
Output: False
Input: "<DIV>  unmatched <  </DIV>"
Output: False
Input: "<DIV> closed tags with invalid tag name  <b>123</b> </DIV>"
Output: False
Input: "<DIV> unmatched tags with invalid tag name  </1234567890> and <CDATA[[]]>  </DIV>"
Output: False
Input: "<DIV>  unmatched start tag <B>  and unmatched end tag </C>  </DIV>"
Output: False

Note:

  1. For simplicity, you could assume the input code (including the any characters mentioned above) only contain letters, digits, '<','>','/','!','[',']' and ' '.

本题需要写一个检查简单html源代码标签是否匹配的程序。规则有很多,8条,比如tag长度必须在[1,9],且必须是大写字母,还有<![CDATA[CDATA_CONTENT]]>这个东西,经常会在html源代码中看见。
这题在比赛的时候没想清楚,思路比较乱。比赛结束之后,看了讨论区的解答,感觉思路好清晰,借鉴过来。
需要检查的主要有两个部分,一是Tag标签匹配,二是cdata。对于cdata,只要找到,则可以过滤掉<![CDATA[和]]>之间的所有内容。对于Tag标签匹配,类似括号匹配,可以用栈来实现。
但是因为Tag和cdata的开头都有<,我们匹配的时候, 应该从特殊到一般,即首先考虑是<![CDATA,其次考虑是</,然后考虑是<,最后就是一般性的字符了。
当遇到<![CDATA时,找到对应的]]>,下标快速跳到]]>的下一位。
当遇到</时,说明遇到了一个结束Tag,此时判断Tag是否合法,如果合法,从栈中弹出开始Tag,判断开始Tag和结束Tag是否匹配。
当遇到<时,说明遇到了一个开始Tag,判断Tag是否合法,如果合法,则压栈。
如果是一般性的字符,下标直接向前进。
需要注意的是,如果i!=0但是栈为空,说明当前的字符不在某个Tag标签内,比如这个样例:<![CDATA[wahaha]]]><![CDATA[]> wahaha]]>,一上来就是cdata,这是不合法的,因为所有内容都应该在标签对内。
完整代码如下:

class Solution {
private:
	bool checkTag(const string &tag) {
		if (tag.size() < 1 || tag.size() > 9)return false;
		for (const auto &c : tag) {
			if (!isupper(c))return false;
		}
		return true;
	}
public:
	bool isValid(string code) {
		stack<string> stk;
		int i = 0;
		while (i < code.size()) {
			if (i > 0 && stk.empty())return false;
			if (code.substr(i, 9) == "<![CDATA[") {
				int end = code.find("]]>", i);
				if (end == string::npos)return false;
				i = end + 3;
			}
			else if (code.substr(i, 2) == "</") {
				int end = code.find('>', i);
				if (end == string::npos)return false;
				string tag = code.substr(i + 2, end - i - 2);
				if (!checkTag(tag))return false;
				if (stk.empty() || stk.top() != tag)return false;
				else stk.pop();
				i = end + 1;
			}
			else if (code[i] == '<') {
				int end = code.find('>', i);
				if (end == string::npos)return false;
				string tag = code.substr(i + 1, end - i - 1);
				if (!checkTag(tag))return false;
				stk.push(tag);
				i = end + 1;
			}
			else {
				++i;
			}
		}
		return stk.empty();
	}
};

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

LeetCode Kth Smallest Element in a Sorted Matrix

LeetCode Kth Smallest Element in a Sorted Matrix
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n2.


给定一个矩阵,该矩阵每行和每列都是有序的,要找出第k小的数。
如果只利用每行或者每列是有序的,则可以使用堆解决。我们以行为例,那么每行都是有序的,则相当于把所有行进行n路归并,然后找到第k小的数。所以我们构建一个最小堆,首先把所有行的首元素放到堆中,然后n路归并k次,每次弹出堆顶元素(即当前最小值),然后把原堆顶元素所在行的下一个元素放入堆中。k次归并结束之后,堆顶元素即为第k小的元素。
代码如下:

class Solution {
private:
	struct Node {
		int val, row, col;
		Node(int v = 0, int r = 0, int c = 0) :val(v), row(r), col(c) {};
		friend bool operator<(const Node& n1, const Node& n2) {
			return n1.val > n2.val;
		}
	};
public:
	int kthSmallest(vector<vector<int>>& matrix, int k) {
		int n = matrix.size();
		priority_queue<Node> pn;
		for (int i = 0; i < n; ++i)pn.push(Node(matrix[i][0], i, 0));
		Node t;
		while (k--) {
			t = pn.top();
			pn.pop();
			if (t.col < n - 1)pn.push(Node(matrix[t.row][t.col + 1], t.row, t.col + 1));
		}
		return t.val;
	}
};

本代码提交AC,用时45MS。时间复杂度是O(klgn),堆的大小为n,每次归并调整堆需要lgn时间,一共需要归并k次,所以总的时间复杂度是O(klgn)。
另外用二分的方法可以同时利用行有序和列有序的特点。这种矩阵可以看成一个曲面,曲面的最低点为左上角元素left,最高点为右下角元素right,所以曲面就是从左上角向上延伸到右下角(想象一下MATLAB画的图)。那么第k小的数肯定在[left,right]范围内,我们可以二分查找这个区间。假设中点是mid,则我们在每一行找找比mid小的数有多少个,加起来如果等于cnt,则说明mid这个数排在第cnt位。因为每一行也是有序的,所以可以直接用upper_bound查找第一个比mid大的数。
代码如下:

class Solution {
public:
	int kthSmallest(vector<vector<int>>& matrix, int k) {
		int n = matrix.size(), left = matrix[0][0], right = matrix[n - 1][n - 1];
		while (left <= right) {
			int mid = left + (right - left) / 2;
			int cnt = 0;
			for (int i = 0; i < n; ++i) {
				cnt += upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
			}
			if (cnt < k)left = mid + 1;
			else right = mid - 1;
		}
		return left;
	}
};

本代码提交AC,用时43MS。时间复杂度是O(lgX nlgn),X为[left,right]的区间大小,ngln是对于每个mid,都需要在每一行二分查找比mid小的数的个数。
还可以将上述复杂度降为O(lgX n)。就是在找cnt,不需要每一行都二分查找,我们可以从矩阵的左下角往右上角阶梯查找,如果要查找的数更大,则往右移,否则往上移,每次查询只需要O(n)的时间,所以总时间是O(lgX n)。
代码如下:

class Solution {
private:
	int count_less_equal(vector<vector<int>>& matrix, int num) {
		int n = matrix.size(), i = n - 1, j = 0, cnt = 0;
		while (i >= 0 && j < n) {
			if (matrix[i][j] <= num) {
				cnt += i + 1;
				++j;
			}
			else --i;
		}
		return cnt;
	}
public:
	int kthSmallest(vector<vector<int>>& matrix, int k) {
		int n = matrix.size(), left = matrix[0][0], right = matrix[n - 1][n - 1];
		while (left <= right) {
			int mid = left + (right - left) / 2;
			int cnt = count_less_equal(matrix, mid);
			if (cnt < k)left = mid + 1;
			else right = mid - 1;
		}
		return left;
	}
};

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

LeetCode Verify Preorder Serialization of a Binary Tree

LeetCode Verify Preorder Serialization of a Binary Tree
One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.
Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
Each comma separated value in the string must be either an integer or a character '#' representing null pointer.
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".
Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true
Example 2:
"1,#"
Return false
Example 3:
"9,#,#,1"
Return false


根据树的先序遍历结果,在不重构树的情况下,判断该先序遍历是否合法。
解法1,使用栈。因为先序遍历的顺序是根左右,如果我们遇到序列x,#,#,其中x不是#时,说明x的左右孩子都是#,此时,我们将x,#,#替换为#,表示将以x为根的子树替换为一个#。如此循环,如果栈中最终只剩下一个#,说明该序列合法。
比如样例"9,3,4,#,#,1,#,#,2,#,6,#,#":

  • 9,3,4,#,# → 9,3,#
  • 9,3,#,1,#,# → 9,3,#,# → 9,#
  • 9,#,2,#,6,#,# → 9,#,2,#,# → 9,#,# → #

不需要担心遇到x,#,#,#的情况,因为在遍历到第二个#时,就符合x,#,#的pattern了,会把x,#,#变成#。
代码如下:

class Solution {
public:
	bool isValidSerialization(string preorder) {
		stack<string> stk;
		int i = 0, j = 0, n = preorder.size();
		while (j < n) {
			while (j < n&&preorder[j] != ',')++j;
			string node = preorder.substr(i, j - i);
			if (node == "#") {
				while (!stk.empty() && stk.top() == "#") {
					stk.pop();
					if (stk.empty())return false;
					stk.pop();
				}
			}
			stk.push(node);
			i = ++j;
		}
		return stk.size() == 1 && stk.top() == "#";
	}
};

本代码提交AC,用时6MS。
解法2,利用度的信息。一棵二叉树通过题目中的加#策略之后,变成了一棵二叉树。这里的满是指一个节点要么有两个孩子,要么没有孩子,不存在有一个孩子的情况。(把#也看成孩子)
那么如果是叶子节点,则只贡献一个入度;如果是非叶子节点,则贡献一个入度和两个出度。所以diff=outdegree-indegree不可能是负数。
所以当来了一个节点,先--diff,因为这个节点肯定会贡献一个入度。然后判断这个节点如果是非叶子节点,则diff+=2,因为非叶子节点贡献两个出度。程序结束时,如果diff==0,则说明序列合法,否则不合法。因为就完整的树来说,入度肯定等于出度的,一条边对于父亲节点来说贡献出度,但对于孩子节点来说,贡献入度,所以总的入度和出度是相等的。
初始时,因为根节点没有入度,但是在外层while循环中,我们把根节点也看成普通的节点了。普通节点假设是有入度的,所以一进来就会--diff。所以初始时给根节点也补上一个入度,即diff=1,这样进入while之后,--diff不至于小于0。
代码如下:

class Solution {
public:
	bool isValidSerialization(string preorder) {
		int i = 0, j = 0, n = preorder.size(), diff = 1;
		while (j < n) {
			while (j < n&&preorder[j] != ',')++j;
			string node = preorder.substr(i, j - i);
			if (--diff < 0)return false;
			if (node != "#")diff += 2;
			i = ++j;
		}
		return diff == 0;
	}
};

本代码提交AC,用时3MS。
解法3,也是利用度的信息。前面说了,通过题目中的策略,一棵普通二叉树已经变成了一棵二叉树,满二叉树的特点是叶子节点的数目=非叶子节点的数目+1。简单证明如下:
假设叶子节点数为leaves,非叶子节点数为nonleaves。则总节点数为leaves+nonleaves,总边数就是leaves+nonleaves-1。一条边贡献两个度,所以总度数就是2(leaves+nonleaves-1)。从另一个角度,一个叶子节点贡献一个度,一个非叶子节点贡献3个度,根节点也是非叶子节点,但它只贡献两个读,所以总度数加起来就是leaves+3*nonleaves-1。令2(leaves+nonleaves-1)=leaves+3*nonleaves-1,就解出了leaves=nonleaves+1。
因为先序遍历是根左右,所以我们找一个满足leaves=nonleaves+1的最短前缀,如果这确实是一个合法的序列,则这个最短前缀就应该是序列本身。因为一棵满二叉树,在遍历的过程中是不会满足leaves=nonleaves+1的,只有当整棵树都遍历完之后才会满足这个条件。

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

上面这棵树,虽然在遍历到节点2时,如果不再往下遍历了,看起来也是满二叉树,但是2是有孩子的,所以会被判断为nonleaves,所以还是不满足leaves=nonleaves+1。
代码如下:

class Solution3 {
public:
	bool isValidSerialization(string preorder) {
		int leaves = 0, nonleaves = 0;
		int i = 0, j = 0, n = preorder.size();
		while (j < n) {
			while (j < n&&preorder[j] != ',')++j;
			string node = preorder.substr(i, j - i);
			if (node == "#")++leaves;
			else ++nonleaves;
			i = ++j;
			if (leaves - nonleaves == 1 && j < n)return false;
		}
		return leaves - nonleaves == 1;
	}
};

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