5484. Find Kth Bit in Nth Binary String

Given two positive integers n and k, the binary string  Sn is formed as follows:

• S1 = "0"
• Si = Si-1 + "1" + reverse(invert(Si-1)) for i > 1

Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first 4 strings in the above sequence are:

• S1 = "0"
• S2 = "011"
• S3 = "0111001"
• S4 = "011100110110001"

Return the kth bit in Sn. It is guaranteed that k is valid for the given n.

Example 1:

Input: n = 3, k = 1
Output: "0"
Explanation: S3 is "0111001". The first bit is "0".

Example 2:

Input: n = 4, k = 11
Output: "1"
Explanation: S4 is "011100110110001". The 11th bit is "1".

Example 3:

Input: n = 1, k = 1
Output: "0"

Example 4:

Input: n = 2, k = 3
Output: "1"

Constraints:

• 1 <= n <= 20
• 1 <= k <= 2n - 1

---

简单题，直接字符串模拟操作即可，完整代码如下：

class Solution {
private:
	string InvertStr(string &s) {
		string ans = "";
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == '0')ans.push_back('1');
			else ans.push_back('0');
		}
		return ans;
	}
public:
	char findKthBit(int n, int k) {
		string s = "0";
		for (int i = 2; i <= n; ++i) {
			string inv_str = InvertStr(s);
			reverse(inv_str.begin(), inv_str.end());
			s = s + "1" + inv_str;
		}
		return s[k - 1];
	}
};

本代码提交AC。

5472. Shuffle String

Given a string s and an integer array indices of the same length.

The string s will be shuffled such that the character at the ith position moves to indices[i] in the shuffled string.

Return the shuffled string.

Example 1:

Input: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
Output: "leetcode"
Explanation: As shown, "codeleet" becomes "leetcode" after shuffling.

Example 2:

Input: s = "abc", indices = [0,1,2]
Output: "abc"
Explanation: After shuffling, each character remains in its position.

Example 3:

Input: s = "aiohn", indices = [3,1,4,2,0]
Output: "nihao"

Example 4:

Input: s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
Output: "arigatou"

Example 5:

Input: s = "art", indices = [1,0,2]
Output: "rat"

Constraints:

• s.length == indices.length == n
• 1 <= n <= 100
• s contains only lower-case English letters.
• 0 <= indices[i] < n
• All values of indices are unique (i.e. indices is a permutation of the integers from 0 to n - 1).

---

给定一个字符串，根据给定规则进行shuffle，直接照做。代码如下：

class Solution {
public:
	string restoreString(string s, vector<int>& indices) {
		int n = s.size();
		string ans = s;
		for (int i = 0; i < n; ++i)ans[indices[i]] = s[i];
		return ans;
	}
};

本代码提交AC。

1513. Number of Substrings With Only 1s

Given a binary string s (a string consisting only of ‘0’ and ‘1’s).

Return the number of substrings with all characters 1’s.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.

Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.

Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.

Example 4:

Input: s = "000"
Output: 0

Constraints:

• s[i] == '0' or s[i] == '1'
• 1 <= s.length <= 10^5

---

给定一个字符串，问有多少个连续为1的子串。

简单题，先找出最长连续的1，假设长度为n，则这个n长的串能形成(n+1)n/2个1的子串，累加所有这样的子串和即可。代码如下：

const long long kMOD = 1e9 + 7;

class Solution {
	long long CalAccSum(long long l) {
		return (l %kMOD)* ((l + 1) % kMOD) / 2;
	}
public:
	int numSub(string s) {

		long long ans = 0;
		int i = 0, j = 0, n = s.size();
		while (i < n) {
			while (i < n&&s[i] == '0')++i;
			if (i >= n)break;
			j = i + 1;
			while (j < n&&s[j] == '1')++j;
			int m = j - i;
			ans += CalAccSum(m) % kMOD;
			i = j;
		}
		return ans % kMOD;
	}
};

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

5416. Check If a Word Occurs As a Prefix of Any Word in a Sentence

Given a sentence that consists of some words separated by a single space, and a searchWord.

You have to check if searchWord is a prefix of any word in sentence.

Return the index of the word in sentence where searchWord is a prefix of this word (1-indexed).

If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.

A prefix of a string S is any leading contiguous substring of S.

Example 1:

Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.

Example 2:

Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.

Example 3:

Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.

Example 4:

Input: sentence = "i use triple pillow", searchWord = "pill"
Output: 4

Example 5:

