题目

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：

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

示例 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 <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

面向问题解决方法

  1. /*
  2. 给定一个含有 M x N 个元素的矩阵（M 行，N 列），
  3. 请以对角线遍历的顺序返回这个矩阵中的所有元素，
  4. 对角线遍历如下图所示。
  6. 输入:
  7. [
  8.  [ 1, 2, 3 ],
  9.  [ 4, 5, 6 ],
  10.  [ 7, 8, 9 ]
  11. ]
  13. 输出:  [1,2,4,7,5,3,6,8,9]
  15.  */
  17. function findDiagonalOrder(mat: [][]) {
  19.   const matLength = mat.length;
  20.   // 找到中心点，unshift，与 push 放置中心点前后元素
  21.   const centerPoint = (matLength + 1) / 2 - 1;
  23.   // 先找到中轴线
  24.   let middleLine = [[centerPoint, centerPoint]];
  26.   let i = centerPoint;
  27.   while(i > 0) {
  28.     // 中心点前面的
  29.     middleLine.unshift([i + 1, i - 1]);
  30.     //中心点后面的
  31.     middleLine.push([i - 1, i + 1]);
  32.     i--;
  33.   }
  35.   let resultMat = [middleLine];
  37.   // 找中轴线前后，找中轴线前面的和后面的
  39.   i = centerPoint + 1;
  41.   while(i > 0) {
  42.     if(i == 1) {
  43.       resultMat.unshift([[0, 0]]);
  44.       resultMat.push([[centerPoint + 1, centerPoint + 1]]);
  45.       return resultMat;
  46.     }
  47.     let beforeMat = [];
  48.     let afterMat = [];
  49.     for(let key = 0; key < i - 1; key++) {
  50.       beforeMat.unshift([key, centerPoint - key]);
  51.       beforeMat.push([centerPoint - key, key]);
  52.       afterMat.unshift([centerPoint - key, centerPoint - key + 1]);
  53.       afterMat.push([centerPoint - key, centerPoint - key + 1]);
  54.     }
  55.     resultMat.unshift(beforeMat);
  56.     resultMat.push(afterMat);
  57.     i--;
  58.   }
  59.   return resultMat;
  60. }
  62. const testArray = [
  63.   [1, 2, 3],
  64.   [4, 5, 6],
  65.   [7, 8, 9]
  66. ]
  68. console.log(findDiagonalOrder(testArray));

优化

  1. /*
  2. 给定一个含有 M x N 个元素的矩阵（M 行，N 列），
  3. 请以对角线遍历的顺序返回这个矩阵中的所有元素，
  4. 对角线遍历如下图所示。
  6. 输入:
  7. [
  8.  [ 1, 2, 3 ],
  9.  [ 4, 5, 6 ],
  10.  [ 7, 8, 9 ]
  11. ]
  13. 输出:  [1,2,4,7,5,3,6,8,9]
  14. [[0,0],
  15. [0,1],[1,0],
  16. [2,0],[1,1],[0,2],
  17. [1,2],[2,1],
  18. [2,2]]
  20.  */
  22. function findDiagonalOrder(mat: number[][]) {
  24.   const matLength = mat.length;
  25.   // 找到中心点，unshift，与 push 放置中心点前后元素
  26.   const centerPoint = (matLength + 1) / 2 - 1;
  28.   // 中轴线之前数组，起始坐标点固定
  29.   let middleLineBeforeMat = [[0,0]];
  30.   // 中轴线之后数组，结束坐标点固定
  31.   let middleLineAfterMat = [[matLength - 1,matLength - 1]];
  33.   // 先找到中轴线
  34.   let middleLine = [[centerPoint, centerPoint]];
  36.   let i = centerPoint;
  37.   while(i > 0) {
  39.     /* 中轴线数组逻辑 */
  40.     middleLine = [[i + 1, i - 1],...middleLine,[i - 1, i + 1]];
  42.     /* 找中轴线两边 */
  43.     let beforeMat: number[] [] = [];
  44.     let afterMat: number[] [] = [];
  45.     for(let key = 0; key < i; key++) {
  46.       beforeMat = [[key, i - key],...beforeMat,[ i - key,key]];
  47.       afterMat = [[i- key, i - key + 1],...afterMat,[i - key + 1,i - key, ]]
  48.     }
  49.     middleLineBeforeMat = [...middleLineBeforeMat,...beforeMat]
  50.     middleLineAfterMat = [...afterMat,...middleLineAfterMat]
  51.     i--;
  52.   }
  54.   return  [...middleLineBeforeMat,...middleLine,...middleLineAfterMat];
  55. }
  57. const testArray = [
  58.   [1, 2, 3],
  59.   [4, 5, 6],
  60.   [7, 8, 9]
  61. ]
  63. console.log(findDiagonalOrder(testArray));

坐标换为值

  1. function findDiagonalOrder(mat: number[][]) {
  3.   const matLength = mat.length;
  4.   // 找到中心点，unshift，与 push 放置中心点前后元素
  5.   const centerPoint = (matLength + 1) / 2 - 1;
  7.   // 中轴线之前数组，起始坐标点固定
  8.   let middleLineBeforeMat = [mat[0][0]];
  9.   // 中轴线之后数组，结束坐标点固定
  10.   let middleLineAfterMat = [mat[matLength - 1][matLength - 1]];
  12.   // 先找到中轴线
  13.   let middleLine = [mat[centerPoint][centerPoint]];
  15.   let i = centerPoint;
  16.   while(i > 0) {
  18.     /* 中轴线数组逻辑 */
  19.     middleLine = [mat[i + 1] [i - 1],...middleLine,mat[i - 1][ i + 1]];
  21.     /* 找中轴线两边 */
  22.     let beforeMat: number[] = [];
  23.     let afterMat: number[]  = [];
  24.     for(let key = 0; key < i; key++) {
  25.       beforeMat = [mat[key][ i - key],...beforeMat,mat[ i - key][key]];
  26.       afterMat = [mat[i- key] [i - key + 1],...afterMat,mat[i - key + 1][i - key ]]
  27.     }
  28.     middleLineBeforeMat = [...middleLineBeforeMat,...beforeMat]
  29.     middleLineAfterMat = [...afterMat,...middleLineAfterMat]
  30.     i--;
  31.   }
  33.   return  [...middleLineBeforeMat,...middleLine,...middleLineAfterMat];
  34. }