将1到99999999之间的数字按字串排序

编辑:解决了!

可以创建按排序顺序输出数字的生成器。我想我们大多数人都知道一些比较串联字符串的规则:

• a<a+b,其中b为非空。
• a+b<a+c,其中b<C

如果您从前1000个数字的排序列表开始,您可以通过添加“千”或“百万”并连接另一组1000个数字来轻松生成其余的数字。

import heapq

first_thousand=[('', 0), ('one', 1), ('two', 2), ('three', 3), ('four', 4),
                ('five', 5), ('six', 6), ('seven', 7), ('eight', 8),
                ('nine', 9), ('ten', 10), ('eleven', 11), ('twelve', 12),
                ('thirteen', 13), ('fourteen', 14), ('fifteen', 15),
                ('sixteen', 16), ('seventeen', 17), ('eighteen', 18),
                ('nineteen', 19)]
tens_name = (None, 'ten', 'twenty', 'thirty', 'forty', 'fifty', 'sixty',
             'seventy','eighty','ninety')
for number in range(20, 100):
    name = tens_name[number/10] + first_thousand[number%10][0]
    first_thousand.append((name, number))
for number in range(100, 1000):
    name = first_thousand[number/100][0] + 'hundred' + first_thousand[number%100][0]
    first_thousand.append((name, number))

first_thousand.sort()

def make_sequence(base_generator, suffix, multiplier):
    prefix_list = [(name+suffix, number*multiplier)
                   for name, number in first_thousand[1:]]
    prefix_list.sort()
    for prefix_name, base_number in prefix_list:
        for name, number in base_generator():
            yield prefix_name + name, base_number + number
    return

def thousand_sequence():
    for name, number in first_thousand:
        yield name, number
    return

def million_sequence():
    return heapq.merge(first_thousand,
                       make_sequence(thousand_sequence, 'thousand', 1000))

def billion_sequence():
    return heapq.merge(million_sequence(),
                       make_sequence(million_sequence, 'million', 1000000))

def solve(stopping_size = 51000000000):
    total_chars = 0
    total_sum = 0
    for name, number in billion_sequence():
        total_chars += len(name)
        total_sum += number
        if total_chars >= stopping_size:
            break
    return total_chars, total_sum, name, number

跑步花了一段时间,大约一个小时。第510亿个字符是600个eventysixmillions甚至100个fortysixth和500个eventyfive中的最后一个字符,此时的整数之和为413540008163475743。

我会对前20个整数的名字和十、百、千的名字进行排序,计算出每一个都有多少个数字,然后从那里开始。

