Leetcode hot100中的题目

大家可以用题号or名字检索 部分题目有C++代码~

哈希

两数之和-1

(1)暴力双循环 n^2复杂度

(2)哈希表 记录nums[i]和i

unordered_map<int, int> mp; // C++

mp[nums[i]]=i; //插入

auto it=mp.find(target-nums[i]);

if(it!=mp.end()); // 找到

return {it->second,i}; // 返回格式是[x,y]

这题注意先查hash表再放入 防止自己和自己匹配

字母异位词分组-49

unordered_map<string,vector<string>> mp; // hash表存排列前的string和原string们

// 遍历hash表：
for(auto it:mp)
{
    // 通过it.first it.second拿取元素
}
// 或者:
for(auto it=mp.begin();it!=mp.end();++it)
{

}

最长连续序列-128

用一个unordered_set存这些数 然后遍历set 慢慢+1去找

这里注意剪枝 如果当前元素-1在set中 那么就跳过（从那个-1开始肯定比这个长）

双指针

移动零-283

双指针遍历 一开始left=right=0 while(right < size) 如果nums[right]是0 right右移 不然就交换 left++ right++

盛最多水的容器-11

左右两个指针放最边上 然后往中间移动 移矮的那个（因为移高的不可能有收益）

三数之和-15

先排序 第一个数从头遍历 二、三个数用双指针在后面找 注意第一个数需要去重

vector<vector<int>> ans;
int n=nums.size();
sort(nums.begin(),nums.end());
for(int i=0;i<n;i++)
{
    if(i>0&&nums[i]==nums[i-1])continue;
    int left=i+1;
    int right=n-1;
    while(left<right)
    {
        if(nums[i]+nums[left]+nums[right]==0)
        {
            ans.push_back({nums[i],nums[left],nums[right]});
            while(left<right&&nums[left]==nums[left+1])left++;
            while(left<right&&nums[right]==nums[right-1])right--;
            left++;
            right--;
        }
        else if(nums[i]+nums[left]+nums[right]<0)
        {
            left++;
        }
        else{
            right--;
        }

    }
}
return ans;

接雨水-42

• 从左往右遍历 记录每个柱子左边最高的柱子 从右往左遍历 记录每个柱子右边最高的柱子 然后竖向来看 能存的就是min(左max,右max)-当前高度

这个方法是竖着算的 ans依次加每一列

• 单调栈方法 维护一个单调递减栈（存下标）每一个i，判断当前栈非空且如果当前元素高于栈顶元素（即当前柱子作为右柱子存雨水） 取出栈中元素 栈中元素的上一个栈中元素（左柱子 如果没有就跳出 存不了雨水） 然后ans+=这一段能存的雨水

这个方法是横着算的 一层一层加

int n=height.size();
stack<int> stk;
int ans=0;
for(int i=0;i<n;i++)
{
    while(!stk.empty()&&height[i]>height[stk.top()])
    {
        int top=stk.top();
        stk.pop();
        if(stk.empty())break;
        int left=stk.top();
        int width=i-left-1;
        int curheight=min(height[left],height[i])-height[top];
        ans+=curheight*width;
    }
    stk.push(i);
}
return ans;

滑动窗口

无重复字符的最长子串-3

套双循环 用一个unordered_set当前有的字符

unordered_set<char> st;
int right=0;
int maxlen=0;
for(int i=0;i<s.size();i++)
{
    while(right<s.size()&&st.count(s[right])==0)
    {
        st.insert(s[right]);
        right++;
    }
    maxlen=max(maxlen,right-i);
    st.erase(s[i]);
}
return maxlen;

找到字符串中所有字母异位词-438

用vector<int> sCount(26)来存当前窗口的情况 在循环中，移出一个，加一个

判断两个vector是否相等可以直接用sCount==pCount

子串

和为k的子数组-560

算前缀和并且加入hash表中 使用unordered_map存储每个前缀和及其出现的次数 遍历过程中直接去找想要的前缀和 总和数目直接加想要的前缀和的数量 O(n)复杂度一次遍历

滑动窗口最大值-239

一个优先队列存所有数和下标，遍历i同时i往后移动，取当前优先队列最大值，如果下标不在窗口范围内，移出，再取直到在范围内。

priority_queue<pair<int, int>> q; //C++

q.emplace(nums[i], i); //加入元素 
q.top().first; 
q.top().second; // 取元素 
q.pop() //出队列 

一个双向队列 里面的下标递增 数字大小递减（因为如果下标增，数字也增，小的下标不可能被用到，所以可以出队列） 遍历i同时i往后移动，取当前队列最大值，如果下标不在窗口范围内，移出，再取直到在范围内。

deque<int> q;

q.pop_back(); 
q.push_back(); 
q.pop_front();

最小覆盖子串-76

滑动窗口的思路 用hash表存储需要的字符 先滑右边界 满足后尝试缩小左边界 看能不能继续缩小子串

普通数组

最大子数组和-53

经典题目 遍历过程中维护一个当前和 如果当前和小于0 则将当前和置为0 否则当前和加当前值 O(n)复杂度

这个思想是动态规划的思想 在pre[i]+x和x中间选一个大的

分治算法也可以（找左边最大，右边最大，左边连右边最大）

合并区间-56

