【leetcode刷题】剑指offer基础版（完结）

一时失言乱红尘 2023-10-10 22:23 19阅读 0赞

##### [剑指 Offer 05. 替换空格][Offer 05.] #####

class Solution {
        
    public:
        string replaceSpace(string s) {
        
            int len = s.size();
            string g;
            for(int i = 0; i < len; i++)
            {
        
                if(s[i] == ' ')
                {
        
                    g += "%20";
                    continue;
                }
                g += s[i];
            }
            return g;
        }
    };

##### [剑指 Offer 58 - II. 左旋转字符串][Offer 58 - II.] #####

class Solution {
        
    public:
        void Reverse(string &a,int left,int right)
        {
        
            while(left < right)
            {
        
                char temp = a[left];
                a[left] = a[right];
                a[right] = temp;
                left++;
                right--;
            }
        }
        string reverseLeftWords(string s, int n) {
        
            int len = s.size();
            if(n >= len)
            {
        
                n %= len;
            }
            Reverse(s,0,n-1);
            Reverse(s,n,len-1);
            Reverse(s,0,len-1);
            return s;
        }   
    };

##### [剑指 Offer 67. 把字符串转换成整数❤️][Offer 67.] #####

class Solution {
        
    public:
        int strToInt(string str) 
        {
        
            int len = str.size();
    
            int i = 0;
            int flag = 1;//标记正负
            long long num = 0;//返回转化后的数字
            while(str[i] == ' ')//去掉前导空格
            {
        
                i++;
            }
            if(str[i] == '+'||str[i] == '-')
            {
        
                if(str[i] =='-')
                    flag = -flag;
                i++;
            }
            while(i < len && str[i] >= '0' && str[i] <= '9')
            {
        
                num = num*10+(str[i]-'0')*flag;
                i++;
                if(flag == -1 && num < INT_MIN )
                {
        
                    return INT_MIN;
                }
                if(flag == 1 && num > INT_MAX  )
                {
        
                    return INT_MAX;
                }
            }
            if(i != len)//没有遍历完就是错误，直接返回当前的值
            {
        
                return num;
            }
            return num;
        }
    };

##### [剑指 Offer 06. 从尾到头打印链表][Offer 06.] #####

class Solution {
        
    public:
        vector<int> reversePrint(ListNode* head) {
        
            vector<int>ret;
            while(head!=NULL)
            {
        
                ret.insert(ret.begin(),head->val);
                head = head->next;
            }
            return ret;
        }
    };

##### [剑指 Offer 24. 反转链表][Offer 24.] #####

class Solution {
        
    public:
        ListNode* reverseList(ListNode* head) {
        
            if(head == nullptr)
            {
        
                return nullptr;
            }
            ListNode * n1 = nullptr;
            ListNode * n2 = head;
            ListNode * n3 = head->next;
            while(n2 != nullptr)
            {
        
                n2->next = n1;
                n1 = n2;
                n2 = n3;
                if(n3 != nullptr)
                {
        
                    n3 = n3->next;
                }
            } 
            return n1;
        }
    };

##### [剑指 Offer 35. 复杂链表的复制][Offer 35.] #####

class Node {
        
    public:
        int val;
        Node* next;
        Node* random;
        
        Node(int _val) {
        
            val = _val;
            next = NULL;
            random = NULL;
        }
    };
    */
    class Solution {
        
    public:
        Node* copyRandomList(Node* head) {
        
            Node * cur = head;
            while(cur)
            {
        
                Node * ne = cur->next;
                Node * newNode = (Node*)malloc(sizeof(Node));
                newNode->val = cur->val;
                newNode->next = ne;
                cur->next = newNode;
                cur = ne;
            }
            cur = head;
            while(cur)
            {
        
                Node * ne = cur->next;
                Node * nene = cur->next->next;
                if(cur->random == nullptr)
                {
        
                    cur->next->random = nullptr;
                }
                else
                {
        
                    cur->next->random = cur->random->next;
                }
                cur = nene;
            }
            Node * newNode1 =nullptr;
            Node * tail = nullptr;
            cur = head;
            while(cur)
            {
        
                Node * ne = cur->next;
                Node * nene = cur->next->next;
                if(newNode1 == nullptr)
                {
        
                    newNode1 = tail = ne;
                }
                else
                {
        
                    tail->next = ne;
                    tail = tail->next;
                }
                cur->next = nene;
                cur = nene;
            }
            return newNode1;
        }
    };

##### [剑指 Offer 18. 删除链表的节点][Offer 18.] #####

/* 
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
        
    public:
        ListNode* deleteNode(ListNode* head, int val) {
        
            ListNode * cur = head;
            ListNode * prev = nullptr;
            while(cur)
            {
        
                ListNode * ne = cur->next;
                if(cur->val == val)
                {
        
                    if(head == cur)//头删
                    {
        
                        head = ne;
                        cur = head;
                    }
                    else
                    {
        
                        prev->next = ne;
                        cur = prev->next;
                    }
                }
                else
                {
        
                    prev = cur;
                    cur = ne;
                }
            }
            return head;
        }
    };

##### [剑指 Offer 22. 链表中倒数第k个节点][Offer 22. _k] #####

/*
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
        
    public:
        ListNode* getKthFromEnd(ListNode* head, int k) {
        
            //快慢指针法
            ListNode * slow = head;
            ListNode * fast = head;
            while(k--)
            {
        
                fast = fast->next;
            }
            while(fast)
            {
        
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    };

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

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
        
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
        {
        
    
            ListNode * newHead = (ListNode*)malloc(sizeof(ListNode));
            newHead->next = nullptr;
            ListNode * tail = newHead;
            while(l1 != nullptr && l2 != nullptr)
            {
        
                if(l1->val <= l2->val)
                {
        
                tail->next = l1;
                tail = tail->next;
                l1 = l1->next;
                }
                else
                {
        
                tail->next = l2;
                tail = tail->next;
                l2 = l2->next;
                }
            }
            if(l1 != nullptr)
            {
        
                tail->next = l1;
            }
            if(l2 != nullptr)
            {
        
                tail->next = l2;
            }
            return newHead->next;
        }
    };

##### [剑指 Offer 52. 两个链表的第一个公共节点][Offer 52.] #####

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
        
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        
            ListNode * curA = headA;
            ListNode * curB = headB;
            int countA = 0;
            int countB = 0;
            while(curA)
            {
        
                curA = curA->next;
                countA++;
            }
            while(curB)
            {
        
                curB = curB->next;
                countB++;
            }
            if(countA > countB)
            {
        
                countA -= countB;
                while(countA--)
                {
        
                    headA = headA->next;
                }
            }
            else
            {
        
                countB -= countA;
                while(countB--)
                {
        
                    headB = headB->next;
                }
            }
            while(headA != nullptr && headB != nullptr)
            {
        
                if(headA == headB)
                {
        
                    return headA;
                }
                headA = headA->next;
                headB = headB->next;
            }
            return nullptr;
        }
    };

##### [剑指 Offer 21. 调整数组顺序使奇数位于偶数前面][Offer 21.] #####

class Solution {
        
    public:
        void exchange(vector<int>&nums,int len)
        {
        
            int * ret = (int*)malloc(sizeof(int) * (len + 1));
            int j = 0;
            for(int i = 0; i < len; i++)
            {
        
                if((nums[i] & 1) == 1)
                {
        
                    ret[j++] = nums[i];
                }
            }
            for(int i = 0; i < len; i++)
            {
        
                if((nums[i] & 1 )== 0)
                {
        
                    ret[j++] = nums[i];
                }
            }
            for(int i = 0; i < len; i++)
            {
        
                nums[i] = ret[i];
            }
        }
        vector<int> exchange(vector<int>& nums) {
        
            int len = nums.size();
            exchange(nums,len);
            return nums;
        }
    };

##### [剑指 Offer 57. 和为s的两个数字][Offer 57. _s] #####

class Solution {
        
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
        
            int len = nums.size();
            unordered_map<int,int>hash;
            vector<int>ret;
            for(int i = 0; i < len; i++)
            {
        
                int num = target - nums[i];
                if(hash.count(num))
                {
        
                    ret.push_back(num);
                    ret.push_back(nums[i]);
                    break;
                }
                hash.insert({
        nums[i],i});
            }
            return ret;
        }
    };

##### [剑指 Offer 59 - I. 滑动窗口的最大值][Offer 59 - I.] #####

class Solution {
        
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        
            int len = nums.size();
            deque<int>q;
            vector<int>ret;
            for(int i = 0; i < nums.size(); i++)
            {
        
                if(!q.empty() && i - k + 1 > q[0]) q.pop_front();//下标小于滑动窗口则头删
                //形成单调递增的队列
                while(!q.empty() && nums[q[q.size()-1]] <= nums[i]) q.pop_back();
                q.push_back(i);
                if(i >= k - 1)
                {
        
                    ret.push_back(nums[q[0]]);
                }
            }
            return ret;
        }
    };

##### [剑指 Offer 58 - I. 翻转单词顺序][Offer 58 - I.] #####

class Solution {
        
    public:
        string reverseWords(string s) {
        
            string ret;
            int i = 0;
            int num = s.size();
            while(i < num)//处理前置空格
            {
        
                if(s[i] != ' ')
                {
        
                    break;
                }
                i++;
            }
            while(s.size() > 0)//处理后置空格
            {
        
                int num = s.size();
                if(s[num-1] != ' ')
                {
        
                    break;
                }
                s.pop_back();
            }
            int len = s.size();
            if(len == 0) return s;
            while(i < len)
            {
        
                int cnt = 0;
                int begin = ret.size();
                while(i < len && s[i] != ' ')
                {
        
                    ret += s[i];
                    i++;
                }
                int end = ret.size();
                reverse(ret.begin()+begin,ret.begin()+end);//部分反转
                while(i < len && s[i] == ' ')
                {
        
                    cnt++;
                    if(cnt == 1)
                    {
        
                        ret += s[i];
                    }
                    i++;
                }
            }
            int num1 = ret.size();
            reverse(ret.begin(),ret.end());
            return ret;
        }
    };

##### [剑指 Offer 09. 用两个栈实现队列][Offer 09.] #####

class CQueue {
        
    public:
        CQueue() {
        
        }
        
        void appendTail(int value) {
        
                p_push.push(value);
        }
        
        int deleteHead() {
        
            if(p_push.empty() && p_pop.empty())
            {
        
                return -1;
            }
            if(!p_pop.empty())
            {
        
                int top = p_pop.top();
                p_pop.pop();
                return top;
            }
            else
            {
        
                while(!p_push.empty())
                {
        
                    p_pop.push(p_push.top());
                    p_push.pop();
                }
            }
            int top = p_pop.top();
            p_pop.pop();
            return top;
        }
    private:
            stack<int>p_push;
            stack<int>p_pop;
    };
    
    /**
     * Your CQueue object will be instantiated and called as such:
     * CQueue* obj = new CQueue();
     * obj->appendTail(value);
     * int param_2 = obj->deleteHead();
     */

