【复盘】第 111 场力扣夜喵双周赛

又是7分选手，好好复盘！

第一题（签到题）

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且
nums[i] + nums[j] < target 的下标对 (i, j) 的数目。 示例 1： 输入：nums =
[-1,1,2,3,1], target = 2 输出：3 解释：总共有 3 个下标对满足题目描述：

• (0, 1) ，0 < 1 且 nums[0] + nums[1] = 0 < target
• (0, 2) ，0 < 2 且 nums[0] + nums[2] = 1 < target
• (0, 4) ，0 < 4 且 nums[0] + nums[4] = 0 < target 注意 (0, 3) 不计入答案因为 nums[0] + nums[3] 不是严格小于 target 。 示例 2： 输入：nums = [-6,2,5,-2,-7,-1,3],
  target = -2 输出：10 解释：总共有 10 个下标对满足题目描述：
• (0, 1) ，0 < 1 且 nums[0] + nums[1] = -4 < target
• (0, 3) ，0 < 3 且 nums[0] + nums[3] = -8 < target
• (0, 4) ，0 < 4 且 nums[0] + nums[4] = -13 < target
• (0, 5) ，0 < 5 且 nums[0] + nums[5] = -7 < target
• (0, 6) ，0 < 6 且 nums[0] + nums[6] = -3 < target
• (1, 4) ，1 < 4 且 nums[1] + nums[4] = -5 < target
• (3, 4) ，3 < 4 且 nums[3] + nums[4] = -9 < target
• (3, 5) ，3 < 5 且 nums[3] + nums[5] = -3 < target
• (4, 5) ，4 < 5 且 nums[4] + nums[5] = -8 < target
• (4, 6) ，4 < 6 且 nums[4] + nums[6] = -4 < target 提示： 1 <= nums.length == n <= 50
  -50 <= nums[i], target <= 50

没什么好说的，两层循环，找到了元素对则计数器加1。

class Solution(object):
    def countPairs(self, nums, target):
        count = 0
        for i in range(0,len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i] + nums[j]<target:
                    count = count + 1
        return count
1
2
3
4
5
6
7
8

第二题（双指针）

给你一个下标从 0 开始的字符串 str1 和 str2 。

一次操作中，你选择 str1 中的若干下标。对于选中的每一个下标 i ，你将 str1[i] 循环 递增，变成下一个字符。也就是说 ‘a’
变成 ‘b’ ，‘b’ 变成 ‘c’ ，以此类推，‘z’ 变成 ‘a’ 。

如果执行以上操作 至多一次 ，可以让 str2 成为 str1 的子序列，请你返回 true ，否则返回 false 。

注意：一个字符串的子序列指的是从原字符串中删除一些（可以一个字符也不删）字符后，剩下字符按照原本先后顺序组成的新字符串。

示例 1：

输入：str1 = “abc”, str2 = “ad” 输出：true 解释：选择 str1 中的下标 2 。 将 str1[2]
循环递增，得到 ‘d’ 。 因此，str1 变成 “abd” 且 str2 现在是一个子序列。所以返回 true 。 示例 2：

输入：str1 = “zc”, str2 = “ad” 输出：true 解释：选择 str1 中的下标 0 和 1 。 将 str1[0]
循环递增得到 ‘a’ 。 将 str1[1] 循环递增得到 ‘d’ 。 因此，str1 变成 “ad” 且 str2
现在是一个子序列。所以返回 true 。 示例 3：

输入：str1 = “ab”, str2 = “d” 输出：false 解释：这个例子中，没法在执行一次操作的前提下，将 str2 变为
str1 的子序列。 所以返回 false 。

提示：

1 <= str1.length <= 105 1 <= str2.length <= 105 str1 和 str2 只包含小写英文字母。

这道题我用了双指针的方法，两个指针分别指向两个字符串的开头，如果匹配或者加1后匹配，则两个指针同时后移；如果不匹配，则匹配的字符串指针后移，被匹配的字符串指针不动。最后退出的条件是：有指针到达字符串终点。如果被匹配的字符串指针到了终点说明匹配成功；反之如果匹配字符串指针到达终点而被匹配的字符串指针没有到达终结则说明匹配失败。

class Solution(object):
    def canMakeSubsequence(self, str1, str2):
        i = 0
        j = 0
        while True:
            if j==len(str2):
                return True
            if j!=len(str2) and i==len(str1):
                return False
            if str2[j] == 'a':
                if str1[i] == 'a' or str1[i] == 'z':
                    i = i + 1
                    j = j + 1
                else:
                    i = i + 1
            else:
                if str1[i]==str2[j] or ord(str1[i])+1 == ord(str2[j]):
                    i = i + 1
                    j = j + 1
                else:
                    i = i + 1            
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第三题（没做出来）

