大灰羊
0%

力扣每日两题2022/2/24

发表于 更新于 分类于
本文字数： 2.6k 阅读时长 ≈ 2 分钟

344.反转字符串

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

示例 1：

输入：s = [“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]

示例 2：

输入：s = [“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]

1
2
3
4
5
6
7
8
9
10
11
12
13
def reverseString(s):
    i , j = 0,len(s) -1
    while i <= j:
        s[i],s[j] = s[j],s[i]
        i += 1
        j -= 1
    return s

if __name__ == '__main__':
    s = ["h","e","l","l","o"]
    s2 = ["H","a","n","n","a","h"]
    print(reverseString(s))
    print(reverseString(s2))

557.反转字符串中的单词III

给定一个字符串s，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 1：
输入：s = “Let’s take LeetCode contest”
输出：”s’teL ekat edoCteeL tsetnoc”

示例 2:
输入： s = “God Ding”
输出：”doG gniD”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 方法一：
def reverseWords(s):
    tmp = s.split(" ")  # ["Let's", 'take', 'LeetCode', 'contest']
    n = len(tmp)
    for i in range(n):
        tmp[i] = list(tmp[i])
    for item in tmp:
        i = 0
        j = len(item) - 1
        while i <= j:
            item[i],item[j] = item[j],item[i]
            i += 1
            j -= 1
    for i in range(n):
        tmp[i] = "".join(tmp[i])
    return " ".join(tmp)

# 方法二：字符串切片 -> good!
def reverseWords2(s):
    tmp = s[::-1].split(" ")
    i,j = 0 ,len(tmp) - 1
    while i <= j:
        tmp[i],tmp[j] = tmp[j] ,tmp[i]
        i += 1
        j -= 1
    return " ".join(tmp)

if __name__ == '__main__':
    s = "Let's take LeetCode contest"
    print(reverseWords(s))
    print(reverseWords2(s))

19.删除链表的第n个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class ListNode:
     def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def removeNthFromEnd(head,n):
    def getLength(head: ListNode) -> int:
        length = 0
        while head:
            length += 1
            head = head.next
        return length

    dummy = ListNode(0, head)
    length = getLength(head)
    cur = dummy
    for i in range(1, length - n + 1):
        cur = cur.next
    cur.next = cur.next.next
    return dummy.next

876.链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 利用列表 ： 因为链表没有下标，故可以先遍历存到列表中 时间空间复杂度为O（n）
def middleNode(head):
    A = [head]
    while A[-1].next:
        A.append(A[-1].next)
    return A[len(A) // 2]

# 单指针法 ： 先遍历链表拿到链表长度n，当指针指到n/2时，返回当前值
def middleNode2(head):
    n,cur = 0,head
    while cur:
        n += 1
        cur = cur.next
    k,cur = 0,head
    while k < n // 2:
        k += 1
        cur = cur.next
    return cur

# 双指针法: 快慢指针法，遍历链表，慢指针一次走一步，快指针一次走两步，当快指针走到结尾时，慢指针走到链表中间
def middleNode3(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow