写点什么

LeetCode 最长快乐字符串使用 JavaScript 解题

作者:董员外
  • 2022 年 9 月 02 日
    江苏
  • 本文字数:1011 字

    阅读完需:约 3 分钟

LeetCode最长快乐字符串使用JavaScript解题

有人相爱,有人夜里开车看海,我是 leetcode 第一题都做不出来

题目

如果字符串中不含有任何 'aaa','bbb' 或 'ccc' 这样的字符串作为子串,那么该字符串就是一个「快乐字符串」。


给你三个整数 a,b ,c,请你返回 任意一个 满足下列全部条件的字符串 s:


  • s 是一个尽可能长的快乐字符串。

  • s 中 最多 有 a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。

  • s 中只含有 'a'、'b' 、'c' 三种字母。


如果不存在这样的字符串 s ,请返回一个空字符串 ""。


输入:a = 1, b = 1, c = 7

输出:"ccaccbcc"

解释:"ccbccacc" 也是一种正确答案。


快乐字符串中不含有三个连续相同的字母。为了找到最长的字符串,我们可以使用如下贪心策略:


  • 尽可能优先使用当前数量最多的字母,因为最后同一种字母剩余的越多,越容易出现字母连续相同的情况。如果构建完成最长的快乐字符串后还存在剩余未选择的字母,则剩余的字母一定为同一种字母且该字母的总数量最多。

  • 依次从当前数量最多的字母开始尝试,如果发现加入当前字母会导致出现三个连续相同字母,则跳过当前字母,直到我们找到可以添加的字母为止。实际上每次只会在数量最多和次多的字母中选择一个。

  • 如果尝试所有的字母都无法添加,则直接退出,此时构成的字符串即为最长的快乐字符串。


上面一大串内容太多了,看不进去;来,咱们简化一下捋一下思路


  • 第一步:建立一个二维数组,记录 a,b,c 的他们的名字和次数。

  • 第二步:建立一个空字符串,把出现次数最多的字母加入字符串后面。

  • 第三步:当数量最多的字母在字符串末尾出现了两次,则推入第二多的字母,以此类推。

  • 第四步:都推不了的时候,就返回结果。


var longestDiverseString = function (a, b, c) {    const abc = [['a', a], ['b', b], ['c', c]];    //存储最终的字符串    let res = '';    while (true) {        //将数组进行排序,最多的排在前面        abc.sort((a, b) => b[1] - a[1]);        //repeat是将字符串自身进行复制,传入的参数就是复制几次 'a'.repeat(2) = 'aa'        //获取res最后两个字符,与剩余个数最多的一个字符的重复进行比较        //如果相同,就说明res最后两个字符是相同的,返回索引为1        const idx = res.slice(-2) === abc[0][0].repeat(2) ? 1 : 0;        //获取到该索引的字符串个数为0是 返回res        if (abc[idx][1]-- === 0) return res;        res += abc[idx][0];    }};
复制代码

知识点

  • repeat是将字符串自身进行复制,传入的参数就是复制几次

发布于: 刚刚阅读数: 3
用户头像

董员外

关注

距离成为百年老程序员还差98年 2021.03.04 加入

公众号:oldCode 分享面经,新技术,实战项目,一起来折腾吧

评论

发布
暂无评论
LeetCode最长快乐字符串使用JavaScript解题_JavaScript_董员外_InfoQ写作社区