How to Check If a Integer is a Strobogrammatic Number?
- 时间:2020-10-11 15:48:46
- 分类:网络文摘
- 阅读:78 次
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string.
Example 1:
Input: “69”
Output: trueExample 2:
Input: “88”
Output: trueExample 3:
Input: “962”
Output: false
The digits of 1, 6, 9, 8, 0 when rotated 180 degrees are valid while the rest are invalid. Therefore, if we meet invalid digits, we can simply return false. Otherwise, we can construct the rotated version and then compare to the origin – a strobogrammatic number if its rotated version is the same.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Solution { public: bool isStrobogrammatic(string num) { string x = ""; for (int i = 0; i < num.size(); ++ i) { switch (num[i] - 48) { case 2: case 3: case 4: case 5: case 7: return false; case 1: x = "1" + x; break; case 6: x = "9" + x; break; case 9: x = "6" + x; break; case 8: x = "8" + x; break; case 0: x = "0" + x; break; } } return x == num; } }; |
class Solution { public: bool isStrobogrammatic(string num) { string x = ""; for (int i = 0; i < num.size(); ++ i) { switch (num[i] - 48) { case 2: case 3: case 4: case 5: case 7: return false; case 1: x = "1" + x; break; case 6: x = "9" + x; break; case 9: x = "6" + x; break; case 8: x = "8" + x; break; case 0: x = "0" + x; break; } } return x == num; } };
The string concatenation may take O(N) complexity in the worst case, thus the above complexity is actually O(N^2). If we think about it, we don’t need to construct the rotated version, we just need to check if the current digit when rotated equals to another digit at the other side, thus we have the following improved version, which just runs at O(N) and O(1) space complexity.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Solution { public: bool isStrobogrammatic(string num) { int len = num.size(); for (int i = 0; i < len; ++ i) { switch (num[i] - 48) { case 2: case 3: case 4: case 5: case 7: return false; case 6: if ('9' != num[len - 1 - i]) return false; break; case 9: if ('6' != num[len - 1 - i]) return false; break; case 1: case 8: case 0: if (num[i] != num[len - 1 - i]) return false; break; } } return true; } }; |
class Solution { public: bool isStrobogrammatic(string num) { int len = num.size(); for (int i = 0; i < len; ++ i) { switch (num[i] - 48) { case 2: case 3: case 4: case 5: case 7: return false; case 6: if ('9' != num[len - 1 - i]) return false; break; case 9: if ('6' != num[len - 1 - i]) return false; break; case 1: case 8: case 0: if (num[i] != num[len - 1 - i]) return false; break; } } return true; } };
To generate the Strobogrammatic numbers of Size N, we can still use the Recursive Depth First Search Algorithm: Depth First Search Algorithm to Find the Strobogrammatic Number of Given Length
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:Algorithm to Count the Minimum Add to Make Parentheses Valid WXT pre-sale is now live – is it worth it? How to Serialize and Deserialize Binary Tree? How to Construct Binary Tree from String (Binary Tree Deserializ Activist’s Mother Faces Prison After One-Word Facebook Reply Ed-Tech Start-Ups Can Allow Anyone To Become A Teacher Russian Hacker Sold Millions Of Passwords For Less Than A $1, Sh How To Successfully Fine-tune Your Overall Social Media Strategy What It Really Takes To Make Money As a Blogger How Do You Increase Website Domain Authority?
- 评论列表
-
- 添加评论