剑指 offer 第 3 天

第 3 天

请实现一个函数，把字符串 <code>s</code> 中的每个空格替换成"%20"。

示例 1：

限制：

题解思路：字符串拼接、数组反向填充

字符串拼接：利用 StringBuilder 可以方便的完成字符串的各种操作

复杂度：时间 O(n) 空间 O(n)

String转为利用字符数组后，计算转换后一共所需空间，然后反向填充字符数组

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 2：

<code>1 &lt;= k &lt; s.length &lt;= 10000</code>

题解思路：字符串拼接、三次反转

字符串拼接：有不同实现方式，利用StringBuilder逐一append、调用subString()方法

subString() 方法：

StringBuilder 方法：

三次反转：利用三次字符串反转，首先反转前 k 个字符，然后反转后 n-k 个字符，最后整体反转 n 个字符，n为字符串长度

字符串反转类似的题目很多，如反转单词、反转前缀、多次反转，利用好 String 内置方法可以方便解答

给定一个字符串 <code>s</code> 和一个整数 <code>k</code>，从字符串开头算起，每计数至 <code>2k</code> 个字符，就反转这 <code>2k</code> 字符中的前 <code>k</code> 个字符。

如果剩余字符少于 <code>k</code> 个，则将剩余字符全部反转。

如果剩余字符小于 <code>2k</code> 但大于或等于 <code>k</code> 个，则反转前 <code>k</code> 个字符，其余字符保持原样。

提示：

<code>1 &lt;= s.length &lt;= 104</code>

<code>s</code> 仅由小写英文组成

<code>1 &lt;= k &lt;= 104</code>

题解思路：过程模拟

过程模拟：一遍遍历遇到该反转的位置便反转，每次反转前判断 n 和 i + k 的大小，从而确定末尾剩余字符不足 k 时，反转多少个元素。反转操作使用双指针交换完成

给你一个字符串 <code>s</code> ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。<code>s</code> 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 <code>s</code> 中单词顺序并用单个空格相连的字符串。

说明：

输入字符串 <code>s</code> 可以在前面、后面或者单词间包含多余的空格。

翻转后单词间应当仅用一个空格分隔。

翻转后的字符串中不应包含额外的空格。

示例 3：

示例 4：

示例 5：

<code>s</code> 包含英文大小写字母、数字和空格 <code>' '</code>

<code>s</code> 中 至少存在一个 单词

题解思路：利用好 API 快速解答、手动编写相关方法、双端队列、双指针

利用正则完成字符串切割：

手动反转字符串数组：

双端队列：先字符串中一个一个单词处理，然后将单词压入队列的头部，再将队列转成字符串即可

双指针：前后指针从后向前搜索单词位置，找到后加入 StringBuilder，继续搜索空格个数，循环如此，直到 left &gt; right

难度简单2收藏分享切换为英文接收动态反馈

给你一个下标从 0 开始的字符串 <code>word</code> 和一个字符 <code>ch</code> 。找出 <code>ch</code> 第一次出现的下标 <code>i</code> ，反转 <code>word</code> 中从下标 <code>0</code> 开始、直到下标 <code>i</code> 结束（含下标 <code>i</code> ）的那段字符。如果 <code>word</code> 中不存在字符 <code>ch</code> ，则无需进行任何操作。

例如，如果 <code>word = "abcdefd"</code> 且 <code>ch = "d"</code> ，那么你应该 反转 从下标 0 开始、直到下标 <code>3</code> 结束（含下标 <code>3</code> ）。结果字符串将会是 <code>"dcbaefd"</code> 。

返回 结果字符串 。

<code>1 &lt;= word.length &lt;= 250</code>

<code>word</code> 由小写英文字母组成

<code>ch</code> 是一个小写英文字母

题解思路：反转部分字符串、

反转部分字符串：利用好 API 快速解答、手动编写方法

利用好 API 快速解答：

手动编写方法：