最近的回文数

问题描述 投票：7回答：6

我遇到了一个常见的面试问题，即找到最接近的回文数。假设输入为127，则输出为131，如果为125则输出为121。

我可以提出逻辑，但我的逻辑在某些情况下失败，例如91,911。在这些输入中它给出99,919，但正确的输出是88和909。

算法步骤是：

  • 将数字转换为字符串。
  • 以相反的顺序将上半部分复制到后半部分
  • 转换为数字并测量abs。与原始数字diff1的差异
  • 添加1到半个字符串，现在以相反的顺序将前半部分复制到后半部分
  • 转换为数字并测量abs。与原始数字diff2的差异
  • 如果diff1小于diff2则返回第一个数字，否则返回第二个数字
c++ algorithm palindrome
6个回答
12
投票

这实际上是一个有趣的问题。显然，你想要做的不仅仅是使用最有效的数字，而是将它们放在最不重要的数字位置以形成回文。 （我将把回文和原文之间的区别称为“距离”）

从那以后我会说我们可以忽略数字中最不重要的一半，因为它确实无关紧要（确定距离时很重要，但这就是全部）。

我将采用一个抽象的数字：ABCDEF。其中A，B，C，D，E，F都是随机数。再次，正如我所说，D，E，F不需要确定回文，因为我们想要的是将数字的前半部分镜像到后半部分。显然，我们不希望以相反的方式做到这一点，或者我们将修改更多有效数字，从而导致与原始数据的距离更远。

所以回文将是ABCCBA，但是你已经说过，这并不总是你最短的距离。然而，“解决方案”仍然是XYZZYX的形式，所以如果我们考虑最小化我们正在修改的数字的“重要性”，这意味着我们想要修改C（或最中间的数字）。

让我们退一步看看为什么：qazxsw poi

  • 起初，修改ABCCBA可能很诱人，因为它处于最不重要的位置：最右边。但是为了修改最不重要的我们需要修改最重要的。所以A出局了。
  • A也是如此，所以B最终成为我们的首选数字。

好的，现在我们已经解决了我们想要修改C以获得我们需要考虑边界的可能更接近的数字。 C是我们的原始数字，如果ABCDEF不是最接近的回文，那么可能是什么？基于我们上面的小迂回，我们可以通过修改ABCCBA找到它。所以有两种情况，C大于ABCDEF或小于ABCCBA。

如果ABCCBA大于ABCDEF，那么让我们加1到ABCCBA。我们会说C所以现在我们有一个数字T = C+1。所以我们将测试以确保ABTTBA，如果是这样我们知道ABCDEF - ABCCBA > ABCDEF - ABTTBA是最近的回文。随着对C的任何更多修改将使我们越来越遥远。

或者，如果ABTTBA小于ABCDEF，那么我们将从ABCCBA中减去1。让我们说C。所以我们有V = C-1，就像上面我们要测试的那样：ABVVBA你将拥有相同的解决方案。

诀窍是ABCDEF - ABCCBA > ABCDEF - ABVVBA总是在ABCDEF和ABTTBA之间，而这些数字之间唯一的其他回文是ABVVBA。因此，您只有3个解决方案选项。如果你将ABCCBA与ABCDEF进行比较，你只需要检查2。

我不认为你很难适应任何规模的数字。在奇数个数字的情况下，你只需要ABCCBA，ABCBA和ABVBA等等......

就像你的例子一样：让我们拿911。

  1. 忽略最后一个我们只采取上半场（向上舍入）。所以91X。
  2. 将X替换为9.我们有919.这是中点。
  3. 我们知道我们原来的911小于919所以从我们的中间数减去1，所以得到第二个（下限）909。
  4. 比较ABTBA和911 - 919
  5. 返回差异最小的那个。

所以这给了我们一个恒定的时间算法:) 正如评论中指出的那样，在最坏的情况下（oops），这不是恒定时间，但肯定比蛮力方法更好。

这似乎是你所拥有的，但我认为我会详细说明这个问题，因为它似乎是你的一个小编程错误。

4
投票

这是Naveen和Don的算法的实现。它使用Happy Yellow Face的算法作为测试oracle。

我很乐意看到人们调整它以删除冗余步骤或特殊情况。

gcc 4.7.3：g ++ -Wall -Wextra -std = c ++ 0x nearest-palindrome.cpp

911 - 909
3
投票

这是一个可以工作1的通用算法，尽管使用暴力：

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>

// I do not have std::to_string.
template <class T>
std::string to_string(const T& v) {
  std::stringstream ss;
  ss << v;
  return ss.str(); }

// Nor do I have std::stoi. :(
int stoi(const std::string& s) {
  std::stringstream ss(s);
  int v;
  ss >> v;
  return v; }

bool isPalindrome(int n) {
  const auto s = to_string(n);
  return s == std::string(s.rbegin(), s.rend()); }

int specNearestPalindrome(int n) {
  assert(0 <= n);

  int less = n, more = n;
  while (true) {
    if (isPalindrome(less)) { return less; }
    if (isPalindrome(more)) { return more; }
    --less; ++more; } }

