Skip to content

Commit 3ebfb0d

Browse files
liuyuboboboliuyubobobo
committed
0790 solved.
1 parent c759b82 commit 3ebfb0d

File tree

5 files changed

+199
-2
lines changed

5 files changed

+199
-2
lines changed

‎0790-Domino-and-Tromino-Tiling/cpp-0790/CMakeLists.txt‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
cmake_minimum_required(VERSION 3.5)
2+
project(D)
3+
4+
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
5+
6+
set(SOURCE_FILES main3.cpp)
7+
add_executable(D ${SOURCE_FILES})

‎0790-Domino-and-Tromino-Tiling/cpp-0790/main.cpp‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
/// Source : https://leetcode.com/problems/domino-and-tromino-tiling/description/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-02-24
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
/// Dynamic Programming
11+
/// dp[i]: how many ways to fill a 2*i tiles
12+
///
13+
/// Time Complexity: O(N^2)
14+
/// Space Complexity: O(N)
15+
class Solution {
16+
17+
public:
18+
int numTilings(int N) {
19+
20+
vector<int> res;
21+
res.push_back(1); // 0
22+
res.push_back(1); // 1
23+
res.push_back(2); // 2
24+
25+
if(N <= 2)
26+
return (int)res[N];
27+
28+
int mod = 1000000007;
29+
for(int i = 3 ; i <= N ; i ++){
30+
// .....A ....AA
31+
// .....A and ....BB
32+
int x = (res[i-1] + res[i-2]) % mod;
33+
34+
// AA112233..nnB
35+
// A112233..nnBB and
36+
// A112233..nnBB
37+
// AA112233..nnB
38+
for(int j = 3 ; i - j >= 0; j += 2){
39+
x = (x + res[i-j]) % mod;
40+
x = (x + res[i-j]) % mod;
41+
}
42+
43+
// AA112233..BB
44+
// A112233..nnB and
45+
// A112233..nnB
46+
// AA112233..BB
47+
for(int j = 4 ; i - j >= 0; j += 2){
48+
x = (x + res[i-j]) % mod;
49+
x = (x + res[i-j]) % mod;
50+
}
51+
52+
res.push_back(x);
53+
}
54+
55+
return res[N];
56+
}
57+
};
58+
59+
int main() {
60+
61+
cout << Solution().numTilings(3) << endl; // 5
62+
cout << Solution().numTilings(4) << endl; // 11
63+
cout << Solution().numTilings(7) << endl; // 117
64+
cout << Solution().numTilings(1000) << endl; // 979232805
65+
66+
return 0;
67+
}

‎0790-Domino-and-Tromino-Tiling/cpp-0790/main2.cpp‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
/// Source : https://leetcode.com/problems/domino-and-tromino-tiling/description/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-03-07
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
/// Dynamic Programming
11+
///
12+
/// dp[i][0]: how many ways to fill a 2*(i-1) tiles plus:
13+
/// .....0
14+
/// .....0
15+
///
16+
/// dp[i][1]: how many ways to fill a 2*(i-1) tiles plus:
17+
/// .....1
18+
/// .....0
19+
///
20+
/// dp[i][2]: how many ways to fill a 2*(i-1) tiles plus:
21+
/// .....0
22+
/// .....1
23+
///
24+
/// dp[i][3]: how many ways to fill a 2*(i-1) tiles plus:
25+
/// .....1
26+
/// .....1
27+
///
28+
/// The answer is dp[N][3]
29+
///
30+
/// Time Complexity: O(N)
31+
/// Space Complexity: O(N)
32+
class Solution {
33+
34+
public:
35+
int numTilings(int N) {
36+
37+
vector<vector<int>> res(N+1, vector<int>(4, 0));
38+
39+
res[0][0] = 0;
40+
res[0][1] = 0;
41+
res[0][2] = 0;
42+
res[0][3] = 1;
43+
44+
int mod = 1000000007;
45+
for(int i = 1 ; i <= N ; i ++){
46+
47+
res[i][0] = res[i-1][3];
48+
res[i][1] = (res[i-1][0] + res[i-1][2]) % mod;
49+
res[i][2] = (res[i-1][0] + res[i-1][1]) % mod;
50+
res[i][3] = 0;
51+
for(int j = 0 ; j < 4 ; j ++)
52+
res[i][3] = (res[i][3] + res[i-1][j]) % mod;
53+
54+
// cout << res[i][0] << " " << res[i][1] << " " << res[i][2] << " " << res[i][3] << endl;
55+
}
56+
57+
return res[N][3];
58+
}
59+
};
60+
61+
int main() {
62+
63+
cout << Solution().numTilings(3) << endl; // 5
64+
cout << Solution().numTilings(4) << endl; // 11
65+
cout << Solution().numTilings(7) << endl; // 117
66+
cout << Solution().numTilings(1000) << endl; // 979232805
67+
68+
return 0;
69+
}