##### [剑指 Offer 30. 包含min函数的栈❤️][Offer 30. _min] #####

class MinStack {
        
        stack<int>x_push;
        stack<int>min_push;
    public:
        /** initialize your data structure here. */
        MinStack() {
        
            min_push.push(INT_MAX);
        }
        void push(int x) 
        {
        
            x_push.push(x);
            min_push.push(std::min(min_push.top(),x));//每次插入插最小的值进去，和最小值的栈顶比较。
        }
        
        void pop() {
        
            x_push.pop();
            min_push.pop();
        }    
        int top() {
        
            return x_push.top();
        }    
        int min() {
        
            return min_push.top();
        }
    };
    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack* obj = new MinStack();
     * obj->push(x);
     * obj->pop();
     * int param_3 = obj->top();
     * int param_4 = obj->min();
     */

##### [剑指 Offer 59 - II. 队列的最大值❤️][Offer 59 - II.] #####

class MaxQueue {
        
    public:
        deque<int>val;
        deque<int>vmax;
        MaxQueue() {
        
        }
        
        int max_value() {
        
            if(vmax.empty())
            {
        
                return -1;
            }
            return vmax.front();
        }
        
        void push_back(int value) {
        
            while((!vmax.empty()) && (vmax.back() < value))//单调递减的队列
            {
        
                vmax.pop_back();
            }
            val.push_back(value);
            vmax.push_back(value);
        }
        
        int pop_front() {
        
            if(val.empty())
            {
        
                return -1;
            }
            int ans = vmax.front();
            if(ans == val.front())//只有和最大值相等才需要删除，跟滑动窗口差不多
            {
        
                vmax.pop_front();
            }
            int front = val.front();
            val.pop_front();
            return front;
        }
    };
    
    /**
     * Your MaxQueue object will be instantiated and called as such:
     * MaxQueue* obj = new MaxQueue();
     * int param_1 = obj->max_value();
     * obj->push_back(value);
     * int param_3 = obj->pop_front();
     */

##### [剑指 Offer 29. 顺时针打印矩阵❤️][Offer 29.] #####

class Solution {
        
    private:
            bool flag[110][110]= {
        false};
            int d[4][2]= {
        {
        0,1},{
        1,0},{
        0,-1},{
        -1,0}};
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
        
            vector<int>ret;
            if (matrix.size() == 0 || matrix[0].size() == 0) return ret;
            int rows = matrix.size(),cols = matrix[0].size();
            int sum = rows * cols;
            int tal = 0;
            int row = 0,col = 0;
            int dir = 0;
            for(int i = 0; i < sum; i++)
            {
        
                ret.push_back( matrix[row][col]);
                flag[row][col] = true;
                int a = row + d[dir][0],b = col + d[dir][1];
                //如果越界或者，或者已经插入的数据那么就走向量的下一个
                if(a < 0 || a >= rows || b < 0 || b >= cols || flag[a][b])
                {
        
                    dir = (dir + 1) % 4;
                }
                //一直往某个方向走，直至不合法才进入上面的判定
                row += d[dir][0];
                col += d[dir][1];
            }
            return ret;
        }
    };

##### [剑指 Offer 31. 栈的压入、弹出序列][Offer 31.] #####

class Solution {
        
    public:
        bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        
            stack<int>st;
            int n = pushed.size();
            int j = 0;
            for(int i = 0; i < n; i++)
            {
        
                st.push(pushed[i]);
                while(!st.empty() && st.top() == popped[j])
                {
        
                    j++;
                    st.pop();
                }
            }
            return st.empty();
        }
    };

##### [剑指 Offer 03. 数组中重复的数字][Offer 03.] #####

class Solution {
        
    public:
        int findRepeatNumber(vector<int>& nums) {
        
            unordered_map<int,int>hash;
            int k = 0;
            for(int i = 0; i < nums.size(); i++)
            {
        
                if(hash.count(nums[i]))//hash判断该数有没有出现过
                {
        
                    k = i;
                    return nums[k];
                }
                hash.insert({
        nums[i],i});
            }
            return nums[k];
        }
    };

##### [剑指 Offer 53 - I. 在排序数组中查找数字 I][Offer 53 - I. _ I] #####

//遍历法
    class Solution {
        
    public:
        int search(vector<int>& nums, int target) {
        
            int count = 0;
            for(int i = 0; i < nums.size(); i++)
            {
        
                if(nums[i] > target)
                {
        
                    break;
                }
                if(nums[i] == target)
                {
        
                    count++;
                }
            }
            return count;
        }
    };
    
    //二分法
    // class Solution {
        
    // public:
    //     int search(vector<int>& nums, int target) {
        
    //         if(nums.size() == 0) return 0;
    //         int a = 0,b = 0;
    //         int left = 0,right = nums.size() - 1;
    //         while(left < right)
    //         {
        
    //             int mid = left + right >> 1;
    //             if(nums[mid] >= target) right = mid;
    //             else left = mid + 1;
    //         }
    //         if(nums[left] != target) return 0;
    //         a = left;
    //         left = 0,right = nums.size() - 1;
    //         while(left < right)
    //         {
        
    //             int mid = left + right + 1>> 1;
    //             if(nums[mid] <= target) left = mid;
    //             else right = mid - 1;
    //         }
    //         b = left;
    //         return b - a + 1;
    //     }
    // };

