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

[剑指 Offer 第 2 版第 58-1 题] “翻转单词序列”做题记录

[剑指 Offer 第 2 版第 58-1 题] “翻转单词序列”做题记录

第 58-1 题:翻转单词顺序列

传送门:AcWing:翻转单词顺序牛客网 online judge 地址

输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。

为简单起见,标点符号和普通字母一样处理。

例如输入字符串"I am a student.",则输出"student. a am I"

样例:

输入:"I am a student."

输出:"student. a am I"

思路:实现一个辅助的方法,将一个字符数组的指定区间进行翻转。

Python 代码:

  class Solution(object):
        def reverseWords(self, s):
            """
            :type s: str
            :rtype: str
            """

            size = len(s)
            arr = list(s)

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

            begin = 0
            index = 0
            while index < size:
                if arr[index] == ' ':
                    self.__reverse(arr, begin, index - 1)
                    begin = index + 1
                index += 1
            # 最后还要反转一下
            self.__reverse(arr, begin, 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 {

        /**
         * 辅助函数:翻转字符数组指定区间内的字符
         *
         * @param str
         * @param start
         * @param end
         */
        private void reverseString(char[] str, int start, int end) {
            int l = start;
            int r = end;
            while (l < r) {
                swap(str, l, r);
                l++;
                r--;
            }
        }

        /**
         * 辅助函数:交换字符数组指定索引的字符
         *
         * @param str
         * @param index1
         * @param index2
         */
        private void swap(char[] str, int index1, int index2) {
            if (index1 == index2) {
                return;
            }
            char temp = str[index1];
            str[index1] = str[index2];
            str[index2] = temp;
        }

        public String ReverseSentence(String str) {
            int len = str.length();
            if (len == 0 || len == 1) {
                return str;
            }
            char[] charArr = str.toCharArray();
            reverseString(charArr, 0, len - 1);
            int start = 0;
            for (int i = 0; i < len; i++) {
                if (charArr[i] == ' ') {
                    reverseString(charArr, start, i - 1);
                    start = i + 1;
                }
            }
            // 最后还要记得反转一下
            reverseString(charArr, start, len - 1);
            return String.valueOf(charArr);
        }

        public static void main(String[] args) {
            String str = "write your code here";
            Solution solution = new Solution();
            String reverseSentence = solution.ReverseSentence(str);
            System.out.println(reverseSentence);
        }
    }

总结:别把问题想复杂了,有点耐心,这些问题其实并没有那么难。

作者:liweiwei1419

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


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

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

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

标题:[剑指 Offer 第 2 版第 58-1 题] “翻转单词序列”做题记录

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

« [剑指 Offer 第 2 版第 55_2 题] “平衡二叉树”做题记录
[剑指 Offer 第 2 版第 58-2 题] “左旋转字符串”做题记录»

相关推荐

QR code