Posts published in “Uncategorized”

花花酱 LeetCode 3508. Implement Router

By zxi on April 15, 2025

算是比较复杂的题目了，主要考察数据结构的选择和应用。

Note that queries for addPacket will be made in increasing order of timestamp.
把题目简化了不少，注意timestamp可能会想同，非严格单调递增。

forwardPacket 的 FIFO，需要deque或者list
getCount 特定key的范围查询，hashmap + vector / deque
addPacket 需要用hashtable 去重。还要remove最旧的packet，最后的选择落到的deque上。

deque两头可以添加/删除，还能random access做二分搜索，真是居家旅行必备之数据结构。

时间复杂度：addPacket: O(1)，forwardPacket：O(1)，getCount：O(logN) N为dst的packet数量。
空间复杂度：O(M)

class Router {

public:

Router(int memoryLimit): memoryLimit_{memoryLimit}, size_{0} {

}

bool addPacket(int source, int destination, int timestamp) {

if (!p_.insert(getKey(source, destination, timestamp)).second){

return false;

}

if (size_ == memoryLimit_) {

forwardPacket(); // remove the oldest.

}

packets_.emplace_back(source, destination, timestamp);

c_[destination].emplace_back(timestamp);

++size_;

return true;

}

vector<int> forwardPacket() {

if (size_ == 0) return {};

auto [src, dst, timestamp] = packets_.front();

packets_.pop_front();

--size_;

c_[dst].pop_front();

p_.erase(getKey(src, dst, timestamp));

return {src, dst, timestamp};

}

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

if (!c_.count(destination)) return 0;

const auto& q = c_[destination];

auto it1 = lower_bound(begin(q), end(q), startTime);

auto it2 = upper_bound(begin(q), end(q), endTime);

return it2 - it1;

}

private:

// https://zxi.mytechroad.com/blog/uncategorized/leetcode-3508-implement-router/

string getKey(int s, int d, int t) {

return to_string(s) + "_" + to_string(d) + "_" + to_string(t);

}

int memoryLimit_;

int size_;

unordered_set<string> p_; // {f'{src}_{dst}_{timestamp}'}

deque<tuple<int, int, int>> packets_; // {{src, dst, timestamp}}

unordered_map<int, deque<int>> c_; // {dst -> timestamp}

};

聊聊Switch2 | 价格 | Key Card | 二手

By zxi on April 6, 2025

Switch2终于发布了，游戏画面看着还不错，有点”次世代”的感觉了呢～

Switch 2真的贵吗？

几乎所有人都在吐槽价格。正所谓没有不好的产品，只有不好的定价。美版首发定价$449.99，如果对比Switch 2017年首发时$299.99定价，贵了足足有50%。但在美国的同学应该都能感受到这几年的通胀，很多商品的价格都涨了不止50%。考虑到Switch2的物料成本（去除通胀）肯定是要比Switch要高不少的，所以说这个价格看着有些抽象，但其实确实在合理范围里面。有人说这个价格都赶上PS5了，但老任可不会干亏本卖机器，靠游戏回血的勾当，而是我都要～个人觉得如果定在$399的话，大部分人应该都能接受了吧。

microSD Express

看了一眼价格256G $60，其实还可以。我两个月前买的128G UHS-I V30的卡也要30刀呢（现在怎么降到16刀了～）。机内的230G，买一张256G的卡，放个几十个数字版/Key Card的游戏应该问题不大，能满足绝大多数人的需求了。再说了，你买得起几十个游戏吗，就来吐槽存储卡贵？关于microSD Express only，其实没啥好说的，目前价格应还算合理，以后只会越来越便宜，换来更快的加载速度完全是值得的。

目前爆料的一些游戏容量：

Mario Kart World: 23.4 GB
Donkey Kong Bananza: 10 GB
Nintendo Classics: GameCube app: 3.5 GB
Super Mario Party Jamboree – Nintendo Switch 2 Edition ＋ Jamboree TV: 7.7 GB
Kirby and the Forgotten Land – Nintendo Switch 2 Edition ＋ Star Crossed World: 5.7 GB

Cyberpunk 2077 会使用64GB的卡带，而非Key-Card。每个实体版的游戏相当于一张小的SD存储卡了。

卡带 / Key Card

时至今日只有老任还在坚持使用卡带，对比与蓝光光碟，那种即插即玩的体验懂的都懂。代价是什么？高昂的制造成本。但是，这一切会被Key Card所终结吗？其实在Switch 1时代就有半Key Card的游戏，部分游戏放在8GB的卡带中（16/32GB的卡带在当时太贵了），剩下的部分需要下载。用这种方式降低发行成本，其实也是无可厚非的选择。由于Switch 2的机能提高了不少，贴图精度必然水涨船高，结果就是游戏容量暴增。虽然还不能和PC和PS5比，但已经达到卡带的极限了，Key Card的推出只能说被时代推着走。这么说来Swtich 1机能弱/游戏小还是某种优势咯（笑）。其实在Switch 1时代，我就想要比完整游戏版卡带便宜一些Key Card了/或者直接说是带包装盒的数字版下载码。对比卡带，游戏的包装盒对我而言的收藏的意义更大一些。这算是现代版的买椟还珠吗？