##### [剑指 Offer 53 - II. 0～n-1中缺失的数字][Offer 53 - II. 0_n-1] #####

class Solution {
        
    public:
        int missingNumber(vector<int>& nums) {
        
            int n = nums.size();
            int sum = 0;
            for(int i = 1; i <= n; i++)
            {
        
                sum += i;
            }
            for(int i = 0 ; i < n; i++)
            {
        
                sum -= nums[i];
            }
            return sum;
        }
    };

##### [剑指 Offer 04. 二维数组中的查找][Offer 04.] #####

class Solution {
        
    public:
        bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        
            if(matrix.size() == 0 || matrix[0].size() == 0) return false;   
            int n = 0,m = matrix[0].size() - 1;
            while(n < matrix.size() && m >=0)
            {
        
                if(matrix[n][m] > target) m--;
                else if(matrix[n][m] < target) n++;
                else return true;
            }
            return false;
        }
    };

##### [剑指 Offer 11. 旋转数组的最小数字❤️][Offer 11.] #####

class Solution {
        
    public:
        int minArray(vector<int>& numbers) {
        
            //这是一个左旋数组
            int n = numbers.size();
            //二分查找法
            int left = 0,right = n - 1;
            while(left < right)
            {
        
                int mid = left + right >> 1;
                if(numbers[mid] > numbers[right]) left = mid + 1;
                else if(numbers[mid] < numbers[right]) right = mid;
                //当出现nums[m] = nums[j] 时，一定有区间[i, m] 内所有元素相等 或 区间[m, j] 内所有元素相等（或两者皆满			 足）。对于寻找此类数组的最小值问题，可直接放弃二分查找，而使用线性查找替代。
                else right--;
            }
            return numbers[left];
        }
    };

##### [剑指 Offer 50. 第一个只出现一次的字符][Offer 50.] #####

class Solution {
        
    public:
        char firstUniqChar(string s) {
        
            if(s.size() == 0) return ' ';
            vector<int>h;
            int arr[26] = {
        0};
            for(int i = 0; i < s.size(); i++)
            {
        
                arr[s[i] - 'a']++;
            }
            for(int i = 0; i < s.size(); i++)
            {
        
                if(arr[s[i] - 'a'] == 1)//找到所有只出现一次的字符
                {
        
                    return s[i];
                }
            }
            return ' ';
        }
    };
    
    //哈希法
    class Solution {
        
    public:
        char firstUniqChar(string s) {
        
            unordered_map<int, int> frequency;
            for (char ch: s) {
        
                ++frequency[ch];
            }
            for (int i = 0; i < s.size(); ++i) {
        
                if (frequency[s[i]] == 1) {
        
                    return s[i];
                }
            }
            return ' ';
        }
    };

##### [剑指 Offer 32 - I. 从上到下打印二叉树][Offer 32 - I.] #####

class Solution {
        
    public:
        vector<int> levelOrder(TreeNode* root) {
        
            if(root == nullptr)
            {
        
                return {
        };
            }
            queue<TreeNode*>q;
            vector<int>ret;
            q.push(root);
            while(q.size())
            {
        
                TreeNode * front = q.front();
                ret.push_back(front->val);
                q.pop();
                if(front->left != nullptr)
                {
        
                    q.push(front->left);
                }
                if(front->right != nullptr)
                {
        
                    q.push(front->right);
                }
            }
            return ret;
        }
    };

##### [剑指 Offer 32 - II. 从上到下打印二叉树 II][Offer 32 - II. _ II] #####

//自己写的
    class Solution {
        
    public:
        int RootSize(TreeNode * root)
        {
        
            if(root == nullptr)
            {
        
                return 0;
            }
            int leftmax = RootSize(root->left);
            int rightmax = RootSize(root->right);
            return leftmax > rightmax ? leftmax + 1 : rightmax + 1;
        }
        vector<vector<int>> levelOrder(TreeNode* root) {
        
            if(root == nullptr)
            {
        
                return {
        };
            }
            int num = RootSize(root);//求深度
            typedef pair<TreeNode*,int>PII;
            const int N = 1010;
            PII q[N];
            int hh = 0, tt = 0;
            int i = 0;
            vector<vector<int>>ret(num);
            q[tt] = {
        root,i};
            while(hh <= tt)
            {
        
                PII t = q[hh++];
                TreeNode * front = t.first;
                int k = t.second;
                ret[k].push_back(front->val);
                if(front->left != nullptr)
                {
        
                    q[++tt] = {
        front->left,k + 1};
                }
                if(front->right != nullptr)
                {
        
                    q[++tt] = {
        front->right,k + 1};
                }
            }
            return ret;
        }
    };
    //官方题解
    class Solution {
        
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
        
            vector <vector <int>> ret;
            if (!root) {
        
                return ret;
            }
    
            queue <TreeNode*> q;
            q.push(root);
            while (!q.empty()) {
        
                int currentLevelSize = q.size();
                ret.push_back(vector <int> ());
                for (int i = 1; i <= currentLevelSize; ++i) {
        
                    auto node = q.front(); q.pop();
                    ret.back().push_back(node->val);
                    if (node->left) q.push(node->left);
                    if (node->right) q.push(node->right);
                }
            }
            
            return ret;
        }
    };

##### [剑指 Offer 32 - III. 从上到下打印二叉树 III][Offer 32 - III. _ III] #####

class Solution {
        
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
        
            if(root == nullptr) return {
        };
            queue<TreeNode*>q;
            vector<vector<int>>ret;
            q.push(root);
            while(!q.empty())
            {
        
                int num = q.size();
                ret.push_back(vector<int>());
                for(int i = 0; i < num; i++)
                {
        
                    auto node = q.front();
                    q.pop();
                    ret.back().push_back(node->val);//在尾部进行尾插，因为插入了二维空vector
                    if(node->left) q.push(node->left);
                    if(node->right) q.push(node->right);
                }
            }
            int k = ret.size();
            for(int i = 0; i < k; i++)
            {
        
                if(i % 2 != 0)//奇数反转
                {
        
                    reverse(ret[i].begin(),ret[i].end());
                }
            }
            return ret;
        }
    };

##### [剑指 Offer 26. 树的子结构❤️][Offer 26.] #####

//我写的
    class Solution {
        
    public:
        bool IsSame(TreeNode * A,TreeNode * B)
        {
        
            if(B == nullptr) return true;//如果子结构为空那就是真
            if(A == nullptr) return false;//子结构不空，主结构空就false
            
            if(A->val == B->val)
            {
        
                //只有子结构完全匹配才是true
                return IsSame(A->left, B->left) && IsSame(A->right, B->right);
            }
            return false;
        }
        void TraverseTree(TreeNode * A,TreeNode * B,bool &flag)
        {
        
            if(A == nullptr) return;
            TraverseTree(A->left,B,flag);//递归到最底部
            if(flag) return;//如果flag变成了真就直接返回了，不需要继续递归
            TraverseTree(A->right,B,flag);
            if(A->val == B->val)
            {
        
                flag = IsSame(A,B);
            }
        }
        bool isSubStructure(TreeNode* A, TreeNode* B) {
        
            if(A == nullptr || B == nullptr) return false;
            bool flag = false;//最初是false
            TraverseTree(A,B,flag);
            return flag;
        }
    };
    //题解：
    class Solution {
        
    public:
        bool isSubStructure(TreeNode* A, TreeNode* B) {
        
            if (A == NULL || B == NULL) return false;
            if (A->val == B->val) {
        
                if (dfs_isEqual(A, B)) {
        
                    return true;
                }
            }
            return isSubStructure(A->left, B) || isSubStructure(A->right, B);
        }
    
        bool dfs_isEqual(TreeNode* A, TreeNode* B) {
        
            if (B == NULL) return true;
            if (A == NULL) return false;
            if (A->val == B->val) {
         
                return dfs_isEqual(A->left, B->left) && dfs_isEqual(A->right, B->right);
            } else {
        
                return false;
            }
        }
    };

