Skip to content

Commit bacd0ed

Browse files
liuyuboboboliuyubobobo
committed
0600 solved.
1 parent 2ea935b commit bacd0ed

File tree

4 files changed

+174
-0
lines changed

4 files changed

+174
-0
lines changed

‎0600-Non-negative-Integers-without-Consecutive-Ones/cpp-0600/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(cpp_0600)
3+
4+
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
5+
6+
set(SOURCE_FILES main2.cpp)
7+
add_executable(cpp_0600 ${SOURCE_FILES})

‎0600-Non-negative-Integers-without-Consecutive-Ones/cpp-0600/main.cpp‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
/// Source : https://leetcode.com/problems/rotated-digits/description/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-03-05
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <cassert>
8+
9+
using namespace std;
10+
11+
/// Memory Search
12+
/// Same algorithm to Leetcode 788
13+
///
14+
/// dp[i][eq][last_one] means we search first i digits,
15+
/// and the i-th digit is equal (or not) to the i-th digit in N (binary form)
16+
/// and last digit of the search is last_one(true or false)
17+
///
18+
/// Time Complexity: O(logN)
19+
/// Space Complexity: O(logN)
20+
class Solution {
21+
22+
private:
23+
vector<vector<vector<int>>> memo;
24+
25+
public:
26+
int findIntegers(int num) {
27+
28+
if(num == 0)
29+
return 1;
30+
31+
string binary = to_binary(num);
32+
// cout << binary << endl;
33+
memo = vector<vector<vector<int>>>(binary.size(), vector<vector<int>>(2, vector<int>(2, -1)));
34+
assert(binary[0] == '1');
35+
return search(0, true, false, binary);
36+
}
37+
38+
private:
39+
int search(int index, bool eq, bool last_one, const string& binary){
40+
41+
if(index == binary.size())
42+
return 1;
43+
44+
if(memo[index][eq][last_one] != -1)
45+
return memo[index][eq][last_one];
46+
47+
int res = 0;
48+
char bound = (eq ? binary[index] : '1');
49+
for(char c = '0' ; c <= bound ; c ++){
50+
51+
if(last_one && c == '1')
52+
continue;
53+
54+
bool this_one = (c == '1');
55+
if(eq && c == bound)
56+
res += search(index + 1, true, this_one, binary);
57+
else
58+
res += search(index + 1, false, this_one, binary);
59+
}
60+
return memo[index][eq][last_one] = res;
61+
}
62+
63+
string to_binary(int num){
64+
string res = "";
65+
while(num){
66+
res += ('0' + num%2);
67+
num /= 2;
68+
}
69+
reverse(res.begin(), res.end());
70+
return res;
71+
}
72+
};
73+
74+
int main() {
75+
76+
cout << Solution().findIntegers(0) << endl;
77+
cout << Solution().findIntegers(1) << endl;
78+
cout << Solution().findIntegers(2) << endl;
79+
cout << Solution().findIntegers(3) << endl;
80+
cout << Solution().findIntegers(4) << endl;
81+
cout << Solution().findIntegers(5) << endl;
82+
83+
return 0;
84+
}

‎0600-Non-negative-Integers-without-Consecutive-Ones/cpp-0600/main2.cpp‎

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
/// Source : https://leetcode.com/problems/rotated-digits/description/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-03-05
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <cassert>
8+
9+
using namespace std;
10+
11+
/// Dynamic Programming
12+
/// Same algorithm to Leetcode 788
13+
///
14+
/// dp[i][eq][last_one] means we search first i digits,
15+
/// and the i-th digit is equal (or not) to the i-th digit in N (binary form)
16+
/// and last digit of the search is last_one(true or false)
17+
///
18+
/// Time Complexity: O(logN)
19+
/// Space Complexity: O(logN)
20+
class Solution {
21+
22+
public:
23+
int findIntegers(int num) {
24+
25+
if(num == 0)
26+
return 1;
27+
28+
string binary = to_binary(num);
29+
assert(binary[0] == '1');
30+
31+
vector<vector<vector<int>>> memo(binary.size() + 1, vector<vector<int>>(2, vector<int>(2, 0)));
32+
for(int eq = 0 ; eq <= 1 ; eq ++)
33+
for(int last_one = 0 ; last_one <= 1 ; last_one ++)
34+
memo[binary.size()][eq][last_one] = 1;
35+
36+
for(int index = binary.size() - 1 ; index >= 0 ; index --)
37+
for(int eq = 0 ; eq <= 1 ; eq ++)
38+
for(int last_one = 0 ; last_one <= 1 ; last_one ++){
39+
40+
int res = 0;
41+
char bound = (eq ? binary[index] : '1');
42+
for(char c = '0' ; c <= bound ; c ++){
43+
44+
if(last_one && c == '1')
45+
continue;
46+
47+
bool this_one = (c == '1');
48+
if(eq && c == bound)
49+
res += memo[index+1][true][this_one];
50+
else
51+
res += memo[index+1][false][this_one];
52+
}
53+
memo[index][eq][last_one] = res;
54+
}
55+
56+
return memo[0][true][false];
57+
}
58+
59+
private:
60+
string to_binary(int num){
61+
string res = "";
62+
while(num){
63+
res += ('0' + num%2);
64+
num /= 2;
65+
}
66+
reverse(res.begin(), res.end());
67+
return res;
68+
}
69+
};
70+
71+
int main() {
72+
73+
cout << Solution().findIntegers(0) << endl;
74+
cout << Solution().findIntegers(1) << endl;
75+
cout << Solution().findIntegers(2) << endl;
76+
cout << Solution().findIntegers(3) << endl;
77+
cout << Solution().findIntegers(4) << endl;
78+
cout << Solution().findIntegers(5) << endl;
79+
80+
return 0;
81+
}

‎readme.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -193,6 +193,8 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
193193
| | | | | | |
194194
| 598 | [Range Addition II](https://leetcode.com/problems/range-addition-ii/description/) | | [C++](0598-Range-Addition-II/cpp-0598/) | | |
195195
| | | | | | |
196+
| 600 | [Non-negative Integers without Consecutive Ones](https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/description/) | [solution](https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/solution/)<br/>[缺：Bit Manipulation]| [C++](0600-Non-negative-Integers-without-Consecutive-Ones/cpp-0600/) | | |
197+
| | | | | | |
196198
| 648 | [Replace Words](https://leetcode.com/problems/replace-words/description/) | [无] | [C++](0648-Replace-Words/cpp-0648/) | | |
197199
| | | | | | |
198200
| 672 | [Bulb Switcher II](https://leetcode.com/problems/bulb-switcher-ii/description/) | [solution](https://leetcode.com/problems/bulb-switcher-ii/solution/) | [C++](0672-Bulb-Switcher-II/cpp-0672/) | | |

0 commit comments

Comments
 (0)