类似直播平台网站的建设费用,聊城做网站低费用,学生如何自己做网站,成都犀牛网站建设Leetcode 2967. Minimum Cost to Make Array Equalindromic 1. 解题思路2. 代码实现 题目链接#xff1a;2967. Minimum Cost to Make Array Equalindromic
1. 解题思路
这一题其实我的思路有点笨#xff0c;多少有点暴力求解的意思。
显然#xff0c;如果我们给出全部的…Leetcode 2967. Minimum Cost to Make Array Equalindromic 1. 解题思路2. 代码实现 题目链接2967. Minimum Cost to Make Array Equalindromic
1. 解题思路
这一题其实我的思路有点笨多少有点暴力求解的意思。
显然如果我们给出全部的对称数并将其有序排列那么对于其中每一个对称数作为目标值时的cost就是一个包含一个最小值的先减后增有序数列而我们要做的就是求这个最小值。
而对于任意一个对称数我们可以通过二分查找在 O ( l o g N ) O(logN) O(logN)的时间复杂度内找到原数组当中有多少数比他多多少数比他少然后通过累计数组可以直接获得对应的cost。
这些其实都还好只是原则上感觉对于第一部分对于这么有规律的东西应该有更好的算法可以更快找到最小值的不过这里我暂时没想到就直接遍历寻找了所以感觉多少有点蠢了……
2. 代码实现
给出python代码实现如下
lru_cache(None)
def get_palindromes():ans [0]for i in range(1, 10**6):s str(i)a int(s s[::-1])if a 10**9:ans.append(a)b int(s s[:-1][::-1])if b 10**9:ans.append(b)return sorted(ans)class Solution:def minimumCost(self, nums: List[int]) - int:n len(nums)nums sorted(nums)sums [0] list(accumulate(nums))palindromes get_palindromes()ans sums[-1]for x in palindromes:idx bisect.bisect_right(nums, x)s x * idx - (sums[idx] - sums[0]) (sums[-1] - sums[idx]) - x * (n-idx)if ans s:ans selse:breakreturn ans提交代码评测得到耗时2414ms占用内存35.7MB。