##### [剑指 Offer 27. 二叉树的镜像][Offer 27.] #####

class Solution {
        
    public:
        TreeNode* mirrorTree(TreeNode* root) {
        
            if(root == nullptr)
            {
        
                return root;
            }
            mirrorTree(root->left);
            mirrorTree(root->right);
            if(root->left != nullptr || root->right != nullptr)
            {
        
                TreeNode * tmp = root->left;
                root->left = root->right;
                root->right = tmp;
            }
            return root;
        }
    };

##### [剑指 Offer 28. 对称的二叉树][Offer 28.] #####

//我写的
    class Solution {
        
    public:
        void mirrorTree(TreeNode * root)
        {
        
            if(root == nullptr) return;
            mirrorTree(root->left);
            mirrorTree(root->right);
            if(root->left != nullptr || root->right != nullptr)
            {
        
                TreeNode * tmp = root->left;
                root->left = root->right;
                root->right = tmp;
            }
            return;
        }
        bool IsEmpty(TreeNode * A,TreeNode * B)
        {
        
            if(A == nullptr && B == nullptr) return true;
            if(A == nullptr || B == nullptr) return false;
            if(A->val == B->val)
            {
        
                return IsEmpty(A->left,B->left) && IsEmpty(A->right,B->right);
            }
            return false;
        }
        bool isSymmetric(TreeNode* root) {
        
            if(root == nullptr) return true;
            mirrorTree(root->right);
            bool flag = IsEmpty(root->left,root->right);
            return flag;
        }
    };
    //官方题解
    class Solution {
        
    public:
        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);
        }
    
        bool isSymmetric(TreeNode* root) {
        
            return check(root, root);
        }
    };

##### [剑指 Offer 12. 矩阵中的路径❤️][Offer 12.] #####

class Solution {
        
    public:
        //DFS算法
        bool IsEmpty(vector<vector<char>>& board, vector<vector<int>>&visited,
                    int rows,int cols,string word,int k)
        {
        
           int a = board.size(),b = board[0].size();
           if(board[rows][cols] != word[k]) return false;//如果字符不同为假
           else if(k == word.size()-1) return true;//匹配成功返回
           visited[rows][cols] = true;
           bool result = false;
    
           for(int i = 0; i < 4; i++)
           {
        
               int x = rows + dx[i],y = cols + dy[i];
               if(x >= 0 && x < a && y >= 0 && y < b)//判断边界
               {
        
                   if(!visited[x][y])//判断是否访问过
                   {
        
                       bool flag = IsEmpty(board, visited, x, y, word, k + 1);
                       if(flag) return true;//如果成功直接返回
                   }
               }
           }
           visited[rows][cols] = false;//跳出循环要取消标记
           return result;
        }
        bool exist(vector<vector<char>>& board, string word) {
        
            int row = board.size(),col = board[0].size();
            vector<vector<int>>visited(row,vector<int>(col));
            bool flag = false;
            for(int i = 0; i < row; i++)
                for(int j = 0; j < col; j++)
                {
        
                    flag = IsEmpty(board,visited,i,j,word,0);
                    if(flag) return true;
                }
            return false;
        }
    private:
        int dx[4] = {
        0,0,-1,1};
        int dy[4] = {
        1,-1,0,0};
    };

##### [剑指 Offer 13. 机器人的运动范围❤️][Offer 13.] #####

//我写的dfs
    class Solution {
        
    public:
        int get(int x)
        {
        
            int sum = 0;
            while(x > 0)
            {
        
                sum += x % 10;
                x /= 10;
            }
            return sum;
        }
        void check(vector<vector<int>>&ans, int row, int col, int k, int &res, int sum, int o)
        {
        
            if(sum > k) return;
            res++;
            int a = ans.size(),b = ans[0].size();
            ans[row][col] = true;//走过就不要走了
            for(int i = 0; i < 2; i++)
            {
        
                int x = row + dx[i], y = col + dy[i];
                if(x >= 0 && x < a && y >= 0 && y < b && !ans[x][y])
                {
        
                        int q = get(x), p = get(y);
                        int sum1 = p + q;
                        check(ans,x,y,k,res,sum1,o+1);
                }    
            }
        }
        int movingCount(int m, int n, int k) 
        {
        
            if(k == 0) return 1;
            vector<vector<int>>ans(m,vector<int>(n));
            int res = 0;//表示走格子的最大值
            int o = 1;
            int sum = 0;//记录数位和
            check(ans,0,0,k,res,sum,o); 
            return res;
        }
    private:
        int dx[4] = {
        1,0};//优化成下和右
        int dy[4] = {
        0,1};
    };
    //官方题解bfs
    class Solution {
        
        // 计算 x 的数位之和
        int get(int x) {
        
            int res=0;
            for (; x; x /= 10) {
        
                res += x % 10;
            }
            return res;
        }
    public:
        int movingCount(int m, int n, int k) {
        
            if (!k) return 1;
            queue<pair<int,int> > Q;
            // 向右和向下的方向数组
            int dx[2] = {
        0, 1};
            int dy[2] = {
        1, 0};
            vector<vector<int> > vis(m, vector<int>(n, 0));
            Q.push(make_pair(0, 0));
            vis[0][0] = 1;
            int ans = 1;
            while (!Q.empty()) {
        
                auto [x, y] = Q.front();
                Q.pop();
                for (int i = 0; i < 2; ++i) {
        
                    int tx = dx[i] + x;
                    int ty = dy[i] + y;
                    if (tx < 0 || tx >= m || ty < 0|| ty >= n 
                       || vis[tx][ty]||get(tx)+get(ty) > k) continue;
                    Q.push(make_pair(tx, ty));
                    vis[tx][ty] = 1;
                    ans++;
                }
            }
            return ans;
        }
    };

##### [剑指 Offer 34. 二叉树中和为某一值的路径❤️][Offer 34.] #####

class Solution {
        
    public:
        vector<vector<int>>ret;
        vector<int>path;
        void dfs(TreeNode * root,int target)
        {
        
            if(root == nullptr) return;
            path.emplace_back(root->val);
            target -= root->val;
            //只有是叶子节点的路径并且目标值为0才插入路径
            if(root->left == nullptr && root->right == nullptr && target == 0)
            {
        
                ret.emplace_back(path);
            }
            dfs(root->left,target);
            dfs(root->right,target);
            path.pop_back();//回退时删除该路径的值
        }
        vector<vector<int>> pathSum(TreeNode* root, int target) {
        
            if(root == nullptr) return {
        };
            dfs(root,target);
            return ret;
        }
    };

##### [剑指 Offer 54. 二叉搜索树的第k大节点❤️][Offer 54. _k] #####

//利用优先队列做法
    class Solution {
        
    public:
            priority_queue<int,vector<int>>q;
            void PreInorder(TreeNode * root)
            {
        
                if(root == nullptr) return;
                q.push(root->val);
                PreInorder(root->left);
                PreInorder(root->right);
            }
            int kthLargest(TreeNode* root, int k) {
        
            PreInorder(root);
            int maxi = -1e9;
            while(k--) 
            {
        
                maxi = q.top();
                q.pop();
            }
            return maxi;
        }
    };

##### [17. 电话号码的字母组合][17.] #####

class Solution {
        
