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

发布于 2022-11-21  202 次阅读


242. 有效的字母异位词 - 力扣(LeetCode)

思路:一道很简单的题目,创建一个大小为26的数组用来存储26个字母出现的次数,先遍历字符串s,每遇到一个字母就将数组中对应的值加1,然后再遍历字符串t,每遇到一个字母就将数组中对应的值减1,如果这两个字符串中字母出现的个数相同,那么最后的结果应该是数组中的值全为0,输出true,否则输出false

记得要将数组初始化,复制类似代码的时候记得改值...

我的AC代码

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    bool isAnagram(string s, string t) {
        int ssize = s.size();
        int tsize = t.size();
        int a[26];
        for (int i = 0; i < 26; ++i) {
            a[i] = 0;
        }
        for(int i = 0; i < ssize; ++i) {
            a[(int)(s[i]-97)]++;
        }
        for(int i = 0; i < tsize; ++i) {
            a[(int)(t[i]-97)]--;
        }
        int flag = 1;
        for (int i = 0; i < 26; ++i) {
            if(a[i] != 0) {
                flag = 0;
                break;
            }
        }
        if(flag == 0) {
            return false;
        }
        else {
            return true;
        }
    }
};

标准答案

//时间复杂度O(),空间复杂度O(1)
class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII,只要求出一个相对数值就可以了
            record[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            record[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (record[i] != 0) {
                // record数组如果有的元素不为零0,说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0,说明字符串s和t是字母异位词
        return true;
    }
};

349. 两个数组的交集 - 力扣(LeetCode)

思路:设置一个unordered_map用来存储数据,先遍历nums1,给所有遇到的元素都赋值为1,然后再遍历nums2unordered_map中已经为1的赋值为2,否则赋值为0,最后将所有为1的key都加到vector中储存,这就是最终答案

推荐标准答案的解法,更加优雅

我的AC代码

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> intmap;
        vector<int> a;
        for(int i = 0; i < nums1.size(); ++i) {
            intmap[nums1[i]] = 1;
        }
        for(int i = 0; i < nums2.size(); ++i) {
            if(intmap[nums2[i]] >= 1) {
                intmap[nums2[i]] = 2;
            }
            else {
                intmap[nums2[i]] = 0;
            }

        }
        for(auto x: intmap) {
            if(x.second == 2) {
                a.push_back(x.first);
            }
        }
        return a;
    }
};

标准答案

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果,之所以用set是为了给结果集去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 发现nums2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

202. 快乐数 - 力扣(LeetCode)

思路:创建一个unordered_set来存储每次各位分别平方相加后的数字,如果遇到重复的就返回false,否则最后就会变成1,返回true

我的AC代码

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> pd;
        pd.insert(n);
        while(n != 1) {
            int t = n;
            int tmp = 0;
            while(t != 0)
            {
                tmp = tmp + (t % 10) * (t % 10);
                t = t / 10;
            }
            if(tmp == 1) {
                break;
            }
            else {
                if(pd.find(tmp) != pd.end()) {
                    return false;
                }
                else {
                    pd.insert(tmp);
                }
            }
            n = tmp;
        }
        return true;
    }
};

标准答案

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    // 取数值各个位上的单数之和
    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1) {
            int sum = getSum(n);
            if (sum == 1) {
                return true;
            }
            // 如果这个sum曾经出现过,说明已经陷入了无限循环了,立刻return false
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

1. 两数之和 - 力扣(LeetCode)

思路:把每个元素和它对应的下标存入unordered_map,如果在unordered_map中找到target - nums[i]就加入vector,最后返回vector

强烈建议使用标准答案的做法,我先添加完数据以后才进行判断,需要处理键值冲突的问题,十分麻烦,完全不如标准答案边添加边判断的方式

我的AC代码

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> a;
        vector<int> b;
        for(int i = 0; i < nums.size(); ++i) {
            if(a.find(nums[i]) != a.end()) {
                a[nums[i]] = -1;
            }
            else {
                a[nums[i]] = i;
            }
        }
        for(int i = 0; i < nums.size() ; ++i) {
            if(a.find(target - nums[i]) != a.end()) {
                if(a[(target - nums[i])] == -1) {
                    for(int j = 0; j < nums.size(); ++j) {
                        if(nums[j] == target / 2) {
                            b.push_back(j);
                        }
                    }
                    return b;
                }
                else if((a[nums[i]] != a[(target - nums[i])])) {
                    b.push_back(a[nums[i]]);
                    b.push_back(a[(target-nums[i])]);
                    return b;
                }
            }
        }
        return b;
    }
};

标准答案

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            // 遍历当前元素,并在map中寻找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果没找到匹配对,就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};