hot100-二刷-牛客

链表

1、反转链表

剑指 Offer 24. 反转链表

递归法

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //递归法
        if(pHead==NULL||pHead->next==NULL)
            return pHead;
        //tmp返回后面已反转的头节点
        ListNode* tmp=ReverseList(pHead->next);
        pHead->next->next=pHead;
        pHead->next=NULL;
        return tmp;
    }
};

非递归法

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //非递归法，要把next保存，然后转换
        ListNode *pre=NULL,*cur=pHead,*tmp;
        while(cur!=NULL){
            tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        //遍历到最后，cur为NULL时，pre不为NULL退出，pre为头节点
        return pre;
    }
};

2、判断一个链表是否为回文结构

队列

class Solution {
public:
    //放入队列，弹出左右进行比较，直到队列为空
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        ListNode* tmp=head;
        deque<ListNode*> dq;
        while(tmp){
            dq.emplace_back(tmp);
            tmp=tmp->next;
        }
        while(!dq.empty()){
            if(dq.size()==1) return true;
            //val相等才行
            if(dq.front()->val!=dq.back()->val) return false;
            dq.pop_front();
            dq.pop_back();
        }
        return true;
    }
};

栈

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    //放入栈,弹出栈顶元素进行比较
    bool isPail(ListNode* head) {
        stack<int> s;
        ListNode *tmp=head;
        while(tmp){
            s.push(tmp->val);
            tmp=tmp->next;
        }
        while(head){
            int val=s.top();
            s.pop();
            if(val!=head->val) return false;
            head=head->next;
        }
        return true;
    }
};

反转+快慢指针

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        if(head==NULL||head->next==NULL) return true;
        //找到中间结点
        ListNode* OneEnd=findHalf(head);
        //反转后半段
        ListNode* TwoStart=reverseNode(OneEnd->next);
        ListNode *p1=head,*p2=TwoStart;
        while(p2){
            //要比较val，因为没有重载=
            if(p1->val!=p2->val) return false;
            p1=p1->next;
            p2=p2->next;
        }
        reverseNode(TwoStart);
        return true;
    }
    //反转链表
    ListNode* reverseNode(ListNode* head){
        if(head==NULL||head->next==NULL) return head;
        ListNode *tmp=reverseNode(head->next);
        head->next->next=head;
        head->next=NULL;
        return tmp;
    }
    //找到中间结点
    ListNode* findHalf(ListNode* head){
        ListNode *slow=head,*fast=head;
        while(fast->next && fast->next->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
};

3、判断链表中是否有环

快慢指针

class Solution {
public:
    //快慢指针相遇时代表有环
    bool hasCycle(ListNode *head) {
        ListNode *slow=head,*fast=head;
        while(fast && fast->next!=NULL){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==NULL) return false;            
            if(fast==slow) return true;
        }
        return false;        
    }
};

class Solution {
public:
       //快慢指针的另一种思路
    bool hasCycle(ListNode *head) {
        if(head==NULL||head->next==NULL) return false;
        ListNode *fast=head->next,*slow=head;
        while(slow!=fast){
            if(fast->next==NULL||fast==NULL) return false;
            slow=slow->next;
            fast=fast->next->next;
        }
        return true;
    }
};

哈希表

class Solution {
public:
    //hash表
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> hashSet;
        while(head){
            if(hashSet.count(head)) return true;
            hashSet.insert(head);
            head=head->next;            
        }
        return false;
    }
};

4、链表中环的入口结点

快慢指针

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(pHead==NULL||pHead->next==NULL) return NULL;
        ListNode *slow=pHead,*fast=pHead;
        while(fast!=NULL && fast->next!=NULL){
            slow=slow->next;
            if(fast->next==NULL) return NULL;
            fast=fast->next->next;  
            //如果相遇，头和slow在相遇即为入口
            if(fast==slow){
                ListNode* tmp=pHead;
                while(tmp!=slow){
                    tmp=tmp->next;
                    slow=slow->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};

哈希表

class Solution {
public:
    //hash表
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        unordered_set<ListNode*>　hashSet;
        while(pHead){
            if(hashSet.count(pHead)) return pHead;
            hashSet.insert(pHead);
            pHead=pHead->next;
        }
        return NULL;
    }
};

5、合并两个排序的链表

剑指 Offer 25. 合并两个排序的链表

递归

class Solution {
public:
    //递归法
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==NULL) return pHead2;
        else if(pHead2==NULL) return pHead1;
        else if(pHead1->val<pHead2->val){
            pHead1->next=Merge(pHead1->next,pHead2);
            return pHead1;
        }
        else{
            pHead2->next=Merge(pHead1,pHead2->next);
            return pHead2;
        }
    }
};

非递归

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //增加虚拟节点
        ListNode *p1=pHead1,*p2=pHead2,*dummy=new ListNode(0);
        ListNode *p=dummy;
        while(p1 && p2){
            if(p1->val<p2->val){
                p->next=p1;
                p1=p1->next;
            }else{
                p->next=p2;
                p2=p2->next;
            }
            p=p->next;
        }
        //p1或p2为空时
        p->next=p1?p1:p2;
        //删除虚拟节点，防止内存泄漏
        p=dummy->next;
        delete dummy;
        return p;
    }
};

6、合并k个已排序的链表

递归+顺序

不满足时间复杂度的要求 O(nlogk)O(nlogk)

递归+二分

class Solution {
public:
    //递归+二分法
    ListNode *mergeKLists(vector<ListNode *> &lists){
        return merge(lists,0,lists.size()-1);
    }
    //二分法选择要合并的两个链表
    ListNode *merge(vector<ListNode*>&lists,int l,int r){
        if(l>r) return NULL;
        if(l==r) return lists[l];
        int mid=(l+r)>>1;
        return merge2Lists(merge(lists,l, mid), merge(lists,mid+1, r));
    }
    ListNode *merge2Lists(ListNode* l1,ListNode* l2){
        if(l1==NULL) return l2;
        else if(l2==NULL) return l1;
        else if(l1->val<l2->val){
            l1->next=merge2Lists(l1->next, l2);
            return l1;
        }else{
            l2->next=merge2Lists(l1, l2->next);
            return l2;
        }
    }
};

优先级队列

class Solution {
public:
    //优先级队列,自定义排序方式
    struct cmp{
        bool operator()(ListNode* n1,ListNode* n2){
            return n1->val>n2->val;
        }  
    };
    priority_queue<ListNode*, vector<ListNode*>, cmp> q;

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        for(auto node:lists){
            if(node){
                q.push(node);
            }
        }

        ListNode* dummy=new ListNode(0);
        ListNode* cur=dummy;
        while(!q.empty()){
            ListNode* node=q.top();
            q.pop();
            if(node->next){
                q.push(node->next);
            }
            cur->next=node;
            cur=cur->next;
        }
        cur=dummy->next;
        delete dummy;
        return cur;
    }
};

7、删除链表的倒数第n个节点

剑指 Offer 22. 链表中倒数第k个节点

快慢指针

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy=new ListNode(0);
        dummy->next=head;
        ListNode *slow=dummy,*fast=dummy,*pre=NULL;
        n++;//虚拟节点也要跳过
        while(n--){
            fast=fast->next;
        }
        //找到要删除节点的前一个位置
        while(fast!=NULL){          
            slow=slow->next;
            fast=fast->next;
        }
        slow->next=slow->next->next;
        head=dummy->next;
        delete dummy;
        return head;
    }
};

栈

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        stack<ListNode*> s;
        //添加一个虚拟节点
        ListNode* dummy=new ListNode(0);
        dummy->next=head;
        ListNode* cur=dummy;
        //全部推入栈
        while(cur){
            s.push(cur);
            cur=cur->next;
        }
        //pop n个
        while(n--){
            s.pop();            
        }
        //找到要删除节点的pre
        ListNode* pre=s.top();
        pre->next=pre->next->next;
        cur=dummy->next;
        delete dummy;
        return cur;
    }
};

8、两个链表的第一个公共结点

双指针

class Solution {
public:
    //双指针
    //先求出两者长度之差，长的那个先走差距，接着两指针同时走，比较值，相同返回
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *p1=pHead1,*p2=pHead2;
        int m=0,n=0;
        //求两个链表长度
        while(p1){
            p1=p1->next;m++;
        }
        while(p2){
            p2=p2->next;n++;
        }
        //找差值
        int step=abs(m-n);
        p1=m>n?pHead1:pHead2;
        p2=m>n?pHead2:pHead1;
        //长的往前走
        while(step--){
            p1=p1->next;
        }
        //比较对应位置的数
        while(p1){
            if(p1->val==p2->val) return p1;
            p1=p1->next;
            p2=p2->next;
        }
        return NULL;        
    }
};

哈希表

class Solution {
public:
    //hash表 先存一个,再查另一个
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        unordered_set<ListNode*> hashSet;
        ListNode *p1=pHead1,*p2=pHead2;
        while(p1){
            hashSet.insert(p1);
            p1=p1->next;
        }
        while(p2){
            if(hashSet.count(p2)){
                return p2;
            }
            p2=p2->next;
        }
        return nullptr;
    }
};

9、单链表的排序

归并排序-自顶向下

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    //归并排序
    ListNode* sortInList(ListNode* head) {
        // write code here
        return sort2Lists(head, NULL);        
    }
    //找到中间结点，合并前后两个链表
    ListNode* sort2Lists(ListNode* head,ListNode* tail){
        if(head==NULL) return head;
        if(head->next==tail){
            head->next=NULL;
            return head;
        }
        ListNode *slow=head,*fast=head;
        while(fast!=tail && fast->next!=tail){
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode *mid=slow;
        return merge2Lists(sort2Lists(head,mid),sort2Lists(mid, tail));

    }
    //合并两个有序链表
    ListNode* merge2Lists(ListNode* l1,ListNode* l2){
        if(l1==NULL) return l2;
        if(l2==NULL) return l1;
        else if(l1->val<l2->val){
            l1->next=merge2Lists(l1->next, l2);
            return l1;
        }else{
            l2->next=merge2Lists(l1, l2->next);
            return l2;
        }
    }
};

归并排序-自底向上

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        //先求长度
        int n=0;
        ListNode* tmp=head;
        while(tmp){
            n++;
            tmp=tmp->next;
        }

        ListNode* dummy=new ListNode(0);
        dummy->next=head;
        //先合并以1为单位，然后2，4，8...
        for(int sublength=1;sublength<n;sublength<<=1){
            ListNode *prev=dummy,*curr=dummy->next;
            while(curr){
                //找到要合并的第一段
                ListNode *head1=curr;
                for(int i=1;i<sublength && curr->next!=NULL;i++){
                    curr=curr->next;
                }
                //找到要合并的第二段
                ListNode* head2=curr->next;
                curr->next=nullptr;
                curr=head2;
                for(int i=1;i<sublength && curr!=nullptr && curr->next!=nullptr;i++){
                    curr=curr->next;
                }
                ListNode* next=nullptr;
                if(curr!=nullptr){
                    next=curr->next;
                    curr->next=nullptr;
                }
                //开始合并
                ListNode *merged=merge2Lists(head1, head2);
                //和之前段连在一起
                prev->next=merged;
                while(prev->next!=nullptr){
                    prev=prev->next;
                }
                curr=next;
            }
        }
        ListNode* curr=dummy->next;
        delete dummy;
        return curr;
    }

    ListNode* merge2Lists(ListNode* l1,ListNode* l2){
        if(l1==NULL) return l2;
        if(l2==NULL) return l1;
        else if(l1->val<l2->val){
            l1->next=merge2Lists(l1->next, l2);
            return l1;
        }else{
            l2->next=merge2Lists(l1, l2->next);
            return l2;
        }
    }
};

10、二叉搜索树和双向链表

二叉搜索树与双向链表

中序遍历+递归

class Solution {
public:
    //中序遍历
    TreeNode *pre=NULL,*head=NULL;
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree==NULL) return NULL;
        //排好左子
        Convert(pRootOfTree->left);
        //将root与左边排好的相连
        if(pre==NULL){
            pre=pRootOfTree;
            head=pRootOfTree;
        }else{
            pre->right=pRootOfTree;
            pRootOfTree->left=pre;
            pre=pRootOfTree;
        }
        //排右子
        Convert(pRootOfTree->right);
        return head;
    }
};

剑指 Offer 36. 二叉搜索树与双向链表

class Solution {
public:
    Node *pre=NULL,*head=NULL;
    Node* treeToDoublyList(Node* root) {
        if(root==NULL) return root;
        traverse(root);
        head->left=pre;
        pre->right=head;
        return head;
    }
    void traverse(Node* root){
        if(root==NULL) return;
        traverse(root->left);

        //pre为前一个，不为空时
        if(pre) pre->right=root;
        //为空时// 保存链表头结点
        else head=root;
        root->left=pre;
        pre=root;

        traverse(root->right);
    }
};

11、链表相加(一)

双指针

