1941. Check if All Characters Have Equal Number of Occurrenc

閱讀時間約 2 分鐘


英文版點我中文版點我


↑看個小廣告,支持好內容↑



❶ Hash Table (索引、桶子)

所有字符必須出現一樣多次,有關計數的任務,就交給索引吧!先遍歷字串 s 做統計,再檢查索引共有幾種值,時間花費 O(2n)

小寫字母就 26 個,因此索引頂多就 26 個 key,空間複雜度 O(26)→O(1)。由於關注的是計數頻率,我們也可開一個長度 26 的陣列 (我習慣稱它桶子),結果會相同:


// s="abacbc"

1. 索引
- 計數結果:map[a]=2, map[b]=2, map[c]=2
- 頻率陣列:Object.values(map) // [2,2,2]

2. 桶子
- 計數結果:arr[0]=2, arr[1]=2, arr[2]=2
- 頻率陣列:arr.filter(x=>x>0) //​ [2,2,2]


次數必須一致,轉成集合檢查 new Set(頻率陣列).size=1 就行了。


❷ Follow-Up: Counting

雖然這題很好 pass,但我蠻好奇有沒有不靠索引的解法 XD

假設把字串排成 aabbcc,當一看到 b 就能肯定 a 出現完畢,再來結算其頻率是否有重複,邏輯上似乎說得通:

// 假設s已依字母順序排好

var areOccurrencesEqual = function(s) {
let freq=0, curr=1;

for(let i=1; i<s.length; i++){
if(s[i]==s[i-1]){
curr++;
}else{
// 以首個字母的次數作為基準
if(freq==0){freq=curr);
// 若出現頻率與基準值不同 => false
if(freq!=curr){return false};
curr=1;
}
}
// 檢查最後一個字母,並排除單一字母的狀況
return freq==curr || freq==0;
};


