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

更新時(shí)間：2022年10月19日 10:48:56 作者：Junkman丶

這篇文章主要為大家介紹了C?C++?題解LeetCode1417重新格式化字符串，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目描述

題目鏈接：1417. 重新格式化字符串

給你一個(gè)混合了數(shù)字和字母的字符串 s，其中的字母均為小寫英文字母。

請(qǐng)你將該字符串重新格式化，使得任意兩個(gè)相鄰字符的類型都不同。也就是說，字母后面應(yīng)該跟著數(shù)字，而數(shù)字后面應(yīng)該跟著字母。

請(qǐng)你返回 重新格式化后 的字符串；如果無法按要求重新格式化，則返回一個(gè) 空字符串 。

提示:

1?s.length?5001
s 僅由小寫英文字母和/或數(shù)字組成。

示例 1：

輸入：s = "a0b1c2"
輸出："0a1b2c"
解釋："0a1b2c" 中任意兩個(gè)相鄰字符的類型都不同。 "a0b1c2", "0a1b2c", "0c2a1b" 也是滿足題目要求的答案。

示例 2：

輸入： s = "leetcode"
輸出： ""
解釋： "leetcode" 中只有字母，所以無法滿足重新格式化的條件。

示例 3：

輸入： s = "1229857369"
輸出： ""
解釋： "1229857369" 中只有數(shù)字，所以無法滿足重新格式化的條件。

示例 4：

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

示例 5：

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

整理題意

題目給定一個(gè)字符串，僅包含小寫字母和數(shù)字，讓我們利用字符串中所給的這些字符構(gòu)造一個(gè)字符串，使得構(gòu)造出來的字符串中字母字符和數(shù)字字符不相鄰。答案返回任意一個(gè)滿足條件的字符串即可，如果無法構(gòu)造這樣的字符串返回空字符串。

解題思路分析

根據(jù)題目描述可知，為了使得字符串中不含有相鄰的字母和數(shù)字，我們盡可能的使得字母和數(shù)字交叉排列，那么當(dāng)字符串中數(shù)字個(gè)數(shù)和字母?jìng)€(gè)數(shù)的差值大于 1 時(shí)，無論我們?cè)趺磁帕锌倳?huì)有兩個(gè)相同的字母字符或數(shù)字字符相鄰。

那么考慮當(dāng)字符串中數(shù)字個(gè)數(shù)和字母?jìng)€(gè)數(shù)的差值小于等于 1 時(shí)，我們將個(gè)數(shù)較多的種類字符放在偶數(shù)位置上，較少的字符種類放在奇數(shù)位置上（位置從 0 開始）。

具體實(shí)現(xiàn)

首先統(tǒng)計(jì)字符串中數(shù)字字符個(gè)數(shù)和字母字符個(gè)數(shù)，并判斷兩者差值是否大于 1，大于 1 的情況直接返回空字符串。

雙指針 實(shí)現(xiàn)字符串排列：

指針 i 指向偶數(shù)位置，j 指向奇數(shù)位置；
初始化 i = 0， j = 1；
當(dāng) i 位置上的字符不為較多的字符種類時(shí)，利用 j 指針從左到右找到第一個(gè)較多的字符種類，與位置 i 進(jìn)行交換字符；
重復(fù)步驟 3 直至遍歷完整個(gè)字符串。

細(xì)節(jié)操作：代碼實(shí)現(xiàn)過程中僅用 if(isdigit(s[i]) != f) 這樣的判斷語句涵括了兩種情況的判斷。

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n)，其中 n 為字符串 s 的長(zhǎng)度，需要遍歷兩遍字符串。
空間復(fù)雜度：O(1)，僅使用常量空間。

代碼實(shí)現(xiàn)

class Solution {
public:
    string reformat(string s) {
        // 統(tǒng)計(jì)數(shù)字和字母的個(gè)數(shù)
        int sum_digit = 0, sum_alpha = 0;
        for(auto &c : s){
            if(isdigit(c)) sum_digit++;
            else sum_alpha++;
        }
        // 當(dāng)個(gè)數(shù)差大于 1 時(shí)無法構(gòu)造
        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){
            // 注意判斷語句的難點(diǎn)，和 f 有關(guān)
            if(isdigit(s[i]) != f){
                while(isdigit(s[j]) != f) j += 2;
                swap(s[i], s[j]);
            }
        }
        return s;
    }
};

總結(jié)

該題為簡(jiǎn)單的字符串題目，需要注意的是代碼實(shí)現(xiàn)過程中的判斷語句部分，isdigit(s[i]) != f 這樣一句判斷語句即可涵括兩種情況的判斷，且判斷語句需要根據(jù) f 的定義來寫。
另外就是雙指針的思想，巧妙利用雙指針實(shí)現(xiàn)字符串的原地構(gòu)造。
測(cè)試結(jié)果：