Leetcode第273场周赛write up

发表于

反转两次的数字

1
2
3
反转 一个整数意味着倒置它的所有位。
例如，反转 2021 得到 1202 。反转 12300 得到 321 ，不保留前导零 。
给你一个整数 num ，反转 num 得到 reversed1 ，接着反转 reversed1 得到 reversed2 。如果 reversed2 等于 num ，返回 true ；否则，返回 false 。
1
2
3
输入：num = 526
输出：true
解释：反转 num 得到 625 ，接着反转 625 得到 526 ，等于 num 。
1
2
3
输入：num = 1800
输出：false
解释：反转 num 得到 81 ，接着反转 81 得到 18 ，不等于 num 。
1
2
3
输入：num = 0
输出：true
解释：反转 num 得到 0 ，接着反转 0 得到 0 ，等于 num 。

这道题分两种情况，最后一位是0和最后一位不是0。

如果最后一位是不是0，直接返回True

如果最后一位是0，分这个数是0还是其他数字。如果这个数是0，直接回返True，如果这个数不是0，直接返回False

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def isSameAfterReversals(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num == 0:
            return True
        if num%10==0:
            return False
        else:
            return True

执行所有后缀指令

1
2
3
4
5
6
现有一个 n x n 大小的网格，左上角单元格坐标 (0, 0) ，右下角单元格坐标 (n - 1, n - 1) 。给你整数 n 和一个整数数组 startPos ，其中 startPos = [startrow, startcol] 表示机器人最开始在坐标为 (startrow, startcol) 的单元格上。
另给你一个长度为 m 、下标从 0 开始的字符串 s ，其中 s[i] 是对机器人的第 i 条指令：'L'（向左移动），'R'（向右移动），'U'（向上移动）和 'D'（向下移动）。
机器人可以从 s 中的任一第 i 条指令开始执行。它将会逐条执行指令直到 s 的末尾，但在满足下述条件之一时，机器人将会停止：
下一条指令将会导致机器人移动到网格外。
没有指令可以执行。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是机器人从第 i 条指令 开始 ，可以执行的指令数目。
1
2
3
4
5
6
7
8
9
输入：n = 3, startPos = [0,1], s = "RRDDLU"
输出：[1,5,4,3,1,0]
解释：机器人从 startPos 出发，并从第 i 条指令开始执行：
- 0: "RRDDLU" 在移动到网格外之前，只能执行一条 "R" 指令。
- 1:  "RDDLU" 可以执行全部五条指令，机器人仍在网格内，最终到达 (0, 0) 。
- 2:   "DDLU" 可以执行全部四条指令，机器人仍在网格内，最终到达 (0, 0) 。
- 3:    "DLU" 可以执行全部三条指令，机器人仍在网格内，最终到达 (0, 0) 。
- 4:     "LU" 在移动到网格外之前，只能执行一条 "L" 指令。
- 5:      "U" 如果向上移动，将会移动到网格外。
1
2
3
4
5
6
7
输入：n = 2, startPos = [1,1], s = "LURD"
输出：[4,1,0,0]
解释：
- 0: "LURD"
- 1:  "URD"
- 2:   "RD"
- 3:    "D"
1
2
3
输入：n = 1, startPos = [0,0], s = "LRUD"
输出：[0,0,0,0]
解释：无论机器人从哪条指令开始执行，都会移动到网格外。

这道题，拿到手，我就直接上if else。分别对上下左右进行边界判断，如果字符串最终走完了，那么说明该字符串的指令都可以执行，如果执行到一半退出了，那么说明越界了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):
    def executeInstructions(self, n, startPos, s):
        """
        :type n: int
        :type startPos: List[int]
        :type s: str
        :rtype: List[int]
        """
        res = []
        for i in range(len(s)):
          	#flag用来标记是否在字符串中间退出
            flag = 1
            tmpPos = startPos[:]
            for j in range(i, len(s)):
                if s[j] == 'L':
                    tmpPos[1] -= 1
                    if tmpPos[1] < 0:
                        res.append(j-i)
                        flag = 0
                        break
                elif s[j] == 'R':
                    tmpPos[1] += 1
                    if tmpPos[1] >= n:
                        res.append(j-i)
                        flag = 0
                        break
                elif s[j] == 'U':
                    tmpPos[0] -= 1
                    if tmpPos[0] < 0:
                        res.append(j-i)
                        flag = 0
                        break
                elif s[j] == 'D':
                    tmpPos[0] += 1
                    if tmpPos[0] >= n:
                        res.append(j-i)
                        flag = 0
                        break
            if flag:
                res.append(len(s) - i)
        return res

做第三题之前，我们先来做一下Leetcode1685题，第三题和这道题类似。

有序数组中差绝对值之和

1
2
3
给你一个 非递减 有序整数数组 nums 。
请你建立并返回一个整数数组 result，它跟 nums 长度相同，且result[i] 等于 nums[i] 与数组中所有其他元素差的绝对值之和。
换句话说， result[i] 等于 sum(|nums[i]-nums[j]|) ，其中 0 <= j < nums.length 且 j != i （下标从 0 开始）。
1
2
3
4
5
6
输入：nums = [2,3,5]
输出：[4,3,5]
解释：假设数组下标从 0 开始，那么
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4，
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3，
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5。
1
2
输入：nums = [1,4,6,8,10]
输出：[24,15,13,15,21]

