C C++ 题解LeetCode1417重新格式化字符串

目录
  • 题目描述
    • 整理题意
  • 解题思路分析
  • 具体实现
    • 复杂度分析
  • 代码实现
  • 总结

题目描述

题目链接：1417. 重新格式化字符串

给你一个混合了数字和字母的字符串 s，其中的字母均为小写英文字母。

请你将该字符串重新格式化，使得任意两个相邻字符的类型都不同。也就是说，字母后面应该跟着数字，而数字后面应该跟着字母。

请你返回 重新格式化后 的字符串；如果无法按要求重新格式化，则返回一个 空字符串 。

提示:

  • 1⩽s.length⩽5001
  • s 仅由小写英文字母和/或数字组成。

示例 1：

输入：s = "a0b1c2"
输出："0a1b2c"
解释："0a1b2c" 中任意两个相邻字符的类型都不同。 "a0b1c2", "0a1b2c", "0c2a1b" 也是满足题目要求的答案。

示例 2：

输入： s = "leetcode"
输出： ""
解释： "leetcode" 中只有字母，所以无法满足重新格式化的条件。

示例 3：

输入： s = "1229857369"
输出： ""
解释： "1229857369" 中只有数字，所以无法满足重新格式化的条件。

示例 4：

输入： s = "covid2019"
输出： "c2o0v1i9d"

示例 5：

输入： s = "ab123"
输出： "1a2b3"

整理题意

题目给定一个字符串，仅包含小写字母和数字，让我们利用字符串中所给的这些字符构造一个字符串，使得构造出来的字符串中字母字符和数字字符不相邻。答案返回任意一个满足条件的字符串即可，如果无法构造这样的字符串返回空字符串。

解题思路分析

根据题目描述可知，为了使得字符串中不含有相邻的字母和数字，我们尽可能的使得字母和数字交叉排列，那么当字符串中数字个数和字母个数的差值大于 1 时，无论我们怎么排列总会有两个相同的字母字符或数字字符相邻。

那么考虑当字符串中数字个数和字母个数的差值小于等于 1 时，我们将个数较多的种类字符放在偶数位置上，较少的字符种类放在奇数位置上（位置从 0 开始）。

具体实现

首先统计字符串中数字字符个数和字母字符个数，并判断两者差值是否大于 1，大于 1 的情况直接返回空字符串。

双指针 实现字符串排列：

  • 指针 i 指向偶数位置，j 指向奇数位置；
  • 初始化 i = 0， j = 1；
  • 当 i 位置上的字符不为较多的字符种类时，利用 j 指针从左到右找到第一个较多的字符种类，与位置 i 进行交换字符；
  • 重复步骤 3 直至遍历完整个字符串。

细节操作：代码实现过程中仅用 if(isdigit(s[i]) != f) 这样的判断语句涵括了两种情况的判断。

复杂度分析

  • 时间复杂度：O(n)，其中 n 为字符串 s 的长度，需要遍历两遍字符串。
  • 空间复杂度：O(1)，仅使用常量空间。

代码实现

class Solution {
public:
    string reformat(string s) {
        // 统计数字和字母的个数
        int sum_digit = 0, sum_alpha = 0;
        for(auto &c : s){
            if(isdigit(c)) sum_digit++;
            else sum_alpha++;
        }
        // 当个数差大于 1 时无法构造
        if(abs(sum_digit - sum_alpha) > 1) return "";
        bool f = sum_digit > sum_alpha;
        int n = s.size();
        for(int i = 0, j = 1; i < n; i += 2){
            // 注意判断语句的难点，和 f 有关
            if(isdigit(s[i]) != f){
                while(isdigit(s[j]) != f) j += 2;
                swap(s[i], s[j]);
            }
        }
        return s;
    }
};

总结

  • 该题为简单的字符串题目，需要注意的是代码实现过程中的判断语句部分，isdigit(s[i]) != f 这样一句判断语句即可涵括两种情况的判断，且判断语句需要根据 f 的定义来写。
  • 另外就是双指针的思想，巧妙利用双指针实现字符串的原地构造。
  • 测试结果：

