leecode刷题

//1.两数之和
vector<int> twoSum(vector<int>& nums, int target){
    //哈希
    unordered_map<int,int> hash;
    for(int i=0; i<nums.size(); i++){
        int val=target-nums[i];
        auto iter = hash.find(val);
        if(iter !=hash.end()){
            return {iter->second, i};
        }
        else{
            hash[nums[i]]=i;
        }
    }
    return {};
}

//2.两数相加
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2){
    ListNode* head = new ListNode(-1);  //定义返回列表的头节点
    ListNode* h=head;   //移动指针
    int sum =0;
    bool carry=false;   //进位
    while(l1 != nullptr || l2 != nullptr){
        sum=0;
        if(l1 != nullptr){
            sum+=l1->val;
            l1=l1->next;
        }
        if(l2 != nullptr){
            sum+=l2->val;
            l2=l2->next;
        }
        if(carry){
            sum+=1;
        }
        h->next=new ListNode(sum%10);
        h=h->next;
        carry=sum>=10? true:false;
    }
    if(carry){
        h->next=new ListNode(1);
    }
    return head->next;
}

//7.整数反转    % /
int reverse(int x){
    int rev=0;
    while(x != 0){
        int pop = x%10;     //如果x是负的那么pop值也是负的
        x=x/10;
        if(rev > INT_MAX/10 || (rev==INT_MAX/10 && pop > INT_MAX%10)) return 0; //正数越界
        if(rev < INT_MIN/10 || (rev==INT_MIN/10 && pop < INT_MIN%10)) return 0; //负数越界
        rev = rev*10+pop;
    }
    return rev;
}

//3.无重复字符的最长子串
int lengthOfLongestSubstring(stirng s){
    if(s.size() == 0) return 0;
    unordered_set<char> lookup;
    int maxStr=0;
    int left = 0;
    for(int i=0; i< s.size(); i++){
        while(lookup.find(s[i]) != lookup.end()){
            lookup.erase(s[left]);      //从左端开始移除，直到不重复为止
            left++;
        }
        maxStr = max(maxStr, i-left+1);
        lookup.insert(s[i]);
    }
    return maxStr;
}

//206.反转链表
//迭代
ListNode *reverseList(ListNode* head){
    ListNode *prev=nullptr,*next;
    while(head){
        next=head->next;
        head->next=prev;
        prev=head;
        head=next;
    }
    return prev;
}
//递归
ListNode *reverseList(ListNode* head){
    if(head==nullptr || head->next==nullptr){
        return head;
    }
    ListNode* cur=reverseList(head->next);
    head->next->next=head;
    head->next=nullptr;
    return cur;
}

//5.最长回文子串  中心扩散法
string longestPalindrome(string s){
    int start=0; end=0;
    for(int i=0; i<s.size(); i++){
        auto[left1, right1] = expandAroundCenter(s, i, i);    //奇数
        auto[left2, right2] = expandAroundCenter(s, i, i+1);  //偶数
        if(right1-left1 > end-start){
            start=left1;
            end=right1;
        }
        if(right2-left2 > end-start){
            start=left2;
            end=right2;
        }
    }
    return s.substr(start, end-start+1);
}
pair<int, int> expandAroundCenter(const string& s, int left, int right){
    while(left >= 0 && right < s.size() && s[left] == s[right]){
        left--;
        right++;
    }
    return {left+1, right-1};
}

//70.爬楼梯 动态规划 dp[n]=dp[n-1]+dp[n-2]
int climbStairs(int n){
    if(n<=2) return n;
    vector<int> dp(n, 0);   //开辟空间
    dp[0]=1;
    dp[1]=2;
    for(int i=2;i<n;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n-1];
}

//15.三数之和 排序+双指针
vector<vector<int>> threeSum(vector<int>& nums){
    int n=nums.size();
    sort(nums.begin(), nums.end());
    vector<vector<int>> ret;
    for(int i=0; i<nums.size(); i++){
        if(nums[i]>0) return ret;
        if(i>0 && nums[i]==nums[i-1]) continue; //去重
        //双指针在nums[i]后面的区间寻找和为0-nums[i]的另外两个数
        int l=i+1,r=n-1;
        while(l<r){
            if(nums[l]+nums[r] == -nums[i]){
                ret.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--;
            }else if(nums[l]+nums[r] > -nums[i]){
                r--;
            }else{
                l++;
            }
        }
    }
    return ret;
}

//46.全排列 回溯
//易理解，易变形版
void backtracking(const vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result){
    if(path.size()==nums.size()){
        result.push_back(path);
        return;
    }
    for(int i=0; i<nums.size(); i++){
        if(used[i]) continue;
        path.push_back(nums[i]);
        used[i]=true;
        backtracking(nums, used);
        path.pop_back();
        used[i]=false;
    }
}
vector<vector<int>> permute(vector<int>& nums){
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> used(nums.size(), false);
    backtracking(nums, used, path, result);
    return result;
}

//不易理解
vector<vector<int>> permute(vector<int>& nums){
    vector<vector<int>> ans;
    backtracking(nums, 0, ans);
    return ans;
}
void bactracking(vector<int>& nums, int level, vector<vector<int>>& ans){
    if(level = nums.size()-1){
        ans.push_back(nums);
        return;
    }
    for(int i=level; i<nums.size(); i++){
        swap(nums[i], nums[level]);
        bactracking(nums, level+1, ans);
        swap(nums[i], nums[level]);
    }
}

//47.全排列II
vector<vector<int>> permuteUnique(vector<int>& nums){
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> used(nums.size(), false);
    sort(nums.begin(), nums.end());
    backtracking(nums, used, path, result);
    return result;
}
void backtracking(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result){
    if(path.size()==nums.size()){
        result.push_back(path);
        return;
    }
    for(int i=0; i<nums.size(); i++){
        if(used[i]==true) continue;
        //剪枝去重 used[i-1]==false 之前的重复的回溯了
        if(i>0 && nums[i]==nums[i-1] && used[i-1]==false) continue;
        path.push_back(nums[i]);
        used[i]=true;
        backtracking(nums, used, path, result);
        path.pop_back();
        used[i]=false;
    }
}

