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。

1512. Number of Good Pairs

Given an array of integers nums.

A pair (i,j) is called good if nums[i] == nums[j] and i < j.

Return the number of good pairs.

Example 1:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.

Example 3:

Input: nums = [1,2,3]
Output: 0

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

直接按题意做就行：

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

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