【LeetCode刷题日记】持续更新中...

【LeetCode刷题日记】持续更新中...

• Day-06-2021-02-04-栈基础题：
• Day-05-2021-02-03-基础题：
• Day-04-2021-02-02-基础题：
• Day-03-2021-02-01-链表基础题：
• Day-02-2021-01-31-链表基础题：
• Day-01-2021-01-30-基础题：

Day-06-2021-02-04-栈基础题：

224. 基本计算器

实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。

class Solution
{
public:
    int calculate(string s)
    {
        stack<int> st;
        int res = 0, n = s.size(), sign = 1;
        for (int i = 0; i < n; i++)
        {
            int num = 0;
            if (s[i] >= '0')
            {
                while (i < n && s[i] >= '0')
                {
                    num = num * 10 + (s[i] - '0');
                    i++;
                }
                i--;
                res += sign * num;
            }
            else if (s[i] == '+')
                sign = 1;
            else if (s[i] == '-')
                sign = -1;
            else if (s[i] == '(')
            {
                st.push(res);
                st.push(sign);
                res = 0;
                sign = 1;
            }
            else if (s[i] == ')')
            {
                res *= st.top();
                st.pop();
                res += st.top();
                st.pop();
            }
        }
        return res;
    }
};

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

class MinStack
{
public:
    stack<int> s;
    stack<int> m;
    MinStack()
    {
        m.push(INT_MAX);
    }
    void push(int x)
    {
        s.push(x);
        m.push(min(m.top(), x));
    }
    void pop()
    {
        s.pop();
        m.pop();
    }
    int top()
    {
        return s.top();
    }
    int getMin()
    {
        return m.top();
    }
};

150. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

class Solution
{
public:
    int evalRPN(vector<string> &tokens)
    {
        vector<int> v;
        for (auto s : tokens)
        {
            if (s == "+" || s == "-" || s == "*" || s == "/")
            {
                int x2 = v.back();
                v.pop_back();
                int x1 = v.back();
                v.pop_back();
                if (s == "+")
                    v.push_back(x1 + x2);
                if (s == "-")
                    v.push_back(x1 - x2);
                if (s == "*")
                    v.push_back(x1 * x2);
                if (s == "/")
                    v.push_back(x1 / x2);
            }
            else
                v.push_back(stoi(s));
        }
        return v.back();
    }
};

Day-05-2021-02-03-基础题：

102. 二叉树的层序遍历（递归）

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

class Solution
{
public:
    void search(TreeNode *root, vector<vector<int>> &ans, int layer)
    {
        if (root)
        {
            if (ans.size() <= layer)
            {
                vector<int> temp;
                ans.push_back(temp);
            }
            ans[layer].push_back(root->val);
            search(root->left, ans, layer + 1);
            search(root->right, ans, layer + 1);
        }
    }
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> ans;
        search(root, ans, 0);
        return ans;
    }
};

102. 二叉树的层序遍历（队列）

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

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 size = q.size();
            ret.push_back(vector<int>());
            for (int i = 0; i < size; i++)
            {
                TreeNode *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;
    }
};

103. 二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root)
    {
        vector<vector<int>> ans;
        if (!root)
        {
            return ans;
        }
        queue<TreeNode *> nodeQueue;
        nodeQueue.push(root);
        bool isOrderLeft = true;
        while (!nodeQueue.empty())
        {
            deque<int> levelList;
            int size = nodeQueue.size();
            for (int i = 0; i < size; ++i)
            {
                auto node = nodeQueue.front();
                nodeQueue.pop();
                if (isOrderLeft)
                {
                    levelList.push_back(node->val);
                }
                else
                {
                    levelList.push_front(node->val);
                }
                if (node->left)
                {
                    nodeQueue.push(node->left);
                }
                if (node->right)
                {
                    nodeQueue.push(node->right);
                }
            }
            ans.push_back(vector<int>{levelList.begin(), levelList.end()});
            isOrderLeft = !isOrderLeft;
        }
        return ans;
    }
};

Day-04-2021-02-02-基础题：

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