//20.有效的括号 栈
bool isValid(stirng s){
    stack<char> stk;
    for(int i=0; i<s.size(); i++){
        if(s[i]==‘{‘ || s[i]==‘[‘ || s[i]==‘(‘){
            stk.push(s[i]);
        }else{
            if(stk.empty()) return false;
            char c=stk.top();
            if((c==‘{‘&& s[i]==‘}‘) || (c==‘[‘ && s[i]==‘]‘) || (c==‘(‘ && s[i]==‘)‘)){
                stk.pop();
            }else{
                return false;
            }
        }
    }
    return stk.empty();
}

//剑指offer03.数组中重复的数字 哈希
int findRepeatNumber(vector<int>& nums){
    unordered_set<int> hash;
    for(int i=0; i<nums.size(); i++){
        if(hash.count(nums[i])){
            return nums[i];
        }
        else{
            hash.insert(nums[i]);
        }
    }
    return -1;
}

//21.合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){
    ListNode* head=new ListNode(-1);
    ListNode* h=head;
    while(l1 && l2){
        if(l1->val > l2->val){
            h->next=l2;
            l2=l2->next;
        }else{
            h->next=l1;
            l1=l1->next;
        }
        h=h->next;
    }
    h->next=l1? l1:l2;
    return head->next;
}

//4.寻找两个正序数组的中位数
//中位数的定义：如果某个有序数组长度是奇数，那么中位数就是中间那个，如果是偶数，那么就是中间两个数的平均值
double findMedianSortArrays(vector<int> nums1, vector<int> nums2){
    vector<int> nums;
    for(n:nums1) nums.push_back(n);
    for(n:nums2) nums.push_back(n);
    sort(nums.begin(), nums.end());
    return double(nums.size()%2 ? nums[nums.size()/2]:(nums[nums.size()/2]+nums[nums.size()/2-1])/2.0);
}

//二分查找
double findMedianSortedArrays(vector<int> nums1, vector<int> nums2){
    //二分查找
    int sum=nums1.size()+nums2.size();
    int n1=0, n2=0, val1=0, val2=0;
    while(n1+n2 <= sum/2)
    {
        val1=val2;
        if(n1==nums1.size()){
            val2=nums2[n2++];
            continue;
        }
        if(n2==nums2.size()){
            val2=nums1[n1++];
            continue;
        }
        if(nums1[n1]<nums2[n2]){
            val2=nums1[n1++];
        }else{
            val2=nums2[n2++];
        }
    }
    return sum%2 ? val2:(val1+val2)/2.0;
}

//45.跳跃游戏 贪心算法
int jump(vector<int>& nums){
    int step=0;
    int end=0;
    int maxPos=0;
    for(int i=0; i<nums.size()-1; i++){
        maxPos=max(nums[i]+i, maxPos);
        if(i == end){   //到达跳跃终点，再跳个最远的
            end = maxPos;
            step++;
        }
    }
    return step;
}

//9.回文数 反转这个整数，如果相等就是回文数
bool isPalindrome(int x){
    if(x<0) return false;
    if(x==0) return true;
    int y=x;
    long rev=0;
    while(x){
        rev=rev*10+x%10;
        x=x/10;
    }
    return int(rev)==y;
}

//92.反转链表2
ListNode* reverseBetween(ListNode* head, int left, int right){
    //设置dummyNode 是这一类问题的一般做法
    ListNode *dummyNode = new ListNode(-1);
    dummyNode->next = head;
    ListNode *pre = dummyNode;
    //1.遍历至第一个节点
    for(int i=0; i<left-1; i++){
        pre=pre->next;
    }

    //2.反转链表
    ListNode *cur =pre->next;
    ListNode * prev=nullptr, *next;
    for(int i=0;i<=right-left; i++){
        next=cur->next;
        cur->next=prev;
        prev=cur;
        cur=next;
    }
    //3.修改left和right位置出节点的指向
    pre->next->next=cur;
    pre->next=prev;
    return dummyNode->next;
}

//42.接雨水 
int trap(vector<int>& height){
    int n=height.size();
    vector<int> left(n), right(n);
    for(int i=1; i<n; i++){
        left[i]=max(left[i-1], height[i-1]);
    }
    for(int i=n-2; i>=0; i--){
        right[i]=max(right[i+1],heght[i+1]);
    }
    int water=0;
    for(int i=0; i<n; i++){
        int level=min(left[i], right[i]);
        water+=max(0, level-height[i]);
    }
    return water;
}

//53.最大子序和 贪心算法真恶心
int maxSubArry(vector<int>& nums){
    int pre=0, maxAns=nums[0];
    for(int i=0; i<nums.size(); i++){
        pre=max(pre+nums[i], nums[i]);
        maxAns=max(maxAns, pre);
    }
    return maxAns;
}

//14.最长公共前缀 暴力 纵向扫描
string longestCommonPrefix(vector<string>& strs){
    if(!strs.size()) return "";
    int length = strs[0].size();
    int count = str.size();
    for(int i=0; i<length; i++){
        char c=strs[0][i];
        for(int j=0; j<count;j++){
            if(i==strs[j].size() || c!=strs[j][i]){
                return strs[i].substr(0,i);
            }
        }
    }
    return strs[0];
}

//143.重排链表  快慢指针、反转链表、合并链表
void reorderList(ListNode* head){
    if(head == nullptr){
        return;
    }
    //寻找链表的中间节点 快慢指针方法
    ListNode* mid=findmidnode(head);
    //反转后面的链表
    ListNode* relist=reverselist(mid->next);
    //归并合并两个链表
    mid->next=nullptr;
    mergelist(head,relist);
}
ListNode* findmidnode(ListNode* head){
    ListNode* slow=head, *fast=head;
    while(fast->next!=nullptr && fast->next->next!=nullptr){
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}
ListNode* reverselist(ListNode* head){
    ListNode* prev=nullptr,* next;
    while(head){
        next=head->next;
        head->next=prev;
        prev=head;
        head=next;
    }
    return prev;
}
void mergelist(ListNode* head, ListNode* relist){
    ListNode *h=head,*tmp_h,*tmp_r;
    while(h && relist){
        tmp_h=h->next;
        tmp_r=relist->next;

        h->next=relist;
        h=tmp_h;

        relist->next=h;
        relist=tmp_r;
    }
}

//146.LRU缓存机制 数据库设计 链表和哈希表都是很快的数据结构
//主要考察 哈希表+双向链表（list）组合体  设计一个缓存机制
class LRUCache{
    private:
        list<pair<int, int>> cache;     //双向链表,链表的尾节点是最近最少使用的数据节点
        unordered_map<int, list<pair<int, int>>::iterator> key2node;    //为什么用iterator迭代器（减少存储），list.erase()要传迭代器（指针的值）进去
        int cap;        //最大容量
    public:
        LRUCache(int capacity):cap(capacity) {}

        int get(int key){
           if(key2node.find(key)==key2node.end()){
               return -1;
           }
           pair<int, int> node = *key2node[key];
           cache.erase(key2node[key]);  //将节点移动到链表头部并更新
           cache.push_front(node);
           key2node[key]=cache.begin();
           return node.second;
        }

        void put(int key, int val){
            auto newNode = std::make_pair(key, val);

            if(key2node.count(key)){    //若节点已存在，则删除旧的节点
                cache.erase(key2node[key]);
            }else{
                if(cap == cache.size()){
                    key2node.erase(cache.back().first); //删除链表最后一个数据索引
                    cache.pop_back();       //删除链表最后一个数据
                }
            }
            cache.push_front(newNode);
            key2node[key]=cache.begin();    //cache.begin()是一个指针
        }
};

//72.编辑距离 动态规划
int minDistance(string word1, string word2){
    vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));

    for(int i=0; i<dp.size(); i++){
        dp[i][0]=i;
    }
    for(int j=0; j<dp[0].size(); j++){
        dp[0][j]=j;
    }
    for(int i=1; i<dp.size(); i++){
        for(int j=1; j<dp[i].size(); j++){
            dp[i][j]=min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1;
            if(word1[i-1] == word2[j-1]){
                dp[i][j]=min(dp[i-1][j-1], dp[i][j]);
            }
        }
    }
    return dp.back().back();
}

//剑指offer22.链表中倒数第k个节点  快慢指针
ListNode* getKthFromEnd(ListNode* head, int k){
    ListNode *fast=head,*slow=head;
    for(int i=0;i<k;i++){
        fast=fast->next;
    }
    while(fast){
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

//25.K个一组翻转链表 hard
ListNode* reverseKGroup(ListNode* head, int k){
    ListNode* dummy = new ListNode(-1), *prev=nullptr,*next;
    dummy->next=head;
    int length=0;
    while(head!=nullptr){
        length++;
        head=head->next;
    }
    for(int i=0;i<length/k; i++){
        for(int j=0; i<k-1; j++){
            next=head->next;
            head->next=prev;
            prev=head;
            head=next;
        }
        //连接链表
        prev=cur;
        cur=prev->next;
    }
    return dummy->next;
}

//54.螺旋矩阵
vector<int> spiralOrder(vector<vector<int>>& matrix){
    vector<int> ans;
    if(matrix.empty()) return ans;
    int u=0;   //赋值上下左右的边界
    int d=matrix.size()-1;
    int l=0;
    int r=matrix[0].size()-1;
    while(true){
        for(int i=l; i<=r; i++) ans.push_back(matrix[u][i]);
        if(++u > d) break;
        for(int i=u; i<=d; i++) ans.push_back(matrix[i][r]);
        if(--r < l) break;
        for(int i=r; i>=l; i--) ans.push_back(matrix[d][i]);
        if(--d < u) break;
        for(int i=d; i>=u; i--) ans.push_back(matrix[i][l]);
        if(++l > r) break;
    }
    return ans;
 }

 //415.字符串相加
 string addStrings(string num1, string num2){
     int l1=nums1.size()-1, l2=num2.size()-1, carry=0;
     string str;
     while(l1>=0 || l2>=0 || carry!=0){
         int x= l1>=0? num1[l1]-‘0‘:0;
         int y= l2>=0? num2[l2]-‘0‘:0;
         int sum=x+y+carry;
         carry=sum/10;
         str.push_back(‘0‘+sum%10);
         l1--;
         l2--;
     }
     //翻转字符串
     reverse(str.begin(), str.end());
     return str;
 }

 //31.下一个排列 模拟法 能大，只能大一点点
void nextPermutation(vector<int>& nums){
    int n=nums.size();
    for(i=n-1; i>=0; i--){
        if(i==0){
            sort(nums.begin(), nums.end());
            return;
        }else{
            if(nums[i]>nums[i-1]){
                sort(nums.begin()+i, nums.end());
                for(int j=i, j<n; j++){
                    if(nums[j]>nums[i-1]){
                        swap(nums[j], nums[i-1]);
                        return;
                    }
                }
            }
        }
    }
}

//200.岛屿数量
int numIslands(vector<char>& grid){
    int numlands=0;
    for(int i=0; i<grid.size();j++){
        for(int j=0;j<grid[i].size();j++){
            if(grid[i][j]==‘1‘){
                numlands++;
                dfs(grid, i,j);
            }
        }
    }
}
void dfs(vector<char>& grid, int i, int j){
    grid[i][j]=‘0‘;
    if(i-1>=0 && grid[i-1][j]==‘1‘) dfs(grid, i-1,j);
    if(j-1>=0 && grid[i][j-1]==‘1‘) dfs(grid, i, j-1);
    if(i+1<grid.size() && grid[i+1][j]==‘1‘) dfs(grid, i+1, j);
    if(j+1<grid[0].size() && grid[i][j+1]==‘1‘) dfs(grid, i, j+1);
}


//82.删除排序链表中的重复元素II
ListNode* deleteDuplicates(ListNode* head){
    if(!head || !head->next) return head;
    ListNode* dummy=new ListNode(-1);
    dummy->next=head;
    ListNode* pre=dummy;
    ListNode* cur=head;
    while(cur){
        //跳过当前的重复节点，使得cur指向当前重复元素的最后一个位置
        while(cur->next && cur->val=cur->next->val){
            cur=cur->next;
        }
        
        if(pre->next=cur){
            //pre和cur之间没有重复节点，pre后移
            pre=pre->next;
        }else{
            //pre->next指向cur的下一个位置（相当于跳过了当前的重复元素）
            //但是pre不移动，仍然指向已遍历的链表结尾
            pre->next=cur->next;
        }

        cur=cur->next;
    }
    return dummy->next;
}

//递归
ListNode* deleteDuplicates(ListNode* head){
    if(!head || !head->next) return head;
    if(head->val !=head->next->val){
        head->next=deleteDuplicates(head->next);
    }else{
        ListNode* move=head->next;
        while(move && head->val==move->val){
            move=move->next;
        }
        return deleteDuplicates(move);
    }
    return head;
}

//131.分割回文串 回溯
class Solution{
private:
    vector<vector<string>> result;
    vector<string> path;    //放已经回文的子串
    void bactracking(const string & s, int startIndex){
        //如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
        if(startIndex >= s.size()){
            result.push_back(path);
            return;
        }
        for(int i=startIndex; i<s.size(); i++){
            if(isPalindrome(s, startIndex, i)){ //是回文子串
                //获取[startIndex, i]在s中的子串
                string str=s.substr(startIndex, i-startIndex+1);
                path.push_back(str);
            }else{
                continue;
            }
            backtracking(s, i+1);   //寻找i+1为起始位置的子串
            path.pop_back();        //回溯过程，弹出本次已经添加的子串
        }
    }
    bool isPalindrome(const string& s, int start, int end){
        for(int i=start, j=end; i<j; i++,j--){
            if(s[i] != s[j]){
                return false;
            }
        }
        return true;
    }
public:
    vector<vector<string>> partition(stirng s){
        result.clear();
        path.clear();
        backtracking(s, 0);
        return result;
    }
}

//121.买卖股票最佳时机
int naxProfit(vector<int>& prices){
    int inf=1e9;
    int minprice=prices[0], maxprofit=0;
    for(int i=1; i<prices.size(); i++){
        minprice=min(minprice, prices[i]);
        maxprofit=max(maxprofit, prices[i]-minprice);
    }
    return maxprofit;
}

//19.删除链表的倒数第N个结点
ListNode* removeNthFromEnd(ListNode* head, int n){
    ListNode* slow=head, *fast=head;
    if(head==nullptr) return head; 
    while(n>0){
        n--;
        fast=fast->next;
    }
    if(fast==nullptr) return head->next;
    while(fast->next){
        slow=slow->next;
        fast=fast->next;
    }
    ListNode *del=slow->next;
    slow->next=slow->next->next;
    delete del;
    return head;
}

//11.盛最多水的容器 双指针
int maxArea(vector<int>& height){
    int l=0,r=height.size()-1, maxArea=0;
    while(l<r){
        maxArea=max(maxArea,min(height[l],height[r])*(r-l));
        if(height[l]>height[r]){
            r--;
        }else{
            l++;
        }
    }
    return maxArea;
}

//22.括号生成
vector<string> generateParenthesis(int n){
    vector<string> ans;
    dfs(ans, "", 0, 0, n);
    return ans;
}

void dfs(vector<string>& ans, string str, int l, int r, int n){
    if(l>n || r>n || l<r){
        return;
    }
    if(l==n && r==n){
        ans.push_back(str);
        return;
    }
    dfs(ans, str+‘(‘, l+1, r, n);
    dfs(ans, str+‘)‘, l, r+1, n);
}


//10.正则表达式匹配
bool isMatch(string s, string p){
    if(p.empty()) return s.empty();

    auto first_match= !s.empty() && (s[0]==p[0] || p[0]==‘.‘);

    if(p.length()>=2 && p[1]==‘*‘){
        return isMatch(s, p.substr(2)) || (first_match && isMatch(s.substr(1),p));
    }else{
        return first_match && isMatch(s.substr(1), p.substr(1));
    }
}

//剑指offer09.用两个栈实现队列
class CQueue{
private:
    stack<int> stk1,stk2;
public:
    CQueue(){}
    void appendTail(int value){
        stk1.push(value);
    }
    int deleteHead(){
        if(stk2.empty()){
            while(!stk1.empty()){
                stk2.push(stk1.top());
                stk1.pop();
            }
        }
        if(stk2.empty()){
            return -1;
        }else{
            int ret=stk2.top();
            stk2.pop();
            return ret;
        }
    }
}

//739.每日温度 单调递减栈
//单调栈：通过维持栈内值的递增（递减）性，在整体O(n)的时间内处理需要大小比较的问题。
/*题解：我们维持一个单调递减的栈，表示每天的温度；为了方便计算天数差，我们这里存放位置（即日期）而非温度本身。我们从左向右遍历温度数组，对于每个日期p，
如果p的温度比栈顶存储位置q的温度高，则我们取出q，并记录q需要等待的天数为p-q；我们重复这一过程，直到p的温度小于等于栈顶存储位置的温度（或栈空）时，我们将p
插入栈顶，然后考虑下一天。
*/
vector<int> dailyTemperatures(vector<int>& T){
    int n=T.size();
    vector<int> ans(n);
    stack<int> indices;
    for(int i=0; i<n;i++){
        while(!indices.empty()){
            int pre_index=indices.top();
            if(T[i] <= T[pre_index]){
                break;
            }
            indices.pop();
            ans[pre_index]=i-pre_index;
        }
        indices.push(i);
    }
}

//剑指Offer42.连续子数组的最大和
int maxSubArray(vector<int>& nums){
    int sum=0,maxsum=nums[0];
    for(int i=0; i<nums.size(); i++){
        sum=max(sum+nums[i], nums[i]);
        maxsum=(maxsum, sum);
    }
    return maxsum;
}

//103.二叉树的锯齿形层序遍历  二叉树层序遍历想到队列解决 queeu
vector<vector<int>> zigzagLevelOrder(TreeNode* root){
    vector<vector<int>> res;
    queue<TreeNode *> q;
    if(root) q.push(root);

    bool lr=true;
    while(!q.empty()){
        int size=q.size();
        vector<int> level(size, 0); //存储一层的元素
        while(size--){
            TreeNode* node = q.front();
            q.pop();
            level[lr? level.size()-size-1:size]=rool->val;
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
        res.push_back(level);
        lr=!lr;
    }
    return res;
}

//105.从前序与中序遍历序列构造二叉树
class Solution{
private:
    unordered_map<int, int> index;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){
        int n=preorder.size();
        for(int i=0; i<n; i++){
            index[inorder[i]]=i;
        }
        return myBuildTree(preorder, inorder, 0, n-1, 0, n-1);
    }

    //递归函数
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right,
        int inorder_left, int inorder_right){
            if(preorder_left > preorder_right){
                return nullptr;
            }
            //前序遍历中第一个节点就是根节点
            int preorder_root=preorder_left;
            //在中序遍历中定位根节点
            int inorder_root = index[preorder[preorder_root]];

            //先把根节点简历出来
            TreeNode* root=new TreeNode(preorder[preorder_root]);
            //得到左子树的节点数目
            int size_left_subtree=inorder_root-inorder_left;
            //递归的构造左子树，并连接到根节点
            root->left=myBuildTree(preorder, inorder, preorder_left+1, preorder_left+size_left_subtree, inorder_left, inorder_root-1);
            //递归的构造右子树，并连接到根节点
            root->right = myBuildTree(preorder, inorder, preorder_left+size_left_subtree+1, preorder_right, inorder_root+1, inorder_right);
            return root;
        }
}

//1190.反转没对括号间的子串  stack
string reverseparentheses(string s){
    string res;
    stack<string> stk;
    for(char c:s){
        if(c==‘(‘){
            stk.push(res);
            res="";
        }else if(c==‘)‘){
            reverse(res.begin(), res.end());
            res=stk.top()+res;
            stk.pop();
        }else{
            res.push_back(c);
        }
    }
    return res;
}

//56.合并区间 排序+双指针
vector<vector<int>> merge(vector<vector<int>>& intervals){
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> res;
    int l=0,r=0,n=intervals.size();
    for(int i=0; i<n; i++){
        l=intervals[i][0];
        r=intervals[i][1];
        while(i<n-1 && r>=intervals[i+1][0]){
            r=max(r,intervals[i+1][1]);
            i++;
        }
        res.push_back({l, r});
    }
    return res;
}

//剑指Offer25.合并两个排序的链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){
    ListNode* dummy=new ListNode(-1), *head=dummy;
    while(l1 && l2){
        if(l1->val < l2->val){
            head->next=l1;
            l1=l1->next;
        }else{
            head->next=l2;
            l2=l2->next;
        }
        head=head->next;
    }
    head->next=l1? l1:l2;
    return dummy->next;
}


//135.分发糖果
int candy(vector<int>& ratings){
    int size=ratings.size();
    if(size<2) return size;
    vector<int> nums(size, 1);
    //从左向右遍历
    for(int i=1; i<size; i++){
        if(ratings[i] > rating[i-1]){
            nums[i]=nums[i-1]+1;
        }
    }
    //从右往左遍历
    for(int i=size-2; i>=0; i--){
        if(ratings[i]>ratings[i+1]){
            nums[i]=max(nums[1],nums[i+1]+1);
        }
    }
    return accumulate(nums.begin(), nums.end(), 0);
}

//118.杨辉三角   找规律，模拟
vector<vector<int>> generate(int numRows){
    vector<vector<int>> ans(numsRows);
    if(numsRows == 0) return ans;   //若numRows为空，返回空数组;
    for(int i=0; i<numRows; i++){   //给数组一个个的赋值
        for(int j=0; j<=i; j++){
            if(j==0 || j==i){   //若是两边的边界，赋值为1
                ans[i].push_back(1);
            }else{
                ans[i].push_back(ans[i-1][j-1]+ans[i-1][j]);    //否则赋值为左上和右上的和
            }
        }
    }
    return ans;
}

//136.只出现一次的数字 ^
int singleNumber(vector<int>& nums){
    int ans=0;
    for(int num:nums){
        ans^=num;
    }
    return ans;
}

//剑指Offer51.数组中的逆序对
int reversePairs(vector<int>& nums){

}

//48.旋转图像
void rotate(vector<vector<int>>& matrix){
    int temp=0, n=matrix.size()-1;
    for(int i=0; i<=n/2;i++){
        for(int j=i;j<n-i;j++){
            temp=matrix[j][n-i];
            matrix[j][n-i]=matrix[i][j];
            matrix[i][j]=matrix[n-j][i];
            matrix[n-j][i]=matrix[n-i][n-j];
            matrix[n-i][n-j]=temp;
        }
    }
}

//16.最接近的三数之和 排序+双指针
int threeSumClosest(vector<int>& nums, int target){
    sort(nums.begin(), nums.end());
    int closeSum=nums[0]+nums[1]+nums[2];
    for(int i=0; i<nums.size(); i++){
        int l=i+1,r=nums.size()-1;
        while(l<r){
            int sum=nums[i]+nums[l]+nums[r];
            if(abs(target-closeSum) > abs(target-sum)){
                closeSum=sum;
            }
            if(sum>target){
                r--;
            }else if(sum<target){
                l++;
            }else{
                return sum;
            }
        }
    }
    return closeSum;
}

//剑指Offer29.顺时针打印矩阵
vector<int> spiralOrder(vector<vector<int>>& matrix){
    vector<int> ret;
    if(matrix.empty()) return ret;
    int l=0;    //左边界
    int r=matrix[0].size()-1;   //右边界
    int u=0;    //上边界
    int d=matrix.size()-1;      //下边界
    while(1){
        for(int i=l; i<=r; i++) ret.push_back(matrix[u][i]);
        if(++u>d) break;
        for(int i=u; i<=d; i++) ret.push_back(matrix[i][r]);
        if(--r<l) break;
        for(int i=r; i>=l; i--) ret.push_back(matrix[d][i]);
        if(--d<u) break;
        for(int i=d; i>=u; i--) ret.push_back(matrix[i][l]);
        if(++l>r) break;
    }
    return ret;
}

//300.最长递增子序列


//6.Z字形变换
string convert(string s, int numRows){
    if(numRows == 1) return s;
    vector<string> rows(min(numRows, int(s.size())));
    int curRow = 0;
    bool goingDown = false;
    
    for(char c:s){
        rows[curRow] += c;
        if(curRow == 0 || curRow == numRows-1) goingDown=!goingDown;
        curRow += goingDown? 1:-1;
    }
    string ret;
    for(string row:rows) ret+=row;
    return ret;
}


//102.二叉树的层序遍历 queue
vector<vector<int>> levelOrder(TreeNode* root){
    vector<vector<int>> ans;
    queue<TreeNode*> q;
    if(!root) return ans;
    q.push(root);
    while(q){
        int size=q.size();
        vector<int> level;
        while(size>0){
            size--;
            TreeNode* node=q.front();
            q.pop();
            level.push_back(node->val);
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
        ans.push_back(level);
    }
    return ans;
}

//215.数组中的第K大个元素 priority_queue优先队列，最大值先出数据结构
int findKthLargest(vector<int>& nums, int k){
    priority_queue<int> priq;       //优先队列，最大值先出数据结构
    int t=nums.size()-k+1;
    for(int num:nums){
        priq.push(num);
        if(priq.size()>t) priq.pop();
    }
    return priq.top();
}

//8.字符串转换整数(atoi) 这题真的毫无意义
int myAtoi(string s){

}

//322.零钱兑换  动态规划
int coinChange(vector<int>& coins, int amount){
    int Max=amount+1;
    vector<int> dp(amount+1, Max);
    dp[0]=0;
    for(int i=1; i<=amount; ++i){
        for(int j=0; j< coins.size(); ++j){
            if(coins[j]<=i){
                dp[i]=min(dp[i], dp[i-coins[j]]+1);
            }
        }
    }
    return dp[amount]>amount ? -1:dp[amount];
}


//283.移动零 双指针
void moveZeroes(vector<int>& nums){
    if(!nums.size()) return;
    int j=0;
    for(int i=0; i<nums.size(); i++){
        if(nums[i]!=0){
            nums[j++]=nums[i];
        }
    }
    for(int i=j; i<nums.size();i++){
        nums[i]=0;
    }
}


//剑指Offer20.表示数值的字符串

//43.字符串相乘
string multiply(string num1, string num2){

}

//23.合并K个升序链表 递归+合并两个有序数组
ListNode* mergeKLists(vector<ListNode*> lists){
    if(lists.empty()) return nullptr;
    ListNode* ans=lists[0];
    for(int i=1; i<lists.size(); i++){
        ans=mergeLists(ans, lists[i]);
    }
    return ans;
}
ListNode* mergeLists(ListNode* l1, ListNode* l2){
    ListNode* dummy=new ListNode(-1), *head=dummy;
    while(l1 && l2){
        if(l1->val < l2->val){
            head->next=l1;
            l1=l1->next;
        }else{
            head->next=l2;
            l2=l2->next;
        }
        head=head->next;
    }
    head->next=l1? l1:l2;
    return dummy->next;
}

//69.x的平方根 二分查找 边界问题
int mySqrt(int a){
    int l=0,r=a, ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if((long long)mid*mid <= a){
            ans=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    return ans;
}


//141.环形链表
bool hasCycle(ListNode* head){
    unordered_set<ListNode*> hash;
    while(head){
        if(hash.count(head)) return true;
        hash.insert(head);
        head=head->next;
    }
    return false;
}

//剑指Offer07.重建二叉树  已知前序中序重建二叉树
unorder_map<int, int> index;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){
    int n=preorder.size();
    for(int i=0; i<n; i++){
        index[inorder[i]]=i;
    }
    return myBuildTree(preorder, inorder,0, n-1, 0, n-1);
}

//递归函数
TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right,
    int inorder_left, int inorder_right){
        if(pre_left> preright) return nullptr;
        //前序遍历中第一个节点就是根节点
        int preorder_root=preorder_left;
        //在中序遍历中定为根节点
        int inorder_root=index[preorder[preorder_root]];

        //先把根节点建立出来
        TreeNode* root=new TreeNode(preorder[preorder_root]);
        //得到左子树的节点数目
        int size_left_subtree=inorder_root-inorder_left;
        //递归的构造左子树并连接到根节点
        root->left=myBuildTree(preorder, inorder, preorder_left+1, preorder_left+size_left_subtree,
            inorder_left, inorder_root-1);
        //递归的构造右子树并连接到根节点
        root->right=myBuildTree(preorder, inorder, preorder_left+size_left_subtree+1, preorder_right,
        inorder_root+1, inorder_right);
        return root;
    }

//93.复原IP地址

//509.斐波那契数列
int fib(int n){
    if(n<2) return n;
    int p=0,q=0,r=1;
    for(int i=2; i<=n; i++){
        p=q;
        q=r;
        r=p+q;
    }
    return r;
}

//134.加油站 贪心算法
int canCompleteCircuit(vector<int>& gas, vector<int>& cost){
    int curSum=0;
    int totalSum=0;
    int start=0;
    for(int i=0; i<gas.size(); i++){
        curSum += gas[i]-cost[i];
        totalSum+=gas[i]-cost[i];
        if(curSum<0){       //当前累加curSum一旦小于0
            start=i+1;      //起始位置更新为i+1
            curSum=0;
        }
    }
    if(totalSum<0) return -1;   //说明怎么走都不可能跑完一圈
    return start;
}

//32.最长有效括号 动态规划解决比较好
int longestVaildParentheses(string s){
    int maxans=0;
    stack<int> stk;
    stk.push(-1);
    for(int i=0; i<s.length();i++){
        if(s[i]==‘(‘){
            stk.push(i);
        }else{
            stk.pop();
            if(stk.empty()){
                stk.push(i);
            }else{
                maxans=max(maxans, i-stk.top());
            }
        }
    }
    return maxans;
}

//13.罗马数字转整数
int romanToInt(string s){
    int result=0;
    map<char, int> luomab={
        {‘I‘, 1},
        {‘V‘, 5},
        {‘X‘, 10},
        {‘L‘, 50},
        {‘C‘, 100},
        {‘D‘, 500},
        {‘M‘, 1000}
    };//初始化哈希表
    for(int i=0; i<s.size(); i++){
        if(luomab[s[i]]<luomab[s[i+1]]){      //s[n]=0;
            result-=luomab[s[i]];
        }else{
            result+=luomab[s[i]];
        }
    }
    return result;
}

//41.缺失的第一个正数
int firstMissingPositive(vector<int>& nums){
    unordered_set<int> hash;
    for(int num:nums){
        if(!hash.count(num)) hash.insert(num);
    }
    for(int i=1; i<=nums.size();i++){
        if(!hash.count(i)) return i;
    }
    return nums.size()+1;
}


//76.最小覆盖子串 滑动窗口 hard 比较有用
string minWindow(string s, string t){
   unordered_map<char, int> map;
   for(char c:t) map[c]++;
   int left=0,cnt=0,minlen=s.size()+1,start=left;
   for(int i=0; i<s.size(); i++){
       if(--map[s[i]] >= 0) ++cnt;
       while(cnt == t.size()){
           if(minlen > i-left+1){
               minlen=i-left+1;
               start=left;
           }
           if(++map[s[left]] > 0) cnt--;        //如果s[left]不在t里边，就是map[s[left]]就是负的，因为前边--了
           left++;
       }
   }
   return minlen==s.size()+1 ? "":s.substr(start, minlen);
}

//199.二叉树的右视图 使用层序遍历，并只保存最后一个节点的值
vector<int> rightSideView(TreeNode* root){
    vector<int> res;
    queue<TreeNode*> q;
    if(!root) return res;
    q.push(root);
    while(!q.empty()){
        int size=q.size();
        res.push_back(q.back()->val);
        while (size--){
            TreeNode* node=q.front();
            q.pop();
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
    }
    return res;
}

//83.删除排序链表中的重复元素
ListNode* deleteDuplicates(ListNode* head){
    ListNode* h=head;
    while(h && h->next){
        if(h->val == h->next->val){
            h->next=h->next->next;
        }else{
            h=h->next;
        }
    }
    return head;
}

//867.转置矩阵
vector<vector<int>> transpose(vector<vector<int>>& matrix){
    int m=matrix.size(), n=matrix[0].size();
    vector<vector<int>> transposed(n, vector<int>(m,0));
    for(int i=0; i<m;i++){
        for(int j=0; j<n;j++){
            transposed[j][i]=matrix[i][j];
        }
    }
    return transposed;
}

//148.排序链表
ListNode* sortList(ListNode* head){

}

//124.二叉树中的最大路径和
int maxpathSum(TreeNode* root){

}

//394.字符串解码 stack 比较实用
string decodeString(string s){
    stack<int> numStack;
    stack<string> resStack;
    int num = 0;
    string res;
    for(int i=0; i<s.size(); i++){
        if(isalpha(s[i])){
            res.push_back(s[i]);
        }else if(isdigit(s[i])){
            num=num*10+s[i]-‘0‘;
        }
        else if(s[i] == ‘[‘){
            resStack.push(res);
            res="";
            numStack.push(num);
            num=0;
        }else{
            for(int j=0; j<numStack.top(); j++){
                resStack.top()+=res;
            }
            numStack.pop();
            res=resStack.top();
            resStack.pop();
        }
    }
    return res;
}

//面试题02.05.链表求和
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2){
    ListNode* dummy=new ListNode(-1),*head=dummy;
    int carry=0,sum=0;
    while(l1 || l2){
        sum=carry;
        if(l1 != nullptr){
            sum+=l1->val;
            l1=l1->next;
        }
        if(l2 != nullptr){
            sum+=l2->val;
            l2=l2->next;
        }
        head->next=new ListNode(sum%10);
        head=head->next;
        carry=sum/10;
    }
    if(carry) head->next=new ListNode(carry);
    return dummy->next;
}

//55.跳跃游戏
bool canJump(vector<int>& nums){
    int k=0;
    for(int i=0; i<nums.size(); i++){
        if(k<i) return false;
        k=max(k, i+nums[i]);
    }
    return ture;
}

//59.螺旋矩阵 上下左右边界要分清楚 模拟法
vector<vector<int>> generateMatrix(int n){
    int l=0, r=n-1, t=0, b=n-1;
    vector<vector<int>> matrix(n, vector<int>(n,0));
    int num=1, target=n*n;
    while(num<=target){
        for(int i=l; i<=r; i++) matrix[t][i]=num++;
        t++;
        for(int i=t; i<=b; i++) matrix[i][r]=num++;
        r--;
        for(int i=r; i>=l; i--) matrix[b][i]=num++;
        b--;
        for(int i=b; i>=t; i--) matrix[i][l]=num++;
        l++;
    }
    return matrix;
}

//剑指Offer04.二维数组中的查找  二分查找
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target){
    int m=matrix.size();
    if(m==0) return false;
    int n=matrix[0].size();
    int i=0,j=n-1;
    while (i<m && j>=0){
        if(matrix[i][j] == target){
            return true;
        }else if(matrix[i][j] < target){
            i++;
        }else{
            j--;
        }
    }
    return false;
}

//18.四数之和 三数之和 排序+双指针
vector<vector<int>> fourSum(vector<int>& nums, int target){
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    if(nums.size()<4) return res;
    int a,b,c,d,n=nums.size();
    for(a=0;a<=n-4;a++){
        if(a>0 && nums[a]==nums[a-1]) continue;     //确保nums[a]改变了
        for(b=a+1;n<=n-3;b++){
            if(b>a+1 && nums[b]==nums[b-1]) continue;   //确保nums[b]改变了
            c=b+1;d=n-1;
            while(c<d){
                if(nums[a]+nums[b]+nums[c]+nums[d]<target){
                    c++;
                }else if(nums[a]+nums[b]+nums[c]+nums[d]>target){
                    d--;
                }else{
                    res.push_back({nums[a], nums[b], nums[c], nums[d]});
                    while(c<d && nums[c+1]==nums[c]){   //确保c变了
                        c++;
                    }
                    while(c<d && nums[d-1]==nums[d]){   //确保d变了
                        d--;
                    }
                    c++;
                    d--;
                }
            }
        }
    }
    return res;
}

//34.在排序数组中查找元素的第一个和最后一个位置 二分查找
vector<int> searchRange(vector<int>& nums, int target){
    if(!nums.size()) return vector<int> {-1,-1};
    int lower=lower_bound(nums, target);
    int upper=upper_bound(nums, target);
    if(lower==nums.size() || nums[lower]!=target) return vector<int>{-1,-1};
    return vector<int>{lower, upper};
}
int lower_bound(vector<int>& nums, int target){
    int l=0,r=nums.size()-1,mid;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(nums[mid]==target){
            r=mid-1;
        }else if(nums[mid]>target){
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    return l;
}
int upper_bound(vector<int>&nums, int target){
    int l=0,r=nums.size()-1,mid;
    while(l<=r){
        mid=l+(r-l)/2;
        if(nums[mid]==target){
            l=mid+1;
        }else if(nums[mid]>target){
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    return r;
}

//1047.删除字符串中的所有相邻重复项
string removeDuplicates(string s){
    string res;
    for(int i=0; i<s.size(); i++){
        if(res.empty() || res.back()!=s[i]){
            res.push_back(s[i]);
        }else{
            res.pop_back();
        }
    }
    return res;
}

//62.不同路径 动态规划 dp[i][j]=dp[i-1][j]+dp[i][j-1]
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 i=0;i<n;i++){
        dp[0][i]=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];
}

//704.二分查找
int search(vector<int>& nums, int target){
    int l=0,r=nums.size()-1,mid;
    while(l<=r){
        mid=l+(r-l)/2;
        if(nums[mid]==target){
            return mid;
        }else if(nums[mid]>target){
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    return -1;
}

//剑指offer10-1.斐波那契数列
int fib(int n){
    if(n<2) return n;
    int q=0,p=0,r=1;
    for(int i=0;i<=n;i++){
        q=p;
        p=r;
        r=(q+p)%1000000007;
    }
    return r;
}


//221.最大正方形 动态规划
int maximalSquare(vector<vector<int>>& matrix){
    if(matrix.size()==0 || matrix[0].size()==0){
        return 0;
    }
    int m=matrix.size(),n=matrix[0].size(),max_side=0;
    vector<vector<int>> dp(m, vector<int>(n,0));    //dp数组
    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(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1;
                }
            }
            max_side=max(max_side, dp[i][j]);
        }
    }
    return max_side*max_side;
}

//88.合并两个有序数组 双指针
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n){
    int k=m-- +n-- -1;
    while(m>=0 && n>=0){
        if(nums1[m]>nums2[n]){
            nums1[k--]=nums1[m--];
        }else{
            nums1[k--]=nums2[n--];
        }
    }
    while(n>=0){
        nums1[k--]=nums2[n--];
    }
}

//198.打家劫舍 dp方程dp[i]=max(nums[i]+dp[i-2], dp[i-1]);
int rob(vector<int>& nums){
    int n=nums.size();
    if(n==1) return nums[0];
    vector<int> dp(n);
    dp[0]=nums[0];
    dp[1]=max(nums[0], nums[1]);
    for(int i=2; i<n; i++){
        dp[i]=max(nums[i]+dp[i-2], dp[i-1]);
    }
    return dp[n-1];
}

//402.移掉K位数字 单调栈
string removeKdigits(string num, int k){
    
}


//剑指Offer52.两个链表的第一个公共节点  相交链表
ListNode* getIntersectionNode(ListNode *headA, ListNode* headB){
    ListNode* node1=headA, *node2=headB;
    while(node1!=node2){
        node1= node1==nullptr? headB:node1->next;
        node2= node2==nullptr? headA:node2->next;
    }
    return node1;
}

//剑指Offer06.从尾到头打印链表
vector<int> reversePrint(ListNode* head){
    //栈
    stack<int> stk;
    vector<int> res;
    while(head){
        stk.push(head->val);
        head=head->next;
    }
    while(stk.size()){
        vec.push_back(stk.top());
        stk.pop();
    }
    return res;
}

//剑指Offer10-II.青蛙跳台阶问题 动态规划 斐波那契数列 dp[i]=dp[i-1]+dp[i-2];
int numWays(int n){
    if(n==0) return 1;
    vector<int> dp(n+1,0);
    dp[0]=1;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        dp[i]=(dp[i-1]+dp[i-2])%100000007;
    }
    return dp[n];
}