class Solution {
public:
    ListNode* ListAdd(ListNode* l1, ListNode* l2) {
        ListNode *head=NULL,*p=head;
        int flag=0;
        while(l1||l2){
            int n1=l1?l1->val:0;
            int n2=l2?l2->val:0;
            int n=(n1+n2+flag)%10;
            flag=(n1+n2+flag)/10;

            if(p==NULL){
                p=head=new ListNode(n);
            }else{
                p->next=new ListNode(n);
                p=p->next;
            }

            if(l1) l1=l1->next;
            if(l2) l2=l2->next;

        }

        if(flag){
            p->next=new ListNode(flag);
        }
        return head;
    }
};

12、 146. LRU 缓存(No)

hash表+双向链表

//hash表+双向链表
struct DLinkNode{
    int key;
    int value;
    DLinkNode* prev;
    DLinkNode* next;
    DLinkNode():key(0),value(0),prev(nullptr),next(nullptr){}
    DLinkNode(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){}
};
class LRUCache {
private:
    unordered_map<int,DLinkNode*> cache;
    DLinkNode* head;
    DLinkNode* tail;
    int capacity;
    int size;
public:
    LRUCache(int _capacity):capacity(_capacity),size(0) {
        //虚拟头节点和尾部节点
        head=new DLinkNode();
        tail=new DLinkNode();
        head->next=tail;
        tail->prev=head;
    }

    int get(int key) {
        //先通过hash表找位置，然后移动到最后边
        if(!cache.count(key)){
            return -1;
        }
        DLinkNode* node=cache[key];
        movToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        //hash表没有这个元素，添加
        if(!cache.count(key)){
            DLinkNode* node=new DLinkNode(key,value);
            cache[key]=node;
            //添加至头部
            addToHead(node);
            size++;
            //超出容量，删除tail元素,并从hash表中删除
            if(size>capacity){  
                DLinkNode* removeNode=removeTail();
                cache.erase(removeNode->key);
                size--;
            }
        }
        //有这个元素，更改value
        DLinkNode* node=cache[key];
        node->value=value;
        movToHead(node);
    }
    //把节点从双向链表中摘出来
    void moveNode(DLinkNode* node){
        node->prev->next=node->next;
        node->next->prev=node->prev;
    }
    //把节点添加到head
    void addToHead(DLinkNode* node){
        node->prev=head;
        node->next=head->next;
        head->next->prev=node;
        head->next=node;
    }
    void movToHead(DLinkNode* node){
        //先把节点摘出来
        moveNode(node);
        //在添加到头部
        addToHead(node);
    }

    DLinkNode* removeTail(){
        DLinkNode* node=tail->prev;
        moveNode(node);
        return node;
    }
};

13、148. 排序链表(No)

归并排序-自上向下

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sortList(head, nullptr);
    }

    ListNode* sortList(ListNode* head, ListNode* tail) {
        if (head == nullptr) {
            return head;
        }
        if (head->next == tail) {
            head->next = nullptr;
            return head;
        }
        ListNode* slow = head, *fast = head;
        while (fast != tail) {
            slow = slow->next;
            fast = fast->next;
            if (fast != tail) {
                fast = fast->next;
            }
        }
        ListNode* mid = slow;
        return merge(sortList(head, mid), sortList(mid, tail));
    }

    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
        while (temp1 != nullptr && temp2 != nullptr) {
            if (temp1->val <= temp2->val) {
                temp->next = temp1;
                temp1 = temp1->next;
            } else {
                temp->next = temp2;
                temp2 = temp2->next;
            }
            temp = temp->next;
        }
        if (temp1 != nullptr) {
            temp->next = temp1;
        } else if (temp2 != nullptr) {
            temp->next = temp2;
        }
        return dummyHead->next;
    }
};

归并排序-自下向上

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        int length = 0;
        ListNode* node = head;
        while (node != nullptr) {
            length++;
            node = node->next;
        }
        ListNode* dummyHead = new ListNode(0, head);
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode* prev = dummyHead, *curr = dummyHead->next;
            while (curr != nullptr) {
                ListNode* head1 = curr;
                for (int i = 1; i < subLength && curr->next != nullptr; i++) {
                    curr = curr->next;
                }
                ListNode* head2 = curr->next;
                curr->next = nullptr;
                curr = head2;
                for (int i = 1; i < subLength && curr != nullptr && curr->next != nullptr; i++) {
                    curr = curr->next;
                }
                ListNode* next = nullptr;
                if (curr != nullptr) {
                    next = curr->next;
                    curr->next = nullptr;
                }
                ListNode* merged = merge(head1, head2);
                prev->next = merged;
                while (prev->next != nullptr) {
                    prev = prev->next;
                }
                curr = next;
            }
        }
        return dummyHead->next;
    }

    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
        while (temp1 != nullptr && temp2 != nullptr) {
            if (temp1->val <= temp2->val) {
                temp->next = temp1;
                temp1 = temp1->next;
            } else {
                temp->next = temp2;
                temp2 = temp2->next;
            }
            temp = temp->next;
        }
        if (temp1 != nullptr) {
            temp->next = temp1;
        } else if (temp2 != nullptr) {
            temp->next = temp2;
        }
        return dummyHead->next;
    }
};

二叉树

1、二叉树的中序遍历

递归

class Solution {
public:
    //递归
    vector<int> res;
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        if(root==NULL) return res;
        //先左
        inorderTraversal(root->left);
        //根
        res.push_back(root->val);
        //后子
        inorderTraversal(root->right);
        return res;
    }
};

迭代

class Solution {
public:
    //迭代，借助栈
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here

        stack<TreeNode*> st;
        vector<int> res;
        //推入栈或开始访问，当没有节点可以推入栈时就开始访问
        while(root!=NULL||!st.empty()){
            //入栈
            if(root!=NULL){
                st.push(root);
                //不断朝左走，推入栈
                root=root->left;
            }
            //开始访问,顺便把右子推入栈
            else{
                TreeNode* node=st.top();
                st.pop();
                res.push_back(node->val);
                root=node->right;
            }
        }
        return res;
    }
};

2、求二叉树的层序遍历

迭代

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(root!=NULL) q.push(root);

        while(!q.empty()){
            //每层size个，依次访问完，同时要把left和right推进去
            int size=q.size();            
            vector<int> vec;
            for(int i=0;i<size;i++){
                TreeNode* node=q.front();
                q.pop();
                vec.push_back(node->val);

                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res.push_back(vec);
        }
        return res;
    }
};

3、按之字形顺序打印二叉树

迭代

class Solution {
public:
    //层序遍历，中间逆序、顺序交叉
    vector<vector<int> > Print(TreeNode* pRoot) {
        // write code here
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(pRoot!=NULL) q.push(pRoot);
        bool order=false;

        while(!q.empty()){
            //每层size个，依次访问完，同时要把left和right推进去
            int size=q.size();            
            vector<int> vec;
            for(int i=0;i<size;i++){
                TreeNode* node=q.front();
                q.pop();
                vec.push_back(node->val);

                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            if(order){
                reverse(vec.begin(),vec.end());
            }            
            order=!order;
            res.push_back(vec);
        }
        return res;
    }

};

4、从前序与中序遍历序列构造二叉树

递归

class Solution {
public:
    //递归
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildRoot(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }

    TreeNode* buildRoot(vector<int>& preorder,int preStart,int preEnd,vector<int>&　inorder,int inStart,int inEnd){
        //前序第一个为根，找到根在中序的位置，该位置之前为左子，之后为右子
        if(preStart>preEnd) return NULL;
        int rootVal=preorder[preStart];
        int rootIndex=0;
        for(int i=inStart;i<=inEnd;i++){
            if(inorder[i]==rootVal){
                rootIndex=i;break;
            }
        }
        int len=rootIndex-inStart;
        TreeNode* root=new TreeNode(rootVal);
        root->left=buildRoot(preorder,preStart+1,preStart+len,inorder,inStart,rootIndex-1);
        root->right=buildRoot(preorder,preStart+len+1,preEnd,inorder,rootIndex+1,inEnd);

        return root;
    }
};

5、对称的二叉树

递归

class Solution {
public:
    //递归，看左子的左子与右子的右子是否相等，左子的右子与右子的左子是否相等
    bool isSymmetrical(TreeNode* pRoot) {
        return check(pRoot, pRoot);
    }
    bool check(TreeNode* p,TreeNode* q){
        if(!p&&!q) return true;
        if(!p||!q) return false;
        return (p->val==q->val)&&check(p->left, q->right)&&check(p->right,q->left);
    }
};

迭代

class Solution {
public:
    //迭代，入栈，左子的左子和右子的右子入栈，并同时取出，应该相等。
    bool isSymmetrical(TreeNode* pRoot) {
        return check(pRoot, pRoot);
    }
    bool check(TreeNode* p,TreeNode* q){
        queue<TreeNode*> que;
        que.push(p);
        que.push(q);
        //同时弹出两个，比较是否相同
        while(!que.empty()){
            p=que.front();
            que.pop();
            q=que.front();
            que.pop();

            //一定要continue 队列为空，继续往下走
            if(!q&&!p) continue;
            if((!q||!p)||(p->val!=q->val)) return false;

            que.push(p->left);
            que.push(q->right);

            que.push(p->right);
            que.push(q->left);
        }
        return true;
    }
};

6、二叉树的最大深度

递归

class Solution {
public:
    //递归
    int maxDepth(TreeNode* root) {
        if(root==NULL) return 0;
        //本层+左右子最大深度的最大值
        return 1+max(maxDepth(root->left),maxDepth(root->right));
    }
};

迭代

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    //迭代，层序遍历
    int maxDepth(TreeNode* root) {
        if(root==NULL) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int depth=0;

        while(!q.empty()){
            int size=q.size();
            depth++;
            for(int i=0;i<size;i++){
                TreeNode* node=q.front();
                q.pop();
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
        }
        return depth;
    }
};

7、翻转二叉树

递归

class Solution {
public:
    //递归，交换左右子树，再反转左右子树
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL) return NULL;
        TreeNode* old=root->left;
        root->left=root->right;
        root->right=old;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

迭代

class Solution {
public:
    //迭代，层序遍历，在入队列时就交换左右子
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL) return NULL;
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            int size=q.size();
            for(int i=0;i<size;i++){
                TreeNode* node=q.front();
                q.pop();

                TreeNode* tmp=node->left;
                node->left=node->right;
                node->right=tmp;

                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
        }
        return root;
    }
};

8、合并二叉树

递归

class Solution {
public:
    //递归
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        // write code here
        if(t1==NULL&&t2==NULL) return NULL;
        if(t1==NULL||t2==NULL) return t1==NULL?t2:t1;         
        //确定根，递归确定左右子
        TreeNode* root=new TreeNode(t1->val+t2->val);
        root->left=mergeTrees(t1->left, t2->left);
        root->right=mergeTrees(t1->right, t2->right);
        return root;        
    }
};

迭代

class Solution {
public:
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    //迭代
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1==NULL&&t2==NULL) return NULL;
        if(!t1||!t2) return t1==NULL?t2:t1;

        TreeNode* root=new TreeNode(t1->val+t2->val);
        //都通过队列 来进行访问
        queue<TreeNode*> q1,q2,q;
        q1.push(t1);
        q2.push(t2);
        q.push(root);

        while(!q1.empty()&&!q2.empty()){
            TreeNode* node=q.front(); q.pop();
            TreeNode* node1=q1.front();q1.pop();
            TreeNode* node2=q2.front();q2.pop();
            //处理左子，都不为空相加，一个为空 等于另一个
            if(node1->left&&node2->left){
                TreeNode* left=new TreeNode(node1->left->val+node2->left->val);                   
                node->left=left;
                q1.push(node1->left);
                q2.push(node2->left);  
                q.push(left);
            }else if(node1->left){
                node->left=node1->left;
            }else{
                node->left=node2->left;
            }
            //右子同样
            if(node1->right && node2->right){
                TreeNode* right=new TreeNode(node1->right->val+node2->right->val);
                node->right=right;
                q1.push(node1->right);
                q2.push(node2->right);
                q.push(right);
            }else if(node1->right){
                node->right=node1->right;
            }else{
                node->right=node2->right;
            }
        }
        return root;
    }
};

9、二叉树的直径

递归

class Solution {
public:
    //递归
    int res=0;
    int diameterOfBinaryTree(TreeNode* root) {
        getHeight(root);
        return res;        
    }
    int getHeight(TreeNode* root){
        if(root==NULL) return 0;
        int l_max=getHeight(root->left);
        int r_max=getHeight(root->right);
        //当前节点的直径为 左右子树深度相加
        int diameter=l_max+r_max;
        res=max(res,diameter);
        //返回较大深度
        return 1+max(l_max,r_max);
    }
};

10、二叉树中的最大路径和

递归

