LeetCode 旋转数组算法题解 All In One

189. Rotate Array

/**
 Do not return anything, modify nums in-place instead.
 */
// solution 1:暴力破解：❌ Time Limit Exceeded	
// function rotate(nums: number[], k: number): void {
//   if(k === 0) {
//     // return;
//   } else {
//     const len = nums.length;
//     while(k > 0) {
//       // deep clone 
//       let temp = [];
//       for(let i= 0; i< len; i++) {
//         // 破解对象引用 bug, 值引用
//         temp[i] = nums[i];
//       }
//       let end = temp[len - 1];
//       // 循环队列
//       for(let i = 1; i< len; i++) {
//         // 交换swap
//         nums[i] = temp[i - 1];
//       }
//       nums[0] = end;
//       // console.log(`nums =`, nums);
//       k -= 1;
//     }
//   }
//  // no return, in-place 就地交换
// };

// solution 2: in-place 就地交换算法 ✅
function reverse(i: number, j: number, nums: number[]): void {
  while(i < j){
    [
      nums[i],
      nums[j]
    ] = [
      nums[j],
      nums[i]
    ];
    // 两两互换
    i++;
    j--;
  }
};

function rotate(nums: number[], k: number): void {
  k %= nums.length;
  // 如果 k 大于 nums.length 则完成一个循环，这意味着它将保持不变，我们必须进行剩余移位
  // reverse all
  reverse(0, nums.length-1, nums);
  // reverse first part
  reverse(0, k - 1, nums)
  // reverse second part
  reverse(k, nums.length-1, nums);
};

https://leetcode.com/problems/rotate-array/
https://leetcode.cn/problems/rotate-array/

796. Rotate String

in-place 就地交换算法

https://leetcode.com/problems/rotate-string/

refs

©xgqfrms 2012-2020

www.cnblogs.com/xgqfrms 发布文章使用：只允许注册用户才可以访问！

原创文章，版权所有©️xgqfrms, 禁止转载