Huahua’s Tech Road

花花酱 LeetCode 3517. Smallest Palindromic Rearrangement I

By zxi on April 16, 2025

这题考查的是排序吧… 还有rbegin的使用。

普通排序：时间 O(nlogn) / 空间 O(1)

前半部分顺序排序，后半部分逆序排序。

class Solution {

public:

string smallestPalindrome(string s) {

const int n = s.length();

sort(begin(s), begin(s) + n / 2);

sort(rbegin(s), rbegin(s) + n / 2);

return s;

}

};

计数排序：时间：O(n)，空间：O(n) -> O(1)

首尾一起写

// 7 ms, 54.65MB

class Solution {

public:

string smallestPalindrome(string s) {

vector<int> f(128);

for (size_t i = 0; i < s.size() / 2; ++i)

++f[s[i]];

auto h=begin(s);

auto t=rbegin(s);

for (char c = 'a'; c <= 'z'; ++c)

while (f[c]--)

*h++ = *t++ = c;

return s;

}

};

花花酱 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}

};

LeetCode 3512. Minimum Operations to Make Array Sum Divisible by K

By zxi on April 15, 2025

求合取余即可，余数就是答案。

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

class Solution {

public:

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

return accumulate(begin(nums), end(nums), 0) % k;

}

};

花花酱 LeetCode 2161. Partition Array According to Given Pivot

By zxi on April 12, 2025

最直接的方法就是扫描三遍，<, = , > pivot。

时间复杂度：O(n)
空间复杂度：O(1) // no extra space used except for output

class Solution {

public:

vector<int> pivotArray(vector<int>& nums, int pivot) {

vector<int> ans;

for (int x: nums)

if (x < pivot) ans.push_back(x);

for (int x : nums)

if (x == pivot) ans.push_back(x);

for (int x : nums)

if (x > pivot) ans.push_back(x);

return ans;

}

};

花花酱 LeetCode 2024. Maximize the Confusion of an Exam

By zxi on April 12, 2025

数据规模高达5 *10⁴,我们只能使用O(n)的算法了。

可以想到的就是滑动窗口(sliding window)，由于最长长度未知，我们可以使用动态滑动窗口。

记录当前滑动窗口中T和F出现的次数，如果其中较少的一个<=k，那么就可以全部替换它，使得整个滑动窗口都变成相同的值。如果这个时候滑动窗口长度大于当前最大长度，我们就把滑动窗口变大，右侧+1，并更新最大长度。否则，减少滑动窗口，左侧-1。

时间复杂度：O(n)
空间复杂度：O(2)

class Solution {

public:

int maxConsecutiveAnswers(string_view A, int k) {

int ans = 0;

int f = 0;

array<int, 2> count; // number of 'F' and 'T' in the sliding window

for (int i = 0; i < A.size(); ++i) {

++count[A[i] == 'T'];

if (min(count[0], count[1]) <= k && count[0] + count[1] > ans)

++ans;

else

--count[A[i - ans] == 'T'];

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 3517. Smallest Palindromic Rearrangement I

花花酱 LeetCode 3508. Implement Router

LeetCode 3512. Minimum Operations to Make Array Sum Divisible by K

花花酱 LeetCode 2161. Partition Array According to Given Pivot

花花酱 LeetCode 2024. Maximize the Confusion of an Exam