//剑指Offer11.旋转数组的最小数字 二分查找
int minArray(vector<int>& numbers){
      int l=0, r=numbers.size()-1;
      while(l<r){
          int mid=(l+r)/2;
          if(numbers[mid]>numbers[r]) l=mid+1;
          else if(numbers[mid]<numbers[r]) r=mid;
          else r--;
      }
      return numbers[l];
}

//234.回文链表 stack
bool isPalindrome(ListNode* head){
    stack<int> stk;
    ListNode* p=head;
    while(p){
        stk.push(p->val);
        p=p->next;
    }
    while(!stk.empty()){
        if(stk.top()==head->val){
            stk.pop();
            head=head->next;
        }else{
            return false;
        }
    }
    return true;
}

//104.二叉树的最大深度 递归
int maxDepth(TreeNode* root){
    if(!root) return 0;
    int left=1+maxDepth(root->left);
    int right=1+maxDepth(root->right);
    return left>right? left:right;
}

//剑指Offer40.最小的k个数 快排
vector<int> getLeastNumbers(vector<int>& arr, int k){
   quickSort(arr, 0, arr.size()-1);
   vector<int> res;
   res.assign(arr.begin(), arr.begin()+k);
   return res; 
}
void quickSort(vector<int>& arr, int l, int r){
    //子数组长度为1时终止递归
    if(l>=r) return;
    int first=l, last=r, key=arr[first];
    while(first<last){  //循环完会把arr分成两部分，左边小于key的值，右边大于 key的值
        while(first<last && key<=arr[last]){
            last--;
        }
        arr[first]=arr[last];
        while(first<last && key>=arr[first]){
            first++;
        }
        arr[last]=arr[first];
    }
    arr[first]=key;
    qucikSort(arr, l, first);
    qucikSort(arr, first+1, r);
}

