栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

16、移动石子

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

16、移动石子

问题描述

在x轴上分布着n个石子,用arr数组表示他们的位置,把这些石子移动到1,3,5,7,2n-1或者2,4,6,8,2n
也就是说这些石子移动到从1开始连续的奇数位或从2开始连续的偶数位上,返回最少的移动次数,每次只可以移动1个石子,只能把石子往左或
往右移动1个位置,同一个位置不能有两个石子。

问题示例

输入[5,4,1],只需把4移动到3,只需一步,
输入[1,6,7,8,9],最优移动方案位把1移动到2,把6移动到4,把7移动到6,把9移动到10,需要5步。

# 代码示例
#方法1:分别创建奇数列表和偶数列表,然后用两个列表分别减arr相同位置的值
class Solution1:
    def move_count(self,arr):
        arr = sorted(arr)
        one = [i for i in range(1, 2 * len(arr), 2)]#奇数列表
        two = [i for i in range(2, 2 * len(arr) + 1, 2)]#偶数列表
        one_count = 0
        two_count = 0
        for c in range(len(arr)):
            one_count += abs(one[c]-arr[c])
            two_count += abs(two[c]-arr[c])
        if one_count > two_count:
            return two_count
        return one_count

arr1 = [5,4,1]
arr2 = [1,6,7,8,9]
s1 = Solution1()
print("方法1:",s1.move_count(arr1))
print("方法1:",s1.move_count(arr2))
# 方法2:arr减相应位置的等差数列
class Solution2:
    def move_count(self,arr):
        arr = sorted(arr)
        one_count = 0
        two_count = 0
        for c in range(len(arr)):
            one_count += abs(arr[c]-(2*c+1))
            two_count += abs(arr[c]-(2*c+2))
        if one_count < two_count:
            return one_count
        return two_count

s2 = Solution2()
print("方法2:",s2.move_count(arr1))
print("方法2:",s2.move_count(arr2))

结果:

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/314087.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号