Given a binary string s (a string consisting only of ‘0’s and ‘1’s), we can split s into 3 non-empty strings s1, s2, s3 (s1+ s2+ s3 = s).
Return the number of ways s can be split such that the number of characters ‘1’ is the same in s1, s2, and s3.
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
Input: s = "10101"
Output: 4
Explanation: There are four ways to split s in 3 parts where each part contain the same number of letters '1'.
"1|010|1"
"1|01|01"
"10|10|1"
"10|1|01"
Example 2:
Input: s = "1001"
Output: 0
Example 3:
Input: s = "0000"
Output: 3
Explanation: There are three ways to split s in 3 parts.
"0|0|00"
"0|00|0"
"00|0|0"
Example 4:
Input: s = "100100010100110"
Output: 12
Constraints:
s[i] == '0' or s[i] == '1'
3 <= s.length <= 10^5
Solution: Counting
Count how many ones in the binary string as T, if not a factor of 3, then there is no answer.
Count how many positions that have prefix sum of T/3 as l, and how many positions that have prefix sum of T/3*2 as r.
Ans = l * r
But we need to special handle the all zero cases, which equals to C(n-2, 2) = (n – 1) * (n – 2) / 2
Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.
For example, given nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.
Return the number of ways to reordernumssuch that the BST formed is identical to the original BST formed fromnums.
Since the answer may be very large, return it modulo 10^9 + 7.
Example 1:
Input: nums = [2,1,3]
Output: 1
Explanation: We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.
Example 2:
Input: nums = [3,4,5,1,2]
Output: 5
Explanation: The following 5 arrays will yield the same BST:
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]
Example 3:
Input: nums = [1,2,3]
Output: 0
Explanation: There are no other orderings of nums that will yield the same BST.
Example 4:
Input: nums = [3,1,2,5,4,6]
Output: 19
Example 5:
Input: nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]
Output: 216212978
Explanation: The number of ways to reorder nums to get the same BST is 3216212999. Taking this number modulo 10^9 + 7 gives 216212978.
Constraints:
1 <= nums.length <= 1000
1 <= nums[i] <= nums.length
All integers in nums are distinct.
Solution: Recursion + Combinatorics
For a given root (first element of the array), we can split the array into left children (nums[i] < nums[0]) and right children (nums[i] > nums[0]). Assuming there are l nodes for the left and r nodes for the right. We have C(l + r, l) different ways to insert l elements into a (l + r) sized array. Within node l / r nodes, we have ways(left) / ways(right) different ways to re-arrange those nodes. So the total # of ways is: C(l + r, l) * ways(l) * ways(r) Don’t forget to minus one for the final answer.
Given 2n balls of k distinct colors. You will be given an integer array balls of size k where balls[i] is the number of balls of color i.
All the balls will be shuffled uniformly at random, then we will distribute the first n balls to the first box and the remaining n balls to the other box (Please read the explanation of the second example carefully).
Please note that the two boxes are considered different. For example, if we have two balls of colors a and b, and two boxes [] and (), then the distribution [a] (b) is considered different than the distribution [b] (a) (Please read the explanation of the first example carefully).
We want to calculate the probability that the two boxes have the same number of distinct balls.
Example 1:
Input: balls = [1,1]
Output: 1.00000
Explanation: Only 2 ways to divide the balls equally:
- A ball of color 1 to box 1 and a ball of color 2 to box 2
- A ball of color 2 to box 1 and a ball of color 1 to box 2
In both ways, the number of distinct colors in each box is equal. The probability is 2/2 = 1
Example 2:
Input: balls = [2,1,1]
Output: 0.66667
Explanation: We have the set of balls [1, 1, 2, 3]
This set of balls will be shuffled randomly and we may have one of the 12 distinct shuffles with equale probability (i.e. 1/12):
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
After that we add the first two balls to the first box and the second two balls to the second box.
We can see that 8 of these 12 possible random distributions have the same number of distinct colors of balls in each box.
Probability is 8/12 = 0.66667
Example 3:
Input: balls = [1,2,1,2]
Output: 0.60000
Explanation: The set of balls is [1, 2, 2, 3, 4, 4]. It is hard to display all the 180 possible random shuffles of this set but it is easy to check that 108 of them will have the same number of distinct colors in each box.
Probability = 108 / 180 = 0.6
Example 4:
Input: balls = [3,2,1]
Output: 0.30000
Explanation: The set of balls is [1, 1, 1, 2, 2, 3]. It is hard to display all the 60 possible random shuffles of this set but it is easy to check that 18 of them will have the same number of distinct colors in each box.
Probability = 18 / 60 = 0.3
Example 5:
Input: balls = [6,6,6,6,6,6]
Output: 0.90327
Constraints:
1 <= balls.length <= 8
1 <= balls[i] <= 6
sum(balls) is even.
Answers within 10^-5 of the actual value will be accepted as correct.
Solution 0: Permutation (TLE)
Enumerate all permutations of the balls, count valid ones and divide that by the total.
Time complexity: O((8*6)!) = O(48!) After deduplication: O(48!/(6!)^8) ~ 1.7e38 Space complexity: O(8*6)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Author: Huahua, TLE 4/21 passed
classSolution{
public:
doublegetProbability(vector<int>& balls) {
const int k = balls.size();
vector<int>bs;
for(inti=0;i<k;++i)
for(intj=0;j<balls[i];++j)
bs.push_back(i);
constintn=bs.size();
doubletotal=0.0;
doublevalid=0.0;
// d : depth
// used : bitmap of bs's usage
// c1: bitmap of colors of box1
// c2: bitmap of colors of box1
function<void(int,long,int,int)>dfs=[&](int d, long used, int c1, int c2) {
You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colours: Red, Yellow or Green while making sure that no two adjacent cells have the same colour (i.e no two cells that share vertical or horizontal sides have the same colour).
You are given n the number of rows of the grid.
Return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 10^9 + 7.
Example 1:
Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown:
Example 2:
Input: n = 2
Output: 54
Example 3:
Input: n = 3
Output: 246
Example 4:
Input: n = 7
Output: 106494
Example 5:
Input: n = 5000
Output: 30228214
Constraints:
n == grid.length
grid[i].length == 3
1 <= n <= 5000
Solution: DP
dp[i][0] := # of ways to paint i rows with 2 different colors at the i-th row dp[i][1] := # of ways to paint i rows with 3 different colors at the i-th row dp[1][0] = dp[1][1] = 6 dp[i][0] = dp[i-1][0] * 3 + dp[i-1][1] * 2 dp[i][1] = dp[i-1][0] * 2 + dp[i-1][1] * 2
Time complexity: O(n) Space complexity: O(n)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Author: Huahua
classSolution{
public:
intnumOfWays(intn){
constexprintkMod=1e9+7;
// dp[i][0] = # of ways to paint i rows with i-th row has 2 colors (e.g. 121)
// dp[i][1] = # of ways to paint i rows with i-th row has 3 colors (e.g. 123)
// dp[1][0] = dp[1][1] = 6.
vector<vector<long>>dp(n+1,vector<long>(2,6));
for(inti=2;i<=n;++i){
// 121 => 2 colors x 3 {212, 232, 313}, 3 colors x 2 {213, 312}
// 123 => 2 colors x 2 {212, 232}, 3 colors x 2 {231, 312}