[剑指 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/