【整数反转】算法优化笔记

矫情吗；* 2023-06-29 05:58 25阅读 0赞

## 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。 ##

示例 1:
    
    		输入: 123
    		输出: 321
    		
    		 示例 2:
    
    		输入: -123
    		输出: -321
    		
    		示例 3:
    
    		输入: 120
    		输出: 21

###### 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 \[−231, 231 − 1\]。请根据这个假设，如果反转后整数溢出那么就返回 0。 ######

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

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

1.  可以暴力法，强行转化成字符串反转。
2.  可以利用取余来每位反向添加入另一个整数中。O(log(x))

# 本章总结 #

【小总结】  
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 int Reverse(int x) { 
            if(x==0)return 0;
            int tag = x>0?1:-1;
            x=x*tag;
            int result=0;
            while(x>0)
            { 
    
                int a = x%10;
                x=x/10;
                if(result>int.MaxValue/10||(result==int.MaxValue/10)&&a>7)
                return 0;
                result = result*10 + a;
    
            }
                return result * tag;
        }
    }

另一个理解比较简单的版本

public class Solution { 
        public int Reverse(int x) { 
                long result = 0;
    
                while (x != 0)
                { 
                    int temp = x % 10;
                    x = x / 10;
                    result = result * 10 + temp;
                                
                }
                //判断是否存在溢出，极易忽略这点
                if (result > int.MaxValue || result < int.MinValue)
                { 
                    result = 0;
                }
    
                return (int)result;
        }
    }

位运算符：
    
    	(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） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

以下是个人的最初解题的垃圾代码，引以为戒。

public class Solution { 
        private const long INT_MAX = 2147483647;
        private const long NINT_MAX = -2147483648;
        public int Reverse(int x) { 
                string before = null;
                if (x < 0)
                before = x.ToString().Remove(0, 1);
                if (x >= 0)
                before = x.ToString();
                char[] after = new char[before.Length];
                for (int i = 0; i < before.Length; i++)
                { 
                    after[i] = before[before.Length - i - 1];
                }
                before = new string(after);
    
                if (x < 0)
                { 
                    if(long.Parse("-" +before)>NINT_MAX)
                    return (int.Parse("-" +before));
                    else
                    return 0;
                }
                else if (x > 0&&x<INT_MAX)
                { 
                    if(long.Parse(before)<INT_MAX)
                    return (int.Parse(before));
                    else
                    return 0;
                }
                else
                { 
                    return (0);
                }
    
    
    
            
        }
    }