1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 58-2 题] “左旋转字符串”做题记录

[剑指 Offer 第 2 版第 58-2 题] “左旋转字符串”做题记录

第 58-2 题:左旋转字符串

传送门:左旋转字符串牛客网 online judge 地址

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。

请定义一个函数实现字符串左旋转操作的功能。

比如输入字符串"abcdefg"和数字2,该函数将返回左旋转2位得到的结果"cdefgab"

注意:

  • 数据保证n小于等于输入字符串的长度。

样例

``` 输入:"abcdefg" , n=2

输出:"cdefgab" ```

思路:“abcdefg” 旋转以后,“gfedcba”,在倒数第 2 位前后,再翻转一下,得“cdefgab”。左旋转字符串的时候要分析清楚,注意:移动的位数要取余数。

Python 代码:

  class Solution(object):
        def leftRotateString(self, s, n):
            """
            :type s: str
            :type n: int
            :rtype: str
            """

            size = len(s)
            # 特判
            if size == 0 or n % size == 0:
                return s
            n = n % size
            arr = list(s)
            self.__reverse(arr, 0, size - 1)

            self.__reverse(arr, 0, size - 1 - n)
            self.__reverse(arr, size - n, size - 1)

            return ''.join(arr)

        def __reverse(self, arr, left, right):
            if left >= right:
                return
            while left < right:
                arr[left], arr[right] = arr[right], arr[left]
                left += 1
                right -= 1

Java 代码:

  public class Solution {

        private void reverseString(char[] charArr, int start, int end) {
            int l = start;
            int r = end;
            while (l < r) {
                swap(charArr, l, r);
                l++;
                r--;
            }
        }

        private void swap(char[] charArr, int index1, int index2) {
            if (index1 == index2) {
                return;
            }
            char temp = charArr[index1];
            charArr[index1] = charArr[index2];
            charArr[index2] = temp;
        }

        public String LeftRotateString(String str, int n) {
            int len = str.length();
            if (len == 0 || n < 0) {
                return "";
            }
            if (len == 1) {
                return str;
            }

            // 这里要注意了
            n = len - n % len;

            char[] charArr = str.toCharArray();
            reverseString(charArr, 0, len - 1);
            reverseString(charArr, 0, n - 1);
            reverseString(charArr, n, len - 1);
            return String.valueOf(charArr);
        }

        public static void main(String[] args) {
            String str = "abcXYZdef";
            Solution solution = new Solution();
            String leftRotateString = solution.LeftRotateString(str, 3);
            System.out.println(leftRotateString);
        }
    }

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程
  4. JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

    本文著作权归作者所有,如若转载,请注明出处

    转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

    标题:[剑指 Offer 第 2 版第 58-2 题] “左旋转字符串”做题记录

    链接:https://www.javajike.com/article/3316.html

« [剑指 Offer 第 2 版第 58-1 题] “翻转单词序列”做题记录
[剑指 Offer 第 2 版第 64 题] “求1+2+3+…+n”做题记录»

相关推荐

QR code