//64.最小的路径和 动态规划
int minPathSum(vector<vector<int>>& grid){
    int m=grid.size(), n=grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n,0));
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(i==0 && j==0){
                dp[i][j]=grid[i][j];
            }else if(i==0){
                dp[i][j]=dp[i][j-1]+grid[i][j];
            }else if(j==0){
                dp[i][j]=dp[i-1][j]+dp[i][j];
            }else{
                dp[i][j]=min(dp[i-1][j], dp[i][j-1])+dp[i][j];
            }
        }
    }
    return dp[m-1][n-1];
}


//347.前k个高频元素
vector<int> topKFrequent(vector<int>& nums, int k){
    unordered_map<int, int> counts;
    int max_count=0;
    for(const int &num:nums){
        max_count=max(max_count, ++counts[num]); //map统计频次，找出最大的频次
    }

    vector<vector<int>> buckets(max_count+1);
    for(auto p:counts){
        buckets[p.second].push_back(p.first);
    }

    vector<int> ans;
    for(int i=max_count; i>=0 && ans.size()<k; --i){
        for(int num:buckets[i]){
            ans.push_back(num);
            if(ans.size() == k){
                break;
            }
        }
    }
    return ans;
}

//面试题01.01.判断字符是否唯一
bool isUnique(string astr){
    unordered_set<char> hash;
    for(char c:astr){
        if(hash.count(c)){
            return false;
        }else{
            hash.insert(c);
        }
    }
    return true;
}

