LeetCode 剑指Offer

剑指 Offer 05. 替换空格

题目描述

​ 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

  • 实例：

    1
    2
    输入：head = [1,3,2]
    输出：[2,3,1]

  • 限制

    • 0 <= 链表长度 <= 10000

解题思路

  • 解题思路:

    1. 申请辅助空间。
    2. 调用原生API。

实现代码

  1. Python解法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    # 申请辅助空间
    class Solution:
        def replaceSpace(self, s: str) -> str:
            arr = []
            for sub in s:
                if sub == " ":
                    arr.append('%20')
                else:
                    arr.append(sub)
            res = ''
            for item in arr:
                res += item
            return res

    # 调用原生API
    class Solution:
        def replaceSpace(self, s: str) -> str:
            return s.replace(" ", "%20")

  2. JS/TS解法

    1
    2
    3
    4
    5
    // 调用原生API replace
    // JS/TS Replace 与 Python Replace不同，JS Replace只替换第一个，需要用正则表达式。
    function replaceSpace(s: string): string {
        return s.replace(/\s/g, "%20");
    };

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

题目描述

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

  • 实例：

    1
    2
    3
    4
    5
    输入: s = "abcdefg", k = 2
    输出: "cdefgab"
        
    输入: s = "lrloseumgh", k = 6
    输出: "umghlrlose"

  • 限制

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

解题思路

  • 解题思路:

    1. 切片/调用原生API；
    2. 若不允许切片则创建辅助空间。

实现代码

  1. Python解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 切片
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[:n]
    
# 创建辅助空间
class Solution:
    def reverseLeftWords(self, s:str, n: int) -> str:
        pre,post = "",""
        for i in range(len(s)):
            if i < n:
                post += s[i]
            else:
                pre += s[i]
        return pre + post
  1. Js/Ts解法
1
2
3
4
function reverseLeftWords(s: string, n: number): string {
    // return s.substring(n,s.length) + s.substr(0,n);
    return s.slice(n, s.length) + s.slice(0, n);
};

🔥 LeetCode 热题 HOT 100

20. 有效的括号

题目描述

​ 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串s ，判断字符串是否有效。

​ 有效字符串需满足：

​ 1. 左括号必须用相同类型的右括号闭合。
​ 2. 左括号必须以正确的顺序闭合。
​ 3. 每个右括号都有一个对应的相同类型的左括号

  • 实例

    1
    2
    3
    4
    5
    6
    7
    8
    输入：s = "()"
    输出：true

    输入：s = "()[]{}"
    输出：true

    输入：s = "(]"
    输出：false

  • 提示

    • 1 <= s.length <= 104
    • s 仅由括号 '()[]{}' 组成

解题思路

  • 解题思路

    使用辅助栈，字符串长度为奇数则False，否则遍历字符串，当前为左括号的时候入栈，当右括号时，判断栈顶元素是否匹配括号，匹配则pop栈顶元素，否则，return False；最后判断栈是否还存有元素(即是否有左括号尚未被匹配)，有则False。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s)%2:
            return False
        stack = []
        left = ['(', '{', '[']
        for sub in s:
            if sub in left:
                stack.append(sub)
                continue
            elif not len(stack):
                return False
            if sub == ')' and stack[-1] != '(':
                    return False
            if sub == ']' and stack[-1] != '[':
                    return False
            if sub == '}' and stack[-1] != '{':
                    return False
            stack.pop()
        return not len(stack)