        char * str[10] = {
        "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//绝对映射
    public:
        void dfs(string digits,vector<string>&v,int di,string conbina)
        {
        
            if(di == digits.size()) 
            {
        
                v.push_back(conbina);
                return;
            }
            int num = digits[di] - '0';//取出数字
            string s = str[num];
            for(auto ch : s)
            {
        
                dfs(digits,v,di + 1,conbina + ch);//conbina不用+=的好处时栈峥回退不用尾删
            }
        }
        vector<string> letterCombinations(string digits) {
        
            vector<string>v;
            if(digits.empty()) return v;
            int di = 0;
            string conbina;
            dfs(digits,v,di,conbina);
            return v;
        }
    };

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

class Solution {
        
    public:
        //二叉搜索树是左小右大，所以进行中序遍历
        void dfs(Node * cur)
        {
        
            if(cur == nullptr) return;
            dfs(cur->left);
            if(head == nullptr) 
            {
        
                head = tail = cur;//无数据要先插入
            }
            else
            {
        
                //双链表的相互指向
                tail->right = cur;
                cur->left = tail;
                tail = cur;
            }
            dfs(cur->right);
        }
        Node* treeToDoublyList(Node* root) 
        {
        
            if(root == nullptr) return nullptr;
            dfs(root);
            //设置为循环链表
            head->left = tail;
            tail->right = head;
            return head;
        }
    
    private:
        Node * head = nullptr;
        Node * tail = nullptr;
    };

##### [剑指 Offer 55 - I. 二叉树的深度][Offer 55 - I.] #####

##### [剑指 Offer 55 - II. 平衡二叉树][Offer 55 - II.] #####

class Solution {
        
    public:
        int maxDepth(TreeNode * root)
        {
        
            if(root == nullptr) return 0;
            int leftmax = maxDepth(root->left);
            int rightmax = maxDepth(root->right);
            return leftmax > rightmax ? leftmax + 1 : rightmax + 1;
        }
        bool isBalanced(TreeNode* root)
        {
        
            if(root==NULL)
            {
        
                return true;
            }
            int leftmax = maxDepth(root->left);
            int rightmax = maxDepth(root->right);
            return abs(leftmax-rightmax)<2 && isBalanced(root->left) && isBalanced(root->right);
        }
    };

##### [剑指 Offer 64. 求1+2+…+n][Offer 64. _1_2_n] #####

class Solution {
        
    public:
        int sumNums(int n) {
        
            n && (n += sumNums(n - 1));
            return n;
        }
    };

##### [剑指 Offer 68 - I. 二叉搜索树的最近公共祖先][Offer 68 - I.] #####

class Solution {
        
    public:
        vector<TreeNode*>GetPath(TreeNode * root,TreeNode *target)
        {
        
            vector<TreeNode*>ret;
    
            while(root != target)
            {
        
                ret.push_back(root);
                if(root->val > target->val)
                {
        
                    root = root->left;
                }   
                else
                {
        
                    root = root->right;
                }
            }
            ret.push_back(root);
            return ret;
        }
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
            vector<TreeNode*>path_p = GetPath(root,p);//保存路径
            vector<TreeNode*>path_q = GetPath(root,q); 
            TreeNode * res = nullptr;
            for(int i = 0; i < path_p.size() && i < path_q.size(); i++)
            {
        
                if(path_p[i] == path_q[i])//寻找最近的公共祖先
                {
        
                    res = path_p[i];
                }
                else{
        
                    break;
                }
            }
            return res;
        }
    };

##### [剑指 Offer 68 - II. 二叉树的最近公共祖先][Offer 68 - II.] #####

class Solution {
        
    public:
        bool GetPath(vector<TreeNode*>&path,TreeNode*root,TreeNode * target)
        {
        
            if(root == nullptr) return false; //没找到   
            if(root == target)
            {
        
                path.push_back(root);//找到将找到的也要插进去
                return true;
            }
            path.push_back(root);
            bool left1 = GetPath(path,root->left,target);
            if(left1) return true;
            bool right1 = GetPath(path,root->right,target);
            if(right1) return true;
            path.pop_back();//没找到退出的时候要删除路径
            return false;
        }
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
            vector<TreeNode*>path_p;
            vector<TreeNode*>path_q;
            bool p1 = GetPath(path_p,root,p);
            bool q1 = GetPath(path_q,root,q);
             TreeNode * res = nullptr;
            for(int i = 0; i < path_p.size() && i < path_q.size(); i++)
            {
        
                if(path_p[i] == path_q[i])//寻找最近的公共祖先
                {
        
                    res = path_p[i];
                }
                else{
        
                    break;
                }
            }
            return res;
        }
    };

##### [剑指 Offer 37. 序列化二叉树❤️][Offer 37.] #####

class Codec {
        
    public:
        void rserialize(TreeNode * root,string & ret)
        {
        
            //前序遍历转为字符串
            if(root == nullptr) 
            {
        
                ret += "#,";
                return;
            }
            ret += to_string(root->val);//字符转换函数
            ret += ",";
            rserialize(root->left,ret);
            rserialize(root->right,ret);
        }
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
        
            string ret;
            rserialize(root,ret);
            return ret;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* rdeserialize(list<string>&dateArray)
        {
        
            if(dateArray.front() == "#")
            {
        
                dateArray.erase(dateArray.begin());
                return nullptr;
            }
            TreeNode * root = new TreeNode(stoi(dateArray.front()));//将字符串转为数字
            dateArray.erase(dateArray.begin());//插入后删除
            root->left = rdeserialize(dateArray);
            root->right = rdeserialize(dateArray);
            return root;
        }
        TreeNode* deserialize(string data) {
        
            list<string>dateArray;//用链表存字符串
            string str;
            for(auto& c : data)
            {
        
                if(c == ',')
                {
        
                    dateArray.push_back(str);
                    str.clear();
                }
                else
                {
        
                    str.push_back(c);
                }
            }
            if(!str.empty()) //如果后面有节点就需要插入在清空
            {
        
                dateArray.push_back(str);
                str.clear();
            }
            return rdeserialize(dateArray);
        }
    };
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec;
    // codec.deserialize(codec.serialize(root));

##### [剑指 Offer 38. 字符串的排列❤️][Offer 38.] #####

//我写的
    class Solution {
        
    public:
        unordered_map<string,int>hash;
        void dfs(string s,vector<string>& ret,int len,string str,vector<int>&flag)
        {
        
            if(str.size() == len)
            {
        
                if(!hash.count(str))
                {
        
                    ret.push_back(str);
                    hash.insert({
        str,1});
                }
                return;
            }
            for(int i = 0; i < s.size(); i++)
            {
        
                if(!flag[i])
                {
        
                    flag[i] = true;
                    dfs(s,ret,len,str + s[i],flag);
                    flag[i] = false;
                }
            }
        }
        vector<string> permutation(string s) {
        
            int len = s.size();
            vector<string>ret;      
            vector<int>flag;
            flag.resize(len);  
            string str;
            dfs(s,ret,len,str,flag);
            return ret;
        }
    };
    //官方题解
    // class Solution {
        
    // public:
    //     vector<string> rec;
    //     vector<int> vis;
    
    //     void backtrack(const string& s, int i, int n, string& perm) {
        
    //         if (i == n) {
        
    //             rec.push_back(perm);
    //             return;
    //         }
    //         for (int j = 0; j < n; j++) {
        
    //             if (vis[j] || (j > 0 && !vis[j - 1] && s[j - 1] == s[j])) {
        
    //                 continue;
    //             }
    //             vis[j] = true;
    //             perm.push_back(s[j]);
    //             backtrack(s, i + 1, n, perm);
    //             perm.pop_back();
    //             vis[j] = false;
    //         }
    //     }
    
    //     vector<string> permutation(string s) {
        
    //         int n = s.size();
    //         vis.resize(n);
    //         sort(s.begin(), s.end());
    //         string perm;
    //         backtrack(s, 0, n, perm);
    //         return rec;
    //     }
    // };