例如,前几个是 [ eight, eighteen, eighthundred, eightmillion, eightthousand, eighty, eleven, ... .

以“八”开头的数字是8。以“八”开头的数字是800-899、800000-899999、80000000-89999999。依此类推。

可以找到0(由空字符串表示)到99的字串联中的字母数并求和;对于更高的范围,可将其乘以“千”=8或“百万”=7。800-899的值将是“eighthundred”长度加上0-99长度的100倍。依此类推。

This guy

这些字符串将有很多常见的前缀,这是 trie

(第一次尝试这一点是错误的,但我将放弃它,因为在解决问题的过程中看到错误比看到最终答案更有用。)

我首先生成从0到999的字符串,并将它们存储到一个名为千字符串的数组中。0元素为“”,并且“”表示以下列表中的空白。

千禧字符串设置使用以下内容:

Units: "" one two three ... nine

Teens: ten eleven twelve ... nineteen

Tens: "" "" twenty thirty forty ... ninety

千禧字符串设置如下所示:

thousandsString[0] = ""

for (i in 1..10)
   thousandsString[i] = Units[i]
end

for (i in 10..19)
   thousandsString[i] = Teens[i]
end

for (i in 20..99)
   thousandsString[i] = Tens[i/10] + Units[i%10]
end

for (i in 100..999)
   thousandsString[i] = Units[i/100] + "hundred" + thousandsString[i%100]
end

然后,我将按字母顺序对数组进行排序。

然后,假设t1 t2 t3是从千串中提取的字符串,则所有字符串都具有以下形式

t1

t1+1000000+t2+000+t3

或

t1+000+t2

foreach (t1 in thousandsStrings)

   if (t1 == "")
     continue;

   process(t1)

   foreach (t2 in thousandsStrings)
      foreach (t3 in thousandsStrings)
         process (t1 + "million" + t2 + "thousand" + t3)
      end
   end

   foreach (t2 in thousandsStrings)
       process (t1 + "thousand" + t2)
   end
end

其中,过程意味着存储以前的和长度,然后将新字符串长度添加到和中,如果新和为>=你的目标和,你吐出结果,也许返回或打破循环,任何让你高兴的事情。

第二次尝试,其他答案是正确的,您需要使用3k字符串而不是1k字符串作为基础。

从上面的千弦开始,但把空白“0”。这就剩下999个元素,并将其称为uStr(单位字符串)。

再创建两个集合:

tStr = the set of all uStr + "thousand"

mStr = the set of all uStr + "million"

现在再创建两个集合联合:

mtuStr = mStr union tStr union uStr

tuStr = tStr union uStr

foreach (s1 in mtuStr)
   process(s1)

   // If this is a millions or thousands string, add the extra strings that can
   // go after the millions or thousands parts.

   if (s1.contains("million"))
      foreach (s2 in tuStr)
         process (s1+s2)          

         if (s2.contains("thousand"))
            foreach (s3 in uStr)
               process (s1+s2+s3)
            end
         end
      end
   end

   if (s1.contains("thousand"))
      foreach (s2 in uStr)
         process (s1+s2)
      end
   end
end

下面是我的python解决方案,它可以在几分之一秒内打印出正确的答案。一般来说,我不是python程序员,因此对于任何令人震惊的代码风格错误,我深表歉意。

#!/usr/bin/env python

import sys

ONES=[
    "",         "one",      "two",      "three",        "four", 
    "five",     "six",      "seven",    "eight",        "nine",
    "ten",      "eleven",   "twelve",   "thirteen",     "fourteen",
    "fifteen",  "sixteen",  "seventeen","eighteen",     "nineteen",
]
TENS=[
    "zero",     "ten",      "twenty",   "thirty",       "forty",
    "fifty",    "sixty",    "seventy",  "eighty",       "ninety",
]

def to_s_h(i):
    if(i<20):
        return(ONES[i])
    return(TENS[i/10] + ONES[i%10]) 

def to_s_t(i):
    if(i<100):
        return(to_s_h(i))
    return(ONES[i/100] + "hundred" + to_s_h(i%100))

def to_s_m(i):
    if(i<1000):
        return(to_s_t(i))
    return(to_s_t(i/1000) + "thousand" + to_s_t(i%1000))

def to_s_b(i):
    if(i<1000000):
        return(to_s_m(i))
    return(to_s_m(i/1000000) + "million" + to_s_m(i%1000000))


def try_string(s,t):
    global letters_to_go,word_sum
    l=len(s)
    letters_to_go -= l
    word_sum += t
    if(letters_to_go == 0):
        print "solved: " + s
        print "sum is: " + str(word_sum)
        sys.exit(0)
    elif(letters_to_go < 0):
        print "failed: " + s + " " + str(letters_to_go)
        sys.exit(-1)

def solve(depth,prefix,prefix_num):
    global millions,thousands,ones,letters_to_go,onelen,thousandlen,word_sum
    src=[ millions,thousands,ones ][depth]
    for x in src:
        num=prefix + x[2]
        nn=prefix_num+x[1]
        try_string(num,nn)
        if(x[0] == 0):
            continue
        if(x[0] == 1):
            stl=(len(num) * 999) + onelen
            ss=(nn*999) + onesum
        else:
            stl=(len(num) * 999999) + thousandlen + onelen*999
            ss=(nn*999999) + thousandsum
        if(stl < letters_to_go):
            letters_to_go -= stl
            word_sum += ss
        else:
            solve(depth+1,num,nn)


ones=[]
thousands=[]
millions=[]
onelen=0
thousandlen=0
onesum=(999*1000)/2
thousandsum=(999999*1000000)/2



for x in range(1,1000):
    s=to_s_b(x)
    l=len(s)
    ones.append( (0,x,s) )
    onelen += l
    thousands.append( (0,x,s) )
    thousands.append( (1,x*1000,s + "thousand") )
    thousandlen += l + (l+len("thousand"))*1000
    millions.append( (0,x,s) )
    millions.append( (1,x*1000,s + "thousand") )
    millions.append( (2,x*1000000,s + "million") )

ones.sort(key=lambda x: x[2])
thousands.sort(key=lambda x: x[2])
millions.sort(key=lambda x: x[2])

letters_to_go=51000000000
word_sum=0

solve(0,"",0)

它的工作原理是预先计算1..999和1..999999之间的数字长度,这样它就可以跳过整个子树,除非它知道答案在子树的某个地方。

我所做的: 1) 遍历1-999,并为每一个生成单词。 2) 创建3个数据结构,其中每个节点都有一个指向子节点的指针,每个节点都有一个字符值和一个指向同级节点的指针(二叉树,事实上,但我们不想这样认为——对我来说,它更容易被概念化为一个兄弟姐妹的列表,孩子的列表悬而未决,但如果你想一想{画一张图片},你会发现它实际上是一个二叉树)。 a) 第一个是生成的单词(即1-999按字母顺序排序) c) B中的所有值+a中的所有值加上百万(总共2997个值) 3) 对于(b)中的每个叶节点,添加一个子节点作为(a)。对于(c)中的每个叶节点,添加一个子节点作为(b)。 4) 遍历这棵树,数一数我们经过了多少个字符,然后停在510亿。