Input: sentence = "hello from the other side", searchWord = "they"
Output: -1

Constraints:

• 1 <= sentence.length <= 100
• 1 <= searchWord.length <= 10
• sentence consists of lowercase English letters and spaces.
• searchWord consists of lowercase English letters.

---

给定一个句子和一个待搜索词，问该搜索词是否可能是这个句子中某个词的前缀。

直接暴力搜索即可，因为指定必须是前缀，所以其实直接截取相同长度的前缀判断相等即可。

class Solution {
public:
	int isPrefixOfWord(string sentence, string searchWord) {
		int idx = 1, i = 0, j = 0, n = sentence.size();
		while (i < n) {
			j = i + 1;
			while (j < n&&sentence[j] != ' ')++j;
			string cur = sentence.substr(i, j - i);
			size_t pos = cur.find(searchWord);
			if (pos != string::npos&&pos == 0) {
				return idx;
			}
			++idx;
			i = j + 1;
		}
		return -1;
	}
};

本代码提交AC。

1418. Display Table of Food Orders in a Restaurant

Given the array orders, which represents the orders that customers have done in a restaurant. More specifically orders[i]=[customerNamei,tableNumberi,foodItemi] where customerNamei is the name of the customer, tableNumberi is the table customer sit at, and foodItemi is the item customer orders.

Return the restaurant’s “display table”. The “display table” is a table whose row entries denote how many of each food item each table ordered. The first column is the table number and the remaining columns correspond to each food item in alphabetical order. The first row should be a header whose first column is “Table”, followed by the names of the food items. Note that the customer names are not part of the table. Additionally, the rows should be sorted in numerically increasing order.

Example 1:

Input: orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]]
Output: [["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],["3","0","2","1","0"],["5","0","1","0","1"],["10","1","0","0","0"]] 
Explanation:
The displaying table looks like:
Table,Beef Burrito,Ceviche,Fried Chicken,Water
3    ,0           ,2      ,1            ,0
5    ,0           ,1      ,0            ,1
10   ,1           ,0      ,0            ,0
For the table 3: David orders "Ceviche" and "Fried Chicken", and Rous orders "Ceviche".
For the table 5: Carla orders "Water" and "Ceviche".
For the table 10: Corina orders "Beef Burrito". 

Example 2:

Input: orders = [["James","12","Fried Chicken"],["Ratesh","12","Fried Chicken"],["Amadeus","12","Fried Chicken"],["Adam","1","Canadian Waffles"],["Brianna","1","Canadian Waffles"]]
Output: [["Table","Canadian Waffles","Fried Chicken"],["1","2","0"],["12","0","3"]] 
Explanation: 
For the table 1: Adam and Brianna order "Canadian Waffles".
For the table 12: James, Ratesh and Amadeus order "Fried Chicken".

Example 3:

Input: orders = [["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]]
Output: [["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]]

Constraints:

• 1 <= orders.length <= 5 * 10^4
• orders[i].length == 3
• 1 <= customerNamei.length, foodItemi.length <= 20
• customerNamei and foodItemi consist of lowercase and uppercase English letters and the space character.
• tableNumberi is a valid integer between 1 and 500.

---

很啰嗦的一个题目。给定一系列顾客的点餐清单，输出整个餐厅的点餐信息表。直接按照题意做就行，题目要求行按桌号升序排列，列按菜名字母序排列，所以行可以用vector下标存储，菜名放到set里会自动有序排列。

完整代码如下：

class Solution {
public:
	vector<vector<string>> displayTable(vector<vector<string>>& orders) {
		vector<map<string, int>> tables(501, map<string, int>());
		set<string> allfoods;
		for (int i = 0; i < orders.size(); ++i) {
			string name = orders[i][0], tb = orders[i][1], food = orders[i][2];
			int ntb = stoi(tb.c_str());
			++tables[ntb][food];
			allfoods.insert(food);
		}
		vector<vector<string>> ans;
		vector<string> header;
		header.push_back("Table");
		for (set<string>::iterator it = allfoods.begin(); it != allfoods.end(); ++it)header.push_back(*it);
		ans.push_back(header);
		for (int i = 1; i <= 500; ++i) {
			vector<string> cur;
			if (tables[i].size() > 0) {
				cur.push_back(to_string(i));
				for (set<string>::iterator it = allfoods.begin(); it != allfoods.end(); ++it) {
					cur.push_back(to_string(tables[i][*it]));
				}
				ans.push_back(cur);
			}
		}
		return ans;
	}
};

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

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。

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。