Re: [閒聊] 每日LeetCode
看板Marginalman作者Neuenmuller (蘇菲・諾伊恩謬拉)時間6月前 (2023/11/09 08:58)推噓0(1推 1噓 0→)留言2則, 2人參與討論串499/719 (看更多)
1759. Count Number of Homogenous Substrings
找相同字元的substring 數各種substring總共出現多少次
ex: input = "aabbbca"
"a": 3
"aa": 1
"b": 3
"bb": 2
"bbb": 1
"c": 1
總共 11
# 思路:
因為數總和就好了，所以不需要額外空間去存各種substr各有幾種。
然後稍微觀察一下如果遍歷一次input能不能解。
另外拿個範例，假設input是"aaa":
當我遍歷到第二個a的時候可以找到homogenous substr "aa"
但同時第二個a單獨自己也是一個homogenous substr，所以sum + 2
以此類推，我遍歷第三個a的時候，同時有"a" "aa" "aaa"三種homogenous substr。
那要解起來就很簡單了，我紀錄上個遍歷到的字元
還有紀錄這個字元我目前連續遇到幾個 叫做cur好了
這樣只要下一個字元還是一樣的，那我sum就只需要加上cur就行
遍歷到不一樣的字元就重設
# 解:
以下Rust，不過老實說跟我寫的C++版本八成像
484有啥酷炫的招式可以做到一樣的事啊？
impl Solution {
pub fn count_homogenous(s: String) -> i32 {
let (mut output, mut cur) = (0, 0);
let mut last: char = '\0';
for c in s.chars() {
if c != last {
last = c;
cur = 1;
}
else {
cur += 1;
}
output += cur;
output %= 1_000_000_007;
}
output
}
}
o('_>')o
--
neuenmuller@atelier:home$ touch plachta
touch: cannot touch 'plachta': Permission denied
neuenmuller@atelier:home$ sudo touch plachta
[sudo] password for neuenmuller:
neuenmuller is not in the sudoers file. This incident will be reported.
neuenmuller@atelier:home$
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 97.99.29.95 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699491525.A.327.html
推
11/09 09:00,
6月前
, 1F
11/09 09:00, 1F
※ 編輯: Neuenmuller (97.99.29.95 美國), 11/09/2023 09:05:41
噓
11/09 09:05,
6月前
, 2F
11/09 09:05, 2F
討論串 (同標題文章)