力扣第444场周赛

这次力扣周赛对我来说难度确实大, 只做出两题, 但还是想分享一下的做题经验和感受 

1. 移除最小数对使数组有序 I

题目链接：力扣

给你一个数组 nums，你可以执行以下操作任意次数：

• 选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。
• 用它们的和替换这对元素。

返回将数组变为 非递减 所需的 最小操作次数 。

如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。

 

示例 1：

输入： nums = [5,2,3,1]

输出： 2

解释：

• 元素对 (3,1) 的和最小，为 4。替换后 nums = [5,2,4]。
• 元素对 (2,4) 的和为 6。替换后 nums = [5,6]。

数组 nums 在两次操作后变为非递减。

示例 2：

输入： nums = [1,2,2]

输出： 0

解释：

数组 nums 已经是非递减的。

 

提示：

• 1 <= nums.length <= 50
• -1000 <= nums[i] <= 1000

解题思路：按题目进行模拟就行, 第一题一般不会卡你时间复杂度的, 找到相邻和最小, 然后用相邻和去替换这个数对

class Solution {
public:bool judge(vector<int>& arr){for(int i=1;i<arr.size();i++){if(arr[i-1]>arr[i]){return false;}}return true;}void solve(vector<int>& nums){int index=-1; int maxNum=INT_MAX;for(int i=1;i<nums.size();i++){if(nums[i]+nums[i-1]<maxNum){maxNum=nums[i]+nums[i-1];index=i;// cout<<index<<endl;}}vector<int>::iterator a=nums.begin()+index; nums[index-1]=maxNum;// cout<<nums[index-1];nums.erase(a);}void print(vector<int>& nums){for(int i=0;i<nums.size();i++){cout<<nums[i];}cout<<endl;}int minimumPairRemoval(vector<int>& nums) {int count=0;while(!judge(nums)){// cout<<count<<endl;solve(nums);// print(nums);count++;}return count;}
};

2.设计路由器 

题目链接：力扣 

 

请你设计一个数据结构来高效管理网络路由器中的数据包。每个数据包包含以下属性：

• source：生成该数据包的机器的唯一标识符。
• destination：目标机器的唯一标识符。
• timestamp：该数据包到达路由器的时间戳。

实现 Router 类：

Router(int memoryLimit)：初始化路由器对象，并设置固定的内存限制。

• memoryLimit 是路由器在任意时间点可以存储的 最大 数据包数量。
• 如果添加一个新数据包会超过这个限制，则必须移除 最旧的 数据包以腾出空间。

bool addPacket(int source, int destination, int timestamp)：将具有给定属性的数据包添加到路由器。

• 如果路由器中已经存在一个具有相同 source、destination 和 timestamp 的数据包，则视为重复数据包。
• 如果数据包成功添加（即不是重复数据包），返回 true；否则返回 false。

int[] forwardPacket()：以 FIFO（先进先出）顺序转发下一个数据包。

• 从存储中移除该数据包。
• 以数组 [source, destination, timestamp] 的形式返回该数据包。
• 如果没有数据包可以转发，则返回空数组。

int getCount(int destination, int startTime, int endTime)：

• 返回当前存储在路由器中（即尚未转发）的，且目标地址为指定 destination 且时间戳在范围 [startTime, endTime]（包括两端）内的数据包数量。

注意：对于 addPacket 的查询会按照 timestamp 的递增顺序进行。

 

示例 1：

输入：
["Router", "addPacket", "addPacket", "addPacket", "addPacket", "addPacket", "forwardPacket", "addPacket", "getCount"]
[[3], [1, 4, 90], [2, 5, 90], [1, 4, 90], [3, 5, 95], [4, 5, 105], [], [5, 2, 110], [5, 100, 110]]

输出：
[null, true, true, false, true, true, [2, 5, 90], true, 1]

解释：

Router router = new Router(3); // 初始化路由器，内存限制为 3。
router.addPacket(1, 4, 90); // 数据包被添加，返回 True。
router.addPacket(2, 5, 90); // 数据包被添加，返回 True。
router.addPacket(1, 4, 90); // 这是一个重复数据包，返回 False。
router.addPacket(3, 5, 95); // 数据包被添加，返回 True。
router.addPacket(4, 5, 105); // 数据包被添加，[1, 4, 90] 被移除，因为数据包数量超过限制，返回 True。
router.forwardPacket(); // 转发数据包 [2, 5, 90] 并将其从路由器中移除。
router.addPacket(5, 2, 110); // 数据包被添加，返回 True。
router.getCount(5, 100, 110); // 唯一目标地址为 5 且时间在 [100, 110] 范围内的数据包是 [4, 5, 105]，返回 1。

示例 2：

输入：
["Router", "addPacket", "forwardPacket", "forwardPacket"]
[[2], [7, 4, 90], [], []]

输出：
[null, true, [7, 4, 90], []]

解释：

Router router = new Router(2); // 初始化路由器，内存限制为 2。
router.addPacket(7, 4, 90); // 返回 True。
router.forwardPacket(); // 返回 [7, 4, 90]。
router.forwardPacket(); // 没有数据包可以转发，返回 []。

 

提示：

• 2 <= memoryLimit <= 105
• 1 <= source, destination <= 2 * 105
• 1 <= timestamp <= 109
• 1 <= startTime <= endTime <= 109
• addPacket、forwardPacket 和 getCount 方法的总调用次数最多为 105。
• 对于 addPacket 的查询，timestamp 按递增顺序给出。

解题思路:   forwardPacket()方法要求先进先出, 就写个队列, addPacket()方法就用set去维护, 当你insert一个[source、destination 和 timestamp]相同的元素时候,insert插入失败（insert的返回值是pair<iterator, bool> p）取出p.second的false即可，getCount()方法返回指定 destination, 时间戳范围 [startTime, endTime]（包括两端）内的数据包数量. 怎么实现呢？用一个邻接表即可,  key: destination, value: timestamp

class Router {
public:int memory_limit;set<tuple<int,int,int>> p_set;queue<tuple<int,int,int>> p_que;unordered_map<int, pair<vector<int>, int>> dest_to_timestamps;   //destination -> [[timestamp], head]Router(int memoryLimit) {this->memory_limit=memoryLimit;}bool addPacket(int source, int destination, int timestamp) {auto p=make_tuple(source,destination,timestamp);if(!p_set.insert(p).second){return false;}//重复包if(p_que.size()==memory_limit){// return false;forwardPacket();}//包超了p_que.push(p);dest_to_timestamps[destination].first.push_back(timestamp);return true;}vector<int> forwardPacket() {if(p_que.empty()){return {};}auto p=p_que.front();p_que.pop();p_set.erase(p);auto [source, destination, timestamp] = p;dest_to_timestamps[destination].second++;return {source, destination, timestamp};}int getCount(int destination, int startTime, int endTime) {auto& [timestamps, head] = dest_to_timestamps[destination];auto left = lower_bound(timestamps.begin() + head, timestamps.end(), startTime);auto right = upper_bound(timestamps.begin() + head, timestamps.end(), endTime);return right - left;}
};
// 0 1 2 3 4
// 2 4
// 4-2=2
// [2,3]=2
/*** Your Router object will be instantiated and called as such:* Router* obj = new Router(memoryLimit);* bool param_1 = obj->addPacket(source,destination,timestamp);* vector<int> param_2 = obj->forwardPacket();* int param_3 = obj->getCount(destination,startTime,endTime);*/

3.最大化交错和为 K 的子序列乘积 

题目链接：力扣 

给你一个整数数组 nums 和两个整数 k 与 limit，你的任务是找到一个非空的 子序列，满足以下条件：

• 它的 交错和 等于 k。
• 在乘积 不超过 limit 的前提下，最大化 其所有数字的乘积。

返回满足条件的子序列的 乘积 。如果不存在这样的子序列，则返回 -1。

子序列 是指可以通过删除原数组中的某些（或不删除）元素并保持剩余元素顺序得到的新数组。

交错和 是指一个 从下标 0 开始 的数组中，偶数下标 的元素之和减去 奇数下标 的元素之和。

 

示例 1：

输入： nums = [1,2,3], k = 2, limit = 10

输出： 6

解释：

交错和为 2 的子序列有：

• [1, 2, 3]
  • 交错和：1 - 2 + 3 = 2
  • 乘积：1 * 2 * 3 = 6
• [2]
  • 交错和：2
  • 乘积：2

在 limit 内的最大乘积是 6。

示例 2：

输入： nums = [0,2,3], k = -5, limit = 12

输出： -1

解释：

不存在交错和恰好为 -5 的子序列。

示例 3：

输入： nums = [2,2,3,3], k = 0, limit = 9

输出： 9

解释：

交错和为 0 的子序列包括：

• [2, 2]
  • 交错和：2 - 2 = 0
  • 乘积：2 * 2 = 4
• [3, 3]
  • 交错和：3 - 3 = 0
  • 乘积：3 * 3 = 9
• [2, 2, 3, 3]
  • 交错和：2 - 2 + 3 - 3 = 0
  • 乘积：2 * 2 * 3 * 3 = 36

子序列 [2, 2, 3, 3] 虽然交错和为 k 且乘积最大，但 36 > 9，超出 limit 。下一个最大且在 limit 范围内的乘积是 9。

 

提示：

• 1 <= nums.length <= 150
• 0 <= nums[i] <= 12
• -105 <= k <= 105
• 1 <= limit <= 5000

代码思路： 我最初用的是, 选或不选的思路, 根据题意, 我们可能需要维护交错和要等于k, 乘积不能超过limit, 还要维护当前子序列长度是奇数还是偶数。每个交错和下, 都保存着最大的乘积。但是，477 / 664 个通过的测试用例。

class Solution {
public:int maxProduct(vector<int>& nums, int k, int limit) {unordered_map<int,int> a;unordered_map<int,int> b;a[0]=1;for(int num:nums){unordered_map<int,int> new_a,new_b;for(auto& [x,y]:a){if(new_a.count(x)==0||y>new_a[x]){new_a[x]=y;}}for(auto& [x,y]:b){if(new_b.count(x)==0||y>new_b[x]){new_b[x]=y;}}for(auto& [x,y]:a){int new_x=x+num;int new_y=y*num;if(new_y<=limit){if(new_a.count(new_x)==0||new_y>new_b[new_x]){new_b[new_x]=new_y;}}}for(auto& [x,y]:b){int new_x=x-num;int new_y=y*num;if(new_x<=limit){if(new_a.count(new_x)==0||new_y>new_a[new_x]){new_a[new_x]=new_y;}}}int only_x=num;int only_y=num;if(only_x<=limit){if(new_b.count(only_x)==0){new_b[only_x]=num;}}a=move(new_a);b=move(new_b);}int maxNum=-1;if(a.count(k)){maxNum=max(maxNum,a[k]);}if(b.count(k)){maxNum=max(maxNum,b[k]);}return maxNum>0?maxNum:-1;}
};

但是其实本题是可以直接进行暴力搜索的, 详细解释如下：

 3509. 最大化交错和为 K 的子序列乘积 - 力扣（LeetCode）

我解释一下, 你在阅读中可能遇到的疑问：

1. 在本题的数据范围下，L≤12 

注：2^12=4096<5000， 选2最多选12个，同理最多选7个3, 对1是的选择是没有限制的

2. 在两个大于 1 的数之间的连续的 1，其交错和 1−1+1−1+⋯ 的绝对值 ≤1。所以子序列中的所有 1 的交错和的绝对值 ≤L+1

注：

1 的影响：

如果有一堆 1，比如 1 -1 +1 -1...，总和要么是 0，要么是 1 或 -1（来回摇摆）。

所以 1 不会让总和变得特别大。

但是在一个序列中可能有L个大于1的数, L个数将序列分成L+1个只包含1的小块儿

eg: [1, 1, 2, 1, 3, 1, 1]

每一段的最大贡献为1, L+1段自然最多贡献L+1

3. 如果大于 1 的数都是 2，交错和的绝对值 ≤2L+(L+1)=3L+1≤37

注：如果选了 L 个 2，最坏情况是 +2 -2 +2 -2...，总和最大是 2L（比如 2 + 2 + 2...）

1*L*2=2*L

所以,  由于“较大的数”的数量有限，且乘积不能太大，实际有效的“乘积”状态非常少。

3. 定义dfs(i,s,m,odd,empty)

参数：x=nums[i]选还是不选, s: 当前子序列的交错和, m: 子序列的元素乘积

odd: 如果选x, 减x/加x empty: 子序列是否为空

递归入口：dfs(0,0,1,false,true)

 代码如下：

class Solution {
public:int maxProduct(vector<int>& nums, int k, int limit) {int total = reduce(nums.begin(), nums.end());if (total < abs(k)) { return -1;}int n = nums.size(), ans = -1;unordered_set<long long> vis;dfs(0, 0, 1, false, true, nums, k, limit, n, total, ans, vis);return ans;}private:void dfs(int i, int s, int m, bool odd, bool empty, const vector<int>& nums, int k, int limit, int n, int total, int& ans,unordered_set<long long>& vis) {if (ans == limit) {return;}if (i == n) {if (!empty && s == k && m <= limit) { ans = max(ans, m);}return;}long long mask = (long long) i << 32 | (s + total) << 14 | m << 2 | odd << 1 | empty;if (!vis.insert(mask).second) {return;}dfs(i + 1, s, m, odd, empty, nums, k, limit, n, total, ans, vis);int x = nums[i];dfs(i + 1, s + (odd ? -x : x), min(m * x, limit + 1), !odd, false, nums, k, limit, n, total, ans, vis);}
};

水平有限, 有疑问可以发布到评论区, 感谢！