|
记一下刷到哪了，推：代码随想录
3. 哈希
总结：leetcode里面的难题不在于算法、数据结构，在于 思维 和 trick。赞。
242.有效的字母异位词
用了两个数组来存储字符出现次数，最后比较。这样空间是O(26+26) 时间是O(n+n+26)
题解用了一个数组，第一个字符串 +，第二个字符串 - ，这样空间是O(26) 时间是O(n+26)，tql.
383. 赎金信
用了一个数组来存储字符出现次数，前面+，后面 -，最后有大于0的，就返回false。
题解是在第二次遍历时，一旦发现有大于0的，直接返回false，tql.
49. 字母异位词分组
用的pair，第一关键字是排序后的字符串，第二关键字是原字符串，排序。
题解用的是unordered_map<string, vector>mp; 结构，写法确实简便不少。
438. 找到字符串中所有字母异位词
每len2长度的子串就判断一下26个字母的数量是否相同。
1. 两数之和
第一次遍历用了unordered_map<int,bool>mp;记录答案中第二个下标，第二次遍历找第一个数的下标。
454.四数相加II
这个题比较有意思。
我开始以为n^3可过，就对其中一个（4）计数， 三重循环（1223）。结果T了。
然后对12又计数一次，再遍历这个，和第三个（12+3），虽然这个还是O(n^3)，但是它过了（感觉数据不够严谨）。
看题解发现，分成两组。12计数一次，34循环。这样就是O(n^2)。机智！
15. 三数之和
一开始计数+n^2，对每一个元组排序，再对结果排序，消除重复的，T了。
后面发现对结果排序会超时。
想办法按顺序得到答案，于是先把原数组从小到大排序，枚举 i，j=i+1
再把结果中重复的消除，T了。
发现有很多重复元组，于是对第一个数再计数，重复的不再往下走，过了。
这样算总体还是O(n^2)+剪枝
题解也是O(n^2)
18.四数之和
感觉和四数相加很像，于是用了O(n^2)的解法，但是卡在重复上面了，花了好久时间改，也许是下午状态不好。
先计算前两个，存（key=和，value=位置），再计算后两个，四个位置递增，可以去除一部分重复。
我是先把所有的按顺序存好，再去重一遍，这样有个问题在于，
[-5, 0, 0, 1, 2, ,3, 4, 5] 这种两个0的情况，前面第一个0会引起，[-5,0,1,4],[-5,0,2,3]，后面第二个0还会有同样的。
也就是[-5,0,1,4], [-5,0,2,3], [-5,0,1,4],[-5,0,2,3]，不能直接去重，但是排序又会T。
所以在后面两重循环的时候，在每一重循环，都加一个，num[i]==num[i-1] continue，即可。
Tips：
???? 1. C98中size()的时间复杂度是O(N), C++11中正常配置下，是O(1)，其它情况下是O(N)
???? 2. 遍历vector& strs，for(string& str: strs)
???? 3. 遍历map，for(auto it = mp.begin(); it != mp.end(); it++)
???? 4. emplace_back()的特别之处。
???? push_back()：向容器尾部添加一个右值元素，然后调用构造函数构造出这个临时对象，最后调用移动构造函数将这个临时对象放入容器中并释放这个临时对象。（注：最后调用的不是拷贝构造函数，而是移动构造函数。因为需要释放临时对象，所以通过std::move进行移动构造，可以避免不必要的拷贝操作）
???? emplace_back()：在容器尾部添加一个元素，调用构造函数原地构造，不需要触发拷贝构造和移动构造。因此比push_back()更加高效。
???? 今天发现评论区都是人才，被敲代码耽误的人才
|