1417. Reformat The String

Given alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).

You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.

Return the reformatted string or return an empty string if it is impossible to reformat the string.

Example 1:

Input: s = "a0b1c2"
Output: "0a1b2c"
Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.

Example 2:

Input: s = "leetcode"
Output: ""
Explanation: "leetcode" has only characters so we cannot separate them by digits.

Example 3:

Input: s = "1229857369"
Output: ""
Explanation: "1229857369" has only digits so we cannot separate them by characters.

Example 4:

Input: s = "covid2019"
Output: "c2o0v1i9d"

Example 5:

Input: s = "ab123"
Output: "1a2b3"

Constraints:

• 1 <= s.length <= 500
• s consists of only lowercase English letters and/or digits.

---

给定一个包含字母和数字的字符串，输出将字母和数字交替排列的字符串，输出任意一个合法的即可。

简单题，首先先统计下字母和数字的个数，要让交替出现，则它们的个数之差必须小于2。然后把个数多的排前面，交替排列即可。完整代码如下：

class Solution {
public:
	string reformat(string s) {
		string alpha = "", digit = "";
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] >= '0'&&s[i] <= '9')digit.push_back(s[i]);
			else alpha.push_back(s[i]);
		}

		int a = alpha.size(), d = digit.size();
		if (abs(a - d) >= 2)return "";
		string ans = "";
		int i = 0, j = 0;
		if (a > d) {
			while (i < a || j < d) {
				ans.push_back(alpha[i++]);
				if (j < d)ans.push_back(digit[j++]);
			}
		}
		else {
			while (i < a || j < d) {
				ans.push_back(digit[j++]);
				if (i < a)ans.push_back(alpha[i++]);
			}
		}
		return ans;
	}
};

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

LCP 08. 剧情触发时间

在战略游戏中，玩家往往需要发展自己的势力来触发各种新的剧情。一个势力的主要属性有三种，分别是文明等级（C），资源储备（R）以及人口数量（H）。在游戏开始时（第 0 天），三种属性的值均为 0。

随着游戏进程的进行，每一天玩家的三种属性都会对应增加，我们用一个二维数组 increase 来表示每天的增加情况。这个二维数组的每个元素是一个长度为 3 的一维数组，例如 [[1,2,1],[3,4,2]] 表示第一天三种属性分别增加 1,2,1 而第二天分别增加 3,4,2。

所有剧情的触发条件也用一个二维数组 requirements 表示。这个二维数组的每个元素是一个长度为 3 的一维数组，对于某个剧情的触发条件 c[i], r[i], h[i]，如果当前 C >= c[i] 且 R >= r[i] 且 H >= h[i] ，则剧情会被触发。

根据所给信息，请计算每个剧情的触发时间，并以一个数组返回。如果某个剧情不会被触发，则该剧情对应的触发时间为 -1 。

示例 1：

输入： increase = [[2,8,4],[2,5,0],[10,9,8]] requirements = [[2,11,3],[15,10,7],[9,17,12],[8,1,14]]

输出: [2,-1,3,-1]

解释：

初始时，C = 0，R = 0，H = 0

第 1 天，C = 2，R = 8，H = 4

第 2 天，C = 4，R = 13，H = 4，此时触发剧情 0

第 3 天，C = 14，R = 22，H = 12，此时触发剧情 2

剧情 1 和 3 无法触发。

示例 2：

输入： increase = [[0,4,5],[4,8,8],[8,6,1],[10,10,0]] requirements = [[12,11,16],[20,2,6],[9,2,6],[10,18,3],[8,14,9]]

输出: [-1,4,3,3,3]

示例 3：

输入： increase = [[1,1,1]] requirements = [[0,0,0]]

输出: [0]

限制：

• 1 <= increase.length <= 10000
• 1 <= requirements.length <= 100000
• 0 <= increase[i] <= 10
• 0 <= requirements[i] <= 100000

---

玩家有c,r,h三个值，每过一天三个值有不同程度的增加，问满足不同阈值的最小天数。

暴力方法两层循环会超时。可以先分别构建c,r,h的递增数组，然后针对每个requirement，在递增数组中二分查找满足阈值的左边界，三个左边界的最大值即为满足3个条件的最小天数。

完整代码如下：

class Solution {
public:
	vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {
		int m = increase.size(), n = requirements.size();
		vector<int> cs(m + 1, 0), rs(m + 1, 0), hs(m + 1, 0);

		for (int i = 0; i < m; ++i) {
			cs[i + 1] = cs[i] + increase[i][0];
			rs[i + 1] = rs[i] + increase[i][1];
			hs[i + 1] = hs[i] + increase[i][2];
		}

		vector<int> ans(n, -1);

		for (int i = 0; i < n; ++i) {
			int minc = lower_bound(cs.begin(), cs.end(), requirements[i][0]) - cs.begin();
			int minr = lower_bound(rs.begin(), rs.end(), requirements[i][1]) - rs.begin();
			int minh = lower_bound(hs.begin(), hs.end(), requirements[i][2]) - hs.begin();
			int cur = max(max(minc, minr), minh);
			if (cur <= m)ans[i] = cur;
		}


		return ans;
	}
};

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

LCP 06. 拿硬币

桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。

示例 1：

输入：[4,2,1]

输出：4

解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。

