給定一個整數N，按字典順序從1到N的打印數字

Question

我試圖按照字典順序打印從1到N的數字，但是我得到一個失敗的輸出。對於下面的輸入100，我得到了100，但是它的移位並且與預期的輸出不匹配，我的代碼中存在一個錯誤，但是我無法回溯它。

class Solution { 
public: 
    vector<int> lexicalOrder(int n) { 
     vector<int> result; 
     for(int i = 1; i <= 9; i ++){ 
     int j = 1; 
     while(j <= n){ 
      for(int m = 0; m < j ; ++ m){ 
       if(m + j * i <= n){ 

        result.push_back(m+j*i); 
       } 
      } 
      j *= 10; 
     } 
    } 
    return result; 

    } 
}; 



Input: 
100 
Output: 
[1,10,11,12,13,14,15,16,17,18,19,100,2,20,21,22,23,24,25,26,27,28,29,3,30,31,32,33,34,35,36,37,38,39,4,40,41,42,43,44,45,46,47,48,49,5,50,51,52,53,54,55,56,57,58,59,6,60,61,62,63,64,65,66,67,68,69,7,70,71,72,73,74,75,76,77,78,79,8,80,81,82,83,84,85,86,87,88,89,9,90,91,92,93,94,95,96,97,98,99] 

