2023-08-20：用go語言寫算法。給定一個(gè)由'W'、'A'、'S'、'D'四種字符組成的字符串，長
2023-08-20：用go語言寫算法。給定一個(gè)由'W'、'A'、'S'、'D'四種字符組成的字符串，長度一定是4的倍數(shù)，
你可以把任意連續(xù)的一段子串，變成'W'、'A'、'S'、'D'組成的隨意狀態(tài)，
目的是讓4種字符詞頻一樣。
返回需要修改的最短子串長度。
完美走位問題。
輸入：s = "QQQW"。
輸出：2。
解釋：我們可以把前面的 "QQ" 替換成 "ER"。
來自華為OD。
來自左程云。
答案2023-08-20：
算法步驟：
1.定義輔助函數(shù)ok()，用于判斷當(dāng)前字符詞頻是否能使四種字符的詞頻相同。
2.初始化數(shù)組arr保存每個(gè)字符的對(duì)應(yīng)值（'Q': 0, 'W': 1, 'E': 2, 'R': 3）和數(shù)組cnts記錄每個(gè)字符的詞頻。
3.使用雙指針來搜索每個(gè)可能的子串。外層循環(huán)控制左指針，內(nèi)層循環(huán)控制右指針。
4.當(dāng)當(dāng)前子串不滿足要求時(shí)，右指針向右移動(dòng)并更新詞頻數(shù)組cnts，直到子串滿足要求。
5.當(dāng)子串滿足要求時(shí)，更新當(dāng)前最短子串長度。
6.左指針向右移動(dòng)并更新詞頻數(shù)組，繼續(xù)搜索可能的子串。
7.返回最短子串長度。
總的時(shí)間復(fù)雜度為O(n)，其中n是字符串的長度。
總的額外空間復(fù)雜度為O(1)，因?yàn)橹皇褂昧斯潭ù笮〉臄?shù)組和常數(shù)個(gè)變量。
go完整代碼如下：
package?main
import?"fmt"
func?balancedString(s?string)?int?{
????n?:=?len(s)
????arr?:=?make([]int,?n)
????cnts?:=?make([]int,?4)
????for?i?:=?0;?i?<?n;?i++?{
????????switch?s[i]?{
????????case?'Q':
????????????arr[i]?=?0
????????case?'W':
????????????arr[i]?=?1
????????case?'E':
????????????arr[i]?=?2
????????case?'R':
????????????arr[i]?=?3
????????}
????????cnts[arr[i]]++
????}
????ans?:=?n
????for?l,?r?:=?0,?0;?l?<?n;?l++?{
????????for?!ok(cnts,?l,?r)?&&?r?<?n?{
????????????cnts[arr[r]]--
????????????r++
????????}
????????if?ok(cnts,?l,?r)?{
????????????ans?=?min(ans,?r-l)
????????}?else?{
????????????break
????????}
????????cnts[arr[l]]++
????}
????return?ans
}
func?ok(cnts?[]int,?l?int,?r?int)?bool?{
????maxCnt?:=?max(max(max(cnts[0],?cnts[1]),?cnts[2]),?cnts[3])
????changes?:=?maxCnt*4?-?cnts[0]?-?cnts[1]?-?cnts[2]?-?cnts[3]
????rest?:=?r?-?l?-?changes
????return?rest?>=?0?&&?rest%4?==?0
}
func?min(a,?b?int)?int?{
????if?a?<?b?{
????????return?a
????}
????return?b
}
func?max(a,?b?int)?int?{
????if?a?>?b?{
????????return?a
????}
????return?b
}
func?main()?{
????s?:=?"QQQW"
????result?:=?balancedString(s)
????fmt.Println(result)
}
rust完整代碼如下：
fn?balanced_string(s:?&str)?->?i32?{
????let?n?=?s.len()?as?i32;
????let?mut?arr?=?Vec::with_capacity(n?as?usize);
????let?mut?cnts?=?vec![0;?4];
????for?c?in?s.chars()?{
????????let?val?=?match?c?{
????????????'W'?=>?1,
????????????'E'?=>?2,
????????????'R'?=>?3,
????????????_?=>?0,
????????};
????????arr.push(val);
????????cnts[val]?+=?1;
????}
????let?mut?ans?=?n;
????for?l?in?0..n?{
????????let?mut?r?=?l;
????????while?!ok(&cnts,?l,?r)?&&?r?<?n?{
????????????cnts[arr[r?as?usize]?as?usize]?-=?1;
????????????r?+=?1;
????????}
????????if?ok(&cnts,?l,?r)?{
????????????ans?=?ans.min(r?-?l);
????????}?else?{
????????????break;
????????}
????????cnts[arr[l?as?usize]?as?usize]?+=?1;
????}
????ans
}
fn?ok(cnts:?&[i32],?l:?i32,?r:?i32)?->?bool?{
????let?max_cnt?=?cnts.iter().max().copied().unwrap_or(0);
????let?changes?=?max_cnt?*?4?-?cnts[0]?-?cnts[1]?-?cnts[2]?-?cnts[3];
????let?rest?=?r?-?l?-?changes;
????rest?>=?0?&&?rest?%?4?==?0
}
fn?main()?{
????let?s?=?"QQQW";
????let?result?=?balanced_string(s);
????println!("{}",?result);
}
c++完整代碼如下：
bool?ok(const?std::vector<int>&?cnts,?int?l,?int?r);
int?balancedString(const?std::string&?str)?{
????int?n?=?str.size();
????std::vector<int>?arr(n);
????std::vector<int>?cnts(4);
????for?(int?i?=?0;?i?<?n;?i++)?{
????????char?c?=?str[i];
????????arr[i]?=?(c?==?'W'???1?:?(c?==?'E'???2?:?(c?==?'R'???3?:?0)));
????????cnts[arr[i]]++;
????}
????int?ans?=?n;
????for?(int?l?=?0,?r?=?0;?l?<?n;?l++)?{
????????while?(!ok(cnts,?l,?r)?&&?r?<?n)?{
????????????cnts[arr[r++]]--;
????????}
????????if?(ok(cnts,?l,?r))?{
????????????ans?=?std::min(ans,?r?-?l);
????????}
????????else?{
????????????break;
????????}
????????cnts[arr[l]]++;
????}
????return?ans;
}
bool?ok(const?std::vector<int>&?cnts,?int?l,?int?r)?{
????int?maxCnt?=?std::max(std::max(cnts[0],?cnts[1]),?std::max(cnts[2],?cnts[3]));
????int?changes?=?maxCnt?*?4?-?cnts[0]?-?cnts[1]?-?cnts[2]?-?cnts[3];
????int?rest?=?r?-?l?-?changes;
????return?rest?>=?0?&&?rest?%?4?==?0;
}
int?main()?{
????std::string?s?=?"QQQW";
????int?result?=?balancedString(s);
????std::cout?<<?"Result:?"?<<?result?<<?std::endl;
????return?0;
}
c完整代碼如下：
int?balancedString(char*?s)?{
????int?n?=?strlen(s);
????int*?arr?=?(int*)malloc(sizeof(int)?*?n);
????int?cnts[4]?=?{?0?};
????for?(int?i?=?0;?i?<?n;?i++)?{
????????char?c?=?s[i];
????????arr[i]?=?c?==?'W'???1?:?(c?==?'E'???2?:?(c?==?'R'???3?:?0));
????????cnts[arr[i]]++;
????}
????int?ans?=?n;
????for?(int?l?=?0,?r?=?0;?l?<?n;?l++)?{
????????while?(!ok(cnts,?l,?r)?&&?r?<?n)?{
????????????cnts[arr[r++]]--;
????????}
????????if?(ok(cnts,?l,?r))?{
????????????ans?=?ans?<?r?-?l???ans?:?r?-?l;
????????}
????????else?{
????????????break;
????????}
????????cnts[arr[l]]++;
????}
????free(arr);
????return?ans;
}
int?ok(int*?cnts,?int?l,?int?r)?{
????int?maxCnt?=?cnts[0];
????for?(int?i?=?1;?i?<?4;?i++)?{
????????if?(cnts[i]?>?maxCnt)?{
????????????maxCnt?=?cnts[i];
????????}
????}
????int?changes?=?maxCnt?*?4?-?cnts[0]?-?cnts[1]?-?cnts[2]?-?cnts[3];
????int?rest?=?r?-?l?-?changes;
????return?rest?>=?0?&&?rest?%?4?==?0;
}
int?main()?{
????char?s[]?=?"QQQW";
????int?result?=?balancedString(s);
????printf("%d\n",?result);
????return?0;
}
