• 剑指offer刷题笔记整理


    剑指offer刷题笔记

    过去几天复习了一遍剑指offer,整理一下笔记方便以后复习,题目来源leetcode,题解来源acwing

    day1

    02 回文链表

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution {
    public:
        ListNode* SearchHalfNode(ListNode* head)
        {
            auto fast = head;
            auto slow = head;
            while (fast)
            {
                fast = fast -> next;
                slow = slow -> next;
                if (fast) fast = fast->next;
            }
            return slow;
        }
    
        ListNode* reverseList(ListNode* node)
        {
            ListNode* pre = nullptr;
            while (node)
            {
                auto next_ = node->next;
                node -> next = pre;
                pre = node;
                node = next_;
            }
            return pre;
        }
        bool isPalindrome(ListNode* head) {
            auto mid = SearchHalfNode(head);
            auto end = reverseList(mid);
            while (end)
            {
                if (head->val != end->val) 
                    return false;
                head = head->next;
                end = end-> next;
            }
            return true;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    03 I 数组中重复的是数字

    class Solution {
    public:
        int findRepeatNumber(vector<int>& nums) {
            int n  = nums.size();
            for (auto x: nums)
                if (x < 0 || x >= n ) 
                    return -1;
            for (int i = 0; i < n; i ++)
            {
                while (i != nums[i] && nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);//交换i nums[i] nums[nums[i]]
                if (i != nums[i] && nums[nums[i]] == nums[i]) return nums[i];//交换位置已经有值,那么返回nums[i]
            }
            return -1; 
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    03II 不修改数组找出重复的数字

    #include 
    #include 
    
    using namespace std;
    const int N = 1010;
    vector<int> nums;
    
    class Solution
    {
    public:
        int duplicateInArray(vector<int> &nums)
        {
            int l = 1, r = nums.size() - 1; //最大值、最小值
            while (l < r)
            {
                //无序数组二分
                int mid = l + r >> 1; //按中位数切分成两半
                // [l,mid] [mid+1,r]
                int s = 0;
                for (auto x : nums)
                    s += x >= l && x <= mid; //按区间计数
                if (s > mid - l + 1)         //如果左边区间的点大于区间中的点位
                    r = mid;                 //去左边查找
                else
                    l = mid + 1; //否则去右边查找
            }
            return r;
        }
    
        void display()
        {
            cout << "this is my function!" << endl;
        }
    };
    
    int main()
    {
        int n;
        cin >> n;
        for (int i = 0; i <= n; i++)
        {
            int x;
            cin >> x;
            nums.push_back(x);
        }
        Solution solution;
        int res;
        // solution.display();
        res = solution.duplicateInArray(nums);
        cout << res << endl;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    04 二维有序数组的查找

    class Solution {
    public:
        bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
            /*
            从左下角开始查找,上边的数一定小,右边的数一定大
            每次都会省略一行
            */
            int m, n;
            if (matrix.empty() || matrix[0].empty()) return false;
            m = matrix.size();
            n = matrix[0].size();
            int i = m - 1, j = 0;
            while (i >= 0 && j < n)
            {
                if (matrix[i][j] > target) i --;
                else if (matrix[i][j] < target) j ++;
                else return true;
            }
            return false;        
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    05 替换空格

    class Solution {
    public:
        string replaceSpace(string s) {
            string res;
            for (auto x: s)
            {
                if (x == ' ') res += "%20";
                else res += x;
            }
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    06 从尾到头打印链表

    struct ListNode {
         int val;
         ListNode *next;
         ListNode(int x) : val(x), next(NULL) {} //构造函数初始化,可以传入参数x
      };
    class Solution {
    public:
        vector<int> reversePrint(ListNode* head) {
            vector<int> res;
            while (head)
            {
                res.push_back(head -> val);
                head = head -> next;
            }
            return vector<int>(res.rbegin(), res.rend());//rbegin与begin正好相反
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    07 根据前序和中序重新构建二叉树

    struct TreeNode {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     };
    
    class Solution {
    public:
        map <int, int> hash;
        vector<int> preorder, inorder;
        TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
            /*
            根左右找到根节点的值
            左根右找到根节点的位置,然后递归左子树和右子树
            */
            preorder = _preorder, inorder = _inorder;
            for (int i = 0; i < inorder.size(); i++) hash[inorder[i]] = i;//使用hash存储每个节点在中序遍历中的位置
            return dfs(0, preorder.size() - 1, 0, inorder.size() - 1);
        }
        TreeNode* dfs(int pl, int pr, int il, int ir)
        {
            if (pl > pr) return nullptr;
            auto root = new TreeNode(preorder[pl]);
            int k = hash[root -> val];
            auto left = dfs(pl + 1, pl  + k - il, il, k - 1);//左子树k-il个元素
            auto right = dfs(pl + k - il + 1, pr, k + 1, ir);
            root -> left = left;
            root -> right = right;
            return root;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    08 二叉树中序遍历的下一个节点

    #include 
    
    struct TreeLinkNode
    {
        int val;
        struct TreeLinkNode *left;
        struct TreeLinkNode *right;
        struct TreeLinkNode *next; // father指针
        TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL){}
    };
    
    class Solution
    {
    public:
        TreeLinkNode *GetNext(TreeLinkNode *pNode)
        {
            //当前节点在中序遍历中的下一个节点:后继
            //二叉搜索树中比当前节点大的最小节点
            // next是父节点
            if (pNode->right)
            {
                pNode = pNode->right;
                while (pNode->left)
                    pNode = pNode->left;//如果有右子树,那么下一个节点一定是右子树的最左节点
                return pNode;
            }
            // 如果没有右子树,中序遍历会向上看,如果是父节点的左节点那么直接返回父节点
            // 如果是父节点的右节点,那么沿着父节点继向上,直到某个节点是父节点的左节点,返回父节点
            // 两种情况可以统一为
            while (pNode->next && pNode == pNode->next->right)
                pNode = pNode->next;
            return pNode->next;
        }
    };
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    09 两个栈实现队列

    class CQueue {
    public:
        stack<int> stk, cache;
        CQueue() {}
        void appendTail(int value) {
            stk.push(value);
        }
        void copy(stack<int> &a, stack<int> &b)
        {
            while (a.size())
            {
                b.push(a.top());
                a.pop();
            }
        }
        int deleteHead() {
            if (stk.size())
            {
                copy(stk, cache);//保存到缓存中
                int res = cache.top();//删除队头
                cache.pop();
                copy(cache, stk);//拷贝回去
                return res;
            }
            return -1;
            
        }
    };
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    10 斐波那契数列、青蛙跳台阶

    class Solution {
    public:
        int fib(int n) {
            int  a = 0, b = 1;
            for (int i = 1; i <= n; i ++)
            {
                int r = (a + b) % 1000000007;// (a + b) % c = (a % c + b % c) % c 所以可以提前取余,避免整形溢出
                a = b;
                b = r;
            }
            return a;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    11 旋转数组中的最小数字

    class Solution {
    public:
        int minArray(vector<int>& numbers) {
            // 有序数组 搬移后仍然是有序数组
            // 左数组最左边 可能 等于右数组最右边 去掉右数组的右半边
            // 右边数组完全小于左边,可以找到右数组的最左元素
            // 使用二分
            int n = numbers.size() - 1;
            if (n < 0) return -1;
            while (n > 0 && numbers[0] == numbers[n]) n --;
            if (numbers[0] <= numbers[n]) return numbers[0]; //只剩左数组
            //二分搜索 小于numbers[0]的最左数
            int l = 0, r = n;
            while (l < r)
            {
                int mid = l + (r - l) /  2;//[l,mid] [mid+1,r]
                if (numbers[mid] < numbers[0]) r = mid;//mid落在了右半
                else l = mid + 1;//mid落在左半
            }
            return numbers[r];
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    12 矩阵中的路径

    class Solution {
    public:
        bool exist(vector<vector<char>>& board, string word) {
            //dfs 从首字母开始查找,如果找到立即返回
            if (board.empty()) return false;
            for (int i = 0; i < board.size(); i ++)
                for(int j = 0; j < board[i].size(); j++)
                {
                    if (dfs(board, word, 0, i, j)) return true;
                }
            return false;
    
        }
    
        bool dfs(vector<vector <char>> &board, string word, int u, int x, int y)
        {
            if (board[x][y] != word[u]) return false;
            // 如果二维矩阵元素等于当前元素
            if (u == word.size() - 1) return true;
            // 如果当前元素相等且不是末尾元素,向下查找
            char t = board[x][y];
            board[x][y] = '*';
            int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};
            for (int i = 0; i < 4; i++)
            {
                int a = x + dx[i];
                int b = y + dy[i];
                //如果在范围内,寻找下一层
                if (a >=0 && a < board.size() && b >= 0 && b < board[a].size())
                    if (dfs(board, word, u + 1, a, b)) return true;
            }
            board[x][y] = t;//回溯
            return false;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    day2

    13 机器人的运动范围

    class Solution {
    public:
        int get_single_sum(int x)
        {
            int s = 0;
            while (x)
            {
                s += x % 10;
                x /= 10;
            }
            return s;
        }
    
        int get_sum(pair<int, int> p) //坐标位数之和不能大于k
        {
            return get_single_sum(p.first) + get_single_sum(p.second);
        }
        int movingCount(int m, int n, int k) {
            int res = 0;
            if (!m || !n) return 0;
    
            vector<vector<bool>> st(m, vector<bool>(n));
            queue<pair<int, int>> q;
            
            q.push({0, 0});//pair列表初始化
            int dx[2] = {1, 0}, dy[2] = {0, 1};//只需要向下和向右查找即可
            while (!q.empty())
            {
                auto t = q.front();
                q.pop();
                if (get_sum(t) > k||st[t.first][t.second]) continue;
                //如果满足条件
                res ++;
                st[t.first][t.second] = true;
                // 广度优先搜索
                for (int i = 0; i < 2; i++)
                {
                    int a = t.first + dx[i];
                    int b = t.second + dy[i];
                    if (a >= 0 && a < m &&b >= 0 && b < n)
                        q.push({a, b});
                }
            }
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    14 剪绳子

    /*
    整数拆分,使其因子乘积最大
    
    结论:
      ni%3 余1 拆出一个2*2=4,剩下被3拆分
      ni%3 余2 拆出一个2,剩下被3拆分
    分析过程:
        假设N > 0, 正整数N拆分成m个数,N = n1 + n2 + n3 + n4 + n..+nm
        1 最优解肯定没有1, 1*(x-1)< x
        2 最优解可以没有4, 2*2=4 可拆  最优解2 3 >4
        3 ni>5, ni必须拆成3*(ni-3),最优解不能包含大于等于5的数,最优解只包含 2和3
                         3 * (ni - 3) >= ni
                         3 * ni - 9 >= ni
                         2 * ni >= 9 成立,拆了更好  
        4 最优解若有3个2: 2 * 2 *2 < 3 * 3 最优解最多两个2 
    */
    
    
    class Solution {
    public:
        int cuttingRope(int n) {
            int res = 1;
            if (n <= 3) return n -1;
            if (n % 3 == 1) res *= 4, n -= 4;
            if (n % 3 == 2) res *= 2, n -= 2;
            while (n)
            {
                res *= 3;
                n -= 3;
            }
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    15 二进制中1的个数

    /*两种解法:
     1 lowbit 最后一位1的二进制表示的十进制数
       在原来的基础上减去即可消去最右边的1,每消一次计数+1
       1010 原码
       0110 补码
    2 直接转换为正数的原码
       在原来的基础上每次右移1位,每次计数 + x&1
     */
    //lowbit算法
    class Solution {
    public:
        int hammingWeight(uint32_t n) {
            int s = 0;
            while (n)
            {
                int x = n & -n;
                n -= x;
                s ++;
            }
            return s;     
        }
    };
    //直接转化为正数
    class Solution {
    public:
        int hammingWeight(uint32_t n) {
            unsigned int n_ = n;
            int s = 0;
            while (n)
            {
                s += n & 1;
                n >>= 1;
            }
            return s;
        }
    };       
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    16 数值的整数次幂

    /*
    快速幂:指数的二进制拆分
    x^N = x2*x2^2*x2^3*x2^4...
    N = 2^2+2^3+2^4...表示为二进制数即可。
    N & 1
    0 res*=x
    1 res*=x*2
    2 res*=x*4
    3 res*=x*8
    ...
    */
    
    class Solution {
    public:
        double myPow(double x, int n) {
            //注意负指数
    
            double res = 1;
            long long  N = abs(n);
            while (N)
            {
                if (N & 1) res *= x;//二进制位=1,那么累加结果
                x *= x; 
                N >>= 1;//指数的二进制拆分
            }      
            if (n < 0) res = 1 / res;
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    17 打印1到最大的n位数

    class Solution {
    public:
        vector<int> printNumbers(int n) {
            //输出所有的n位数
            int m = (pow(10, n)) - 1;
            vector<int> nums(m, 1);
            for (int i = 1; i < m; i ++)
                nums[i] = nums[i-1] + 1;
            return nums;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    18 删除链表的节点

    class Solution {
    public:
        ListNode* deleteNode(ListNode* head, int val) {
            //如果是头节点
            if (head -> val == val) return head -> next;
            //不是头节点
            ListNode* cur = head;
            while(cur-> next -> val != val)
                cur = cur -> next;
            cur -> next = cur -> next -> next;
            return head;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    LC 83 删除有序链表中的重复节点

    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            // dummy 哨兵机制 头结点可能被删掉
            auto dummy = new ListNode(-1);
            dummy -> next = head;
            // 链表双指针 dummy 1 1 1 2 2 3 3 4 4 分段看
            auto p = dummy;
            while (p -> next)
            {
                auto cur = p -> next;
                while (cur -> next && cur -> val == cur -> next -> val) 
                    cur = cur -> next;
                // 如果没有重复,p移动到cur,
                if (p -> next  == cur) p = cur;
                // 如果有重复,将p的next指针指向cur
                else p -> next = cur;//cur在下一个区间
            }
            return dummy -> next;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    19 正则表达式匹配

    class Solution {
    public:
        int n, m;
        vector<vector<int>> f;
        string s, p;
        bool isMatch(string s_, string p_) {
            s = s_, p = p_;
            n = s.size(), m = p.size();
            f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
            return dp(0, 0);
        }
    
        bool dp(int x, int  y)
        {
            if (f[x][y] != -1) 
                return f[x][y];
            if (y == m) 
                return f[x][y] = x == n; // 初始化
            bool first_match = x < n && (p[y] == '.' || s[x] == p[y]);
            if (y + 1 < m && p[y + 1] == '*')
                //匹配0次跳过两个匹配字符
                //匹配一次以上: 当前字符匹配且f[x+1][y]后面字符也是匹配的
                f[x][y] = dp(x, y + 2) || (first_match && dp(x + 1, y));
            else
            {
                f[x][y] =  first_match && dp(x + 1, y + 1);
            }
            return f[x][y];
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    20 PASS

    21. 调整数组顺序使奇数位于偶数前面

    class Solution {
    public:
        vector<int> exchange(vector<int>& nums) {
            /*双指针
             第一个指针前面全是奇数
             第二个指针后面全是偶数*/
             int l = 0, r = nums.size() - 1;
             while (l <= r)
             {
                 while (l <= r && nums[l] % 2 == 1) l ++;
                 while (l <= r && nums[r] % 2 == 0) r --;
                 if (l < r) swap(nums[l], nums[r]);
             }
             return nums;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

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

    class Solution {
    public:
        ListNode* getKthFromEnd(ListNode* head, int k) {
            auto slow = head;
            int idx = 0;
            while (head)
            {
                if (idx >= k)
                    slow = slow -> next;
                head = head->next;
                idx ++;
            }
            return slow;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    23 链表中环的入口

    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            // 链表中环的检测
            auto fast = head;
            auto slow = head;
            bool find = false;
            while (slow && fast)
            {
                //fast走两步
                fast = fast -> next;
                if (fast) fast = fast -> next;
                //fast空时,无环
                if (!fast) return nullptr;
                //slow走一步
                slow = slow -> next;
                //如果相遇,那么停止
                if (fast == slow) 
                {
                    find = true;  
                    break;
                }
            }
            //没有环
            if (!find) return nullptr;
            //从头开始走,直到相遇
            slow = head;
            while (slow && fast && slow != fast)
            {
                fast = fast -> next;
                slow = slow -> next;
            }
            return slow;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    day3

    24 反转链表

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    
    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            //记录一个前驱节点
            ListNode * pre = nullptr;
            auto cur = head;
            while (cur)
            {
                auto next = cur -> next;
                cur -> next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    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) {
            //归并排序的并操作
            auto dummy = new ListNode(-1);
            auto cur = dummy;
            while (l1 && l2)
            {
                if (l1 -> val <= l2 -> val) 
                {
                    cur -> next = l1;
                    l1 = l1 ->next;
                }
                else 
                {
                    cur -> next = l2;
                    l2 = l2 -> next;
                }
                cur = cur ->next;
            }
            if (l1) cur -> next = l1;
            else cur ->next = l2;
            return dummy -> next;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    26 树的子结构

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        bool isSubStructure(TreeNode* A, TreeNode* B) {
            // B恰好能覆盖A的部分节点 类似字符串匹配 
            // 从树根开始看,如果不是,后移一位 暴力匹配 空树不是任意子结构 
            if (!A || !B) return false;//某棵树为空 返回fasle
            if (isPart(A, B)) return true;// 如果A\B匹配返回true
            return isSubStructure(A->left, B) || isSubStructure(A->right,B);//如果不匹配 看左右子树是否匹配
        }
    
        bool isPart(TreeNode* p1, TreeNode* p2)
        {
            if (!p2) return true;//如果p2没有点了,匹配成功
            if (!p1 || p1 -> val !=  p2 -> val) return false;//p1没有电,匹配失败
            //如果p1 p2有点且值相等,那么当前节点匹配,看左右节点是否匹配
            return isPart(p1 -> left, p2 -> left) && isPart(p1 -> right, p2 -> right);
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    27 二叉树镜像

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode * mirrorTree(TreeNode* root) {
            if (!root) return root;
            swap(root->left, root->right);
            mirrorTree(root->left);
            mirrorTree(root->right);
            return root;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    28 对称的二叉树

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            // 除了根节点  
            // 左节点的左儿子和右节点的右儿子 相等
            // 左节点的右儿子和右节点的左儿子 相等
            if (!root) return true;
            // 看左右子树是否对称
            return dfs(root -> left,  root->right);
        }
        bool dfs(TreeNode* p1, TreeNode* p2)
        {
            if (!p1 || !p2) return !p1 && !p2;
            //只有两个同时为空才返回true;
            if (p1 -> val != p2 -> val) return false;
            //如果两个节点相等,则递归判断两个节点的左右儿子
            return dfs(p1 -> left, p2 -> right) && dfs(p1 -> right, p2 -> left);
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    29 顺时针打印矩阵

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            vector <int> res;
            if (matrix.empty()) return res;
            int m = matrix.size();
            int n = matrix[0].size();
            vector<vector<bool>> st(m, vector<bool>(n, false));
            int dx[4] = {0,1,0,-1},  dy[4] = {1, 0, -1, 0};
            int x = 0, y = 0, d = 0;
            for (int i = 0; i < m * n; i ++)
            {
                res.push_back(matrix[x][y]);
                st[x][y] = true;
                int a = x + dx[d], b = y + dy[d];
                if (a < 0 || a >= m || b < 0 || b >= n || st[a][b])
                {
                    //如果走出了矩阵范围,那么回退到x,y 然后调整方向
                    d = (d + 1) % 4;
                    a = x + dx[d], b = y + dy[d];
                }
                x = a, y = b;//新的坐标
            }
            return res;
     
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    30 包含min函数的栈

    class MinStack {
    public:
        stack<int> stk, min_stk;
        /** initialize your data structure here. */
        MinStack() {
        }
        //单调栈
        
        void push(int x) {
            stk.push(x);
            if (min_stk.empty() || x <= min_stk.top()) min_stk.push(x);
    
        }
        
        void pop() {
            if (stk.top() == min_stk.top()) min_stk.pop();
            stk.pop();
        }
        
        int top() {
            return stk.top();
        }
        
        int min() {
            return min_stk.top();
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    31 栈的输入和弹出序列

    class Solution {
    public:
        bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
            int m = pushed.size();
            int n = popped.size();
            stack<int> stk;
            for (int i = 0, j = 0; i < m; i ++)
            {
                stk.push(pushed[i]);
                while (j < n && stk.size() && stk.top() == popped[j]) 
                    stk.pop(), j++;
            }
            if (stk.size()) return false;
            return true;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    32 从上到下打印二叉树(不分行)

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<int> levelOrder(TreeNode* root) {
            vector<int> res;
            if (!root) return res;
            queue<TreeNode*> q;
            q.push(root);
            while (q.size())
            {
                auto t = q.front();
                q.pop();
                res.push_back(t -> val);
                if (t -> left) q.push(t -> left);
                if (t -> right) q.push(t -> right);
            }
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    32 从上到下打印二叉树(分行)

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>> res;
            // 第一行加入null标记
            // 遍历到第一行的null时,第二行自然也是null此时代表第二行结束...依次类推
            queue<TreeNode*> q;
            if (!root) return res;
            q.push(root);
            q.push(nullptr);
            vector<int> level;
            while (q.size())
            {
                auto t = q.front();
                q.pop();
                if (!t)
                {
                    // 如果到达末尾
                    if (level.empty()) return res;
                    // 如果到达行尾
                    res.push_back(level);
                    level.clear();
                    q.push(nullptr);
                    continue;
                }
                level.push_back(t -> val);
                if (t -> left) q.push(t -> left);
                if (t -> right) q.push(t -> right);
            }
            return res;
    
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    32 从上到下打印二叉树(之字形:左右左)

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>> res;
            if (!root) return res;
            vector<int> level;
            queue<TreeNode*> q;
            q.push(root);
            q.push(nullptr);
            bool zigzag = false;
            while(q.size())
            {
                auto t = q.front();
                q.pop();
                if(!t)
                {
                    if (level.empty()) return res;
                    if (zigzag) reverse(level.begin(), level.end());
                    res.push_back(level);
                    level.clear();
                    q.push(nullptr);
                    zigzag = !zigzag;
                    continue;
                }
                level.push_back(t -> val);
                if (t -> left) q.push(t -> left);
                if (t -> right) q.push(t -> right);
            }
            return res;
    
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    day4

    33. 二叉搜索树的后序遍历序列

    // 中序+后序 nlogn
    class Solution {
    public:
        vector<int> inorder, postorder;
        map<int, int> hash;
        bool verifyPostorder(vector<int>& postorder_) {
            postorder = postorder_;
            sort(postorder_.begin(), postorder_.end()); 
            inorder = postorder_;
            for (int i = 0; i < postorder.size(); i ++) hash[inorder[i]] = i;
            return dfs(0, postorder.size() - 1, 0, inorder.size() - 1);
        }
        int dfs(int pl, int pr, int il, int ir)
        {
            if (pl > pr) return true;
            auto root = postorder[pr];
            int k = hash[root];
            if (k < il || k > ir) return false; //当前的根节点不在中序遍历的范围内
            bool left = dfs(pl, pl + k- il - 1 , il,  k - 1);//长度为k-il
            bool right = dfs(pl + k-il, pr - 1, k+ 1, ir);
            return left && right;
        }
    };
    //只用后序遍历 n*n
    class Solution {
    public:
        vector<int> postorder;
        bool verifyPostorder(vector<int>& postorder_) {
            postorder = postorder_;
            return dfs(0, postorder.size() - 1);
        }
    
        bool dfs(int l, int r)
        {
            if (l >= r) return true;
            int root = postorder[r];
            int k = l;
            //左子树的元素都小于根节点
            while (k < r && postorder[k] < root) 
                k++;//右子树的第一个元素
            for (int i = k; i < r; i ++)
                // 右子树的元素都大于根节点
                if (postorder[i] < root) 
                    return false;
            return dfs(l, k - 1) && dfs(k, r - 1);
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    34. 二叉树中和为某一值的路径

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        vector<int> path;
        vector<vector<int>> ans;
        vector<vector<int>> pathSum(TreeNode* root, int target) {
            dfs(root, target);
            return ans;
        }
    
        void dfs(TreeNode* root, int target)
        {
            if (!root) return;
            // 单层递归逻辑
            /*
            1 先放入当前节点
            2 检查是否为叶节点
                如果是
                    满足和条件,直接加入答案
                    不满足条件,回溯 if(!root) return 
                如果不是,递归 if(!root) return 
            */
            path.push_back(root->val);
            target -= root->val;
            if (!root-> left && !root->right && !target)
                ans.push_back(path);
            dfs(root-> left, target);
            dfs(root-> right, target);
            path.pop_back();
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    35 复杂链表的复制

    /*
    // Definition for a Node.
    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) {
            if (!head) return nullptr;
            //复制链表
            Node* cur = head;
            while (cur)
            {
                Node* post = new Node(cur->val);
                post-> next = cur -> next;
                cur -> next = post;
                cur = post -> next;
            }
            // 复制随机指针
            cur = head;
            while (cur)
            {
                if (cur -> random)
                    cur -> next -> random = cur -> random -> next;
                cur = cur -> next -> next;
            }
            // 分离节点
            auto dummy = new Node(-1);
            cur = dummy;
            Node* raw = head;
            while (raw)
            {         
                cur -> next = raw -> next;
                raw -> next = cur -> next-> next;
                cur = cur -> next;
                raw = raw -> next;   
            }
            return dummy-> next;
            
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    36 二叉搜索树与双线链表

    /*
    // Definition for a Node.
    class Node {
    public:
        int val;
        Node* left;
        Node* right;
    
        Node() {}
    
        Node(int _val) {
            val = _val;
            left = NULL;
            right = NULL;
        }
    
        Node(int _val, Node* _left, Node* _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    };
    */
    class Solution {
    public:
        Node* treeToDoublyList(Node* root) {
            if (!root) return root;
            auto slides = dfs(root);
            slides.first -> left = slides.second;
            slides.second -> right = slides.first;
            return slides.first;
        }
        pair<Node*, Node*> dfs(Node* root)
        {
            if (!root->left && !root-> right) return {root, root};
            else if (root->left && root->right)
            {
                //pari存储双向链表的头尾节点,经过dfs后所有子树都链接成了双向链表
                // 将头尾指针连接即可得到双向循环链表
                auto lslide = dfs(root->left), rslide = dfs(root->right);
                lslide.second -> right = root, root-> left = lslide.second;
                root-> right = rslide.first,   rslide.first -> left = root;
                return {lslide.first, rslide.second};
            }
            else if (root->left)
            {
                auto lslide = dfs(root->left);
                lslide.second -> right = root, root-> left = lslide.second;
                return {lslide.first, root};
            }
            else
            {
                auto  rslide = dfs(root->right);
                root-> right = rslide.first, rslide.first -> left = root;
                return {root, rslide.second};
            }
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    37 二叉树的序列化和反序列化

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Codec{
    public:
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            string res;
            dfs_s(root, res);
            return res;        
        }
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            int u = 0;
            return dfs_d(data, u);
        }
    
        void dfs_s(TreeNode* root, string& res)
        {
            if (!root)
            {
                res += "null ";
                return;
            }
            res += to_string(root->val) + " ";
            dfs_s(root->left, res);
            dfs_s(root->right,res);
        }
    
    
        TreeNode* dfs_d(string data, int& u)
        {
            
            if (u == data.size()) return nullptr;
            int k = u;
            //当前节点的末尾后一位
            while (data[k] != ' ') k ++;
            //节点是null是null的话,空格的下一位 下一节点
            if (data[u] == 'n')
            {
                u = k + 1;
                return nullptr;
            }
            //如果是数字
            int val = 0;
            //负数
            if (data[u] == '-')
            {
                for (int i = u + 1; i < k; i++) 
                    val = val * 10 + (data[i]- '0');
                val = -val;
            }
            //正数
            else
            {   
                for (int i = u; i < k; i++) 
                    val = val * 10 + (data[i]- '0');
            }
            u = k + 1;
            auto root = new TreeNode(val);
            root-> left = dfs_d(data, u);//遍历到空节点,返回的是null
            root-> right = dfs_d(data, u);//遍历到空节点,返回的是null
            return root;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71

    38 字符串序列

    class Solution {
    public:
        vector<string> res;
        string path;
        vector<string> permutation(string s) {
            res.clear();
            path.clear();
            sort(s.begin(), s.end());
            vector<bool> used(s.size(), false);
            dfs(s, used);
            return res;
        }
    
        void dfs(string s, vector<bool>& used)
        {
            if (path.size() == s.size())
            {   
                res.push_back(path);
                return; 
            }
            for (int i = 0; i < s.size(); i ++)
            {    
                if (i > 0 && s[i] == s[i-1] && !used[i-1])
                    continue;
                if (!used[i])
                {
                    path += s[i];
                    used[i] = true;
                    dfs(s, used);
                    used[i] = false;
                    path.pop_back();
                }
            }
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

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

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int val, cnt;
            val = -1, cnt = 0;
            /*
            使用其他数字去抵消超过一半的数字,剩下的就是结果
            如果数字等于val,cnt++;
            如果数字不等于val,cnt--
            如果cnt=0,更新数字  val=nums[i], cnt = 1
            */
            for (int i = 0; i < nums.size(); i ++)
            {
                if (!cnt) val = nums[i], cnt =  1;
                else if (nums[i] == val) cnt ++;
                else cnt --;
            }
            return val;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    day5

    40 最小的k个数

    class Solution {
    public:
        vector<int> getLeastNumbers(vector<int>& arr, int k) {
            /*
            维护一个大根堆:因为大根堆元素比堆顶元素小
            */
            vector<int> res;
            priority_queue<int> heap;
            for (auto x : arr)
            {
                heap.push(x);
                if (heap.size() > k) heap.pop();
            }
            for (int i = 0; i < k; i ++)
            {
                res.push_back(heap.top());
                heap.pop();
            }
            reverse(res.begin(), res.end());
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    41 数据流中位数

    class MedianFinder {
    public:
        /** initialize your data structure here. */
        priority_queue<int> max_heap;
        priority_queue<int, vector<int>, greater<int>> min_heap;
        MedianFinder() { }
        
        void addNum(int num) {
            max_heap.push(num);
            if (min_heap.size() && max_heap.top() > min_heap.top())
            {
                auto maxv = max_heap.top(), minv = min_heap.top();
                max_heap.pop(), min_heap.pop();
                max_heap.push(minv), min_heap.push(maxv);
            }
            if (max_heap.size() - min_heap.size() > 1)
            {
                min_heap.push(max_heap.top());
                max_heap.pop();
            }
    
        }
        
        double findMedian() {
            if (max_heap.size() + min_heap.size() & 1) return max_heap.top();
            else return (max_heap.top() + min_heap.top()) / 2.0;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    42 连续子数组最大和

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int summ = 0;
            int res = INT_MIN;
            for (int i = 0; i < nums.size(); i ++)
            {
                //如果小于0从新开始计算数组和
                //以当前为结尾的前缀和
                summ = max(summ + nums[i], nums[i]);
                res = max(res, summ);
            }
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    43 1~n中1出现的次数

    class Solution {
    public:
        int countDigitOne(int n) {
            /*
            cur:当前位置
            left:cur左边
            right:cur右边  
            t: 10^右边的位数
            左边取0~left-1(cur肯定会有1) 右边可以取全部  left*t次
            左边取left的话,cur可能没有1
            当前cur是0时,res+= 0
            当前cur是1时,res+=right
            当前cur>1时,res+=t
            */
            if (!n) return 0;
            vector<int> nums;
            int res = 0;
            while(n) nums.push_back(n % 10), n /= 10;
            for (int i = nums.size() - 1; i >=0; i --)
            {
                int left = 0, right = 0, t = 1;
                for(int j = nums.size() - 1; j > i; j --) left = left * 10 + nums[j];
                for (int j = i - 1; j >=0; j --) right = right * 10 + nums[j], t *= 10;
                res += left * t;
                if (nums[i] == 1) res += right + 1;
                else if (nums[i] > 1) res += t;
                else res += 0;
            }
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    44 数字序列中某一位的数字

    class Solution {
    public:
        int findNthDigit(int n) {
            //确定是几位数 n-10-90*2-900*3-9000*4-..直到小于i*s 位数*9
            //确定该位数的第几个数  1000+235-1 =1234
            //属于该数的第几位  1234 % 
            long long i = 1, s = 9, base = 1;
            // 1 计算几位数i,剩下多少位n
            while (n > i * s)
            {
               n -= i * s;
               i ++;//位数+1
               s*= 10;//数量级扩大十倍
               base *=10; //基数扩大十倍
            }
            // 2 根据n,计算i位数的第多少个数字,下取整代替上取整
            //   计算n,属于i位数的第几位
            int number = base + (n + i - 1) /  i - 1;                 
            int r = n % i ? n % i : i;
            // 3 根据i,number,r 可以定位到真实的数字
            //  如果整除,那么就是最后一位,如果不整除,去掉r位后面的
            for (int j = 0; j < i - r; j ++) number /= 10;
            return number % 10;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    45 把数组排成最小的数

    class Solution {
    public:
    /* 定义新的比较方式
       a < b  <=> ab < ba
       如果排好序的序列是  
       a1 a2 a3 a4.. an
       证明  假设最小序列是
       a1a2a4a3 ..an,且a4 > a3 即a4a3 > a3a4
       交换a3a4的位置显然可以得到更小的一个数
       a1a2|a3a4...an
    */
        static bool cmp(int a, int b)
        {
            auto as = to_string(a), bs = to_string(b);
            return as + bs < bs + as;
        }
        string minNumber(vector<int>& nums) {
            sort(nums.begin(), nums.end(), cmp);
            string res;
            for (auto x: nums) res += to_string(x);
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    46 数字翻译成字符串

    class Solution {
    public:
        int translateNum(int num) {
            /*
            1 状态表示 dp[i] 前i位数字有多少中不同表示
            2 状态计算 
                第i位数翻译成一位: dp[i-1] 
                i-1,i翻译成一位:   dp[i-2] 
                    必须在10~25
                dp[i] = dp[i-1] + dp[i-2]
            3 边界
                dp[0] = 1
            */
            auto s = to_string(num);
            int n = s.size();
            vector<int> dp(n + 1);
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; i ++)
            {
                dp[i] = dp[i - 1];
                int t = (s[i - 2] - '0') * 10 + (s[i-1] - '0');
                if (t >=10 && t <= 25) dp[i] += dp[i - 2];
            }
            return dp[n];
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    47 礼物的最大价值

    class Solution {
    public:
        int maxValue(vector<vector<int>>& grid) {
            /*
            1状态表示dp[i,j]走到当前各自能够获得的最大价值是多少      
            2 状态转移
               从上方dp[i-1,j] 或者从左边dp[i,j-1]的最大值
               dp[i,j] = max(dp[i-1,j],dp[i, j -1]) + grid[i][j]
            3 状态初始化   
               dp[i,0] = f[0,j] = 0; 
            */
            int m = grid.size(), n = grid[0].size();
            vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
            for (int i = 1; i <= m; i ++)
                for (int j = 1; j <= n; j ++)
                    dp[i][j] = max(dp[i-1][j], dp[i][j - 1])  + grid[i - 1][j - 1];
            return dp[m][n];
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    48 最长不含重复子串

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            /*暴力做法
            先确定结尾,然后枚举前缀最长不重复子串
              双指针做法:借助哈希表
            如果i,j之间有重复,那么把i往后移动一位
            最后取最大值
            */
            unordered_map<char, int> cnt;
            int res = 0;
            for (int i = 0, j = 0; j < s.size(); j ++)
            {
                cnt[s[j]]++;
                if (cnt[s[j]] > 1)
                {
                    while (cnt[s[i]] == 1)
                    {
                        cnt[s[i]] --;
                        i++;
                    }
                    cnt[s[i]] --;
                    i++;
                }
                res = max(res, j- i + 1);  
            }
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    49 丑数

    class Solution {
    public:
        int nthUglyNumber(int n) {
            /*三路归并
            假设丑数序列为a1 a2 a3 a4 a5...
            设置三个序列
            nums1 = a1*2 a2*2 a3*2..
            nums2 = a1*3 a2*3 a3*3..
            nums3 = a1*5 a2*5 a3*5..
            那么这三个序列一定是丑数序列,如何避免遗漏呢?
            归并排序的思想
            t = min(2*dp[i],3*dp[j],5*dp[k])
            */
            if (n <= 1) return n;
            vector<int> dp(1, 1);
            int i = 0, j = 0, k = 0;
            long long  t = 0;
            while (--n)
            {
                t = min(min(2 * dp[i], 3 * dp[j]), 5 * dp[k]);
                if (t == 2 * dp[i]) i ++;
                if (t == 3 * dp[j]) j ++;
                if (t == 5 * dp[k]) k ++;
                dp.push_back(t);
            }
            return dp.back();
        }
    }; 
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    50 第一个只出现一次的字符

    class Solution {
    public:
        char firstUniqChar(string s) {
            unordered_map<char, int> cnt;
            char res = ' ';
            for (auto x: s) cnt[x] ++;
            for (auto x: s)
                if (cnt[x] == 1) 
                {
                    res =  x;
                    break;
                }
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    day6

    51 数组中的逆序对

    class Solution {
    public:
        int merge_sort(vector<int>& nums, int l, int r)
        {
            if (l >= r) return 0;
            int mid = l + r  >> 1;
            int res = merge_sort(nums, l, mid) + merge_sort(nums, mid + 1, r);
            vector<int> temp;
            int i = l, j = mid + 1;
            
            while (i <= mid && j <= r)
            {
                if (nums[i] > nums[j])
                {  
                    temp.push_back(nums[j++]);
                    res += mid - i + 1;
                }
                else  temp.push_back(nums[i++]);
            }
    
            while (i <= mid) temp.push_back(nums[i++]);
            while (j <= r) temp.push_back(nums[j++]);
            i = l;
            for (auto x: temp) nums[i++] = x;
            return res;
        }
        int reversePairs(vector<int>& nums) {
            //暴力做法:冒泡排序  n2
            // 归并排序模板题 nlogn
            return merge_sort(nums, 0, nums.size() - 1);
    
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    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) {
            /*因为不等长,所以把两个链表拼接起来就登场了
              headA headB 时就相交了*/
            ListNode* prea = headA;
            ListNode* preb = headB;
            while (prea != preb)
            {
    
                prea = prea  != NULL? prea -> next: headB;
                preb = preb  != NULL? preb -> next: headA;
            }
            return prea;
            
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    53I 排序数组中查找数字

    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            if (nums.empty()) return 0;
            int l = 0, r = nums.size() - 1;
            // 分为三个区间
            //  target
            while (l < r)
            {
                // 只要小于k就会往右走,直到找到左端点
                int mid = (l + r) / 2;
                if (nums[mid] < target) l = mid + 1;
                else r = mid;
            }
            
            if (nums[l] != target) return 0;
            int left = l;
            
            l = 0, r = nums.size() - 1;
            while (l < r)
            {
                //只要小于等于k就会往右走,直到找到做端点
                //l == mid时注意向上取整
                int mid = (l + r + 1) / 2;
                if (nums[mid] <= target) l = mid;
                else r = mid - 1;
            }
            return r - left + 1;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    53II 0~n-1中缺失的数字

    class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            int n = nums.size();
            int res = n * (n + 1) / 2; // 1~n 总共有n个数 
            for (auto x: nums) res -= x;
            return res;
        }
    };
    
    
    //二分查找
    class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            int l = 0, r = nums.size() - 1;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (nums[mid] > mid) r = mid - 1;
                else if (nums[mid] == mid) l = mid + 1;
                else continue;
            }
            if (nums[l] == l) return l + 1;
            return l;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    53III 数组中数值和下标相等的元素

    class Solution {
    public:
        int getNumberSameAsIndex(vector<int>& nums) {
            
            int l = 0, r = nums.size() - 1;
            while (l < r)
            {
                // nums[i] - nums[i-1] >= 0
                // i - i  + 1 >= 0
                // nums[i] -  i -  nums[i-1] + i + 1 >=0
                // nums[i] - i 是单调递增的
                int mid = l + r >>1;
                if (nums[mid] - mid  > 0) r = mid;
                else if (nums[mid] - mid < 0) l = mid + 1;
                else return mid;
            }
            if (nums[l] == l) return l;
            return -1;        
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    54 二叉搜索树的第k大节点

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* ans;
        int kthLargest(TreeNode* root, int k) {
            dfs(root, k);
            return ans->val;
        }
    
        void dfs(TreeNode* root, int& k)
        {
            if (!root) return;
            dfs(root-> right, k);
            k --;
            if (k == 0) ans = root;
            if (k > 0 ) dfs(root->left, k);
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    55I 二叉树的深度

    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            // 左子树深度+右子树深度+1
            if (!root) return 0;
            return max(maxDepth(root->left), maxDepth(root->right)) + 1;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    55II 平衡二叉树

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        bool ans = true;
        bool isBalanced(TreeNode* root) {
            dfs(root);
            return ans;
        }
        int dfs(TreeNode* root)
        {
            if (!root) return 0;
            int ldepth = dfs(root->left);
            int rdepth = dfs(root->right);
            if (abs(ldepth - rdepth) > 1) ans = false;
            return max(ldepth, rdepth) + 1;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    56I 数组中数字出现的次数

    class Solution {
    public:
        vector<int> singleNumbers(vector<int>& nums) {
            // 异或操作可以得到集合中计数为1的数(只能有1个)
            // 如果有两个  异或结果为 x^y 其二进制表示一定有一位为1,另一个数该位为0
            // 将所有数分成1集合和0集合,然后进行异或即可找出两个集合中计数为1的数
            int sum = 0;
            for (auto x: nums) sum ^= x;
            int k = 0;
            while (!(sum >> k & 1)) k ++;
            int first = 0;
            for (auto x: nums)
                if (x >> k & 1) 
                    first ^= x;
            return vector<int>{first, sum ^ first};
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    56II 数组中数字出现的次数

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            // // 唯一数出现1次,其他出现3次
            // // 有限状态机
            // // 对于x的所有位(0,0)-> (1,0) -> (0,1) -> (0,0)
            // int ones = 0, twos = 0;
            // for (auto x: nums)
            // {
            //     ones = (ones ^ x) & (~twos);
            //     twos = (twos ^ x) & (~ones);
            // }
            // // ones相当于x的所有位 因为0遇到0->0  0遇到1->1
            // return ones;
            
            int ans = 0;
            for (int i = 0; i < 32; i ++)
            {   
                int cnt = 0;
                for (auto x: nums)
                    if (x >> i & 1) cnt ++;
                if (cnt % 3)
                    ans = ans | 1 << i;//%3=1的必定为唯一数
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    57I 和为s的数字

    //两数之和
    class Solution {
    public:
        unordered_set<int> hash;
        vector<int> twoSum(vector<int>& nums, int target) {
            for (auto x: nums)
            {
                if (hash.count(target-x)) return vector<int> {target-x, x};
                else hash.insert(x);     
            } 
            return vector<int> {-1,-1};  
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    57II 和为s的连续正数序列

    //双指针的题目
    class Solution {
    public:
        vector<vector<int>> findContinuousSequence(int target) {
            vector<vector<int>> res;
            for(int i = 1, j = 1 ,s = 1; i <= target; i ++)
            {
                while (s < target) s += ++ j;
                if (s == target && j - i + 1 > 1)
                {
                    vector<int> line;
                    for (int k = i; k <= j; k ++) line.push_back(k);
                    res.push_back(line);
    
                }
                s -= i;//每次右移需要减去i
            }
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    58I 翻转单词顺序

    class Solution {
    public:
        string reverseWords(string s) {
            string res;
            for (int i = 0; i < s.size(); i ++)
            {
                while (s[i] == ' ') i ++;//start of word
                int j = i;
                while (j < s.size() && s[j] != ' ') j ++;//end of word
                string word;
                for (int k = i; k < j; k ++) word += s[k];//word
                if (j < s.size()) res = ' ' + word + res;
                else if (j) res = word + res; 
                i = j;
            }
            return res[0] == ' '? res.substr(1) : res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    58II 左旋转字符串

    class Solution {
    public:
        string reverseLeftWords(string s, int n) {
            // 全部翻转
            // 前n-k和翻转  后k个翻转
            reverse(s.begin(), s.end());
            reverse(s.begin(), s.begin() + s.size() - n);
            reverse(s.begin() + s.size() - n,s.end());
            return s;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    59 队列的最大值

    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> res;
            deque<int> que;
            for (int i = 0; i <nums.size(); i++)
            {
                if (que.size() && i - que.front() + 1 > k)
                    que.pop_front();
                while (que.size() && nums[que.back()] <= nums[i])
                    que.pop_back();
                que.push_back(i);
                if (que.size() && i >= k - 1) res.push_back(nums[que.front()]);
            }
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    60I n个骰子的点数次数

    // 可能的点数列表
    // 背包问题:分组背包
    class Solution {
    public:
        vector<int> numberOfDice(int n) {
            vector<int> res;
            vector<int> dp(6 * n + 1, 0);//可能的得分
            for (int i = 1; i <= 6; i ++) dp[i] = 1;//第一次扔骰子1~6的投法都为1
            for (int i = 2; i <= n; i++) //分组数
                for (int j = 6 * i; j >= 0; j --) // 物品数 倒序遍历避免 当前dp[j-k]覆盖过去的dp[j-k]
                {   
                    dp[j] = 0;//清空数组,dp[j]不会由上一个同一得分求出
                    for (int k = 6; k >=1; k--)//价值
                        if (j > k) 
                            dp[j] += dp[j-k];
                }
            for (int i = n; i < 6 * n + 1; i ++) res.push_back(dp[i]);
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    60II n个骰子的点数概率

    //可能的点数对应的概率
    class Solution {
    public:
        vector<double> dicesProbability(int n) {
            //取值范围为n-6n  5n + 1中可能的值
            //dp[N][i] 表示有n颗骰子且和为i时的概率
            //dp[1][i] = 1/ 6
            //dp[2][i] = dp[1][i-1]+dp[1][i-2]...+dp[1][i-6]
            //res = dp[N]
            //当前骰子点数之和i+1,,i+2, i+6,只能由dp即过去的的i中递推过来
            //如果反向推到会导致数组越界
            vector<double> dp(6, 1.0/6.0);
            for (int i = 2; i <= n; i ++)
            {
                vector<double> temp(5*i + 1, 0.0);
                for (int j = 0; j < dp.size(); j ++)    
                    for (int k = 0; k < 6; k ++)
                        temp[j + k] += dp[j] * (1.0/ 6.0);
                dp = temp;
            }
            return dp;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    day7

    61 扑克牌的顺子

    class Solution {
    public:
        bool isStraight(vector<int>& nums) {
            /*1 删掉0
              2 重复
              3 差<=4  
            */
            if (!nums.size()) return false;
            sort(nums.begin(), nums.end());
            int k = 0;
            while (!nums[k]) k ++;
            for (int i = k + 1; i < nums.size(); i ++)
                if (nums[i] == nums[i-1]) 
                    return false;
            return nums.back() - nums[k] <= 4;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    62 圆圈中最后剩下的数字(约瑟夫环)

    class Solution {
    public:
        int lastRemaining(int n, int m) {
            /*
            n个人每次删去第m个,最终剩下dp[n][m] 
            0 1 2 ...           m-1   m     m+1    m+2 ...n
            重新编号 .           ——    0     1      2  
            n-1个人则是,重新编号后的dp[n-1,m]  (此时原来的编号为 新的编号+m)%n右移了m位
            dp[n][m] = (dp[n-1][m] + m) % n
            dp[1][m] = 0
            */
            // vector> dp(n + 1, vector(m + 1, 0));
            // for (int i = 2; i <= n; i ++)
            //     for (int j = 1; j <= m; j ++)
            //         dp[i][j] = (dp[i-1][j] + j) % i;
            // return dp[n][m];
            if (n == 1) return 0;
            return (lastRemaining(n - 1, m) + m) % n;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    63 股票的最大利润

    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int minPrice = INT_MAX;
            int res = 0;
            for (auto p: prices)
            {
                if (p < minPrice) minPrice = p;
                res = max(res, p - minPrice);
            }
            return res;
    
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    64 1+2+…+n

    class Solution {
    public:
        int sumNums(int n) {
            int res = n;
            (n >0) && (res +=   sumNums(n- 1));
            return res;
    
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    65 不用加减乘除的加法

    class Solution {
    public:
        int add(int a, int b) {
            // 位运算在计算机中的加法
            // a + b = cd 
            // d = a^b
            // c = a&b
            /*
            不考虑所有进位计算 a^b
            再加上所有进位     a&b 有进位的地方都是1,需要把结果左移1  a&b << 1;
            结果等于 a^b + a&b << 1 新的两个数相加
            b中的进位总会消失
            */
            while (b)
            {
                int sum1 = a ^ b;
                unsigned int carry = (unsigned int)(a & b) << 1;
                a =  sum1;
                b = carry;//
            }
            return a;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    66 构建乘积数组

    class Solution {
    public:
        vector<int> constructArr(vector<int>& a) {
            if (!a.size()) return vector<int>();
            vector<int> res(a.size(),1);
            //左半边先乘进去 1 2 3 4 5
            // 1 1 2 6 24 
            for (int i = 0, lprod = 1; i < a.size(); i ++){
                res[i] = lprod;
                lprod*= a[i];      
            }
            //右半边再乘进去
            // i= 4  24*1  右边没有 rprod = 5
            // i= 3  6*5   右边是5 左边是123 rprod = 20
            // i= 2  2*20   左边是12 右边是45 rprod=60
            // i= 1  1*60   左边是1  rprod = 120
            // i= 0  120
            for (int i = a.size() - 1, rprod = 1; i >= 0; i --)
            {
                res[i]*= rprod;
                rprod*= a[i];
            }
            return res;
    
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    67 字符串转换为整数

    class Solution {
    public:
        int strToInt(string str) {
            int k = 0;
            while (k < str.size() && str[k] == ' ') k ++;
            long long num = 0;
            bool is_minus = false;
            if (str[k] == '+') k ++;
            else if (str[k] == '-')  
            {
                k++;
                is_minus=true;
            }
            while (k < str.size() && str[k] >= '0' && str[k] <= '9')
            {
                num = num * 10 +  str[k] - '0';
                k++;
                if (!is_minus && num > INT_MAX) return  INT_MAX;
                if (is_minus  && num > INT_MAX) return  INT_MIN;
            }
            if (is_minus) num *= -1;
            return (int)num;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    68 二叉树的最低公共祖先

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            /*
            在左右两边,返回根节点
            都在左边,公共祖先在左边
            都在右边,公共祖先在右边
            */
            if (!root) return nullptr;
            if (root == p || root == q) return root;
            auto left = lowestCommonAncestor(root->left, p, q);//查找左子树中是否存在p q节点
            auto right = lowestCommonAncestor(root->right,p, q);//查找右子树中是否存在p q节点
            if (left && right) return root;
            else if (left) return left;
            return right;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
  • 相关阅读:
    添加用户报错useradd: cannot open /etc/passwd
    2022护网日记,护网工作内容、护网事件、告警流量分析
    【业务安全-02】业务数据安全测试及商品订购数量篡改实例
    力扣记录:剑指offer(7)——JZ59-68
    匈利亚算法的实现
    矩阵分析与应用-13-矩阵的迹
    paramiko库SSHClient的exec_command执行sudo命令时如何输入密码
    Ruoyi若依前后端一体项目整合cas单点登录
    搜索技术——盲目与启发
    Azkaban (二) --------- Azkaban 入门
  • 原文地址:https://blog.csdn.net/weixin_51499396/article/details/127876040