首页 > 其他分享 >【Leetcode 1370 】 数组序号转换—— 桶计数

【Leetcode 1370 】 数组序号转换—— 桶计数

时间:2024-08-20 18:23:28浏览次数:13  
标签:字符 arr 示例 res 1370 字符串 步骤 序号 Leetcode

给你一个字符串 s ,请你根据下面的算法重新构造字符串:

  1. 从 s 中选出 最小 的字符,将它 接在 结果字符串的后面。
  2. 从 s 剩余字符中选出 最小 的字符,且该字符比上一个添加的字符大,将它 接在 结果字符串后面。
  3. 重复步骤 2 ,直到你没法从 s 中选择字符。
  4. 从 s 中选出 最大 的字符,将它 接在 结果字符串的后面。
  5. 从 s 剩余字符中选出 最大 的字符,且该字符比上一个添加的字符小,将它 接在 结果字符串后面。
  6. 重复步骤 5 ,直到你没法从 s 中选择字符。
  7. 重复步骤 1 到 6 ,直到 s 中所有字符都已经被选过。

在任何一步中,如果最小或者最大字符不止一个 ,你可以选择其中任意一个,并将其添加到结果字符串。

请你返回将 s 中字符重新排序后的 结果字符串 。

示例 1:

输入:s = "aaaabbbbcccc"
输出:"abccbaabccba"
解释:第一轮的步骤 1,2,3 后,结果字符串为 result = "abc"
第一轮的步骤 4,5,6 后,结果字符串为 result = "abccba"
第一轮结束,现在 s = "aabbcc" ,我们再次回到步骤 1
第二轮的步骤 1,2,3 后,结果字符串为 result = "abccbaabc"
第二轮的步骤 4,5,6 后,结果字符串为 result = "abccbaabccba"

示例 2:

输入:s = "rat"
输出:"art"
解释:单词 "rat" 在上述算法重排序以后变成 "art"

示例 3:

输入:s = "leetcode"
输出:"cdelotee"

示例 4:

输入:s = "ggggggg"
输出:"ggggggg"

示例 5:

输入:s = "spo"
输出:"ops"

桶计数

function sortString(s: string): string {
  //从 s 中找出最小值,并与res的最后一个字符比较,比它小则拼接,一样则从 s 中找到除它以外最小的值,并继续比较

  //保存26个字母,索引为 其charCode与a的偏移量
  const arr = Array(26).fill(0);
  // a 的 UTF-16 码元
  const base = "a".charCodeAt(0);
  for (const char of s) {
    // a 为索引0(因为其偏移量为0)
    arr[char.charCodeAt(0) - base] += 1;
  }
  const res: number[] = [];

  while (res.length < s.length) {
    //升序
    for (let i = 0; i < 26; i++) {
      if (arr[i] > 0) {
        res.push(i);
        arr[i]--;
      }
    }
    //降序
    for (let i = 26; i >= 0; i--) {
      if (arr[i] > 0) {
        res.push(i);
        arr[i]--;
      }
    }
  }
  // UTF-16 码元 转字符串
  return res.map((n) => String.fromCharCode(n + base)).join("");
}

标签:字符,arr,示例,res,1370,字符串,步骤,序号,Leetcode
From: https://blog.csdn.net/Caoshuang_/article/details/141363203

相关文章

  • 【Leetcode 1365 】 有多少小于当前数字的数字 —— 数组模拟哈希表(就没写过这么详细
    给你一个数组 nums,对于其中每个元素 nums[i],请你统计数组中比它小的所有数字的数目。换而言之,对于每个 nums[i] 你必须计算出有效的 j 的数量,其中 j 满足 j!=i 且 nums[j]<nums[i] 。以数组形式返回答案。示例1:输入:nums=[8,1,2,2,3]输出:[4,0,1,1,3]解......
  • Leetcode 59.螺旋矩阵II
    力扣题目链接(opensnewwindow)**给定一个正整数n,生成一个包含1到n^2所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。示例:输入:3输出:[[1,2,3],[8,9,4],[7,6,5]]思路这道题目可以说在面试中出现频率较高的题目,本题并不涉及到什么算法,就是......
  • Leetcode JAVA刷刷站(55)跳跃游戏
    一、题目概述二、思路方向    在Java中,为了解决这个问题,你可以采用贪心算法的思想。贪心算法在这里的应用主要体现在,每一步都尽可能跳得远,以此来判断是否能够到达数组的最后一个下标。    算法的思路是,遍历数组nums,用一个变量farthest来记录遍历过程中能够......
  • Leetcode面试经典面试题-81.搜索旋转排序数组II
    解法都在代码里,不懂就留言或者私信,这个题目一定要注意重复元素的情况shpublicstaticbooleansearch(int[]nums,inttarget){/**空数组不可能找到任何数*/if(nums==null||nums.length==0){returnfalse;}/**如果......
  • LeetCode-Python-3154. 到达第 K 级台阶的方案数(DFS + 数学)
    给你有一个 非负 整数 k 。有一个无限长度的台阶,最低 一层编号为0。Alice 有一个整数 jump ,一开始值为0。Alice从台阶1开始,可以使用 任意 次操作,目标是到达第 k 级台阶。假设Alice位于台阶 i ,一次 操作 中,Alice可以:向下走一级到 i-1 ,但该操作......
  • leetcode 1082典型题 ,开窗函数
     示例零: SELECTseller_id,RANK()OVER(ORDERBYSUM(price)DESC)ASr,SUM(price)FROMSales结果:返回一条数据,没有partition关键字,等于是全表做orderby,基于全表做sum排序,其实这个sql有问题.|seller_id|rk|SUM(price)||---------|--|------......
  • LCP:60 排列序列[leetcode-4]
    LCP:60排列序列给出集合[1,2,3,...,n],其所有元素共有n!种排列。按大小顺序列出所有排列情况,并一一标记,当n=3时,所有排列如下:"123""132""213""231""312""321"给定n和k,返回第k个排列。示例1:输入:n=3,k=3输出:"213"示例2:输入:n=4,......
  • leetcode面试经典150题-125. 验证回文串
    https://leetcode.cn/problems/valid-palindrome/description/?envType=study-plan-v2&envId=top-interview-150 packageleetcode150import("strings""testing")funcTestIsPalindrome(t*testing.T){s:="0P"......
  • LeetCode 202. 快乐数
    题目描述编写一个算法来判断一个数n是不是快乐数。「快乐数」 定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为1,也可能是无限循环但始终变不到1。如果这个过程结果为 1,那么这个数就是快乐数。如果n是快乐......
  • Leetcode-552 学生出勤记录II
    Leetcode-552学生出勤记录II1.题目描述2.解题思路3.代码实现1.题目描述Leetcode-552学生出勤记录II2.解题思路(1)使用记忆化搜索来实现;(2)定义f[i][j][k]为右边填写j个A,且右边相邻位置有k个连续的L的情况下,向左填字母能构造多少个长为i的字符串;(3)对......