网站开发如何共用菜单栏require,江苏省工程建设标准网站,域名是干什么的,最吸引人的广告图片【力扣】189. 轮转数组 文章目录 【力扣】189. 轮转数组1. 题目介绍2. 解法2.1 方法一#xff1a;不太正规#xff0c;但是简单2.2 方法二#xff1a;使用额外的数组2.3 方法三#xff1a;环状替换2.4 方法四#xff1a;数组翻转 3. Danger参考 1. 题目介绍
给定一个整数…【力扣】189. 轮转数组 文章目录 【力扣】189. 轮转数组1. 题目介绍2. 解法2.1 方法一不太正规但是简单2.2 方法二使用额外的数组2.3 方法三环状替换2.4 方法四数组翻转 3. Danger参考 1. 题目介绍
给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。 2. 解法
2.1 方法一不太正规但是简单
class Solution:def rotate(self, nums: List[int], k: int) - None:Do not return anything, modify nums in-place instead.k k % len(nums)for i in range(k):tem nums.pop()nums.insert(0, tem)return nums2.2 方法二使用额外的数组
我们可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度我们遍历原数组将原数组下标为 i 的元素放至新数组下标为(ik) mod n 的位置最后将新数组拷贝至原数组即可。
class Solution {
public:void rotate(vectorint nums, int k) {int n nums.size();vectorint newArr(n);for (int i 0; i n; i) {newArr[(i k) % n] nums[i];}nums.assign(newArr.begin(), newArr.end());}
};2.3 方法三环状替换
需要了解一个定理环的个数等于gcd(k, n)
class Solution {
public:void rotate(vectorint nums, int k) {int n nums.size();k k % n;int count gcd(k, n);for (int start 0; start count; start) {int current start;int prev nums[start];do {int next (current k) % n;swap(nums[next], prev);current next;} while (start ! current);}}
};2.4 方法四数组翻转 class Solution {
public:void reverse(vectorint nums, int start, int end) {while (start end) {swap(nums[start], nums[end]);start 1;end - 1;}}void rotate(vectorint nums, int k) {k % nums.size();reverse(nums, 0, nums.size() - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.size() - 1);}
};3. Danger
力扣LeetCode是领扣网络旗下专注于程序员技术成长和企业技术人才服务的品牌。源自美国硅谷力扣为全球程序员提供了专业的IT技术职业化提升平台有效帮助程序员实现快速进步和长期成长。此外力扣LeetCode致力于解决程序员技术评估、培训、职业匹配的痛点逐步引领互联网技术求职和招聘迈向专业化。
据了解到的情况Easy题和Medium 题在面试中比较常见通常会以手写代码之类的形式出现您需要对问题进行分析并给出解答并于面试官进行交流沟通有时还会被要求分析时间复杂度8与空间复杂度°面试官会通过您对题目的分析解答了解您对常用算法的熟悉程度和您的程序实现功底。而在一些对算法和程序实现功底要求较高的岗位Hard 题也是很受到面试官的青睐如果您在面试中成功Bug-Free出一道Hard题我们相信您一定会给面试官留下很深刻的印象并极大增加拿到Offer的概率据相关人士统计如果您在面试成功解出一道Hard题拿不到Offer的概率无限接近于0。所以,力扣中Easy和Medium相当于面试中的常规题而Hard 则相当于面试中较难的题解出—道Hard题Offer可以说是囊中之物。
参考
【1】链接https://leetcode.cn/problems/rotate-array/ 来源力扣LeetCode