//面试题02.03.删除中间节点
void deleteNode(ListNode* node){
    node->val=node->next->val;
    node->next=node->next->next;
}

//33.搜索旋转排序数组
int search(vector<int>& nums, int target){
    int l=0, r=nums.size()-1;
    while(l<=r){
        int mid = (l+r)/2;
        if(nums[mid]==target) return mid;
        if(nums[mid]<nums[r]){      //右边是有序的
            if(nums[mid]<target && target<=nums[r]){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }else{      //左边是有序的
            if(nums[mid]>target && target>=nums[l]){
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
    }
    return -1;
}

//剑指Offer26.树的子结构
bool isSubStructure(TreeNode* A, TreeNode* B){
    if(A==nullptr || B==nullptr) return false;
    return compare(A,B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
bool compare(TreeNode* A, TreeNode* B){
    if(B==nullptr) return true;
    if(A==nullptr) return false;
    return (A->val == B->val) && compare(A->left, B->left) && compare(A->right, B->right);
}

//416.分割等和子集 动态规划
bool canPartition(vector<int>& nums){

}

//剑指Offer48.最长不包含重复字符的子字符串
int lengthOfLongestSubstring(string s){
    if(s.size()==0) return 0;
    int maxStr=0;
    int left=0;
    unordered_set<char> lookup;
    for(int i=0; i<s.size(); i++){
        while(lookup.find(s[i] != lookup.end())){
            lookup.erase(s[left]);
            left++;
        }
        lookup.insert(s[i]);
        maxStr=max(maxStr, i-left+1);
    }
    return maxStr;
}

//349.两个数组的交集
vector<int> intersection(vector<int>& nums1, vector<int>& nums2){
    //哈希
    unordered_set<int> hash(nums1.begin(), nums1.end());
    unordered_set<int> hash1;
    vector<int> res;
    for(int num:nums2){
        if(hash.find(num) != hash.end()){
            if(hash1.find(num) == hash1.end()){
                res.push_back(num);
                hash1.insert(num);
            }
        }
    }
    return res;
}

//面试题01.06字符串压缩
string compressString(string s){
    int cnt=1;
    string res;
    for(int i=0; i<s.size(); i++){
        res+=s[i];
        while(s[i]==s[i+1]){
            cnt++;
            i++;
        }
        res+=tostring(cnt);
        cnt=1;
    }
    return res.size()>=s.size()? s:res;
}

//139.单词拆分 动态规划
bool wordBreak(string s, vector<string>& wordDict){
    
}

//35.搜索插入位置 二分查找
int searchInsert(vector<int>& nums, int target){
    if(nums.size()==0) return 0;
    int l=0,r=nums.size()-1,mid;
    while(l<=r){
        mid=(l+r)/2;
        if(nums[mid]==target){
            return mid;
        }else if(nums[mid]>target){
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    return r;
}

//81.搜索旋转排序数组（数组中值可以重复）
bool search(vector<int>& nums, int target) {
    int l=0,r=nums.size()-1;
    while(l<=r){
        while(l<r && nums[l]==nums[l+1]) l++;   //去重
        while(l<r && nums[r]==nums[r-1]) r--;
        int mid=(l+r)/2;
        if(nums[mid]==target) return true;
        if(nums[mid]<nums[r]){
            if(target>nums[mid] && target<=nums[r]){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }else{
            if(target>=nums[l] && target<nums[mid]){
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
    }
    return false;
}


//90.子集II
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path);
        unordered_set<int> uset;
        for (int i = startIndex; i < nums.size(); i++) {
            if (uset.find(nums[i]) != uset.end()) {
                continue;
            }
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 去重需要排序
        backtracking(nums, 0);
        return result;
    }