我的PS5实体游戏到现在还没拆封…

游戏价格｜二手｜氪金｜盗版

网友们接着吐槽游戏价格贵。实体版比数字版价格贵我觉得是合理的，毕竟多一个包装盒呢，游戏卡带算是附加送的（笑）。主要的是卡带/Key Card可以出二手。回血玩家们转手十来次，老任只收了一份的钱，不得哭晕在厕所啊。这时Intel/AMD/Nvida/Apple同时站出来说，没有人比我更懂转手几十次的垃圾佬。关于二手商品的流通对厂商的影响、以后会单独写一篇文章。

为什么大家会觉得现在的游戏贵？说贵的同学可以看看九十年代FC游戏的定价。就拿我最喜欢的《火焰之纹章-外传》来说，1992年在日本的发行价格为6800日元，就算不考虑通胀，当时的价格为现在汇率下的47刀，或者336人民币。92年，336人民币什么概念？可能要1个多月工资了。当时国内的FC卡带几乎都是盗版的，但毕竟成本摆在那里，在上海普遍的价格是100多人民币一盒，记得容量更大的《吞食天地 – 诸葛孔明传》更是要价250元。当时买游戏卡绝对是一件奢侈的事情，过年的时候拿着压岁钱咬牙买了一盒《松鼠大战2》，记得好像是125元，那是95年前后吧。有时侯也会和街坊邻居/同学交换游戏卡玩，也算是某种形式的回血了。

九十年代后期，那时候兴起了多媒体电脑热，1万元左右的价格咬咬牙还是买得起的，家里有台电脑还倍有面子，所以游戏也渐渐转移到PC上面（毕竟当时个人拥有SFC/PS/SS的是少数）。游戏的载体也变成CD，当然绝大多数都是盗版的，起初价格还要15元，后来10元，最后慢慢稳定到5元一张碟。游戏玩家快速成长，再也没有人觉得游戏贵了。

再后来到了2002年前后，宽带开始普及，游戏也从购买CD变成了网上下载，当然还是盗版的，但获取单机游戏的边际成本趋近于0。

当时很多网游都是要充点卡的，还是有些小贵。当然比起拨号+点卡时代已经便宜很多了。我玩《石器时代》拨号费可能都花了几千块钱…

再后来氪金网游/手游开始大行其道，从此开启了正版游戏也能免费玩的时代。

但不管在什么年代，正版的单机大作卖的一直不便宜，只是提及的人比较少，或者说其受众多说能够接受这个定价，吐糟的大多都是伸手党。

说了这么多，不是想给老任/Sony开脱，虽然开发工具/生产力大幅提升了，但现代游戏开发成本和当年比起来是高了一个数量级都不止，要不是游戏玩家变多了平摊掉不少成本，不然游戏价格还会更贵。

虽然游戏的定价对于发展中国家来说还是比较贵的，不锁区没办法，但对于美国玩家来说，大作$80刀，1天的工资都不到，你觉得这个价格还贵吗？

对于一些人来说，缺少的哪里是那80刀，而是玩游戏的时间和热情。

Switch 2 我还是会买的（但可能要等到减肥成功之后）手持1080p 60绝对是足够了。

我更愿意以合理的价格玩到优秀的游戏，而不愿用便宜的价格玩粗制滥造的玩意儿。

感觉这次Switch 2可能会撑10年，希望是我预测错了～

以上，

花花

花花酱 LeetCode 2974. Minimum Number Game

By zxi on January 8, 2024

You are given a 0-indexed integer array nums of even length and there is also an empty array arr. Alice and Bob decided to play a game where in every round Alice and Bob will do one move. The rules of the game are as follows:

Every round, first Alice will remove the minimum element from nums, and then Bob does the same.
Now, first Bob will append the removed element in the array arr, and then Alice does the same.
The game continues until nums becomes empty.

Return the resulting array arr.

Example 1:

Input: nums = [5,4,2,3]
Output: [3,2,5,4]
Explanation: In round one, first Alice removes 2 and then Bob removes 3. Then in arr firstly Bob appends 3 and then Alice appends 2. So arr = [3,2].
At the begining of round two, nums = [5,4]. Now, first Alice removes 4 and then Bob removes 5. Then both append in arr which becomes [3,2,5,4].

Example 2:

Input: nums = [2,5]
Output: [5,2]
Explanation: In round one, first Alice removes 2 and then Bob removes 5. Then in arr firstly Bob appends and then Alice appends. So arr = [5,2].

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100
nums.length % 2 == 0

Solution: Sort and Swap

Sort the array first and then swap the adjacent elements.

Time complexity: O(nlogn)
Space complexity: O(1)

C++

class Solution {

public:

vector<int> numberGame(vector<int>& nums) {

sort(begin(nums), end(nums));

for (int i = 0; i < nums.size(); i += 2)

swap(nums[i], nums[i + 1]);

return nums;

}

};

