【回文数】算法优化笔记

╰半橙微兮° 2023-06-30 06:52 26阅读 0赞

## 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数（不将整数转为字符串来解决）。 ##

示例 1:
    
    	输入: 121
    	输出: true
    	示例 2:
    
    	输入: -121
    	输出: false
    	解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
    	示例 3:
    
    	输入: 10
    	输出: false
    	解释: 从右向左读, 为 01 。因此它不是一个回文数。

###### 你能不将整数转为字符串来解决这个问题吗？ ######

> *来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-number*

##### 初步分析 #####

1.  可以暴力法，强行转化成字符串反转判断是否相同。
2.  （上次的整数反转算法）可以利用取余来每位反向添加入另一个整数中。
3.  （也是上次的整数反转算法）不过这次可以反转一半和另一半比较相同则为回文数。

# 本章总结 #

【小总结】  
1.【尽量不要用暴力法】  
2.【利用数学运算eg：%，/】

【详细总结】

<table> 
 <thead> 
  <tr> 
   <th>原x</th> 
   <th>a</th> 
   <th>变化后x</th> 
   <th>result</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1234</td> 
   <td>4</td> 
   <td>123</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>123</td> 
   <td>3</td> 
   <td>12</td> 
   <td>43</td> 
  </tr> 
  <tr> 
   <td>12</td> 
   <td>2</td> 
   <td>1</td> 
   <td>432</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>4321</td> 
  </tr> 
 </tbody> 
</table>

# 详细代码 #

public class Solution { 
        public bool IsPalindrome(int x) { 
            if(x<0) return false;
            if(x<10) return true;
            if(x%10==0) return false;
            int before = x;
            int result =0;
            while(x!=0)
            { 
                int a=x%10;
                x=x/10;
                result = result*10+a;
            }
            return result==before;
        }
    }

另一个理解比较简单的版本(反转一半判断)

public class Solution { 
        public bool IsPalindrome(int x) { 
            if(x < 0 || (x % 10 == 0 && x != 0)) { 
                return false;
            }
            int result = 0;
            while(x > result ) { 
                result = result * 10 + x % 10;
                x /= 10;
            }
            return x == result || x == result /10;
        }
    }
    
    		位运算符：
    
    		(a & b)
    		按位与运算符：参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0
    		输出结果 12 ，二进制解释： 0000 1100
    
    		(a | b)
    		按位或运算符：只要对应的二个二进位有一个为1时，结果位就为1。
    		输出结果 61 ，二进制解释： 0011 1101
    
    		(a ^ b)
    		按位异或运算符：当两对应的二进位相异时，结果为1
    		输出结果 49 ，二进制解释： 0011 0001
    
    		(~a )
    		按位取反运算符：对数据的每个二进制位取反,即把1变为0,把0变为1 。~x 类似于 -x-1
    		输出结果 -61 ，二进制解释： 1100 0011，在一个有符号二进制数的补码形式。
    
    		a << 2
    		左移动运算符：运算数的各二进位全部左移若干位，由 << 右边的数字指定了移动的位数，高位丢弃，低位补0。
    		输出结果 240 ，二进制解释： 1111 0000
    
    		a >> 2
    		右移动运算符：把">>"左边的运算数的各二进位全部右移若干位，>> 右边的数字指定了移动的位数
    		输出结果 15 ，二进制解释： 0000 1111
    
    		赋值运算符：
    
    		*= 乘法赋值运算符 c *= a 等效于 c = c * a
    		/= 除法赋值运算符 c /= a 等效于 c = c / a
    		%= 取模赋值运算符 c %= a 等效于 c = c % a
    		**= 幂赋值运算符 c **= a 等效于 c = c ** a
    		//= 取整除赋值运算符 c //= a 等效于 c = c // a
    
    > 作者：boywithacoin_cn
    > 链接：https://leetcode-cn.com/problems/reverse-integer/solution/pythondan-chu-he-tui-ru-shu-zi-yi-chu-qian-jin-xin/
    > 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。