代码随想录算法训练营第六天|LeetCode 242. 有效的字母异位词 、349. 两个数组的交集 、 202. 快乐数、1. 两数之和

LeetCode 242. 有效的字母异位词

题目链接：242. 有效的字母异位词

方法一：

分析：

两个字符串里的每个字母的个数相等，那么我对每个字符串里的字符串都进行下排序，排出来后岂不是两个字符串的每个字母如果一一对应就会返回true，否则返回false。此方法比较巧妙，只需排序后直接对比两个数组即可，不需要使用暴力求解，都是单层的。

思路：

1、创建两个容器，遍历分别把两个字符串都放进去

2、用sort函数进行排序

3、直接比较即可

class Solution {
public:
    bool isAnagram(string s, string t) {
        vector<int> v1;
        vector<int> v2;
        for(int i = 0;i < s.size(); i++){
            v1.push_back(s[i]);
        }
        for(int i = 0;i < t.size(); i++){
            v2.push_back(t[i]);
        }
        sort(v1.begin(),v1.end());
        sort(v2.begin(),v2.end());
        if (v1 == v2){
            return true;
        }
        else{
            return false;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二：

分析：

此题可以使用哈希表方法，创建一个相对大小的数组，然后对第一个字符串的每个字母相对位置进行++操作，再对第二个字符串每个相对位置–操作，最后判断下这个数组是否都是0元素即可。

思路：

1、创建一个空间大小为26的数组

2、首先将第一个字符串的每个字母的相对位置进行++

3、然后将第二个字符转的每个字母的相对位置进行–

4、判断这个数组中的每个位置是否为空，不为空返回false，为空返回true

class Solution {
public:
    bool isAnagram(string s, string t) {
        int fu_zhu [26] = {};
        for (int i = 0; i < s.size(); i++) {
            fu_zhu[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            fu_zhu[t[i] -'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (fu_zhu[i] != 0) {
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode 349. 两个数组的交集

题目链接：349. 两个数组的交集

方法一（1）：

分析：

对nums1和nums2暴力搜索出相同的元素，最后想办法输出每个元素都是唯一的即可，这里输出唯一的想法是多创建了个容器。

思路：

1、创建两个容器v和t

2、对nums1和nums2暴力搜索出相同的元素，都插入到v容器中

3、对v容器进行排序

4、排序完把每个唯一的数插入到t容器中，然后返回t即可

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> v;
        vector<int> t;
        for (int i = 0; i < nums1.size(); i++) {
            for (int j = 0; j < nums2.size(); j++){
                if (nums2[j] == nums1[i]) {
                    v.push_back(nums1[i]);
                }
            }
        }
        sort(v.begin(),v.end());
        if (v.size() <= 1) {
            return v;
        }
        else {
            t.push_back(v[0]);
            for (int i = 1; i < v.size(); i++) {
                if (v[i] != v[i - 1]) {
                    t.push_back(v[i]);
                }
            }
            return t;
        }

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

方法一（2）：

分析：

对nums1和nums2暴力搜索出相同的元素，最后想办法输出每个元素都是唯一的即可，这里输出唯一的想法是直接在v容器中进行把重复的元素进行删除。

思路：

1、只创建一个元素

2、对nums1和nums2暴力搜索出相同的元素，都插入到v容器中

3、对v进行遍历，将重复的元素删除，唯一的元素保留下来即可，然后返回v即可

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> v;
        for (int i = 0; i < nums1.size(); i++) {
            for (int j = 0; j < nums2.size(); j++){
                if (nums2[j] == nums1[i]) {
                    v.push_back(nums1[i]);
                }
            }
        }
        sort(v.begin(),v.end());
        if (v.size() <= 1) {
            return v;
        }
        else {
            for(vector<int>::iterator it=v.begin() + 1; it!=v.end(); ){
                if(*it == *(it - 1)) {
                    it = v.erase(it);
                }
                else {
                    ++it;
                }
            }
            return v;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

方法二：

分析：

本题还可以使用哈希表做，使用unordered_set，因为输入也是唯一的，正好unordered_set也不会存在重复值。

思路：

1、创建两个无序哈希set，并将nums1全部放入到其中一个set中

2、遍历nums2，在这个set中查找有没有其中的值，如果有则插入到另一个无序set中

3、转成vector 输出即可

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        unordered_set<int> num_set(nums1.begin(),nums1.end());
        for (int num : nums2) {
            if (num_set.find(num) != num_set.end()) {
                result_set.insert(num);
            }
        } 
        return vector<int>(result_set.begin(),result_set.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode 202. 快乐数

题目链接：202. 快乐数

方法一：

分析：

一看就是递归的思想，先写一个方法，不断调用即可，然后判断是不是就行，这里使用的是自己设定的次数100次，for循环进行判断即可。

思路：

1、写一个方法ReturnNum(int n)，此方法用来实现一个数的各个位数的平方在累加和

2、主方法调用ReturnNum(int n)，因为此题说的无限循环，其实也循环不了多少次，一般超过十几二十次结果不能到1，就真的不会到1了，所以我这里就简单写了个100次就行判断即可

class Solution {
public:
    bool isHappy(int n) {
        for (int i = 0; i< 100 ; i++) {
            n = ReturnNum(n);
            if (n == 1) {
                return true;
            }
        }
        return false;
    }

    //这里写递归方法函数
    int ReturnNum(int n){
        int t = 0;
        while (n > 0 ){
            int x = n%10;
            t += pow(x,2);
            n = n / 10;
        }
        return t;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法二：

分析：

这里使用的是哈希中unorder_set 不存在重复的特性进行判断。

思路：

1、写一个方法ReturnNum(int n)，此方法用来实现一个数的各个位数的平方在累加和

2、主方法调用ReturnNum(int n)，当n为1时，返回true

3、不断的循环判断，当再次出现的值已经在set中出现过，就陷入了死循环，返回false，否则继续插入即可。

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> set;
        while (true) {
            n = ReturnNum(n);
            if (n == 1) {
                return true;
            }
            if(set.find(n) != set.end()) {
                return false;
            }
            else{
                set.insert(n);
            }
        }
    }

    //这里写递归方法函数
    int ReturnNum(int n){
        int t = 0;
        while (n > 0 ){
            int x = n%10;
            t += pow(x,2);
            n = n / 10;
        }
        return t;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

LeetCode 1. 两数之和

题目链接：1. 两数之和

方法一：

分析：

暴力求解，嵌套for循环查找即可

思路：

1、创建个容器v

2、嵌套for循环进行搜索

3、将查找到符合要求的下标插入到v中即可，最后返回v即可

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> v;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i+1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    v.push_back(i);
                    v.push_back(j);
                }
            }
        }
        return v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法二：

分析：

哈希方法可求解，使用map

思路：

1、创建个 unordered_map map

2、遍历数组nums，将iter设为需要在map中找到所需差值的迭代器

3、如果找到，返回迭代器的第二个元素，即为value值和i值，否则最后但会空。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for (int i = 0; i< nums.size(); i++) {  
            auto iter = map.find(target - nums[i]);
            if (iter != map.end()) {
                return {iter -> second,i};
            }
            else {
                map.insert(pair<int,int>(nums[i],i));
            }
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

总结：

当需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

• 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
• set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用
• map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下标。（记住，first是key值（具体数值），second是value值（下标值））。