LeetCode 564. 寻找最近的回文数

Categories:

题目描述
思路分析
1. 解法一：构造候选回文（推荐）
相似题目

题目描述

✅ 564. 寻找最近的回文数

思路分析

解法一：构造候选回文（推荐）

核心思路：

取前半部分生成回文，候选为 prefix-1、prefix、prefix+1 的镜像。

加入边界候选 10^k + 1 与 10^(k-1) - 1。

选绝对差最小、差相同取更小值的候选。

复杂度分析：

时间复杂度：O(len)，其中 len 表示数字长度。

空间复杂度：O(1)。

import java.util.HashSet;
import java.util.Set;

class Solution {
    public String nearestPalindromic(String n) {
        long num = Long.parseLong(n);
        int len = n.length();
        Set<Long> candidates = new HashSet<>();

        candidates.add((long) Math.pow(10, len) + 1);
        candidates.add((long) Math.pow(10, len - 1) - 1);

        long prefix = Long.parseLong(n.substring(0, (len + 1) / 2));
        for (long p : new long[]{prefix - 1, prefix, prefix + 1}) {
            candidates.add(makePalindrome(p, len % 2 == 1));
        }

        long ans = -1;
        for (long cand : candidates) {
            if (cand == num) {
                continue;
            }
            if (ans == -1) {
                ans = cand;
                continue;
            }
            long diff1 = Math.abs(cand - num);
            long diff2 = Math.abs(ans - num);
            if (diff1 < diff2 || (diff1 == diff2 && cand < ans)) {
                ans = cand;
            }
        }

        return String.valueOf(ans);
    }

    private long makePalindrome(long prefix, boolean odd) {
        long res = prefix;
        if (odd) {
            prefix /= 10;
        }
        while (prefix > 0) {
            res = res * 10 + prefix % 10;
            prefix /= 10;
        }
        return res;
    }
}

import "strconv"

func nearestPalindromic(n string) string {
	num, _ := strconv.ParseInt(n, 10, 64)
	length := len(n)
	candidates := make(map[int64]struct{})

	pow10 := int64(1)
	for i := 0; i < length; i++ {
		pow10 *= 10
	}
	candidates[pow10+1] = struct{}{}
	candidates[pow10/10-1] = struct{}{}

	prefix, _ := strconv.ParseInt(n[:(length+1)/2], 10, 64)
	for _, p := range []int64{prefix - 1, prefix, prefix + 1} {
		candidates[makePal(p, length%2 == 1)] = struct{}{}
	}

	ans := int64(0)
	first := true
	for cand := range candidates {
		if cand == num {
			continue
		}
		if first {
			ans = cand
			first = false
			continue
		}
		diff1 := abs64(cand - num)
		diff2 := abs64(ans - num)
		if diff1 < diff2 || (diff1 == diff2 && cand < ans) {
			ans = cand
		}
	}

	return strconv.FormatInt(ans, 10)
}

func makePal(prefix int64, odd bool) int64 {
	res := prefix
	if odd {
		prefix /= 10
	}
	for prefix > 0 {
		res = res*10 + prefix%10
		prefix /= 10
	}
	return res
}

func abs64(x int64) int64 {
	if x < 0 {
		return -x
	}
	return x
}

相似题目

题目	难度	考察点
9. 回文数	简单	回文
5. 最长回文子串	中等	回文
214. 最短回文串	困难	字符串
680. 验证回文串 II	简单	双指针
647. 回文子串	中等	回文

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/55348450