按照first元素对intervals排序 注意lambda表达式写法

sort(intervals.begin(),intervals.end(),[](vector<int> &a,vector<int> &b){
            return a[0]<b[0];
        });

判断待加入的左端点和当前右端点的大小，如果待加入左端点大，那就分开；如果当前右端点大，就合并与更新右端点

轮转数组-189

• 可以理解成先整个数组反转 然后前k%n个反转 和后一半反转

• 直接开额外空间存 然后放到对应位置也可以

除自身以外数组的乘积-238

维护一个前缀积 这样ans[0]是1 ans[n]是前n-1个元素的积

然后从后面维护一个后缀积 ans[n]*=后缀积 返回ans即可

缺失的第一个正数-41

原地hash 遍历一遍 让该去自己位置的元素都去自己的位置（不该去的不用管） 遍历到i这个位置的时候 只要让nums[i]这个元素去它对应的位置就好了(如果新来的元素也能去 那就必须也要去 所以要套while而不是if)

然后从头开始找一遍即可

注意交换条件

while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]) // 新下标在0-n之间 且新下标的数位置不对

// 如果最后一个判断条件是 nums[i]-1!=i 那么会死循环(eg:[1,1]情况 在1下标这个位置 1 1一直换)  

矩阵

矩阵置零-73

先记录第一行和第一列是否有0 然后以第一行（列）为标志位记录这一列（行）是否有0

先把标志位所在行（列）置0 然后如果第一行（列）有0 就置0

螺旋矩阵-54

按层模拟

旋转图像-48

遍历i,j的时候只需要记录左上角的1/4就可以，因为四个换位置一圈就保证了所有

for(int i=0;i<(n+1)/2;i++)
{
    for(int j=0;j<n/2;j++)
    {}
}

搜索二维矩阵II-240

• 对每一行二分查找 O(mlogn)

• Z型查找 左下角开始 如果比想要的数字大 就排除了一行(x--) 小则排除了一列(y++) O(m+n)

链表

相交链表-160

• 两个链表同时往后移 p1走到末尾就移到p2的头 p2走到末尾就移到p1的头 那么就会相遇（都走了自己的开始未相交部分 相交部分 对方的未相交部分） 如果不想交 那么就是走完自己 走完对方以后 同时是null 所以就可以跳出while

if(headA==NULL||headB==NULL)return NULL;
ListNode *pa=headA;
ListNode *pb=headB;
while(pa!=pb)
{
    pa=pa==NULL?headB:pa->next;
    pb=pb==NULL?headA:pb->next;
}
return pa;

• hash表存链表的节点

反转链表-206

当前元素是cur 上一个元素是pre while(cur!=nullptr) 记录tmp是下一个 cur->next=pre pre=cur cur=tmp 最后return的是pre 因为最后一步之后 cur已经是最后一个的next了 pre才是最后一个

递归也是一样的思路 返回值是ListNode*类型

回文链表-234

翻转以后 两个链表一起移动 或者翻转一半

环形链表-141

快慢指针 如果快指针到null就直接退出来（不存在环 不然已经回去和慢指针相遇了）

while(fast!=nullptr)
{
    fast=fast->next;
    if(fast!=nullptr)fast=fast->next;
    if(fast==slow)return true;
    slow=slow->next;
}

环形链表II-142

• 这题要找到入环的节点 可以先让快慢指针在环中相遇

然后让相遇指针和头指针一起后移 遇到的节点就是入环的节点

证明：可以设环外节点有a个 slow指针进入环后 走了b与fast相遇 此时fast指针走了n圈 总距离为a+n(b+c)+b

a+n(b+c)+b=2(a+b) 得到a=c+(n-1)(b+c)

从相遇点到入环点的距离+(n-1)环长=头到环距离 所以得证

• 直接hash表记录也可以

合并两个有序链表-21

可以创建一个dummy 然后两个链表在while中套

两数相加-2

保留一个进位 创建一个新链表存结果 就从个位（链表头）开始加 每加一位相当于尾插法

删除链表的倒数第N个节点-19

• 计算出长度后 从头遍历 数数来删

• 双指针 使用两个指针 first比second超前n个节点 first到末尾时 second就是倒数第n个

两两交换链表中的节点-24

标记first second third

ListNode *dummy=new ListNode();
dummy->next=head;
ListNode *cur=dummy;
while(cur->next&&cur->next->next){
    ListNode *first = cur->next;
    ListNode *second = first->next;
    ListNode *third = second->next;

    cur->next = second;
    second->next = first;
    first->next = third;

    cur = first;
}
return dummy->next;

K个一组翻转链表-25

写一个翻转链表的函数

注意翻转完之后 头节点和尾节点的连接都要处理 比如0 1 2 3 翻转的是1 2 然后0要连2（这个通过head->next=prev;实现） 1要连3（这个通过一开始把prev置为tail而不是null 最开始递归的时候实现）

下面这个也要注意：先建一个dummy节点 然后走过k个之后 调用函数的tail是下一个 比如k=2 一开始从0开始走 走两步 到2 tail是下一个3 然后翻转链表函数的返回值是新链表的curr也就是1 这个节点是下一次调用的头节点 还有一个判断是如果没走完k步就到null了 直接返回dummy->next 不要翻转了 如果翻转完之后 tail为null 就返回

