题解 | #句子逆序#

句子逆序

http://www.nowcoder.com/practice/48b3cb4e3c694d9da5526e6255bb73c3

库函数

思路

  1. 使用 split() 方法按照空格分割,得数组 arr
  2. 逆序遍历 arr,并添加到 res
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] arr = in.nextLine().split(" ");
        StringBuilder res = new StringBuilder();
        for (int i = arr.length - 1; i >= 0; i--) {
            res.append(arr[i]);
            res.append(" ");
        }
        System.out.println(res);
        in.close();
    }
}
  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)

双指针

由于 JavaString 是不可变的,所以无法像 C++ 中做到空间 O(1)O(1)。但是,如果所给输入为 char[] 数组,则可以做到“原地算法”,将空间降为 O(1)O(1) (这里假装输入是 char[] :smile:)

思路

  • reverse(char[] arr, int left, int right) 函数:双指针反转 数组区间 arr[left, right]左闭右闭区间
  • 反转每一个单词(空格分隔
    • [I am a boy] --> [I ma a yob]
  • 整体反转全部 arr
    • [I ma a yob] --> [boy a am I]
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        char[] arr = s.toCharArray();
        int n = arr.length;
        int left = 0;
        // 反转每一个单词
        while (left < n) {
            int right = left;
            while (right + 1 < n && arr[right + 1] != ' ') {
                right++;
            }
            reverse(arr, left, right);
            // arr[right]是当前单词的末尾,arr[right + 1]为空格,arr[right + 2]为下一个单词开头(或越界)
            left = right + 2;
        }
        // 整体反转
        reverse(arr, 0, n - 1);
        System.out.println(new String(arr));
        in.close();
    }
    
    // 双指针反转, arr[left, right]
    static void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 11:27
点赞 评论 收藏
分享
06-15 20:57
已编辑
门头沟学院 Java
CARLJOSEPH...:年轻人有傲气很正常,但是建议工作前洗净傲气。 说实在的,什么奖学金什么奖项的都很一般。尊重你的老师,在有时间的时候去上课,真遇到走不开的事,请态度端正地向你的老师说明情况,请求请假。我相信任何一个有师德的老师都会允许的(我的老师就是这样)。
点赞 评论 收藏
分享
07-07 11:33
江南大学 Java
已经在暑假实习了&nbsp;,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务