数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学Python程序：查找两个数字列表中距离最大的配对
假设我们有两个名为A和B的数字列表，它们的长度相同。我们需要找到所有0 ≤ i < j < n时：|a[i] - a[j]| + |b[i] - b[j]| + |i - j| 的最大值。
因此，如果输入类似于A = [2, 4, 10, 6] B = [3, 4, 7, 5]，则输出将为14，因为当i = 0且j = 2时，我们得到|2 - 10| + |3 - 7| + |1 - 3|。
为了解决这个问题，我们将遵循以下步骤：
- ans := 0
- n := a的长度
- 对于每个配对 (s, t) in [(-1, -1) ,(-1, 1) ,(1, -1) ,(1, 1) ]，执行：
- cur_min := 无穷大
- cur_max := -无穷大
- 对于 i in range 0 到 n，执行：
- tmp := s * a[i] + t * b[i] + i
- cur_min := cur_min 和 tmp 中的最小值
- cur_max := cur_max 和 tmp 中的最大值
- ans := ans 和 (cur_max - cur_min) 中的最大值
- 返回 ans
让我们看看下面的实现，以便更好地理解：
示例
class Solution:
def solve(self, a, b):
ans = 0
n = len(a)
for s, t in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
cur_min = float("inf")
cur_max = float("-inf")
for i in range(n):
tmp = s * a[i] + t * b[i] + i
cur_min = min(cur_min, tmp)
cur_max = max(cur_max, tmp)
ans = max(ans, cur_max - cur_min)
return ans
ob = Solution()
A = [2, 4, 10, 6]
B = [3, 4, 7, 5]
print(ob.solve(A, B))输入
[2, 4, 10, 6],[3, 4, 7, 5]
输出
14
更新于: 2020年11月19日
127 次浏览
广告