ListNode* reverse(ListNode *head, ListNode *tail) {
    // 不包括head和tail 
    ListNode *prev=tail;  
    ListNode *curr=head->next;
    ListNode *first=curr;
    while(curr!=tail){
        ListNode *next=curr->next;
        curr->next=prev;
        prev=curr;
        curr=next;
    }
    head->next=prev;
    return first;
}

ListNode* reverseKGroup(ListNode* head, int k) {
    if(head==nullptr||k==1)return head;
    ListNode *dummy=new ListNode();
    dummy->next=head;
    ListNode *pre=dummy;
    while(1)
    {
        ListNode *check=pre;
        for(int i=0;i<k;i++)
        {
            check=check->next;
            if(check==nullptr)return dummy->next;
        }
        ListNode *newstart=check->next;
        pre=reverse(pre,newstart);
        if(newstart==nullptr)break;
    }
    return dummy->next;
}

随机链表的复制-138

先遍历一遍 得到一个next完成的链表 并用hash表存一个原节点到新节点的对应

再遍历一遍 把random指针指向新节点

这样虽然麻烦但思路很清晰

排序链表-148

可以用归并排序 采用递归 从上到下 注意最后merge的是两个子链表 所以要切断链表避免有环等情况

ListNode* sortList(ListNode* head) {
    return sortList(head,nullptr);
}

ListNode *sortList(ListNode* head, ListNode *tail)
{
    if(head==nullptr)return nullptr;
    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 *l1,ListNode *l2)
{
    ListNode *dummy=new ListNode();
    ListNode *temp=dummy,*temp1=l1,*temp2=l2;
    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 dummy->next;
}

合并K个升序链表-23

可以写成递归形式 两两合并 中间二分 不然单个链表会比较长

ListNode *Two(ListNode *a,ListNode *b){
    if(a==nullptr||b==nullptr)return a?a:b;
    ListNode head,*tail=&head,*aptr=a,*bptr=b;
    while(aptr&&bptr){
        if(aptr->val<bptr->val){
            tail->next=aptr;
            aptr=aptr->next;
        }
        else{
            tail->next=bptr;
            bptr=bptr->next;
        }
        tail=tail->next;
    }
    tail->next=(aptr?aptr:bptr);
    return head.next;
}
ListNode* merge(vector<ListNode*>& lists,int l,int r){
    if(l==r)return lists[l];
    if(l>r)return nullptr;
    int mid=(l+r)>>1;
    return Two(merge(lists,l,mid),merge(lists,mid+1,r));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
    return merge(lists,0,lists.size()-1);
}

LRU缓存-146

要一个双向链表存信息，一个unordered_map<int,DLinkedNode*>存cache 一个size 一个capacity来维护

每次get从map中找到节点 然后在链表中移到头部

每次put如果不存在 就创新节点 加进map和链表头部 如果超出capacity 删除双向链表尾部节点 并从map中删除 如果存在 通过hash表定位再修改value

struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        if (!cache.count(key)) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);
            // 添加进哈希表
            cache[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode* removed = removeTail();
                // 删除哈希表中对应的项
                cache.erase(removed->key);
                // 防止内存泄漏
                delete removed;
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

如果直接用list造好的轮子和迭代器要简单一些：

class LRUCache {
private:
    unordered_map<int, list<pair<int, int>>::iterator> keyToNode;
    list<pair<int, int>> cache; 
    int capacity;

public:
    LRUCache(int _capacity) : capacity(_capacity) {}

    int get(int key) {
        if (keyToNode.find(key) == keyToNode.end()) return -1;
        auto it = keyToNode[key];
        int value = it->second;
        cache.erase(it);
        cache.push_front({key, value});
        keyToNode[key] = cache.begin();
        return value;
    }

    void put(int key, int value) {
        if (keyToNode.find(key) != keyToNode.end()) {
            auto it = keyToNode[key];
            cache.erase(it);
        } else if (cache.size() >= capacity) {
            int keyToRemove = cache.back().first;
            keyToNode.erase(keyToRemove);
            cache.pop_back();
        }
        cache.push_front({key, value});
        keyToNode[key] = cache.begin();
    }
};

二叉树

二叉树的中序遍历-94

递归 注意返回条件 函数开始写个如果nullptr就返回 后面就不用判断是否为null了 直接遍历

迭代 用栈

二叉树的最大深度-104

int maxDepth(TreeNode* root) {
    if(root==nullptr)return 0;
    return max(maxDepth(root->left),maxDepth(root->right))+1;
}

翻转二叉树-226

TreeNode* swap(TreeNode *root)
{
    if(root!=nullptr)
    {
        TreeNode* temp;
        temp=root->left;
        root->left=root->right;
        root->right=temp;
        swap(root->left);
        swap(root->right);
    }
    return root;
}
TreeNode* invertTree(TreeNode* root) {
    swap(root);
    return root;
}

对称二叉树-101

bool Judge(TreeNode* root1,TreeNode* root2)
{
    if(root1==nullptr&&root2==nullptr)return true;
    if(root1==nullptr||root2==nullptr)return false;
    if(root1->val!=root2->val)return false;
    return Judge(root1->left,root2->right)&&Judge(root1->right,root2->left);
}
bool isSymmetric(TreeNode* root) {
    if(root==nullptr)return true;
    return Judge(root->left,root->right);
}

二叉树的直径-543

dfs到每个节点的时候，记录每个节点的左右子树的直径，然后加起来和ans比较

int ans=0;
int getD(TreeNode* root){
    if(root==nullptr){
        return -1;
    }
    int left=getD(root->left)+1;
    int right=getD(root->right)+1;
    ans=max(ans,left+right);
    return max(left,right);
}
int diameterOfBinaryTree(TreeNode* root) {
    getD(root);
    return ans;
}

二叉树的层序遍历-102

用队列广搜

if(root==nullptr)return {};
queue<TreeNode *> q;
vector<vector<int>> ans;
q.push(root);
while(!q.empty()){
    int n=q.size();
    vector<int> cur;
    while(n--)
    {
        TreeNode *node =q.front();
        q.pop();
        cur.push_back(node->val);
        if(node->left)q.push(node->left);
        if(node->right)q.push(node->right);
    }
    ans.push_back(cur);
}
return ans;

用递归深搜 注意需要判断是给ans加一层ans.push_back({node->val})还是某一层加元素ans[level].push_back(node->val)

vector<vector<int>> ans;

void LevelOrder(TreeNode *node,int level)
{
    if(level>=ans.size())
    {
        ans.push_back({node->val});
    }
    else{
        ans[level].push_back(node->val);
    }
    if(node->left)
    {
        LevelOrder(node->left,level+1);
    }
    if(node->right)
    {
        LevelOrder(node->right,level+1);
    }
}

vector<vector<int>> levelOrder(TreeNode* root) {
    if(root)LevelOrder(root,0);
    return ans;
}

将有序数组转换为二叉搜索树-108

先把中间节点建好 向两边递归

验证二叉搜索树-98

可以中序遍历然后判断是否递增

或者递归判断（注意最大值是INT_MAX,然后有等号是否 所以最大要开到比INT_MAX大，可以来LONG_MAX）

二叉搜索树种第K小的元素-230

中序遍历 找第k个元素

二叉树的右视图-199

递归的时候记录层数 把每层最后一个节点存到ans就行

二叉树展开为链表-114

前序遍历 把所有遍历到的节点存到vector里面 最后修改每个node的指针

从前序与中序遍历序列构造二叉树-105

前序的第一个就是根 然后在中序中找到根 左边的都是左子树 右边的都是右子树 递归

unordered_map<int,int> mp;
TreeNode *dfs(vector<int>& preorder, vector<int>& inorder,int prel,int prer,int inl,int inr)
    {
        if(prel>=prer)return nullptr;
        int val=preorder[prel];
        int location=mp[val];
        int leftsize=location-inl;
        TreeNode *left=dfs(preorder,inorder,prel+1,prel+1+leftsize,inl,location);
        TreeNode *right=dfs(preorder,inorder,prel+1+leftsize,prer,location+1,inr);
        return new TreeNode(val,left,right);
    }

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

    for(int i=0;i<inorder.size();i++)
    {
        mp[inorder[i]]=i;
    }

    return dfs(preorder,inorder,0,preorder.size(),0,inorder.size());
}

路径综合III-437

维护一个前缀和的map 注意map要随着遍历去更新 dfs搜下去 这个点搜完了 就把这个点的前缀和从map中-1

unordered_map<long long,int> prefix;
int ret=0;
void dfs(TreeNode *root,long long cur,int targetSum)
{
    if(root==nullptr)return;
    cur+=root->val;
    if(prefix.count(cur-targetSum))
    {
        ret+=prefix[cur-targetSum];
    }
    prefix[cur]++;
    dfs(root->left,cur,targetSum);
    dfs(root->right,cur,targetSum);
    prefix[cur]--;
}

int pathSum(TreeNode* root, int targetSum) {
    prefix[0]=1;
    dfs(root,0,targetSum);
    return ret;
}

二叉树的最近公共祖先-236

判断：p是root或者q是root或者root是空 返回root 递归左边 递归右边 如果都有 就返回root 如果左边有返回值 就返回左边 右边有 就返回右边

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root==nullptr||root==p||root==q)return root;
    TreeNode *left=lowestCommonAncestor(root->left,p,q);
    TreeNode *right=lowestCommonAncestor(root->right,p,q);
    if(left!=nullptr&&right!=nullptr)return root;
    if(left!=nullptr)return left;
    if(right!=nullptr)return right;
    return nullptr;
}

如果是二叉搜索树 判断p，q节点值和当前节点大小 如果都大于root 就在root的右子树 如果都小于root 就在root的左子树 如果一大一小 就是root 不需要判断是不是空 因为不可能会到空节点

二叉树中的最大路径和-124

先求每个节点的最大贡献值（node->val+max(左节点的max(最大贡献值,0)+右节点的max(最大贡献值,0))）

作为返回值（只能算上一边 因为这个节点不作为根节点 就不能两边的路都走）

同时更新最大值（左右两边都算上）

图论

岛屿数量-200

dfs遍历 记得标记已经遍历过的格子

