给出一串随机顺序的数字，你必须以严格降序的十进制格式打印它们

问题描述 投票：0回答：3

示例：nieignhtesevfouenr 答：9874

请有人回答这个问题。 谢谢你。

algorithm data-structures
3个回答
8
投票

您可以应用此算法：

  • 首先统计输入字符串中每个字母的出现次数。例如，示例输入字符串出现以下情况：

    {
  "e": 4,
  "f": 1,
  "g": 1,
  "h": 1,
  "i": 2,
  "n": 3,
  "o": 1,
  "r": 1,
  "s": 1,
  "t": 1,
  "u": 1,
  "v": 1,
  "w": 0,
  "x": 0,
  "z": 0
}

    我还包含了未使用的字母，因为它们将在“二”、“六”和“零”中发挥作用，但在此示例输入中未表示它们。

现在我们可以观察到：

  • 输入中的每个“z”都属于“零”；
  • 每个“w”都属于一个“two”；
  • 每个“u”都属于一个“4”；
  • 每个“x”都属于一个“6”；
  • 每个“g”都属于“8”

如果在输入字符串中找到“z”的数量，则可以推断出“0”出现的次数，并且可以从“z”、“e”、“r”和“o”中扣除该次数”。应该为输出记录那么多“0”。

完成上述操作后，我们可以继续以下操作：

  • 每个剩余“o”都属于一个“一”（因为此时所有“零”、“二”、“四”都已被计算在内）。
  • 每个剩余“h”都属于“三”
  • 剩下的每个“f”都属于“五”
  • 剩下的每个“s”都属于“七”

考虑完这些之后，我们最终可以得出结论：

  • 剩下的每个“i”都属于“9”

我们可以简化一点，因为有些字母在决定代表哪些数字时并没有真正发挥作用。例如，在上面的逻辑中，我们不关心“n”或“e”的数量，因此当我们检测到“1”等时，我们最好不要减少它们的数量。上面列出了我们唯一关心的 10 个字母。

最后我们使用每个数字的计数来构建排序后的字符串。

这是 JavaScript 中的实现。它运行示例输入的算法。没有输入验证...假定是数字名称的有效组合：

// reference data. The identifying letter is put at the front, 
//    and the letters that still matter for another digit
//    follow it.
let map = [
    ["zo", "0"],
    ["wo", "2"],
    ["ufo", "4"],
    ["xis", "6"],
    ["gih", "8"],
    ["o", "1"],
    ["h", "3"],
    ["fi", "5"],
    ["s", "7"],
    ["i", "9"]
];

// The algorithm
function decimals(s) {
    // Count occurrences of letters
    let charCount = {};
    for (let c of "efghinorstuvwxz") charCount[c] = 0;
    for (let c of s) charCount[c]++;
    // Recognise digits by their identifying letter
    let digitCount = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    for (let [name, digit] of map) {
        let frequency = charCount[name[0]];
        for (let letter of name) charCount[letter] -= frequency;
        digitCount[digit] = frequency;
    }
    // Build the result string
    let result = "";
    for (let digit of "9876543210") result += digit.repeat(digitCount[digit]);
    return result;
}

// Example run
let result = decimals("nieignhtesevfouenr");
console.log(result);

1
投票

@trincot 用 JavaScript 中的巧妙算法打响了第一枪。

这是 Python 中的改编，逻辑基本相同：

import collections

def unscramble(s):
  c = collections.Counter(s)
  return list(itertools.chain.from_iterable(
    [[9]*(c['i'] - c['x'] - c['g'] - (c['f']-c['u'])),
     [8]*c['g'],
     [7]*(c['s']-c['x']),
     [6]*c['x'],
     [5]*(c['f']-c['u']),
     [4]*c['u'],
     [3]*(c['h'] - c['g']),
     [2]*c['w'],
     [1]*(c['o'] - c['z'] - c['w'] - c['u']),
     [0]*c['z']]))

为了进行比较，这里有一个 python 中的暴力方法，它会尝试每种数字组合（进行一些检查以避免迭代显然不具有正确长度的组合）。暴力解决方案在输入字符串上的速度大约慢 100 倍 

'nieignhtesevfouenr'
。

import itertools

def unscramble_bruteforce(s):
  s = ''.join(sorted(s))
  for r in range(len(unscramble.d)):
    if unscramble.min_lengths[r] <= len(s) <= unscramble.max_lengths[r]:
      for c in itertools.combinations(unscramble.d, r):
        if sum(len(n) for n in c) == len(s):
          if ''.join(sorted(''.join(c))) == s:
            return sorted([unscramble.d[n] for n in c], reverse=True)
  return None

