数组作为哈希表-leetcode 763、leetcode 1002

今天的每日一题Leetcode 763-划分字母区间用到了用数组存储的哈希表，index为小写字母的序号（ch-‘a’)，value为最后出现的位置 题目描述

思路： 初始化区间下界start、上界end均为0。遍历整个字符串，根据每个字母出现的位置更新上界end，因为要保证只有当前区间有这个字符，所以上界end要取max(end, last[S[i]-'a'])

代码如下：

class Solution { public: vector<int> partitionLabels(string S) { vector<int> last(26,-1); for(int i=0;i<S.size();i++) last[S[i]-'a']=i; vector<int> partition; int start=0,end=0; for(int i=0;i<S.size();i++){ end=max(end,last[S[i]-'a']); if(end==i){ partition.push_back(end-start+1); start=end+1; } } return partition; } };

这道题用数组存储哈希表的思路类似于Leetcode 1002-查找常用字符，题目如下： 思路如下： ①数组作为哈希表，26位，存每个字母出现的次数； index: 字母 - ‘a’，value: 字母出现的次数

vector<int> hash_first(26,0); for(auto it:A[0]) hash_first[it-'a']++;

②hash_first 第1个存第一个字符串的每个字母次数； hash_mov 第2个依次遍历，并每次和hash_first 比较求26位每一位最小值

vector<int> hash_mov(26,0); for(int i=1;i<A.size();i++){ for(auto it:A[i]) hash_mov[it-'a']++; for(int j=0;j<26;j++) hash_first[j]=min(hash_first[j],hash_mov[j]); for(int k=0;k<26;k++) hash_mov[k]=0; }

这里借用一下“代码随想录”的题解图，清晰易懂，大家可以去他的微信公众号关注一下、去代码随想录的GitHub 🌟一下～ 完整代码如下：

class Solution { public: vector<string> commonChars(vector<string>& A) { vector<string> res; vector<int> hash_first(26,0); vector<int> hash_mov(26,0); for(auto it:A[0]) hash_first[it-'a']++; for(int i=1;i<A.size();i++){ for(auto it:A[i]) hash_mov[it-'a']++; for(int j=0;j<26;j++) hash_first[j]=min(hash_first[j],hash_mov[j]); for(int k=0;k<26;k++) hash_mov[k]=0; } for(int i=0;i<26;i++) if(hash_first[i]!=0){ int cnt=hash_first[i]; while(cnt--) res.push_back(string(1,i+'a')); } return res; } };

注意⚠️： auto it只能读、不能改 比如每次用完hash_mov移到下一个之前，把hash_mov中26个值全部设为0，不能用auto it，还是用index访问修改吧。 ①错误代码：

for(auto it:hash_mov) it=0;

②正确的代码：

for(int k=0;k<26;k++) hash_mov[k]=0;