leetcode刷题笔记—剑指offer

剑指 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. 左旋转字符串

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. 把字符串转换成整数❤️

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. 从尾到头打印链表

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. 反转链表

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. 复杂链表的复制

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. 删除链表的节点

/* 
 * 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个节点

 /*
 * 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. 合并两个排序的链表

/**
 * 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. 两个链表的第一个公共节点

/**
 * 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. 调整数组顺序使奇数位于偶数前面

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的两个数字

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. 滑动窗口的最大值

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. 翻转单词顺序

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. 用两个栈实现队列

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函数的栈❤️

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. 队列的最大值❤️

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. 顺时针打印矩阵❤️

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. 栈的压入、弹出序列

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. 数组中重复的数字

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

//遍历法
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中缺失的数字

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. 二维数组中的查找

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. 旋转数组的最小数字❤️

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. 第一个只出现一次的字符

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. 从上到下打印二叉树

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

//自己写的
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

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. 树的子结构❤️

//我写的
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. 二叉树的镜像

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. 对称的二叉树

//我写的
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. 矩阵中的路径❤️

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. 机器人的运动范围❤️

//我写的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. 二叉树中和为某一值的路径❤️

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大节点❤️

//利用优先队列做法
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. 电话号码的字母组合

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. 二叉搜索树与双向链表

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. 二叉树的深度

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;
    }
};

剑指 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

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

剑指 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. 二叉树的最近公共祖先

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. 序列化二叉树❤️

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. 字符串的排列❤️

//我写的
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位数

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. 数组中的逆序对

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. 重建二叉树

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. 数值的整数次方

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. 把数组排成最小的数❤️

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. 扑克牌中的顺子

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个数

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. 逆波兰表达式求值

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. 斐波那契数列

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. 青蛙跳台阶问题

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. 股票的最大利润❤️

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. 连续子数组的最大和

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. 礼物的最大价值❤️

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. 把数字翻译成字符串

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

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. 最长不含重复字符的子字符串❤️

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

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的个数

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

剑指 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. 数组中数字出现的次数

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

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. 数组中出现次数超过一半的数字

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. 构建乘积数组

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的连续正数序列❤️

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. 圆圈中最后剩下的数字

//超时
// 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. 数字序列中某一位的数字❤️

    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. 二叉搜索树的后序遍历序列❤️

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);
    }
};