void dfs(vector<vector<char>>& grid,int x,int y)
{
    if(x<0||x>=grid.size()||y<0||y>=grid[0].size())
    {
        return;
    }
    if(grid[x][y]!='1')
    {
        return;
    }
    grid[x][y] = '2';
    dfs(grid,x-1,y);
    dfs(grid,x+1,y);
    dfs(grid,x,y-1);
    dfs(grid,x,y+1);
}

int numIslands(vector<vector<char>>& grid) {
    int cnt=0;
    for(int i=0;i<grid.size();i++)
    {
        for(int j=0;j<grid[0].size();j++)
        {
            if(grid[i][j]=='1')
            {
                cnt++;
                dfs(grid,i,j);
            }
        }
    }
    return cnt;
}

腐烂的橘子-994

bfs遍历 用一个队列存当前腐烂的和时间

while(!Q.empty()) 要记录还有没有新鲜橘子 没有就直接break

二维数组也可以memset(dis, -1, sizeof(dis)) / memset(dis, -1, sizeof dis)

课程表-207

拓扑排序 不存在环就ok

可以用 unordered_map<int, vector<int>>存邻接表 用vector<int>存入度

bfs更好理解 用一个队列存可以的节点 慢慢出 时间复杂度O(n+m) (时间复杂度深搜广搜都一样)

实现Trie（前缀树）-208

需要用一个标记来表示是否走到底 不然没法确定是前缀还是真的有这个字符串

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix)
    {
        Trie *node=this;
        for(char ch:prefix)
        {
            ch-='a';
            if(node->children[ch]==nullptr)return nullptr;
            node=node->children[ch];
        }
        return node;
    }
public:
    Trie(): children(26),isEnd(false){
    }

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

    bool search(string word) {
        Trie *node=this->searchPrefix(word);
        return node!=nullptr &&node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix)!=nullptr;
    }
};

回溯

全排列-46

和组合的差距：拿了后面的元素 还要回去拿前面的元素 所以套一个循环在Back函数内部 然后用used记录是否拿过这个元素 而不是下标递增的方式 也不需要尝试放该元素or不放 因为所有的都会被放 只是顺序问题

vector<vector<int>> keep;
void Back(vector<int> &nums,vector<int> &help,vector<bool> &used)
{
    if(help.size()==nums.size())
    {
        keep.push_back(help);
        return;
    }
    for(int i=0;i<nums.size();i++)
    {
        if(used[i])continue;
        used[i]=true;
        help.push_back(nums[i]);
        Back(nums,help,used);
        used[i]=false;
        help.pop_back();
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<bool> used(nums.size(),false);
    vector<int> help;
    Back(nums,help,used);
    return keep;
}

子集-78

标准的回溯

vector<int> t;
vector<vector<int>> ans;

void dfs(int cur,vector<int> &nums){
    if(cur==nums.size()){
        ans.push_back(t);
        return;
    }
    t.push_back(nums[cur]);
    dfs(cur+1,nums);
    t.pop_back();
    dfs(cur+1,nums);
}
vector<vector<int>> subsets(vector<int>& nums) {
    dfs(0,nums);
    return ans;
}

电话号码的字母组合-17

和上一题很类似

组合总和-39

注意每个数可以被选取多次 所以dfs调用的时候 下标不能后移 而是根据和来判断

括号生成-22

dfs的时候记录左括号和右括号数量

单词搜索-79

遍历每个点作为起点 dfs中记录已经走了几步 走完了就true

分割回文串-131

回溯+dp 先用dp数组保存哪些子串是回文串

然后dfs保存一个当前起点 套一个i循环作为长度回溯

vector<vector<string>> ret;
vector<string> ans;
int n;
void dfs(string &s,int i,vector<vector<bool>> f)
{
    if(i==n)
    {
        ret.push_back(ans);
        return;
    }
    for(int j=i;j<n;j++)
    {
        if(f[i][j])
        {
            ans.push_back(s.substr(i,j-i+1));
            dfs(s,j+1,f);
            ans.pop_back();
        }
    }
}
vector<vector<string>> partition(string s) {
    n=s.size();
    vector<vector<bool>> f(n,vector<bool>(n));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            f[i][j]=true;
        }
    }
    for(int len=2;len<=n;len++)
    {
        for(int i=0;i+len<=n;i++)
        {
            int j=i+len-1;
            f[i][j]=(s[i]==s[j])&&f[i+1][j-1];
        }
    }
    dfs(s,0,f);
    return ret;
}

N皇后-51

可以用一维数组来存每行放在第几列

bool JudgeOK(vector<int> &row,vector<int> &column,int l,int c)
{
    for(int i=0;i<l;i++)
    {
        int c1=row[i];
        if(c1-i==c-l||c1+i==c+l)return false;
    }
    return true; 
}

