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。

5483. Make The String Great

Given a string s of lower and upper case English letters.

A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where:

• 0 <= i <= s.length - 2
• s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.

To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

Example 1:

Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".

Example 2:

Input: s = "abBAcC"
Output: ""
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

Example 3:

Input: s = "s"
Output: "s"

Constraints:

• 1 <= s.length <= 100
• s contains only lower and upper case English letters.

给定一个字符串，如果相邻两个字符是同一字母的大小写形式，则需要删除这两个字母，问最终的字符串形式是什么。

简单题，使用栈，完整代码如下：

class Solution {
public:
    string makeGood(string s) {
        stack<char> stk;
        for(int i = 0; i < s.size(); ++i) {
            if(!stk.empty() && abs(stk.top() - s[i]) == 32) {
                stk.pop();
            } else {
                stk.push(s[i]);
            }
        }
        string ans="";
        while(!stk.empty()) {
            ans = string(1, stk.top()) + ans;
            stk.pop();
        }
        return ans;
    }
};

本代码提交AC。

5473. Bulb Switcher IV

There is a room with n bulbs, numbered from 0 to n-1, arranged in a row from left to right. Initially all the bulbs are turned off.

Your task is to obtain the configuration represented by target where target[i] is ‘1’ if the i-th bulb is turned on and is ‘0’ if it is turned off.

You have a switch to flip the state of the bulb, a flip operation is defined as follows:

• Choose any bulb (index i) of your current configuration.
• Flip each bulb from index i to n-1.

When any bulb is flipped it means that if it is 0 it changes to 1 and if it is 1 it changes to 0.

Return the minimum number of flips required to form target.

Example 1:

Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
flip from the third bulb:  "00000" -> "00111"
flip from the first bulb:  "00111" -> "11000"
flip from the second bulb:  "11000" -> "10111"
We need at least 3 flip operations to form target.

Example 2:

Input: target = "101"
Output: 3
Explanation: "000" -> "111" -> "100" -> "101".

Example 3:

Input: target = "00000"
Output: 0

Example 4:

Input: target = "001011101"
Output: 5

Constraints:

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

给一排灯泡，初始时都是灭的，每次可以选第i个灯泡，然后把第i个到最后的所有灯泡的状态翻转。问最少需要多少次操作才能得到目标状态序列。

很有意思的题，观察数据发现数据规模在1e5，数据量比较大，估计只有O(n)算法能过。接着，观察样例，不要被样例的解答给迷惑了。比如第一个例子10111，除了样例的解法，还可以谈心的做，序列变化如下：

0. 00000
1. 11111
2. 10000
3. 10111

即每次从左往右，把第一个不符合target状态的灯及往后的灯都flip，这种方法已经是最优的了。所以对于任意一个灯泡，它至少被翻转的次数就是它前面有多少种连续不同状态的灯泡。比如对于10111的后三个111，它前面有1和0，因为最原始是00，要变成10，则在满足第一个灯泡时有个0->1的翻转，导致第2个灯泡也变了；第二个灯泡也要flip一次；等到111时，它需要翻转的次数就是前面10共有2种特异状态。

所以问题转换为求字符串中有多少个连续相同状态的片段，所有片段数就是需要翻转的次数。另外要注意如果开头是0的话，则开头可以少翻转一次。代码如下：

class Solution {
public:
	int minFlips(string target) {
		int n = target.size();
		int ans = 0;
		int  i = 0;
		while (i < n) {
			int j = i + 1;
			while (j < n&&target[j] == target[i])++j;
			++ans;
			i = j;
		}
		if (target[0] == '0')return ans - 1;
		else return ans;
	}
};

本代码提交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。

76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

给两个字符串S和T，问S中是否存在一个子串，包括T中的所有字符，如果存在，输出最短的那个子串。

hard题，用双指针+滑动窗口。核心思想是找到滑动窗口[i,j)，首先++j，加入右边界的字符；然后检查[i,j)是否能覆盖t；再然后++i，丢掉左边界的字符。

首先设置一个required数组，存储t中每个字符出现的次数，表示滑动窗口[i,j)需要覆盖的每个字符的次数。found表示需要找到的字符总数，如果found==t.size()表示滑动窗口能覆盖t。

首先检查右边界j，如果s[j]在t中，则++found。然后看看found==n?，如果是，则检查左边界，如果左边界s[i]在t中，则i++之后要–found。在窗口滑动过程中记录窗口最小长度。完整代码如下：

class Solution {
public:
	string minWindow(string s, string t) {
		int m = s.size(), n = t.size();
		vector<int> required(128, 0);
		for (int i = 0; i < n; ++i) {
			++required[t[i]];
		}

		int min_len = m + 1, start_id = 0, found = 0;
		int i = 0, j = 0;
		while (j < m) {
			--required[s[j]];
			if (required[s[j]] >= 0) { // s[j]在t中
				++found;
			}
			++j;

			while (found == n) {
				int cur_len = j - i;
				if (cur_len < min_len) {
					min_len = cur_len;
					start_id = i;
				}
				++required[s[i]];
				if (required[s[i]] > 0) --found;
				++i;
			}
		}
		if (min_len == m + 1) return "";
		else return s.substr(start_id, min_len);
	}
};

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

今晚字节跳动三面，面试官问了一个此题的变种，即只给定了字符串s，要找s的一个子串，使得该子串能覆盖s中所有特异的字符，且子串越短越好。可以把面试问题转换为这个问题，即先遍历s，把s中的特异字符拼成一个字符串t，然后调用本题的解法。

5464. Water Bottles

Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Return the maximum number of water bottles you can drink.

Example 1:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

Example 2:

Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle. 
Number of water bottles you can drink: 15 + 3 + 1 = 19.

Example 3:

Input: numBottles = 5, numExchange = 5
Output: 6

Example 4:

Input: numBottles = 2, numExchange = 3
Output: 2

Constraints:

• 1 <= numBottles <= 100
• 2 <= numExchange <= 100

很贴近生活的一个题。初始有n瓶满饮料，喝完之后，可以每m个空瓶子换一瓶新饮料，问最终能喝多少瓶饮料。

直接模拟，代码如下：

class Solution {
public:
	int numWaterBottles(int numBottles, int numExchange) {
		int full = numBottles, empty = 0, div = numExchange;
		int ans = 0;
		while (full + empty >= div) {
			ans += full;
			empty += full;
			full = empty / div;
			empty = empty % div;
		}
		return ans + full;
	}
};

本代码提交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。