🖋
LeetCode 9. Palindrome Number
はじめに
LeetCode 「9. Palindrome Number」の問題をGoで解きました。
問題
問題文
Given an integer x, return true if x is a palindrome, and false otherwise.
和訳
整数 x が与えられた場合、x が回文であれば true を返し、そうでない場合は false を返します。
例
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.
Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
制約
- -231 <= x <= 231 - 1
解答1（文字列に変換）
まず、数値を文字列に変換する方法で解きます。
先頭と末尾の文字を比較しながら中央に向かい、その途中で文字が一致しなければfalseを返します。
コード
func isPalindrome(x int) bool {
if x < 0 {
return false
}
if x < 10 {
return true
}
x_str := strconv.Itoa(x)
left := 0
right := len(x_str) - 1
for left < right {
if x_str[left] != x_str[right] {
return false
}
left++
right--
}
return true
}
計算量
- 時間的計算量：O(log N)
- 空間的計算量：O(log N)
解答2（文字列を使わない）
文字列を使わず、数値のまま反転させることでより効率的に解くアプローチもあります。
文字数変換を避けることで、追加のメモリを減らせます。
数字を全部反転するとオーバーフローの危険がありますが、
回文は前半と後半が対称なので、後半だけを反転させて前半と比較していきます。
コード
func isPalindrome(x int) bool {
if x < 0 {
return false
}
if x%10 == 0 && x != 0 {
return false
}
revertedNumber := 0
for x > revertedNumber {
revertedNumber = revertedNumber*10 + x%10
x /= 10
}
return x == revertedNumber || x == revertedNumber/10
}
以下のコードで、末尾が0かつ0ではない数を弾いています(例:10)
if x%10 == 0 && x != 0 {
return false
}
以下のコードで、数字の後半を1桁ずつ反転させています。
revertedNumber := 0
for x > revertedNumber {
revertedNumber = revertedNumber*10 + x%10
x /= 10
}
x = 1221 を例とすると以下のような流れとなります。
1回目:
- revertedNumber = 0 * 10 + 1221 % 1 = 1
- x = 1221 / 10 = 122
2回目:
- revertedNumber = 1 * 10 + 122 % 1 = 12
- x = 122 / 10 = 12
ここでループ終了
最後に、xとrevertedNumberを比較します。
- 偶数桁の場合：x == revertedNumber
- 奇数桁の場合：x == revertedNumber/10
奇数桁 例:12321 の場合、ループ終了後に x = 12 revertedNumber = 123 となります。
真ん中の3は比較不要なので、/10 をしています。
計算量
- 時間的計算量：O(log N)
- 空間的計算量：O(1)
Discussion