void backtrace(vector<vector<string>> &solutions,vector<int> &row,vector<int> &column,int n)
{
    if(n==row.size())
    {
        vector<string> help;
        for(int i=0;i<row.size();i++)
        {
            string s="";
            for(int j=0;j<column.size();j++)
            {
                if(j==row[i])s.push_back('Q');
                else s.push_back('.');
            }
            help.push_back(s);
        }
        solutions.push_back(help);
    }
    for(int i=0;i<column.size();i++)
    {
        if(column[i]==-1&&JudgeOK(row,column,n,i))
        {
            column[i]=n;
            row[n]=i;
            backtrace(solutions,row,column,n+1);
            row[n]=-1;
            column[i]=-1;
        }
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<int> row(n,-1);
    vector<int> column(n,-1);
    vector<vector<string>> solutions;
    backtrace(solutions,row,column,0);
    return solutions;
}

二分查找

搜索插入位置-35

经典二分 如果不存在就返回要插入的位置 最后返回left就行了 while里面是left<=right

比如1 3 5 6找2 mid=3 然后right=0 然后left=1之后break掉 return 1

搜索二维矩阵-74

• 把矩阵展成一维的然后二分

• 左下角or右上角开始 一次排除一行or一列

在排序数组中查找元素的第一个和最后一个位置-34

• 可以找第一个>=target的作为左边界 >target的-1作为右边界

• 找target-0.5和target+0.5

搜索旋转排序数组-33

先确认数组中最小的元素下标 再联合首元素和target判断是去前半部分找还是后半部分找

找最小值：需要时刻更新minn 注意>=minn 2 1 正确情况：mid=0 left=1 mid=1 可以更新minn 错误情况：mid=0 right=0 right=-1 跑出去了 mincur是0

int left=0,right=nums.size()-1;
int minn=nums[0],mincur=0;
while(left<=right)
{
    int mid=left+(right-left)/2;
    if(nums[mid]>=minn)
    {
        left=mid+1;
    }
    else if(nums[mid]<minn)
    {
        minn=nums[mid];
        mincur=mid;
        right=mid-1;
    }
}

寻找旋转排序数组中的最小值-153

上一题代码

寻找两个正序数组的中位数

递归 找两个数组前k/2个元素（k要减小） 每次排除一半的元素 如果第一个数组的元素小于第二个数组的 说明第一个的前k/2个都不是中位数（第k个元素）

注意奇数个和偶数个的情况

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int n=nums1.size();
    int m=nums2.size();
    int left=(n+m+1)/2;
    int right=(n+m+2)/2;
    return (getKth(nums1,0,n-1,nums2,0,m-1,left)+getKth(nums1,0,n-1,nums2,0,m-1,right))/2.0;
}

int getKth(vector<int>& nums1,int start1,int end1,vector<int>& nums2,int start2,int end2,int k)
{
    int len1=end1-start1+1;
    int len2=end2-start2+1;
    if(len1>len2)
    {
        return getKth(nums2,start2,end2,nums1,start1,end1,k);
    }
    if(len1==0)return nums2[start2+k-1];
    if(k==1)return min(nums1[start1],nums2[start2]);
    int i=start1+min(len1,k/2)-1;
    int j=start2+min(len2,k/2)-1;
    if(nums1[i]>nums2[j])
    {
        return getKth(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));
    }
    else{
        return getKth(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
    }
}

栈

有效的括号-20

如果是([{就入栈 是)]}就出一个比较（注意栈非空 否则直接返回false） 注意最后栈要是空的

最小栈-155

关键是栈的性质 每个元素入栈时记录当前元素入栈后 栈内元素的最小值 求最小值的时候直接就可以拿出来 Keep.push_back(min(val,Keep[Keep.size()-1]))

如果不使用额外空间，在栈中保存当前值和最小值的差 注意如果当前元素是最小值 push的差值不要是0 而是那个负数 不然这个元素出栈以后 之前的信息恢复不了

元素出栈的时候 如果栈元素小于0 说明当前值是最小值 恢复最小值 如果栈元素大于0 直接出栈

注意需要开long long

字符串解码-394

开一个数字栈和字符串栈 如果遇到左括号 当前数字和字符串入栈 如果遇到右括号 栈顶字符串+当前字符串乘以数字以后成为新的当前字符串 栈顶字符串出栈

3[a2[c]] 3入栈 a入栈 2入栈 当前字符串变成acc a 2出栈 当前字符串变成accaccacc 3出栈

每日温度-739

单调栈做法：在O(n)时间复杂度下求数组中各元素右侧第一个更大的元素和其下标

性质：单调栈存储的下标中 对应的温度列表中的温度依次递减

遍历下标 如果栈空：入栈 如果栈非空：栈顶温度大于当前温度：入栈 栈顶温度小于当前温度：栈顶元素出栈 栈顶元素的下一个高温就是当前元素 然后继续看下一个栈顶元素

元素遍历完以后 如果栈中还有下标 那就是找不到下一个高温

柱状图中最大的矩形-84

利用单调栈存每个柱子当前左边比它矮的第一个 右边比它矮的第一个 一开始初始化left全是-1 right全是n 最后面积是right-left-1 这样不用特判最边上（比如最左边那个 左边没有比它矮的 left=-1 右边第一个就比它矮 right=1 他的宽只有它自身就是1 right-left-1也是1 正好对上）

堆

数组中的第K个最大元素-215

维护一个大根堆 全放进去 出k-1个

priority_queue<int, vector<int>> Heap;
priority_queue<int, vector<int>, greater<int>> Heap; // 小根堆

前K个高频元素-347

先用hash表记录每个元素出现次数 再维护一个小根堆 每次都移出最小的堆顶元素（保持堆尺寸<=k） 这样剩的就是最大的

数据流的中位数-295

两个堆 一个堆放小的一半 一个堆放大的一半 注意维护两个堆的大小（差距为1or相等）