class Solution
{
public:
    int trap(vector<int> &height)
    {
        if (height.size() < 3)
        {
            return 0;
        }
        int i = 0;
        int ans = 0, n;
        int max_index = 0;
        for (i = 1; i < height.size(); i++)
        {
            if (height[i] > height[max_index])
            {
                max_index = i;
            }
        }
        stack<int> h;
        // 从左向右
        i = 0;
        int left;
        while (height[i] < height[i + 1])
        {
            i++;
            if (i + 1 > max_index)
            {
                break;
            }
        }
        left = height[i];
        for (i++; i <= max_index; i++)
        {
            n = height[i];
            if (n < left)
            {
                h.push(n);
            }
            else
            {
                while (!h.empty())
                {
                    ans += left - h.top();
                    h.pop();
                }
                left = n;
            }
        }
        // 从右向左
        i = height.size() - 1;
        int right;
        while (height[i] < height[i - 1] && i > max_index)
        {
            i--;
            if (i - 1 < max_index)
            {
                break;
            }
        }
        right = height[i];
        for (i--; i >= max_index; i--)
        {
            n = height[i];
            if (n < right)
            {
                h.push(n);
            }
            else
            {
                while (!h.empty())
                {
                    ans += right - h.top();
                    h.pop();
                }
                right = n;
            }
        }
        return ans;
    }
};

20. 有效的括号

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

class Solution
{
public:
    bool isValid(string s)
    {
        int n = s.size();
        if (n % 2 == 1)
        {
            return false;
        }
        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}};
        stack<char> stk;
        for (char ch : s)
        {
            if (pairs.count(ch))
            {
                if (stk.empty() || stk.top() != pairs[ch])
                {
                    return false;
                }
                stk.pop();
            }
            else
            {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

class Solution
{
public:
    void inorder(TreeNode *root, vector<int> &ans)
    {
        if (root)
        {
            inorder(root->left, ans);
            ans.push_back(root->val);
            inorder(root->right, ans);
        }
    }
    vector<int> inorderTraversal(TreeNode *root)
    {
        vector<int> ans;
        inorder(root, ans);
        return ans;
    }
};

96. 不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

class Solution
{
public:
    int numTrees(int n)
    {
        vector<int> ans(n + 1, 0);
        ans[0] = 1;
        ans[1] = 1;
        for (int in = 2; in <= n; in++)
        {
            for (int i = 1; i <= in; i++)
            {
                ans[in] += ans[i - 1] * ans[in - i];
            }
        }
        return ans[n];
    }
};

Day-03-2021-02-01-链表基础题：

61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

class Solution
{
public:
    ListNode *rotateRight(ListNode *head, int k)
    {
        if ((!head) || (!head->next) || !k)
            return head;
        int count = 0;
        ListNode *hair = new ListNode(0, head);
        ListNode *tail = hair;
        while (tail->next)
        {
            count++;
            tail = tail->next;
        }
        k = k % count;
        if (k == 0) return head;
        tail = head;
        for (int i = 0; i < k; i++)
        {
            tail = tail->next;
        }
        while (tail->next)
        {
            tail = tail->next;
            head = head->next;
        }
        ListNode *temp = hair->next;
        hair->next = head->next;
        head->next = tail->next;
        tail->next = temp;
        return hair->next;
    }
};

82. 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

class Solution
{
public:
    // 0->|1->2->3->3->4->4->5|->null
    // 0->|1->2->4->4->5|->null
    ListNode *deleteDuplicates(ListNode *head)
    {
        if (!head || !head->next)
            return head;
        ListNode *hair = new ListNode(0, head);
        ListNode *p1 = hair, *p2 = head;
        while (p2 && p2->next)
        {
            if (p2->val == p2->next->val)
            {
                while (p2->next && p2->val == p2->next->val)
                    p2 = p2->next;
                p1->next = p2->next;
                p2 = p1->next;
            }
            else
            {
                p1 = p1->next;
                p2 = p2->next;
            }
        }
        return hair->next;
    }
};

83. 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

class Solution
{
public:
    ListNode *deleteDuplicates(ListNode *head)
    {
        if(!head || !head->next) return head;
        ListNode *p1 = head, *p2 = p1->next;
        // 1->1->2->2->2->3->3
        // 1->2->2->2->3->3
        // 1->2->3->null
        while (p1 && p2)
        {
            while (p2 && p2->val == p1->val)
            {
                p2 = p2->next;
            }
            p1->next = p2;
            p1 = p1->next;
            if(!p1) break;
            p2 = p1->next;
        }
        return head;
    }
};

86. 分隔链表

给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

class Solution
{
public:
    ListNode *partition(ListNode *head, int x)
    {
        if (!head || !head->next)
            return head;
        ListNode *p1 = new ListNode(-1), *p2 = new ListNode(-1);
        ListNode *hair1 = p1, *hair2 = p2;
        while (head)
        {
            if (head->val < x)
            {
                p1->next = head;
                p1 = p1->next;
            }
            else
            {
                p2->next = head;
                p2 = p2->next;
            }
            head = head->next;
        }
        p1->next = hair2->next;
        p2->next = head;
        return hair1->next;
    }
};

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

class Solution
{
public:
    // 输入: 1->2->3->4->5->NULL, m = 2, n = 4
    //       m  n
    //       1->3->2->4->5->NULL
    // 输出: 1->4->3->2->5->NULL
    ListNode *reverseBetween(ListNode *head, int m, int n)
    {
        ListNode *hair = new ListNode(-1, head);
        ListNode *pm = hair, *pn = nullptr, *temp;
        for (int i = 0; i < m - 1; i++)
            pm = pm->next;
        pn = pm->next;
        ListNode *link = pn;
        // pn->next 放到 pm 后面
        for (int i = 0; i < n - m; i++)
        {
            temp = pn->next;
            pn->next = temp->next;
            pm->next = temp;
            temp->next = link;
            link = temp;
        }
        return hair->next;
    }
};

Day-02-2021-01-31-链表基础题：

23. 合并K个升序链表（分治）

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *a, ListNode *b)
    {
        if ((!a) || (!b))
            return a ? a : b;
        ListNode *head = new ListNode(0), *tail = head;
        while (a && b)
        {
            if (a->val < b->val)
            {
                tail->next = a;
                a = a->next;
            }
            else
            {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }
        tail->next = (a ? a : b);
        return head->next;
    }
    ListNode *merge(vector<ListNode *> &lists, int l, int r)
    {
        if (l == r)
        {
            return lists[l];
        }
        else if (l > r)
        {
            return nullptr;
        }
        int mid = (l + r) / 2;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        return merge(lists, 0, lists.size() - 1);
    }
};

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

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        if (!head)
            return nullptr;
        ListNode *p = head;
        while (p && p->next)
        {
            int temp = p->val;
            p->val = p->next->val;
            p->next->val = temp;
            p = p->next->next;
        }
        return head;
    }
};

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

