安徽住房和城乡建设部网站百度小程序seo

217. 存在重复元素

题目

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

AC代码

class Solution {
public:bool containsDuplicate(vector<int>& nums) {// 利用 set 容器的唯一性，与原数组长度比较return set<int>(nums.begin(),nums.end()).size()!=nums.size();}
};

389. 找不同

题目

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

AC代码

class Solution {
public:char findTheDifference(string s, string t) {int vs[26]={0},vt[26]={0}; // 哈希表存，两段字符串字符出现的次数for(int i=0;i<t.size();i++){if(i<s.size())vs[s[i]-'a']++;vt[t[i]-'a']++;}char ans;for(int i=0;i<26;i++){if(vt[i]!=vs[i])// 比较两段字符串中不同的字符次数{ans=(char)(i+'a');break;}}return ans;}
};

705. 设计哈希集合

题目

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

AC代码

class MyHashSet {public:int v[1000010];MyHashSet() {memset(v,0,sizeof(v));// 初始化 哈希表 }void add(int key) {v[key]=1;	//添加标记}void remove(int key) {v[key]=0; //删除标记}bool contains(int key) {return v[key]==1; //判断是否标记}
};/*** Your MyHashSet object will be instantiated and called as such:* MyHashSet* obj = new MyHashSet();* obj->add(key);* obj->remove(key);* bool param_3 = obj->contains(key);*/

3. 无重复字符的最长子串

题目

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串的长度。

AC代码

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char,int>mp; // 用来标记重复出现的字符int res=0;for(int i=0,j=0;i<s.size();i++){mp[s[i]]++; // 出现标记while(mp[s[i]]>1)mp[s[j++]]--; // 去除重复字符res=max(res,i-j+1);}return res;}
};

139. 单词拆分

题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

AC代码

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> ne(wordDict.begin(),wordDict.end());// 存储字典，便于查找vector<bool>dp(s.size()+1,false); // 初始化状态dp[0]=true;for(int i=1;i<=s.size();i++){for(int j=0;j<i;j++){string w=s.substr(j,i-j);if(ne.find(w)!=ne.end()&&dp[j]) dp[i]=true; // 更新 该点位dp}}return dp[s.size()];}
};