[LintCode] Rotate String [周而復始]

CarlBenjamin 發布于2019-08-14 15:12 / 631人閱讀

Problem

Given a string and an offset, rotate string by offset. (rotate from left to right)

Example

Given "abcdefg".

offset=0 => "abcdefg"
offset=1 => "gabcdef"
offset=2 => "fgabcde"
offset=3 => "efgabcd"

Challenge

Rotate in-place with O(1) extra memory.

Note

完成challenge，三步翻轉法。見Sol.2。

Solution

public class Solution {
    public void rotateString(char[] str, int offset) {
        int len = str.length;
        char[] newstr = new char[len+1];
        if (str == null || str.length ==  0) return;
        //modify offset if offset > length;
        offset = offset % len;
        for (int i = 0; i < offset; i++) {
            newstr[i] = str[len-offset+i];
        }
        for (int i = offset; i < len; i++) {
            newstr[i] = str[i-offset];
        }
        for (int i = 0; i < len; i++) {
            str[i] = newstr[i];
        }
        return;
    }
}

三步翻轉法：O(1) extra memory

public class Solution {
    public void rotateString(char[] str, int offset) {
        if (str == null || str.length == 0) {
            return;
        }
        int len = str.length;
        offset = offset % len;
        reverse(str, 0, len-offset-1);
        reverse(str, len-offset, len-1);
        reverse(str, 0, len-1);
        return;
    }
    public void reverse(char[] str, int start, int end) {
        while (start <= end) {
            char temp = str[start];
            str[start] = str[end];
            str[end] = temp;
            start++;
            end--;
        }
    }
}

云服務器 GPU云服務器 Rotate LintCode 旋轉-rotate LintCode134_LRU

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65457.html

[LintCode/LeetCode] Rotate Array

Problem Given an array, rotate the array to the right by k steps, where k is non-negative. Example Example 1: Input: [1,2,3,4,5,6,7] and k = 3Output: [5,6,7,1,2,3,4]Explanation:rotate 1 steps to the r...

chanthuang 2019-08-16 12:44 評論0 收藏0
[LintCode/LeetCode] Rotate Image

摘要：兩種方法，轉置鏡像法和公式法。首先看轉置鏡像法原矩陣為轉置后水平鏡像翻轉后所以，基本的思路是兩次遍歷，第一次轉置，第二次水平鏡像翻轉變換列坐標。公式法是應用了一個翻轉的公式如此翻轉四次即可。二者均可，并無分別。 Problem You are given an n x n 2D matrix representing an image.Rotate the image by 90 de...

BenCHou 2019-08-14 15:22 評論0 收藏0
[LintCode/LeetCode] Rotate List

摘要：而后吾當依除取余之法，化大為小，則指針不致于越界也。后欲尋右起第結點，令快指針先行數日，及至兩指針相距為，便吟鞭東指，與慢指針策馬共進。快慢指針亦止于其所焉。舞動長劍，中宮直入，直取首級，而一掌劈空，已鴻飛冥冥。自此，一代天驕，霸業已成。 Problem Given a list, rotate the list to the right by k places, where k is...

Blackjun 2019-08-14 15:22 評論0 收藏0
SVG + CSS 實現 Material Design Loading

摘要：在研究的過程中，發現有大神用在上實現了它。由制定，是一個開放標準。省略這時，你就能看到線段周而復始地從一根細線變為一個圓圈。這次感覺是不是很相像了，只是現在它的開口一直處于一個位置，就沒什么魔性了。 showImg(http://upload-images.jianshu.io/upload_images/1258730-02e5f2eca07eaa59.gif?imageMogr2/...

txgcwm 2019-08-29 11:16 評論0 收藏0
[LeetCode/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 評論0 收藏0