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。

1424. Diagonal Traverse II

Given a list of lists of integers, nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]

Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

Example 3:

Input: nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]]
Output: [1,4,2,5,3,8,6,9,7,10,11]

Example 4:

Input: nums = [[1,2,3,4,5,6]]
Output: [1,2,3,4,5,6]

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i].length <= 10^5
• 1 <= nums[i][j] <= 10^9
• There at most 10^5 elements in nums.

---

如上图所示，给定一个残缺矩阵，要求遍历每个对角线，输出所有元素的值。

朴素解法会TLE，特别是如果有某一行或某一列比其他行列长特别多的情况。

提示解法：观察规律发现，处于同一对角线的元素的行列下标之和相等。所以我们可以把所有元素的行列下标进行排序，如果下标和相等，则处于同一对角线，按行下标从大到小排序；如果下标和不相等，则按下标和从小到大排序。完整代码如下：

bool cmp(const pair<int, int> &p1, const pair<int, int> &p2) {
	int sum1 = p1.first + p1.second, sum2 = p2.first + p2.second;
	if (sum1 == sum2) {
		return p1.first > p2.first;
	}
	else {
		return sum1 < sum2;
	}
}
class Solution {
public:
	vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
		vector<pair<int, int>> idxs;
		for (int i = 0; i < nums.size(); ++i) {
			for (int j = 0; j < nums[i].size(); ++j) {
				idxs.push_back(make_pair(i, j));
			}
		}
		sort(idxs.begin(), idxs.end(), cmp);
		vector<int> ans;
		for (int i = 0; i < idxs.size(); ++i) {
			ans.push_back(nums[idxs[i].first][idxs[i].second]);
		}
		return ans;
	}
};

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

LeetCode Bulb Switcher There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds. Example:

Given n = 3.
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].
So you should return 1, because there is only one bulb is on.

---

给定n盏灯，第一轮是所有灯都是亮的；第二轮每两盏灯触发（亮变灭或灭变亮）一盏灯；第三轮每三盏灯触发一盏灯；如此循环直到第n轮只触发最后一盏灯。问最后有多少盏灯是亮着的。 首先模拟一把： [cpp] class Solution { public: int bulbSwitch(int n) { if (n == 0)return 0; vector<int> bulbs(n + 1, 1); for (int i = 2; i <= n; ++i) { for (int j = 1; j*i <= n; ++j)bulbs[j*i] = !bulbs[j*i]; } int ans = 0; for (int i = 1; i <= n; ++i)if (bulbs[i])++ans; return ans; } }; [/cpp] 本代码提交TLE，过不了大数据集。 然后就把前10的结果列出来了，在OEIS中找到了序列对应的公式：a(n) = floor(sqrt(n))。后来看了网上的题解，得到了这个通项公式的解释： 如果第i盏灯的i的因子有奇数个，则这盏灯最终是亮的，比如9有1,3,9这3个因子，则第9盏灯会分别在第1、3、9轮被触发，由于第1轮是变亮，经过奇数轮之后还是亮的。如果i的因子有偶数个，则类似的分析可知这盏灯最终是灭的。 那么哪些数的因子个数是奇数呢，只有完全平方数的因子个数是奇数，因为非完全平方数的因子都是成对出现的，比如8=1*8=2*4=4*2，而完全平方数有两个因子是重复的9=1*9=3*3，3相当于1个因子。 1~n有floor(sqrt(n))个完全平方数，所以结果就是floor(sqrt(n))。 代码如下： [cpp] class Solution { public: int bulbSwitch(int n) { return floor(sqrt(n)); } }; [/cpp] 本代码提交AC，用时3MS。]]>

LeetCode Queue Reconstruction by Height Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue. Note: The number of people is less than 1,100. Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

---

本题给了一个存储pair的数组，每个pair是一个(h,k)对，表示身高为h的人，其前面有k个身高大于等于h的人。现在要对这个数组重新排序，使得所有pair都满足其自己的(h,k)约束。 网上有一种很巧妙的方法，先对数组排序，排序规则是h大的在前，如果h相等，则k小的在前。然后新建一个数组，把每个pair插入到下标k的位置。 我们来举个例子，比如样例数据，先按上述规则排序之后变成了： [7,0], [7,1], [6,1], [5,0], [5,2], [4,4] 上述排序规则基于这样一个事实：h越小的，其前面比h大的数越多，越有可能满足其k约束；h相同时，肯定是k小的排前面，因为相同的h对k是有贡献的。 然后新建一个空的数组，不断把上述排好序的元素插入空数组中。

