leetcode刷题记录——2024年1月

Andromeda

发布于 2024-01-04 08:16:51

1060

发布于 2024-01-04 08:16:51

2487、从链表中移除节点——递归、单调栈

整个过程可以理解为维护一个递减的栈，栈中的节点是按照从大到小的顺序排列的。每遇到一个新节点时，如果栈顶节点的值大于当前节点的值，则将栈顶节点替换为当前节点，即删除栈顶节点，并将当前节点压入栈中。这样最终栈中留下的节点就是需要保留的节点。

/**
 * 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 *removeNode(ListNode *head,
                         stack<ListNode *> &st)
    {
        if (head == nullptr)
        {
            return nullptr;
        }
        head->next = removeNode(head->next, st);
        if (st.empty())
        {
            st.push(head);
        }
        else
        {
            if (st.top()->val > head->val)
            {
                delete head;
                return st.top();
            }
            else
            {
                st.push(head);
            }
        }
        return head;
    }

    ListNode *removeNodes(ListNode *head)
    {
        stack<ListNode *> st;
        return removeNode(head, st);
    }
};

63、不同路径Ⅱ——动态规划

对于每个位置(i, j)，遍历方向数组dirs中的每个方向。
检查当前位置的上方和左方是否是合法的位置（即不越界），并且上方和左方的位置不是障碍物（值为0）。
如果满足上述条件，将当前位置(i, j)的路径数量dp[i][j]增加上方位置(i+dir.first, j+dir.second)和左方位置(i+dir.first, j+dir.second)的路径数量之和。
如果终点是障碍物，即obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1]等于1，说明无法到达终点，返回0；否则返回dp[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1]。

class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        vector<vector<int>> dp(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), 0));
        dp[0][0] = 1;
        vector<pair<int, int>> dirs = {
            {-1, 0},
            {0, -1},
        };
        for (int i = 0; i < obstacleGrid.size(); i++)
        {
            for (int j = 0; j < obstacleGrid[0].size(); j++)
            {
                for (auto dir : dirs)
                {
                    if (i + dir.first >= 0 &&
                        j + dir.second >= 0 &&
                        obstacleGrid[i + dir.first][j + dir.second] == 0)
                    {
                        dp[i][j] += dp[i + dir.first][j + dir.second];
                    }
                }
            }
        }
        return obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1] == 1 ? 0 : dp[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1];
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

int