贪心算法

买卖股票的最佳时机-121

遍历数组 在每一天考虑：如果我是在历史最低点买入的 那我当前卖出能赚多少 然后max(以前，当天) 所以遍历的同时用一个变量记录历史最低点

跳跃游戏-55

遍历数组每一个下标 更新能到达的最远距离 如果遍历过程中 有i>最远距离 说明到不了 false 否则就是true

跳跃游戏II-45

• 反向查找 从最后一个位置开始 选能到的最远的位置 O(n^2)复杂度

• 正向查找 维护当前能够到达的最大位置 如果到达该最大位置

例如 一开始只能到0 维护0能到的最远位置 为2 然后要走一步了 步数+1 最远位置为2 然后看1 2能到的最远位置 1能到4 然后要走一步了 步数+1 发现到4了 结束

这个过程一开始设置end=0 遍历i 从0到n-1 maxpos=max(maxpos,i+nums[i]) if(i==end) end=maxpos 更新最远位置 ans++

划分字母区间-763

用一个表格记录每个字母最远位置的元素

从头开始遍历 并用新字母的最远位置和原有的最远位置取个max 如果遍历到最远元素 就ok了 记录当前的长度 然后继续遍历直到结束

动态规划

爬楼梯-70

初始化dp[0]=dp[1]=1 dp[n]=dp[n-1]+dp[n-2] (或者不管0 直接初始化1和2 这样更有道理一点)

杨辉三角-118

dp[i][j]=dp[i-1][j-1]+dp[i-1][j]

打家劫舍-198

dp[i]=max(dp[i-1],dp[i-2]+nums[i])

完全平方数-279

for(int j=1;j*j<i;j++)
{
    minn=min(minn,dp[i-j*j]+1);
}

零钱兑换-322

完全背包：每个元素无限多

i 金额(体积) j 硬币(物品)

一开始可以把dp数组都设成amount+1（因为最多就是amount个硬币，最后可以通过判断dp[amount]是否是amount+1判断是否有解）

外层枚举体积 内层枚举硬币 反过来也可以 但这样比较好理解

dp[0]=0 
for(int i=1;i<=amount;i++)
{
    for(int j=0;j<coins.size();j++)
    {
        if(i-coins[j]>=0)
        dp[i]=min(dp[i],dp[i-coins[j]]+1);
    }
}

关于时间复杂度 外层循环枚举物品的写法，只会遍历物品数组一次；而内层循环枚举物品的写法，会遍历物品数组多次。从 cache 的角度分析，多次遍历数组会导致额外的 cache miss，带来额外的开销。所以虽然这两种写法的时间空间复杂度是一样的，但外层循环枚举物品的写法常数更小。（来自0x3f)

单词拆分-139

把所有单词都存入一个unordered_set 字符串从短开始遍历

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

最长递增子序列-300

dp[i]表示以s[i]结尾的最长递增子序列的长度（注意要s[i]结尾）

这样递推公式就很自然：每个i 遍历之前的j 如果s[j]<s[i] 那么dp[i]=max(dp[i],dp[j]+1)

int maxx=0;
for(int i=0;i<n;i++)
{
    dp[i]=1;
    for(int j=0;j<i;j++)
    {
        if(nums[i]>nums[j])
        {
            dp[i]=max(dp[i],dp[j]+1);
        }
    }
    maxx=max(maxx,dp[i]);
}

乘积最大子数组-152

两个变量存到当前的最大乘积和到当前的最小乘积（包括当前的） 一个变量存整体的最大（不需要包含当前）

遍历数组 如果当前是正数 就更新当前的最大乘积maxx=max(nums[i],maxxnums[i]) 最小乘积minn=min(nums[i],minnnums[i]); 如果当前是负数 可以先把最大和最小换个位置 然后更新最大乘积和最小乘积 注意更新完之后都要更新整体的最大

分割等和子集-416

01背包问题 选or不选一个 最后总量是总和/2

可以把dp数组设成bool i表示数字 j表示和 dp[i][j]表示前i个数能否组成和为j 也可以把数组设成int 每个东西重量和价值都是nums[i] 最后判断dp[n-1][target]是否等于target

需要注意初始化

vector<vector<int>> dp(n,vector<int>(target+1)); 
for(int j=0;j<=target;j++)
{
    dp[0][j]=0;
}
for(int i=1;i<n;i++)
{
    dp[i][0]=0;
    for(int j=1;j<=target;j++)
    {
        if(j-nums[i]>=0)
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
        else dp[i][j]=dp[i-1][j];
    }
}
return dp[n-1][target]==target;

int target=summ/2;
vector<vector<bool>> dp(n,vector<bool>(target+1,false)); 
dp[0][0]=true;
for(int i=1;i<n;i++)
{
    dp[i][0]=true;
    for(int j=1;j<=target;j++)
    {
        if(j-nums[i]>=0)
        dp[i][j]=dp[i-1][j]|dp[i-1][j-nums[i]];
        else dp[i][j]=dp[i-1][j];
    }
}
return dp[n-1][target];

最长有效括号-32

如果当前括号是右括号 说明最长有效括号长度可能增加 去看上一个 如果是左 那就是dp[i]=dp[i-2]+2(判断有没有i-2)

