leetcode

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> umap;

        for (string s:strs){
            string key = s;
            sort(key.begin(), key.end());
            umap[key].push_back(s);
        }

        for (auto it=umap.begin(); it != umap.end(); it  ){
            res.push_back(it->second);
        }
        return res;
    }
};

哈希-128. 最长连续序列

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size()==1) return 1;
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(),nums.end()), nums.end());
        // 去重排序
        int res = 1;
        int pre = nums[0];
        vector<int> ress;
        for (int i = 1; i < nums.size(); i  ){
            if (nums[i] - pre == 1) res  ;
            else {
                ress.push_back(res);
                res = 1;
            }
            pre = nums[i];
        }
        int fres;
        if (ress.empty()) fres = res;
        else {
            ress.push_back(res);
            auto it = max_element(ress.begin(),ress.end());
            fres = *it;
        }
        return fres;
    }
};

02.04

哈希-1.两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> umap;
        for (int i = 0; i < nums.size(); i  ){
            auto it = umap.find(target - nums[i]);
            if (it != umap.end()) return {i, it->second};
            else umap.insert(pair<int,int>(nums[i], i));
        }
        return {};
    }
};

哈希-49.字母异位词分组

哈希-128. 最长连续序列

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //最好先排序 去重
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        vector<int> ress;
        if (nums.empty()) return 0;
        if (nums.size()==1) return 1;

        int res = 1;
        int num = nums[0];
        vector<int> nums2(nums.begin() 1, nums.end());
        for (int i:nums2){
            if (i-num == 1) res  ;
            else res = 1;
            ress.push_back(res);
            num = i;
        }
        auto it = max_element(ress.begin(), ress.end());
        return *it;
    }
};

双指针-283.移动零

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int cnt = 0;
        for (int i = 0; i < nums.size(); i  ){
            if (!nums[i]){
                nums.erase(nums.begin() i);
                i--;// 删完一个0，数组长度减1，索引相应减1
                cnt  ;
            }
        }
        while(cnt--){
            nums.push_back(0);
        }
        return;
    }
};

// 交换
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i  ){
            if (nums[i]!=0) continue;
            else{
                int offset = 1;
                int j = i   offset;
                while(j < nums.size() && nums[j]==0){
                    offset  ;
                    j = i offset;//i 2
                }
                if (j < nums.size()) 
                    swap(nums[i], nums[j]);//1 0 0 0 0 0
            }
        }
        return;
    }
};

02.12

滑动窗口-438.找到字符串中所有字母异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (s.size() < p.size()) return {};
        vector<int> res;
        int shash[26] = {0}; // 或 std::vector<int> pcnt(26), scnt(26);
        int phash[26] = {0};
        for (int i = 0; i < p.size(); i  ){
            shash[s[i]-'a']  ;
            phash[p[i]-'a']  ;
        }
        if (equal(begin(shash), end(shash), begin(phash))) res.push_back(0);
        for (int i = 0; i < s.size()-p.size();i  ){
            shash[s[i]-'a']--;
            shash[s[i p.size()]-'a']  ;
            if (equal(begin(shash), end(shash), begin(phash))) res.push_back(i 1);
        }
        return res;
    }
};

超时做法

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        if (s.size() < p.size()) return res;
        sort(p.begin(), p.end());
        int start = 0;
        for (;start < s.size();start  ){
            string subs = s.substr(start,p.size());
            sort(subs.begin(), subs.end());
            if (p==subs) res.push_back(start);
        }
        return res;
    }
};

02.13

链表-2.两数相加

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode*head = nullptr, *tail = nullptr;
        int quo=0, num1, num2, sum;
        while(l1||l2){
            num1=l1?l1->val:0;
            num2=l2?l2->val:0;
            sum=num1 num2 quo;
            quo=sum/10;
            if(!head)head=tail=new ListNode(sum%10);
            else{
                tail->next=new ListNode(sum%10);
                tail=tail->next;
            }
            if(l1)l1=l1->next;
            if(l2)l2=l2->next;
        }
        if(quo) tail->next = new ListNode(quo);
        return head;
    }
};

C 刷题小抄

unordered_set：

uset.insert(i); //uset插入
for (auto it = uset.begin(); it != uset.end(); it  ) cout << *it << " "; //uset遍历

vector中求最大元素：

auto it = max_element(vec.begin(), vec.end());
cout << *it;

vector 首元素/末元素的引用

vector<int> s = {1,2,4,3};
s.front() = 999;//等于s[0]
s.back() = 888;//等于s[s.size()-1]