‎0790-Domino-and-Tromino-Tiling/cpp-0790/main3.cpp‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
/// Source : https://leetcode.com/problems/domino-and-tromino-tiling/description/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-03-07
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
/// Dynamic Programming
11+
/// Optimiaze last solution about space complexity
12+
/// Time Complexity: O(N)
13+
/// Space Complexity: O(1)
14+
class Solution {
15+
16+
public:
17+
int numTilings(int N) {
18+
19+
int res[4];
20+
21+
res[0] = 0;
22+
res[1] = 0;
23+
res[2] = 0;
24+
res[3] = 1;
25+
26+
int mod = 1000000007;
27+
for(int i = 1 ; i <= N ; i ++){
28+
29+
int last_zero = res[0];
30+
int last_one = res[1];
31+
int last_two = res[2];
32+
33+
res[0] = res[3];
34+
35+
res[3] = last_zero;
36+
for(int j = 0 ; j < 3 ; j ++)
37+
res[3] = (res[3] + res[j]) % mod;
38+
39+
res[1] = (last_zero + last_two) % mod;
40+
res[2] = (last_zero + last_one) % mod;
41+
}
42+
43+
return res[3];
44+
}
45+
};
46+
47+
int main() {
48+
49+
cout << Solution().numTilings(3) << endl; // 5
50+
cout << Solution().numTilings(4) << endl; // 11
51+
cout << Solution().numTilings(7) << endl; // 117
52+
cout << Solution().numTilings(1000) << endl; // 979232805
53+
54+
return 0;
55+
}

‎readme.md‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -257,7 +257,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
257257
| | | | | | |
258258
| 788 | [Rotated Digits](https://leetcode.com/problems/rotated-digits/description/) | [solution](https://leetcode.com/problems/rotated-digits/solution/) | [C++](0788-Rotated-Digits/cpp-0788/) | | |
259259
| 789 | [Escape The Ghosts](https://leetcode.com/problems/escape-the-ghosts/description/) | [solution](https://leetcode.com/problems/escape-the-ghosts/solution/) | [C++](0789-Escape-The-Ghosts/cpp-0789/) | | |
260-
| | | | | | |
260+
| 790 | [Domino and Tromino Tiling](https://leetcode.com/problems/domino-and-tromino-tiling/description/) | [solution](https://leetcode.com/problems/domino-and-tromino-tiling/solution/)<br/>[缺：转移矩阵求幂解法] | [C++](0790-Domino-and-Tromino-Tiling/cpp-0790/) | | |
261261
| 791 | [Custom Sort String](https://leetcode.com/problems/custom-sort-string/description/) | [solution](https://leetcode.com/problems/custom-sort-string/solution/) | [C++](0791-Custom-Sort-String/cpp-0791/) | | |
262262
| 792 | [Number of Matching Subsequences](https://leetcode.com/problems/number-of-matching-subsequences/description/) | [solution](https://leetcode.com/problems/number-of-matching-subsequences/solution/) | [C++](0792-Number-of-Matching-Subsequences/cpp-0792/) | | |
263263
| 793 | [Preimage Size of Factorial Zeroes Function](https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/description/) | [solution](https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/solution/) | [C++](0793-Preimage-Size-of-Factorial-Zeroes-Function/cpp-0793/) | | |
@@ -267,7 +267,6 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
267267
---
268268

269269
短期计划：<br/>
270-
contest 73: 789, 790, 791; <br/>
271270
contest 72: 784, 785, 786, 787; <br/>
272271
contest 71: 782; <br/>
273272
contest 70: 779, 776, 777, 778; <br/>

0 commit comments

Comments
 (0)