[LintCode] Rotate String [周而复始]

CarlBenjamin 发布于2019-08-14 15:12 / 441人阅读

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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