[已解决]Python：每日一题 269

zltzlt

今天的题目：

给一个整数数组，调整每个数的大小，使得相邻的两个数的差不大于一个给定的整数 target。

调整每个数的代价为调整前后的差的绝对值（例如 4 被调整为 2，那么这个数的调整代价就是 2，因为 abs(4 - 2) == 2），求调整代价之和最小是多少。

示例 1:

输入:  [1,4,2,3], target=1
输出:  2

示例 2:

输入:  [3,5,4,7], target=2
输出:  1

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

华一仙

2019-11-6 22:45:37

懒得动脑筋了，在 5 楼的基础上做了点微调

1. def f269(A, target):
   
2.     if A == []:
   
3.         return -1
   
4. 
   
5.     raw = len(A)
   
6.     col = max(A) + 1
   
7.     f = [abs(A[0]-i) for i in range(col)]
   
8.     for r in range(1, raw):
   
9.         tmp = [float("inf")] * col
   
10.         for c in range(col):                                                # c: 供 A 中元素调整的数字
    
11.             if f[c] != float("inf"):
    
12.                 for k in range(max(0, c-target), min(c+target, col-1)+1):   # 若 A[r-1] 调为了 c，则 k 为 A[r] 可以调的数字
    
13.                     tmp[k] = min(tmp[k], f[c]+abs(A[r]-k))                  # tmp[k]: 把 A[r] 调为 k 的最小代价
    
14.         f = tmp[:]
    
15.     return min(f)
    

复制代码

跳转到最佳答案楼层

Unicorn#

难搞...

调整后的值可以是浮点数吗

zltzlt

Unicorn# 发表于 2019-11-5 22:07
难搞...

调整后的值可以是浮点数吗

仔细看题

给一个整数数组

这意味调整后的数组也应该是整数数组。

Will_M

感觉这道题更侧重于考数学知识啊，各种排列组合，选取最优的一组，只要懂了数学原理，写代码就简单了，我希望有人能来讲解一下其中的数学原理。。。。

零0℃度

网上看了下   需要动态规划，跟前面的书包题一样的，都是动态规划，用二维数组，  这个不会  ，网上都是 C++ 的代码  看了下 用python写还是很简单的 就是理解不了，自己折腾玩  没有学过算法

1. def f269(A, target):
   
2.     m = max(A)+1
   
3.     f = [[sys.maxsize for j in range(m)] for i in range(len(A)+1)]
   
4.     for i in range(m):
   
5.         f[0][i] = 0
   
6.     n = len(A)
   
7.     for i in range(1, n+1):
   
8.         for j in range(m):
   
9.             if f[i-1][j] != sys.maxsize:
   
10.                 for k in range(m):
    
11.                     if abs(j-k) <= target:
    
12.                         f[i][k] = min(f[i][k], f[i-1][j] + abs(A[i-1]-k))
    
13.     return min(f[n])

复制代码

fish_b

来自新手的参与
我可能没有穷尽每种可能性，但目前就这样吧

1. 
   
2. def filter(listA,target):
   
3.     '一定有一个数字不用变 -》 穷举哪一个数字不变'
   
4.     min_count=0
   
5.     for x in range(0,len(listA)):
   
6.         count=0
   
7.         a = listA[:]
   
8.         i = x
   
9.         while i >0:
   
10.             dif = a[i] - a[i-1]
    
11.             if abs(dif)>target:
    
12.                 count += abs(dif) - target
    
13.                 if dif < 0: # a[i]比较小
    
14.                     a[i - 1] = a[i]  + target
    
15.                 else:
    
16.                     a[i - 1] = a[i]  - target
    
17.             i -= 1
    
18. 
    
19.         i = x
    
20.         while i < len(listA)-1:
    
21.             dif = a[i] - a[i + 1]
    
22.             if abs(dif) > target:
    
23.                 count += abs(dif) - target
    
24.                 if dif < 0:
    
25.                     a[i + 1] = a[i] + target
    
26.                 else:
    
27.                     a[i + 1] = a[i] - target
    
28.             i += 1
    
29. 
    
30.         if x == 0:
    
31.             min_count = count
    
32.             result = a
    
33.         elif count < min_count:
    
34.             min_count = count
    
35.             result = a
    
36. 
    
37.     print(result)
    
38.     print(min_count)
    
39.     return(min_count)
    

复制代码

阴阳神万物主

Will_M 发表于 2019-11-5 22:43
感觉这道题更侧重于考数学知识啊，各种排列组合，选取最优的一组，只要懂了数学原理，写代码就简单了，我希 ...

仅仅排列组合，那可没用，示例2 那里，处理完之后能出现新的数字

danteer

1. def func(list1,target):
   
2.     result = []
   
3.     list2 = list1.copy()
   
4.     for each in range(len(list1)):
   
5.         temp = 0
   
6.         if each == 0:
   
7.             for i in range(1,len(list1)):
   
8.                 if abs(list1[i] - list1[i-1]) > target:
   
