By Long Luo
Leetcode 423. 从英文中重建数字 题解。
方法一:按照独占性依次确定每一个数字的次数
思路与算法:
最开始,看到这道题我是懵逼 的,字符串怎么变成一串数字,按照什么规律,认真读了几遍,参考示例才明白啥意思。
每个数字都对应一个英文单词,z e r o , o n e , t w o , t h r e e , f o u r , f i v e , s i x , s e v e n , e i g h t , n i n e zero, one, two, three, four, five, six, seven, eight, nine z e r o , o n e , t w o , t h r e e , f o u r , f i v e , s i x , s e v e n , e i g h t , n i n e ,统计每个英文字母在这些单词中出现的情况,发现有些字母只出现在某一个单词里,而有些字母则会出现在很多单词里。
比如 z z z 就只出现在 z e r o zero z e r o 里,g g g 只出现在 e i g h t eight e i g h t 里。 而 i i i 则同时出现在了 f i v e , s i x , e i g h t , n i n e five, six, eight, nine f i v e , s i x , e i g h t , n i n e 中,那么我们需要先求出乱序的字符串中每个数字包含了多少个,然后按照升序进行排列。
那么我们先对乱序字符串遍历计数,按照独占性,先把特定数字中的单词数量找出来,比如出现多少个 z z z ,就一定有多少个 0 0 0 。然后再把 0 0 0 中出现的字母去掉,逐步消元。
那么我们可以先统计每个字母的个数,然后减去对应数字的单词字母数,直至都为 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 . 😉😃💗