代码随想录算法训练营第六天（一）|242.有效的字母异位词

LeetCode 242 有效的字母异位词

题目：

给定两个字符串 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 仅包含小写字母

思路：

首先需要理解字母异位词的含义，简单理解为：两字符串的长度相同，字母相同，但顺序不同。
字母异位词简意为两字符串长度相同，字母相同，顺序不同。如果是异位词那么输出true，否则就输出false。

首先我的想法是：第一步判断两个字符串的长度是否相等，其次，分别统计每一个字母出现的次数，在进行比较。如果都一样，那么输出true，否则false。

既然提示说，只会出现小写字母，那我们不妨用一个大小为27的数组来统计对应的字母出现的次数，已知小写英文字母的ASCII范围为97-122，那么分别对应1-26的下标数组。

初始化这个数组全为0，当第一个统计第一个字符串的时候，我们采用自增，统计第二个字符串的时候，我们采用自减。是异位词的话，那么说明它最后会回到初始状态，如果出现其他情况，比如-1，或者加和不为0，那么false。

上代码！

class Solution {
public:bool isAnagram(string s, string t) {int nums = s.size();int numt = t.size();if (nums != numt) {return false;}int a[27] = { 0 };for (int i = 0; i < nums; i++) {a[s[i] - 97]++;}for (int i = 0; i < numt; i++) {a[t[i] - 97]--;}int sum = 0;for (int i = 0; i < 27; i++) {sum += a[i];if (a[i] < 0) {return false;}else if (sum != 0) {return false;}}return true;}
};

这代码，够垃圾，也够直接！

​

---

LeetCode 349 两个数组的交集

题目：

给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

思路：

首先，题目要求我们交到两个数组的交集部分，并且返回交集的元素只能是唯一的，就是不重复的意思。

那么我们第一步应该先把两个数组中相同的部分找出来，然后再进行一次遍历，删除相同元素就可以返回结果了。

具体怎么做呢？

用数组a记录数组nums1中每个元素出现的次数，再统计数组nums2每一项出现的次数，做好标记，输出交集即可。

上代码！

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {int len1 = nums1.size();int len2 = nums2.size();int a[10] = { 0 };int b[10] = { 0 };for (int i = 0; i < len1; i++) {a[nums1[i]]++;}for (int i = 0; i < len2; i++) {if (a[nums2[i]] != 0) { b[nums2[i]] = 1;}}vector<int> ss;for (int i = 0; i < 10; i++) {if (b[i] != 0) {ss.push_back(i);//由于是容器的返回，用push_back传值}}return ss;}
};

你以为这就完了吗，LeetCode真恶心，你告诉我这是个什么东西。

改呗，还能怎么办！

好好好，加到1000还不够，是我保守了。

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {int len1 = nums1.size();int len2 = nums2.size();int a[9999] = { 0 };int b[9999] = { 0 };for (int i = 0; i < len1; i++) {a[nums1[i]]++;}for (int i = 0; i < len2; i++) {if (a[nums2[i]] != 0) { b[nums2[i]] = 1;}}vector<int> ss;for (int i = 0; i < 9999; i++) {if (b[i] != 0) {ss.push_back(i);//由于是容器的返回，用push_back传值}}return ss;}
};