以上就是C C++ 题解LeetCode1417重新格式化字符串的详细内容，更多关于C C++ 重新格式化字符串的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Java C++题解leetcode915分割数组示例

    目录 题目要求 思路一:两次遍历 Java C++ Rust 思路二:一次遍历 Java C++ Rust 题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好: 首先从后向前遍历,找[i,n−1]里最小的值: 然后从前向后遍历,找[0,i]里最大的值: 然后找满足max[i]<=min[i+1]的分割点i: 可以将2.3两步结合为一步完成,由于iii从前向后不断增大,所以用后面(较大)的值覆盖更新之前的值. 找到分界点的索引

  • Java C++题解leetcode902最大为N的数字组合数位DP

    目录 题目要求 阅读理解 思路:数位DP Java C++ 总结 题目要求 题目链接 阅读理解 思路:数位DP Java class Solution { public int atMostNGivenDigitSet(String[] digits, int n) { // 转存digits int[] nums = new int[digits.length]; for (int i = 0; i < digits.length; i++) nums[i] = Integer.parseIn

  • C++ LeetCode1827题解最少操作使数组递增

    目录 LeetCode1827.最少操作使数组递增 方法一:遍历 AC代码 C++ LeetCode1827.最少操作使数组递增 力扣题目链接:leetcode.cn/problems/mi… 给你一个整数数组 nums (下标从 0 开始).每一次操作中,你可以选择数组中一个元素,并将它增加 1 . 比方说,如果 nums = [1,2,3] ,你可以选择增加 nums[1] 得到 nums = [1,3,3] . 请你返回使 nums 严格递增 的 最少 操作次数. 我们称数组 nums 是

  • C++ LeetCode1832题解判断句子是否为全字母句

    目录 LeetCode 1832.判断句子是否为全字母句 方法一:统计 AC代码 C++ LeetCode 1832.判断句子是否为全字母句 力扣题目链接:leetcode.cn/problems/ch… 全字母句 指包含英语字母表中每个字母至少一次的句子. 给你一个仅由小写英文字母组成的字符串 sentence ,请你判断 sentence 是否为 全字母句 . 如果是,返回 true :否则,返回 false . 示例 1: 输入:sentence = "thequickbrownfoxju

  • C++ LeetCode0547题解省份数量图的连通分量

    目录 LeetCode 547.省份数量 方法一:BFS求图的连通分量 AC代码 C++ LeetCode 547.省份数量 力扣题目链接:leetcode.cn/problems/nu… 有 n 个城市,其中一些彼此相连,另一些没有相连.如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连. 省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市. 给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i

  • C++ LeetCode1945题解字符串转化后的各位数字之和

    目录 1945.字符串转化后的各位数字之和 方法一:计算 AC代码 C++ 1945.字符串转化后的各位数字之和 力扣题目链接:leetcode.cn/problems/su… 给你一个由小写字母组成的字符串 s ,以及一个整数 k . 首先,用字母在字母表中的位置替换该字母,将 s 转化 为一个整数(也就是,'a' 用 1 替换,'b' 用 2 替换,... 'z' 用 26 替换).接着,将整数 转换 为其 各位数字之和 .共重复 转换 操作 k 次 . 例如,如果 s = "zbax&qu

  • C++ LeetCode1781题解所有子字符串美丽值之和

    目录 LeetCode 1781.所有子字符串美丽值之和 方法一:前缀和 AC代码 C++ 方法二:边遍历边计算 AC代码 C++ LeetCode 1781.所有子字符串美丽值之和 力扣题目链接:leetcode.cn/problems/su… 一个字符串的 美丽值 定义为:出现频率最高字符与出现频率最低字符的出现次数之差. 比方说,"abaacc" 的美丽值为 3 - 1 = 2 . 给你一个字符串 s ,请你返回它所有子字符串的 美丽值 之和. 示例 1: 输入:s = &quo

  • C C++ 题解LeetCode1417重新格式化字符串

    目录 题目描述 整理题意 解题思路分析 具体实现 复杂度分析 代码实现 总结 题目描述 题目链接:1417. 重新格式化字符串 给你一个混合了数字和字母的字符串 s,其中的字母均为小写英文字母. 请你将该字符串重新格式化,使得任意两个相邻字符的类型都不同.也就是说,字母后面应该跟着数字,而数字后面应该跟着字母. 请你返回 重新格式化后 的字符串:如果无法按要求重新格式化,则返回一个 空字符串 . 提示: 1⩽s.length⩽5001 s 仅由小写英文字母和/或数字组成. 示例 1: 输入:s

  • Python中用format函数格式化字符串的用法

    自python2.6开始,新增了一种格式化字符串的函数str.format(),可谓威力十足.那么,他跟之前的%型格式化字符串相比,有什么优越的存在呢?让我们来揭开它羞答答的面纱. 语法 它通过{}和:来代替%. "映射"示例 通过位置 In [1]: '{0},{1}'.format('kzc',18) Out[1]: 'kzc,18' In [2]: '{},{}'.format('kzc',18) Out[2]: 'kzc,18' In [3]: '{1},{0},{1}'.fo

  • JavaScript实现格式化字符串函数String.format

    JavaScript实现格式化字符串函数String.format

    在js开发中,我们可能会遇到这样一个问题 当需要通过js动态插入html标签的时候 特别是当遇到大量的变量拼接.引号层层嵌套的情况,会出现转义字符问题,经常出错 我们来看个例子 <!DOCTYPE html> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; c

  • C# 格式化字符串的实现代码

    1 前言 如果你熟悉Microsoft Foundation Classes(MFC)的CString,Windows Template Library(WTL)的CString或者Standard Template Library(STL)的字符串类,那么你对String.Format方法肯定很熟悉.在C#中也经常使用这个方法来格式化字符串,比如下面这样: int x = 16; decimal y = 3.57m; string h = String.Format( "item {0} se

  • Python常见格式化字符串方法小结【百分号与format方法】

    本文实例讲述了Python常见格式化字符串方法.分享给大家供大家参考,具体如下: [方式一]百分号(%)方式,类C的printf,需要分别不同类型. 1.匿名tuple.(推荐在参数少时用) >>> '姓名:%s, 年龄:%d' % ('walker', 99) '姓名:walker, 年龄:99' 2.命名dict,字典的key可以重用. >>> '姓名:%(name)s, 年龄:%(age)d, 工龄:%(age)d' % {'name':'walker', 'ag

  • python格式化字符串实例总结

    本文实例总结了python格式化字符串的方法,分享给大家供大家参考.具体分析如下: 将python字符串格式化方法以例子的形式表述如下: * 定义宽度 Python代码如下: >>>'%*s' %(5,'some') ' some' - 左对齐 Python代码如下: >>>'%-*s' %(5,'some') 'some ' 最小宽度为6的2位精度的浮点小数,位数不够时前补空格 Python代码如下: >>>'%6.2f' %8.123 ' 8.12

  • java & Android 格式化字符串详解

    %1$s %1$d Android string (java & Android 格式化字符串) 1$s // String %1$d // int //R.string.old: <string name="old">我今年%1$d岁了</string> String sAgeFormat = getResources().getString(R.string.old); String sFinalAge = String.format(sAgeFor

  • Python格式化字符串f-string概览(小结)

    简介 f-string,亦称为格式化字符串常量(formatted string literals),是Python3.6新引入的一种字符串格式化方法,该方法源于PEP 498 – Literal String Interpolation,主要目的是使格式化字符串的操作更加简便.f-string在形式上是以 f 或 F 修饰符引领的字符串(f'xxx' 或 F'xxx'),以大括号 {} 标明被替换的字段:f-string在本质上并不是字符串常量,而是一个在运行时运算求值的表达式: While

  • Python中应该使用%还是format来格式化字符串

    %还是format 1.皇城PK Python中格式化字符串目前有两种阵营:%和format,我们应该选择哪种呢? 自从Python2.6引入了format这个格式化字符串的方法之后,我认为%还是format这根本就不算个问题.不信你往下看. # 定义一个坐标值 c = (250, 250) # 使用%来格式化 s1 = "敌人坐标:%s" % c 上面的代码很明显会抛出一个如下的TypeError: TypeError: not all arguments converted dur

  • python3格式化字符串 f-string的高级用法(推荐)

    f-string,亦称为格式化字符串常量(formatted string literals),是Python3.6新引入的一种字符串格式化方法,该方法源于PEP 498 – Literal String Interpolation,主要目的是使格式化字符串的操作更加简便. f-string在形式上是以 f 或 F 修饰符引领的字符串(f'xxx' 或 F'xxx'),以大括号 {} 标明被替换的字段:f-string在本质上并不是字符串常量,而是一个在运行时运算求值的表达式: While ot

随机推荐