初看这道题，我眼前一亮，一上来就是一个双重循环。多么美妙的手法啊！写完之后，执行代码没有问题，点击提交，多么优雅！过了三秒，如下图所示，我知道我大意了。

1

思索数分钟后，我点击了相关标签这个选项，试图寻找一丝灵感。相关标签里写到了三个大字，前缀和。我恍然大悟。接下来，我将通过如下的思路来进行分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
解题思路：
        因为是有序排列，因此后一个减去前一个肯定是正数，无论是否加绝对值
        考虑nums = 2 3 5 6这四个数
        res1 = |2-2|+|2-3|+|2-5|+|2-6|
        从第二个绝对值开始，结果都要取反，不考虑相等的值
        将res1改为
        res1 = 2-2+3-2+5-2+6-2 = sum(nums)-2*len(nums)
        
        res2 = |3-2|+|3-3|+|3-5|+|3-6|
        从第三个绝对值开始，结果都要取反，不考虑相等的值
        将res2改为
        res2 = 3-2+3-3+5-3+6-3，其中为了凑到sum(res1)
        我们将 3-2 凑成 (2-3)+(3-2)*2
        则res2 = sum(nums)-3*len(nums) + (3-2)*2
        
        res3 = |5-2|+|5-3|+|5-5|+|5-6|
        从第四个绝对值开始，结果都要取反，不考虑相等的值
        将res3改为
        res3 = 5-2+5-3+5-5+6-5，其中为了凑到sum(res1)
        我们将 5-2+5-3 凑成 (2-5+3-5)+(5-2+5-3)*2
        则res2 = sum(nums)-5*len(nums) + (5-2+5-3)*2
        
        res4 = |6-2|+|6-3|+|6-5|+|6-6|
        将res4改为
        res4 = 6-2+6-3+6-5+6-6，其中为了凑到sum(res1)
        我们将 6-2+6-3+6-5 凑成 (2-6+3-6+5-6)+(6-2+6-3+6-5)*2
        则res2 = sum(nums)-6*len(nums) + (6-2+6-3+6-5)*2
        
        通过上述分析我们最终可以得到第i个数的结果为
        res[i] = (sum(nums)-nums[i]*len(nums)+(nums[i]*i - sum(1...i))*2

如果你看懂了上面的分析过程，那么代码写起来将会非常容易。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def getSumAbsoluteDifferences(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = []
        n = len(nums)
        sums = sum(nums)
        tmp_sum = 0
        for i in range(len(nums)):
            res.append(sums - nums[i] * n + (nums[i] * i - tmp_sum) * 2)
            tmp_sum += nums[i]
        return res

现在让我们回到本周周赛的第三题

相同元素的间隔之和

1
2
3
4
给你一个下标从 0 开始、由 n 个整数组成的数组 arr 。
arr 中两个元素的间隔定义为它们下标之间的 绝对差 。更正式地，arr[i]和arr[j] 之间的间隔是 |i - j|。
返回一个长度为 n 的数组 intervals ，其中 intervals[i] 是 arr[i] 和 arr 中每个相同元素（与 arr[i] 的值相同）的 间隔之和 。
注意：|x| 是 x 的绝对值。
1
2
3
4
5
6
7
8
9
10
输入：arr = [2,1,3,1,2,3,3]
输出：[4,2,7,2,4,4,5]
解释：
- 下标 0 ：另一个 2 在下标 4 ，|0 - 4| = 4
- 下标 1 ：另一个 1 在下标 3 ，|1 - 3| = 2
- 下标 2 ：另两个 3 在下标 5 和 6 ，|2 - 5| + |2 - 6| = 7
- 下标 3 ：另一个 1 在下标 1 ，|3 - 1| = 2
- 下标 4 ：另一个 2 在下标 0 ，|4 - 0| = 4
- 下标 5 ：另两个 3 在下标 2 和 6 ，|5 - 2| + |5 - 6| = 4
- 下标 6 ：另两个 3 在下标 2 和 5 ，|6 - 2| + |6 - 5| = 5
1
2
3
4
5
6
7
输入：arr = [10,5,10,10]
输出：[5,0,3,4]
解释：
- 下标 0 ：另两个 10 在下标 2 和 3 ，|0 - 2| + |0 - 3| = 5
- 下标 1 ：只有这一个 5 在数组中，所以到相同元素的间隔之和是 0
- 下标 2 ：另两个 10 在下标 0 和 3 ，|2 - 0| + |2 - 3| = 3
- 下标 3 ：另两个 10 在下标 0 和 2 ，|3 - 0| + |3 - 2| = 4

现在再看这道题，多么熟悉！由于我之前并没有做过1685这道题，所以我早上比赛的时候一脸懵逼，但是还是硬着头皮写了一下。我先讲一下我没有做1685这道题之前做这个题的思路。

  • 首先我肯定需要分组，按照相同的数字将他们的下标分在一组。
  • 其次针对每一组数我都需要计算他们各自和组里其他数的绝对值之和。

于是我写了如下代码，其中我通过字典的key来保存数字，value来保存数字的下标。之后对字典的value进行遍历，去计算组内每个数和其他数之间的绝对值之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def getDistances(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        d = {}
        res = [0] * len(arr)
        result = []
        for i in range(len(arr)):
            if arr[i] not in d.keys():
                d[arr[i]] = [i]
            else:
                d[arr[i]].append(i)
        print(d)
        for value in d.values():
            for v in value:
                s = 0
                for r in value:
                    s+=abs(v-r)
                res[v] = s
        return res

最终还是超时了。。。。。

当我做了1685这道题之后，我明白了我需要改进的地方。对于字典分组这一块还是不需要改变的，只需要改进后面计算绝对值之和。改进后的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def getDistances(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        d = {}
        res = [0] * len(arr)
        for i in range(len(arr)):
            if arr[i] not in d.keys():
                d[arr[i]] = [i]
            else:
                d[arr[i]].append(i)
        for nums in d.values():
            res = []
            n = len(nums)
            sums = sum(nums)
            tmp_sum = 0
            for i in range(len(nums)):
                res.append(sums - nums[i] * n + (nums[i] * i - tmp_sum) * 2)
                tmp_sum += nums[i]
            for i in range(len(nums)):
                result[nums[i]] = res[i]
        return result

最终还是超时了。。。。。

我突然感觉眼前一片黑暗，这特么也能超时？？？于是我打算优化一下前面字典分组这一块，优化代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def getDistances(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        d = {}
        for i,v in enumerate(arr):
            if v not in d.keys():
                d[v] = [i]
            else:
                d[v].append(i)
        result = [0] * len(arr)
        for nums in d.values():
            res = []
            n = len(nums)
            sums = sum(nums)
            tmp_sum = 0
            for i in range(len(nums)):
                res.append(sums - nums[i] * n + (nums[i] * i - tmp_sum) * 2)
                tmp_sum += nums[i]
            for i in range(len(nums)):
                result[nums[i]] = res[i]
        return result

梅开三度，还是超时。。。于是我看了一下题解是怎么写的。其中有一个python的解法跟我这个差不太多，我借用了一下人家对于字典分组这块的写法，最终代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def getDistances(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        
        d = collections.defaultdict(list)
        ans = {}
        for i , v in enumerate(arr):
          d[v].append(i)
        result = [0] * len(arr)
        for nums in d.values():
            res = []
            n = len(nums)
            sums = sum(nums)
            tmp_sum = 0
            for i in range(len(nums)):
                res.append(sums - nums[i] * n + (nums[i] * i - tmp_sum) * 2)
                tmp_sum += nums[i]
            for i in range(len(nums)):
                result[nums[i]] = res[i]
        return result

终于通过了😭😭😭，特么的，同样都是字典，为啥原生的字典和collections模块中的字典差距就这么大呢。。。

2

还原原数组

1
2
3
4
5
6
Alice 有一个下标从 0 开始的数组 arr ，由 n 个正整数组成。她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher ：
对每个满足 0 <= i < n 的下标 i ，lower[i] = arr[i] - k
对每个满足 0 <= i < n 的下标 i ，higher[i] = arr[i] + k
不幸地是，Alice 丢失了全部三个数组。但是，她记住了在数组 lower 和 higher 中出现的整数，但不知道每个整数属于哪个数组。请你帮助 Alice 还原原数组。
给你一个由 2n 个整数组成的整数数组 nums ，其中 恰好 n 个整数出现在 lower ，剩下的出现在 higher ，还原并返回 原数组 arr 。如果出现答案不唯一的情况，返回 任一 有效数组。
注意：生成的测试用例保证存在 至少一个 有效数组 arr 。
1
2
3
4
5
6
输入：nums = [2,10,6,4,8,12]
输出：[3,7,11]
解释：
如果 arr = [3,7,11] 且 k = 1 ，那么 lower = [2,6,10] 且 higher = [4,8,12] 。
组合 lower 和 higher 得到 [2,6,10,4,8,12] ，这是 nums 的一个排列。
另一个有效的数组是 arr = [5,7,9] 且 k = 3 。在这种情况下，lower = [2,4,6] 且 higher = [8,10,12] 。
1
2
3
4
5
6
7
输入：nums = [1,1,3,3]
输出：[2,2]
解释：
如果 arr = [2,2] 且 k = 1 ，那么 lower = [1,1] 且 higher = [3,3] 。
组合 lower 和 higher 得到 [1,1,3,3] ，这是 nums 的一个排列。
注意，数组不能是 [1,3] ，因为在这种情况下，获得 [1,1,3,3] 唯一可行的方案是 k = 0 。
这种方案是无效的，k 必须是一个正整数。
1
2
3
4
输入：nums = [5,435]
输出：[220]
解释：
唯一可行的组合是 arr = [220] 且 k = 215 。在这种情况下，lower = [5] 且 higher = [435] 。

这道题嘛！告辞。。。