题目描述javascript
继MIUI8推出手机分身功能,MIUI计划推出一个电话号码分身得功能:首先将电话号码中的每一个数字加上8取个位,而后使用对应得大写字母代替 ("ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"), 而后随机打乱这些字母,所生成得字符串即为电话号码对应得分身。java
例子:
输入 => 输出
EIGHT => 0
ZEROTWOONE => 234
OHWETENRTEO => 345
OHEWTIEGTHENRTEO => 0345算法
这道题是输入一个字符串,映射到一个数字串。
映射题个人习惯是先尝试用字典的方式作,那么接下来开始作这道题:数组
10个数字与其英文单词一一对应,那么这些词能不能作些文章呢?code
咱们能够发现,在这十个数字的英文单词中,字符 Z
只存在于 ZERO
,W
只存在于 TWO
,以此类推。
因此如今一旦在字符串中发现 Z
,咱们就能够说存在 0
。
咱们在这里把 Z
称做 特征字符
, ZERO
称做 字符值
, 0
称为 数字值
那么,咱们能够获得一组映射:排序
{ Z: ['ZERO', 0], W: ['TWO', 2], U: ['FOUR', 4], X: ['SIX', 6], G: ['EIGHT', 8] }
所以0, 2, 4, 6, 8
已经处理好了,如今还剩下 1, 3, 5, 7, 9
。
仔细分析能够发现,字符O
在这五个数字的英文中,只存在于ONE
;字符F
只存在于FIVE
中,以此类推。
那么,咱们又能够获得一组映射:ip
{ O: ['ONE', 1], T: ['THREE', 3], F: ['FIVE', 5], S: ['SEVEN', 7] }
为何这里没有9
的映射呢?由于 NINE
中N, I, E
在 1, 3, 5, 7
中都有出现,这里咱们就先空着。字符串
注意
这里的两个映射关系是不能够合并的,想一想为何?it
那么这些映射关系有什么用呢?这里就要用到字典(dict)啦。
咱们能够把输入的字符串,转换为一个字典结构,key
是字符, value
是这个字符在整个字符串中出现的次数。console
例如:
"OHEWTIEGTHENRTEO" var dict = { E: 4, T: 3, O: 2, H: 2, I: 1, G: 1, W: 1, N: 1, R: 1 }
而后咱们遍历这个字典:
[{ Z: ['ZERO', 0], W: ['TWO', 2], U: ['FOUR', 4], X: ['SIX', 6], G: ['EIGHT', 8] },{ O: ['ONE', 1], T: ['THREE', 3], F: ['FIVE', 5], S: ['SEVEN', 7] }].map(map => { Object.keys(dict).map(key => { /** 检查当前字符是否在映射表中 * 在的话检查字典中当前字符的数量是否仍然大于0 */ map[key] && dict[key] > 0 && /** * 把映射关系中的字面值取出并拆解为一个字符数组, * 遍历这个字符数组,将字典中该字符的计数减去1,即消化了这个字面值 */ map[key][0].split('').map(char => dict[char] -= 1) && // 把消化的数字值打出来 console.log(map[key][1]) }) }) /** * 2 * 8 * 1 * 3 */
但是题目说明 OHEWTIEGTHENRTEO
的输出值应该是 0345
呀,哪里出错了呢?
注意题目中的一句话
首先将电话号码中的每一个数字加上8取个位
也就是说,咱们打出来的值还须要对这个 加8取个位
进行逆向。
有几种方法,一是在打印时对 map[key][1]
进行处理:
num => num - 8 >= 0 ? num - 8 : num + 2
或者,我这里用了偷懒的办法,还记得咱们映射表中有个数字值吗?我人工替换了 :P
[{ Z: ['ZERO', 2], W: ['TWO', 4], U: ['FOUR', 6], X: ['SIX', 8], G: ['EIGHT', 0] },{ O: ['ONE', 3], T: ['THREE', 5], F: ['FIVE', 7], S: ['SEVEN', 9 }].map(map => { Object.keys(dict).map(key => { map[key] && dict[key] > 0 && map[key][0].split('').map(char => dict[char] -= 1) && console.log(map[key][1]) }) }) /** * 4 * 0 * 3 * 5 */
那么如今只须要把输出值进行一下正序排序便可:
var output = []; [{ Z: ['ZERO', 2], W: ['TWO', 4], U: ['FOUR', 6], X: ['SIX', 8], G: ['EIGHT', 0] },{ O: ['ONE', 3], T: ['THREE', 5], F: ['FIVE', 7], S: ['SEVEN', 9}].map(map => { Object.keys(dict).map(key => { map[key] && dict[key] > 0 && map[key][0].split('').map(char => dict[char] -= 1) && output.push(map[key][1]) }) }) /* * 还记得咱们把 9 的处理留空了吗?如今要补上啦~ * 9 的英文 NINE 你只须要随意检查前边过滤后的字典是否还存在 N I E 任意一个字符便可 * 我选择的是判断 E * 输入的9对应的输出应该是1,还记得为何吗? */ //if (dict['E'] && dict['E'] > 0) output.push(1) /** * 2017.09.19 08:36 更新: * 以前只判断了是否还存在9,可是忘了多个9同时存在的状况,那么须要作以下改进: */ dist['E'] && // 检查是否还存在特征字符 E,在通过前面的映射关系过滤后,还剩下几个E,就还有几个9 (output = output.concat(Array(dist['E']).fill(1))) //纯js技巧,快速生成指定大小的数组并填充一个值 output.sort() console.log(output) // 0 3 4 5
虽说本文标题有个 [算法]
前缀,不过这个写法彻底没考虑什么复杂度之类的东西 ORZ