好久没写博客了,随着工作时间见长,也发现有的东西太不值得写,而且随便一搜都能找到,无论是google还是baidu。所以也还是想写一些精品一点的文章。
之前不经意间在cnode逛社区的时候看到一个网站 codewars 不经意间也迷上了刷题之路,比国内的OJ平台起码界面上友好的多得多。而今天要做的一个东西也是其中一个题目。
Recover a secret string from random triplets
_看博客之前请先看连接的题目内容,在这里就不贴题了
代码
个人惯例上代码(本人小菜鸡,这是排名第一的答案)
1 | var recoverSecret = function(triplets) { var charInfo = {}; var registeredOrderedPair = function(ch1, ch2) { var ch1Info = charInfo[ch1] || {earlier: [], later: []}; var ch2Info = charInfo[ch2] || {earlier: [], later: []}; ch1Info.later.push(ch2); ch2Info.earlier.push(ch1); charInfo[ch1] = ch1Info; charInfo[ch2] = ch2Info; }; var findEarliest = function() { // Earliest is the one that has no earlier characters for(var ch in charInfo) { if (charInfo[ch].earlier.length == 0) return ch; } }; var removeChar = function(chToDelete) { delete charInfo[chToDelete]; var isNotCh = function(ch) {return ch !== chToDelete;}; for(var ch in charInfo) { charInfo[ch].earlier = charInfo[ch].earlier.filter(isNotCh); charInfo[ch].later = charInfo[ch].later.filter(isNotCh); } }; triplets.forEach(function(triplet) { registeredOrderedPair(triplet[0], triplet[1]); registeredOrderedPair(triplet[1], triplet[2]); }); var result = ''; while(Object.keys(charInfo).length > 0) { var ch = findEarliest(); result += ch; removeChar(ch); } return result; }; |
代码详解
建立树形结构
代码中的registeredOrderedPair
便是根据给定的数组,对于每一个节点 一个earlier
,和later
数组。
找到第一个
如何找到第一个呢,只要这个字母earlier
数组为空,那么就代表这个字母肯定是第一个。
找到第二个 第三个 。。。
如何找到第二个第三个呢,在所有字母的earlier
中删掉第一个字母的痕迹,,那么第二个字母的earlier
肯定会为空,然后依次类推就可以一直推出整个字符串了。