代码随想录刷题记录 Day8

发表于 更新于 本文字数： 1.5k 阅读时长 ≈ 5 分钟

To Do List

  • DAY 7 回顾
  • LeetCode 344. 反转字符串
  • LeetCode 541. 反转字符串II
  • LeetCode 剑指Offer 05.替换空格
  • LeetCode 151. 翻转字符串里的单词
  • LeetCode 剑指Offer 58-II.左旋转字符串

DAY 7 回顾

（）

LeetCode 344. 翻转字符串

1
Difficulty: Easy

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Translated by zh-CN 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

Example 1:

1
2
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

1
2
Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Constraints:

Translated by zh-CN s[i] 都是 ASCII 码表中的可打印字符

解法：

(JavaScript)

1
2
3
4
5
6
7
8
9
10
/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */

var reverseString = function(s) {
    let len = s.length
    let i = -1, j = len
    while(++i < --j) [s[i], s[j]] = [s[j], s[i]]
};

LeetCode 541. 翻转字符串 II / Reverse String II

1
Difficulty: Easy

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.

Translated by zh-CN 给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

Example 1:

1
2
Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Example 2:

1
2
Input: s = "abcd", k = 2
Output: "bacd"

Constraints:

  • 1 <= s.length <= 10^4
  • s consists of only lowercase English letters.
  • 1 <= k <= 10^4
Translated by zh-CN s 仅由小写英文组成

解法：

(JavaScript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function(s, k) {
    let strarr = s.split("")
    for (let i = 0; i < strarr.length; i += 2*k) {
        if (i + k < strarr.length) {
            let l = i - 1, r = i + k
            while (++l < --r) [strarr[l], strarr[r]] = [strarr[r], strarr[l]]
            continue
        } else {
            let l = i - 1, r = strarr.length
            while (++l < --r) [strarr[l], strarr[r]] = [strarr[r], strarr[l]]
        }
    }
    return strarr.join('')
};

LeetCode 剑指 Offer 05. 替换空格

1
Difficulty: Easy

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

示例 1：

1
2
输入：s = "We are happy."
输出："We%20are%20happy."

限制：

1
0 <= s 的长度 <= 10000

解法：

(JavaScript 法一)

1
2
3
4
5
6
7
/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(s) {
    return s.split(' ').join("%20")
};

PS: 用库函数解这道题很简单的 (x 一般情况下如果要练算法就不要过度依赖于库函数和 API.

(JavaScript 法二)

（其他方法带补充）

LeetCode 151. 翻转字符串里的单词 / Reverse Words in a String

1
Difficulty: Medium

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Translated by zh-CN 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串.
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

Example 1:

1
2
Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

1
2
3
4
Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
反转后的字符串中不能存在前导空格和尾随空格。

Example 3:

1
2
3
4
Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

Constraints:

  • 1 <= s.length <= 104
  • s contains English letters (upper-case and lower-case), digits, and spaces ' '.
  • There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Translated by zh-CN s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词
如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

解法：

(JavaScript 法一)

1
2
3
4
5
6
7
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.match(/[A-Za-z0-9]+/g).reverse().join(' ')
};

PS: 用库函数解这道题很简单的 (x 一般情况下如果要练算法就不要过度依赖于库函数和 API.

(JavaScript 法二)

（其他方法带补充）

LeetCode 剑指 Offer 58 - II. 左旋转字符串

1
Difficulty: Easy

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

示例 1：

1
2
输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：

1
2
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

限制：

  • 1 <= k < s.length <= 10000

解法：

(JavaScript 法一)

1
2
3
4
5
6
7
8
/**
 * @param {string} s
 * @param {number} n
 * @return {string}
 */
var reverseLeftWords = function(s, n) {
    return s.substring(n) + s.substring(0, n)
};

PS: 用库函数解这道题很简单的 (x 一般情况下如果要练算法就不要过度依赖于库函数和 API.

(JavaScript 法二)

（其他方法带补充）

DAY 8 总结