某关于等差数列的问题

问题

已知一数列 , 其首项 和末项 的和与第二项 和 倒数第二项 的和相等，以此类推。且该数列单调递增。现在这一数列丢失了一个数 （该数不在头尾），求该数。

样例

样例1：

input1: 5
input2: {1, 3, 5, 9, 11}

output1: 7

样例2：

input1: 5
input2: {2, 4, 6, 10, 12}

output2: 8

题解

本题难度：🌕

本题非常简单，给了很多有利条件（如首尾元素存在，数列单调递增）。因此只要先计算首尾元素的和，再从第二个元素开始遍历，至多只要遍历原数组的一半即可找到缺失的数。时间复杂度为 .

代码

def solve1(input1:int, input2: list[int]) -> int:
    s = input2[0] + input2[input1 - 1]
    for i in range(1, input1):
        if s - input2[i] not in input2: # Python 的 not in 真是太方便了
            return s - input2[i]

某关于字符串的问题

问题

给定一段文本 text，由若干单词组成，单词之间由空格分隔。现在这个文本中的每个单词都被人打乱了，打乱的方式是从左往右循环移位 次。但即使这样，文本中仍有一些单词没有发生变化，请找出没有发生变化的单词的个数。

样例

样例1：

input1: "llohe ereth"
input2: 2

output1: 0

说明：原单词是 "hello there", 经过 2 次变换后，变换后的单词和原单词不相等，因此输出 0.

样例2：

input1: "adaada"
input2: 3

output2: 1

说明：原单词是 "adaada"，变换 3 次以后和原单词相等，于是输出 1.

题解

本题难度：🌕🌗

首先分割该字符串，得到每个单词的序列。对每个单词，进行循环移位，若移位后的单词和原单词相等，则相等的单词数+1.

此处有坑：要考虑单词变换次数大于（甚至远大于）单词本身长度的问题。 如果真的采用机械式的循环移位，真的遇到变换次数远大于单词本身长度的时候，可能会超时。（感谢出题人没有出这么变态的样例）

代码

def solve2(input1: str, input2: int)->int:
    all_words = input1.split()
    num_of_correct_words = 0
    for word in all_words:
        r = input2 % len(word)
        new_word = word[r:] + word[:r]  # Python 的切片操作真是太方便啦
        if new_word == word:
            num_of_correct_words += 1
    return num_of_correct_words

某关于字符串匹配的问题

问题

有两个人分别叫 K 和 J，他们是棋逢对手的宿敌。由于 K 的地位比 J 高，所以每次对决时必须由 K 先出招，J 为了表示对 K 的尊敬，也会回敬相同次数的出招。但在一次对决中，发生了时空错乱，导致两人出招的顺序发生了改变。现在你有修正时空的能力，可以将两人出招的顺序修正过来。请找出最小需要改变时空的次数。

样例

样例1：

input1: JK

output1: 2

说明：由于 K 必须先出招，所以第一个 J 要改成 K，而 J 必须回敬一次 K 的出招，所以第二个 K 要改成 J，总共需要修改 2 次。

样例2：

input1: KKKK

output2: 2

说明：由于 J 的出手次数必须和 K 相同，所以将第二、第四个位置的 K 改为 J，一共需要修改 2 次。

题解

本题难度：🌕🌕

本题不要被这个背景唬住。本质上是字符串配对的问题。进一步抽象，可以将 J 看成右括号，K 看成左括号。实际上就变成了括号配对。根据题目的要求，两个成对的括号必须配对，那么剩下的就是需要修改的。

这里可以建立一个栈，分为下列情况：

1. 栈空，无论压入什么都必须压入。
2. 栈非空，且栈顶元素为 K，当试图压入 J 时，弹出栈顶。
3. 栈非空，且栈顶元素为 K，当试图压入 K 时，压入。
4. 栈非空，且栈顶元素为 J，无论压入什么都必须压入。

当遍历完输入字符串后，栈内剩下的元素：

1. 若为奇数，则不可能有符合要求的解，输出 -1。
2. 若为偶数，则建立一个和栈等长的字符串，其中为 K、J、K、J……的交替序列。
3. 栈（此时不再看成栈）和字符串比较，若不一样则记录一次变换。

代码

def solve3(input1: str) -> int:
    stack = []
    ex = 0
    for ch in input1:
        if not stack:
            stack.append(ch)
        elif stack[-1] == 'K':
            if ch == 'J':
                stack.pop()
            elif ch == 'K':
                stack.append(ch)
        elif stack[-1] == 'J':
            stack.append(ch)
    if len(stack) % 2 != 0:
        return -1
    else:
        s = ''
        for i in range(len(stack)):
            if i % 2 == 0:
                s += 'K'
            else:
                s += 'J'
        for i in range(len(stack)):
            if stack[i] != s[i]:
                ex += 1
        return ex

只可惜这个题没做完，被样例坑了，以为 J 和 K 一定是交替序列，调试调了很久，到最后时间来不及了。但我觉得我的解法应该是对的。