9.                     if list1[i] > list1[i-1]:
   
10.                         list1[i] = list1[i-1] + target
    
11.                         temp += list2[i] - list1[i]
    
12.                     else:
    
13.                         list1[i] = list1[i-1] - target
    
14.                         temp += list1[i] - list2[i]
    
15.         elif each == len(list1) - 1:
    
16.             for i in range(len(list1)-2,0,-1):
    
17.                 if abs(list1[i] - list1[i+1]) > target:
    
18.                     if list1[i] > list1[i+1]:
    
19.                         list1[i] = list1[i+1] + target
    
20.                         temp += list2[i] - list1[i]
    
21.                     else:
    
22.                         list1[i] = list1[i+1] - target
    
23.                         temp += list1[i] - list2[i]
    
24.         else:
    
25.             for i in range(each-1,0,-1):
    
26.                 if abs(list1[i] - list1[i+1]) > target:
    
27.                     if list1[i] > list1[i+1]:
    
28.                         list1[i] = list1[i+1] + target
    
29.                         temp += list2[i] - list1[i]
    
30.                     else:
    
31.                         list1[i] = list1[i+1] - target
    
32.                         temp += list1[i] - list2[i]
    
33.             for j in range(each+1,len(list1)):
    
34.                 if abs(list1[i] - list1[i-1]) > target:
    
35.                     if list1[i] > list1[i-1]:
    
36.                         list1[i] = list1[i-1] + target
    
37.                         temp += list2[i] - list1[i]
    
38.                     else:
    
39.                         list1[i] = list1[i-1] - target
    
40.                         temp += list1[i] - list2[i]
    
41.         result.append(temp)
    
42.         return min(result)

复制代码

哆啦蓝胖

题都看不太懂

hccdpt_

Unicorn# 发表于 2019-11-5 22:07
难搞...

调整后的值可以是浮点数吗

1111

Unicorn#

明白了，这题用不到dp算法吧

1. def solve(nums, target):
   
2.     n = len(nums)
   
3.     record = [0]*n
   
4.     signal = lambda x:1 if x>0 else -1
   
5.     for i in range(n-1):
   
6.         r = nums[i+1]-nums[i]
   
7.         if abs(r) > target:
   
8.             nums[i+1] = nums[i] + signal(r)*target
   
9.             record[i+1] += signal(r)*target - r
   
10.     p = int(sum(record)/n)
    
11.     ans = sum(abs(record[i]-p) for i in range(n))
    
12.     print(ans)

复制代码

zltzlt

零0℃度 发表于 2019-11-5 22:59
网上看了下   需要动态规划，跟前面的书包题一样的，都是动态规划，用二维数组，  这个不会  ，网上都是 C+ ...

恭喜通过！

执行用时：1298 ms

zltzlt

fish_b 发表于 2019-11-6 09:22
来自新手的参与
我可能没有穷尽每种可能性，但目前就这样吧

解答错误

输入：[51,62,81,14,15,39,63,38,48,94,42,91,91,81,91,40,67,66,82,16], target = 20
打印：[51, 54, 34, 14, 19, 39, 59, 39, 48, 68, 48, 68, 88, 81, 91, 71, 67, 66, 82, 62]
199
输出：199
预期结果：188

zltzlt

danteer 发表于 2019-11-6 13:12

解答错误

输入：[12,3,7,4,5,13,2,8,4,7,6,5,7], target = 2
输出：21
预期结果：19

zltzlt

Unicorn# 发表于 2019-11-6 19:03
明白了，这题用不到dp算法吧

解答错误

输入：[12,3,7,4,5,13,2,8,4,7,6,5,7], target = 2
输出：21
预期结果：19

华一仙

懒得动脑筋了，在 5 楼的基础上做了点微调

1. def f269(A, target):
   
2.     if A == []:
   
3.         return -1
   
4. 
   
5.     raw = len(A)
   
6.     col = max(A) + 1
   
7.     f = [abs(A[0]-i) for i in range(col)]
   
8.     for r in range(1, raw):
   
9.         tmp = [float("inf")] * col
   
10.         for c in range(col):                                                # c: 供 A 中元素调整的数字
    
11.             if f[c] != float("inf"):
    
12.                 for k in range(max(0, c-target), min(c+target, col-1)+1):   # 若 A[r-1] 调为了 c，则 k 为 A[r] 可以调的数字
    
13.                     tmp[k] = min(tmp[k], f[c]+abs(A[r]-k))                  # tmp[k]: 把 A[r] 调为 k 的最小代价
    
14.         f = tmp[:]
    
15.     return min(f)
    

复制代码

__mrsq__

看了5楼的解法，感觉dp真的太好用了！状态更新判定条件那步感觉很妙，完美消除改变后面元素对前面元素的影响！感觉自己要修炼好久才能有思路写出这种代码！

zltzlt

华一仙 发表于 2019-11-6 22:45
懒得动脑筋了，在 5 楼的基础上做了点微调

恭喜通过！

执行用时：912 ms