2487、从链表中移除节点——递归、单调栈
整个过程可以理解为维护一个递减的栈，栈中的节点是按照从大到小的顺序排列的。每遇到一个新节点时，如果栈顶节点的值大于当前节点的值，则将栈顶节点替换为当前节点，即删除栈顶节点，并将当前节点压入栈中。这样最终栈中留下的节点就是需要保留的节点。
代码语言：javascript复制/**
* 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];
}
};
