Re: [閒聊] 每日leetcode
白癡leetocde出這三小題目
564. Find the Closest Palindrome
給你一個字串化的整數s
請回傳與s差距最小的回文(不包含s)
如果有兩個差距一樣的，請回傳比較小的那個
思路：
題目要回文所以將s分成左右兩邊
且要差距最小，變動左半邊的影響會比右半邊大
所以以左半邊當作基礎去創造回文
這是最容易想到的一個可能
還有4種可能
(1)
將s的長度減1並且全部填9
ex s=100，最接近會是99
(2)
將s的長度加1並且頭尾填1
ex s=99，最接近會是101
(3)
如果s是奇數將s中間的數+1
如果s是偶數將s中間的兩個數+1
ex s=88088，最接近會是88188
(4)
如果s是奇數將s中間的數-1
如果s是偶數將s中間的兩個數-1
ex s=8888，最接近會是8778
把五種可能都算出來
就可以得到答案了
golang code :
func nearestPalindromic(s string) string {
n := len(s)
if n == 1 {
return string(s[0] - 1)
}
lefthalf, _ := strconv.Atoi(s[:(n+1)/2])
num, _ := strconv.Atoi(s)
candidates := make([]int, 5)
candidates[0] = createPalindromic(lefthalf+1, n%2 == 0)
candidates[1] = createPalindromic(lefthalf, n%2 == 0)
candidates[2] = createPalindromic(lefthalf-1, n%2 == 0)
candidates[3] = int(math.Pow10(n)) + 1
candidates[4] = int(math.Pow10(n-1)) - 1
result := 0
for _, val := range candidates {
if val != num {
if abs(result-num) > abs(val-num) {
result = val
} else if abs(result-num) == abs(val-num) && result > val {
result = val
}
}
}
return strconv.Itoa(result)
}
func createPalindromic(lefthalf int, iseven bool) int {
palindromic := lefthalf
if !iseven {
palindromic /= 10
}
for lefthalf > 0 {
palindromic = palindromic*10 + lefthalf%10
lefthalf /= 10
}
return palindromic
}
func abs(i int) int {
if i < 0 {
return -i
}
return i
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.187.65 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724482122.A.1FB.html
推
08/24 15:03,
1年前
, 1F
08/24 15:03, 1F
討論串 (同標題文章)
完整討論串 (本文為第 762 之 1548 篇)：