1. 找出数组中的所有 K 近邻下标

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

检查每一个符合 key 值的下标，然后将范围内下标加入集合即可。

代码

class Solution:
    def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
        ans = set()
        n = len(nums)
        for i in range(n):
            if nums[i] == key:
                for j in range(1, k + 1):
                    ans.add(i)
                    if 0 <= i - j < n: ans.add(i - j)
                    if 0 <= i + j < n: ans.add(i + j)
        ans = sorted(list(ans))
        return ans

2. 统计可以提取的工件

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

一开始没搞懂题意，有一个用例没过才发现什么意思。

给的工件最多占四个格子，四个坐标指明了其左上、右下的格子坐标。如果工件只有一个格子，那么两组坐标相同。如果工件是四个格子一列，那么左上格子是最上面的格子，右下格子是最下面的格子，根据这个来判断裸露情况即可。

代码

class Solution:
    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:
        ans = 0
        ground = [[0 for i in range(n)] for j in range(n)]
        for r, c in dig: ground[r][c] = 1
        for r1, c1, r2, c2 in artifacts:
            if r1 == r2 and c1 == c2:
                if ground[r1][c1] == 1:
                    ans += 1
            elif r1 == r2:
                ans += 1
                for j in range(c1, c2 + 1):
                    if ground[r1][j] == 0:
                        ans -= 1
                        break
            elif c1 == c2:
                ans += 1
                for j in range(r1, r2 + 1):
                    if ground[j][c1] == 0:
                        ans -= 1
                        break
            else:
                if ground[r1][c1] == 1 and ground[r1][c2] == 1 and ground[r2][c2] == 1 and ground[r2][c1] == 1:
                    ans += 1
        return ans

3. K 次操作后最大化顶端元素

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

有时候没有错误用例就发现不了那种情况会出错，很难受。

代码

class Solution:
    def maximumTop(self, nums: List[int], k: int) -> int:
        n = len(nums)
        origin_k = k
        if n == 1 and (k & 1) == 1: return -1
        k = k if k <= n - 1 else n - 1
        nums = sorted(zip(nums[:k + 1:], range(k + 1)), reverse = True)
        if nums[0][1] == origin_k - 1: return nums[1][0]
        else: return nums[0][0]

4. Excel 表中某个范围内的单元格

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

列号和行号均有限，直接模拟即可。

代码

class Solution:
    def cellsInRange(self, s: str) -> List[str]:
        ans = []
        for c in range(ord(s[0]), ord(s[3]) + 1):
            for j in range(int(s[1]), int(s[4]) + 1):
                ans.append(chr(c) + str(j))
        return ans

5. 向数组中追加 K 个整数

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

脑子短路了，居然一开始想用遍历做。

先把数组排序，在数组开头加个0，数组末尾加上元素上限。

逐个遍历，尽可能地累加两个元素间的元素即可。

代码

class Solution:
    def minimalKSum(self, nums: List[int], k: int) -> int:
        ans = 0
        nums.append(0)
        nums.sort()
        nums.append(int(1e+9 + 1))
        n = len(nums)
        for i in range(1, n):
            if k == 0: break
            if nums[i - 1] + 1 <= min(nums[i - 1] + k, nums[i] - 1):
                ans += (nums[i - 1] + 1 + min(nums[i - 1] + k, nums[i] - 1)) * (min(nums[i - 1] + k, nums[i] - 1) - (nums[i - 1])) // 2
                k -= (min(nums[i - 1] + k, nums[i] - 1) - (nums[i - 1]))
        return ans

6. 根据描述创建二叉树

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

先用字典记录下父节点的孩子。找到自身是父节点，但不是子节点的节点，即为根节点，然后用栈构造树。

代码

class Solution:
    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
        parents = set()
        children = set()
        dic = defaultdict(list[list[int]])
        for p, c, isL in descriptions:
            parents.add(p)
            children.add(c)
            dic[p].append([c, isL])
        parents = list(parents)
        rootVal = -1
        for p in parents:
            if p not in children: rootVal = p
        root = TreeNode(rootVal)
        stack = [root]
        while stack:
            cur = stack.pop()
            for children in dic[cur.val]:
                child = TreeNode(children[0])
                if children[1] == 1:
                    cur.left = child
                else:
                    cur.right = child
                stack.append(child)
        return root