[已解决]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 楼的基础上做了点微调

def f269(A, target):
    if A == []:
        return -1

    raw = len(A)
    col = max(A) + 1
    f = [abs(A[0]-i) for i in range(col)]
    for r in range(1, raw):
        tmp = [float("inf")] * col
        for c in range(col):                                                # c: 供 A 中元素调整的数字
            if f[c] != float("inf"):
                for k in range(max(0, c-target), min(c+target, col-1)+1):   # 若 A[r-1] 调为了 c，则 k 为 A[r] 可以调的数字
                    tmp[k] = min(tmp[k], f[c]+abs(A[r]-k))                  # tmp[k]: 把 A[r] 调为 k 的最小代价
        f = tmp[:]
    return min(f)

跳转到最佳答案楼层

Unicorn#

难搞...

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

zltzlt

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

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

仔细看题

给一个整数数组

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

Will_M

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

零0℃度

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

def f269(A, target):
    m = max(A)+1
    f = [[sys.maxsize for j in range(m)] for i in range(len(A)+1)]
    for i in range(m):
        f[0][i] = 0
    n = len(A)
    for i in range(1, n+1):
        for j in range(m):
            if f[i-1][j] != sys.maxsize:
                for k in range(m):
                    if abs(j-k) <= target:
                        f[i][k] = min(f[i][k], f[i-1][j] + abs(A[i-1]-k))
    return min(f[n])

fish_b

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

def filter(listA,target):
    '一定有一个数字不用变 -》 穷举哪一个数字不变'
    min_count=0
    for x in range(0,len(listA)):
        count=0
        a = listA[:]
        i = x
        while i >0:
            dif = a[i] - a[i-1]
            if abs(dif)>target:
                count += abs(dif) - target
                if dif < 0: # a[i]比较小
                    a[i - 1] = a[i]  + target
                else:
                    a[i - 1] = a[i]  - target
            i -= 1

        i = x
        while i < len(listA)-1:
            dif = a[i] - a[i + 1]
            if abs(dif) > target:
                count += abs(dif) - target
                if dif < 0:
                    a[i + 1] = a[i] + target
                else:
                    a[i + 1] = a[i] - target
            i += 1

        if x == 0:
            min_count = count
            result = a
        elif count < min_count:
            min_count = count
            result = a

    print(result)
    print(min_count)
    return(min_count)

阴阳神万物主

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

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

danteer

def func(list1,target):
    result = []
    list2 = list1.copy()
    for each in range(len(list1)):
        temp = 0
        if each == 0:
            for i in range(1,len(list1)):
                if abs(list1[i] - list1[i-1]) > target:
                    if list1[i] > list1[i-1]:
                        list1[i] = list1[i-1] + target
                        temp += list2[i] - list1[i]
                    else:
                        list1[i] = list1[i-1] - target
                        temp += list1[i] - list2[i]
        elif each == len(list1) - 1:
            for i in range(len(list1)-2,0,-1):
                if abs(list1[i] - list1[i+1]) > target:
                    if list1[i] > list1[i+1]:
                        list1[i] = list1[i+1] + target
                        temp += list2[i] - list1[i]
                    else:
                        list1[i] = list1[i+1] - target
                        temp += list1[i] - list2[i]
        else:
            for i in range(each-1,0,-1):
                if abs(list1[i] - list1[i+1]) > target:
                    if list1[i] > list1[i+1]:
                        list1[i] = list1[i+1] + target
                        temp += list2[i] - list1[i]
                    else:
                        list1[i] = list1[i+1] - target
                        temp += list1[i] - list2[i]
            for j in range(each+1,len(list1)):
                if abs(list1[i] - list1[i-1]) > target:
                    if list1[i] > list1[i-1]:
                        list1[i] = list1[i-1] + target
                        temp += list2[i] - list1[i]
                    else:
                        list1[i] = list1[i-1] - target
                        temp += list1[i] - list2[i]
        result.append(temp)
        return min(result)

哆啦蓝胖

题都看不太懂

hccdpt_

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

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

1111

Unicorn#

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

def solve(nums, target):
    n = len(nums)
    record = [0]*n
    signal = lambda x:1 if x>0 else -1
    for i in range(n-1):
        r = nums[i+1]-nums[i]
        if abs(r) > target:
            nums[i+1] = nums[i] + signal(r)*target
            record[i+1] += signal(r)*target - r
    p = int(sum(record)/n)
    ans = sum(abs(record[i]-p) for i in range(n))
    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 楼的基础上做了点微调

def f269(A, target):
    if A == []:
        return -1

    raw = len(A)
    col = max(A) + 1
    f = [abs(A[0]-i) for i in range(col)]
    for r in range(1, raw):
        tmp = [float("inf")] * col
        for c in range(col):                                                # c: 供 A 中元素调整的数字
            if f[c] != float("inf"):
                for k in range(max(0, c-target), min(c+target, col-1)+1):   # 若 A[r-1] 调为了 c，则 k 为 A[r] 可以调的数字
                    tmp[k] = min(tmp[k], f[c]+abs(A[r]-k))                  # tmp[k]: 把 A[r] 调为 k 的最小代价
        f = tmp[:]
    return min(f)

__mrsq__

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

zltzlt

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

恭喜通过！

执行用时：912 ms