# LeetCode Bulb Switcher IV

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'

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

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;
}
};

# LeetCode Diagonal Traverse II

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.

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;
}
};

# LeetCode Bulb Switcher

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.

# LeetCode Count Numbers with Unique Digits

LeetCode Count Numbers with Unique Digits Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n. Example: Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99]) Hint:

1. A direct way is to use the backtracking approach.
2. Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
3. This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
4. Let f(k) = count of numbers with unique digits with length equals k.
5. f(1) = 10, …, f(k) = 9 * 9 * 8 * … (9 – k + 2) [The first factor is 9 because a number cannot start with 0].

• k=1，一位数，可以填入0~9这10个数，结果为10
• k=2，两位数，十位填入1~9这9个数，个位填入0~9中除了十位的那个数字，有9种情况，结果为9*9
• k=3，三位数，百位填入1~9这9个数字，十位填入0~9中除了百位的那个数字，有9种情况，个位填入0~9中除了百位和十位的那两个数字，有8种情况，结果为9*9*8
• k=n，结果为9*9*8*…*(9-n+2)

# LeetCode Queue Reconstruction by Height

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]]

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]

# LeetCode Integer Break

343. Integer Break

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note: You may assume that n is not less than 2 and not larger than 58.

• 0：0
• 1：0
• 2：1=1*1
• 3：2=2*1
• 4：4=2*2
• 5：6=3*2
• 6：9=3*3
• 7：12=3*4
• 8：18=3*3*2
• 9：27=3*3*3
• 10：36=3*3*4

class Solution {
public:
int integerBreak(int n)
{
if (n <= 3)
return n – 1;
int ans = 1;
while (n > 4) {
ans *= 3;
n -= 3;
}
return ans * n;
}
};

class Solution {
public:
int integerBreak(int n)
{
vector<int> dp = { 0, 0, 1, 2, 4, 6, 9 };
for (int i = 7; i <= n; ++i)
dp.push_back(dp[i – 3] * 3);
return dp[n];
}
};

# LeetCode Bitwise AND of Numbers Range

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

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

# LeetCode Elimination Game

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

# LeetCode Magical String

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.

# LeetCode Single Number II

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

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;
}
};

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;
}
};