AC：3/4

AC：3/4

全是字符串，累。

第一题：5468. 第 k 个缺失的正整数

题目：

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
请你找到这个数组里第 k 个缺失的正整数。

示例 1：
输入：arr = [2,3,4,7,11], k = 5
输出：9
解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,…] 。第 5 个缺失的正整数为 9 。

示例 2：
输入：arr = [1,2,3,4], k = 2
输出：6
解释：缺失的正整数包括 [5,6,7,…] 。第 2 个缺失的正整数为 6 。

答案：

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        n=max(arr)
        count=0
        dict1=set(arr)
        for i in range(1,n+2000):
            if i not in dict1:count+=1
            if count==k:return i
        return i

思路：

傻逼了，wa在了1000上，多给1000随便过

第二题：5469. K 次操作转变字符串

题目：

给你两个字符串 s 和 t ，你的目标是在 k 次操作以内把字符串 s 转变成 t 。
在第 i 次操作时（1 <= i <= k），你可以选择进行如下操作：

选择字符串 s 中满足 1 <= j <= s.length 且之前未被选过的任意下标 j （下标从 1 开始），并将此位置的字符切换 i 次。
不进行任何操作。

切换 1 次字符的意思是用字母表中该字母的下一个字母替换它（字母表环状接起来，所以 'z' 切换后会变成 'a'）。
请记住任意一个下标 j 最多只能被操作 1 次。
如果在不超过 k 次操作内可以把字符串 s 转变成 t ，那么请你返回 true ，否则请你返回 false 。

示例 1：
输入：s = “input”, t = “ouput”, k = 9
输出：true
解释：第 6 次操作时，我们将 ‘i’ 切换 6 次得到 ‘o’ 。第 7 次操作时，我们将 ‘n’ 切换 7 次得到 ‘u’ 。

示例 2：
输入：s = “abc”, t = “bcd”, k = 10
输出：false
解释：我们需要将每个字符切换 1 次才能得到 t 。我们可以在第 1 次操作时将 ‘a’ 切换成 ‘b’ ，但另外 2 个字母在剩余操作中无法再转变为 t 中对应字母。

示例 3：
输入：s = “aab”, t = “bbb”, k = 27
输出：true
解释：第 1 次操作时，我们将第一个 ‘a’ 切换 1 次得到 ‘b’ 。在第 27 次操作时，我们将第二个字母 ‘a’ 切换 27 次得到 ‘b’ 。

提示：

1 <= s.length, t.length <= 10^5
0 <= k <= 10^9

s 和 t 只包含小写英文字母。

答案：

class Solution:
  def canConvertString(self, s: str, t: str, k: int) -> bool:
      if len(s)!=len(t):return False
      def change(s1,s2):
          if ord(s2)>=ord(s1):
              return ord(s2)-ord(s1)
          else:
              return ord(s2)-ord(s1)+26
      ans=[change(s1,s2) for s1,s2 in zip(s,t)]
      print(ans)
      visit={}
      for num in ans:
          if num==0:continue
          if num not in visit:
              if k< num:return False
              visit[num]=1
          else:
              if k< num+visit[num]*26:return False
              visit[num]+=1
      return True

思路：

模拟一下，过了。wa在了字符串不等上，恶心。

第三题：5470. 平衡括号字符串的最少插入次数

题目：

给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：

任何左括号 '(' 必须对应两个连续的右括号 '))' 。
左括号 '(' 必须在对应的连续两个右括号 '))' 之前。

比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。
你可以在任意位置插入字符 ‘(‘ 和 ‘)’ 使字符串平衡。
请你返回让 s 平衡的最少插入次数。

示例 1：
输入：s = “(()))”
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ‘)’ 使字符串变成平衡字符串 “(())))” 。

示例 2：
输入：s = “())”
输出：0
解释：字符串已经平衡了。

示例 3：
输入：s = “))())(“
输出：3
解释：添加 ‘(‘ 去匹配最开头的 ‘))’ ，然后添加 ‘))’ 去匹配最后一个 ‘(‘ 。

示例 4：
输入：s = “((((((“
输出：12
解释：添加 12 个 ‘)’ 得到平衡字符串。

示例 5：
输入：s = “)))))))”
输出：5
解释：在字符串开头添加 4 个 ‘(‘ 并在结尾添加 1 个 ‘)’ ，字符串变成平衡字符串 “(((())))))))” 。

提示：

1 <= s.length <= 10^5

s 只包含 '(' 和 ')' 。

答案：

class Solution:
  def minInsertions(self, s: str) -> int:
      stack=[]
      ans=0
      count=0
      for word in s:
          if not stack:
              if word==")":
                  count+=1
                  stack.append("(")
                  ans+=1
                  stack.append(word)
              # elif word==")" and count==1:
              else:
                  stack.append(word)
          else:
              if word=="(":
                  if count==0:
                      stack.append(word)
                  elif count==1:
                      ans+=1
                      stack.pop()
                      stack.pop()
                      stack.append(word)
                      count=0
              else:
                  if count==0:
                      stack.append(word)
                      count+=1
                  elif count==1:
                      stack.pop()
                      stack.pop()
                      count=0
      print(stack,ans,count)
      while stack:
          if count==1:
              ans+=1
              stack.pop()
              stack.pop()
              count=0
          elif count==0:
              ans+=2
              stack.pop()
      return ans

思路：

写的长了一点，但是就是普通的栈模拟一遍

第四题：5485. 找出最长的超赞子字符串

题目：

给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
「超赞子字符串」需满足满足下述两个条件：

该字符串是 s 的一个非空子字符串
进行任意次数的字符交换重新排序后，该字符串可以变成一个回文字符串

示例 1：
输入：s = “3242415”
输出：5
解释：“24241” 是最长的超赞子字符串，交换其中的字符后，可以得到回文 “24142”

示例 2：
输入：s = “12345678”
输出：1

示例 3：
输入：s = “213123”
输出：6
解释：“213123” 是最长的超赞子字符串，交换其中的字符后，可以得到回文 “231132”

示例 4：
输入：s = “00”
输出：2

提示：

1 <= s.length <= 10^5

s 仅由数字组成

答案：

class Solution:
  def longestAwesome(self, s: str) -> int:
      hashvalue=0
      ans=0
      n=len(s)
      pos=dict()
      pos[0]=-1

      for i in range(n):
          hashvalue=hashvalue^(1<<int(s[i]))
          if hashvalue in pos:
              ans= max(ans,i-pos[hashvalue])
          for j in range(10):
              temp=hashvalue^(1<<j)
              if temp in pos:
                  ans=max(ans,i-pos[temp])
          if hashvalue not in pos:
              pos[hashvalue]=i

      return ans

思路：

子串要么都是偶，要么有一个独立奇。
所以无论count 一个数字多少次都和 mod2一样，题目中一共出现10个数字，所以使用状态压缩表示，一共10位，每一位表示奇偶。

如果我的hashvalue 出现过，说明有一段之间可以回文(偶)。
如果我的hashvalue 异或某位出现过，说明有一段之间可以回文（奇）。
那一段显然是 i-pos[nowhash]
由于是从左往右字典式更新，所以答案一定是最长的那一个。

算法

20200808 第32周双周赛 score：3/4 排名：257 / 2957

AC：3/4

第一题：5468. 第 k 个缺失的正整数

题目：

答案：

思路：

第二题：5469. K 次操作转变字符串

题目：

答案：

思路：

第三题：5470. 平衡括号字符串的最少插入次数

题目：

答案：

思路：

第四题：5485. 找出最长的超赞子字符串

题目：

答案：

思路：