如何解决电话号码排列问题

Question

问题:

一家公司正在给员工分发电话号码，以使工作更容易。下一位不能等于最后一位是唯一的规则，例如0223不允许，而2023允许。每次至少要排除三位数字。编写一个函数，接受电话号码的长度和将被排除的数字。该函数应该打印所有可能的电话号码。

我在面试中遇到过这个问题，我以前在大学里也见过类似的问题。这是一个排列问题。我的问题是什么是最好的或体面的方法来解决这个问题，而不需要无数的for循环。

我确实理解这是技术上的工作方式

号码长度= 3;

[0-9]，[0-9]不包括最后一位，[0-9]不包括最后一位

但我不确定如何将其转换为代码的最佳方式。任何语言都可以!

谢谢:

我也可能在错误的地方问这个。如果我是，请告诉我。

Answer 1

解决这个问题的一个简单方法是使用递归。下面是我注释过的c++代码:

void solve(int depth, int size, vector <int> &curr_seq){
// If the recursion depth is equal to size, that means we've decided size
// numbers, which means that curr_seq.size() == size. In other words, we've
// decided enough numbers at this point to create a complete phone number, so
// we print it and return.
if(depth == size){
for(int item : curr_seq){
cout << item;
}
cout << "n";
return;
}
// Try appending every possible digit to the current phone number
for(int i = 0; i <= 9; ++i){
// Make sure to only append the digit i if it is not equal to the last digit
// of the phone number. We can also append it, however, if curr_seq
// is empty (because that means that we haven't decided the 1st digit yet).
if(curr_seq.empty() || curr[curr.size() - 1] != i){
curr_seq.push_back(i);
solve(depth + 1, size, curr);
curr_seq.pop_back();
}
}
}

Answer 2

我想我喜欢递归解决方案，但是您也可以生成所有的排列直到极限(迭代)，过滤掉任何重复的数字，并打印成功的候选者:

#include <iomanip>
#include <iostream>
#include <sstream>
using namespace std;
// Because C/C++ still has no integer power function.
int ipow(int base, int exp) {
int result = 1;
for (;;) {
if (exp & 1)
result *= base;
exp >>= 1;
if (!exp)
return result;
base *= base;
}
}
void noconsec(const int len) {
int lim = ipow(10, len);
// For e.g. len 4 (lim 10000),
// obviously 00xx won't work, so skip anything smaller than lim / 100.
int start = (len <= 2) ? 0 : (lim / 100);
for (int num = start;num < lim;num++) {
// Convert to string.
std::stringstream ss;
ss << std::setw(len) << std::setfill('0') << num;
std::string num_s = ss.str();
// Skip any consecutive digits.
bool is_okay = true;
auto prev_digit = num_s[0];
for (int digit_idx = 1;digit_idx < num_s.length();digit_idx++) {
auto digit = num_s[digit_idx];
if (prev_digit == digit) {
is_okay = false;
}
prev_digit = digit;
}
// Output result.
if (is_okay) {
cout << num_s << "n";
}
}
}
int main(const int argc, const char * const argv[]) {
noconsec(4);
}

差异要注意，这需要一个整数幂函数来计算极限。将int型转换为字符串，然后检查字符串，比直接构造字符串要复杂得多。我想如果你已经有一个整数列表，它可能会很有用，但主要是为了好玩。