class Solution {
public:
    //递归
    int res=0;
    int diameterOfBinaryTree(TreeNode* root) {
        getHeight(root);
        return res;        
    }
    int getHeight(TreeNode* root){
        if(root==NULL) return 0;
        //还要与0比较，负数可以不要这个数
        int l_max=max(getHeight(root->left),0);
        int r_max=max(getHeight(root->right),0);
        //当前节点的直径为 左右子树深度相加
        int diameter=l_max+r_max;
        res=max(res,diameter);
        //返回较大深度
        return 1+max(l_max,r_max);
    }
};

11、树的最近公共祖先问题

二叉搜索树的最近公共祖先

递归

class Solution {
public:
    //递归
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        //空树找不到公共祖先
        if(root==NULL) return -1;
        //pq在该节点两边说明这就是最近公共祖先
        if((p<=root->val && q>=root->val)||(p>=root->val && q<=root->val))
            return root->val;
        //pq都在该节点的左边
        else if(p<=root->val && q<=root->val)
            return lowestCommonAncestor(root->left,p, q);
        //pq都在该节点的右边
        else 
            return lowestCommonAncestor(root->right,p, q);
    }
};

在二叉树中找到两个节点的最近公共祖先

递归

class Solution {
public:
    //递归
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        return helper(root, o1, o2)->val;
    }
    TreeNode* helper(TreeNode* root, int o1, int o2){
        if(root==NULL||root->val==o1||root->val==o2) return root;
        TreeNode* left=helper(root->left, o1,o2);
        TreeNode* right=helper(root->right, o1,o2);
        if(left==NULL) return right;
        if(right==NULL) return left;
        return root;
    }
};

二叉树的最近公共祖先

递归

class Solution {
public:
    //递归
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL) return NULL;
        if(p==root||q==root) return root;

        //从左右子树中找
        TreeNode* left=lowestCommonAncestor(root->left, p, q);
        TreeNode* right=lowestCommonAncestor(root->right, p, q);

        //左子树没找到，看右子树
        if(left==NULL) return right;
        //右子树没找到，看左子树
        if(right==NULL) return left;
        //左右子树中都找到了，那就是根
        if(left!=NULL && right!=NULL) return root;

        return NULL;
    }
};

12、序列化

序列化二叉树

递归+前序

class Solution {
public:
    string res="";
    void inorder(TreeNode* root){
        if(root==NULL){
            res += "#";
            return;
        }
        res += to_string(root->val)+",";
        inorder(root->left);
        inorder(root->right);
    }

    char* Serialize(TreeNode *root) {    
        //前序遍历
        inorder(root);
        //分配内存
        char* ans=new char[res.size()+1];
        // c_str返回c风格的字符串
        strcpy(ans, res.c_str());
        return ans;
    }
    TreeNode* Deserialize(char *str) {
        int p=0;//指向字符串处理的位置
        return des(str,p);
    }
    TreeNode* des(char *str,int &p){
        if(str[p]=='#'){
            p++;
            return NULL;
        }
        //如果是负数
        bool flag=true;
        if(str[p]=='-'){
            p++;
            flag=false;
        }
        int val=0;
        while(str[p]!=','){
            val=val*10+str[p]-'0';
            p++;
        }
        p++;//跳过数字后的","
        if(!flag) val=-val;
        TreeNode* node=new TreeNode(val);
        node->left=des(str,p);//向左递归
        node->right=des(str,p);//向右递归
        return node;
    }
};

297. 二叉树的序列化与反序列化

剑指 Offer 37. 序列化二叉树

递归

class Codec {
public:

    // Encodes a tree to a single string.
    string res;
    string serialize(TreeNode* root) {
        if(root==NULL) return "#";
        string left=serialize(root->left);
        string right=serialize(root->right);
        //前序遍历
        return to_string(root->val)+","+left+","+right;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        list<string> lt;
        string str;
        for(char &c:data){
            if(c==','){
                lt.push_back(str);
                str.clear();
            }else{
                str.push_back(c);
            }
        }
        //最后一个没有结束符，看str是否为空
        if(!str.empty()){
            lt.push_back(str);
            str.clear();
        }

        return helper(lt);
    }

    TreeNode* helper(list<string>& lt){
        string str=lt.front();
        lt.pop_front();
        if(str=="#"){
            return NULL;
        }
        TreeNode* node=new TreeNode(stoi(str));
        node->left=helper(lt);
        node->right=helper(lt);
        return node;
    }
};

13、96. 不同的二叉搜索树

递归-超时

class Solution {
public:
    //递归法
    int numTrees(int n) {
        return numCount(1,n);
    }
    int numCount(int low,int high){
        if(low>high) return 1;
        int cnt=0;
        //以i为根，计算左子和右子的种数
        for(int i=low;i<=high;i++)
            cnt+=numCount(low,i-1)*numCount(i+1,high);
        return cnt;
    }
};

备忘录

class Solution {
public:
    //备忘录
    vector<vector<int>> memo;
    int numTrees(int n) {
        memo.resize(n+1,vector<int>(n+1,-1));
        return numCount(1,n);
    }
    int numCount(int low,int high){
        if(low>high) return 1;
        if(memo[low][high]!=-1) return memo[low][high];

        int cnt=0;
        //以i为根，计算左子和右子的种数
        for(int i=low;i<=high;i++)
            cnt+=numCount(low,i-1)*numCount(i+1,high);
        memo[low][high]=cnt;
        return cnt;
    }
};

动态规划

class Solution {
public:
    int numTrees(int n) {
        if(n<=2) return n;
        //base  dp[i]代表 BST中i个节点可组成的种数
        vector<int> dp(n+1,0);
        //edge
        dp[0]=1;//0个节点也是一种，空
        dp[1]=1;
        dp[2]=2;
        //relation
        for(int i=3;i<=n;i++){
            for(int j=1;j<=i;j++){ //根的位置 从第一个开始取
                dp[i]+=dp[j-1]*dp[i-j]; // 根左边的num*右边的num
            }
        }
        return dp[n];
    }
};

14、判断是不是二叉搜索树

递归

class Solution {
public:
    //递归
    bool isValidBST(TreeNode* root) {
        return helper(root, INT_MAX, INT_MIN);
    }
     // 左子树都小于 根，右子树都大于
    bool helper(TreeNode* root,long long m_max,long long m_min){
        if(root==NULL) return true;
        if(root->val>=m_max || root->val<=m_min) return false;
        return helper(root->left, root->val, m_min) && helper(root->right, m_max, root->val);
    }
};

迭代+中序

class Solution {
public:
    //迭代+中序
    bool isValidBST(TreeNode* root) {
        if(root==NULL) return true;
        stack<TreeNode*> q;
        TreeNode* curr=root;
        TreeNode* pre=NULL;
        while(curr!=NULL||!q.empty()){
            if(curr!=NULL){
                q.push(curr);
                curr=curr->left;
            }else{
                curr=q.top();
                q.pop();
                //比较与前一节点
                if(pre!=NULL && pre->val>=curr->val){
                    return false;
                }
                //更新前一节点
                pre=curr;
                curr=curr->right;
            }
        }
        return true;

    }
};

递归+中序

class Solution {
public:
    //递归+中序
    vector<int> res;
    //看 res是否升序
    bool isValidBST(TreeNode* root) {
        traverse(root);
        for(int i=1;i<res.size();i++){
            if(res[i]<res[i-1])
                return false;
        }
        return true;
    }
    void traverse(TreeNode* root){
        if(root==NULL) return ;
        traverse(root->left);
        res.push_back(root->val);
        traverse(root->right);
    }
};

15、将二叉搜索树改为累加树

递归

class Solution {
public:
    //递归
    TreeNode* convertBST(TreeNode* root) {
        traverse(root);
        return root;
    }
    int sum=0;
    void traverse(TreeNode* root){
        if(root==NULL) return ;
        //逆中序，从右开始，因为右子总是大的
        traverse(root->right);
        sum+=root->val;
        root->val=sum;
        traverse(root->left);
    }
};

迭代

class Solution {
public:
    //迭代+逆中序
    TreeNode* convertBST(TreeNode* root) {
        if(root==NULL) return NULL;
        stack<TreeNode*> st;
        TreeNode* curr=root;
        int sum=0;

        while(curr!=NULL||!st.empty()){
            if(curr!=NULL){
                st.push(curr);
                //先入右
                curr=curr->right;
            }else{
                curr=st.top();
                st.pop();
                sum+=curr->val;
                curr->val=sum;
                //左子在后
                curr=curr->left;
            }
        }
        return root;        
    }
};

16、208. 实现 Trie (前缀树)(No)

前缀树

class Trie {
public:
    Trie():next(26),isEnd(false) {
    }

    void insert(string word) {
        Trie* node=this;
        for(char c:word){
            if(node->next[c-'a']==NULL){
                node->next[c-'a']=new Trie();
            }
            node=node->next[c-'a'];
        }
        node->isEnd=true;
    }

    bool search(string word) {
        Trie* node=this;
        for(char c:word){
            node=node->next[c-'a'];
            if(node==NULL){
                return false;
            }
        }
        return node->isEnd;
    }

    bool startsWith(string prefix) {
        Trie* node=this;
        for(char c:prefix){
            node=node->next[c-'a'];
            if(node==NULL){
                return false;
            }
        }
        return true;
    }

    bool isEnd;
    vector<Trie*> next;
};

动态规划

股票系列

1、买卖股票的最好时机(一)

动态规划

class Solution {
public:
    //动态规划
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(2));

        //dp[i][j]表示第i天的最大利润，j=0/1为持有或不持有股票
        dp[0][0]=0;
        dp[0][1]=-prices[0];//第一天不可能拥有股票

        for(int i=1;i<n;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
            //当天持有股是因为买入，-prices[i];
            dp[i][1]=max(-prices[i],dp[i-1][1]);
        }
        return dp[n-1][0];
    }
};

优化

class Solution {
public:
    //动态规划
    int maxProfit(vector<int>& prices) {
        int n=prices.size();

        int dp_0=0;
        int dp_1=-prices[0];//第一天不可能拥有股票

        for(int i=1;i<n;i++){
            dp_0=max(dp_0,dp_1+prices[i]);
            //当天持有股是因为买入，-prices[i];
            dp_1=max(-prices[i],dp_1);
        }
        return dp_0;
    }
};

2、买卖股票的最好时机(二)

动态规划

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(2));

        //dp[i][j]表示第i天的最大利润，j=0/1为持有或不持有股票
        dp[0][0]=0;
        dp[0][1]=-prices[0];//第一天不可能拥有股票

        for(int i=1;i<n;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
            ////当天可多次交易，dp_0-prices[i];
            dp[i][1]=max(dp[i-1][0]-prices[i],dp[i-1][1]);
        }
        return dp[n-1][0];
    }
};

优化

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();

        int dp_0=0;
        int dp_1=-prices[0];//第一天不可能拥有股票

        for(int i=1;i<n;i++){
            dp_0=max(dp_0,dp_1+prices[i]);
            //当天可多次交易，dp_0-prices[i];
            dp_1=max(dp_0-prices[i],dp_1);
        }
        return dp_0;
    }
};

3、买卖股票的最好时机(三)

递归

class Solution {
public:
    //动态规划
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int k_max=2;

        vector<vector<vector<int>>> dp(n,vector<vector<int>>(k_max+1,vector<int>(2)));

        for(int k=1;k<=k_max;k++){
            dp[0][k][0]=0;
            dp[0][k][1]=-prices[0];
        }

        for(int i=1;i<n;i++){
            for(int k=k_max;k>0;k--){
                //今天不拥有=max(昨天不拥有，昨天拥有和今天卖出)，不计入交易次数
                dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
                //今天拥有=max(昨天拥有，昨天不拥有和今天买入)，计入交易次数
                dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);
            }
        }

        return dp[n-1][k_max][0];       

    }
};

优化

class Solution {
public:
    //动态规划
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int k_max=2;

        int dp_0_1_0=0;
        int dp_0_1_1=-prices[0];
        int dp_0_2_0=0;
        int dp_0_2_1=-prices[0];

        for(int i=1;i<n;i++){
            for(int k=k_max;k>0;k--){
                //今天不拥有=max(昨天不拥有，昨天拥有和今天卖出)，不计入交易次数
                dp_0_2_0=max(dp_0_2_0,dp_0_2_1+prices[i]);
                //今天拥有=max(昨天拥有，昨天不拥有和今天买入)，计入交易次数
                dp_0_2_1=max(dp_0_2_1,dp_0_1_0-prices[i]);
                dp_0_1_0=max(dp_0_1_0,dp_0_1_1+prices[i]);
                dp_0_1_1=max(dp_0_1_1,-prices[i]);
            }
        }

        return dp_0_2_0;

    }
};

oj输入

int main () {
    vector<int> prices;
    int num;
    while(1){
        cin>>num;
        prices.push_back(num);
        if(cin.get()=='\n') break;
    }

    Solution solution;
    cout<<"Max prices: "<<solution.maxProfit(prices)<<endl;


    return 0;
}

打家劫舍

4、309. 最佳买卖股票时机含冷冻期

