1046. Last Stone Weight

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

• If x == y, both stones are totally destroyed;
• If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)

Example 1:

Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

Note:

1. 1 <= stones.length <= 30
2. 1 <= stones[i] <= 1000

给定一个数组，每个数表示一个石头的质量，每次从数组中选两个最终的石头，如果相等，则两个石头都砸碎，不相等这把质量差再次放入数组。问最终剩余质量是多少。

简单模拟题，使用最大堆来装所有石头的质量，代码如下：

class Solution {
public:
	int lastStoneWeight(vector<int>& stones) {
		priority_queue<int,vector<int>,std::less<int>> pq(stones.begin(),stones.end());
		while (pq.size() >= 2) {
			int first = pq.top();
			pq.pop();
			int second = pq.top();
			pq.pop();

			if (first != second)pq.push(first - second);
		}
		if (pq.size() == 0)return 0;
		else return pq.top();
	}
};

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

1408. String Matching in an Array

Given an array of string words. Return all strings in words which is substring of another word in any order. 

String words[i] is substring of words[j], if can be obtained removing some characters to left and/or right side of words[j].

Example 1:

Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is substring of "mass" and "hero" is substring of "superhero".
["hero","as"] is also a valid answer.

Example 2:

Input: words = ["leetcode","et","code"]
Output: ["et","code"]
Explanation: "et", "code" are substring of "leetcode".

Example 3:

Input: words = ["blue","green","bu"]
Output: []

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 30
• words[i] contains only lowercase English letters.
• It’s guaranteed that words[i] will be unique.

给定一个字符串数组，如果某个字符串是其他字符串的子串，则输出，找出所有这种字符串。

简单题，直接两遍for循环查找即可，代码如下：

class Solution {
public:
	vector<string> stringMatching(vector<string>& words) {
		vector<string> ans;
		for (int i = 0; i < words.size(); ++i) {
			for (int j = 0; j < words.size(); ++j) {
				if (i == j)continue;
				if (words[j].find(words[i]) != string::npos) {
					ans.push_back(words[i]);
					break;
				}
			}
		}
		return ans;
	}
};

本代码提交AC，用时8MS。

1409. Queries on a Permutation With Key

Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:

• In the beginning, you have the permutation P=[1,2,3,...,m].
• For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the beginning of the permutation P. Notice that the position of queries[i] in P is the result for queries[i].

Return an array containing the result for the given queries.

Example 1:

Input: queries = [3,1,2,1], m = 5
Output: [2,1,2,1] 
Explanation: The queries are processed as follow: 
For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2, then we move 3 to the beginning of P resulting in P=[3,1,2,4,5]. 
For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,3,2,4,5]. 
For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is 2, then we move 2 to the beginning of P resulting in P=[2,1,3,4,5]. 
For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,2,3,4,5]. 
Therefore, the array containing the result is [2,1,2,1].  

Example 2:

Input: queries = [4,1,2,2], m = 4
Output: [3,1,2,0]

Example 3:

Input: queries = [7,5,5,8,3], m = 8
Output: [6,5,0,7,5]

Constraints:

• 1 <= m <= 10^3
• 1 <= queries.length <= m
• 1 <= queries[i] <= m

初始时给定一个P=[1,2,…,m]的数组，然后有一个queries数组，对于每一个query，问其在P中的下标，并且将该元素移到P的开头，最后问queries数组中所有query的下标的数组。

模拟题，由于有元素的移动操作，即删除和插入操作，所以这里借用链表来处理。完整代码如下：

class Solution {
public:
	vector<int> processQueries(vector<int>& queries, int m) {
		list<int> lst;
		for (int i = 1; i <= m; ++i)lst.push_back(i);
		vector<int> ans;
		for (int i = 0; i < queries.size(); ++i) {
			int val = queries[i];
			int j = 0;
			list<int>::iterator it = lst.begin();
			while (it != lst.end()) {
				if (*it == val) {
					ans.push_back(j);
					lst.erase(it);
					lst.push_front(val);
					break;
				}
				else {
					++it;
					++j;
				}
			}
		}
		return ans;
	}
};

本代码提交AC，用时28MS。

1410. HTML Entity Parser

HTML entity parser is the parser that takes HTML code as input and replace all the entities of the special characters by the characters itself.