std::string reflect(std::string& str, int n) {
  std::string s(str);
  s.resize(s.size() + n);
  std::reverse_copy(std::begin(str),
      std::next(std::begin(str), n),
      std::next(std::begin(s), str.size()));
  return s; }

bool isPow10(int n) {
  return n < 10 ? n == 1 : (n % 10 == 0) && isPow10(n / 10); }

int nearestPalindrome(int n) {
  assert(0 <= n);
  if (n != 1 && isPow10(n)) { return n - 1; }  // special case

  auto nstr = to_string(n);
  // first half, rounding up
  auto f1 = nstr.substr(0, (nstr.size() + 1) / 2);
  auto p1 = stoi(reflect(f1, nstr.size() / 2));

  const auto twiddle = p1 <= n ? 1 : -1;
  auto f2 = to_string((stoi(f1) + twiddle));
  auto p2 = stoi(reflect(f2, nstr.size() / 2));

  if (p2 < p1) { std::swap(p1, p2); }
  return n - p1 <= p2 - n ? p1 : p2; }

int main() {
  std::vector<int> tests = { 0, 1, 6, 9, 10, 11, 12, 71, 74, 79, 99, 100, 999, 1000, 9900, 9999, 999000 };

  for (const auto& t : tests) {
    std::cout <<
      (nearestPalindrome(t) == specNearestPalindrome(t) ? "." : "X");
  }
  std::cout << std::endl;

  return 0; }

在withinint findNearestPalindrome(int n) { int less = n; int more = n; while(true) { if (isPalindrome(less)) return less; if (isPalindrome(more)) return more; --less; ++more; } } 函数中，您需要做的就是将数字转换为字符串，然后是isPalindrome()。

1然而，这不会检查领带案例，如Ted Hopp评论。您必须进行一些更改才能使其可以识别。

1
投票
compare the string with itself reversed
0
投票
#include <iostream>
#include <cmath>
#include <functional>
#include <limits>
#include <sstream>

// for convience
using namespace std; 
using ULL = unsigned long long int;

// calculate the number of digits
auto Len = [](auto num) -> ULL {
return floor(log10(num)) + 1; };

// extract left half of number
auto Halfn = [](auto num, auto olen) {
for (unsigned i = 0; i < olen / 2; num /= 10, ++i);
 return num; 
};

int main() {   
ULL num;   cin >> num;
// some basic checking   
if (num < 10)   {
cerr << "Error, enter a number >= 10";
return 0;   
}

if (numeric_limits<ULL>::max() <  num) {
cerr << "Error, number too large\n";
return 0;   
}
cout << ([](auto num) {   
auto olen = Len(num);   
auto lhalf = Halfn(num, olen);   

function<ULL(ULL)> palin = [olen]  (auto lhalf) { 
auto half = to_string(lhalf);
// this is the mirror string that needs to be  
// appended to left half to form the final 
// palindrome 
auto tmp = half.substr(0, olen / 2);

// take care of a corner case which 
// happens when the number of digits in 
// the left half of number decrease, while
// trying to find a lower palindrome 
// e.g.  num = 100000
// left half = 100  , the value passed to the  
// function palin, is 99. if all digits  are 9 
// then we need to adjust the   count of 9, 
// otherwise if i simply replicate it, i'll get 
// 9999 but one more 9 is required for the   
// correct output.

if (olen / 2 > tmp.size() &&
all_of(tmp.begin(), tmp.end(),
[](auto c) { return '9' == c; }))  {
tmp += '9';  
}

// append, convert and return   
half = half + string(tmp.crbegin(),                              
                   tmp.crend());
return stoull(half);  
};

auto bpalin = palin(lhalf);   
auto hpalin = palin(lhalf + 1);   
auto lpalin = palin(lhalf - 1);

stringstream ss;
ss << "base palindrome = " << bpalin <<'\n'; 
ss << "higher palindrome = "<<hpalin <<'\n';
ss << "lower palindrome = " << lpalin  <<'\n';

// calculating absolute difference for 
// finding the nearest palindrome

auto diffb = labs(bpalin - num);   
auto diffh = labs(hpalin - num); 
auto diffl = labs(lpalin - num);

auto nearest = (diffb < diffh) ? 
(diffb < diffl) ? bpalin : lpalin : 
(diffh < diffl) ? hpalin : lpalin;

ss << "nearest palindrome = "
     << nearest << endl;
    return move(ss.str());
 }(num)); 
} // end main
0
投票

Javascript解决方案：

class Solution {
    public String nearestPalindromic(String n) {
         int order = (int) Math.pow(10, n.length()/2);
    Long ans = Long.valueOf(new String(n));
    Long noChange = mirror(ans);
    Long larger = mirror((ans/order)*order + order+1);
    Long smaller = mirror((ans/order)*order - 1 );
    if ( noChange > ans) {
        larger = (long) Math.min(noChange, larger);
    } else if ( noChange < ans) {
        smaller = (long) Math.max(noChange, smaller); 
    }       
    return String.valueOf( ans - smaller <= larger - ans ? smaller :larger) ;
}
Long mirror(Long ans) {
    char[] a = String.valueOf(ans).toCharArray();
    int i = 0;
    int j = a.length-1;
    while (i < j) {
        a[j--] = a[i++];
    }
    return Long.valueOf(new String(a));
} 


}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.