动规

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();

        if(n<2){
            return 0;
        }

        vector<vector<int>> dp(n,vector<int>(2));

        dp[0][0]=0;
        dp[0][1]=-prices[0];
        dp[1][0]=max(dp[0][0],dp[0][1]+prices[1]);
        dp[1][1]=max(dp[0][1],dp[0][0]-prices[1]);

        for(int i=2;i<n;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-2][0]-prices[i]);
        }

        return dp[n-1][0];

    }
};

5、打家劫舍(一)

递归

class Solution {
public:
    //递归
    int rob(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n+1);

        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);

        for(int i=2;i<n;i++){
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }

        return dp[n-1];
    }
};

优化

class Solution {
public:
    //递归
    int rob(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n+1);

        int dp_0=nums[0];
        int dp_1=max(nums[0],nums[1]);

        for(int i=2;i<n;i++){
            int temp=max(dp_1,dp_0+nums[i]);
            dp_0=dp_1;
            dp_1=temp;
        }

        return dp_1;
    }
};

6、打家劫舍(二)

动态规划

class Solution {
public:
    vector<int> dp;
    int rob(vector<int>& nums) {
        int n=nums.size();
        dp.resize(n);        
        return max(helper(nums, 0, n-1),helper(nums, 1, n));
    }

    int helper(vector<int>& nums,int start,int end){
        dp[start]=nums[start];
        dp[start+1]=max(nums[start],nums[start+1]);

        for(int i=start+2;i<end;i++){
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[end-1];
    }
};

优化

class Solution {
public:
    vector<int> dp;
    int rob(vector<int>& nums) {
        int n=nums.size();
        dp.resize(n);        
        return max(helper(nums, 0, n-1),helper(nums, 1, n));
    }

    int helper(vector<int>& nums,int start,int end){
        int dp_0=nums[start];
        int dp_1=max(nums[start],nums[start+1]);

        for(int i=start+2;i<end;i++){
            int temp=max(dp_1,dp_0+nums[i]);
            dp_0=dp_1;
            dp_1=temp;
        }
        return dp_1;
    }
};

7、337. 打家劫舍 III

动规

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> res(2,0);//代表本节点偷不偷
        res=helper(root);
        return max(res[0],res[1]);     //找两种的最大值
    }

    vector<int> helper(TreeNode* root){
        vector<int> res(2,0);//代表本节点偷不偷

        if(root==NULL) return res;

        vector<int> left=helper(root->left);
        vector<int> right=helper(root->right);

         //本节点不偷
        res[0]=max(left[0],left[1])+max(right[0],right[1]);
        //本节点偷,两子不能偷
        res[1]=left[0]+right[0]+root->val;

        return res;
    }
};

8、最长公共子串

动态规划

class Solution {
public:
    //动态规划
    string LCS(string str1, string str2) {
        int n1=str1.length();
        int n2=str2.length();

        vector<vector<int>> dp(n1+1,vector<int>(n2+1));

        int index=0;
        int len=0;

        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                 //如果该两位相同， //则增加长度
                if(str1[i-1]==str2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    //该位置为0
                    dp[i][j]=0;
                }
                //更新最大长度
                if(dp[i][j]>len){
                    len=dp[i][j];
                    index=i-1;
                }
            }
        }
        return str1.substr(index-len+1,len);
    }
};

OJ

int main () {
    string x,y;
    cin>>x>>y;

    Solution solution;
    cout<<"Result: "<<solution.LCS(x,y)<<endl;

    return 0;
}

优化

class Solution {
public:
    //动态规划-状态压缩
    string LCS(string str1, string str2) {
        int n1=str1.length();
        int n2=str2.length();

        vector<int> dp(n2+1);

        int index=0;
        int len=0;        

        for(int i=1;i<=n1;i++){
            for(int j=n2;j>=0;j--){
                 //如果该两位相同， //则增加长度
                if(str1[i-1]==str2[j-1]){
                    dp[j]=dp[j-1]+1;
                }else{
                    //该位置为0
                    dp[j]=0;
                }
                //更新最大长度
                if(dp[j]>len){
                    len=dp[j];
                    index=i-1;
                }
            }
        }
        return str1.substr(index-len+1,len);
    }
};

9、最长公共子序列(二)

动态规划

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        int n1=s1.length();
        int n2=s2.length();

        vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));
        string res="";

        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(s1[i-1]==s2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        //从dp还原
        for(int i=n1,j=n2;dp[i][j]>0;){
            if(s1[i-1]==s2[j-1]){
                res+=s1[i-1];
                i--;j--;
            }else if(dp[i][j-1]>=dp[i-1][j]){
                j--;
            }else{
                i--;
            }
        }
        reverse(res.begin(),res.end());
        return res.empty()?"-1":res;

    }
};

另一种动规,内存超限

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        int n1=s1.length();
        int n2=s2.length();

        vector<vector<string>> dp(n1+1,vector<string>(n2+1,""));

        for(int i = 0; i <= n1; i++) {
            // j == 0
            dp[i][0] = "";
        }
        for(int j = 0; j <= n2; j++) {
            // i == 0
            dp[0][j] = "";
        }

        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(s1[i-1]==s2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+s1[i-1];
                }else{
                    dp[i][j]=dp[i-1][j].length()>=dp[i][j-1].length()?dp[i-1][j]:dp[i][j-1];
                }
            }
        }
        return dp[n1][n2].empty()?"-1":dp[n1][n2];

    }
};

9、最长上升子序列(一)

动规

class Solution {
public:
    int LIS(vector<int>& arr) {
        if(arr.size()<1) return 0;

        int n=arr.size();
        vector<int> dp(n,1); //初始化为0，自身序列为1
        int m_max=dp[0];

        for(int i=1;i<n;i++){
            //找 nums[i]之前的 dp最大
            for(int j=0;j<i;j++){
                if(arr[j]<arr[i]){
                    dp[i]=max(dp[j]+1,dp[i]);
                }
            }
            //找 dp[i]最大的
            m_max=max(m_max,dp[i]);
        }

        return m_max;
    }
};

10、最长回文子串

动规

class Solution {
public:
    int getLongestPalindrome(string A) {
        int n=A.length();

        vector<vector<bool>> dp(n+1,vector<bool>(n+1));
        int m_max=1;

        for(int i=n;i>0;i--){
            for(int j=i+1;j<=n;j++){
                // 对角线上
                if(i==j && A[i-1]==A[j-1]){
                    dp[i][j]=1; 
                }
                // 中间相差0或1个元素
                else if(j-i<=2 && A[i-1]==A[j-1] ){
                    dp[i][j]=1;
                }
                //相差多个元素
                else{
                    dp[i][j]=dp[i+1][j-1] && (A[i-1]==A[j-1]);
                }
                //看是不是最长
                if(dp[i][j]){
                    m_max=max(j-i+1,m_max);
                }
            }
        }
        return m_max;
    }
};

中心扩散

class Solution {
public:
    //中心扩散
    int getLongestPalindrome(string A) {
        int n=A.length();
        if(n<1) return 0;
        int m_max=1;
        //计算每一个中心扩散的最大值
        for(int i=0;i<n-1;i++){
            int len=max(centerSpread(A,i,i),centerSpread(A,i,i+1));
            m_max=max(len,m_max);
        }
        return m_max;
    }
    int centerSpread(string A,int left,int right){
        int n=A.length();
        while(A[left]==A[right] && left>=0 && right<=n-1 ){
            left--;right++;
        }
        //减去2是因为 这是两边已经不相等了
        return right-left+1-2;
    }
};

11、正则表达式匹配

动规

class Solution {
public:
    bool match(string str, string pattern) {
        int n1=str.length();
        int n2=pattern.length();
        //dp[i][j]表示str前i个字符和pattern前j个字符是否匹配
        vector<vector<bool>> dp(n1+1,vector<bool>(n2+1,false));
        //两个都为空串自然匹配
        dp[0][0]=true;
        //初始化str为空的情况，字符串下标从1开始
        for(int j=2;j<=n2;j++){
            if(pattern[j-1]=='*'){
                dp[0][j]=dp[0][j-2];
            }
        }        

        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                //当前字符不为*，用.去匹配或者字符直接相同
                if((str[i-1]==pattern[j-1] || pattern[j-1]=='.') && pattern[j-1]!='*'){
                    dp[i][j]=dp[i-1][j-1];
                }else if(pattern[j-1]=='*'&& j>=2){//当前的字符为*
                     //若是前一位为.或者前一位可以与这个数字匹配
                    if( pattern[j-2]=='.' || str[i-1]==pattern[j-2] ){
                        //转移情况
                        dp[i][j]=dp[i][j-2] || dp[i-1][j];
                    }else{
                        //不匹配
                        dp[i][j]=dp[i][j-2];
                    }
                }
            }
        }

        return dp[n1][n2];
    }
};

递归

class Solution {
public:
    //递归
    bool match(string str, string pattern) {
        if(pattern.empty()) return str.empty();
        bool firstMatch=!str.empty() && (str[0]==pattern[0]||pattern[0]=='.');

        if(pattern.length()>1 && pattern[1]=='*'){
            return match(str, pattern.substr(2)) || (firstMatch && match(str.substr(1),pattern));
        }else{
            return firstMatch && match(str.substr(1), pattern.substr(1));
        }

    }
};

递归+备忘录

class Solution {
public:
    //递归+备忘录
    map<pair<string,string>,bool> memo;
    bool match(string str, string pattern) {
        if(pattern.empty()) return str.empty();

        auto key=make_pair(str, pattern);
        if(memo.count(key)){
            return memo[key];
        }
        bool firstMatch=!str.empty() && (str[0]==pattern[0]||pattern[0]=='.');

        if(pattern.length()>1 && pattern[1]=='*'){
            memo[key] = match(str, pattern.substr(2)) || (firstMatch && match(str.substr(1),pattern));
        }else{
            memo[key] = firstMatch && match(str.substr(1), pattern.substr(1));
        }

        return memo[key];

    }
};

12、647. 回文子串

动规

class Solution {
public:
    int countSubstrings(string s) {
        int n=s.length();
        vector<vector<bool>> dp(n,vector<bool>(n,false));
        int res=0;

        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s[i]==s[j]){
                    if(j-i<=2){
                        dp[i][j]=true;
                        res++;
                    }else{
                        if(dp[i+1][j-1]){
                            dp[i][j]=true;
                            res++;
                        }
                    }
                }
            }
        }
        return res;
    }
};

13、跳台阶

动规优化

#include<iostream>
using namespace std;

class Solution{
public:
    int getStep(int n){
        if(n<2) return n;
        int dp_0=1,dp_1=2;
        for(int i=2;i<n;i++){
            int temp=dp_0+dp_1;
            dp_0=dp_1;
            dp_1=temp;
        }
        return dp_1;
    }
};

int main(){
    int n;
    cin>>n;
    Solution s;
    cout<<s.getStep(n)<<endl;
    return 0;
}

14、跳台阶扩展问题

递归

class Solution{
public:
    int getStep(int n){
        if(n<2) return n;
        int dp=1;
        //f(n)=2*f(n)
        for(int i=2;i<=n;i++){
            dp*=2;
        }
        return dp;
    }
};

15、32. 最长有效括号

动规-不推荐

class Solution {
public:
    int longestValidParentheses(string s) {
        int n=s.length();

        vector<int> dp(n,0);
        int m_max=0;

        for(int i=1;i<n;i++){
            if(s[i]==')'){
                if(s[i-1]=='(')
                    dp[i]=(i>=2?dp[i-2]:0)+2;
                else
                    dp[i]=dp[i-1]+((i-dp[i-1])>=2?dp[i-dp[i-1]-2]:0)+2;

                m_max=max(m_max,dp[i]);
            }
        }
        return m_max;

    }
};

栈

class Solution {
public:
    int longestValidParentheses(string s) {
        int m_max=0;
        stack<int> st;
        st.push(-1);
        for(int i=0;i<s.length();i++){
            if(s[i]=='('){
                st.push(i);
            }else{
                st.pop();
                if(st.empty()){
                    st.push(i);
                }else{
                    m_max=max(i-st.top(),m_max);
                }
            }
        }
        return m_max;
    }
};

16、连续子数组最大和

动规优化

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    int maxSubArray(int n,vector<int>& nums) {
        //define  dp[i]是以num[i]结尾的最大序列和
        int pre=nums[0];
        int m_max=nums[0];
        for(int i=1;i<n;i++){
            pre=max(pre+nums[i],nums[i]);
            m_max=max(m_max,pre);
        }
        return m_max;
    }
};

int main(){
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    Solution s;
    cout<<s.maxSubArray(n, arr)<<endl;
    return 0;
}

17、不同路径的数目(一)

动规

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n));

        for(int i=0;i<m;i++) dp[i][0]=1;
        for(int j=0;j<n;j++) dp[0][j]=1;

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

18、矩阵的最小路径和

