力扣 217. 存在重复元素，389. 找不同，705. 设计哈希集合，3. 无重复字符的最长子串，139. 单词拆分

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()];
   }
};

原文地址：https://blog.csdn.net/2302_80423900/article/details/140534576

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！