【Codility Lesson2】CyclicRotation

Codilityの勧め ~JavaScriptで解くアルゴリズム~の実践編です。

問題

An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is 6, 3, 8, 9, 7.

The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

Write a function:

class Solution { public int[] solution(int[] A, int K); }

that, given an array A consisting of N integers and an integer K, returns the array A rotated K times.

For example, given

A = [3, 8, 9, 7, 6]
K = 3

the function should return [9, 7, 6, 3, 8]. Three rotations were made:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

For another example, given

A = [0, 0, 0]
K = 1

the function should return [0, 0, 0]

Given

A = [1, 2, 3, 4]
K = 4

the function should return [1, 2, 3, 4]

Assume that:

N and K are integers within the range [0..100];
each element of array A is an integer within the range [−1,000..1,000].
In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

語彙メモ

• integer 整数
• rotate array A K times arrayAをK回回転させる
• Write a function: (:以下の)関数を書け
• Assume that: (that:以下を)仮定しなさい

解法

1. pop()とunshift()を使用する

pop()メソッドは配列から最後の要素を取り除き、その取り除いた要素を返します。
unshift()メソッドは配列の最初に一つ以上の要素を追加し、新しい配列の長さを返り値として返します。
また、pop(), unshift()共に破壊的なメソッド（＝元の配列を直接変化させる）であることに留意してください。

配列A、回転数Kを引数とした関数を作ります。
変数iに初期値として0を代入します。
A.pop()で配列Aの最後の要素を取り出し、A.unshift(A.pop())で配列Aの最後の要素を最初の要素として追加した新しい配列Aを作ります。これをwhile文でK回ループさせます。

function solution(A, K) {
    // write your code in JavaScript (Node.js 8.9.4)
    let i = 0;
    while(i < K) {
        A.unshift(A.pop())
        i++
    }

    return A
}

for文を使用する際はこちら。

function solution(A, K) {
    // write your code in JavaScript (Node.js 8.9.4)
    for(let i = 0; i < K; i++) {
        A.unshift(A.pop())
    }

    return A
}

2.pop()の代わりにslice()を使用する

function solution(A, K) {
  if (A.length >= K) {
    A.unshift(...A.splice(-K));
  } else {
    let i = 0;
    while (i < K) {
      A.shift(A.splice(-1));
      i++;
    }
  }
  return A;
}

// line 4: To add the elements of that array to the start of nums (instead of the array itself) we use the spread operator: ...nums.splice(-K)

参考

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

世界でもっとも強力な9のアルゴリズム

なっとく！アルゴリズム

初めてのJavaScript 第3版 ―ES2015以降の最新ウェブ開発

徹底例解ロイヤル英文法　改訂新版