动规

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        int m=matrix.size(),n=matrix[0].size();
        vector<vector<int>> dp(m,vector<int>(n));
        int m_min=0;

        dp[0][0]=matrix[0][0];

        for(int i=1;i<m;i++){
            dp[i][0]=dp[i-1][0]+matrix[i][0];
        }
        for(int j=1;j<n;j++){
            dp[0][j]=dp[0][j-1]+matrix[0][j];
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=min(dp[i][j-1],dp[i-1][j])+matrix[i][j];
            }
        }
        return dp[m-1][n-1];

    }
};

19、计算字符串的编辑距离

动规

#include<iostream>
#include<vector>
using namespace std;
class Solution{
public:
    int editDistance(string& str1,string& str2){
        int n1=str1.length(),n2=str2.length();
        vector<vector<int>> dp(n1+1,vector<int>(n2+1));

        for(int i=0;i<n1+1;i++) dp[i][0]=i;
        for(int j=0;j<n2+1;j++) dp[0][j]=j;

        for(int i=1;i<n1+1;i++){
            for(int j=1;j<n2+1;j++){
                if(str1[i-1]!=str2[j-1])
                    dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
                else
                    dp[i][j]=dp[i-1][j-1];
            }
        }

        return dp[n1][n2];
    }
};

int main(){
    string str1="",str2="";
    cin>>str1>>str2;
    Solution s;
    cout<<s.editDistance(str1, str2);
    return 0;
}

20、连续子数组的最大乘积

动规

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int m_max=INT_MIN;

        int pre_max=1; //记录当前i的最大乘积
        int pre_min=1; //记录当前i的最小乘积

        for(int i=0;i<nums.size();i++){
            if(nums[i]<0){
                int temp=pre_max;
                pre_max=pre_min;
                pre_min=temp;
            }
            //不达到要求，清空重来
            pre_max=max(pre_max*nums[i],nums[i]);
            pre_min=min(pre_min*nums[i],nums[i]);    
            m_max=max(m_max,pre_max);
        }
        return m_max;
    }
};

21、兑换零钱(一)

动规

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型vector the array
     * @param aim int整型 the target
     * @return int整型
     */
    int minMoney(vector<int>& arr, int aim) {
        int n=aim;
        vector<int> dp(n+1,INT_MAX);

        dp[0]=0;

        for(int i=1;i<n+1;i++){
            for(int j=0;j<arr.size();j++){
                if(arr[j]<=i){
                    dp[i]=min(dp[i-arr[j]]+1,dp[i]);
                }
            }
        }
        return dp[aim]==INT_MAX?-1:dp[aim];
    }
};

22、最大正方形

动规

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最大正方形
     * @param matrix char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& matrix) {
        if(matrix.size()==0||matrix[0].size()==0) return 0;
        int m=matrix.size(),n=matrix[0].size();
        vector<vector<int>> dp(m,vector<int>(n));
        int maxSide=0;

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                    if(i==0||j==0) dp[i][j]=1;
                    else dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    maxSide=max(maxSide,dp[i][j]);
                }
            }
        }
        return maxSide*maxSide;
    }
};

23、最大矩形

动规

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> 
     * @return int整型
     */
    int maximalRectangle(vector<vector<int> >& matrix) {
        if(matrix.size()==0||matrix[0].size()==0) return 0;
        int m=matrix.size(),n=matrix[0].size();
        vector<vector<int>> dp(m,vector<int>(n));
        int maxSize=0;

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                //找横着最长的1
                if(matrix[i][j]==1){
                    if(j==0){
                        dp[i][j]=1;
                    }else{
                        dp[i][j]=dp[i][j-1]+1;
                    }
                }else{
                    dp[i][j]=0;
                }
                //高度上进行扩展,同时计算最大面积
                int width=dp[i][j];
                int area=width*1;
                for(int h=i-1;h>=0;h--){
                    int height=i-h+1;
                    width=min(width,dp[h][j]);
                    area=max(area,height*width);                        
                } 
                maxSize=max(area,maxSize);

            }
        }

        return maxSize;
    }
};

栈

只在力扣通过

class Solution {
public:
    int maximalRectangle(vector<vector<int> >& matrix) {
        if(matrix.size()==0) return 0;
        int area=0;
        int m=matrix.size(),n=matrix[0].size();
        vector<int> heights(n,0);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                    heights[j]+=1;
                }else{
                    heights[j]=0;
                }
            }
            area=max(area,largestRectangleArea(heights));
        }
        return area;
    }

    int largestRectangleArea(vector<int> heights) {
        int res=0;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        stack<int> s;
        for(int i=0;i<heights.size();i++){
            while(!s.empty() && heights[s.top()] > heights[i] ){
                int cur=s.top();
                s.pop();
                int left=s.top()+1;
                int right=i-1;
                res=max(res,(right-left+1)*heights[cur]);
            }
            s.push(i);
        }
        return res;
    }
};

24、目标和

动规

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        //neg=(sum-target)/2;
        if(nums.size()<1) return 0;
        int n=nums.size();
        int sum=0;
        for(int num:nums) sum+=num;
        int diff=sum-target;
        if(diff<0||diff%2!=0) return 0;

        diff/=2;

        vector<vector<int>> dp(n+1,vector<int>(diff+1));
        dp[0][0]=1;

        for(int i=1;i<=n;i++){
            for(int j=0;j<=diff;j++){
                if(nums[i-1]<=j){
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
                }else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }

        return dp[n][diff];
    }
};

回溯法

class Solution {
public:
    int res=0;
    int findTargetSumWays(vector<int>& nums, int target) {
        backtracing(nums, target, 0, 0);
        return res;
    }

    void backtracing(vector<int>& nums, int target,int sum,int index){
        if(nums.size()<1){
            res=0;
            return;
        }
        if(index==nums.size()){
            if(sum==target)
                res++;
        }else{
            backtracing(nums, target, sum+nums[index], index+1);
            backtracing(nums, target, sum-nums[index], index+1);  
        }             
    }
};

25、最少的完全平方数

动规

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,0);
        dp[0]=0;
        for(int i=1;i<=n;i++){
            int m_min=INT_MAX;//记录本层的最小
            for(int j=1;j*j<=i;j++){
                dp[i]=min(m_min,dp[i-j*j]+1);
                m_min=min(m_min,dp[i-j*j]+1);
            };
        }
        return dp[n];
    }
};

26、单词拆分(一)

动规

class Solution {
public:
    bool wordDiv(string s, vector<string>& dic) {
        int n=s.length();
        unordered_set<string> hashSet;
        for(auto& d:dic){
            hashSet.insert(d);
        }

        vector<bool> dp(n+1);
        dp[0]=true;
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                //在哈希表中找到该串
                if(hashSet.count(s.substr(j,i-j)) && dp[j]){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

27、338. 比特位计数

动规

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n+1);
        //正整数 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，因此 y & (y−1)=0
        int highbit=0;
        for(int i=1;i<=n;i++){
            if((i&(i-1))==0)
                highbit=i;
            dp[i]=dp[i-highbit]+1;
        }
        return dp;
    }
};

28、分割等和子集

动规

class Solution {
public:
    bool partition(vector<int>& nums) {
        int n=nums.size();

        int sum=0;
        for(int num: nums) sum+=num;
        if(sum<0||sum%2!=0) return false;

        sum/=2;
        vector<vector<bool>> dp(n+1,vector<bool>(sum+1,false));

        for(int i=0;i<=n;i++) dp[i][0]=true;

        for(int i=1;i<=n;i++){
            for(int j=0;j<=sum;j++){
                if(nums[i-1]<=j){
                    dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[n][sum];
    }
};

29、接雨水问题

动规

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        //dp找每个单元左右两边的最大值
        int n=arr.size();
        if(n<3) return 0;

        vector<int> dp_left(n+1),dp_right(n+1);

        for(int i=1;i<n;i++){
            dp_left[i]=max(dp_left[i-1],arr[i-1]);
        }
        for(int i=n-2;i>=0;i--){
            dp_right[i]=max(dp_right[i+1],arr[i+1]);
        }

        int res=0;
        for(int i=1;i<n-1;i++){
            int curHeight=min(dp_left[i],dp_right[i]);
            if(curHeight>arr[i]){
                res+=curHeight-arr[i];
            }
        }
        return res;
    }
};

栈

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        stack<int> s;
        int n=arr.size();
        int res=0;
        for(int i=0;i<n;i++){
            while(!s.empty() && arr[i]>arr[s.top()]){
                int top=s.top();
                s.pop();
                if(s.empty()) break;

                int wid=i-s.top()-1;
                int hei=min(arr[i],arr[s.top()])-arr[top];;

                res+=wid*hei;
            }
            s.push(i);            
        }
        return res;
    }
};

30、312. 戳气球

动规

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n=nums.size();
        vector<int> val(n+2);
        vector<vector<int>> res(n+2,vector<int>(n+2));
        for(int i=1;i<=n;i++) val[i]=nums[i-1];
        val[0]=1;val[n+1]=1;

        for(int i=n-1;i>=0;i--){
            for(int j=i+2;j<=n+1;j++){
                for(int k=i+1;k<j;k++){
                    int sum=val[i]*val[k]*val[j];
                    sum+=res[i][k]+res[k][j];
                    res[i][j]=max(res[i][j],sum);
                }
            }
        }
        return res[0][n+1];
    }
};

31、 238. 除自身以外数组的乘积(No)

动规

class Solution {
public:    
    //L*R
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> L(n,0),R(n,0);
        vector<int> res(n);

        L[0]=1;
        R[n-1]=1;
        for(int i=1;i<n;i++){
            L[i]=L[i-1]*nums[i-1];
        }
        for(int i=n-2;i>=0;i--){
            R[i]=R[i+1]*nums[i+1];
        }
        for(int i=0;i<n;i++){
            res[i]=L[i]*R[i];
        }
        return res;
    }
};

优化

class Solution {
public:
    //L*R 空间压缩至O(1)
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> res(n);

        res[0]=1;
        for(int i=1;i<n;i++){
            res[i]=res[i-1]*nums[i-1];
        }
        int R=1;
        for(int i=n-1;i>=0;i--){
            res[i]*=R;
            R*=nums[i];
        }
        return res;
    }
};

32、139. 单词拆分(No)

动规

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        auto wordDictSet = unordered_set <string> ();
        for (auto word: wordDict) {
            wordDictSet.insert(word);
        }

        auto dp = vector <bool> (s.size() + 1);
        dp[0] = true;
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.size()];
    }
};

哈希表

1、两数之和

哈希表

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int,int> hashMap;
        for(int i=0;i<numbers.size();i++){
            if(hashMap.count(target-numbers[i]))
                return {hashMap[target-numbers[i]],i+1};
            hashMap.insert({numbers[i],i+1});
        }
        return {};
    }
};

2、数组中出现次数超过一半的数字

哈希表

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> hashMap;
        for(int &num:nums){
            hashMap[num]++;
            if(hashMap[num]>nums.size()/2){
                return num;
            }
        }
        return -1;
    }
};

Boyer Moore算法

class Solution {
public:
    //Boyer Moore算法 有待研究。同归于尽法
    //先来的小兵占据阵营，后来的是同一个阵营++，不是--，当兵力全无，新士兵成为领主，最终剩下的必然是众数
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int can=-1;
        int cnt=0;
        for(int i=0;i<numbers.size();i++){
            if(numbers[i]==can)
                cnt++;
            else{
                cnt--;
                if(cnt<0){
                    can=numbers[i];
                    cnt=1;
                }
            }
        }
        return can;
    }
};

3、数组里面没有出现过的数字

哈希表

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        unordered_set<int> hashMap;
        for(int& num:nums){
            hashMap.insert(num);
        }
        for(int i=1;i<=nums.size();i++){
            if(!hashMap.count(i))
                res.push_back(i);
        }
        return res;

    }
};

4、49. 字母异位词分组(No)

哈希表

class Solution {
public:
     //map 排序
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        //map第一个key放排序结果，value放排序前的词，可能有多个
        unordered_map<string,vector<string>> mp;
        for(string& str:strs){
            string key=str;
            sort(key.begin(),key.end());
            mp[key].emplace_back(str);//直接在尾部创建，而非push_back那样 创建-复制
        }

        vector<vector<string>> res;
        for(auto it=mp.begin();it!=mp.end();it++){
            res.emplace_back(it->second);
        }
        return res;
    }
};

5、 128. 最长连续序列(No)

class Solution {
public:
    //枚举法
    //找每个元素x 的+1、+2、+3看是否存在
    //放入hash表中,将O(n)--->O(n)
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        for(const int &num:nums){
            num_set.insert(num);
        }
        int res=0;

        for(const int &num:nums){
            //
            if(!num_set.count(num-1)){
                int y=num;
                while(num_set.count(y+1)){
                    y++;
                }
                res=max(res,y-num+1);
            }
        }
        return res;
    }
};

6、 136. 只出现一次的数字(No)

哈希表

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> map;
        for(int &num:nums){
            map[num]++;
        }
        for(int &num:nums){
            if(map[num]==1){
                return num;
            }
        }
        return 0;
    }
};