Expected: 
[1,10,100,11,12,13,14,15,16,17,18,19,2,20,21,22,23,24,25,26,27,28,29,3,30,31,32,33,34,35,36,37,38,39,4,40,41,42,43,44,45,46,47 

Answer 1

你通過所有的2位數字環路輸出前3位號碼前從1開始的，所以你的方法是行不通的。

執行此操作的一種方法是輸出基數爲11的數字，用前導空格填充到最大位數，在此情況下爲3.輸出0作爲空格，1作爲0,2作爲1等。拒絕任何在該表示中具有任何非尾隨空格的數字，或者當被解釋爲基數10數字時，拒絕任何大於n的數字。應該可以一次跳過多個拒絕，但這是不必要的優化。保持你輸出的數字的計數，並在達到n時停止。這將爲您提供基數爲10的字典順序。

使用O（1）空間的示例實現，您可以在輸出第一個數據前不必生成並排序所有數字：

void oneToNLexicographical(int n) 
{ 
    if(n < 1) return; 

    // count max digits 
    int digits = 1, m = n, max_digit11 = 1, max_digit10 = 1; 
    while(m >= 10) 
    { 
     m /= 10; digits++; max_digit11 *= 11; max_digit10 *= 10; 
    } 

    int count = 0; 
    bool found_n = false; 
    // count up starting from max_digit * 2 (first valid value with no leading spaces) 
    for(int i = max_digit11 * 2; ; i++) 
    { 
     int val = 0, trailing_spaces = 0; 
     int place_val11 = max_digit11, place_val10 = max_digit10; 
     // bool valid_spaces = true; 
     for(int d = 0; d < digits; d++) 
     { 
      int base11digit = (i/place_val11) % 11; 
      if(base11digit == 0) 
      { 
       trailing_spaces++; 
       val /= 10; 
      } 
      else 
      { 
       // if we got a non-space after a space, it's invalid 
       // if(trailing_spaces > 0) 
       // { 
       // valid_spaces = false; 
       // break; // trailing spaces only 
       // } 
       val += (base11digit - 1) * place_val10; 
      } 
      place_val11 /= 11; 
      place_val10 /= 10; 
     } 
     // if(valid_spaces && (val <= n)) 
     { 
      cout << val << ", "; 
      count++; 
     } 
     if(val == n) 
     { 
      found_n = true; 
      i += 10 - (i % 11); // skip to next number with one trailing space 
     } 

     // skip past invalid numbers: 

     // if there are multiple trailing spaces then the next run of numbers will have spaces in the middle - invalid 
     if(trailing_spaces > 1) 
      i += (int)pow(11, trailing_spaces - 1) - 1; 
     // if we have already output the max number, then all remaining numbers 
     // with the max number of digits will be greater than n 
     else if(found_n && (trailing_spaces == 1)) 
      i += 10; 

     if(count == n) 
      break; 
    } 
} 

這會跳過所有無效的數字，所以在輸出每個無效數字之前不需要測試valid_spaces。

內環可以通過執行base11被移除 - >底座10轉換使用的差異，使得該算法O（N） - 內的while循環趨向一個常數：

int val = max_digit10; 
for(int i = max_digit11 * 2; ; i++) 
{ 
    int trailing_spaces = 0, pow11 = 1, pow10 = 1; 
    int j = i; 
    while((j % 11) == 0) 
    { 
     trailing_spaces++; 
     pow11 *= 11; 
     pow10 *= 10; 
     j /= 11; 
    } 

    int output_val = val/pow10;  
    if(output_val <= n) 
    { 
     cout << output_val << ", "; 
     count++; 
    } 
    if(output_val == n) 
     found_n = true; 

    if(trailing_spaces > 1) 
    { 
     i += (pow11/11) - 1; 
    } 
    else if(found_n && (trailing_spaces == 1)) 
    { 
     i += 10; 
     val += 10; 
    } 
    else if(trailing_spaces == 0) 
     val++; 

    if(count == n) 
     break; 
} 

Demonstration

另一種更簡單的方法是從數字中生成N個字符串並對它們進行排序。

Answer 2

想想當i=1，j=10將在

for(int m = 0; m < j ; ++ m){ 
       if(m + j * i <= n){ 

        result.push_back(m+j*i); 
       } 
      } 

發生什麼，是的，result會的push_back 10（0 + 10 * 1），11（1 + 10 * 1），12（2 + 10 * 1）.. 這裏是一個解決方案：

#include <iostream> 
#include <vector> 
#include <string> 
std::vector<int> fun(int n) 
{ 
     std::vector<std::string> result; 
     for (int i = 1; i <= n; ++i) { 
      result.push_back(std::to_string(i)); 
     } 
     std::sort(result.begin(),result.end()); 
     std::vector<int> ret; 
     for (auto i : result) { 
      ret.push_back(std::stoi(i)); 
     } 
     return ret; 
} 
int main(int argc, char *argv[]) 
{ 
     std::vector<int> result = fun(100); 
     for (auto i : result) { 
      std::cout << i << ","; 
     } 
     std::cout << std::endl; 
     return 0; 
} 

Answer 3

也許更通用的解決方案？

#include <vector> 
#include <algorithm> 

using namespace std; 

// returns true is i1 < i2 according to lexical order 
bool lexicalLess(int i1, int i2) 
{ 
    int base1 = 1; 
    int base2 = 1; 
    for (int c = i1/10; c > 0; c/=10) base1 *= 10; 
    for (int c = i2/10; c > 0; c/=10) base2 *= 10; 
    while (base1 > 0 && base2 > 0) { 
     int d1 = i1/base1; 
     int d2 = i2/base2; 
     if (d1 != d2) return (d1 < d2); 
     i1 %= base1; 
     i2 %= base2; 
     base1 /= 10; 
     base2 /= 10; 
    } 
    return (base1 < base2); 
} 

vector<int> lexicalOrder(int n) { 
    vector<int> result; 
    for (int i = 1; i <= n; ++i) result.push_back(i); 
    sort(result.begin(), result.end(), lexicalLess); 
    return result; 
} 

爲lexicalLess(...)另一個想法是對比之前整數轉換爲字符串：

#include <vector> 
#include <algorithm> 
#include <string>  
#include <boost/lexical_cast.hpp> 

using namespace std; 

// returns true is i1 < i2 according to lexical order 
bool lexicalLess(int i1, int i2) 
{ 
    string s1 = boost::lexical_cast<string>(i1); 
    string s2 = boost::lexical_cast<string>(i2); 
    return (s1 , s2); 
} 

您需要Boost運行的第二個版本。

Answer 4

一個容易實現的將數字轉換爲字符串，它們串與std::sort在算法頭陣，在字典順序排序字符串進行排序，然後再打開數字爲整數

• 做一個矢量要按字典順序排序的整數，請將其命名爲數字。
• 製作其他矢量並在第一個矢量中填充數字字符串。將其命名爲strs。
• Sort strs array.4。轉換的可疑交易報告載體的字符串爲整數，並把它放在載體
  

列表項

#include <cstdlib> 
#include <string> 
#include <algorithm> 
#include <vector> 
#include <iostream> 
using namespace std; 


string int_to_string(int x){ 
    string ret; 
    while(x > 0){ 
     ret.push_back('0' + x % 10); 
     x /= 10;enter code here 
    } 
    reverse(ret.begin(), ret.end()); 
    return ret; 
} 

int main(){ 
    vector<int> ints; 
    ints.push_back(1); 
    ints.push_back(2); 
    ints.push_back(100); 
    vector<string> strs; 
    for(int i = 0; i < ints.size(); i++){ 
     strs.push_back(int_to_string((ints[i]))); 
    } 
    sort(strs.begin(), strs.end()); 
    vector<int> sorted_ints; 
    for(int i = 0; i < strs.size(); i++){ 
     sorted_ints.push_back(atoi(strs[i].c_str())); 
    } 
    for(int i = 0; i < sorted_ints.size(); i++){ 
     cout<<sorted_ints[i]<<endl; 
    } 
}