unscramble.d = { ''.join(sorted(n)): i for i,n in enumerate(['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten', 'eleven', 'twelve']) }
unscramble.max_lengths = [max(sum(len(n) for n in c) for c in itertools.combinations(unscramble.d, r)) for r in range(len(unscramble.d))]
unscramble.min_lengths = [min(sum(len(n) for n in c) for c in itertools.combinations(unscramble.d, r)) for r in range(len(unscramble.d))]

print(unscramble('nieignhtesevfouenr'))
# [9, 8, 7, 4]

为了将 

['eight', 'seven', 'four', 'nine']
等组合与加扰的输入字符串 
'nieignhtesevfouenr'
进行比较，我们按字母顺序对两个字符串进行排序：将 
''.join(sorted(s))
与 
''.join(sorted(''.join(c)))
进行比较。或者，我们可以比较两个多重集/
collections.Counter
对象，计算两个字符串中每个不同字符的出现次数并检查它们是否对应。渐近地，这应该更有效，但在输入字符串
'nieignhtesevfouenr'
的实践中，结果慢了大约 40%。

0
投票

这是我的方法，基于字符频率的计数，并贪婪地检查“z”等唯一字母表示“零”，还考虑“九”等需要 2 个“n”。

#include<bits/stdc++.h>
using namespace std;

// Problem : Derive Telephone Number
void solve(string s)
{
    unordered_map<char,int> mp;
    for(int i=0;i<s.length();i++){
        if(s[i]>='A' && s[i]<='Z') s[i]+=32;
        mp[s[i]]++;
    }
    
    int ans[11]={};

    ans[6] += min(mp['s'],min(mp['i'],mp['x']));
    mp['s']-=ans[6];mp['i']-=ans[6];mp['x']-=ans[6];

    ans[8] += min(mp['e'],min(mp['i'],min(mp['g'],min(mp['h'],mp['t']))));
    mp['e']-=ans[8];mp['i']-=ans[8];mp['g']-=ans[8];mp['h']-=ans[8];mp['t']-=ans[8];

    ans[2] += min(mp['t'],min(mp['w'],mp['o']));
    mp['t']-=ans[2];mp['w']-=ans[2];mp['o']-=ans[2];

    ans[4] += min(mp['f'],min(mp['o'],min(mp['u'],mp['r'])));
    mp['f']-=ans[4];mp['o']-=ans[4];mp['u']-=ans[4];mp['r']-=ans[4];

    ans[0]+=min(mp['z'],min(mp['e'],min(mp['r'],mp['o'])));
    mp['z']-=ans[0];mp['e']-=ans[0];mp['r']-=ans[0];mp['o']-=ans[0];

    ans[3] += min(mp['t'],min(mp['h'],min(mp['r'],mp['e']/2)));
    mp['t']-=ans[3];mp['h']-=ans[3];mp['r']-=ans[3];mp['e']-=2*ans[3];

    ans[7] += min(mp['s'],min(mp['e']/2,min(mp['v'],mp['n'])));
    mp['s']-=ans[7];mp['e']-=2*ans[7];mp['v']-=ans[7];mp['n']-=ans[7];

    ans[5] += min(mp['f'],min(mp['i'],min(mp['v'],mp['e'])));
    mp['f']-=ans[5];mp['i']-=ans[5];mp['v']-=ans[5];mp['e']-=ans[5];

    ans[1] += min(mp['o'],min(mp['n'],mp['e']));
    mp['o']-=ans[1];mp['n']-=ans[1];mp['e']-=ans[1];

    ans[9] += min(mp['n']/2,min(mp['i'],mp['e']));
    mp['n']-=2*ans[9];mp['e']-=ans[9];mp['i']-=ans[9];

    for(int i=9;i>=0;i--){
        while(ans[i]--) cout<<i;
    }
    cout<<endl;
}

int main(){
    string s = "OfNTiWenINeOVE";
    solve(s);
    s = "zWRoTeorzeo";
    solve(s);
    s = "FISEVENVETHNINEREONEE";  // 97531
    solve(s);
    s = "ninenineninesevensevensevensevenfivefivethreethreethreethreeoneoneoneoneoneoneoneone"; //999777755333311111111
    solve(s);
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.