##### [剑指 Offer 17. 打印从1到最大的n位数][Offer 17. _1_n] #####

class Solution {
        
    public:
        vector<int> printNumbers(int n) {
        
            vector<int>ret;
            if(n == 0) return ret;
            int k = 1;
            while(n--)
            {
        
                k *= 10;
            }
            for(int i = 1; i < k; i++)
            {
        
                ret.push_back(i);
            }
            return ret;
        }
    };

##### [剑指 Offer 51. 数组中的逆序对][Offer 51.] #####

class Solution {
        
    public:
        int merge(vector<int>&nums,int left,int right,vector<int>&tmp)
        {
        
            if(left >= right) return 0;
            int mid = (left + right) >> 1;
            int res = merge(nums,left,mid,tmp) + merge(nums,mid+1,right,tmp);
            int k = 0,i = left,j = mid + 1;
            while(i <= mid && j <= right)
            {
        
                if(nums[i] <= nums[j])
                {
        
                    tmp[k++] = nums[i++];
                }
                else
                {
        
                    tmp[k++] = nums[j++];
                    //只有q[i]>q[j]时才是逆序对，若是它大于q[j]了，那么mid-i+1的数都会大于q[j]，都属于逆序对，这是进行扫尾
                    res += mid - i + 1;
                }
            }
            while(i <= mid)
            {
        
                tmp[k++] = nums[i++];
            }
            while(j <= right)
            {
        
                tmp[k++] = nums[j++];
            }
            for(int i = left,j = 0; i <= right; i++, j++)
            {
        
                nums[i] = tmp[j];
            }
            return res;
        }
        int reversePairs(vector<int>& nums) {
        
            if(nums.size() == 0) return 0;
            vector<int>tmp;
            int len = nums.size();
            tmp.resize(len+1);
            return merge(nums,0,len-1,tmp);
        }
    };

##### [剑指 Offer 07. 重建二叉树][Offer 07.] #####

class Solution {
        
    private:
        unordered_map<int, int> hash;
    public:
        TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& prei,
                            int in_begin,int in_end) 
                            {
        
            if(in_begin > in_end) 
                return nullptr;
            TreeNode* root = new TreeNode(preorder[prei++]);
            int root_size = hash[root->val];
            root->left = _buildTree(preorder,inorder,prei,in_begin,root_size-1);
            root->right = _buildTree(preorder,inorder,prei,root_size+1,in_end);
            return root;
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        
           for(int i = 0; i < inorder.size(); i++)
            {
        
                hash.insert({
        inorder[i],i});
            }
            int i = 0;
            return _buildTree(preorder,inorder,i,0,inorder.size()-1);
        }
    };

##### [剑指 Offer 16. 数值的整数次方][Offer 16.] #####

class Solution {
        
    public:
        double Pow(double x,long long n)
        {
        
           if(n == 0) return 1.0;
           double y = Pow(x,n / 2);//快速幂算法
           //如果n为偶数就是返回的结果的平方，否则就是返回的结果多乘x
           return n % 2 == 0? y * y : y * y * x;
        }
        double myPow(double x, int n) 
        {
        
            if(n == 0) return 1.0;
            long long N = n;//防止越界
            return N >= 0 ? Pow(x,N) : 1 / Pow(x,-N);
        }
    };

##### [剑指 Offer 45. 把数组排成最小的数❤️][Offer 45.] #####

class Solution {
        
    public:
        void quick_sort(vector<string>&str, int left, int right)
        {
        
            if(left >= right) return;
            int i = left,j = right;
            while(i < j)
            {
        
                //找小
                while(i < j && str[j] + str[left] >= str[left] + str[j]) j--;//必须先从右往左
                //找大
                while(i < j && str[i] + str[left] <= str[left] + str[i]) i++;
                 if(i < j) swap(str[i],str[j]);
            }
            swap(str[left],str[j]);
            quick_sort(str,left,j - 1);
            quick_sort(str,j + 1,right);
        }
        string minNumber(vector<int>& nums) {
        
            vector<string>str;
            int len = nums.size();
            for(int i = 0; i < len; i++)
            {
        
                str.push_back(to_string(nums[i]));
            }
            quick_sort(str,0,len-1);
            string ret;
            for(auto ch : str)
            {
        
                ret += ch;
            }
            return ret;
        }
    };

##### [剑指 Offer 61. 扑克牌中的顺子][Offer 61.] #####

class Solution {
        
    public:
        bool isStraight(vector<int>& nums) {
        
            //大小王相当于赖子，只要最大值和最小值的差小于5肯定是顺子
            int maxi = 0, mini = 14;
            unordered_map<int,int>hash;
            for(int i = 0; i < 5; i++)
            {
        
                if(nums[i] == 0) continue;//遇到大小王跳过
                maxi = ::max(nums[i],maxi);
                mini = ::min(nums[i],mini);
                if(hash.count(nums[i]))//如果重复则不是顺子
                {
        
                    return false;
                }
                hash.insert({
        nums[i],i});
            }
            if(maxi - mini < 5) return true;
            return false;
        }
    };

##### [剑指 Offer 40. 最小的k个数][Offer 40. _k] #####

class Solution {
        
    public:
        vector<int> getLeastNumbers(vector<int>& arr, int k) {
        
            vector<int>ret;
            priority_queue<int,vector<int>,greater<int>>q;
            for(auto ch : arr)
            {
        
                q.push(ch);
            }
            while(k--)
            {
        
                int top = q.top();
                q.pop();
                ret.push_back(top);
            }
            return ret;
        }
    };

##### [150. 逆波兰表达式求值][150.] #####

class Solution {
        
    public:
        int evalRPN(vector<string>& tokens) {
        
            stack<int>st;
            for(auto& ch : tokens)
            {
        
                if(ch == "+" || ch == "-" || ch == "*" || ch == "/")
                {
        
                    int right = st.top();
                    st.pop();
                    int left = st.top();
                    st.pop();
                    char str = ch[0];
                    int num;
                    switch(str)
                    {
        
                        case '+':
                            num = left + right;
                            st.push(num);
                            break;
                        case '-':
                            num = left - right;
                            st.push(num);
                            break;
                        case '*':
                            num = left * right;
                            st.push(num);
                            break;
                        case '/':
                            num = left / right;
                            st.push(num);
                            break;
                    }
                }
                else
                {
        
                    st.push(stoi(ch));
                }
            }
            return st.top();
        }
    };

##### [剑指 Offer 10- I. 斐波那契数列][Offer 10- I.] #####

class Solution {
        
    public:
        int fib(int n) {
        
            long long * dp = new long long [110];
            dp[0] = 0;
            dp[1] = 1;
            for(int i = 2; i <= n; i++)
            {
        
                dp[i] = (dp[i - 1] + dp[i - 2])%(1000000007);
            }
            return(int)dp[n];
        }
    };

##### [剑指 Offer 10- II. 青蛙跳台阶问题][Offer 10- II.] #####

class Solution {
        
    public:
        int numWays(int n) {
        
            long long * dp = new long long [110];
            dp[0] = 1;
            dp[1] = 1;
            for(int i = 2; i <= n; i++)
            {
        
                dp[i] = (dp[i - 1] + dp[i - 2])%(1000000007);
            }
            return(int)dp[n];
        }
    };

##### [剑指 Offer 63. 股票的最大利润❤️][Offer 63.] #####

class Solution {
        
    public:
        int maxProfit(vector<int>& prices) {
        
            int len = prices.size();
            int mini = 0x3f3f3f3f;//买股票的最小值
            int maxi = 0;//卖股票的最大值
            for(auto price : prices)
            {
        
                maxi = max(maxi,price - mini);
                mini = min(mini,price);
            }
            return maxi;
        }
    };

##### [剑指 Offer 42. 连续子数组的最大和][Offer 42.] #####

class Solution {
        
