Rotated Digits Solutions in C++
Number 788
Difficulty Easy
Acceptance 57.1%
Link LeetCode
Other languages —
Solutions
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/rotated-digits/description//// Author : liuyubobobo/// Time : 2018-02-24#include <iostream>#include <vector>#include <cassert>using namespace std;/// Brute Force/// Time Complexity: O(NlogN)/// Space Complexity: O(logN)class Solution {public:int rotatedDigits(int N) {int res = 0;for(int i = 1 ; i <= N ; i ++){vector<int> digits = get_digits(i);bool ok = true;for(int d: digits)if(d == 3 || d == 4 || d ==7){ok = false;break;}if(ok){rotate(digits);int num = get_num(digits);if(num != i)res ++;}}return res;}private:int get_num(const vector<int>& digits){int x = 0;for(int d: digits)x = x * 10 + d;return x;}void rotate(vector<int>& digits){for(int i = 0 ; i < digits.size() ; i ++)if(digits[i] == 2)digits[i] = 5;else if(digits[i] == 5)digits[i] = 2;else if(digits[i] == 6)digits[i] = 9;else if(digits[i] == 9)digits[i] = 6;elseassert(digits[i] == 0 || digits[i] == 1 || digits[i] == 8);}vector<int> get_digits(int x){vector<int> res;while(x){res.push_back(x%10);x /= 10;}reverse(res.begin(), res.end());return res;}};int main() {cout << Solution().rotatedDigits(10) << endl;return 0;}
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/rotated-digits/description//// Author : liuyubobobo/// Time : 2018-03-05#include <iostream>#include <vector>#include <cassert>using namespace std;/// Brute Force/// Using String////// Time Complexity: O(NlogN)/// Space Complexity: O(logN)class Solution {public:int rotatedDigits(int N) {int res = 0;for(int i = 1 ; i <= N ; i ++){string digits = to_string(i);string rdigits = digits;if(ok(digits, rdigits))res ++;}return res;}private:bool ok(const string& digits, string& rdigits){for(int i = 0 ; i < rdigits.size() ; i ++)if(rdigits[i] == '3' || rdigits[i] == '4' || rdigits[i] == '7')return false;else if(rdigits[i] == '2')rdigits[i] = '5';else if(rdigits[i] == '5')rdigits[i] = '2';else if(rdigits[i] == '6')rdigits[i] = '9';else if(rdigits[i] == '9')rdigits[i] = '6';return digits != rdigits;}};int main() {cout << Solution().rotatedDigits(10) << endl;return 0;}
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/rotated-digits/description//// Author : liuyubobobo/// Time : 2018-03-05#include <iostream>#include <vector>#include <cassert>using namespace std;/// Brute Force/// We need to write using only digits from 0125689,/// and write at least one digit from 2569.////// Time Complexity: O(NlogN)/// Space Complexity: O(logN)class Solution {public:int rotatedDigits(int N) {int res = 0;for(int i = 1 ; i <= N ; i ++)if(ok(i, false))res ++;return res;}private:bool ok(int num, bool flag){if(num == 0)return flag;int d = num % 10;if(d == 3 || d == 4 || d == 7)return false;if(d == 0 || d == 1 || d == 8)return ok(num / 10, flag);return ok(num / 10, true);}};int main() {cout << Solution().rotatedDigits(10) << endl;return 0;}
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/rotated-digits/description//// Author : liuyubobobo/// Time : 2018-03-05#include <iostream>#include <vector>#include <cassert>using namespace std;/// Memory Search////// We need to write using only digits from 0125689,/// and write at least one digit from 2569.////// dp[i][eq][contain2569] means we search first i digits,/// and the i-th digit is equal (or not) to the i-th digit in N/// and the search has (or not) already meet a digit of 2569////// Time Complexity: O(logN)/// Space Complexity: O(logN)class Solution {private:vector<vector<vector<int>>> memo;public:int rotatedDigits(int N) {string N_str = to_string(N);memo = vector<vector<vector<int>>>(N_str.size(), vector<vector<int>>(2, vector<int>(2, -1)));return search(0, true, false, N_str);}private:int search(int index,bool eq, bool contain2569, const string& s){if(index == s.size())return contain2569 ? 1 : 0;if(memo[index][eq][contain2569] != -1)return memo[index][eq][contain2569];int res = 0;char bound = eq ? s[index] : '9';for(char c = '0' ; c <= bound ; c ++){if(c == '3' || c == '4' || c == '7')continue;bool is2569 = (c == '2' || c == '5' || c == '6' || c =='9');if(!eq)res += search(index + 1, eq, contain2569 || is2569, s);else if(c < bound)res += search(index + 1, false, contain2569 || is2569, s);elseres += search(index + 1, true, contain2569 || is2569, s);}return memo[index][eq][contain2569] = res;}};int main() {cout << Solution().rotatedDigits(10) << endl; // 4cout << Solution().rotatedDigits(857) << endl; // 247return 0;}
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/rotated-digits/description//// Author : liuyubobobo/// Time : 2018-03-05#include <iostream>#include <vector>#include <cassert>using namespace std;/// Dynamic Programming////// We need to write using only digits from 0125689,/// and write at least one digit from 2569.////// dp[i][eq][contain2569] means we search first i digits,/// and the i-th digit is equal (or not) to the i-th digit in N/// and the search has (or not) already meet a digit of 2569////// Time Complexity: O(logN)/// Space Complexity: O(logN)class Solution {public:int rotatedDigits(int N) {string N_str = to_string(N);vector<vector<vector<int>>> memo(N_str.size() + 1, vector<vector<int>>(2, vector<int>(2, 0)));memo[N_str.size()][false][true] = 1;memo[N_str.size()][true][true] = 1;for(int index = N_str.size() - 1 ; index >= 0 ; index --)for(int eq = 0 ; eq <= 1 ; eq ++)for(int contain2569 = 0 ; contain2569 <= 1 ; contain2569 ++){int res = 0;char bound = eq ? N_str[index] : '9';for(char c = '0' ; c <= bound ; c ++){if(c == '3' || c == '4' || c == '7')continue;bool is2569 = (c == '2' || c == '5' || c == '6' || c =='9');if(!eq)res += memo[index+1][eq][contain2569 || is2569];else if(c < bound)res += memo[index+1][false][contain2569 || is2569];elseres += memo[index+1][true][contain2569 || is2569];}memo[index][eq][contain2569] = res;}return memo[0][true][false];}};int main() {cout << Solution().rotatedDigits(10) << endl; // 4cout << Solution().rotatedDigits(857) << endl; // 247return 0;}