​LeetCode刷题实战186:翻转字符串里的单词 II

简介: 算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 翻转字符串里的单词 II  ,我们先来看题面:https://leetcode-cn.com/problems/reverse-words-in-a-string-ii/

Given an input string , reverse the string word by word.


Example:


Input:  ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]

Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

题意


给定一个字符串,逐个翻转字符串中的每个单词。

示例

示例:
输入: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
输出: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
注意:
单词的定义是不包含空格的一系列字符
输入字符串中不会包含前置或尾随的空格
单词与单词之间永远是以单个空格隔开的
进阶:使用 O(1) 额外空间复杂度的原地解法。

解题


思路大致为:先对每个单词进行翻转,然后对句子进行翻转即可。对单词反转后,单词变得不伦不类,比如 blue 变成了 eulb,并且此时每个单词的相对位置没变。

再对句子进行一次翻转,不仅把每个单词变正常了,且每个单词的相对位置进行了翻转。

翻转的函数实现很简单,给定 str 和待翻转的索引区间即可。

class Solution {
public void reverseWords(char[] str) {
        int i = 0;
        for (int j = 0; j < str.length; j++) { // aTbTc
            if (str[j] == ' ') {
                reverse(str, i, j);
                i = j + 1;
            }
        }
        reverse(str, i, str.length); // 最后一个单词末尾没有空格
        System.out.println(String.valueOf(str));
        reverse(str, 0, str.length); // 整体再翻转一次
    }
    /**
     * 将 str 的 [i, j] 进行翻转,如 "the" 转换后变成 “eht”
     * 注意,[i,j] 是左闭右开
     *
     * @param str
     * @param i
     * @param j
     */
    private void reverse(char[] str, int i, int j) {
        for (int k = i; k < (i + j) / 2; k++) {
            char tmp = str[k]; // 位置 k 的元素
            int g = j - 1 - k + i; // 位置 k 的对称位置
            str[k] = str[g];
            str[g] = tmp;
        }
    }
}

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

相关文章
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
36 1
|
2月前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
34 1
|
2月前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
25 9
|
2月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
19 0
|
2月前
Leetcode(最后一个单词长度)
这篇文章介绍了两种解决LeetCode第58题的方法,即计算给定字符串中最后一个单词的长度,方法包括翻转字符串和逆向遍历统计。
22 0
|
2月前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
30 0
|
2月前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
19 0
|
2月前
【LeetCode 19】541.反转字符串II
【LeetCode 19】541.反转字符串II
21 0
|
2月前
【LeetCode 18】6.2.反转字符串
【LeetCode 18】6.2.反转字符串
15 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行