算法题记录 16

2296.设计一个文本编辑器（1912）

请你设计一个带光标的文本编辑器，它可以实现以下功能：

添加：在光标所在处添加文本。
删除：在光标所在处删除文本（模拟键盘的删除键）。
移动：将光标往左或者往右移动。
当删除文本时，只有光标左边的字符会被删除。光标会留在文本内，也就是说任意时候 0 <= cursor.position <= currentText.length 都成立。

请你实现 TextEditor 类：

TextEditor() 用空文本初始化对象。
void addText(string text) 将 text 添加到光标所在位置。添加完后光标在 text 的右边。
int deleteText(int k) 删除光标左边 k 个字符。返回实际删除的字符数目。
string cursorLeft(int k) 将光标向左移动 k 次。返回移动后光标左边 min(10, len) 个字符，其中 len 是光标左边的字符数目。
string cursorRight(int k) 将光标向右移动 k 次。返回移动后光标左边 min(10, len) 个字符，其中 len 是光标左边的字符数目。

涉及知识点

栈

解决思路

秒答题，要实现的功能很简单，但是我们可以让整个算法变漂亮。采用两个栈，一个栈存光标左边的字符，一个栈存光标右边的字符，光标移动就是左边栈和右边栈左手倒右手，删除就是在左边栈出栈k个。

class TextEditor:
    def __init__(self):
        self.left = []  # 光标左侧字符
        self.right = []  # 光标右侧字符

    def addText(self, text: str) -> None:
        self.left.extend(text)  # 入栈

    def deleteText(self, k: int) -> int:
        pre = len(self.left)  # 删除之前的栈大小
        del self.left[-k:]  # 出栈
        return pre - len(self.left)  # 减去删除之后的栈大小

    def text(self) -> str:
        return ''.join(self.left[-10:])  # 光标左边至多 10 个字符

    def cursorLeft(self, k: int) -> str:
        while k and self.left:
            self.right.append(self.left.pop())  # 左手倒右手
            k -= 1
        return self.text()

    def cursorRight(self, k: int) -> str:
        while k and self.right:
            self.left.append(self.right.pop())  # 右手倒左手
            k -= 1
        return self.text()

798.得分最高的最小轮调（2130）

给你一个数组 nums，我们可以将它按一个非负整数 k 进行轮调，这样可以使数组变为 [nums[k], nums[k + 1], … nums[nums.length - 1], nums[0], nums[1], …, nums[k-1]] 的形式。此后，任何值小于或等于其索引的项都可以记作一分。

例如，数组为 nums = [2,4,1,3,0]，我们按 k = 2 进行轮调后，它将变成 [1,3,0,2,4]。这将记为 3 分，因为 1 > 0 [不计分]、3 > 1 [不计分]、0 <= 2 [计 1 分]、2 <= 3 [计 1 分]，4 <= 4 [计 1 分]。
在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调下标 k 。如果有多个答案，返回满足条件的最小的下标 k 。

涉及知识点

滑动窗口

解决思路

示例：nums=[2, 3, 1, 4, 0]
在nums后面拼上一个nums，构造出新的数组，下标index与值value对应关系如下：
0 1 2 3 4 5 6 7 8 9
2 3 1 4 0 2 3 1 4 0
题目要求每个轮调中value<=index的个数，而如上k=1时，所有index增加了1，实际上求value-(index-k)<=0的个数，即k<=index-value
只需存储index-value即可，利用SortedList对每个轮调排序，利用二分搜索计算大于等于k的个数即可

from sortedcontainers import *
class Solution:
    def bestRotation(self, nums: List[int]) -> int:
        n = len(nums)
        st = SortedList()

        res = -1
        pre = 0
        for i in range(2 * n - 1):
            st.add((i - nums[i % n]))
            if i >= n - 1:
                k = i - n + 1
                j = n - st.bisect_left(k)
                if j > pre:
                    res = k
                    pre = j
                st.remove(i - n + 1 - nums[i - n + 1])
        return res

858.镜面反射（1881）

有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为 0， 1，以及 2。

正方形房间的墙壁长度为 p，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 0 的距离为 q 。

返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。

涉及知识点

数学

解决思路

#将光线分解成垂直和水平两个速度,然后转化成p,q的最小公倍数
#如果垂直方向走的步数是偶数,答案是0
#如果垂直方向走的步数是奇数,答案是2或1,我们再计算水平方向走的步数,如果水平步数是奇数,答案是1,否则是2

class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        l=lcm(p,q)
        vertical=l//p
        if vertical&1:
            horizon=l//q
            if horizon&1:
                return 1
            else:
                return 2
        else:
            return 0

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。