按位异或

异或运算有以下三个性质。

• 任何数和 0 做异或运算，结果仍然是原来的数。
• 任何数和其自身做异或运算，结果是 0。
• 异或运算满足交换律和结合律。

经过两次异或，number变为0；

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result=0;
        for(int &num:nums){
            result^=num;
        }
        return result;
    }
};

7、560. 和为 K 的子数组(No)

哈希表+前缀和

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        //定义哈希表存放前缀和
        unordered_map<int,int> preSum;
        preSum[0]=1;
        //转换为 preSum[j]==preSum[i]-k;
        int count=0,sum_i=0;
        for(int i=0;i<nums.size();i++){
            sum_i+=nums[i];
            //nums[0...j]
            int sum_j=sum_i-k;
            //如果前边有这个前缀和，直接更新
            if(preSum[sum_j]!=0){
                count+=preSum[sum_j];
            }
            //把nums[0...i]加入preSum中
            preSum[sum_i]++;
        }
        return count;
    }
};

栈与队列

1、每日温度

栈

class Solution {
public:
    vector<int> temperatures(vector<int>& dailyTemperatures) {
        int n=dailyTemperatures.size();
        vector<int> res(n);
        stack<int> s;

        for(int i=n-1;i>=0;i--){
            while(!s.empty() && dailyTemperatures[i]>=dailyTemperatures[s.top()]){
                s.pop();
            }
            res[i]=s.empty()?0:(s.top()-i);
            s.push(i);
        }
        return res;
    }
};

2、155. 最小栈

栈

class MinStack {
private:
    stack<int> s;
    stack<int> ms;
public:
    MinStack() {
        while(!s.empty()) s.pop();
        while(!ms.empty()) s.pop();
        ms.push(INT_MAX);
    }

    void push(int val) {
        s.push(val);
        ms.push(min(val,ms.top()));
    }

    void pop() {
        s.pop();
        ms.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return ms.top();
    }
};

栈+map

class MinStack {
private:
    stack<pair<int,int>> s;
public:
    MinStack() {        
        if(!s.empty()) s.pop();
    }

    void push(int val) {
        if(s.empty()) s.push(make_pair(val,val));
        else s.push(make_pair(val,min(val,s.top().second)));
    }

    void pop() {
        s.pop();
    }

    int top() {
        return s.top().first;
    }

    int getMin() {
        return s.top().second;
    }
};

3、有效括号序列

栈

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;
        for(int i=0;i<s.length();i++){
            if(s[i]=='(')    st.push(')');
            else if(s[i]=='[')    st.push(']');
            else if(s[i]=='{')    st.push('}');
            else if(!st.empty() && s[i]==st.top()) st.pop();
            else return false;
        }
        return st.empty();
    }
};

4、直方图内最大矩形

栈

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res=0;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        stack<int> s;
        for(int i=0;i<heights.size();i++){
            while(!s.empty() && heights[s.top()]>heights[i]){
                int top=s.top();
                s.pop();
                int right=i-1;
                int left=s.top()+1;
                int wid=right-left+1;
                res=max(res,heights[top]*wid);
            }
            s.push(i);
        }
        return res;
    }
};

5、字符串解码

栈

class Solution {
public:
    string decodeString(string s) {
        int n=s.length();
        stack<int> nums;
        stack<string> strs;

        int num=0;
        string str="";

        for(int i=0;i<n;i++){
            if(s[i]>='0' && s[i]<='9'){
                num=num*10+s[i]-'0';
            }else if((s[i]>='a' && s[i]<='z')||(s[i]>='A' && s[i]<='Z')){
                str.push_back(s[i]);            
            }else if(s[i]=='['){
                nums.push(num);
                num=0;
                strs.push(str);
                str="";
            }else if(s[i]==']'){
                int cnt=nums.top();
                nums.pop();
                while(cnt--){
                    strs.top()+=str;
                }
                str=strs.top();
                strs.pop();
            }
        }
        return str;
    }
};

6、239. 滑动窗口最大值(No)

队列

class Solution {
private:
    class MyQueue{
    //保证队列第一个元素为最大的,队列递减
    public:
        deque<int> d;
        void push(int value){
            while(!d.empty()&&value>d.back()){
                d.pop_back();
            }
            d.push_back(value);
        }
        void pop(int value){
            if(!d.empty()&&value==d.front()){
                d.pop_front();
            }
        }
        int getMax(){
            return d.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue mq;
        vector<int> result;

        for(int i=0;i<k;i++){
            mq.push(nums[i]);         
        }
        result.push_back(mq.getMax());

        for(int i=k;i<nums.size();i++){
            mq.pop(nums[i-k]);            
            mq.push(nums[i]);
            result.push_back(mq.getMax());
        }
        return result;
    }
};

回溯法

1、没有重复项数字的全排列

回溯

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used;
    vector<vector<int> > permute(vector<int> &num) {
        used.resize(num.size(),false);
        backtracing(num);
        return res;
    }

    void backtracing(vector<int>& num){
        if(path.size()==num.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<num.size();i++){
            if(used[i]){
                continue;
            }
            used[i]=true;
            path.push_back(num[i]);
            backtracing(num);
            used[i]=false;
            path.pop_back();
        }       
    }
};

47. 全排列 II

动规

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        used.resize(nums.size(),false);
        backtracing(nums);
        return res;        
    }

    void backtracing(vector<int>& num){
        if(path.size()==num.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<num.size();i++){
            if(i>0 && num[i]==num[i-1] && used[i-1]){
                continue;
            }
            if(used[i]==false){
                used[i]=true;
                path.push_back(num[i]);
                backtracing(num);
                used[i]=false;
                path.pop_back();
            }

        }       
    }
};

2、加起来和为目标值的组合

回溯

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int> > combinationCount(int target, vector<int>& nums) {
        backtracing(nums,target,0,0);
        return res;
    }

    void backtracing(vector<int>& candidates, int target,int sum,int start){
        if(sum>target) return;
        if(sum==target){
            res.push_back(path);
            return;
        }

        for(int i=start;i<candidates.size();i++){
            path.push_back(candidates[i]);
            sum+=candidates[i];

            backtracing(candidates,target,sum,i);

            sum-=candidates[i];
            path.pop_back();
        }
    }
};

3、电话号码的字母组合

回溯

class Solution {
public:
    const string letterMap[10]={
        "","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"
    };
    vector<string> res;
    string path;
    vector<string> phoneNumber(string num) {
        if(num.length()==0) return res;
        backtracing(num, 0);
        return res;
    }
    void backtracing(string num,int index){
        if(index==num.length()){
            res.push_back(path);
            return;
        }
        int digit=num[index]-'0';
        string letter=letterMap[digit];
        for(int i=0;i<letter.length();i++){
            path.push_back(letter[i]);
            backtracing(num,index+1);
            path.pop_back();
        }
    }
};

4、131. 分割回文串

回溯

class Solution {
public:
    vector<vector<string>> res;
    vector<string> path;
    vector<vector<string>> partition(string s) {
        backtracing(s,0);
        return res;
    }
    void backtracing(string s,int start){
        if(start>=s.length()){
            res.push_back(path);
            return;
        }
        for(int i=start;i<s.length();i++){
            string str=s.substr(start,i-start+1);
            if(!isValid(str))
                continue;
            else 
                path.push_back(str);
            //都要回溯
            backtracing(s,i+1);
            path.pop_back();
        }
    }
    bool isValid(string s){
        for(int i=0,j=s.length()-1;i<j;i++,j--){
            if(s[i]!=s[j])
                return false;
        }
        return true;
    }
};

5、集合的所有子集(一)

回溯

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int> > subsets(vector<int> &S) {
        backtracing(S, 0);
        return res;
    }
    void backtracing(vector<int> &S,int start){
        res.push_back(path);
        if(start>=S.size()){
            return;
        }
        for(int i=start;i<S.size();i++){
            path.push_back(S[i]);
            backtracing(S,i+1);
            path.pop_back();
        }
    }
};

6、岛屿数量

深度优先遍历

class Solution {
public:
    int solve(vector<vector<char> >& grid) {
        int res=0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j]=='1'){
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }

    void dfs(vector<vector<char> >& grid,int i,int j){
        int m=grid.size(),n=grid[0].size();
        if(i<0||i>=m||j<0||j>=n) return;
        if(grid[i][j]=='0') return;
        grid[i][j]='0';//变海水，避免再次遍历
        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
    }

};

并查集

class Solution {
public:
    class UF{
    private:
        vector<int> parent;
        vector<int> weight;
        int count;
    public:
        UF(vector<vector<char> >& grid){
            int m=grid.size(),n=grid[0].size();
            count=0;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(grid[i][j]=='1'){
                        parent.push_back(i*n+j);
                        count++;
                    }else{
                        parent.push_back(-1);
                    }
                    weight.push_back(0);
                }
            }
        }
        int find(int x){
            while(parent[x]!=x){
                parent[x]=parent[parent[x]];
                x=parent[x];
            }
            return x;
        }
        void myunion(int x,int y){
            int rootX=find(x);
            int rootY=find(y);
            if(rootX==rootY) return;
            if(weight[rootX]<weight[rootY]){
                parent[rootX]=rootY;
                weight[rootY]++;
            }
            else{
                parent[rootY]=rootX;
                weight[rootX]++;
            }
            count--;
        }
        int getCount() const{
            return count;
        }
    };
    int solve(vector<vector<char> >& grid) {
        int m=grid.size(),n=grid[0].size();
        UF uf(grid);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    grid[i][j]='0';
                    if(i-1>=0 && grid[i-1][j]=='1') uf.myunion((i-1)*n+j,i*n+j);
                    if(i+1<m && grid[i+1][j]=='1') uf.myunion((i+1)*n+j,i*n+j);
                    if(j-1>=0 && grid[i][j-1]=='1') uf.myunion(i*n+j-1,i*n+j);
                    if(j+1<n && grid[i][j+1]=='1') uf.myunion(i*n+j+1,i*n+j);                    
                }
            }
        }
        return uf.getCount();
    }
};

7、单词搜索

回溯法

class Solution {
public:
    bool exist(vector<string>& board, string word) {
        int m=board.size(),n=board[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(dfs(board,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<string>& board, string word,int i,int j,int index){
        int m=board.size(),n=board[0].size();
        if(board[i][j]!=word[index]) return false;
        if(index==word.length()-1){
            return true;
        }
        char temp=board[i][j];
        board[i][j]=0;
        if((i-1>=0&&dfs(board, word,i-1, j, index+1))||
                (i+1<m && dfs(board, word,i+1, j, index+1))||
                (j-1>=0 && dfs(board, word,i, j-1, index+1))||
                (j+1<n && dfs(board, word,i, j+1, index+1)))
           return true;
        board[i][j]=temp;
        return false;
    }
};

8、括号生成

回溯

class Solution {
public:
    vector<string> res;
    vector<string> generateParenthesis(int n) {
        dfs(n,0,0,"");
        return res;
    }
    void dfs(int n,int lc,int rc,string str){
        // 添加左括号，左括号数量要足够，添加右括号，右括号数量要足够，且左括号数要大于右括号数
        if(lc==n && rc==n) res.push_back(str);
        if(lc<n)
            dfs(n,lc+1,rc,str+"(");
        if(rc<n && lc>rc)
            dfs(n,lc,rc+1,str+")");        
    }
};

9、 301. 删除无效的括号(No)

回溯+剪枝

class Solution {
public:
     //回溯+剪枝
    vector<string> res;
    vector<string> removeInvalidParentheses(string s) {
        int lremove=0,rremove=0;
        for(char c:s){
            if(c=='(')
                lremove++;
            else if(c==')'){
                if(lremove==0) rremove++;
                else lremove--;
            }
        }
        helper(s,0,0,0,lremove,rremove);
        return res;
    }

    void helper(string s,int start,int lcount,int rcount,int lremove,int rremove){
        if(lremove==0 && rremove==0){
            if(isValid(s)){
                res.push_back(s);
            }
            return;
        }
        for(int i=start;i<s.length();i++){
            char cur=s[i];
            if(i==start||cur!=s[i-1]){
                //如果剩下的字符不能满足字数要求，直接返回，剪枝
                if(lremove+rremove>s.length()-i) return;
                //尝试去掉一个左括号
                if(lremove>0 && s[i]=='('){
                    helper(s.substr(0,i)+s.substr(i+1),i,lcount,rcount,lremove-1,rremove);
                }
                if(rremove>0 && s[i]==')'){
                    helper(s.substr(0,i)+s.substr(i+1),i,lcount,rcount,lremove,rremove-1);
                }
            }
            if(cur=='(') lcount++;
            else if(cur==')') rcount++;
            else if(lcount<rcount) break;  
        }      
    }
    bool isValid(const string& s){
        int cnt=0;
        for(int i=0;i<s.length();i++){
            if(s[i]=='(') cnt++;
            else if(s[i]==')'){
                cnt--;
                if(cnt<0){
                    return false;
                }
            }
        }
        return cnt==0;
    }
};

深度优先遍历

class Solution {
public:
    //bfs:每一轮删除字符串中的 11 个括号，直到出现合法匹配的字符串为止
    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        unordered_set<string> currSet;

        currSet.insert(s);
        while(true){
            for(auto &str:currSet){
                if(isValid(str)){
                    res.emplace_back(str);
                }
            }

            if(res.size()>0){
                return res;
            }
            //接下来要遍历的set
            unordered_set<string> nextSet;
            for(auto &str:currSet){
                for(int i=0;i<str.size();i++){
                    if(i>0 && str[i]==str[i-1]) continue;
                    if(str[i]==')'||str[i]=='('){
                        nextSet.insert(str.substr(0,i)+str.substr(i+1));
                    }
                }
            }
            currSet=nextSet;
        }
    }

    bool isValid(string s){
        int cnt=0;
        for(int i=0;i<s.length();i++){
            if(s[i]=='('){
                cnt++;
            }else if(s[i]==')'){
                cnt--;
                if(cnt<0){
                    return false;
                }
            }
        }
        return cnt==0;
    }
};

排序算法

1、406. 根据身高重建队列

双排序

class Solution {
public:
    //根据第一个元素降序，第二个元素升序排列
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),[](const vector<int>& u,const vector<int>& v){
            return u[0]>v[0] || (u[0]==v[0]&&u[1]<v[1]);
        });
        //依次插入队列，根据第二元素
        vector<vector<int>> res;
        for(const vector<int>& v:people){
            res.insert(res.begin()+v[1],v);
        }
        return res;
    }
};

