C++ LeetCode1945題解字符串轉(zhuǎn)化后的各位數(shù)字之和

更新時(shí)間：2022年12月16日 10:22:21 作者：LetMeFly

這篇文章主要為大家介紹了C++ LeetCode1945題解字符串轉(zhuǎn)化后的各位數(shù)字之和示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

1945.字符串轉(zhuǎn)化后的各位數(shù)字之和

給你一個(gè)由小寫(xiě)字母組成的字符串 s ，以及一個(gè)整數(shù) k 。

首先，用字母在字母表中的位置替換該字母，將 s 轉(zhuǎn)化 為一個(gè)整數(shù)（也就是，'a' 用 1 替換，'b' 用 2 替換，... 'z' 用 26 替換）。接著，將整數(shù) 轉(zhuǎn)換 為其 各位數(shù)字之和 。共重復(fù) 轉(zhuǎn)換 操作 k 次 。

例如，如果 s = "zbax" 且 k = 2 ，那么執(zhí)行下述步驟后得到的結(jié)果是整數(shù) 8 ：

轉(zhuǎn)化："zbax" ? "(26)(2)(1)(24)" ? "262124" ? 262124
轉(zhuǎn)換 #1：262124 ? 2 + 6 + 2 + 1 + 2 + 4 ? 17
轉(zhuǎn)換 #2：17 ? 1 + 7 ? 8

返回執(zhí)行上述操作后得到的結(jié)果整數(shù)。

示例 1：

<strong>輸入：</strong>s = "iiii", k = 1
<strong>輸出：</strong>36
<strong>解釋?zhuān)?lt;/strong>操作如下：
- 轉(zhuǎn)化："iiii" ? "(9)(9)(9)(9)" ? "9999" ? 9999
- 轉(zhuǎn)換 #1：9999 ? 9 + 9 + 9 + 9 ? 36
因此，結(jié)果整數(shù)為 36 。

示例 2：

<strong>輸入：</strong>s = "leetcode", k = 2
<strong>輸出：</strong>6
<strong>解釋?zhuān)?lt;/strong>操作如下：
- 轉(zhuǎn)化："leetcode" ? "(12)(5)(5)(20)(3)(15)(4)(5)" ? "12552031545" ? 12552031545
- 轉(zhuǎn)換 #1：12552031545 ? 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 ? 33
- 轉(zhuǎn)換 #2：33 ? 3 + 3 ? 6
因此，結(jié)果整數(shù)為 6 。

提示：

1 <= s.length <= 100
1 <= k <= 10
s 由小寫(xiě)英文字母組成

方法一：計(jì)算

字符串長(zhǎng)度可能為100100100，C++C++C++等語(yǔ)言中很難直接存放下1020010^{200}10200的數(shù)

這里有兩種方案，一種是將數(shù)字以字符串的形式存放，另一種是，不存放1020010^{200}10200這么大的數(shù)字，而是直接存放這個(gè)數(shù)字的每位之和

這個(gè)數(shù)字的每位之和最大不超過(guò)9×2009\times2009×200，很容易用整數(shù)型變量存下。

接下來(lái)就是進(jìn)行k−1k-1k−1次特殊計(jì)算

計(jì)算的時(shí)候，我們將這個(gè)數(shù)的每一位不斷取出，并累加到一個(gè)臨時(shí)變量中，然后使用這個(gè)臨時(shí)變量代替這個(gè)數(shù)即可

// 一次求和操作
int temp = 0;
while (ans) {
    temp += ans % 10;
    ans /= 10;
}
ans = temp;

時(shí)間復(fù)雜度O(\len(s)+k)O(\len(s) + k)O(\len(s)+k)，每次求和操作的時(shí)間復(fù)雜度可以視為O(1)O(1)O(1)，因?yàn)檫@個(gè)數(shù)最多不超過(guò)180018001800，最多進(jìn)行444次加法運(yùn)算
空間復(fù)雜度O(1)O(1)O(1)

AC代碼

C++

class Solution {
public:
    int getLucky(string& s, int k) {
        int ans = 0;
        for (char c : s) {
            ans += (c - 'a' + 1) / 10 + (c - 'a' + 1) % 10;
        }
        while (--k) {
            int temp = 0;
            while (ans) {
                temp += ans % 10;
                ans /= 10;
            }
            ans = temp;
        }
        return ans;
    }
};

執(zhí)行結(jié)果：