撇除掉排列字母,這樣只要跑一次迴圈就能完成,有沒有挺像之前按計數器的感覺呢?遵循相似的思維,這題確實也能用雙指針來解沒錯!今天篇幅夠了,就當回家作業吧 (X



  • 本題分類標籤:Hash TableStringCounting
  • 本題正解率=77.0%

❤️ 若內容對你實用,歡迎追蹤本專題,或小額贊助支持~
⭐ 這是我的第 16 篇刷題筆記,完整解題索引看這裡 → Here

54會員
59內容數
我要成為 LeetCode 王!快跟我一起踏上旅程!
留言0
查看全部
發表第一個留言支持創作者!
LeetCode King 的其他內容
究竟誰是 i、誰又是 j?矩陣問題務必趁腦子清楚時才解 XDD
總是記不順雙指針法的程序?畫圖跑一次給你看!
題目到底要我們做什麼?閱讀素養有多重要,試試這題就知道!
老是從頭重算可不是好法子,把加過的累積值存起來備用,這才符合 Prefix Sum 的精神!
三種做法所花的時間都不同,請試著一步步優化,在只跑一次迴圈下完成吧!
你聽過 "LIFO" 嗎?搞不好在解這題時你已經不知不覺用到它了喔 XD
究竟誰是 i、誰又是 j?矩陣問題務必趁腦子清楚時才解 XDD
總是記不順雙指針法的程序?畫圖跑一次給你看!
題目到底要我們做什麼?閱讀素養有多重要,試試這題就知道!
老是從頭重算可不是好法子,把加過的累積值存起來備用,這才符合 Prefix Sum 的精神!
三種做法所花的時間都不同,請試著一步步優化,在只跑一次迴圈下完成吧!
你聽過 "LIFO" 嗎?搞不好在解這題時你已經不知不覺用到它了喔 XD
你可能也想看
Google News 追蹤
Thumbnail
本專欄將提供給您最新的市場資訊、產業研究、交易心法、精選公司介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.cc/VNYVxZ 每月 $99 訂閱方案👉https://re
Thumbnail
女孩們對於婚禮一定有個專屬的美麗憧憬,不管浪漫、感人、搞笑的,這是要花時間準備的人生課程。即將踏入婚禮的你們是不是也開始煩惱該如何準備夢想中的婚禮呢?嘴上說不緊張,內心卻開始默默煩惱總覺得有些事情沒準備好?就讓你的婚禮好朋友-OKOH陪著你們一起CHECK IT!
Thumbnail
聖誕夜的前一天,也是忙碌的一天。早上到學校check off (skill test),然後下午會有一堆朋友來家裡party。 我參加的這個nursing program有三種形式:在家視訊上課以及考試; 到學校練習hangs on的技能以及考試,這樣的考試我們稱為check off; 以及到醫院實
Thumbnail
二十世紀中葉,全球爆發了毀滅性的戰役,能夠贏下戰爭的關鍵並非武力,而是『情報』。 『我們每天都會攔截到數千則敵人的加密電報,如果無法破譯,那這些情報終究只是戰場上的噪音;反之,若能了解編碼的規則便能扭轉戰局。』 於是,盟軍派遣數批詐降士兵進入戰俘營執行機密任務: 《竊取敵軍情報編碼規則,並逃出
1941~1944年天王星進入雙子,與海王星處女尾天秤頭三分,與冥王獅子形成一個風火小三角格局,能量關鍵是水瓶頭。接下來近百年,天海冥的關係從天王星三分海王星、四分海王星,1960年代追上冥王星處女,然後1990年代追上海王星摩羯,2010年代天王白羊四分冥王星摩羯,到2026天王雙子冥王水瓶三分,
It’s a vast industry; for each of the devices, pricing, functions, software/hardware spec all vary a lot.
Thumbnail
我痛恨著戰爭。但同時,卻不得不感謝它。因為如果沒有戰爭的話……如果我一直都只是一個屬於先生的無名城市的話,我大概就不會如此實在地存在於世上,遇上了你──義呆利同人,清水,米英香,1941.12.24 - 1945.9.02。沒有 CP 向的米英香。歷史向。
Thumbnail
【何日 #重光】 【#當年今日】1941年 #12月25日 香港守軍血戰十八日(#12月8日 至25日),彈盡援絕;英王 #佐治六世 及首相 #邱吉爾 雖先後呼籲 #英聯邦軍 抗敵到底,但港督 #楊慕
Thumbnail
當我期待的那個詩的盛世不知不覺就已經來了。如何從頭到尾的,作為一個小人物樂天知命地一直寫下去。
Thumbnail
本專欄將提供給您最新的市場資訊、產業研究、交易心法、精選公司介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.cc/VNYVxZ 每月 $99 訂閱方案👉https://re
Thumbnail
女孩們對於婚禮一定有個專屬的美麗憧憬,不管浪漫、感人、搞笑的,這是要花時間準備的人生課程。即將踏入婚禮的你們是不是也開始煩惱該如何準備夢想中的婚禮呢?嘴上說不緊張,內心卻開始默默煩惱總覺得有些事情沒準備好?就讓你的婚禮好朋友-OKOH陪著你們一起CHECK IT!
Thumbnail
聖誕夜的前一天,也是忙碌的一天。早上到學校check off (skill test),然後下午會有一堆朋友來家裡party。 我參加的這個nursing program有三種形式:在家視訊上課以及考試; 到學校練習hangs on的技能以及考試,這樣的考試我們稱為check off; 以及到醫院實
Thumbnail
二十世紀中葉,全球爆發了毀滅性的戰役,能夠贏下戰爭的關鍵並非武力,而是『情報』。 『我們每天都會攔截到數千則敵人的加密電報,如果無法破譯,那這些情報終究只是戰場上的噪音;反之,若能了解編碼的規則便能扭轉戰局。』 於是,盟軍派遣數批詐降士兵進入戰俘營執行機密任務: 《竊取敵軍情報編碼規則,並逃出
1941~1944年天王星進入雙子,與海王星處女尾天秤頭三分,與冥王獅子形成一個風火小三角格局,能量關鍵是水瓶頭。接下來近百年,天海冥的關係從天王星三分海王星、四分海王星,1960年代追上冥王星處女,然後1990年代追上海王星摩羯,2010年代天王白羊四分冥王星摩羯,到2026天王雙子冥王水瓶三分,
It’s a vast industry; for each of the devices, pricing, functions, software/hardware spec all vary a lot.
Thumbnail
我痛恨著戰爭。但同時,卻不得不感謝它。因為如果沒有戰爭的話……如果我一直都只是一個屬於先生的無名城市的話,我大概就不會如此實在地存在於世上,遇上了你──義呆利同人,清水,米英香,1941.12.24 - 1945.9.02。沒有 CP 向的米英香。歷史向。
Thumbnail
【何日 #重光】 【#當年今日】1941年 #12月25日 香港守軍血戰十八日(#12月8日 至25日),彈盡援絕;英王 #佐治六世 及首相 #邱吉爾 雖先後呼籲 #英聯邦軍 抗敵到底,但港督 #楊慕
Thumbnail
當我期待的那個詩的盛世不知不覺就已經來了。如何從頭到尾的,作為一個小人物樂天知命地一直寫下去。