剑指offer | 面试题45：翻转单词顺序

2022-02-23 15:40:46 浏览数 (1)

死磕算法系列文章

  1. 干货 | 手撕十大经典排序算法
  2. 剑指offer | 认识面试
  3. 剑指offer | 面试题2：实现Singleton模式
  4. 剑指offer | 面试题3：二维数组的查找
  5. 剑指offer | 面试题4：替换空格
  6. 剑指offer | 面试题5：从尾到头打印链表
  7. 剑指offer | 面试题6：重建二叉树
  8. 剑指offer | 面试题7：用两个栈实现队列
  9. 剑指offer | 面试题8：旋转数组的最小数字
  10. 剑指offer | 面试题9：斐波那契数列
  11. 剑指offer | 面试题10：青蛙跳台阶问题
  12. 剑指offer | 面试题11：矩阵覆盖
  13. 剑指offer | 面试题12：二进制中1的个数
  14. 剑指offer | 面试题13：数值的整数次方
  15. 剑指offer | 面试题14：打印从1到最大的n位数
  16. 剑指offer | 面试题15：删除链表的节点
  17. 剑指offer | 面试题16：将数组中的奇数放在偶数前
  18. 剑指offer | 面试题17：链表中倒数第k个节点
  19. 剑指offer | 面试题18：反转链表
  20. 剑指offer | 面试题19：合并两个有序链表
  21. 剑指offer | 面试题20：判断二叉树A中是否包含子树B
  22. 剑指offer | 面试题21：二叉树的镜像
  23. 剑指offer | 面试题22：顺时针打印矩阵
  24. 剑指offer | 面试题23：包含min函数的栈
  25. 剑指offer | 面试题24：栈的压入、弹出序列
  26. 剑指offer | 面试题25：从上到下打印二叉树
  27. 剑指offer | 面试题26：二叉搜索树的后序遍历序列
  28. 剑指offer | 面试题27：二叉树中和为某一值的路径
  29. 剑指offer | 面试题28：复杂链表的复制
  30. 剑指offer | 面试题29：二叉搜索树转换为双向链表
  31. 剑指offer | 面试题30：字符串的排列
  32. 剑指offer | 面试题31：数组中出现次数超过一半的数字
  33. 剑指offer | 面试题32：最小的k个数
  34. 剑指offer | 面试题33：连续子数组的最大和
  35. 剑指offer | 面试题34：1～n 整数中 1 出现的次数
  36. 剑指offer | 面试题35：把数组排成最小的数
  37. 剑指offer | 面试题36：丑数
  38. 剑指offer | 面试题37：第一个只出现一次的字符
  39. 剑指offer | 面试题38：数组中的逆序对
  40. 剑指offer | 面试题39：两个链表的第一个公共节点
  41. 剑指offer | 面试题40：数组中数字出现的次数
  42. 剑指offer | 面试题41：二叉树的深度
  43. 剑指offer | 面试题42：平衡二叉树
  44. 剑指offer | 面试题43：和为s的两个数字
  45. 剑指offer | 面试题44：和为s的连续整数序列

“Leetcode : https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/

“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_44_findContinuousSequence/Solution.java

剑指 Offer 58 - I. 翻转单词顺序

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

示例 1：

代码语言：javascript复制
输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

代码语言：javascript复制
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

代码语言：javascript复制
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

方法1：双指针

算法解析：
  • 倒序遍历字符串 s，记录单词左右索引边界 i , j；
  • 每确定一个单词的边界，则将其添加至StringBuilder单词列表res；
  • 最终，将单词列表拼接为字符串，并返回即可。

复杂度分析:

  • 时间复杂度0(N)：N为字符串s的长度,线性遍历字符串。
  • 空间复杂度O(N) ：新建StringBuilder()中的字符串总长度< N，占用O(N)大小的额外空间。
代码语言：javascript复制
package com.nateshao.sword_offer.topic_45_reverseWords;

import javax.swing.*;

/**
 * @date Created by 邵桐杰 on 2022/1/27 16:18
 * @微信公众号 千羽的编程时光
 * @个人网站 www.nateshao.cn
 * @博客 https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description:
 */
public class Solution {
    public static void main(String[] args) {
        String s = "the sky is blue";
        System.out.println("reverseWords1(s) = "   reverseWords1(s));
//        System.out.println("reverseSentence(s) = "   reverseSentence(s));//reverseSentence(s) = blue is sky the
//        System.out.println("reverseWords2(s) = "   reverseWords2(s));
    }

    /**
     * 双指针
     * 1. 倒序遍历字符串，记录单词左右索引边界i,j
     * 2. 每确定单词的边界，放入res
     * 3. 最后，拼接成字符串，返回即可
     *
     * @param s
     * @return
     */
    public static String reverseWords1(String s) {
        s = s.trim();
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while (i >= 0) {
            // 搜索首个空格，添加单词
            // 是字母就添加进去
            while (i >= 0 && s.charAt(i) != ' ') i--;
            res.append(s.substring(i   1, j   1)   " ");
            // 是空格的话，跳过单词间空格，j就指向下一个单词尾字符。
            while (i >= 0 && s.charAt(i) == ' ') i--;
            j = i;
        }
        return res.toString().trim();// 转化为字符串，并且返回
    }

    // 方法二：分割   倒序 （面试时不建议使用）
    public static String reverseWords2(String s) {
        // 删除首尾空格，分割字符串
        String[] strs = s.trim().split(" ");
        StringBuilder res = new StringBuilder();
        // 倒序遍历单词列表
        for (int i = strs.length - 1; i >= 0; i--) {
            // 遇到空格则跳过
            if (strs[i].equals("")) continue;
            // 将单词拼接到StringBuilder()
            res.append(strs[i]   " ");
        }
        // 转化为字符串，删除尾部空格，并返回
        return res.toString().trim();
    }

    /**
     * 剑指offer PDF
     *
     * @param sentence
     * @return
     */
    public static String reverseSentence(String sentence) {
        if (sentence == null || sentence.length() == 0 || sentence.trim().length() == 0) {
            return sentence;
        }
        String blank = " ";
        String sentenceReverse = reverse(sentence);
        String[] splitStrings = sentenceReverse.split(blank);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < splitStrings.length - 1; i  ) {
            sb.append(reverse(splitStrings[i])).append(blank);
        }
        sb.append(reverse(splitStrings[splitStrings.length - 1]));
        return String.valueOf(sb);
    }

    public static String reverse(String str) {
        StringBuilder sb = new StringBuilder();
        for (int i = str.length() - 1; i >= 0; i--) {
            sb.append(str.charAt(i));
        }
        return String.valueOf(sb);
    }
}

参考链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/solution/mian-shi-ti-58-i-fan-zhuan-dan-ci-shun-xu-shuang-z/

二叉树 https 网络安全 java 编程算法

0 人点赞