判断vector是否为空:

bool vec.empty()

vector 去重：

sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());

通过迭代器实现vector 切片：

vector<int> s = {1,2,4,3};
auto begin = s.begin() 1; 
auto end = s.end()-1; 
vector<int> s2(begin, end);//此处不是等号，是构造函数

vector 删除指定的元素

vector<int> s = {1,2,4,3};
s.erase(s.begin()   0);//删除第一个元素1

vector和array按固定长度5初始化

vector<int> s(5, 0); 等效于 vector<int> s(5); //正确vector<int> s= {1,2,3,4,5}; 错误写法vector<int> s(5) = {1,2,3,4,5};
int s[5] = {1,2,3,4,5};
int s[5] = {0};

求原生数组的长度

int s[5] = {1,2,3,4,5};
int length = sizeof(s) / sizeof(s[0]);

对比原生数组 int s[5]，数组 std::array，向量 std::vector，字符串 std::string的区别

1.原生数组没有成员函数或方法，对数组的操作通常需要使用标准库或手动编写代码
  数组array是标准库容器，可调用封装好的成员函数和方法
2.向量vector是动态数组，提供了方便的动态调整大小和元素操作的功能
  数组array是静态数组，长度固定，不能动态调整，但在长度已知的情况下，访问速度较快
3.字符串string实际是基于向量vector实现的动态数组，继承了vector的动态调整大小的特性以适应字符串的长度变化，在处理字符串时更加灵活和方便

string 中根据索引选出子串

string s = "Hello, World!";
string ss = s.substr(startIndex, length);

数组不能直接用数组名比较大小

//数组名表示指向数组首元素的指针 a==b恒为0
int a[3] = {0}, b[3] = {0};
bool x = equal(begin(a), end(a), begin(b));

刷题方式

力扣刷题全流程

[力扣刷题攻略] Re：从零开始的力扣刷题生活

力扣刷题最强指南（版本1.0）

第一阶段按照 tag 去刷，第二阶段则要一题多解，多题同解，挖掘题目背后的东西

去年找互联网的工作，刷了两遍LeetCode，只做了前200道。面试过程中碰到的算法题基本都被秒杀了。最后拿了9个offer。我是按Tag来刷的。链表，二叉树，回溯，深度宽度优先遍历，图，贪心，动规，数组，哈希表……每个tag由easy到hard，每道题先自己思考，不会的参考了一个开源的解答或者参考Discuss或者博客。开始的时候自己独立思考的时间比较长，后来没了耐心，不会的题目就马上看解答了。一般题目解法有多种，这时候最好尝试一下其他的做法，至少要知道思路。比如有关图的题目就会有DFS和BFS两种解法。Discuss里一般都会有高质量的解答。关键是每道题都要弄明白。一开始用IDE，跑出正确结果，再在线默写代码。后来写的多了，直接在线写代码了。这是一个自然的过程，做的多了就有“手感”了。总结一下，按tag由易到难，每道题弄清楚，知道其他的解法，这是核心！搞定了核心，

前200题是最经典的。前期可以先积累量，把前两百题刷完刷够量之后，对算法有了一个大概的理解。然后再精刷。最好先按tag刷。分类总结下自己需要刷的tag。然后按出现频率排序，再按这个顺序刷。最后面试前再刷要面试的那个公司的高频题。

分享一下身边大神的刷题顺序：

如果你时间比较紧迫，为了找工作而刷题，我建议你先刷热门推荐，一共两百多道题。

在 https://leetcode-cn.com/problemset/all/ 页面的右侧。先刷热题 HOT 100，再刷精选 TOP 面试题，之后刷其他的题。如果你时间比较充裕，那我建议你：按从低到高的难度分组刷按 tag 分类刷定期复习，重做之前刷过的题

刷题方法：

第一遍：可以先思考，之后看参考答案刷，结合其他人的题解刷。思考、总结并掌握本题的类型，思考方式，最优题解。

第二遍：先思考，回忆最优解法，并与之前自己写过的解答作比对，总结问题和方法。

第三遍：提升刷题速度，拿出一个题，就能够知道其考察重点，解题方法，在短时间内写出解答。定期总结：按照题目类型进行总结：针对一类问题，总结有哪些解题方法，哪种方法是最优的，为什么。总结重点：有些题你刷了好多遍都还是不会，那就要重点关注，多思考解决方法，不断练习强结合图解刷题：有些人认为刷题比较枯燥，比较抽象。那你可以结合动画图解刷题。