LeetCode 每日一题
2487. 从链表中移除节点
问题
给你一个链表的头节点 head 。
移除每个右侧有一个更大数值的节点。
返回修改后链表的头节点 head 。
解答
- 首先可以看出这是一个非常典型的单调栈，所以直接用单调栈即可解决
- 其次，单调栈是栈，那么就可以考虑递归，类似于 拓展1 的反转链表递归方法，可以利用后续遍历的思想进行递归
- 最后，也可以使用反转链表实现
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNodes(struct ListNode* head) {
struct ListNode *stack[100000] = {0};
stack[0] = head;
int top = 1;
head = head -> next;
while (head) {
while (top && head -> val > stack[top - 1] -> val) {
top--;
}
stack[top++] = head;
head = head -> next;
}
for(int i = 0; i < top - 1; i++) {
stack[i] -> next = stack[i + 1];
}
stack[top - 1] -> next = 0;
return stack[0];
}
拓展
依据灵神的网站题目顺序
1325. 删除给定值的叶子节点
问题
给你一棵以 root 为根的二叉树和一个整数 target ，请你删除所有值为 target 的 叶子节点 。
注意，一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target ，那么这个节点也应该被删除。
也就是说，你需要重复此过程直到不能继续删除。
解答
很显然的 后序遍历
代码：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
def dfs(p, node, flag):
if not node:
return None
l = dfs(node, node.left, 0)
r = dfs(node, node.right, 1)
if not l and not r and node.val == target:
node = None
if p and flag == 0:
p.left = node
elif p and flag == 1:
p.right = node
return node
return dfs(None, root, 0)
# 优化一下
class Solution:
def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
def dfs(node):
if not node:
return None
node.left = dfs(node, node.left, 0)
node.right = dfs(node, node.right, 1)
if not node.left and not node.right and node.val == target:
node = None
return node
return dfs(None, root, 0)
拓展
1217. 玩筹码
问题
有 n 个筹码。第 i 个筹码的位置是 position[i] 。
我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个筹码的位置从 position[i] 改变为:
position[i] + 2 或 position[i] - 2 ，此时 cost = 0
position[i] + 1 或 position[i] - 1 ，此时 cost = 1
返回将所有筹码移动到同一位置上所需要的 最小代价 。
解答
因为整个数组的下标都是在自然数域内，所以可以考虑将操作扩充至移动 n 次需要花多少钱，此为原子操作复杂化
将两个操作合在一起则变为 移动偶数次不需要花钱，移动奇数次需要花 1 元
代码：
class Solution:
def minCostToMoveChips(self, position: List[int]) -> int:
cnt = [0, 0]
for i in position:
cnt[i & 1] += 1
return min(cnt)
拓展
1006. 笨阶乘
问题
- 数学问题数学方法解，从中寻找数学规律
- 公式问题栈来解，类似于扩展的三道题，其本质是符号的优先级，讲到优先级，我们应该联想其本质 偏序关系，而本质上，单调栈 就是获取 偏序集 的一种思想
解答
代码：
int clumsy(int n) {
int stk[n], top = 0;
stk[top++] = n;
n--;
int index = 0; // 用于控制乘、除、加、减
while (n > 0) {
if (index % 4 == 0) {
stk[top - 1] *= n;
} else if (index % 4 == 1) {
stk[top - 1] /= n;
} else if (index % 4 == 2) {
stk[top++] = n;
} else {
stk[top++] = -n;
}
index++;
n--;
}
// 把栈中所有的数字依次弹出求和
int sum = 0;
while (top) {
sum += stk[--top];
}
return sum;
}
// 作者：力扣官方题解
// 链接：https://leetcode.cn/problems/clumsy-factorial/solutions/692629/ben-jie-cheng-by-leetcode-solution-deh2/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
int clumsy(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else if (n == 3) {
return 6;
} else if (n == 4) {
return 7;
}
if (n % 4 == 0) {
return n + 1;
} else if (n % 4 <= 2) {
return n + 2;
} else {
return n - 1;
}
}
// 作者：力扣官方题解
// 链接：https://leetcode.cn/problems/clumsy-factorial/solutions/692629/ben-jie-cheng-by-leetcode-solution-deh2/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
拓展
2110. 股票平滑下跌阶段的数目
问题
给你一个整数数组 prices ，表示一支股票的历史每日股价，其中 prices[i] 是这支股票第 i 天的价格。
一个 平滑下降的阶段 定义为：对于 连续一天或者多天 ，每日股价都比 前一日股价恰好少 1 ，这个阶段第一天的股价没有限制。
请你返回 平滑下降阶段 的数目。
解答
对于某一天，当前的利益只与之前的几天有关，这是典型的动态规划问题
代码：
class Solution:
def getDescentPeriods(self, prices: List[int]) -> int:
n = len(prices)
res = 1 # 平滑下降阶段的总数，初值为 dp[0]
prev = 1 # 上一个元素为结尾的平滑下降阶段的总数，初值为 dp[0]
# 从 1 开始遍历数组，按照递推式更新 prev 以及总数 res
for i in range(1, n):
if prices[i] == prices[i-1] - 1:
prev += 1
else:
prev = 1
res += prev
return res
# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/number-of-smooth-descent-periods-of-a-stock/solutions/1167833/gu-piao-ping-hua-xia-die-jie-duan-de-shu-w3hi/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。