【codewars】修复秘钥

发布在 codewars

好久没写博客了,随着工作时间见长,也发现有的东西太不值得写,而且随便一搜都能找到,无论是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 肯定会为空,然后依次类推就可以一直推出整个字符串了。

注释和共享

  • 第 1 页 共 1 页

yuansc

生命不息,奋斗不止


改变世界