Posts tagged as “list”

花花酱 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 2130. Maximum Twin Sum of a Linked List

By zxi on January 9, 2022

In a linked list of size n, where n is even, the i^th node (0-indexed) of the linked list is known as the twin of the (n-1-i)^th node, if 0 <= i <= (n / 2) - 1.

For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Example 1:

Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.

Example 2:

Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:
- Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
- Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
Thus, the maximum twin sum of the linked list is max(7, 4) = 7.

Example 3:

Input: head = [1,100000]
Output: 100001
Explanation:
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

Constraints:

The number of nodes in the list is an even integer in the range [2, 10⁵].
1 <= Node.val <= 10⁵

Solution: Two Pointers + Reverse List

Use fast slow pointers to find the middle point and reverse the second half.

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

C++

// Author: Huahua

class Solution {

public:

int pairSum(ListNode* head) {

auto reverse = [](ListNode* head, ListNode* prev = nullptr) {

while (head) {

swap(head->next, prev);

swap(head, prev);

}

return prev;

};

ListNode* fast = head;

ListNode* slow = head;

while (fast) {

fast = fast->next->next;

slow = slow->next;

}

slow = reverse(slow);

int ans = 0;

while (slow) {

ans = max(ans, head->val + slow->val);

head = head->next;

slow = slow->next;

}

return ans;

}

};

Posts tagged as “list”

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

花花酱 LeetCode 2296 Design a Text Editor

花花酱 LeetCode 2181. Merge Nodes in Between Zeros

Solution: List

C++

花花酱 LeetCode 2130. Maximum Twin Sum of a Linked List

Solution: Two Pointers + Reverse List

C++

花花酱 LeetCode 2095. Delete the Middle Node of a Linked List

Solution: Fast / Slow pointers

C++