The special characters and their entities for HTML are:

• Quotation Mark: the entity is " and symbol character is ".
• Single Quote Mark: the entity is ' and symbol character is '.
• Ampersand: the entity is & and symbol character is &.
• Greater Than Sign: the entity is > and symbol character is >.
• Less Than Sign: the entity is < and symbol character is <.
• Slash: the entity is ⁄ and symbol character is /.

Given the input text string to the HTML parser, you have to implement the entity parser.

Return the text after replacing the entities by the special characters.

Example 1:

Input: text = "& is an HTML entity but &ambassador; is not."
Output: "& is an HTML entity but &ambassador; is not."
Explanation: The parser will replace the & entity by &

Example 2:

Input: text = "and I quote: "...""
Output: "and I quote: \"...\""

Example 3:

Input: text = "Stay home! Practice on Leetcode :)"
Output: "Stay home! Practice on Leetcode :)"

Example 4:

Input: text = "x > y && x < y is always false"
Output: "x > y && x < y is always false"

Example 5:

Input: text = "leetcode.com⁄problemset⁄all"
Output: "leetcode.com/problemset/all"

Constraints:

• 1 <= text.length <= 10^5
• The string may contain any possible characters out of all the 256 ASCII characters.

给定一个HTML字符串，要求把其中的特殊符号转换为其原来的表示。

简单题，遍历字符串，找到以&开头，以;结尾的子串，根据情况把它转换为原来的字符即可。请注意，有可能该子串不属于文中6种情况中的任何一种，此时不需要转义，直接原样拷贝。代码如下：

class Solution {
public:
	string entityParser(string text) {
		int n = text.size(), i = 0;
		string ans = "";
		while (i < n) {
			while (i < n&&text[i] != '&') {
				ans.push_back(text[i]);
				++i;
			}
			if (i >= n)break;
			int j = i + 1;
			while (j < n&&text[j] != ';')++j;
			string mark = text.substr(i, j - i + 1);
			if (mark == "&quot;")ans.push_back('\"');
			else if (mark == "&apos;")ans.push_back('\'');
			else if (mark == "&amp;")ans.push_back('&');
			else if (mark == "&gt;")ans.push_back('>');
			else if (mark == "&lt;")ans.push_back('<');
			else if (mark == "&frasl;")ans.push_back('/');
			else ans += mark;
			i = j + 1;
		}
		return ans;
	}
};

本代码提交AC，用时460MS。

844. Backspace String Compare

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:

1. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S and T only contain lowercase letters and '#' characters.

Follow up:

• Can you solve it in O(N) time and O(1) space?

给定两个字符串，其中包含小写字母和#，#表示删除前一个字符。问这两个字符串的最终结果是否一致。

这道题如果不考虑Follow up的话很简单，新建一个string，看到字母就push_back，看到#就pop_back，最后看剩余字符串是否相等即可。

但是Follow up要求只使用O(1)的空间，这就需要思考一下了。思路是这样的，从后往前处理两个字符串，统计#的数目，模拟删除过程，直到无法删除找到一个能被留在最终字符串中的字母，比较S和T的这个字符是否相等。完整代码如下：

class Solution {
public:
	bool backspaceCompare(string S, string T) {
		int i = S.size() - 1, j = T.size() - 1;
		while (i >= 0 || j >= 0) {
			int skipS = 0, skipT = 0;
			while (i >= 0) {
				if (S[i] == '#') {
					++skipS;
					--i;
				}
				else if (skipS > 0) {
					--skipS;
					--i;
				}
				else {
					break;
				}
			}

			while (j >= 0) {
				if (T[j] == '#') {
					++skipT;
					--j;
				}
				else if (skipT > 0) {
					--skipT;
					--j;
				}
				else {
					break;
				}
			}

			if ((i >= 0) != (j >= 0))return false;
			if (i >= 0 && S[i] != T[j])return false;
			--i;
			--j;
		}
		return true;
	}
};

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

876. Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

• The number of nodes in the given list will be between 1 and 100.

给定一个单向链表，要求找到其中间节点。

简单题，快慢指针，快指针的速度是慢指针的2倍，则当快指针走到末尾时，慢指针正好指向中间位置。代码如下：

