題目:
Determine whether an integer is a palindrome. Do this without extra space.
官方難度:
Easy
翻譯:
判斷一個整數是否為回文結構,不使用額外空間。
思路:
1.回文結構的整數,與之前回文字符串類似,形如1,121,34543,345543的結構。
2.不使用額外空間,表名要從數字而不是字符串的角度來考慮問題。
3.負數不在討論范圍。
4.確定最高位,遍歷至maxLevel/2處,檢查對稱位置即可。
解題中可能遇到的困難:
1.獲得指定位置的數字的算法:(number / Math.pow(10, index - 1)) % 10)。
2.理論上0的最高位也是1,但是計算的最高位是0,不影響結果,但考慮的時候要留意一下。、
解題代碼:
1 private static boolean method(int number) { 2 // 負數不在討論范圍 3 if (number < 0) { 4 return false; 5 } 6 // 確定最高位(0的最高位數是0,等下特殊處理) 7 int maxLevel = 0; 8 int copyNumber = number; 9 while (copyNumber > 0) { 10 copyNumber /= 10; 11 maxLevel++; 12 } 13 // 低高位 14 int low; 15 int high; 16 // 無論最高位是奇偶,遍歷至maxLevel/2就行了 17 // maxLevel=0在這裡直接跳過了 18 for (int i = 1; i < maxLevel / 2 + 1; i++) { 19 // 低位+高位的和是maxLevel+1 20 low = getIndexNumber(i, number); 21 high = getIndexNumber(maxLevel + 1 - i, number); 22 if (!(low == high)) { 23 return false; 24 } 25 } 26 return true; 27 } 28 29 // 獲取一個數字具體某一位的數字 30 // index是自低位起的數字 31 private static int getIndexNumber(int index, int number) { 32 return (int) ((number / Math.pow(10, index - 1)) % 10); 33 } View Code測試代碼地址:
https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/easy/Q009.java
LeetCode題目地址:
https://leetcode.com/problems/palindrome-number/
PS:如有不正確或提高效率的方法,歡迎留言,謝謝!