HackerRank左旋转(Java)

huangapple go评论80阅读模式
英文:

HackerRank Left Rotation in Java

问题

以下是翻译好的内容:

我昨天查找了这个问题的解决方案,今天尝试自己解决,但发现自己在用不同的方式解决这个问题。我感觉我可能把问题复杂化了,但我仍然希望能够得到对我的可能解决方案的答案,因为不知道这让我感到很烦恼(我相信每个人在某个时候都经历过这种情况)。无论如何,以下是问题:

<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>

我的想法是,首先要检查数组长度是否等于所需的旋转次数,如果是,则直接返回原始数组,不需要进行任何操作。

我的下一个想法是检查旋转次数是否大于数组长度。如果是这种情况,我们可以进行旋转次数减去数组长度,或者取绝对值(数组长度减去旋转次数),这会得到相同的结果。我们可以将这个值重新赋值给变量 D。

接下来,我们可以创建一个情况来进行向右旋转,而不是向左旋转。当旋转次数大于数组长度的一半时,我们不需要向左旋转,因为这样会多做无用功。相反,我们会选择向右旋转。例如:

数组长度为 4
旋转次数为 3(左旋转)

我们只需向右旋转一次,而不是向左旋转 3 次。我们可以将 rotateRight 布尔值设置为 true(否则设置为 false,表示正常进行左旋转)。

不过,这是我卡住的地方。我不确定如何进行元素的旋转。我考虑返回一个新的数组。如何获得新数组的正确值?我在处理索引越界异常方面遇到了问题。在这个示例中,我是否也可以使用 try-catch,还是这样做有些过度?

以下是我目前的代码,它应该与上面的想法相匹配:

static int[] rotLeft(int[] a, int d) {
        int aLength = a.length;
        int counter = 0;
        int[] newArray = new int[aLength];
        boolean rotateRight = false;
        if (aLength == d) {
            return a;
        }
        if (a.length - d &lt; 0) {
            d = Math.abs(a.length - d);
        }

        if(d &gt; a.length/2) {
            rotateRight = true;
        }
        
   
    return newArray;
}

如果需要更多信息,请让我知道。

英文:

I looked up the solution to this problem yesterday and tried to solve on my own today but found myself trying to solve this problem in a different way. I feel I may be overcomplicating the problem but I still want an answer to my possible solution just because it is bugging me to know (I am sure everyone has experienced this at some point or another). Anyway here is the problem:
<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>

My idea is that you would first check to see if your array length was equal to the rotations you want then you would simply return the original. There is no work needed to be done.

My next idea would be to check to see if our rotations is greater than our array length. If this is the case, we can either do rotations - array length or ABS VALUE(array length - rotations), which gives us the same result. We can reassign this value to D.

Next, we can create a case to rotate right instead of left. When your rotation is greater than your array length / 2, then we would not to rotate left since we are doing extra work. We instead would want to rotate right. For example:

Array Length 4
Rotations 3 (LEFT)

We can simply rotate right once instead of rotating left 3 times. We could set the rotateRight boolean to true (otherwise set to false which indicated to rotateLeft as normal)

Anyway this is the part I get caught on. I am unsure of how to rotate my elements here. I was thinking of returning a new array. How can I get the correct values for my new array? I am facing issues with IndexOutOfBounds exceptions. Can I also use try catches in this example or is it overkill?

Here is the code I have currently it should match my thoughts from up above:

static int[] rotLeft(int[] a, int d) {
        int aLength = a.length;
        int counter = 0;
int[] newArray = new int[aLength];
        boolean rotateRight = false;
        if (aLength == d) {
            return a;
        }
        if (a.length - d &lt; 0) {
            d = Math.abs(a.length - d);
        }

        if(d &gt; a.length/2) {
            rotateRight = true;
        }
        
   
    return newArray;
    }

If you need any more info let me know.

答案1

得分: 2

代码部分已翻译如下:

如果试图简化数学问题导致编写更复杂的程序,则几乎没有好处 - 尤其是因为您根本不想旋转数组,可以直接将正确的值直接放在正确的位置。

如果元素 i 的旧位置是 i,在大小为 len 的数组进行了 d 次左旋转后,它的新位置将是 (i-d)%len。如果 d == len+1,这确实等同于 (i+1)%len - 这对人类来说更容易,但计算机同样可以愉快地计算这两个表达式。

因此,建议的代码如下:

static int[] rotLeft(int[] a, int d) {
    int[] b = new int[a.length];
    for (int s = d, t = 0; t < a.length; s++, t++) {
        // t 是目标位置;s 是源位置
        b[t] = a[s % a.length];
    }
    return b;
}

注意:代码未经测试

英文:

There is little benefit to trying to simplify the maths, if it leads to a harder-to-write program -- especially since you do not want to rotate the array at all, and can simply place the correct values in the correct places directly.

If the old position of element i was i, after d left-rotations of an array of size len, its new position will be (i-d)%len. If d == len+1 this is indeed equivalent to (i+1)%len -- easier for humans, but computers calculate either expression just as happily.

So the suggested code is:

static int[] rotLeft(int[] a, int d) {
    int[] b = new int[a.length];
    for (int s=d, t=0; t&lt;a.length; s++, t++) {
       // t is target position; s is source position
       b[t] = a[s%a.length];
    }
    return b;
}

Note: code is untested

huangapple
  • 本文由 发表于 2020年10月9日 20:29:22
  • 转载请务必保留本文链接:https://go.coder-hub.com/64280094.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定