示例 2：

输入：[2,3,10]

输出：8

限制：

• 1 <= n <= 4
• 1 <= coins[i] <= 10

---

有一个硬币数组，每次可以拿1枚或2枚，问最少拿多少次可以拿完。

简单题，贪心，每次拿2枚。完整代码如下：

class Solution {
public:
	int minCount(vector<int>& coins) {
		int ans = 0;
		for (int i = 0; i < coins.size(); ++i) {
			ans += (coins[i] / 2);
			if (coins[i] % 2 == 1)++ans;
		}
		return ans;
	}
};

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

678. Valid Parenthesis String

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

Example 1:

Input: "()"
Output: True

Example 2:

Input: "(*)"
Output: True

Example 3:

Input: "(*))"
Output: True

Note:

1. The string size will be in the range [1, 100].

---

给定一个字符串，里面包含左括号、右括号和星号，星号可以表示左括号、右括号或空格。问这个字符串是否可能是一个合法的括号字符串。

这题有点难理解，直接看题解。

解法1，两遍扫描法，好理解。星号有3种情况，第一次假设星号全部是左括号，如果能满足左括号总数≥右括号总数，说明字符串中的右括号不会太多，用星号加原有的左括号能抵消掉所有的右括号。第二次假设星号全部是右括号，如果能满足右括号总数≥左括号总数，说明字符串中的左括号不会太多，用星号加原有的右括号能抵消掉所有的左括号。由于星号还可以表示空格，所以如果上述两种情况都满足，则多于的星号可以换成空格。

该解法本质上考虑了两种极端情况，而合法解肯定在这两个极端之间。

在以上两种情况的判断过程中，扫描的时候如果不满足条件可以提前终止。比如假设星号全部是左括号时，从左往右扫描字符串，如果出现右括号数大于左括号数的情况，直接返回false。因为我已经把所有星号假设为左括号了，但还是满足不了右括号，说明右括号太多了，非法。类似的，当假设星号为右括号时，从右往左扫描，也可以提前终止。完整代码如下：

class Solution {
public:
	bool checkValidString(string s) {
		int left_balance = 0;
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == '(' || s[i] == '*')++left_balance;
			else --left_balance;
			if (left_balance < 0)return false;
		}
		if (left_balance == 0)return true;

		int right_balance = 0;
		for (int i = s.size() - 1; i >= 0; --i) {
			if (s[i] == ')' || s[i] == '*')++right_balance;
			else --right_balance;
			if (right_balance < 0)return false;
		}
		return true;
	}
};

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

解法2，一遍扫描法，不太好理解。定义字符串中多余出来的左括号数的最小值min_left和最大值max_left。从左往右扫描字符串，遇到左括号，则min_left和max_left都要加一；遇到右括号，则min_left和max_left都要减一；遇到星号时，把它当做右括号，则min_left减一，把它当做左括号，则max_lfet加一。如果[min_left, max_left]区间包括0，则说明字符串有可能是合法的，因为多余的左括号等于0的话，说明左右括号平衡了。完整代码如下：

class Solution {
public:
	bool checkValidString(string s) {
		int min_left = 0, max_left = 0;
		for (int i = 0; i < s.size(); ++i) {
			min_left += (s[i] == '(' ? 1 : -1);
			max_left += (s[i] != ')' ? 1 : -1);
			if (max_left < 0)break;
			min_left = max(min_left, 0);
		}
		return min_left == 0;
	}
};

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

LeetCode Perform String Shifts

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]:

• direction can be 0 (for left shift) or 1 (for right shift). 
• amount is the amount by which string s is to be shifted.
• A left shift by 1 means remove the first character of s and append it to the end.
• Similarly, a right shift by 1 means remove the last character of s and add it to the beginning.

Return the final string after all operations.

Example 1:

Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation: 
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

Example 2:

Input: s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]]
Output: "efgabcd"
Explanation:  
[1,1] means shift to right by 1. "abcdefg" -> "gabcdef"
[1,1] means shift to right by 1. "gabcdef" -> "fgabcde"
[0,2] means shift to left by 2. "fgabcde" -> "abcdefg"
[1,3] means shift to right by 3. "abcdefg" -> "efgabcd"

Constraints:

• 1 <= s.length <= 100
• s only contains lower case English letters.
• 1 <= shift.length <= 100
• shift[i].length == 2
• 0 <= shift[i][0] <= 1
• 0 <= shift[i][1] <= 100

---

给定一个字符串s，并且给定一些向左或向右shift的操作，问经过这些操作之后，字符串最终的形式是怎样的。

简单题，虽然有很多操作，但可以先把向左的操作数累加，向右的操作数累加，最后比比大小，看最终是向左还是向右。完整代码如下：

class Solution {
public:
	string stringShift(string s, vector<vector<int>>& shift) {
		int left = 0, right = 0, n = s.size();
		for (int i = 0; i < shift.size(); ++i) {
			if (shift[i][0] == 0)left += shift[i][1];
			else right += shift[i][1];
		}
		if (left > right) {
			left -= right;
			left %= n;
			return s.substr(left) + s.substr(0, left);
		}
		else if (right > left) {
			right -= left;
			right %= n;
			return s.substr(n - right) + s.substr(0, n - right);
		}
		else {
			return s;
		}
	}
};

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

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。