?前言?
在這個系列中，博主準備分享每日在萬人千題社區打卡學習的演算法，博主也是小白，因此也很能理解新手在刷題時的困惑，所以關注博主，每天學習一道演算法吧，同時也歡迎大家加入萬人千題習活動，正所謂：一個人可以走的很快，但一群人才能走的更遠，
萬人千題打卡社區
https://bbs.csdn.net/forums/hero?category=0&typeId=17913
目錄
一、演算法思想筆記
二、唯一元素的和 ?
三、字串中唯一字符 ?
四、大餐問題 ??
五、課后作業
一、演算法思想筆記
我們知道，通過for回圈，可以用一個計數變數計數出某個數出現多少次，那么如何反應一組數的資料分布呢？桶計數就是我們可以嘗試的方法，（和博主高中學的桶排序很像，就用桶的方式為大家演示）
現假設有一組資料的范圍在0~5，我們開辟5個“桶”，與每個數一一對應，來對其計數，什么意思呢，我們畫個圖來理解，
其實很簡單，在我們遍歷陣列的程序中，將數字“對號入座”即可，cnt[i]只存放數值為i的數的個數
有了基礎的知識我們就可以開始刷題了
二、唯一元素的和 ?
1748. 唯一元素的和https://leetcode-cn.com/problems/sum-of-unique-elements/https://leetcode-cn.com/problems/sum-of-unique-elements/①問題呈現
②代碼操練
int sumOfUnique(int* nums, int numsSize)
{
int i=0;
int sum=0;
int cnt[101];//（1）
memset(cnt, 0, sizeof(cnt));//(2)
for(i=0;i<numsSize;i++)
{
cnt[nums[i]]++;//(3)
}
for(i=0;i<101;i++)
{
if(cnt[i]==1)
{
sum+=i;//(4)
}
}
return sum;
}③分析
1.要開辟101個桶，考慮到陣列下標從0開始
2.用memset函式為計數陣列的每一個“桶”初始值賦為0
3.數字“對號入座”，進行計數
4.根據題目要求只相交滿足要求的“桶”
三、字串中唯一字符 ?
387. 字串中的第一個唯一字符https://leetcode-cn.com/problems/first-unique-character-in-a-string/https://leetcode-cn.com/problems/first-unique-character-in-a-string/
①題目呈現
②代碼操練
int firstUniqChar(char * s)
{
int i=0;
int size=strlen(s);
int cnt[27];
memset(cnt,0,sizeof(cnt));
for(i=0;i<size;i++)
{
cnt[s[i]-96]++;
}
for(i=0;i<size;i++)
{
if(cnt[s[i]-96]==1)
return i;
}
return -1;
}③分析
這道題目的思想和上一道題目完全一致，這里不再贅述，
四、大餐問題 ??
1711. 大餐計數https://leetcode-cn.com/problems/count-good-meals/https://leetcode-cn.com/problems/count-good-meals/
① 題目呈現
②思路點撥
③代碼操練
int countPairs(int* deliciousness, int deliciousnessSize)
{
int i=0;
int sum=0;
int other =0;
int cnt[1<<21+1];//(1)
int ans=0;
memset(cnt, 0, sizeof(cnt));//(2)
for(i = 0;i < deliciousnessSize;i++)//(3)
{
for(sum = 1;sum <= (1<<21) ;sum *= 2)//(4)
{
other= sum- deliciousness[i];//(5)
if (other < 0)
{
continue;
}
ans += cnt[other];
ans %= 1000000007;//(6)
}
cnt[deliciousness[i]]++;(7)
}
return ans;
}
思想：
由于題目規定每一道菜都不一樣，所以我們需要桶計數出，這道菜對應各種可能的sum，分別所需要的other有多少個，所以我們的基本思想是用桶記錄各種other有多少個，
解釋：
1.考慮到other最大為2^21-1,所以cnt創建的大小應該為[(1 << 21) + 1]而不是(1 << 20) + 1]
2.為每個桶初始化內容為0
3.遍歷每一道菜
4.遍歷每一種sum
5.判斷other是否存在
6.根據題目要求需要取余
五、課后作業
1941. 檢查是否所有字符出現次數相同?https://leetcode-cn.com/problems/check-if-all-characters-have-equal-number-of-occurrences/https://leetcode-cn.com/problems/check-if-all-characters-have-equal-number-of-occurrences/448. 找到所有陣列中消失的數字?https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/1512. 好數對的數目??https://leetcode-cn.com/problems/number-of-good-pairs/https://leetcode-cn.com/problems/number-of-good-pairs/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/339061.html
標籤：其他
上一篇：二叉樹的中序遍歷
下一篇：JS原生雙欄穿梭選擇框