2023-05-08：我們定義了一個函數(shù) countUniqueChars(s) 來統(tǒng)計字符串 s 中的唯一字符，
2023-05-08：我們定義了一個函數(shù) countUniqueChars(s) 來統(tǒng)計字符串 s 中的唯一字符，
并返回唯一字符的個數(shù)。
例如：s = "LEETCODE" ，則其中 "L", "T","C","O","D" 都是唯一字符，
因為它們只出現(xiàn)一次，所以 countUniqueChars(s) = 5 。
本題將會給你一個字符串 s ，我們需要返回 countUniqueChars(t) 的總和，
其中 t 是 s 的子字符串。輸入用例保證返回值為 32 位整數(shù)。
注意，某些子字符串可能是重復(fù)的，但你統(tǒng)計時也必須算上這些重復(fù)的子字符串
（也就是說，你必須統(tǒng)計 s 的所有子字符串中的唯一字符）。
輸入: s = "ABC"。
輸出: 10。
答案2023-05-08：
1.定義函數(shù)?countUniqueChars(s)，參數(shù)為字符串?s，返回值為整數(shù)。
2.創(chuàng)建一個空的哈希表?indies?來記錄每個字符出現(xiàn)的位置。
3.遍歷字符串?s?中的每個字符，對于每個字符：
3.1.檢查該字符是否已經(jīng)在?indies?中出現(xiàn)過，如果沒有則將其加入哈希表，并將初始位置 -1 添加到其位置數(shù)組中。
3.2.將當前字符的位置添加到其位置數(shù)組中。
4.初始化計數(shù)器?res?為 0。
5.遍歷哈希表?indies?中的每個鍵值對，對于每個鍵值對：
5.1.在該鍵所對應(yīng)的位置數(shù)組的末尾添加字符串?s?的長度，方便后續(xù)計算。
5.2.遍歷該鍵所對應(yīng)的位置數(shù)組中除了開頭和結(jié)尾的位置，對于每組相鄰的位置 i 和 j，計算左側(cè)有多少個連續(xù)的該鍵字符和右側(cè)有多少個連續(xù)的該鍵字符，累加乘積到?res?中。
6.返回計數(shù)器?res。
注意：該題目要求統(tǒng)計所有子字符串中的唯一字符的數(shù)量，因此需要遍歷所有子串。具體實現(xiàn)方法可以枚舉所有子串，或者使用一個雙重循環(huán)來分別枚舉子串的起始位置和結(jié)束位置，時間復(fù)雜度為 O(n^3)，其中 n 是字符串?s?的長度。但由于該題目的數(shù)據(jù)范圍較小，因此可以使用暴力枚舉來實現(xiàn)。
時間復(fù)雜度：
遍歷字符串?s?的時間復(fù)雜度為 O(n)，其中 n 是字符串的長度。
遍歷哈希表?indies?中的每個位置數(shù)組的時間復(fù)雜度為 O(k)，其中 k 是該鍵對應(yīng)的字符在字符串?s?中出現(xiàn)的次數(shù)。
因此，整個程序的時間復(fù)雜度為 O(nk)。
額外空間復(fù)雜度：
哈希表?indies?和每個鍵所對應(yīng)的位置數(shù)組的空間復(fù)雜度都是 O(k)，其中 k 是該鍵對應(yīng)的字符在字符串?s?中出現(xiàn)的次數(shù)。因此，整個程序的額外空間復(fù)雜度為 O(nk)。
go完整代碼如下：
package?main
import?"fmt"
func?uniqueLetterString(s?string)?int?{
????//?key?:?某一種字符
????//?value?:?出現(xiàn)這種字符依次的位置
????indies?:=?make(map[byte][]int)
????for?i?:=?0;?i?<?len(s);?i++?{
????????c?:=?s[i]
????????if?_,?ok?:=?indies[c];?!ok?{
????????????indies[c]?=?[]int{-1}
????????}
????????indies[c]?=?append(indies[c],?i)
????}
????res?:=?0
????for?_,?arr?:=?range?indies?{
????????arr?=?append(arr,?len(s))
????????for?i?:=?1;?i?<?len(arr)-1;?i++?{
????????????res?+=?(arr[i]?-?arr[i-1])?*?(arr[i+1]?-?arr[i])
????????}
????}
????return?res
}
func?main()?{
????s?:=?"ABC"
????res?:=?uniqueLetterString(s)
????fmt.Println(res)
}
rust完整代碼如下：
use?std::collections::HashMap;
fn?unique_letter_string(s:?&str)?->?i32?{
????//?key?:?某一種字符
????//?value?:?出現(xiàn)這種字符依次的位置
????let?mut?indies:?HashMap<char,?Vec<i32>>?=?HashMap::new();
????for?(i,?c)?in?s.chars().enumerate()?{
????????indies.entry(c).or_insert_with(Vec::new).push(i?as?i32);
????}
????let?mut?res?=?0;
????for?(_,?arr)?in?indies.iter()?{
????????let?mut?arr?=?arr.clone();
????????arr.insert(0,?-1);
????????arr.push(s.len()?as?i32);
????????for?i?in?1..arr.len()?-?1?{
????????????res?+=?(arr[i]?-?arr[i?-?1])?*?(arr[i?+?1]?-?arr[i]);
????????}
????}
????res?as?i32
}
fn?main()?{
????let?s?=?"ABC";
????let?res?=?unique_letter_string(s);
????println!("{}",?res);
}
c完整代碼如下：
#include?<stdio.h>
#include?<stdlib.h>
#include?<string.h>
#define?MAX_N?1000
struct?Vector?{
????int?data[MAX_N];
????int?size;
};
void?vector_init(struct?Vector*?vec)?{
????memset(vec->data,?-1,?sizeof(vec->data));
????vec->data[0]?=?-1;
????vec->size?=?1;
}
void?vector_push_back(struct?Vector*?vec,?int?x)?{
????vec->data[vec->size++]?=?x;
}
int?uniqueLetterString(char*?s)?{
????//?key?:?某一種字符
????//?value?:?出現(xiàn)這種字符依次的位置
????struct?Vector?indies[256];
????int?cnt[256]?=?{?0?};
????for?(int?i?=?0;?s[i];?i++)?{
????????char?c?=?s[i];
????????if?(cnt[c]?==?0)?{
????????????vector_init(&indies[c]);
????????}
????????vector_push_back(&indies[c],?i);
????????cnt[c]++;
????}
????int?res?=?0;
????for?(int?c?=?0;?c?<?256;?c++)?{
????????if?(cnt[c]?==?0)?continue;
????????vector_push_back(&indies[c],?strlen(s));
????????for?(int?i?=?1;?i?<?indies[c].size?-?1;?i++)?{
????????????int?left?=?indies[c].data[i]?-?indies[c].data[i?-?1];
????????????int?right?=?indies[c].data[i?+?1]?-?indies[c].data[i];
????????????res?+=?left?*?right;
????????}
????}
????return?res;
}
int?main()?{
????char?s[]?=?"ABC";
????int?res?=?uniqueLetterString(s);
????printf("%d\n",?res);
????return?0;
}
c++完整代碼如下：
#include?<iostream>
#include?<vector>
#include?<unordered_map>
using?namespace?std;
int?uniqueLetterString(string?s)?{
????//?key?:?某一種字符
????//?value?:?出現(xiàn)這種字符依次的位置
????unordered_map<char,?vector<int>>?indies;
????for?(int?i?=?0;?i?<?s.length();?i++)?{
????????char?c?=?s[i];
????????if?(!indies.count(c))?{
????????????indies[c]?=?{?-1?};
????????}
????????indies[c].push_back(i);
????}
????int?res?=?0;
????for?(auto?entry?:?indies)?{
????????auto?arr?=?entry.second;
????????arr.push_back(s.length());
????????for?(int?i?=?1;?i?<?arr.size()?-?1;?i++)?{
????????????res?+=?(arr[i]?-?arr[i?-?1])?*?(arr[i?+?1]?-?arr[i]);
????????}
????}
????return?res;
}
int?main()?{
????string?s?=?"ABC";
????int?res?=?uniqueLetterString(s);
????cout?<<?res?<<?endl;
????return?0;
}
福大大架構(gòu)師每日一題
java當死，golang當立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡(luò)，操作系統(tǒng)。
公眾號