    public:
        int maxSubArray(vector<int>& nums) {
        
            vector<int>dp(nums.size(),0);
            dp[0] = nums[0];
            for(int i = 1; i < nums.size(); i++)
            {
        
                dp[i] = max(dp[i - 1] + nums[i],nums[i]);
            }
            int maxi = -0x3f3f3f3f;
            for(int i = 0; i < nums.size(); i++)
            {
        
                maxi = max(dp[i],maxi);
            }
            return maxi;
        }
    };

##### [剑指 Offer 47. 礼物的最大价值❤️][Offer 47.] #####

class Solution {
        
    public:
        int maxValue(vector<vector<int>>& grid) {
        
            //动态规划
            int m = grid.size(), n = grid[0].size();
            vector<vector<int>> dp(m, vector<int>(n));
           for(int i = 0; i < m; i++)
           {
        
               for(int j = 0; j < n; j++)
               {
        
                   if(i > 0)//只有大于0，才有向上走的那一步
                   {
        
                       dp[i][j] = max(dp[i][j],dp[i-1][j]);
                   }
                   if(j > 0)//只有大于0，才有向左走的那一步
                   {
        
                       dp[i][j] = max(dp[i][j],dp[i][j -1]);
                   }
                   dp[i][j] += grid[i][j];//确定了当前位置的上一步后就可以加当前的价值了
               }
           }
            return dp[m - 1][n - 1];
        }
    };

##### [剑指 Offer 46. 把数字翻译成字符串][Offer 46.] #####

class Solution {
        
    public:
        int translateNum(int num) {
        
            string str = to_string(num);
            int len = str.size();
            vector<int>dp(len+1,0);
            //类似青蛙跳台阶问题，青蛙可以一直跳一个台阶，跳两个台阶要分情况
            dp[0] = 1;
            dp[1] = 1;
            for(int i = 2; i <= len; i++)
            {
        
                string sub = str.substr(i - 2,2);//从第几位开始取多少位字符串
                if(sub <= "25" && sub >= "10")
                {
        
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
                else
                {
        
                    dp[i] = dp[i - 1];
                }
            }
            return dp[len];
        }
    };

##### [剑指 Offer 64. 求1+2+…+n][Offer 64. _1_2_n] #####

class Sum
    {
        
    public:
        Sum()
        {
        
            _sum += _i;
            _i++;
        }
        static int get()
        {
        
            return _sum;
        }
        void Destroy()
        {
        
            _sum = 0;
            _i = 1;
        }
    private:
        static int _i;
        static int _sum;
    };
    int Sum::_sum = 0;
    int Sum::_i = 1;
    int func(int n)
    {
        
        Sum *s = new Sum[n];
        int ret = s->get();
        s->Destroy();//因为leetcode是全部测试用例用完才销毁，要重置，并且不能用析构
        return ret;
    }
    class Solution {
        
    public:
        int sumNums(int n) {
        
            return func(n);
        }
    };

##### [剑指 Offer 48. 最长不含重复字符的子字符串❤️][Offer 48.] #####

class Solution {
        
    public:
        int lengthOfLongestSubstring(string s) {
        
            int len = s.size();
            if(len == 0) return 0;
            if(len == 1) return 1;
            vector<int>dp(len,0);
            dp[0] = 1;
            int maxlen = 0;
            int tmp = 0;
    
            for(int i = 1; i < len; i++)
            {
        
                int j = i - 1;
                while(j >= 0 && s[i] != s[j]) j--;
                if(dp[i-1] < i - j) dp[i] = dp[i-1] + 1;//第j个字符不在dp[i-1]的区间之内
                else dp[i] = i - j;//第j个字符在dp[i-1]的区间之内
                if(dp[i] > maxlen) maxlen = dp[i];
            }
            return maxlen;
        }
    };

##### [264. 丑数 II][264. _ II] #####

class Solution {
        
    public:
        int nthUglyNumber(int n) {
        
            priority_queue<double,vector<double>,greater<double>>q;
            double ans = 1;
            for(int i = 1; i < n; i++)
            {
        
                q.push(ans*2);
                q.push(ans*3);
                q.push(ans*5);
                ans = q.top();
                q.pop();
                while(!q.empty() && q.top() == ans) q.pop();
            }
            return ans;
        }
    };

##### [剑指 Offer 15. 二进制中1的个数][Offer 15. _1] #####

class Solution {
        
    public:
        int hammingWeight(uint32_t n) {
        
            int count = 0;
            while(n)
            {
        
                n = n & (n - 1);
                count++;
            }
            return count;
        }
    };

##### [剑指 Offer 65. 不用加减乘除做加法][Offer 65.] #####

class Solution {
        
    public:
        int add(int a, int b) {
        
            while (b != 0) {
        
                unsigned int carry = (unsigned int)(a & b) << 1;
                a = a ^ b;
                b = carry;
            }
            return a;
        }
    };

##### [剑指 Offer 56 - I. 数组中数字出现的次数][Offer 56 - I.] #####

class Solution {
        
    public:
        vector<int> GetNum(vector<int>&nums, int sz)
        {
        
            vector<int>ret;
            int k = 0;
            for(int i = 0; i < 31; i++)
            {
        
                if((sz >> i) & 1 == 1) 
                {
        
                    k = i;
                    break;
                }
            }
            int a = 0, b = 0;
            for(int i = 0; i < nums.size(); i++)
            {
        
                if(((nums[i] >> k) & 1) == 0)
                {
        
                    a ^= nums[i];
                }
                else
                {
        
                    b ^= nums[i];
                }
            }
            ret.push_back(a);
            ret.push_back(b);
            return ret;
        }
        vector<int> singleNumbers(vector<int>& nums) 
        {
        
            vector<int>ret;
            int sz = 0;
    
            for(int i = 0; i < nums.size(); i++)
            {
        
                sz ^= nums[i];
            }
            return GetNum(nums,sz);
        }
    };

##### [剑指 Offer 56 - II. 数组中数字出现的次数 II][Offer 56 - II. _ II] #####

class Solution {
        
    public:
        int singleNumber(vector<int>& nums) {
        
            if(nums.size() == 1) return nums[0];
            sort(nums.begin(),nums.end());
            for(int i = 1; i < nums.size()-1; i++)
            {
        
                if(nums[i] != nums[i - 1] && nums[i] != nums[i + 1])
                {
        
                    return nums[i];
                }
            }
            if(nums[0] != nums[1]) return nums[0];//边界问题
            return nums[nums.size() - 1];//两个边界另外处理
        }
    };

##### [剑指 Offer 39. 数组中出现次数超过一半的数字][Offer 39.] #####

class Solution {
        
    public:
        int majorityElement(vector<int>& nums) {
        
            if(nums.size() == 1) return nums[0];
            sort(nums.begin(),nums.end());
            int count = 1;
            int sz = nums[0];
            int len = nums.size() / 2;
            for(int i = 1; i < nums.size(); i++)
            {
        
                if(count > len)
                {
        
                    break;
                }
                if(sz == nums[i])
                {
        
                    count++;
                }
                else
                {
        
                    sz = nums[i];
                    count = 1;
                }
            }
            return sz;
        }
    };

##### [剑指 Offer 66. 构建乘积数组][Offer 66.] #####

class Solution {
        
    public:
        vector<int> constructArr(vector<int>& a) {
        
            vector<int>ret;
            if(a.size() == 0) return ret;
            int len = a.size();
            vector<int>left(len,0);
            vector<int>right(len,0);
            left[0] = 1;//因为左侧没有元素，所以赋值为1
            for(int i = 1; i < len; i++)
            {
        
                left[i] = a[i - 1] * left[i - 1];
            }
            right[len - 1] = 1;//因为len- 1右侧没有元素，所以赋值为1
            for(int i = len - 2; i >= 0; i--)
            {
        
                right[i] = a[i + 1] * right[i + 1];
            }
            for(int i = 0; i < len; i++)
            {
        
                ret.push_back(left[i] * right[i]);
            }
            return ret;
        }
    };

##### [剑指 Offer 57 - II. 和为s的连续正数序列❤️][Offer 57 - II. _s] #####

class Solution {
        