注意:这不会求和(我最初读取时没有读取该位),运行时间仅超过3分钟(使用c++,通常约192秒)。

奇怪但有趣的想法。

构建一个稀疏列表,列出从0到9,再到10-90乘以10,再到100,1000等等,再到十亿,索引是存储长度的整数部分的值。

编写一个函数,使用表将数字计算为字符串长度。 (将数字分成几部分,并查找围裙的长度,但实际上从未创建字符串。)

然后你只需要在遍历这些数字的时候做数学运算,从这些数字计算长度 为您的总和填写表格。

通过求和和和最后一个整数的值,算出拼写的整数,然后volia,就完成了。

简单地说,不要存储“onethousandleventyseven”单词,而是编写排序以在比较时使用它。

public class BillionsBillions implements Comparator {
    public int compare(Object a, Object b) {
        String s1 = (String)a; // "1234";
        String s2 = (String)b; // "1235";

        int n1 = Integer.valueOf(s1);
        int n2 = Integer.valueOf(s2);

        String w1 = numberToWords(n1);
        String w2 = numberToWords(n2);

        return w1.compare(w2);
    }

    public static void main(String args[]) {
        long numbers[] = new long[1000000000]; // Bring your 64 bit JVMs

        for(int i = 0; i < 1000000000; i++) {
            numbers[i] = i;
        }

        Arrays.sort(numbers, 0, numbers.length, new BillionsBillions());

        long total = 0;

        for(int i : numbers) {
            String l = numberToWords(i);
            long offset = total + l - 51000000000;

            if (offset >= 0) {
                String c = l.substring(l - offset, l - offset + 1);
                System.out.println(c);
                break;
            }
         }
    }
}

“numberToWords”留给读者作为练习。

是否需要将整个字符串保存在内存中?

二十

然后我会看着你 进一步基于可能的前缀。例如,在ninehundred中,您将拥有所有必须从900开始的相同桶,仅适用于从900开始的数字。

问题在于高效的数据存储,而不是字符串操作。创建一个枚举来表示单词。单词应该以排序的顺序出现,这样当需要排序时,它只是一个简单的比较。现在生成列表并进行排序。使用这样一个事实,即您知道每个单词与枚举结合的时间长度,以添加到所需的字符。

代码赢了。。。

#!/bin/bash
n=0
while [ $n -lt 1000000000 ]; do
   number -l $n | sed -e 's/[^a-z]//g'
   let n=n+1
done | sort > /tmp/bignumbers
awk '
BEGIN {
    total = 0;
}
{
    l = length($0); 
    offset = total + l - 51000000000;
    print total " " offset
    if (offset >= 0) {
        c = substr($0, l - offset, 1);
        print c;
        exit;
    }
    total = total + l;
}' /tmp/bignumbers

测试范围小得多;-)。需要大量的磁盘空间,一个压缩的文件系统是有价值的,但是没有那么多内存。

Sort也有压缩工作文件的选项,您可以加入gzip直接压缩数据。

这不是最快捷的解决方案。

但它确实有效。

1. 将十亿个字符串插入索引表。
2. 计算字符串长度列。
3. 开始用一个总数一次刷新前X记录,直到我达到510亿。

可能会让服务器崩溃一段时间,因为它需要执行大量磁盘IO,但总体而言,我认为我可以比编写程序的人更快地找到答案。

有时候,客户真正想要的就是完成它,而不在乎您使用了什么花哨的设计模式或数据结构。

计算出1-999的长度,并将0的长度包含为0。

(不打算详细介绍生成此文件的过程) 还需要一千个最后字母的数组last_letters[1000] (同样,我不打算详细介绍生成该循环的细节,因为它更容易,即使是数百个d,甚至是十个y,除了10,它是n个其他循环,尽管最后一个是on) E 通过nin E 零是不相关的)