比赛的时候看题以为是暴力可以求出来，结果最后一直有10% 的样例不过。

给你一个下标从 0 开始长度为 n 的整数数组 nums 。

从 0 到 n - 1 的数字被分为编号从 1 到 3 的三个组，数字 i 属于组 nums[i] 。注意，有的组可能是 空的 。

你可以执行以下操作任意次：

选择数字 x 并改变它的组。更正式的，你可以将 nums[x] 改为数字 1 到 3 中的任意一个。 你将按照以下过程构建一个新的数组
res ：

将每个组中的数字分别排序。 将组 1 ，2 和 3 中的元素 依次 连接以得到 res 。 如果得到的 res 是
非递减顺序的，那么我们称数组 nums 是 美丽数组 。

请你返回将 nums 变为 美丽数组 需要的最少步数。

示例 1：

输入：nums = [2,1,3,2,1] 输出：3 解释：以下三步操作是最优方案：

1. 将 nums[0] 变为 1 。
2. 将 nums[2] 变为 1 。
3. 将 nums[3] 变为 1 。 执行以上操作后，将每组中的数字排序，组 1 为 [0,1,2,3,4] ，组 2 和组 3 都为空。所以 res 等于 [0,1,2,3,4] ，它是非递减顺序的。 三步操作是最少需要的步数。 示例 2：

输入：nums = [1,3,2,1,3,3] 输出：2 解释：以下两步操作是最优方案：

1. 将 nums[1] 变为 1 。
2. 将 nums[2] 变为 1 。 执行以上操作后，将每组中的数字排序，组 1 为 [0,1,2,3] ，组 2 为空，组 3 为 [4,5] 。所以 res 等于 [0,1,2,3,4,5] ，它是非递减顺序的。 两步操作是最少需要的步数。 示例 3：

输入：nums = [2,2,2,2,3,3] 输出：0 解释：不需要执行任何操作。 组 1 为空，组 2 为 [0,1,2,3] ，组 3
为 [4,5] 。所以 res 等于 [0,1,2,3,4,5] ，它是非递减顺序的。

提示：

1 <= nums.length <= 100 1 <= nums[i] <= 3

比赛结束后，看到题解有dp突然想起来可能是动态规划。
a代表结尾为1时所需要的最小步数，b代表结尾为2时所需要的最小步数，c代表结尾为3时所需要的最小步数。当num等于1时，结尾为1不需要做出任何调整，结尾为2则需要选取aa和bb的最小值并对num进行调整，结尾为3则需要选取aa和bb和cc的最小值并对num进行调整。

class Solution(object):
    def minimumOperations(self, nums):
        a = 0
        b = 0
        c = 0 
        for num in nums:
            aa = a
            bb = b
            cc = c
            if num==1:
                a = aa
                b = min(aa,bb) + 1
                c = min(aa,bb,cc) + 1
            elif num==2:
                a = aa + 1
                b = min(aa,bb)
                c = min(aa,bb,cc) + 1
            elif num==3:
                a = aa + 1
                b = min(aa,bb) + 1
                c = min(aa,bb,cc)
        return min(a,b,c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

第四题（没做出来）

第四题是最恶心了，每次都有几个或者十几个样例卡你，不是超时就是超内存hhhh。

给你正整数 low ，high 和 k 。

如果一个数满足以下两个条件，那么它是 美丽的 ：

偶数数位的数目与奇数数位的数目相同。 这个整数可以被 k 整除。 请你返回范围 [low, high] 中美丽整数的数目。

示例 1：

输入：low = 10, high = 20, k = 3 输出：2 解释：给定范围中有 2 个美丽数字：[12,18]

• 12 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
• 18 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。 以下是一些不是美丽整数的例子：
• 16 不是美丽整数，因为它不能被 k = 3 整除。
• 15 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。 给定范围内总共有 2 个美丽整数。 示例 2：

输入：low = 1, high = 10, k = 1 输出：1 解释：给定范围中有 1 个美丽数字：[10]

• 10 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 1 整除。 给定范围内总共有 1 个美丽整数。 示例 3：

输入：low = 5, high = 5, k = 2 输出：0 解释：给定范围中有 0 个美丽数字。

• 5 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。

提示：

0 < low <= high <= 109 0 < k <= 20

我的代码（超内存了）：

class Solution(object):
    def numberOfBeautifulIntegers(self, low, high, k):
        count = 0
        for i in range(low,high+1):
            ji = 0
            ou = 0
            if i%k==0:
                length = len(str(i))
                for p in str(i):
                    if ji>=length//2+1 or ou>=length//2+1:
                        break
                    if p in ['1','3','5','7','9']:
                        ji = ji + 1
                    else:
                        ou = ou + 1
                if ou==ji:
                    count = count + 1
        return count
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

看题解是数位DP，没接触过。。