【Leetcode刷题记录】1、最多可以摧毁的敌人城堡数目；2、消灭怪物的最大数量；3、序列化和反序列化二叉搜索树

Archigenius / 2023-09-04 / 原文

1、最多可以摧毁的敌人城堡数目

题目：给你一个长度为 n ，下标从 0 开始的整数数组 forts ，表示一些城堡。forts[i] 可以是 -1 ，0 或者 1 ，其中：

-1 表示第 i 个位置没有城堡。
0 表示第 i 个位置有一个敌人的城堡。
1 表示第 i 个位置有一个你控制的城堡。

现在，你需要决定，将你的军队从某个你控制的城堡位置 i 移动到一个空的位置 j ，满足：

0 <= i, j <= n - 1
军队经过的位置只有敌人的城堡。正式的，对于所有 min(i,j) < k < max(i,j) 的 k ，都满足 forts[k] == 0 。

当军队移动时，所有途中经过的敌人城堡都会被摧毁。

请你返回最多可以摧毁的敌人城堡数目。如果无法移动你的军队，或者没有你控制的城堡，请返回 0 。

思路：一次遍历！只需找到相邻的 1 和 -1 的距离的最大值即可。代码很优雅！

代码：C++

 1 class Solution {
 2 public:
 3     int captureForts(vector<int>& forts) {
 4         int res = 0, pre = -1;
 5         for(int i = 0; i < forts.size(); ++i){
 6             if(forts[i] == 1 || forts[i] == -1){
 7                 if(pre >= 0 && forts[i] != forts[pre]){
 8                     res = max(res,i - pre - 1);
 9                 }
10                 pre = i;
11             }
12         }
13         return res;
14     }
15 };

2、消灭怪物的最大数量

题目：你正在玩一款电子游戏，在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为 n 的整数数组 dist ，其中 dist[i] 是第 i 个怪物与城市的 初始距离（单位：米）。

怪物以恒定的速度走向城市。给你一个长度为 n 的整数数组 speed 表示每个怪物的速度，其中 speed[i] 是第 i 个怪物的速度（单位：米/分）。

怪物从 第 0 分钟 时开始移动。你有一把武器，并可以选择在每一分钟的开始时使用，包括第 0 分钟。但是你无法在一分钟的中间使用武器。这种武器威力惊人，一次可以消灭任一还活着的怪物。

一旦任一怪物到达城市，你就输掉了这场游戏。如果某个怪物恰在某一分钟开始时到达城市，这会被视为输掉游戏，在你可以使用武器之前，游戏就会结束。

返回在你输掉游戏前可以消灭的怪物的最大数量。如果你可以在所有怪物到达城市前将它们全部消灭，返回 n 。

思路：将每个怪物到达城堡的时间放进一个非递减优先队列，注意有些怪物到达的时间是个小数，需要向上取整。然后从优先队列中一次取出怪物，如果怪物到达的时间小于等于存活的天数，则结束！

代码：C++

 1 class Solution {
 2 public:
 3     int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
 4         priority_queue<int,vector<int>,greater<int>> que;
 5         for(int i = 0; i < dist.size(); ++i){
 6             if(speed[i] >= dist[i]){
 7                 que.push(1);
 8             } else {
 9                 que.push(dist[i]%speed[i]>0 ? dist[i]/speed[i] + 1: dist[i]/speed[i]);
10             }
11         }
12         int res = 0;
13         while(!que.empty()){
14             int cur = que.top();
15             que.pop();
16             if(res >= cur){
17                 break;
18             }
19             res++;
20         }
21         return res;
22     }
23 };

3、序列化和反序列化二叉搜索树

题目：序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。对序列化/反序列化算法的工作方式没有限制。您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

思路：首先将二叉树中序遍历得到字符串，每个节点的值用逗号分开，空节点用 NULL 填充，再将字符串每一个节点对应的值放进一个队列，根据队列实现反序列化！

代码：C++

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Codec {
11 public:
12 
13     // Encodes a tree to a single string.
14     string serialize(TreeNode* root) {
15         string str;
16         Myserialize(root,str);
17         return str;
18     }
19 
20     // Decodes your encoded data to tree.
21     TreeNode* deserialize(string data) {
22         queue<string> que;
23         string str;
24         for(auto const& c : data){
25             if(c == ','){
26                 que.push(str);
27                 str.clear();
28             } else {
29                 str += c;
30             }
31         }
32         return Mydeserialize(que);
33     }
34 private:
35     void Myserialize(TreeNode* root,string& str) {
36         if(root == NULL){
37             str += "NULL,";
38             return;
39         }
40         str += to_string(root->val) + ",";
41         Myserialize(root->left,str);
42         Myserialize(root->right,str);
43     }
44     TreeNode* Mydeserialize(queue<string>& que){
45         string cur = que.front();
46         que.pop();
47         if(cur == "NULL"){
48             return NULL;
49         }
50         TreeNode* node = new TreeNode(stoi(cur));
51         node->left = Mydeserialize(que);
52         node->right = Mydeserialize(que);
53         return node;
54     }
55 };
56 
57 // Your Codec object will be instantiated and called as such:
58 // Codec* ser = new Codec();
59 // Codec* deser = new Codec();
60 // string tree = ser->serialize(root);
61 // TreeNode* ans = deser->deserialize(tree);
62 // return ans;