題目連結: Reverse Integer

題目描述為給定一個 32 位元帶有正負符號的整數，要求返回他的反轉數。
題目有補充說明可接受的數值範圍為 : [−2³¹, 2³¹ − 1]，反轉後的數不在此範圍內則返回0。

思路1： 轉換成字串處理

我們可以先把該整數轉成字串後反轉再轉回數字，然後檢查是否符合範圍。

• 複雜度評估
  如果輸入的數字 x 為 n 位數，則需要轉換 n 次，因為此題 x 有界，所以 n 也有界，最多也只需要進行常數次轉換，時間複雜度為 O(1) 。此方法有另外宣告 []byte 來存放轉換後的數字，同理空間複雜度為 O(1)。

參考程式碼

func reverse(x int) ( int) {   
    
    sign:=1
    if x<0{
        sign=-1
        x=-x
    }
    
    s:=strconv.Itoa(x)
    bs:=[]byte(s)
    
    head:=0
    tail:=len(bs)-1
    
    for head<tail{
        bs[head],bs[tail]=bs[tail],bs[head]
        head++
        tail--
    }
   
    rs:=string(bs)
    
    if sign==-1{
        rs="-"+rs
    }
    
    y, err := strconv.Atoi(rs)
    if err!=nil{
        fmt.Println(err,rs)  
    }
      
    if( (y > math.MaxInt32) || (y < math.MinInt32)) {
		return 0
	}
               
    return y       
}

思路2：直接處理數字

我們也可以直接處理數字 x 得到他的反轉數。處理方式為初始化一個新的數 y，對 x 取最後一位得到的餘數 r 直接放到 y 數字的後面，重複此流程直到取完 x 的所有位數。

參考程式碼

func reverse(x int) ( int) {
   
    y:=0
    r:= 0
    sign:=1
      
    if x<0{
        sign=-1
        x=-x
    }
    
    for x>0{        
        r=x%10
        y=y*10+r 
        x=x/10
    }
         
    y*=sign
    
    if( (y > math.MaxInt32) || (y < math.MinInt32)) {
		return 0
	}
               
    return y       
}

• 複雜度評估：
  如果輸入的數字 x 為 n 位數，則要重複此步驟 n 次。n 有界，所以時間複雜度為 O(1)。此方法只用了常數個變數，空間複雜度為 O(1)。

小結

在此題中對負數取餘數也可以直接得到我們要的結果 (ex: -31%10 會得到 -1 )，但筆者還是習慣先全部轉為正數再做處理。而 Go 語言中 int 型別的大小，官方文件是這麼寫的:
The int, uint, and uintptr types are usually 32 bits wide on 32-bit systems and 64 bits wide on 64-bit systems. When you need an integer value you should use int unless you have a specific reason to use a sized or unsigned integer type.

解法 2 中宣告的 y 是 int 型別，如果在32位元系統此方法不適用，需要進行修改。此做法筆者是在網路上看到的分享解法:
我們需要多檢查每次迭代完後的數值是否溢位，檢查方式為對其數字逆運算後與前一次迭代結果相比，如果不一致則表示溢位了。修改後參考程式碼如下：

func reverse(x int) ( int) {
   
    prey:=0
    y:=0
    r:= 0
    sign:=1
    
    if x<0{
        sign=-1
        x=-x
    }
    
    for x>0{        
        r=x%10
        y=y*10+r 

        if ((y-r)/10 )!= prey{
            return 0
        }
        
        prey=y
        x=x/10
    }
       
    y*=sign
    
	if( (y > math.MaxInt32) || (y < math.MinInt32)) {
		return 0
	}
               
    return y       
}

附上簡單的測試，程式碼 在此。