Huahua’s Tech Road

花花酱 LeetCode 368. Largest Divisible Subset

By zxi on April 4, 2025

也算是一道比较经典的DP题了，需要找到一个最大的子集，使得其中元素两两的余数为0。

我们假设有一个集合为{a1, a2, a3, …, an}, {a1 < a2 < … < an)

如果 a2 % a1 = 0, a3 % a2 == 0, 那么a3 % a1 一定也等于0。也就是说a2是a1的倍数，a3是a2的倍数，那么a3一定也是a1的倍数。所以我们并不需要测试任意两个元素之间的余数为0，我们只需要检测a[i]是否为a[i-1]的倍数即可，如果成立，则可以确保a[i]也是a[i-2], a[i-3], … a[1]的倍数。这样就可以大大降低问题的复杂度。

接下来就需要dp就发挥威力了。我们将原数组排序，用dp[i]来表示以a[i]结尾（集合中的最大值），能够构建的子集的最大长度。

转移方程：dp[j] = max(dp[j], dp[i] + 1) if nums[j] % nums[i] = 0.

这表示，如果nums[j] 是 nums[i]的倍数，那么我们可以把nums[j]加入以nums[i]结尾的最大子集中，构建一个新的最大子集，长度+1。当然对于j，可能有好多个满足条件的i，我们需要找一个最大的。

举个例子：
nums = {2, 3, 4, 12}
以3结尾的最大子集{3}，长度为1。由于12%3==0，那么我们可以把12追加到{3} 中，构成{3,12}。
以4结尾的最大子集是{2,4}，长度为2。由于12%4==0，那么我们可以把12追加到{2,4} 中，构成{2,4,12} 。得到最优解。

这样我们只需要双重循环，枚举i，再枚举j (0 <= i < j)。时间复杂度：O(n^2)。空间复杂度：O(n)。

最后需要输出一个最大子集，如果不记录递推过程，则需要稍微判断一下。

class Solution {

public:

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

const int n = nums.size();

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

// dp[i] = max size of subset ends with nums[i]

vector<int> dp(n);

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

if (nums[j] % nums[i] == 0)

dp[j] = max(dp[j], dp[i] + 1);

int s = *max_element(begin(dp), end(dp));

vector<int> ans;

for (int i = n - 1; i >= 0; --i) {

if (dp[i] == s && (ans.empty() || ans.back() % nums[i] == 0)) {

ans.push_back(nums[i]);

--s;

}

return ans;

}

};

花花酱 LeetCode 2296 Design a Text Editor

By zxi on April 2, 2025

方法1：双向链表来存储文本，迭代器指向光标所在的位置。加一个dummy head会使代码简单很多。

时间复杂度：TextEditor O(1) addText O(|text|) deleteText O(k) cursorLeft O(k) cursorRight(k)
空间复杂度：O(n)

由于每个字符需要创建一个节点（17+个字节），虽然没有超时，但实际工程中是不能使用这种方式的。

// https://zxi.mytechroad.com/blog/string/leetcode-2296-design-a-text-editor/

class TextEditor {

public:

TextEditor(): data_{'$'}, cursor_{begin(data_)} {}

void addText(string text) {

for (char c : text)

cursor_ = data_.insert(++cursor_, c);

}

int deleteText(int k) {

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

if (cursor_ == begin(data_)) return i;

data_.erase(cursor_--);

}

return k;

}

string cursorLeft(int k) {

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

if (cursor_ == begin(data_)) break;

cursor_--;

}

return getText();

}

string cursorRight(int k) {

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

if (cursor_ == prev(end(data_))) break;

cursor_++;

}

return getText();

}

private:

string getText() {

string ans;

auto it = cursor_;

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

if (it == begin(data_)) break;

ans += *it--;

}

reverse(begin(ans), end(ans));

return ans;

}

list<char> data_;

list<char>::iterator cursor_;

};

方法2: 用两个string来代表光标左边的字符串和光标右边的字符串。注：右边字符串是反转的。

左右两边的字符串只会增长（或者覆盖），不会缩短，这是用空间换时间。

删除的时候就是修改了长度而已，并没有缩短字符串，所以是O(1)的。
如果缩短的话需则要O(k)时间，还要加上内存释放/再分配的时间，应该会慢一些但不多。

移动光标的时候，就是把左边字符串的最后k个copy到右边的最后面，或者反过来。同样没有缩短，只会变长。

时间复杂度: TextEditor O(1) addText O(|text|) deleteText O(1) cursorLeft O(k) cursorRight(k)
空间复杂度：O(n)，n为构建的最长的字符串

// https://zxi.mytechroad.com/blog/string/leetcode-2296-design-a-text-editor/

class TextEditor {

public:

TextEditor() {}

void addText(string_view text) {

ensureSize(l, m + text.size());

copy(begin(text), end(text), begin(l) + m);

m += text.size();

}

int deleteText(int k) {

k = min(k, m);

m -= k;

return k;

}

string cursorLeft(int k) {

ensureSize(r, n + k);

for (k = min(k, m); k > 0; --k)

r[n++] = l[--m];

return getText();

}

string cursorRight(int k) {

ensureSize(l, m + k);

for (k = min(k, n); k > 0; --k)

l[m++] = r[--n];

return getText();

}

private:

inline void ensureSize(string& s, int size) {

if (s.size() < size)

s.resize(size);

}

string getText() const {

return string(begin(l) + m - min(m, 10), begin(l) + m);

}

string l;

string r;

int m = 0;

int n = 0;

};

花花酱 LeetCode 3498 Reverse Degree of a String

By zxi on March 30, 2025

送分题，简单仿真即可。

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

// https://zxi.mytechroad.com/blog/string/leetcode-3498-reverse-degree-of-a-string/

class Solution {

public:

int reverseDegree(string s) {

int ans = 0;

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

ans += ('z' - s[i] + 1) * (i + 1);

return ans;

}

};

花花酱 LeetCode 2349. Design a Number Container System

By zxi on March 30, 2025

两个hashtable，一个是index->number，另外一个是number -> {index}，使用treeset，自动排序。

时间复杂度：change O(logn)，find O(1)
空间复杂度：O(n)

class NumberContainers {

public:

NumberContainers() {}

void change(int index, int number) {

if (m_.count(index)) {

auto it = idx_.find(m_[index]);

it->second.erase(index);

if (it->second.empty())

idx_.erase(it);

}

m_[index] = number;

idx_[number].insert(index);

}

int find(int number) {

auto it = idx_.find(number);

if (it == end(idx_)) return -1;

return *begin(it->second);

}

private:

unordered_map<int, int> m_; // index -> num

unordered_map<int, set<int>> idx_; // num -> {index}

};

Huahua's Tech Road

花花酱 LeetCode 430. Flatten a Multilevel Doubly Linked List

花花酱 LeetCode 368. Largest Divisible Subset

花花酱 LeetCode 2296 Design a Text Editor

花花酱 LeetCode 3498 Reverse Degree of a String

花花酱 LeetCode 2349. Design a Number Container System