力扣刷题3

一、前言

sheepice开启新的篇章了，虽然现在比较忙，但是如果有空，且写到一些比较有启发的力扣题的时候希望能够发一点点题解，毕竟三叶姐坚持了那么久，也给我有了很好的榜样作用！

sheepice的CSDN地址：大家感兴趣也可以去里面，说不定能学到一点东西哦！

二、leetcode每日一题

今天的每日一题难度不大，主要想记录一下关系哈希表的容器相关写法吧！

---

①思路：

采用哈希表记录下来所有出现过的数和对应的次数，然后利用绝对值大小进行排序（这个排序可以方便我们对表进行一次遍历，只需要看arr[i]对应的arr[i] * 2的次数是不是比前者大，即满足前者能够充分的匹配后者，然后一旦不满足就return false就好了的。

---

②解答：

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
         unordered_map<int, int> cnt;
        for (int x : arr) {
            ++cnt[x];
        }
        if (cnt[0] % 2) {
            return false;
        }

        vector<int> vals;
        vals.reserve(cnt.size());
        for (auto &[x, y] : cnt) {
            vals.push_back(x);
        }
        sort(vals.begin(), vals.end(), [](int a, int b) { return abs(a) < abs(b); });

        for (int x : vals) {
            if (cnt[2 * x] < cnt[x]) { // 无法找到足够的 2x 与 x 配对
                return false;
            }
            cnt[2 * x] -= cnt[x];
        }
        return true;
    }
};

---

③学到的东西

//应该都是容器的相关知识，但是我还没看到，就先记录一下
1.
    //将哈希表里面的第一个元素放到数组里面，
    for (auto &[x, y] : cnt) {
            vals.push_back(x);
        }
2.
    //直接在sort里面进行比较函数的书写
    sort(vals.begin(), vals.end(), [](int a, int b) { return abs(a) < abs(b); });

---

三、三叶姐的题解

xxxxxxxxxx //c++版本的解答class Solution {public:    int maxProduct(vector& words) {        int n = words.size();        vector dp(n,0);        for(int i = 0; i < n; i++) {            for(int j = 0; j < words[i].size(); j++) {                char u = words[i][j];                //进行每一位1的存储                dp[i] |= (1 << (u - ‘a’));             }       }        int ans = 0;        //从头比较到尾，满足无重复数字就进行相关的答案记录        for(int i = 0; i < n - 1; i++) {            for(int j = i+1; j < n; j++) {                if((dp[i] & dp[j]) == 0) {//这里取最大值的地方可以注意一下//可以用ans = max(ans, (int)(words[i].size() * words[j].size()));//因为.size()结构是返回无符号类型的int所以力扣上会报错！！！                    if(words[i].size() * words[j].size() > ans)                    ans = words[i].size() * words[j].size();               }           }       }        return ans;   }};c++

三叶姐的题解