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/


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