[LeetCode]9. Palindrome Number

题目描述

思路1

遍历一次，栈保存前1/2， 后1/2比较

代码1

// version 1 bool isPalindrome(int x) { string num = std::to_string(x); stack<char> s; bool res = true; int len = num.size(), flag = floor(len / 2); for (int i = 0; i < len; ++i){ if (len % 2 && i == flag) continue; if (i < flag){ s.push(num[i]); } else{ if (s.top() != num[i]) { res = false; break; } s.pop(); } } return res; }

思路2

不需要栈，遍历1/2即可

代码2

// version 2 bool isPalindrome(int x) { string num = std::to_string(x); bool res = true; int len = num.size(), flag = floor(len / 2); for (int i = 0; i < flag; ++i){ if (num[i] != num[len - i - 1]){ res = false; break; } } return res; }

思路3

考虑空间复杂度要求O(1)

代码3

// version 3 bool isPalindrome(int x) { int len = (int)(log(x) / log(10) + 1), mid = (floor)(len / 2); int res = 0, source = x; for (int i = 0; i < mid; ++i){ res += (x % 10) * pow(10, i) + (x % 10) * pow(10, len - i - 1); x = x / 10; } if (len % 2){ res += (x % 10) * pow(10, mid); } return res == source; }

思路4

考虑空间复杂度基础上优化时间

代码

// version 4 bool isPalindrome(int x) { if (x < 0 || x && x % 10 == 0) return false; int sum = 0; while (sum < x){ sum = sum * 10 + x % 10; x /= 10; } return sum == x || x == sum / 10; }