花花酱 LeetCode 2918. Minimum Equal Sum of Two Arrays After Replacing Zeros

By zxi on October 29, 2023

You are given two arrays nums1 and nums2 consisting of positive integers.

You have to replace all the 0‘s in both arrays with strictly positive integers such that the sum of elements of both arrays becomes equal.

Return the minimum equal sum you can obtain, or -1 if it is impossible.

Example 1:

Input: nums1 = [3,2,0,1,0], nums2 = [6,5,0]
Output: 12
Explanation: We can replace 0's in the following way:
- Replace the two 0's in nums1 with the values 2 and 4. The resulting array is nums1 = [3,2,2,1,4].
- Replace the 0 in nums2 with the value 1. The resulting array is nums2 = [6,5,1].
Both arrays have an equal sum of 12. It can be shown that it is the minimum sum we can obtain.

Example 2:

Input: nums1 = [2,0,2,0], nums2 = [1,4]
Output: -1
Explanation: It is impossible to make the sum of both arrays equal.

Constraints:

1 <= nums1.length, nums2.length <= 10⁵
0 <= nums1[i], nums2[i] <= 10⁶

Solution: A few cases

Calculate the sum of number of zeros of each array as (s1, z1), (s2, z2). There are a few cases:

z1 == z2 == 0, there is no way to change, just check s1 == s2.
z1 == 0, z1 != 0 or z2 == 0, z1 != 0. Need to at least increase the sum by number of zeros, check s1 + z1 <= s2 / s2 + z2 <= s1
z1 != 0, z2 != 0, the min sum is max(s1 + z1, s2 + z2)

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

long long minSum(vector<int>& nums1, vector<int>& nums2) {

auto getSumAndZeros = [](const vector<int>& nums) {

long long sum = 0;

long long zeros = 0;

for (int x : nums) {

sum += x;

zeros += x == 0;

}

return pair{sum, zeros};

};

auto [s1, z1] = getSumAndZeros(nums1);

auto [s2, z2] = getSumAndZeros(nums2);

if (z1 == 0 && z2 == 0) {

return s1 == s2 ? s1 : -1;

} else if (z1 == 0) {

return s2 + z2 <= s1 ? s1 : -1;

} else if (z2 == 0) {

return s1 + z1 <= s2 ? s2 : -1;

} else {

return max(s1 + z1, s2 + z2);

}

return -1;

}

};

花花酱 LeetCode 2917. Find the K-or of an Array

By zxi on October 29, 2023

You are given a 0-indexed integer array nums, and an integer k.

The K-or of nums is a non-negative integer that satisfies the following:

The i^th bit is set in the K-or if and only if there are at least k elements of nums in which bit i is set.

Return the K-or of nums.

Note that a bit i is set in x if (2ⁱ AND x) == 2ⁱ, where AND is the bitwise AND operator.

Example 1:

Input: nums = [7,12,9,8,9,15], k = 4
Output: 9
Explanation: Bit 0 is set at nums[0], nums[2], nums[4], and nums[5].
Bit 1 is set at nums[0], and nums[5].
Bit 2 is set at nums[0], nums[1], and nums[5].
Bit 3 is set at nums[1], nums[2], nums[3], nums[4], and nums[5].
Only bits 0 and 3 are set in at least k elements of the array, and bits i >= 4 are not set in any of the array's elements. Hence, the answer is 2^0 + 2^3 = 9.

Example 2:

Input: nums = [2,12,1,11,4,5], k = 6
Output: 0
Explanation: Since k == 6 == nums.length, the 6-or of the array is equal to the bitwise AND of all its elements. Hence, the answer is 2 AND 12 AND 1 AND 11 AND 4 AND 5 = 0.

Example 3:

Input: nums = [10,8,5,9,11,6,8], k = 1
Output: 15
Explanation: Since k == 1, the 1-or of the array is equal to the bitwise OR of all its elements. Hence, the answer is 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15.

Constraints:

1 <= nums.length <= 50
0 <= nums[i] < 2³¹
1 <= k <= nums.length

Solution: Bit Operation

Enumerate every bit and enumerate every number.

Time complexity: O(31 * n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findKOr(vector<int>& nums, int k) {

int ans = 0;

for (int i = 0; i < 31; ++i) {

int count = 0;

for (int x : nums)

if (x >> i & 1) ++count;

if (count >= k) ans |= 1 << i;

}

return ans;

}

};

Posts published in “Uncategorized”

花花酱 LeetCode 3508. Implement Router

聊聊Switch2 | 价格 | Key Card | 二手

Switch 2真的贵吗？

microSD Express

卡带 / Key Card

游戏价格 ｜二手 ｜ 氪金 ｜盗版

花花酱 LeetCode 2974. Minimum Number Game

Solution: Sort and Swap

C++

花花酱 LeetCode 2918. Minimum Equal Sum of Two Arrays After Replacing Zeros

Solution: A few cases

C++

花花酱 LeetCode 2917. Find the K-or of an Array

Solution: Bit Operation

C++

游戏价格｜二手｜氪金｜盗版