uint32 sizes999[1000];

uint64 totallen = 0;
strlen_million = strlen("million");
strlen_thousand = strlen("thousand");
for (uint32 i = 0; i<1000;++i){
    for (uint32 j = 0; j<1000;++j){
        for (uint32 j = 0; j<1000;++j){ 
           total_len += sizes999[i]+strlen_million + 
                        sizes999[j]+strlen_thousand +
                        sizes999[k];
           if totallen == 51000000000 goto done;
           ASSERT(totallen <51000000000);//he claimed  51000000000 was not intermediate
        }
    }
}
done:

//现在使用i j k通过使用last_letters999获取最后一个字母

//把i,j,k想象成以1000为基数的数字

//如果只有k=0,那么字母是d千 D

//其他明智的做法是使用自

//以1000为基数的单位,即k,不是零

//对于数字i、j、k之和,是以1000为基数的数字

n = i*1000000 + j*1000 + k;

//表示数字和用途

sum = n*(n+1)/2;

如果您需要对51000000000以外的数字进行计算,那么也要计算SUM_sizes999,并以自然的方式使用它。

总时间:0(n),其中n是数字

这就是我要做的:

1. 创建一个包含2997个字符串的数组:“one”到“ninehundredninetyine”,“onethousand”到“ninehundredninetyinethousand”,以及“one000000”到“ninehundredninetyinemellion”。
3. 按字母顺序对2997个字符串排序。

创建此数组后,可以根据以下观察结果按字母顺序直接查找所有99999999字符串:

2. 任何内容或“一”字符串都不能跟在“千”字符串后面
3. “一”字符串、“千”字符串或“千”字符串(然后是“一”字符串)后面不能跟“百万”字符串。

2. 如果不能做到这一点,请尽可能按字母顺序将最右边的标记前进到下一个标记。
3. 如果这也是不可能的,那么移除最右边的标记,并将第二个最右边的标记按字母顺序前进到下一个标记(如果可能)。
4. 如果这也不可能,你就完了。

在每一步中,只需保持两个运行总数,就可以计算字符串的总长度和数字的总和。

对我来说,这需要一个动态规划解决方案,其中计算出数十、数百、数千等字符串的数量,并将其存储在某种类型的查找表中。当然,会有一对十一,二对十二等特殊情况

如果我能得到一个快速运行的解决方案,我会更新这个。

错了!!!!!!!!!我把问题看错了。我以为它的意思是“按字母顺序排列的最后一个数字的最后一个字母是什么”

public class Nums {

// if overflows happen, switch to an BigDecimal or something
// with arbitrary precision
public static void main(String[] args) {
    System.out.println("last letter: " + lastLetter(1L, 51000000L);
    System.out.println("sum: " + sum(1L, 51000000L);
}    

static char lastLetter(long start, long end) {
   String last = toWord(start);
   for(long i = start; i < end; i++)
      String current = toWord(i);
      if(current.compareTo(last) > 1)
         last = current;

   return last.charAt(last.length()-1);
}

static String toWord(long num) {
   // should be relatively easy, but for now ...
   return "one";
}

static long sum(long first, long n) {
   return (n * first + n*n) / 2;
}
}

还没有真正尝试过这个:/LOL

你有10亿个数字和510亿个字符-这很可能是一个诡计问题,因为每个数字平均有51个字符。把所有数字的换算加起来,看看总数是否达到510亿。

我在2008年的某个时候用Java解决了这个问题,并将其作为应用程序的一部分 ITA Software .

代码很长,现在已经三年过去了,我带着一点恐惧看着它。。。所以我不打算发了。

但我会引用我在应用程序中包含的一些注释。

紧跟在任何以百万结尾的条目(比如数字是X)之后的是99999个条目,它们以相同的文本开头,表示X+1中的所有数字

所有这些数字的总和可以通过经典公式(算术数列)计算,字符计数可以通过基于前缀(上面的X)的类似简单公式计算,以及从1到999999的数字的一次计算的字符计数。两者都只取决于范围底部数字的百万部分。因此,如果整个范围的字符计数将使整个计数低于搜索目标,则不需要遍历各个条目。

1到999步进1 1000到999000步进1000

代码遍历该列表,累积总和和字符计数,根据需要递归创建、排序和遍历类似但较小的列表。

我没有得到这份工作,但后来将代码用作另一份工作的“代码示例”,我确实得到了这份工作。

Java代码使用这些技术跳过大部分显式计数并在大约8秒内添加运行。