2、 215. 数组中的第K个最大元素(No)

内置排序

class Solution {
public:
    //内置排序
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()-k];
    }
};

快排

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        quickSort(nums,0,nums.size()-1);
        return nums[nums.size()-k];
    }
    //快排
    void quickSort(vector<int>& nums,int left,int right){
        if(left<right){
            int mid=partition(nums,left,right);
            quickSort(nums,left,mid-1);
            quickSort(nums,mid+1,right);
        }
    }
    int partition(vector<int>& nums,int left,int right){
        int priot=nums[left];
        int i=left+1,j=right;
        while(1){
            while(i<=j && nums[i]<=priot) i++;
            while(i<=j && nums[j]>=priot) j--;
            if(i>=j) break;
            swap(nums[i],nums[j]);
        }
        nums[left]=nums[j];
        nums[j]=priot;
        return j;
    }
};

快排优化

class Solution {
public:
    //快速排序，随机选择中轴元素
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0));
        quickSort(nums,0,nums.size()-1);
        return nums[nums.size()-k];
    }
    //快排
    void quickSort(vector<int>& nums,int left,int right){
        if(left<right){
            int mid=partition(nums,left,right);
            quickSort(nums,left,mid-1);
            quickSort(nums,mid+1,right);
        }
    }
    int partition(vector<int>& nums,int left,int right){
        //随机选择中轴元素
        int a=rand()%(right-left+1)+left;
        swap(nums[left],nums[a]);

        int priot=nums[left];
        int i=left+1,j=right;
        while(1){
            while(i<=j && nums[i]<=priot) i++;
            while(i<=j && nums[j]>=priot) j--;
            if(i>=j) break;
            swap(nums[i],nums[j]);
        }
        nums[left]=nums[j];
        nums[j]=priot;
        return j;
    }
};

堆排序

class Solution {
public:
    //堆排序
    int findKthLargest(vector<int>& nums, int k) {
        //建立大根堆
        int　n=nums.size();
        for(int i=n/2-1;i>=0;i--){
            downAdjust(nums,i,n-1);
        }
        //pop k-1个元素
        for(int i=n-1;i>=n-k+1;i--){
            swap(nums[0],nums[i]);
            downAdjust(nums,0,i-1);
        }
        return nums[0];

    }
    void downAdjust(vector<int>& nums,int parent,int length){
        int child=2*parent+1;
        int temp=nums[parent];
        while(child<=length){
            //左右子节点中较大的一个与其交换
            if(child+1<=length && nums[child+1]>nums[child]){
                child++;
            }
            if(temp>=nums[child]) break;
            nums[parent]=nums[child];
            parent=child;
            child=2*parent+1;
        }
        nums[parent]=temp;//完成下沉 赋值
    }
};

3、 34. 在排序数组中查找元素的第一个和最后一个位置(No)

二分法

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftBorder=getLeftBorder(nums,target);
        int rightBorder=getRightBorder(nums,target);
        if(leftBorder==-2||rightBorder==-2){
            return {-1,-1};
        }
        if(rightBorder-leftBorder>1){
            return {leftBorder+1,rightBorder-1};   //注意下标
        }
        return {-1,-1};        
    }
    //分别寻找左右边界
    //寻找左边界
    int getLeftBorder(vector<int>& nums, int target){
        int left=0,right=nums.size()-1;
        int leftBorder=-2;
        while(left<=right){
            int middle=left+(right-left)/2;
            if(nums[middle]>=target){   //锁定左边边界，不断向左收缩
                right=middle-1;
                leftBorder=right;
            }else{
                left=middle+1;
            }
        }
        return leftBorder;
    }
    //寻找右边界
    int getRightBorder(vector<int>& nums, int target){
        int left=0,right=nums.size()-1;
        int rightBorder=-2;
        while(left<=right){
            int middle=left+(right-left)/2;
            if(nums[middle]>target){  
                right=middle-1;
            }else{  //锁定右边边界，不断向右收缩, nums[middle] == target的时候更新left
                left=middle+1;
                rightBorder=left;
            }
        }
        return rightBorder;
    }
};

4、347. 前 K 个高频元素(No)

堆排序

class Solution {
public:
    class myComparison{
    public:
        bool operator()(const pair<int,int>& a,const pair<int,int>& b){
            return a.second>b.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        //map的key为num,value为freq
        unordered_map<int,int> map;
        for(int i=0;i<nums.size();i++){
            map[nums[i]]++;
        }

        //根据map的freq进行排序，小堆树
        //定义 priority_queue<数据类型、底层容器、比较函数>
        priority_queue<pair<int,int>,vector<pair<int,int>>,myComparison> pri_que;
        for(auto it=map.begin();it!=map.end();it++){
            pri_que.push(*it);
            if(pri_que.size()>k){
                pri_que.pop(); //满k个后弹出freq低的
            }
        }

        //输出priority_queue剩下的k个
        vector<int> result(k);
        for(int i=k-1;i>=0;i--){
            result[i]=pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};

滑动窗口

1、最长不含重复字符的子字符串

滑动窗口

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        int res=0;
        unordered_map<char, int> window;
        int left=0,right=0;//起初窗口为0
        //不断扩大窗口，即right++
        while(right<s.length()){
            //把这个字符加入窗口，看是否符合条件，不符合，收缩窗口
            // 进行窗口内数据的一系列更新
            char c=s[right];
            right++;
            window[c]++;
            while(window[c]>1){
                // 进行窗口内数据的一系列更新
                char d=s[left];
                window[d]--;
                left++;
            }
            //取最长,// 在这里更新答案，在判断完是否有重复元素后再更新
            res=max(res,right-left);
        }
        return res;
    }
};

2、最小覆盖子串

滑动窗口

class Solution {
public:
    string minWindow(string S, string T) {
        unordered_map<char, int> need,window;
        for(char& c:T) need[c]++;

        int left=0,right=0;
        int min_len=INT_MAX;
        int valid_len=0;
        int start_index=0;

        while(right<S.length()){
            //尝试扩大窗口
            char c=S[right];
            right++;
            if(need.count(c)){
                window[c]++;
                //窗口内字符数和 所需相同，说明已覆盖
                if(window[c]==need[c]){
                    valid_len++;
                }
            }

            //缩小窗口，但要满足最小覆盖的原则
            while(need.size()==valid_len){
                //更新最小长度
                if(right-left<min_len){
                    min_len=min(right-left,min_len);
                    start_index=left;
                }
                //尝试缩小窗口
                char d=S[left];
                left++;
                //如果舍掉的是所需字符，更新相关数据
                if(need.count(d)){
                    if(window[d]==need[d]){
                        valid_len--;
                    }
                    window[d]--;                    
                }               

            }           

        }
        return min_len==INT_MAX?"":S.substr(start_index,min_len);
    }
};

3、找到字符串中的异位词

滑动窗口

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        unordered_map<char, int > window,need;
        for(char c:p) need[c]++;

        int left=0,right=0;
        int valid_len=0;

        while(right<s.length()){
            //尝试扩大窗口
            char c=s[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(need[c]==window[c]){
                    valid_len++;
                }
            }

            while(right-left>=p.size()){
                if(valid_len==need.size()){
                    res.push_back(left);
                }
                char d=s[left];
                left++;
                if(need.count(d)){
                    if(need[d]==window[d]){
                        valid_len--;
                    }
                    window[d]--;
                }

            }
        }
        return res;
    }
};

双指针

1、4. 寻找两个正序数组的中位数(No)

合并+排序

class Solution {
public:
    //先合并，在排序，然后找中位数
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        for(int &num:nums2){
            nums1.push_back(num);
        }
        sort(nums1.begin(),nums1.end());
        int n=nums1.size();
        if(n%2==1){
            return nums1[n/2];
        }else{
            //除以2.0
            return (nums1[n/2-1]+nums1[n/2])/2.0;
        }
    }
};

双指针

class Solution {
public:
    //双指针，找count为中间的
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        //定义两个指针指向两个数组,pre记录前一数，cur记录现在访问的数
        int i=0,j=0,pre=-1,cur=-1;
        //index记录访问的总个数,当为一半时返回，注意分奇偶
        int index=0;

        int n1=nums1.size(),n2=nums2.size();
        int n=n1+n2;
        while(index<((n>>1)+1)){
            pre=cur; 
            if(i<n1&&j<n2){
                if(nums1[i]<nums2[j]){
                    cur=nums1[i++];
                }else{
                    cur=nums2[j++];
                }
            }else if(i>=n1&&j<n2){
                cur=nums2[j++];
            }else if(i<n1){
                cur=nums1[i++];
            }           
            index++;
        }
        if(n%2==0){
            return (cur+pre)*0.5;
        }
        return cur;
    }
};

二分法

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size()>nums2.size()){
            vector<int> tmp=nums1;
            nums1=nums2;
            nums2=tmp;
        }

        int m=nums1.size(),n=nums2.size();
        // 分割线左边的所有元素需要满足的个数 m + (n - m + 1) / 2;

        int totalLeft=(m+n+1)/2;
        // 在 nums1 的区间 [0, m] 里查找恰当的分割线，
        // 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]
        int left=0,right=m;

        while(left<right){
            int i=left+(right-left+1)/2;
            int j=totalLeft-i;

            if(nums1[i-1]>nums2[j]){
                // 下一轮搜索的区间 [left, i - 1]
                right=i-1;
            }else{
                // 下一轮搜索的区间 [i, right]
                left=i;
            }
        }

        int i=left;
        int j=totalLeft-i;

        int nums1LeftMax=i==0?INT_MIN:nums1[i-1];
        int nums1RightMin=i==m?INT_MAX:nums1[i];
        int nums2LeftMax=j==0?INT_MIN:nums2[j-1];
        int nums2RightMin=j==n?INT_MAX:nums2[j];

        if((m+n)%2==1){
            return max(nums1LeftMax,nums2LeftMax);
        }else{
            return (double)(max(nums1LeftMax,nums2LeftMax)+min(nums1RightMin,nums2RightMin))/2.0;
        }
    }
};

2、盛水最多的容器

双指针

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left=0,right=height.size()-1;

        int res=0;
        while(left<right){
            int area=min(height[left],height[right])*(right-left);
            res=max(res,area);

            if(height[left]<=height[right]) left++;
            else right--;
        }
        return res;
    }
};

3、15. 三数之和(No)

排序+双指针

class Solution {
public:
    //排序+双指针
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int n=nums.size();
        if(n<3){
            return res;
        }

        sort(nums.begin(),nums.end());
        for(int i=0;i<n;i++){
            //第一个元素就大于0，后边比不可能小于0
            if(nums[i]>0){
                return res;
            }
            //去重
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int l=i+1,r=n-1;
            while(l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(sum==0){
                    //是一种情况，push到结果中
                    res.push_back({nums[i],nums[l],nums[r]});
                    // l和r往后走
                    while(l<r&&nums[l]==nums[l+1]) l++;
                    while(l<r&&nums[r]==nums[r-1]) r--;
                    l++;r--;
                }
                //和小了，增大最大值
                else if(sum<0){
                    l++;
                }
                //和大了，减小最大值
                else if(sum>0){
                    r--;
                }
            }
        }
        return res;
    }
};

4、33. 搜索旋转排序数组(No)