class Solution
{
public:
    // 翻转一个子链表，并且返回新的头与尾 |1->2->3|->4
    pair<ListNode *, ListNode *> myReverse(ListNode *head, ListNode *tail)
    {
        ListNode *p1 = head, *p2 = tail->next, *p = nullptr;
        while (p1 != tail)
        {
            p = p1->next;
            p1->next = p2;
            p2 = p1;
            p1 = p;
        }
        tail->next = p2;
        return {tail, head};
    }

    ListNode *reverseKGroup(ListNode *head, int k)
    {
        ListNode *hair = new ListNode(0);
        hair->next = head;
        ListNode *pre = hair;

        while (head)
        {
            ListNode *tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i)
            {
                tail = tail->next;
                if (!tail)
                {
                    return hair->next;
                }
            }
            ListNode *nex = tail->next;
            pair<ListNode *, ListNode *> result = myReverse(head, tail);
            head = result.first;
            tail = result.second;
            pre->next = head;
            tail->next = nex;
            pre = tail;
            head = tail->next;
        }

        return hair->next;
    }
};

Day-01-2021-01-30-基础题：

两数相加：

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *head = nullptr, *tail = nullptr;
        int temp = 0;
        while (l1 || l2)
        {
            int x1 = l1 ? l1->val : 0;
            int x2 = l2 ? l2->val : 0;
            int y = x1 + x2 + temp;
            if (!head)
            {
                head = tail = new ListNode(y % 10);
            }
            else
            {
                tail->next = new ListNode(y % 10);
                tail = tail->next;
            }
            temp = y / 10;
            if (l1)
            {
                l1 = l1->next;
            }
            if (l2)
            {
                l2 = l2->next;
            }
        }
        if(temp){
            tail->next = new ListNode(temp);
        }
        return head;
    }
};

删除链表的倒数第 N 个结点：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;
        ListNode* second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

合并两个有序链表：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        ListNode *ans = new ListNode(0);
        ListNode *p = ans;
        while (l1 && l2)
        {
            int x1 = l1 ? l1->val : INT_MIN;
            int x2 = l2 ? l2->val : INT_MIN;
            if (x1 < x2)
            {
                p->next = new ListNode(x1);
                p = p->next;
                l1 = l1->next;
            }
            else
            {
                p->next = new ListNode(x2);
                p = p->next;
                l2 = l2->next;
            }
        }
        p->next = l1 ? l1 : l2;
        return ans->next;
    }
};

合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        ListNode *ans = new ListNode(0);
        ListNode *p = ans;
        while (l1 && l2)
        {
            int x1 = l1 ? l1->val : INT_MIN;
            int x2 = l2 ? l2->val : INT_MIN;
            if (x1 < x2)
            {
                p->next = new ListNode(x1);
                p = p->next;
                l1 = l1->next;
            }
            else
            {
                p->next = new ListNode(x2);
                p = p->next;
                l2 = l2->next;
            }
        }
        p->next = l1 ? l1 : l2;
        return ans->next;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        ListNode *ans = nullptr;
        for (int i = 0; i < lists.size(); i++){
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
};