1. [7,0]插入第0个位置，数组为[7,0]
2. [7,1]插入第1个位置，数组为[7,0], [7,1]
3. [6,1]插入第1个位置，数组为[7,0], [6,1], [7,1]
4. [5,0]插入第0个位置，数组为[5,0], [7,0], [6,1], [7,1]
5. [5,2]插入第2个位置，数组为[5,0], [7,0], [5,2], [6,1], [7,1]
6. [4,4]插入第4个位置，数组为[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]

完整代码如下： [cpp] bool comp(const pair<int, int>& p1, const pair<int, int>& p2) { return p1.first > p2.first || (p1.first == p2.first&&p1.second < p2.second); } class Solution { public: vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) { sort(people.begin(), people.end(), comp); vector<pair<int, int>> ans; for (int i = 0; i < people.size(); ++i) { ans.insert(ans.begin() + people[i].second, people[i]); } return ans; } }; [/cpp] 本代码提交AC，用时49MS。]]>

201. Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: [5,7]
Output: 4

Example 2:

Input: [0,1]
Output: 0

---

求把从m~n的所有整数相与的结果。
暴力方法就是从m到n遍历一遍，把所有数都相与一下。但是TLE。
这题明显是个数学题或者找规律题。网上的解法大多数是这样的，把m~n的所有数相与的结果等于m和n这两个数的二进制的最长公共前缀。比如题目中的[5,7]，5和7的二进制分别为101和111，最长公共前缀就是100=4，后两位不一样也要补0。再比如[26,30]，26和30的二进制分别为11010和11110，最长公共前缀为11000=24。
知道这个规律就好办了，因为m和n都是正数，不断同时把m和n往右移，直到他们相等，最后再把m往左移回去就是最终结果。代码如下：

class Solution {
public:
    int rangeBitwiseAnd(int m, int n)
    {
        int offset = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            ++offset;
        }
        return m << offset;
    }
};

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

二刷。看下面的图，m和n最长公共前缀后面的二进制位，在[m,n]范围内都在不停的变化，也就是有0也有1，所以全与之后肯定都是0，只有公共前缀的1相与不会变0，所以要找公共前缀。

LeetCode Elimination Game There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list. Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers. We keep repeating the steps again, alternating left to right and right to left, until a single number remains. Find the last number that remains starting with a list of length n. Example:

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
Output:
6

---

本题介绍了一个消除游戏，就是1~n排列了n个数，先从左往右每隔一个数消除一个（包含1），然后从右往左每隔一个数消除一个（包含最后一个数），如此循环，直到只剩一个数，要求输出这个数。 我一开始以为这是个模拟题，直接用STL的双向链表list模拟了，代码如下： [cpp] class Solution { public: int lastRemaining(int n) { list<int> l; for (int i = 1; i <= n; i++)l.push_back(i); while (l.size() != 1) { list<int>::iterator it = l.begin(); while (it != l.end()) { it = l.erase(it); if (it != l.end())++it; } if (l.size() == 1)break; list<int>::reverse_iterator rit = l.rbegin(); while (rit != l.rend()) { rit = list<int>::reverse_iterator(l.erase(–(rit.base()))); if (rit != l.rend())++rit; } if (l.size() == 1)break; } return *l.begin(); } }; [/cpp] 很不幸，本代码提交TLE，超时了。 网上查题解，这个人讲得比较清楚。一开始1,2,3,4,5,6,7,8,…,n，第一次从左往右消除之后，剩余2,4,6,8…,n，其实就相当于2*(1,2,3,4,…n/2)。但是这个时候我们要对1,2,3,4,…n/2从右往左消除了，那么从右往左和从左往右消除得到的结果有什么规律呢，他们的结果应该是呈镜像对称的，也就是说如果长度为n/2的话，如果从左往右的结果为x，那么从右往左的结果就应该是n/2+1-x；同理如果从右往左的结果是y的话，那么从左往右的结果就应该是n/2+1-y。 代码实现为： [cpp] class Solution { public: int lastRemaining(int n) { return n == 1 ? 1 : 2 * (n / 2 + 1 – lastRemaining(n / 2)); } }; [/cpp] 本代码提交AC，用时49MS。]]>

