LeetCode 每日一题

446.统计重复个数

问题

定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。

例如，str == ["abc", 3] =="abcabcabc" 。
如果可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。

例如，根据定义，s1 = "abc" 可以从 s2 = "abdbec" 获得，仅需要删除加粗且用斜体标识的字符。
现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = [s1, n1]、str2 = [s2, n2] 。

请你找出一个最大整数 m ，以满足 str = [str2, m] 可以从 str1 获得。

解答

由小到大，寻找循环节，此后每逢循环节必包含

代码：

拓展

依据灵神的网站题目顺序

2734. 执行子串操作后的字典序最小字符串

问题

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：

选择 s 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，'b' 用 'a' 替换，'a' 用 'z' 替换。
返回执行上述操作恰好一次后可以获得的字典序最小的字符串。

子字符串是字符串中的一个连续字符序列。

现有长度相同的两个字符串 x 和字符串 y ，在满足 x[i] != y[i] 的第一个位置 i 上，如果 x[i] 在字母表中先于 y[i] 出现，则认为字符串 x 比字符串 y 字典序更小。

解答

显然 a 最小，则遇 a 就停

代码：

char * smallestString(char * s){
    char *tmp = s;
    while (*tmp && *tmp == 'a') {
        tmp++;
    }
    if (!*tmp) *(tmp - 1) = 'z';
    while (*tmp && *tmp != 'a') {
        (*tmp)--;
        tmp++;
    }
    return s;
}

1410. HTML 实体解析器

问题

「HTML 实体解析器」是一种特殊的解析器，它将 HTML 代码作为输入，并用字符本身替换掉所有这些特殊的字符实体。

HTML 里这些特殊字符和它们对应的字符实体包括：

双引号：字符实体为 " ，对应的字符是 " 。
单引号：字符实体为 ' ，对应的字符是 ' 。
与符号：字符实体为 & ，对应对的字符是 & 。
大于号：字符实体为 > ，对应的字符是 > 。
小于号：字符实体为 < ，对应的字符是 < 。
斜线号：字符实体为 ⁄ ，对应的字符是 / 。
给你输入字符串 text ，请你实现一个 HTML 实体解析器，返回解析器解析后的结果。

解答

一次遍历即可得到答案

代码：

class Solution:
    def entityParser(self, text: str) -> str:
        entityMap = {
            '&quot;': '"',
            '&apos;': "'",
            '&gt;': '>',
            '&lt;': '<',
            '&frasl;': '/',
            '&amp;': '&',
        }

        i = 0
        n = len(text)
        res = []
        while i < n:
            isEntity = False
            if text[i] == '&':
                for e in entityMap:
                    if text[i:i + len(e)] == e:
                        res.append(entityMap[e])
                        isEntity = True
                        i += len(e)
                        break
            if not isEntity:
                res.append(text[i])
                i += 1
        return ''.join(res)

拓展

2451. 差值数组不同的字符串

问题

给你一个字符串数组 words ，每一个字符串长度都相同，令所有字符串的长度都为 n 。

每个字符串 words[i] 可以被转化为一个长度为 n - 1 的差值整数数组 difference[i] ，其中对于 0 <= j <= n - 2 有 difference[i][j] = words[i][j+1] - words[i][j] 。注意两个字母的差值定义为它们在字母表中位置之差，也就是说 'a' 的位置是 0 ，'b' 的位置是 1 ，'z' 的位置是 25 。

比方说，字符串 "acb" 的差值整数数组是 [2 - 0, 1 - 2] = [2, -1] 。
words 中所有字符串除了一个字符串以外，其他字符串的差值整数数组都相同。你需要找到那个不同的字符串。

请你返回 words中差值整数数组不同的字符串。

解答

上述的操作实际上就是差分。整个题目直接使用哈希即可解答，因为每个差值都在 \([-25, 25]\) 之间，且合格字符串的大小最长为20，所以对于一个差值我们有hash = i * 50 + 25 + 差值 + 前一个数的hash，只要比较哈希值即可
当然，想到哈希，一定是要想到状态压缩/位操作的，不过本例应不适用，因为他要对比的是差值，而不是字符串元素
但是由于题目中说：“words 中所有字符串除了一个字符串以外，其他字符串的差值整数数组都相同。你需要找到那个不同的字符串。”，所以直接用第一个差值比较后面的即可，没有什么技巧科研了

代码：

拓展

1886. 判断矩阵经轮转后是否一致

问题

给你两个大小为 n x n 的二进制矩阵 mat 和 target 。现以 90 度顺时针轮转矩阵 mat 中的元素若干次，如果能够使 mat 与 target 一致，返回 true ；否则，返回 false 。

解答

模拟时，唯一需要注意的是代码实现中如何对矩阵的一个圈进行分割。显然最多转四次，所以复杂度为\(O(n^2)\)，主要用在比较上
也可以利用矩阵旋转的变换性质
// 转度数原坐标转换坐标
90° [x, y] -> [y, n-x]
180° [x, y] -> [n-x, n-y]
270° [x, y] -> [n-y, x]

代码：