python C++速解Leetcode 1945 Sum of Digits of String After Convert

An-Wen Deng
4粉絲
82 次觀看·2024年10月14日
python C++速解Leetcode 1945 Sum of Digits of String After Convert
這是個簡單問題,有技巧。
第一次轉換不需要用bigINT來存,只是將數字與第1輪的數字相加即可。
由於s.length最多可能為100,因此使用bigInt或其他字串效率非常低。
---
This is an easy question with some tricks.
The first conversion does not need to use a bigINT to hold, but just add the digits to the number in the 1st round.
Since s.length may be 100 at most, it's very inefficient to use bigInt or other string.
[codes on Leetcode]https://leetcode.com/problems/sum-of-digits-of-string-after-convert/solutions/5728524/convert-letters-to-number-then-sum-digits-beats-100/
[Leetcode Playlist]https://www.youtube.com/watch?v=B1GQlUN08lk&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk
好,各位好,我們來解今天 LeetCode 的問題
今天問題是第 1945 題
它標示是為一個簡單的問題
所謂 sum of digits of string after convert
就是說
你有一個字串
你要將它轉換成為數字
然後再考慮數字的和
那我們看它的一個題目
題目是這樣的
假設你有一個字串 S
它只有小寫的英文字母
然後還有一個整數 K
首先呢
你要將 S 轉換成為整數
它怎麼轉換呢?
這邊就寫得很清楚
A 的話就要用 1 來替換
B 請用 2 來替換
C 的話是 26
所以
這個部分 A 的話是 1
那這是第一個轉換
首先的轉換
然後呢
基本上你是要將這樣的一個數字
用所謂 sum of its digits
也就是它數字的和來取代
然後你要做下面的一個步驟
這樣的 transform 呢
你要行使 K 次
所以它這邊就給一個簡單的例子
比方說 S 等於 ZB
A X
K 等於 2
首先呢
你當然就是按照它的提議
將它轉換 Z 變成 26
B 變成 2
A 變成 1
X 變成 24
所以就變成這樣一個數字
然後呢
你第一次的 transform
transform number 1
當然就是這個數字的和
所以就 2 加 6 加 2 加 1 加 2 加 4
變成 17
然後第二次的 transform
是 17 變成 1 加 7
所以就是 8
以它這邊的一個例子來講的話
答案是 8
那我們再看它下面的例子
它下面有列舉了三個例子
第一個例子呢
I I I I
所以 I 的話它是對應到 9
所以就總共是
9999
那總共有四個 9
所以當然就 36
因為它 K 等於 1
所以你只要做一次數字的和就可以了
那我們再看第二個例子
是叫做 decode
它要做兩次
所以第一次呢
是將它的小寫英文字母轉換成為數字
然後再去考慮它數字的和
所以做第一次的 transform
所以是 1 加 2 加 5
加 5 加 2
加 0 加 3
加 1 加 5
加 4 加 5
變成 33
再做第二次
33 就轉換成為 3 加 3 等於 6
所以這個是它的第二個例子
第三個例子它就沒有做說明瞭
那我們主要要看它的 constraint
constraint 的部分其實滿重要的
也就是說你這個 S 最長可以到 100
所以
你一開頭的轉換
如果你是採用
像是西語言
或是西加加去撰寫的話
它當然
你用 int 或是 long long
這個當然都不行
所以這個在撰寫上稍微有點技巧
那 K 的話是
這個還好
它最多是到 10
那 S 它是有
只擁有
小寫的英文字母
那我們就看看我們大概是怎麼解
這樣的一個問題
好那我們這裡先切到
我們的一個 note 的頁面
針對這樣一個解題的一個步驟
我們大概是
打算是這樣解
就是說我們的第一步當然是
將 S 先轉換成為 number
那基本上我們就是
在 S 字串每個字元都去做轉換
但是要請注意
它每個字元
它轉換的數字
可能 1 到 2 個數字
所以呢
我們一開始就給它做加總
就將它
所對應的數字
因為它是 1 到 26
所以這邊呢
基本上你用所謂的
DIV NOD
就是除法
有餘數的除法
這樣的一個函數去作用
基本上它 Q 的話
就是它的 sum
基本上就 0 1 2
R 的話還有餘數
所以你就將它的 sum
跟餘數都給它加進來
那我們就
不需要用一個很長的整數
或者另外一個字串去存
這樣的轉換
不需要
我們就
第一次的 transform
我們就先把答案
先把它處理
所以如果說 K 如果只有一次的話
等於 1 的話
我們其實答案就出來了
然後原則上我們就是
每一次都是 K 往下減 1
所以我們會用一個
應該算是 nasty loop
所謂的潮狀迴圈去做
一開始我們當然設定
X 等於 number
然後我們只要是
我們的 X 大於等於 10
而且 K 大於等於 0
那我們就做下面的步驟
當然這邊我們的
每一個 step 就是
K 要減 1
所以我們的內層迴圈
一樣跟它的一個步驟
也是去做除法
但是這是有餘數的除法
然後我們再將數字
再把它加進來
最後答案當然就是 number
那我們這個部分
我們就用 Python 來設定
首先我們當然就根據剛剛所說的
所以我們當然就先設 number
一開始當然是 0
所以第一次的轉換
當然 C 是在
我們的 S 這個 string 裡面的
所有的字元
然後呢
我們的 X 是
C 的 rod
因為它這邊 a 的話是
小 a 的話呢
S key code 是 97
所以我們這邊就
直接就減 96 就好了
乾脆一點
然後我們去算除法
當然有餘數的除法
Q 是它的 sum
R 是它的餘數
d,v,i,n,o,d
所以 X 當然就是除以 10
所以我們的 number
你就把 Q 跟 R 把它加進來
所以我們這邊當然就是
你可以做判斷
如果是 k 等於 1 的話
我們就把答案傳回去
但是我們也不需要
所以我們這邊基本上就統一來做
所以 k 你就減等於 1
所以在 k 減掉 1 之後呢
我們要將 X 更新為
我們的目前的 number
所以你要繼續
因為 k 已經是大於 1 了
下面的情況
所以我們下面就用迴圈來考慮
在迴圈的外層呢
它應該是跟變數是無關的
所以我們用
underscore 來就可以了
它的變動的方式是從
k 到 1 為止
所以這邊是有頭無尾
所以這要填 0
每一次都要減 1
接下來我們的 number
就設為 0
內層迴圈我們還是用條件迴圈
所以只要是 X 大於 0
我們都做下面的事項
所以一樣是跟
我們上面的 transform 一樣
是有餘數的除法
X 除以 10
這個時候 number 你就要加
把 R 加進來
那 Q 可能還是很大
所以你就繼續要做下去
所以繼續要做下去
我們就將 X 更新為 Q
然後再回到上一層
我們的 X 就用 number 來替換
這個時候你就會考慮
它是不是可以提早結束
只要是 X 是小於 10
它如果小於 10
假設 K 很大的話
後面也不用做了
再怎麼做它還是那個 number
所以呢
我們最後的答案應該就是 number
那我們執行一次
所以這個 code 說簡單也不是很簡單
它其實不小心的話是很容易錯誤的
那我們掃密看看
好
那原則上
還好 34 毫秒
那我們看一下它其他的程式語言
因為我們一開始是用 C++ 的
這邊我們是有加上一些
所謂的輸出
加上這兩個 test case
那我們讓它整個執行一次
所以這邊我們就可以看到
有步驟的會比較容易看
像剛剛講的第一個 case
當然答案就是 36
因為 K 等於 1 所以要做一次
我們看第二個 case
所謂的 leak code
它要做兩次
33
第三個 case
它也是要做兩次
第一次是 17
然後再來是 1 加 7 等於 8
我們再看第四個 case
它這個 K 等於 1
直接就是變成 79
比較有意思的是這個
這個我們特別去照
它的長度就剛好是 100
case 等於 5
但是它會提早結束
所以當它 K 等於 3 的時候
它就是 1 了嘛
你後面當然可以繼續做
但是後面做出來也都是 1
所以這個可以提早結束
好
那我們就先談到這裡
謝謝
