金三银四复工高频面试题java算法LeetCode396旋转函数

目录
  • 题目描述
  • 前缀和 + 滑动窗口
  • 最后

题目描述

这是 LeetCode 上的 396. 旋转函数 ，难度为 中等。

Tag : 「前缀和」、「滑动窗口」

给定一个长度为 n 的整数数组 nums

F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]

返回 F(0), F(1), ..., F(n-1) 中的最大值 。

生成的测试用例让答案符合 32 位 整数。

示例 1:

输入: nums = [4,3,2,6]

输出: 26

解释:
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。

示例 2:

输入: nums = [100]

输出: 0

提示:

前缀和 + 滑动窗口

为了方便，我们将 numsnumsnums 的长度记为 nnn。

实现上，我们并不需要真正对 nums 进行复制拼接，而只需要在计算前缀和数组 sum 进行简单的下标处理即可。

代码：

class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n * 2 + 10];
        for (int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + nums[(i - 1) % n];
        int ans = 0;
        for (int i = 1; i <= n; i++) ans += nums[i - 1] * (i - 1);
        for (int i = n + 1, cur = ans; i < 2 * n; i++) {
            cur += nums[(i - 1) % n] * (n - 1);
            cur -= sum[i - 1] - sum[i - n];
            if (cur > ans) ans = cur;
        }
        return ans;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.396 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

以上就是金三银四复工高频面试题java算法LeetCode396旋转函数的详细内容，更多关于java算法LeetCode旋转函数的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • java LeetCode普通字符串模拟题解示例

    目录 题目描述 模拟 最后 题目描述 这是 LeetCode 上的 393. UTF-8 编码验证 ,难度为 中等. Tag : 「模拟」 给定一个表示数据的整数数组 data ,返回它是否为有效的 UTF−8 编码. UTF-8 中的一个字符可能的长度为 1 到 4 字节,遵循以下的规则: 对于 1字节 的字符,字节的第一位设为 0,后面 7 位为这个符号的 unicode 码. 对于 n 字节 的字符 (n>1),第一个字节的前 n 位都设为 1,第 n+1 位设为 0 ,后面字节的前两位一

  • Java C++题解leetcode816模糊坐标示例

    目录 题目 思路:枚举 Java C++ Rust 总结 题目 题目要求 思路:枚举 既然要输出每种可能了,那必然不能“偷懒”,就暴力枚举咯: 在每个间隔处添加逗号: 定义函数decPnt(sta, end)分别列举逗号左右两边的数能构成的可能性: 同样在每个间隔添加小数点: 注意两种不合法的结构——前导0和后缀0: 不要忘记无小数点的整数版本, 分别组合两边的不同可能性,根据要求各式加入答案. Java class Solution { String str; public List<Stri

  • Java C++题解leetcode1620网络信号最好的坐标

    目录 题目 思路:暴力模拟 Java C++ Rust 题目 题目要求 思路:暴力模拟 因为数据范围小,所以是万万没想到的逐个遍历…… 遍历每个塔,然后找每个塔辐射的范围,用一个大矩阵记录每个点对应的信号大小,同时维护当前最大的信号及其对应坐标. Java class Solution { public int[] bestCoordinate(int[][] towers, int radius) { int[][] grid = new int[110][110]; int cx = 0,

  • Java C++刷题leetcode1106解析布尔表达式

    目录 题目 思路:栈[计算器] Java C++ Rust 总结 题目 题目要求 思路:栈[计算器] 和计算器原理类似,分别用两个栈存操作数和操作符,然后到)就开始运算前面的内容,括号里运算都相同所以还是比较简单的. 要注意字母t.f和布尔值true.false的转换. Java class Solution { public boolean parseBoolExpr(String expression) { Deque<Character> tfs = new ArrayDeque<

  • 全面了解OAuth 2.0四种授权方式金三银四无惧面试

    目录 首先 第一种授权方式:授权码 第二种方式:隐藏式 第三种方式:密码式 第四种方式:凭证式 首先 我们需要清楚 OAuth 是什么? OAuth 引入了一个授权层,用来分离两种不同的角色:客户端和资源所有者.......资源所有者同意以后,资源服务器可以向客户端颁发令牌.客户端通过令牌,去请求数据. 上面这段话的意思就是:OAuth 的核心就是向第三方应用颁发令牌. 由于互联网有多种场景,OAuth 2.0 规定了四种获得令牌的流程,你可以选择最适合自己的那一种,向第三方应用颁发令牌. 下面

  • 面试题:Java 实现查找旋转数组的最小数字

    在算法面试中,面试官总是喜欢围绕链表.排序.二叉树.二分查找来做文章,而大多数人都可以跟着专业的书籍来做到倒背如流.而面试官并不希望招收的是一位记忆功底很好,但不会活学活用的程序员.所以学会数学建模和分析问题,并用合理的算法或数据结构来解决问题相当重要. 面试题:打印出旋转数组的最小数字 题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素.例如数组 {3,4,5,1,2} 为数组 {1,2,3,4,5} 的一个旋转,该

  • 几个MySQL高频面试题的解答

    几个MySQL高频面试题的解答

    前言: 在各类技术岗位面试中,似乎 MySQL 相关问题经常被问到.无论你面试开发岗位或运维岗位,总会问几道数据库问题.经常有小伙伴私信我,询问如何应对 MySQL 面试题.其实很多面试题都是大同小异的,提前做准备还是很有必要的.本篇文章简单说下几个常见的面试题,一起来学习下吧. 1.什么是关系型数据库?谈谈你对 MySQL 的认识. 这是一道基础题,考察面试者对数据库的了解程度,一般可以简单讲下自己的认知,有条理即可.比如: 关系型数据库是指采用了关系模型来组织数据的数据库,其以行和列的形式存

  • 三十四、 WIN2000注册表应用九例

    三十四. WIN2000注册表应用九例 我们知道,与Windows 9x操作系统相似,在Windows 2000中,配置信息也是集中存储在注册表这个数据库里,但比较不同的是在Windows 9x中用来修改注册表文件的注册表编辑器是regedit.exe,而在Windows 2000中,要修改Registry数据库你可以使用两种"注册表编辑器"来进行编辑:一个是regedit.exe,而另一个则是regedt32.exe.前者可以在Windows 2000的安装目录\WINNT下找到,后

  • 几天洗一次头最健康(中医建议每星期洗三至四次头)

    首先测试一下你的头发是否健康吧!   光泽度测试 操作方法:中分清洁后的头发,梳平梳顺.在正对面放一面镜子,位置以自己能够清楚看到头顶为准.使灯光从头顶射下来,形成一个皇冠似的圆晕. 推断:圆晕越亮,头发光泽度越好. 韧度测试 操作方法:在洗头之前,剪下一束大约一寸长的头发,再将其置入水中. 推断:发质的好坏,在30秒钟内就能看出来.发质差的头发容易吸水下沉得快.如果你的头发直线下沉,那么你该注意头发的养护了. 顺滑测试 操作方法:用梳子从上到下梳理头发.握住一把头发的末梢,用力搓揉它们,然后看

  • 九个Python列表生成式高频面试题汇总

    目录 1. 引言 2. 字符串转整数 3. 大于10的数字 4. 大于10且整除3的数字 5. 对列表中的偶数执行加1操作 6. 包含数字1的数字 7. 合并两个列表 8. 根据value对字典排序 9. 求两个列表的元素组合 10. 列表中两个元素的唯一组合,其和为3的倍数 11. 总结 1. 引言 之前已经有博客专门介绍了Python中的列表生成式,可能大家还不太擅长.这里推荐九个Python列表生成式的面试题(从简单到困难排序),可以帮助大家提高列表生成式的理解水平. 闲话少说,我们直接开

  • JS面试题---关于算法台阶的问题

    有100格台阶,可以跨1步可以跨2步,那么一个有多少种走法: 今天电话面试.遇到一道算法问题,然后瞬间一脸懵逼: 然后机智的我,自作聪明的想到如果一个人每次都走1步,那么最多100步,每次走2步最少50步:然后明显跑题了...还好对方及时把我打断了...不然我估计要对着这玩意一直死脑经...一路走到黑.. 然后回到家了.拿着偶的mac,然后静静的思考,终于写出来了 var Stairs = new step(); function step(){ this.n1=1; this.n2=2; th

  • 面试题:java中为什么foreach中不允许对元素进行add和remove

    面试题:java中为什么foreach中不允许对元素进行add和remove

    目录 1.foreach遍历ArrayList过程中使用 add 和 remove 2.追根溯源 2.1.modCount是什么? 2.2.expectedModCount 是什么? 2.3.熟悉的checkForComodification方法 2.4.流程回顾 3.避免fail-fast 机制 3.1.使用listIterator或iterator 3.2.使用CopyOnWriteArrayList 3.2.1.CopyOnWriteArrayList的add方法 3.2.2.CopyOn

  • java算法题解Leetcode15三数之和实例

    目录 题目 解题思路 题目 15. 三数之和 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例 1:输入:nums = [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]示例 2:输入:nums = []输出:[]示例 3:输入:nums = [0]输出:[]提示:0 <= nums.length <=

  • 2019最新21个MySQL高频面试题介绍

    今天给大家分享 21 个 MySQL 面试题. 1.Mysql中有哪几种锁? MyISAM 支持表锁,InnoDB 支持表锁和行锁,默认为行锁. 表级锁:开销小,加锁快,不会出现死锁.锁定粒度大,发生锁冲突的概率最高,并发量 最低. 行级锁:开销大,加锁慢,会出现死锁.锁力度小,发生锁冲突的概率小,并发度最高. 2.Mysql支持事务吗? 在缺省模式下,MYSQL 是 autocommit 模式的,所有的数据库更新操作都会即时提交,所 以在缺省情况下,mysql 是不支持事务的. 但是如果你的

随机推荐