如果是右 去找i-dp[i-1]-1位置(因为dp[i-1]就代表带上它 它之前的这么多个元素组成了一组有效括号 去看这群的上一个是啥) 如果是左 就这一大段也是有效括号 加上 如果是右 无事发生

int longestValidParentheses(string s) {
    int n=s.size();
    vector<int> dp(n,0);
    int maxx=0;
    for(int i=1;i<n;i++)
    {
        if(s[i]==')')
        {
            if(s[i-1]=='(')
            {
                if(i>=2)
                {
                    dp[i]=dp[i-2]+2;
                }
                else dp[i]=2;
            }
            else if(i-dp[i-1]>0&&s[i-dp[i-1]-1]=='(')
            {
                if(i-dp[i-1]>=2)
                {
                    dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2;
                }
                else{
                    dp[i]=dp[i-1]+2;
                }
            }
            maxx=max(maxx,dp[i]);
        }
    }
    return maxx;
}

多维动态规划

不同路径-62

• 直接组合数计算 相当于共动m-1+n-1下 选m-1下往下 共有几种路径 C(m-1+n-1,m-1)

• dp 先初始dp[i][0] dp[0][j]为1 然后dp[i][j]=dp[i-1][j]+dp[i][j-1]

最小路径和-64

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];

最长回文子串-5

中心扩散法 有一个精妙的点是可以在外层i遍历中心的时候 内层j设置为0 1 然后l=i r=i+j

int n=s.size();
int maxlen=0;
int start=0;
for(int i=0;i<n;i++)
{
    for(int j=0;j<=1;j++)
    {
        int l=i;
        int r=i+j;
        while(l>=0&&r<n&&s[l]==s[r])
        {
            l--;
            r++;
        }
        int len=r-l-2+1;
        if(maxlen<len)
        {
            maxlen=len;
            start=l+1;
        }
    }
}
return s.substr(start,maxlen);

动态规划 dp[i][j]表示s[i..j]是不是回文串 注意先枚举长度为2的 长度依次递增

int n=s.size();
if(n<2)return s;
int maxLen=1;
int begin=0;
vector<vector<int>> dp(n,vector<int>(n));
for(int i=0;i<n;i++)
{
    dp[i][i]=true;
}

for(int len=2;len<=n;len++)
{
    for(int i=0;i<n;i++)
    {
        int j=i+len-1;
        if(j>=n)break;
        if(s[i]!=s[j])dp[i][j]=false;
        else{
            if(j-i<=2)dp[i][j]=true;
            else dp[i][j]=dp[i+1][j-1];
        }
        if(dp[i][j]&&j-i+1>maxLen)
        {
            begin=i;
            maxLen=j-i+1;
        }
    }
}
return s.substr(begin,maxLen);

最长公共子序列-1143

dp[i][j]表示s1[0,i]和s2[0,j]的最长公共子序列的长度

注意一开始初始化dp[0][x]和dp[x][0]全为0

for(int i=1;i<=r;i++)
{
    for(int j=1;j<=c;j++)
    {
        if(text1[i-1]==text2[j-1])
        {
            dp[i][j]=dp[i-1][j-1]+1;
        }
        else{
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
}

编辑距离-72

// dp[i][j]:1的前i个和2的前j个的距离(注意要初始化的是前0个(就是有空串的情况))

int m=word1.size();
int n=word2.size();
if(m==0||n==0)return n+m;
vector<vector<int>> dp(m+1,vector<int>(n+1));
for(int i=0;i<m+1;i++)
{
    dp[i][0]=i;
}
for(int j=0;j<n+1;j++)
{
    dp[0][j]=j;
}
for(int i=1;i<m+1;i++)
{
    for(int j=1;j<n+1;j++)
    {
        int left=dp[i-1][j]+1;
        int up=dp[i][j-1]+1;
        int leftup=dp[i-1][j-1];
        if(word1[i-1]!=word2[j-1])leftup+=1;
        dp[i][j]=min(left,min(up,leftup));
    }
}
return dp[m][n];

技巧

只出现一次的数字-136

全部元素异或（两个相同元素异或为0）剩下的元素是什么 什么就只出现了一次

其他方法 如用集合存元素 没有就加 有就删； hash表存元素和次数 再遍历； 集合元素两倍-数组元素和 空间都是O(n)

多数元素-169

每次从数组中删除两个不同的元素 遍历完后 肯定剩下的就是众数

int x=0,vote=0;
for(int i=0;i<nums.size();i++)
{
    if(vote==0)x=nums[i];
    if(nums[i]==x)vote++;
    else vote--;
}
return x;

颜色分类-75

• 直接统计0，1数量然后对数组赋值

• 开双指针 把0都挪动到前面 2都挪动到后面

下一个排列-31

从后往前找非递增的第一个 比如4 5 2 6 3 1这个 6 3 1已经没有操作空间了 最大了 找到2 然后从后面找第一个比2大的就是3 然后2 3换一下 4 5 3 6 2 1然后给3后面的逆序一下

如果整个是递减的 相当于把整个数组逆序一下

寻找重复数-287

快慢指针 相当于建立映射 就是判断是否有环

最后还要找到入环的点 相当于建一个从头跑的指针和slow指针一起再跑 类似于环形链表II-142