双指针

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n=nums.size();
        if(n<1) return -1;
        if(n==1) return target==nums[0]?0:-1;

        int l=0,r=n-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[mid]==target) return mid;
            if(nums[mid]>=nums[0]){  //左边有序
                if(nums[0]<=target&&target<=nums[mid]){
                    r=mid-1;
                }else{
                    l=mid+1;
                }
            }else{  //右边有序
                if(nums[mid]<=target&&nums[r]>=target){
                    l=mid+1;
                }else{
                    r=mid-1;
                }
            }
        }
        return -1;
    }
};

5、287. 寻找重复数(No)

二分法

class Solution {
public:
    //二分查找法：找中间那个数，看小于他的有多少个 
    int findDuplicate(vector<int>& nums) {
        int left=1;
        int right=nums.size()-1;
        while(left<right){
            int mid=left+(right-left)/2;
            int cnt=0;
            for(int &num:nums){
                if(num<=mid){
                    cnt++;
                }
            }
            if(cnt>mid){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;       

    }
};

快慢指针

class Solution {
public:
    //快慢指针
    int findDuplicate(vector<int>& nums) {
        int slow=0;
        int fast=0;
        //找到环
        do{
            slow=nums[slow];
            fast=nums[nums[fast]];
        }while(slow!=fast);
        //找入口
        slow=0;
        while(slow!=fast){
            slow=nums[slow];
            fast=nums[fast];
        }
        return slow;
    }
};

6、88. 合并两个有序数组(No)

逆向双指针

class Solution {
public:
    //尾部排序,逆向双指针，比较大小，大的放后边
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=nums1.size()-1;
        m--;
        n--;
        while(n>=0){
            while( m>=0 && nums1[m] > nums2[n]){
                swap(nums1[i--],nums1[m--]);
            }            
            swap(nums1[i--],nums2[n--]);
        }
    }
};

双指针

class Solution {
public:
    //正向双指针
    //新建一个数组，比较、移动
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
       vector<int> temp(m+n,0);
       int p1=0,p2=0,p3=0;
       int cur=0;
       while(p1<m||p2<n){
           if(p1==m){
                temp[p3++]=nums2[p2++];
           }else if(p2==n){
                temp[p3++]=nums1[p1++];
           }else if(nums1[p1]<nums2[p2]){
                temp[p3++]=nums1[p1++];
           }else{
                temp[p3++]=nums2[p2++];
           }
       }
       for(int i=0;i!=m+n;i++){
           nums1[i]=temp[i];
       }  
    }
};

直接合并排序

class Solution {
public:
    //合并后排序
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i=0;i<n;i++){
            nums1[m+i]=nums2[i];
        }
        sort(nums1.begin(),nums1.end());
    }
};

7、75. 颜色分类(No)

双指针

class Solution {
public:
    //双指针 p0指向0，p2指向2，从后往前将2放回，在从前往后
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        int p0=0,p2=n-1;
        for(int i=0;i<=p2;i++){
            while(i<=p2&&nums[i]==2){
                swap(nums[i],nums[p2]);
                p2--;
            }
            if(nums[i]==0){
                swap(nums[i],nums[p0]);
                p0++;
            }
        }
    }
};

单指针

class Solution {
public:
    //单指针，先放正0，在接着后边放1
    void sortColors(vector<int>& nums) {
        int ptr=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==0){
                swap(nums[i],nums[ptr]);
                ptr++;
            }
        }
        for(int i=0;i<nums.size();i++){
            if(nums[i]==1){
                swap(nums[i],nums[ptr]);
                ptr++;
            }
        }

    }
};

8、 581. 最短无序连续子数组(No)

双指针

class Solution {
public:
    // 先排序，然后数组左右两端开始扫描
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> tmp(nums);
        sort(nums.begin(),nums.end());

        int res=0;
        int left=0,right=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=tmp[i]){
                left=i;
                break;
            }
        }
        for(int i=nums.size()-1;i>=0;i--){
            if(nums[i]!=tmp[i]){
                right=i;
                break;
            }
        }
        // 如果都为0，说明有序，返回0
        return right==left?0:right-left+1;
    }
};

分段

public:
    // A B C序列 B无序，但B中值要大于C中最小值，B中值要大于A中最大值
    int findUnsortedSubarray(vector<int>& nums) {
        int n=nums.size();

        //记录A最大值，C最小值
        int m_max=INT_MIN,m_min=INT_MAX,l=-1,r=-1;

        for(int i=0;i<n;i++){
            //找最后一个小于m_max的元素下标
            if(nums[i]<m_max) r=i;  
            else m_max=nums[i];  

            //找最后一个大于m_min的元素下标
            if(nums[n-1-i]>m_min) l=n-1-i;
            else m_min=nums[n-1-i]; //正常的，更新右边最小值
        }
        return r==-1?0:(r-l+1);
    }
};

9、240. 搜索二维矩阵 II(No)

双指针

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for (const auto& row: matrix) {
            auto it = lower_bound(row.begin(), row.end(), target);
            if (it != row.end() && *it == target) {
                return true;
            }
        }
        return false;
    }
};

暴力

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for (const auto& row: matrix) {
            for (int element: row) {
                if (element == target) {
                    return true;
                }
            }
        }
        return false;
    }
};

10、283. 移动零(No)

双指针

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //先用双指针移除0，再在末尾补足0
        int slow=0,fast=0;
        while(fast<nums.size()){
            if(nums[fast]!=0){
                nums[slow]=nums[fast];
                slow++;
            }
            fast++;
        }
        for(;slow<nums.size();slow++){
            nums[slow]=0;
        }
    }
};

贪心算法

1、合并区间

贪心算法

class Solution {
public:
    static bool cmp(Interval& a,Interval& b){
        return a.start<b.start;
    }
    vector<Interval> merge(vector<Interval> &intervals) {
        int n=intervals.size();
        vector<Interval> res;
        if(n<1) return res;
        sort(intervals.begin(),intervals.end(),cmp);
        res.push_back(intervals[0]);

        for(int i=1;i<n;i++){
            if(intervals[i].start<=res.back().end){
                res.back().end=max(res.back().end,intervals[i].end);
            }else{
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};

图论

1、207. 课程表(No)

深度优先算法

class Solution {
public:
    vector<bool> onPath;
    vector<bool> visited;
    bool hasCycle=false;
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        //建图
        vector<vector<int>> graph(numCourses);
        for(auto p:prerequisites){
            int from=p[1],to=p[0];
            graph[from].push_back(to);
        }

        onPath.resize(numCourses);
        visited.resize(numCourses);
        for(int i=0;i<numCourses;i++){
            traverse(graph,i);
        }
        return !hasCycle;
    }

    //看路径中是否有相同的节点，有则循环。
    void traverse(vector<vector<int>>& graph,int s){
        if(onPath[s]){
            hasCycle=true;
        }
        if(visited[s]||hasCycle){
            return;
        }
        visited[s]=true;
        onPath[s]=true;
        for(int p:graph[s]){
            traverse(graph,p);
        }
        onPath[s]=false;
    }

};

2、399. 除法求值

深度优先算法

class Solution {
public:
    //dfs
    vector<double> res;
    bool Nofind;
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        ////string - string(double)  a连接b(b带上权值)
        unordered_map<string,vector<pair<string,double>>> g;
        unordered_map<string,int> visit;

        for(int i=0;i<equations.size();i++){
            g[equations[i][0]].push_back(make_pair(equations[i][1],values[i]));
            g[equations[i][1]].push_back(make_pair(equations[i][0],1.0/values[i]));
        }

        //遍历queries，对每一组进行dfs计算结果。
        //如果相连接，就把 路径上的权值相乘就是结果
        for(int i=0;i<queries.size();i++){
            if(!g.count(queries[i][0])){
                res.push_back(-1.0);
                continue;
            }
            //设置一个全局变量，如果进行dfs后，queries[0]到不了queries[1]，Nofind = true;
            Nofind=true;

            visit[queries[i][0]]=1;
            dfs(g,visit,queries[i][0],queries[i][1],1);
            visit[queries[i][0]]=0;

            if(Nofind){
                res.push_back(-1.0);
            }          
        }
        return res;
    }

    void dfs(unordered_map<string,vector<pair<string,double>>> &g,unordered_map<string,int>& visit,string val,const string& target,const double& path){
        //如果节点已经相连接，那没 必要再dfs搜索了，直接返回
        if(Nofind==false) return;
        if(val==target){
            Nofind=false;
            res.push_back(path);
            return;
        }
        for(int j=0;j<g[val].size();j++){
            if(visit[g[val][j].first]==0){
                visit[g[val][j].first]=1;
                dfs(g,visit,g[val][j].first,target,path*g[val][j].second);
                visit[g[val][j].first]=0;
            }
        }
    }
};

并查集

class Solution {
public:
    //并查集
    class UF{
    private:
        vector<int> parent;
        //指向父节点的权值
        vector<double> weight;
    public:
        UF(int n){
            parent.resize(n);
            weight.resize(n,1.0);
            for(int i=0;i<n;i++){
                parent[i]=i;
            }
        }
        void Union(int x,int y,double value){
            int rootX=find(x);
            int rootY=find(y);
            if(rootX==rootY){
                return;
            }
            parent[rootX]=rootY;
            weight[rootX]=weight[y]*value/weight[x];
        }
        //找x的root，顺便路径压缩
        int find(int x){
            if(x!=parent[x]){
                int old=parent[x];
                parent[x]=find(old);
                weight[x]*=weight[old];
            }
            return parent[x];
        }
        //判断是否相连
        double isConnected(int x,int y){
            int rootX=find(x);
            int rootY=find(y);
            if(rootX==rootY){
                return weight[x]/weight[y];
            }else{
                return -1.0;
            }
        }

    };
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string,int> hashMap;
        //存放结果
        vector<double> res;
        int id=1;

        //首先把等式放入并查集中
        //给字母赋予id，以便取出,存入hash表
        for(auto& str:equations){
            if(!hashMap.count(str[0])){
                hashMap[str[0]]=id++;
            }
            if(!hashMap.count(str[1])){
                hashMap[str[1]]=id++;
            }
        }
        UF uf(id);
        for(int i=0;i<values.size();i++){
            uf.Union(hashMap[equations[i][0]],hashMap[equations[i][1]],values[i]);
        }
        //进行查询        
        for(auto& str:queries){
            if(!hashMap.count(str[0])||!hashMap.count(str[1])){
                res.push_back(-1.0);
                continue;
            }
            res.push_back(uf.isConnected(hashMap[str[0]],hashMap[str[1]]));
        }
        return res;
    }

};

数学问题

1、31. 下一个排列(No)

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        //找到要交换的位置 
        int i=nums.size()-2;
        while(i>=0&&nums[i]>=nums[i+1]){
            i--;
        }

        //从后往前找第一个满足 大于要交换的数，保证改动的幅度最小 
        if(i>=0){
            int j=nums.size()-1;
            while(j>=0&&nums[i]>=nums[j]){
                j--;
            }
            //交换
            swap(nums[i],nums[j]);
        }
        //保证后边升序，没有找到也升序排列
        reverse(nums.begin()+i+1,nums.end());
    }
};

2、461. 汉明距离(No)

除数法

class Solution {
public:
    //均除以2 看余数是否相等 
    int hammingDistance(int x, int y) {
        int dis=0;
        while(x>1||y>1){
            if(x%2!=y%2){
                dis++;
            }
            x/=2;
            y/=2;
        }
        //剩下的一位数 也要看是否相等
        if(x!=y) dis++;
        return dis;
    }
};

内置函数

class Solution {
public:
    // 内置函数：计算二进制表达中 1 的数量
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x^y);
    }
};

• 时间复杂度：O(1)
• 空间复杂度：O(1)

移位计数

class Solution {
public:
    // 移位计数
    int hammingDistance(int x, int y) {
       int s=x^y,res=0;
       while(s!=0){
           res+=s&1;
           s=s>>1;
       }
       return res;
    }
};

Brian Kernighan 算法

class Solution {
public:
    // Brian Kernighan 算法:对任何一个数 n ，n & ( n − 1 ) 的结果是n的比特位最右端的1变为0的结果
    int hammingDistance(int x, int y) {
       int s=x^y,res=0;
       while(s){
           s=s&(s-1);
           res++;
       }
       return res;
    }
};

3、 48. 旋转图像(No)

直接翻转

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        //水平翻转
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n;j++){
                swap(matrix[i][j],matrix[n-1-i][j]);
            }
        }

        //主对角线翻转
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                swap(matrix[i][j],matrix[j][i]);
            }
        }

    }
};

4、621. 任务调度器(No)

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int len=tasks.size();
        if(n<0||len==0) return 0;
        vector<int> arr(26,0);
        for(int i=0;i<len;i++)
          arr[tasks[i]-'A']++;
        std::sort(std::begin(arr),std::end(arr));
        int result=(arr[25]-1)*(n+1);
        for(int j=25;j>0&&arr[j]==arr[25];j--)
          result++;
        return result>len?result:len;        
    }
};