By Long Luo
Leetcode 423. 从英文中重建数字 题解。
方法一:按照独占性依次确定每一个数字的次数
思路与算法:
最开始,看到这道题我是懵逼的,字符串怎么变成一串数字,按照什么规律,认真读了几遍,参考示例才明白啥意思。
每个数字都对应一个英文单词,zero,one,two,three,four,five,six,seven,eight,nine,统计每个英文字母在这些单词中出现的情况,发现有些字母只出现在某一个单词里,而有些字母则会出现在很多单词里。
比如 z 就只出现在 zero 里,g 只出现在 eight 里。 而 i 则同时出现在了 five,six,eight,nine 中,那么我们需要先求出乱序的字符串中每个数字包含了多少个,然后按照升序进行排列。
那么我们先对乱序字符串遍历计数,按照独占性,先把特定数字中的单词数量找出来,比如出现多少个 z,就一定有多少个 0。然后再把 0 中出现的字母去掉,逐步消元。
那么我们可以先统计每个字母的个数,然后减去对应数字的单词字母数,直至都为 0。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| public String originalDigits(String s) { Map<Character, Integer> map = new HashMap<Character, Integer>(); for (int i = 0; i < s.length(); ++i) { map.put(s.charAt(i), map.getOrDefault(ch, 0) + 1); }
int[] cnt = new int[10]; cnt[0] = map.getOrDefault('z', 0); cnt[2] = map.getOrDefault('w', 0); cnt[4] = map.getOrDefault('u', 0); cnt[6] = map.getOrDefault('x', 0); cnt[8] = map.getOrDefault('g', 0);
cnt[3] = map.getOrDefault('h', 0) - cnt[8]; cnt[5] = map.getOrDefault('f', 0) - cnt[4]; cnt[7] = map.getOrDefault('s', 0) - cnt[6];
cnt[1] = map.getOrDefault('o', 0) - cnt[0] - cnt[2] - cnt[4];
cnt[9] = map.getOrDefault('i', 0) - cnt[5] - cnt[6] - cnt[8];
StringBuffer ans = new StringBuffer(); for (int i = 0; i < 10; ++i) { for (int j = 0; j < cnt[i]; ++j) { ans.append((char) (i + '0')); } } return ans.toString(); }
|
复杂度分析:
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