资讯专栏INFORMATION COLUMN

总结各类题目中的数学奇技淫巧(?)

zsy888 / 2192人阅读

摘要:所以说,要使所有数相等,可以等价转换为所有数都减到和一样大。于是思路变成了找到累加每个数与的差值。于是只需要一次遍历,一边求和,一边找到,最后返回即可。

LC453

这是准备coursera OA遇到的一个easy却有趣的题,一开始我想的是先排序,然后不停找出最小值,前n-1个数加1...总之就是时间复杂度太高无法AC,这时候我觉得无法AC的easy题肯定是要用一些数学上的巧办法了,google之,于是整理如下:
每做一次move,相当于除了最后一位数之外所有数+1,换个角度想其实是最后一位数-1: [1,2,3] ---> [2, 2, 3] = [1, 2, 2]效果是一样的。所以说,要使所有数相等,可以等价转换为所有数都减到和min一样大。于是思路变成了“找到min -> 累加每个数与min的差值”。继续优化,因为找到Min至少需要一次遍历,累加又是一次遍历,有没有办法同一次遍历搞定所有事情呢?很简单,对于数组[a1,a2,a3,...,an] 累加 (a1 - min) + (a2 - min) + (a3 - min) + ... + (an - min) = ∑a - n x min(sf怎么打星号就变成了斜体...)。 于是只需要一次遍历,一边求和,一边找到Min,最后返回sum - nums.length x min即可。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/68358.html

相关文章

  • 魔幻语言 JavaScript 系列之类型转换、宽松相等以及原始值

    摘要:通过使用其构造函数,可以将一个值的类型转换为另一种类型。如果使用两次,可用于将该值转换为相应的布尔值。 编译自:[1] + [2] – [3] === 9!? Looking into assembly code of coercion.全文从两个题目来介绍类型转换、宽松相等以及原始值的概念: [1] + [2] – [3] === 9 如果让 a == true && a == fa...

    li21 评论0 收藏0
  • CSS开发

    摘要:译十六进制颜色揭秘原文地址原文作者译文出自掘金翻译计划本文永久链接教程入门篇关于是一款进行栅格布局的辅助工具,它让开发者摆脱了冗杂的数学计算,同时降低了样式与结构的耦合程度。 【译】CSS 十六进制颜色揭秘 原文地址:CSS Hex Colors Demystified 原文作者:Dave Gash 译文出自:掘金翻译计划 本文永久链接:https://github.com/xitu/...

    warkiz 评论0 收藏0
  • 个人分享--web前端学习资源分享

    摘要:前言月份开始出没社区,现在差不多月了,按照工作的说法,就是差不多过了三个月的试用期,准备转正了一般来说,差不多到了转正的时候,会进行总结或者分享会议那么今天我就把看过的一些学习资源主要是博客,博文推荐分享给大家。 1.前言 6月份开始出没社区,现在差不多9月了,按照工作的说法,就是差不多过了三个月的试用期,准备转正了!一般来说,差不多到了转正的时候,会进行总结或者分享会议!那么今天我就...

    sherlock221 评论0 收藏0
  • 你真的会写hello world的么?

    摘要:现如今编程这个行当,也约定俗成出了一个入行仪式,就是选你将要使用的编程语言,写段代码输出,这片文章讲的就是这么个事写个函数输出,请真的不要觉得很简单。但每行两个字符的限制,是把函数创建的生门堵死了。 自古,三百六十行,每一行入行的时候都有个仪式。现如今编程这个行当,也约定俗成出了一个入行仪式,就是选你将要使用的编程语言,写段代码输出hello world!,这片文章讲的就是这么个事——...

    tianhang 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<