    public:
        vector<vector<int>> findContinuousSequence(int target) {
        
            vector<vector<int>>ret;
            int i = 1;//滑动窗口左边界
            int j = 1;//滑动窗口右边界
            int sum =0;
            while(i <= target / 2) // 超过它的两倍是容纳不了两个数的
            {
        
                if(sum > target)
                {
        
                    sum -= i;
                    i++;
                }
                else if(sum < target)
                {
        
                    sum += j;
                    j++;
                }
                else
                {
        
                    vector<int>res;
                    for(int k = i; k < j; k++)
                    {
        
                        res.push_back(k);
                    }
                    ret.push_back(res);
                    sum -= i;
                    i++;
                }
            }
        return ret;
        }
    };

##### [剑指 Offer 62. 圆圈中最后剩下的数字][Offer 62.] #####

//超时
    // class Solution {
        
    // public:
    //     int lastRemaining(int n, int m) {
        
    //         if(n == 1) return 0;
    //         vector<int>res;
    //         for(int i = 0; i < n; i++)
    //         {
        
    //             res.push_back(i);
    //         }
    //         int cnt = n;
    //         int num = 0;
    //         while(cnt != 1)
    //         {
        
    //             for(int i = 0; i < res.size(); i++)
    //             {
        
    //                 if(res[i] != -1)
    //                 {
        
    //                     num++;
    //                     if(num == m)
    //                     {
        
    //                         num = 0;
    //                         res[i] = -1;
    //                         cnt--;
    //                         if(cnt == 1) break;
    //                     }
    //                 }
    //             }
    //         }
    //         for(int i = 0; i < res.size(); i++)
    //         {
        
    //             if(res[i] != -1)
    //             {
        
    //                 num = i;
    //                 break;
    //             }
    //         }
    //         return num;
    //     }
    // };
    class Solution {
        
    public:
        int lastRemaining(int n, int m) {
        
            /*
            方法2:计算法(参考题解区->想吃火锅的木易)
            假设有一圈数字[0,1,2,3,4,5],m=3
            我们令删除后的元素的后一个元素放在最前面方便计数
            1.删除2->[3,4,5,0,1]
            2.删除5->[0,1,3,4]
            3.删除3->[4,0,1]
            4.删除1->[4,0]
            5.删除4->[0]
            尝试反推:
            如何从最后剩下的元素的索引0反推至第一轮元素索引呢?
            注意到:2->1的过程是将删除的的元素5补在尾巴上变成[0,1,3,4,5],然后再总体向右移动m位
            变成:[3,4,5,0,1];同样地,此时的最终活下来的元素0的索引由0->3
            显然这是(idx+m)%len的结果,idx为删除5后的索引,len为补上删除元素后数组的长度
            */
            // 最后的位置必然为0
            int pos = 0;
            // 这里的i为还原后数组的长度,范围为[2,n]
            for(int i = 2; i <= n; i++) {
        
                // 经过推断可知新的pos=(旧的pos + m) % len
                // 其中pos表示索引,len表示还原后的数组长度,即i
                pos = (pos + m) % i;
            }
            // 数组为[0,1,2,...,n-1],因此数组索引=元素
            return pos;
        }
    };

##### [剑指 Offer 44. 数字序列中某一位的数字❤️][Offer 44.] #####

class Solution {
        
        public:
            int findNthDigit(int n) {
        
               //当n=0不存在。  
                //分段
    
                //第一段（1-9）数字1-10 个，长度 9*1
                //第二端（10-99）数字(100-10)个，长度（100-10）*2 = 90*2
                //第三段（100-999）数字(1000-100)个, 长度（1000-100）*3 =900*3
    
                //n=1，返回1 。n=10 对应第二段的第一个数字10。取第一位为1
    
                int i=1;//分段 第1段开始 
    
                while(n > 9*pow(10,i-1) *i)//找到n在第几段 ，如第二段有90*2 个字符
                {
        
                    n = n - 9*pow(10,i-1) *i;
                    i++;
                }
                //到这里已经知道是第几段i。 且是这一段的第几个字符
    
                int min_num = pow(10,i-1);//这一段的最小值。比如第二段，最小为10
                int cur_num = min_num + (n-1)/i;//知道是属于哪个数字 每个数字长度为i  第0数字是它本身
                int cur_bit = (n-1)%i;//看是这个数字的第几位
    
               string s = to_string(cur_num);
               return   s[cur_bit]-'0';//返回这一位的数字
            }
        };

##### [剑指 Offer 33. 二叉搜索树的后序遍历序列❤️][Offer 33.] #####

class Solution {
        
    public:
        bool PostOrder(vector<int>& postorder, int start, int end)
        {
        
            /* 递归终止条件 */
            if(start >= end) return true;
            int index = start;
            /* 中间处理逻辑 */
            while(postorder[index] < postorder[end]) index++;
             /* 记录分割点 */
            int min_index = index;
            while(postorder[index] > postorder[end]) index++;
             /* 递归左右子树 */
            bool left = PostOrder(postorder,start,min_index - 1);
            bool right = PostOrder(postorder,min_index,end-1);
            return index == end && left && right;
        }
        bool verifyPostorder(vector<int>& postorder) {
        
            return PostOrder(postorder, 0, postorder.size()-1);
        }
    };

[Offer 05.]: https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
[Offer 58 - II.]: https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
[Offer 67.]: https://leetcode.cn/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/
[Offer 06.]: https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
[Offer 24.]: https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/
[Offer 35.]: https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/
[Offer 18.]: https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/
[Offer 22. _k]: https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
[Offer 25.]: https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
[Offer 52.]: https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
[Offer 21.]: https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
[Offer 57. _s]: https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
[Offer 59 - I.]: https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
[Offer 58 - I.]: https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/
[Offer 09.]: https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
[Offer 30. _min]: https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/
[Offer 59 - II.]: https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof/
[Offer 29.]: https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
[Offer 31.]: https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
[Offer 03.]: https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
[Offer 53 - I. _ I]: https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
[Offer 53 - II. 0_n-1]: https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/
[Offer 04.]: https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
[Offer 11.]: https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
[Offer 50.]: https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
[Offer 32 - I.]: https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
[Offer 32 - II. _ II]: https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
[Offer 32 - III. _ III]: https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
[Offer 26.]: https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/
[Offer 27.]: https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/
[Offer 28.]: https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/
[Offer 12.]: https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/
[Offer 13.]: https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
[Offer 34.]: https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
[Offer 54. _k]: https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
[17.]: https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
[Offer 36.]: https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
[Offer 55 - I.]: https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/
[Offer 55 - II.]: https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/
[Offer 64. _1_2_n]: https://leetcode.cn/problems/qiu-12n-lcof/
[Offer 68 - I.]: https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[Offer 68 - II.]: https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[Offer 37.]: https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/
[Offer 38.]: https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/
[Offer 17. _1_n]: https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/
[Offer 51.]: https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
[Offer 07.]: https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/
[Offer 16.]: https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
[Offer 45.]: https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
[Offer 61.]: https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof/
[Offer 40. _k]: https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
[150.]: https://leetcode.cn/problems/evaluate-reverse-polish-notation/
[Offer 10- I.]: https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/
[Offer 10- II.]: https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
[Offer 63.]: https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof/
[Offer 42.]: https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
[Offer 47.]: https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/
[Offer 46.]: https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
[Offer 48.]: https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
[264. _ II]: https://leetcode.cn/problems/ugly-number-ii/
[Offer 15. _1]: https://leetcode.cn/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
[Offer 65.]: https://leetcode.cn/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/
[Offer 56 - I.]: https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
[Offer 56 - II. _ II]: https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
[Offer 39.]: https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
[Offer 66.]: https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/
[Offer 57 - II. _s]: https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
[Offer 62.]: https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
[Offer 44.]: https://leetcode.cn/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/
[Offer 33.]: https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/