LeetCode Magical String A magical string S consists of only ‘1’ and ‘2’ and obeys the following rules: The string S is magical because concatenating the number of contiguous occurrences of characters ‘1’ and ‘2’ generates the string Sitself. The first few elements of string S is the following: S = “1221121221221121122……” If we group the consecutive ‘1’s and ‘2’s in S, it will be: 1 22 11 2 1 22 1 22 11 2 11 22 …… and the occurrences of ‘1’s or ‘2’s in each group are: 1 2 2 1 1 2 1 2 2 1 2 2 …… You can see that the occurrence sequence above is the S itself. Given an integer N as input, return the number of ‘1’s in the first N number in the magical string S. Note: N will not exceed 100,000. Example 1:

Input: 6
Output: 3
Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.

---

这道题给了一个magic字符串，具体怎么magic题目说得很清楚了。这个字符串只包含字符1和2，依次计算字符串中连续的1或2出现的次数，把这些数字串起来，构成的一个新的字符串和原字符串是完全一样的！然后问字符串中前n个字符出现1的次数。 这是一个模拟题，我们根据magic的规则模拟生成这个字符串，然后统计一下前n个字符中1出现的次数。 模拟的方法就是把字符串中的数当做原字符串中1或2出现的次数，然后不断在原字符串中追加新的字符。比如开始是122：1表示1出现1次；第一个2表示出现两次，因为前面有1出现1次的约束，所以出现两次的只可能是2；第二个2也表示出现两次，因为前面已经出现了两个2了，所以这里不能再接两个2了（要不然就出现4个2了），只能表示出现了两次1，所以我们可以在原字符串中追加两个1，变为12211。如此不断的模拟下去，直到字符串长度满足要求。 完整代码如下： [cpp] class Solution { public: int magicalString(int n) { string magic = "122"; int pos = 2; while (magic.size() < n) { switch (magic[magic.size()-1]) { case ‘1’: magic += string(magic[pos] – ‘0’, ‘2’); break; case ‘2’: magic += string(magic[pos] – ‘0’, ‘1’); break; } ++pos; } int ans = 0; for (int i = 0; i < n; ++i) { ans += magic[i] == ‘1’ ? 1 : 0; } return ans; } }; [/cpp] 本代码提交AC，用时9MS。]]>

137. Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

---

数组中有出现3次的数，但是也有一个出现1次的数，现在要把这个只出现1次的数找出来。要求是线性时间复杂度和常数空间复杂度。 相比于LeetCode Single Number有难度。网上看到一个很不错的题解，分析得很详细。 初级解法是，把数组中每个数字的对应二进制位加起来，因为3个相同的数对应二进制位加起来之后模3一定等于0，比如5的二进制为101，三个101加起来就是303，每一位模3就是000。所以如果混入了一个只出现一次的数，这样取模之后，剩余位为1的就是我们要找的数的二进制形式。 这种解法需要一个32位的数组，用来统计所有数每一位出现1的次数之和，所以空间复杂度是O(32)=O(1)。时间复杂度的话，相当于O(32n)=O(n)，是线性的。完整代码如下：

class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int bit_len = sizeof(int) * 8;
        vector<int> bit(bit_len, 0);
        for (int i = 0; i < bit_len; ++i) {
            for (int j = 0; j < nums.size(); ++j) {
                bit[i] += (nums[j] & 1);
                nums[j] >>= 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < bit_len; ++i) {
            int r = bit[i] % 3;
            ans |= (r << i);
        }
        return ans;
    }
};

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

高级解法是，使用三个int的每一位表示所有数每一位出现1次数之和的情况，one对应位为1表示这一位出现了1次1，two对应位为1表示这一位出现了2次1，three对应位为1表示这一位出现了3次1。但是one,two,three对应位不可能都同时为1。

通过分析对应位的关系（请看原博客），发现one,two,three可以快速通过位运算计算得到。完整代码如下：

class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int one = 0, two = 0, three = 0;
        for (int i = 0; i < nums.size(); ++i) {
            two |= (one & nums[i]);
            one ^= nums[i];
            three = one & two;
            one -= three;
            two -= three;
        }
        return one;
    }
};

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

初级解法还是好理解一些，会不会是一个通用的解法呢，比如数组中出现1次和出现4次（甚至k次）的数混在一起，都可以通过模k求解呢？