Leetcode力扣秋招刷题路-0189

这篇具有很好参考价值的文章主要介绍了Leetcode力扣秋招刷题路-0189。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结

189. 轮转数组

给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:
输入:nums = [-1,-100,3,99], k = 2
输出:[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示:
1 <= nums.length <= 1 0 5 10^5 105
− 2 31 -2^{31} 231 <= nums[i] <= 2 31 − 1 2^{31} - 1 2311
0 <= k <= 1 0 5 10^5 105

进阶:
尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

思路
从nums[0]开始,放到该数的新位置(0 + k),然后再寻找该位置值的新位置,直至回到0时结束。 但是该方法不能保证遍历完所有的位置,如 7 位的数组后移3个位置只需遍历一遍,而 6 位的数组后移4个位置需要遍历两遍(再从i = 1开始)。 可以发现这个遍历的次数就是数组长度和k的最大公约数。

代码文章来源地址https://www.toymoban.com/news/detail-415163.html

public void rotate(int[] nums, int k) {
    int len = nums.length;
    for (int i = 0;i < gcd(k, len);i++){
        int idx = (k + i) % len, num = nums[i];
        while (idx != i){
            int item = nums[idx];
            nums[idx] = num;
            idx = (idx + k) % len;
            num = item;
        }
        nums[i] = num;
    }
}

private int gcd(int a, int b) {
    return a % b == 0 ? b : gcd(b % a, a);
}

到了这里,关于Leetcode力扣秋招刷题路-0189的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode力扣秋招刷题路-0721

    从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 给定一个列表 accounts,每个元素 accounts[i] 是一个字符串列表,其中第一个元素 accounts[i][0] 是 名称 (name),其余元素是 emails 表示该账户的邮箱地址。 现在,我们想合并这些账户。如果两个账户都有一些共同

    2023年04月27日
    浏览(76)
  • Leetcode力扣秋招刷题路-0447

    从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 给定平面上 n 对 互不相同 的点 points ,其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ,其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等(需要考虑元组的顺序)。 返回平面上所有回旋镖的

    2023年04月22日
    浏览(62)
  • 07 Linux补充|秋招刷题|9月6日

    Linux 结构体内存字节对齐 静态变量static 空指针 结构体内存字节要对⻬: 32位系统:4 8 32;64位系统:8 16 24 字节对⻬:字节对⻬是指在计算机中,各种类型数据按照⼀定的规则在空间上排列,以满⾜硬件平台对存储空间的处理要求。 (1)在修饰变量的时候,static 修饰的静

    2024年02月09日
    浏览(28)
  • 从零开始的力扣刷题记录-第四十天

    题目描述: 给定一个整数 num,将其转化为 7 进制,并以字符串形式输出。 题解: 其实和二进制转换是一样的,除以7取余再倒序取出结果就可以了 代码(Go): 题目描述: 给你两个字符串 s 和 goal ,只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果,就返回 t

    2024年02月06日
    浏览(29)
  • 从零开始的力扣刷题记录-第四十八天

    给你一个下标从 0 开始的数组 nums ,数组大小为 n ,且由 非负 整数组成。 你需要对数组执行 n - 1 步操作,其中第 i 步操作(从 0 开始计数)要求对 nums 中第 i 个元素执行下述指令: 如果 nums[i] == nums[i + 1] ,则 nums[i] 的值变成原来的 2 倍,nums[i + 1] 的值变成 0 。否则,跳过

    2024年02月09日
    浏览(38)
  • 从零开始的力扣刷题记录-第三十九天

    题目描述: 给定一个 无重复元素 的 有序 整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中的每个区间范围 [a,b] 应该按如下格式输

    2024年02月06日
    浏览(33)
  • 从零开始的力扣刷题记录-第六十二天

    题目描述: 给你一个非负整数数组 nums 。在一步操作中,你必须: 选出一个正整数 x ,x 需要小于或等于 nums 中 最小 的 非零 元素。 nums 中的每个正整数都减去 x。 返回使 nums 中所有元素都等于 0 需要的 最少 操作数。 题解: 由于每次都要减去一个最小的非零元素,可以想

    2024年02月11日
    浏览(37)
  • 从零开始的力扣刷题记录-第七十二天

    题目描述: 给你一个整数数组 nums ,它包含 2 * n 个整数。 你需要将 nums 划分成 n 个数对,满足: 每个元素 只属于一个 数对。 同一数对中的元素 相等 。 如果可以将 nums 划分成 n 个数对,请你返回 true ,否则返回 false 题解: 哈希表统计各元素数量,如果有不能被2整除的就

    2024年02月11日
    浏览(35)
  • 从零开始的力扣刷题记录-第四十二天

    题目描述: 给你长度相等的两个字符串 s1 和 s2 。一次 字符串交换 操作的步骤如下:选出某个字符串中的两个下标(不必不同),并交换这两个下标所对应的字符。 如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等,返回 true ;否则,返回 false 。

    2024年02月06日
    浏览(42)
  • 从零开始的力扣刷题记录-第八十七天

    题目描述: 给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字: 例如,从根节点到叶节点的路径 1 - 2 - 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。 叶节点 是指没有子节点的节点

    2024年02月07日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包