Leetcode 第 137 场双周赛

Powered by:NEFU AB-IN

Link

Q1. 长度为 K 的子数组的能量值 I

题意

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个数组的 能量值 定义为：

如果 所有 元素都是依次 连续 且 上升 的，那么能量值为 最大 的元素。
否则为 -1 。
你需要求出 nums 中所有长度为 k 的子数组的能量值。

请你返回一个长度为 n - k + 1 的整数数组 results ，其中 results[i] 是子数组 nums[i…(i + k - 1)] 的能量值。

思路

这个数据范围小，可以直接暴力

代码

# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)# Set recursion limit
setrecursionlimit(int(2e9))class Arr:array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])graph = staticmethod(lambda size=N: [[] for _ in range(size)])class Math:max = staticmethod(lambda a, b: a if a > b else b)min = staticmethod(lambda a, b: a if a < b else b)class IO:input = staticmethod(lambda: stdin.readline().strip())read = staticmethod(lambda: map(int, IO.input().split()))read_list = staticmethod(lambda: list(IO.read()))read_mixed = staticmethod(lambda *types: [t(v) for t, v in zip(types, IO.input().split())])class Std:pass# ————————————————————— Division line ——————————————————————class Solution:def resultsArray(self, nums: List[int], k: int) -> List[int]:n = len(nums)res = []for i in range(n - k + 1):flag = Truemax_ = nums[i]for j in range(i + 1, i + k):if nums[j] != nums[j - 1] + 1:flag = Falsebreakmax_ = Math.max(max_, nums[j])if flag:res.append(max_)else:res.append(-1)return res

Q2. 长度为 K 的子数组的能量值 II

题意

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个数组的 能量值 定义为：

如果 所有 元素都是依次 连续 且 上升 的，那么能量值为 最大 的元素。
否则为 -1 。
你需要求出 nums 中所有长度为 k 的子数组的能量值。

请你返回一个长度为 n - k + 1 的整数数组 results ，其中 results[i] 是子数组 nums[i…(i + k - 1)] 的能量值。

思路

求前缀和即可，然后通过等差数列求和判断是否相等，而且d = 1

代码

# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)# Set recursion limit
setrecursionlimit(int(2e9))class Arr:array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])graph = staticmethod(lambda size=N: [[] for _ in range(size)])class Math:max = staticmethod(lambda a, b: a if a > b else b)min = staticmethod(lambda a, b: a if a < b else b)class IO:input = staticmethod(lambda: stdin.readline().strip())read = staticmethod(lambda: map(int, IO.input().split()))read_list = staticmethod(lambda: list(IO.read()))read_mixed = staticmethod(lambda *types: [t(v) for t, v in zip(types, IO.input().split())])class Std:class PrefixSum:def __init__(self, nums: List[int]):"""Initializes the PrefixSum object with the given list of numbers.Args:nums (List[int]): The input array of integers (0-based index)."""self._n = len(nums)self._prefix_sum_ = Arr.array(0, self._n + 1)  # 1-based index# Compute the prefix sum with adjusted indexingfor i in range(1, self._n + 1):# Adjust nums index by subtracting 1 to map 1-based prefix_sum to 0-based numsself._prefix_sum_[i] = self._prefix_sum_[i - 1] + nums[i - 1]def query(self, left: int, right: int) -> int:"""Returns the sum of elements in the range [left, right]. The input coordinates is 0-based indexing."""# Convert the 0-based indices to 1-based by adding 1return self._prefix_sum_[right + 1] - self._prefix_sum_[left]# ————————————————————— Division line ——————————————————————class Solution:def resultsArray(self, nums: List[int], k: int) -> List[int]:n = len(nums)res = []pre = Std.PrefixSum(nums)for i in range(n - k + 1):flag = pre.query(i, i + k - 1) == (k * (nums[i] + nums[i + k - 1]) // 2) and nums[i + k - 1] - nums[i] == k - 1if flag:res.append(nums[i + k - 1])else:res.append(-1)return res

Q3. 放三个车的价值之和最大 I

Q4. 放三个车的价值之和最大 II

题意

给你一个 m x n 的二维整数数组 board ，它表示一个国际象棋棋盘，其中 board[i][j] 表示格子 (i, j) 的 价值 。

处于 同一行 或者 同一列 车会互相 攻击 。你需要在棋盘上放三个车，确保它们两两之间都 无法互相攻击 。

请你返回满足上述条件下，三个车所在格子 值 之和 最大 为多少。

思路

类似贪心，可以推出来，每一列和每一行，最多取三个最大的值，取出来全放进set中去重，然后进行三个棋子的挨个枚举即可
偏暴力，应该不是最优解法，复杂度最大为排序的复杂度，n最大为1e7左右

代码

'''
Author: NEFU AB-IN
Date: 2024-08-17 22:12:44
FilePath: \LeetCode\CP137_2\c\c.py
LastEditTime: 2024-08-17 23:11:38
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)# Set recursion limit
setrecursionlimit(int(2e9))class Arr:array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])graph = staticmethod(lambda size=N: [[] for _ in range(size)])class Math:max = staticmethod(lambda a, b: a if a > b else b)min = staticmethod(lambda a, b: a if a < b else b)class IO:input = staticmethod(lambda: stdin.readline().strip())read = staticmethod(lambda: map(int, IO.input().split()))read_list = staticmethod(lambda: list(IO.read()))read_mixed = staticmethod(lambda *types: [t(v) for t, v in zip(types, IO.input().split())])class Std:pass# ————————————————————— Division line ——————————————————————class Solution:def maximumValueSum(self, board: List[List[int]]) -> int:m, n = len(board), len(board[0])row_dict = defaultdict(list)col_dict = defaultdict(list)for i in range(m):for j in range(n):value = board[i][j]if len(row_dict[i]) < 3:row_dict[i].append((value, i, j))row_dict[i].sort(reverse=True, key=lambda x: x[0])elif value > row_dict[i][-1][0]:row_dict[i][-1] = (value, i, j)row_dict[i].sort(reverse=True, key=lambda x: x[0])if len(col_dict[j]) < 3:col_dict[j].append((value, i, j))col_dict[j].sort(reverse=True, key=lambda x: x[0])elif value > col_dict[j][-1][0]:col_dict[j][-1] = (value, i, j)col_dict[j].sort(reverse=True, key=lambda x: x[0])row_max_set = set()for i in range(m):row_max_set.update(row_dict[i])for j in range(n):row_max_set.update(col_dict[j])row_max = list(row_max_set)row_max.sort(reverse=True, key=lambda x: x[0])res = -INFfor i in range(len(row_max)):v1, r1, c1 = row_max[i]for j in range(i + 1, len(row_max)):v2, r2, c2 = row_max[j]if c1 == c2 or r1 == r2:continuefor k in range(j + 1, len(row_max)):v3, r3, c3 = row_max[k]if r2 != r3 and r1 != r3 and c2 != c3 and c1 != c3:res = Math.max(res, v1 + v2 + v3)breakreturn res