dtcms Vue全家桶 DHCP printing arm Seajs vue循环数组 web前端毕业设计题目 软件测试实战项目 mysql当前时间减一天 svn默认安装路径 mac虚拟打印机 datetimepicker赋值 kb转mb 时间戳java spring源码下载 mysql数据库 安装mysql mysqlinsert python迭代器 python环境设置 python函数参数 java开发学习 java地址 java日期函数 java线程停止 sql实例 行业软件下载 计算机网络自顶向下 fireworks8 blued是什么软件 今日头条邀请码 medcalc 华为手机刷公交卡 奥法隐藏外观 快手规则 模拟邻居 键盘指法练习游戏 文件压缩工具 狮子狗打野天赋
当前位置: 首页 > 学习教程  > 编程语言

剑指 offer 面试题8 翻转单词顺序(双指针、分割+倒序)

2020/8/11 19:15:46 文章标签:

I 翻转单词顺序(本质上是移动单词顺序)

个人博客


输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串"I am a student. “,则输出"student. a am I”。

题解

  • 双指针寻找单词

    • 算法思想
      • 使用两个指针,i 指针寻找单词的第一个字母位置。j 指针寻找单词的最后一个字母位置
      • 当遇到空格就使用 while 跳过
    • 复杂度分析
      • 时间复杂度 O(n)
      • 空间复杂度 O(n)
    class Solution {
        public String reverseWords(String s) {
            s = s.trim();
            int i = s.length() -1,j = i;
            StringBuilder sb = new StringBuilder();
            while(i >= 0){
                while(i >= 0 && s.charAt(i) != ' ')i--;
                sb.append(s.substring(i+1,j+1)+" ");
                while(i > 0 && s.charAt(i) == ' ')i--;
                j = i;
            }
            return sb.toString().trim();
        }
    }
    
  • 分割 + 倒序

    • 算法思想
      • 将句子中的单词分割,然后将分割后的数组倒序就得到结果
    • 复杂度分析
      • 时间复杂度 O(n)
      • 空间复杂度 O(n)
    class Solution {
        public String reverseWords(String s) {
            String[] strs = s.split(" ");
            StringBuilder sb = new StringBuilder();
            for(int i = strs.length -1;i >= 0;i--){
                if(strs[i].equals(""))continue;
                sb.append(strs[i]+" ");
            }
            return sb.toString().trim();
        }
    }
    

本文链接: http://www.dtmao.cc/news_show_100106.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?