LeetCode 9 - Palindrome Number


http://articles.leetcode.com/2012/01/palindrome-number.html
Determine whether an integer is a palindrome. Do this without extra space. Assume that a negative integer is not a palindrome.

Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
https://leetcode.com/discuss/23563/line-accepted-java-code-without-the-need-handling-overflow
public boolean isPalindrome(int x) { if (x<0 || (x!=0 && x%10==0)) return false; int rev = 0; while (x>rev){ rev = rev*10 + x%10; x = x/10; } return (x==rev || x==rev/10); }
Overflow does not guarantee to be negative. Think about 2147483647 *3 is also positive.
http://www.programcreek.com/2013/02/leetcode-palindrome-number-java/
可以首先排除能被10整除的数,这样的数是不可能为回文数的。
public boolean isPalindrome(int x) {
        if (x < 0)      // Negative numbers are assumed to be non-palindromic
            return false;
        // The smallest integer that has the same number of digits with x
        // Used to get the leftmost digit
        int oneZeros = 1; // change variable name to div: readability
        while (x / oneZeros >= 10)
            oneZeros *= 10;
        // Compare the digits at both ends
        while (x != 0) {
            int leftmost = x / oneZeros;
            int rightmost = x % 10;
            if (leftmost != rightmost)
                return false;
            x = (x % oneZeros) / 10;     // Chop the leftmost and rightmost digits
            oneZeros /= 100;             // Update oneZeros as two digits are chopped
        }
        return true;
    }
http://www.programcreek.com/2013/02/leetcode-palindrome-number-java/
Problems related with numbers are frequently solved by / and %. No need of extra space is required. This problem is similar with the Reverse Integer problem.
直接按照PalidromeString的方法,就直接判断第一个和最后一个,循环往复。这样就不会对数字进行修改,而只是判断而已。
    public boolean isPalindrome(int x) {
        //negative numbers are not palindrome
  if (x < 0)
   return false;
 
  // initialize how many zeros
  int div = 1;
  while (x / div >= 10) {
   div *= 10;
  }
 
  while (x != 0) {
   int left = x / div;
   int right = x % 10;
 
   if (left != right)
    return false;
 
   x = (x % div) / 10;
   div /= 100;
  }
 
  return true;
    }

http://codercareer.blogspot.com/2011/11/no-23-palindrome-numbers.html
Solution 1: Convert a Number into a String
This should be preferred in real application: as its performance would be much better. JDK's Interget.toString is highly optimized.
Solution 2: Compose a Reversed Number
A simple method for this problem is to first reverse digits of num, then compare the reverse of num with num. If both are same, then return true, else false.
==> it may overflow
// without consider about overflow
Use bigger data type
bool IsPalindrome_solution2(unsigned int number)
{
    int reversed = 0;
    int copy = number;

    while(number != 0)
    {
        reversed = reversed * 10 + number % 10;
        number /= 10;
    }

    return (reversed == copy);


}
考虑越界溢出问题。遇见这种处理Number和Integer的问题,首要考虑的就是会不会溢出越界。然后再考虑下负数,0。还有就是要心里熟悉\的结果和%的结果。
Recursive Solution:
http://yucoding.blogspot.com/2013/04/leetcode-question-62-palindrome-number.html
    bool check(int x, int &y){
        if (x==0) {return true;}
        if (check(x/10,y)){
            if (x%10==y%10){
                y=y/10;
                return true;
            }
        }
        return false;
    }
    bool isPalindrome(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (x<0){return false;}
        return check(x,x);
    }

http://www.geeksforgeeks.org/check-if-a-number-is-palindrome/
int isPal(int num)
{
    // If num is negative, make it positive
    if (num < 0)
       num = -num;

    // Create a separate copy of num, so that modifications made
    // to address dupNum don't change the input number.
    int *dupNum = new int(num); // *dupNum = num
    return isPalUtil(num, dupNum);
}
// A recursive function to find out whether num is palindrome
// or not. Initially, dupNum contains address of a copy of num.
bool isPalUtil(int num, int* dupNum)
{
    // Base case (needed for recursion termination): This statement
    // mainly compares the first digit with the last digit
    if (oneDigit(num))
        return (num == (*dupNum) % 10);
    // This is the key line in this method. Note that all recursive
    // calls have a separate copy of num, but they all share same copy
    // of *dupNum. We divide num while moving up the recursion tree
    if (!isPalUtil(num/10, dupNum))
        return false;
    // The following statements are executed when we move up the
    // recursion call tree
    *dupNum /= 10;
    // At this point, if num%10 contains i'th digit from beiginning,
    // then (*dupNum)%10 contains i'th digit from end
    return (num % 10 == (*dupNum) % 10);
}
http://bylijinnan.iteye.com/blog/1346521
  1.     //generic solution, may overflow
  2.     public boolean isPalindromeInt(int x){  
  3.         if(x<0)return false;  
  4.         int x2=x;  
  5.         int y=0;  
  6.         while(x>0){  
  7.             y*=10;  
  8.             y+=x%10;  
  9.             x/=10;  
  10.         }  
  11.         return x2==y;  
  12.     } 
https://leetcode.com/discuss/21138/sharing-simple-straightforward-solution-with-explanation
bool isPalindrome(int x) {
    long reverse = 0;
    long num = abs(x);
    while(x != 0){
        reverse *= 10;
        reverse += x % 10;
        x /= 10;
    }
    return reverse == num;
}
The basic idea is to reverse x.
However, we need to handle two issues. First of all, what if reverse number overflows? We uselong to solve. Secondly, negative number doesn't have palindrome. So we make num = abs(x).
http://liangjiabin.com/blog/2015/03/leetcode-palindrome-number-in-python.html
Read full article from LeetCode - Palindrome Number | Darren's Blog

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts