《英雄联盟》也要裁员了，赔偿方案感人。。
《英雄联盟》裁员
大家平时可能听「游戏工作室裁员/解散」、「游戏上线几十天就宣布关停」比较多，这些大多都是因为游戏在市场上表现不好所导致的。
那有没有一些市场表现十分火热，甚至是国民级/现象级的游戏也面临裁员呢？
答案是有的。
著名游戏厂商「拳头游戏」宣布要进行裁员，而且本次裁员主要针对《英雄联盟》团队。
《英雄联盟》作为风靡全球的游戏，火了 15 年，虽然这几年因为手游的崛起，开始逐渐走下坡路，但也算是游戏界的常青树，如今也要面临裁员。
实际上，这不是《英雄联盟》的第一次裁员，早在今年一月份，拳头游戏就宣布过，将在全球范围内裁员约 530 人，占总人数的 11%，当中就涉及《英雄联盟》团队的成员。
关于这次裁员，拳头游戏方面给出的解释和上次类似：“这并不是为了节省开支而裁员，而是为了确保我们拥有合适的专业人才。”
别的公司说这样的话，我会觉得是场面话，但拳头游戏说这样的话，可信度还真不低。
看看他们这两次裁员的赔偿方案就知道了：
-
按法律规定赔偿 n+1，n+1 如果少于 6 个月，则按 6 个月计算，即 至少赔偿 6 个月，工作年限高的话上不封顶 -
提供全年的绩效奖金，按前一年的进行计算，若在 2024 年被裁，可以拿到与 2023 年个人年度绩效奖金等额的现金奖励 -
在退回公司电脑后， 可以申请一台笔记本电脑，同时可以保留原有的键盘、鼠标、耳机等外设 -
提供 就业安置援助、医疗保险等等
这还真不像是经济原因裁员，但《英雄联盟》在市场上的失势又是客观事实。
对此你怎么看，你有玩过《英雄联盟》这款游戏吗？欢迎评论区交流。
...
回归主题。
来一道和「秋招」相关的算法题。
题目描述
平台：LeetCode
题号：173
实现一个二叉搜索树迭代器类 BSTIterator，表示一个按中序遍历二叉搜索树（BST）的迭代器：
-
BSTIterator(TreeNode root)初始化BSTIterator类的一个对象。BST的根节点root会作为构造函数的一部分给出。指针应初始化为一个不存在于BST中的数字，且该数字小于BST中的任何元素。 -
boolean hasNext()如果向指针右侧遍历存在数字，则返回true；否则返回false。 -
int next()将指针向右移动，然后返回指针处的数字。
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
示例：
输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]
解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False
提示：
-
树中节点的数目在范围 [1, ] 内 -
-
最多调用 次 hasNext和next操作
进阶：
-
你可以设计一个满足下述条件的解决方案吗？ next()和hasNext()操作均摊时间复杂度为 ，并使用 内存。其中h是树的高度。
基本思路
「这道题本质上考的是「将迭代版的中序遍历代码」做等价拆分。」
我们知道，中序遍历的基本逻辑是：处理左子树 -> 处理当前节点 -> 处理右子树。
其中迭代做法是利用「栈」进行处理：
-
先将当前节点的所有左子树压入栈，压到没有为止 -
将最后一个压入的节点弹出（栈顶元素），加入答案 -
将当前弹出的节点作为当前节点，重复步骤一
相应的裸题在这里：94. 二叉树的中序遍历。
中序遍历的迭代代码：
class Solution {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> d = new ArrayDeque<>();
public List<Integer> inorderTraversal(TreeNode root) {
while (root != null || !d.isEmpty()) {
// 步骤 1
while (root != null) {
d.addLast(root);
root = root.left;
}
// 步骤 2
root = d.pollLast();
ans.add(root.val);
// 步骤 3
root = root.right;
}
return ans;
}
}
总的来说是这么一个迭代过程：步骤 1 -> 步骤 2 -> 步骤 3 -> 步骤 1 ...
「中序遍历」代码的「等价拆分」
首先因为 next() 方法中我们需要输出一个值，执行的的是「步骤 2」的逻辑，同时我们需要在其前后添加「步骤 1」和「步骤 3」。
另外，我们还有一个 hasNext() 要处理，显然 hasNext() 应该对应我们的栈是否为空。
为此，我们「需要确保每次输出之后「步骤 1」被及时执行。」
综上，我们应该在初始化时，走一遍「步骤 1」，然后在 next() 方法中走「步骤 2」、「步骤 3」和「步骤 1」。
Java 代码：
class BSTIterator {
Deque<TreeNode> d = new ArrayDeque<>();
public BSTIterator(TreeNode root) {
// 步骤 1
dfsLeft(root);
}
public int next() {
// 步骤 2
TreeNode root = d.pollLast();
int ans = root.val;
// 步骤 3
root = root.right;
// 步骤 1
dfsLeft(root);
return ans;
}
public boolean hasNext() {
return !d.isEmpty();
}
void dfsLeft(TreeNode root) {
while (root != null) {
d.addLast(root);
root = root.left;
}
}
}
C++ 代码：
class BSTIterator {
public:
stack<TreeNode*> d;
BSTIterator(TreeNode* root) {
dfsLeft(root);
}
int next() {
TreeNode* root = d.top();
d.pop();
int ans = root->val;
root = root->right;
dfsLeft(root);
return ans;
}
bool hasNext() {
return !d.empty();
}
void dfsLeft(TreeNode* root) {
while (root != nullptr) {
d.push(root);
root = root->left;
}
}
};
Python 代码：
class BSTIterator:
def __init__(self, root: TreeNode):
self.d = deque()
self.dfsLeft(root)
def next(self) -> int:
root = self.d.pop()
ans = root.val
root = root.right
self.dfsLeft(root)
return ans
def hasNext(self) -> bool:
return len(self.d) > 0
def dfsLeft(self, root):
while root:
self.d.append(root)
root = root.left
TypeScript 代码：
class BSTIterator {
d: TreeNode[];
constructor(root: TreeNode | null) {
this.d = [];
this.dfsLeft(root);
}
next(): number {
const root = this.d.pop()!;
const ans = root.val;
root.right && this.dfsLeft(root.right);
return ans;
}
hasNext(): boolean {
return this.d.length > 0;
}
dfsLeft(root: TreeNode | null): void {
while (root) {
this.d.push(root);
root = root.left;
}
}
}
-
时间复杂度：由于每个元素都是严格「进栈」和「出栈」一次，复杂度为均摊 -
空间复杂度：栈内最多保存与深度一致的节点数量，复杂度为
进阶
若要求空间复杂度也能做到 ，该如何做呢？
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
原文地址：https://blog.csdn.net/weixin_33243821/article/details/143018430
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！