[数据结构与算法]LeetCode（数据结构入门题单——字符串部分）

怎么又水了一天啊，打FIFA打的我眼睛好晕。。。

明天还是得学习，学习，还tmd是学习

又爱上了口香糖

字符串：6天

感觉入门篇主要是对stringSTL的使用，没有什么太复杂的地方

毕竟也就仨题

目录

387. 字符串中的第一个唯一字符

383. 赎金信

242. 有效的字母异位词

387. 字符串中的第一个唯一字符

难度简单562收藏分享切换为英文接收动态反馈

给定一个字符串?s?，找到?它的第一个不重复的字符，并返回它的索引?。如果不存在，则返回?-1?。

示例 1：

输入: s = "leetcode"
输出: 0

示例 2:

输入: s = "loveleetcode"
输出: 2

示例 3:

输入: s = "aabb"
输出: -1

提示:

• 1 <= s.length <= 105
• s?只包含小写字母

统计次数，不重复，一下子就能想到又要用哈希表了（用数组自己维护一个哈希也行c-'a'），使用unordered_map；将字母作first，出现频率作second即可，两次遍历。

class Solution {
public:
    int firstUniqChar(string s) 
	{
		unordered_map<int,int>frequen;
		for(char	ch:s)
		{
			++frequen[ch];
		}
		for(int	i=0;i<s.size();i++) 
		{
			if(frequen[s[i]]==1)
				return	i;
		}
		return	-1;
    }
};

383. 赎金信

难度简单363收藏分享切换为英文接收动态反馈

给你两个字符串：ransomNote?和?magazine?，判断?ransomNote?能不能由?magazine?里面的字符构成。

如果可以，返回?true?；否则返回?false?。

magazine?中的每个字符只能在?ransomNote?中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote?和?magazine?由小写英文字母组成

再用哈希表即可，跟上一题原理相同，但发现如使用数组自己维护哈希要比使用unordered_map快一倍。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) 
    {
  		if(ransomNote.size()>magazine.size())
			return	false;
		unordered_map<int,int>frequen;
		for(char	c:magazine)
		{
			frequen[c]++;	
		}	      
		for(char	c:ransomNote)
		{
			frequen[c]--;
			if(frequen[c]<0)
			{
				return	false;
			}
		}
		return	true;
    }
};

242. 有效的字母异位词

难度简单612收藏分享切换为英文接收动态反馈

给定两个字符串?s?和?t?，编写一个函数来判断?t?是否是?s?的字母异位词。

注意：若?s?和?t?中每个字符出现的次数都相同，则称?s?和?t?互为字母异位词。

示例?1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

• 1 <= s.length, t.length <= 5 * 104
• s?和?t?仅包含小写字母

进阶:?如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

?一手hash直接解决，这仨题都一样哈

当然sort直接走人我也没什么意见

class Solution {
public:
    bool isAnagram(string s, string t) 
    {
        if(s.length()!=t.length())
            return  false;
        unordered_map<int,int>frequen;
        for(char    c:s)
        {
            frequen[c]++;
        }
        for(char    c:t)
        {
            frequen[c]--;
            if(frequen[c]<0)
                return  false;
        }
        return  true;
    }
};

这仨题就是unordered_map应用... ...