iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 1
0
自我挑戰組

30天 HackerRank 解解解 系列 第 2

Day 2 - Arrays: Left Rotation

Arrays: Left Rotation

原題網址

https://www.hackerrank.com/challenges/ctci-array-left-rotation/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

難度: easy

題目描述

本題要做的就是對一個陣列做左移的位移,把左邊的元素位移到右邊

如下例:

做 2 次 left rotation 的例子

[1, 2, 3, 4, 5] -> [2, 3, 4, 5, 1] -> [3, 4, 5, 1, 2] 

做 4 次 left rotation 的例子

[1, 2, 3, 4, 5] -> [2, 3, 4, 5, 1] -> [3, 4, 5, 1, 2] 
-> [4, 5, 1, 2, 3] -> [5, 1, 2, 3, 4]

目的

給 d 次 left rotation, 顯示最後的結果

解題概念:

因為本題要做的就是往左位移,然後會不斷的移到右邊

所以如果今天要做 d 次 left rotation 我們可以用 mod 的方式計算出最後的位置 (因為陣列大小是固定的)

ex: 陣列大小是 5, 要做 4 次 left rotation 那我們可以算出

原本在 index 0 的值, 會變成 (0 + 4) % 5 = 4

也就是原本在 index = 4 的元素 會左移 4 到 index = 0 上,

原本在 index 1 的值, 會變成 (1 + 4) % 5 = 0

也就是原本在 index = 0 的元素 會左移 4 到 index = 1 上,

...

依此類推

程式碼

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
import java.util.stream.IntStream;

public class Solution {

    // Complete the rotLeft function below.
    static int[] rotLeft(int[] a, int d) {
        int size = a.length;
        int rs[] = new int[size];
        IntStream.range(0, a.length).forEach(i -> {
            int newIndex = (i + d) % size;
            rs[i] = a[newIndex];
        });
        return rs;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nd = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nd[0]);

        int d = Integer.parseInt(nd[1]);

        int[] a = new int[n];

        String[] aItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int aItem = Integer.parseInt(aItems[i]);
            a[i] = aItem;
        }

        int[] result = rotLeft(a, d);

        for (int i = 0; i < result.length; i++) {
            bufferedWriter.write(String.valueOf(result[i]));

            if (i != result.length - 1) {
                bufferedWriter.write(" ");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}



以上是今天的解題分享! 感謝!


上一篇
Day 1 - 2D Array - DS
系列文
30天 HackerRank 解解解 2

尚未有邦友留言

立即登入留言