class Solution {
public:
	ListNode* middleNode(ListNode* head) {
		if (head == NULL || head->next == NULL)return head;
		ListNode *fast = head, *slow = head;
		while (fast->next) {
			fast = fast->next->next;
			slow = slow->next;
			if (fast == NULL)break;
		}
		return slow;
	}
};

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

1396. Design Underground System

Implement the class UndergroundSystem that supports three methods:

1. checkIn(int id, string stationName, int t)

• A customer with id card equal to id, gets in the station stationName at time t.
• A customer can only be checked into one place at a time.

2. checkOut(int id, string stationName, int t)

• A customer with id card equal to id, gets out from the station stationName at time t.

3. getAverageTime(string startStation, string endStation) 

• Returns the average time to travel between the startStation and the endStation.
• The average time is computed from all the previous traveling from startStation to endStation that happened directly.
• Call to getAverageTime is always valid.

You can assume all calls to checkIn and checkOut methods are consistent. That is, if a customer gets in at time t₁ at some station, then it gets out at time t₂ with t₂ > t₁. All events happen in chronological order.

Example 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output
[null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);
undergroundSystem.checkOut(27, "Waterloo", 20);
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge");       // return 14.0. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.0
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 12.0

Constraints:

• There will be at most 20000 operations.
• 1 <= id, t <= 10^6
• All strings consist of uppercase, lowercase English letters and digits.
• 1 <= stationName.length <= 10
• Answers within 10^-5 of the actual value will be accepted as correct.

设计一个地铁记录系统。完整代码如下，使用system记录每条线路的用时和乘坐次数，使用starts记录每个人旅行起点。不用记录终点，因为checkout的时候，把起点取出计算用时即可。

class UndergroundSystem {
private:
	map<string, map<string, pair<int, int>>> system_; // start->end, total time, #travels
	map<int, pair<string, int>> starts_; // travel start station
public:
	UndergroundSystem() {

	}

	void checkIn(int id, string stationName, int t) {
		starts_[id] = make_pair(stationName, t);
	}

	void checkOut(int id, string stationName, int t) {
		string start_station = starts_[id].first;
		int start_time = starts_[id].second;
		starts_.erase(id);
		if (system_.find(start_station) == system_.end()
			|| system_[start_station].find(stationName) == system_[start_station].end()) {
			system_[start_station][stationName] = make_pair(0, 0);
		}
		system_[start_station][stationName].first += (t - start_time);
		system_[start_station][stationName].second += 1;
	}

	double getAverageTime(string startStation, string endStation) {
		return system_[startStation][endStation].first / double(system_[startStation][endStation].second);
	}
};

本代码提交AC，用时744MS。

1395. Count Number of Teams

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

• Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
• A team is valid if:  (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

• n == rating.length
• 1 <= n <= 200
• 1 <= rating[i] <= 10^5

给定一个数组，要求找出这样的升序或者降序的三元组数目。

竞赛阶段，由于n的范围较小，首先尝试暴力O(n^3)解法，代码如下：

class Solution {
public:
	int numTeams(vector<int>& rating) {
		int ans = 0, n = rating.size();
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				for (int k = j + 1; k < n; ++k) {
					if (rating[i] < rating[j] && rating[j] < rating[k])++ans;
					else if (rating[i] > rating[j] && rating[j] > rating[k])++ans;
				}
			}
		}
		return ans;
	}
};

本代码提交AC，用时204MS。

还有更优的O(n^2)的解法。对于每个士兵，统计其左边小于它的数目，和右边大于它的数目，则这两个数相乘即为该士兵能组成的升序数目，类似的可以算到该士兵能组成的降序数目。代码如下：

class Solution {
public:
	int numTeams(vector<int>& rating) {
		int ans = 0, n = rating.size();
		for (int i = 1; i < n - 1; ++i) {
			vector<int> less_num(2, 0), greater_num(2, 0);
			for (int j = 0; j < n; ++j) {
				if (rating[j] < rating[i])++less_num[j < i];
				else if (rating[j] > rating[i])++greater_num[j > i];
			}
			ans += less_num[1] * greater_num[1] + less_num[0] * greater_num[0];
		}
		return ans;
	}
};

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