LeetCode day10

4 minutes read
LeetCode
#LeetCode
views 713 words

234. Palindrome Linked List

Topic: Linked list, Two pointer

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:

  • Could you do it in O(n) time and O(1) space?

Approach1

my, 堆栈

def isPalindrome(head: ListNode) -> bool:
    if not head or not head.next: return True
    stack = []
    curr = head
    while(curr):
        stack.append(curr)
        curr = curr.next
    node1 = head
    while(stack):
        node2 = stack.pop()
        if node1.val != node2.val:
            return False
        node1 = node1.next
    return True

时间复杂度：O(N); 空间复杂度：O(N)

Approach2

  • 快慢指针 反转链表
  • 设置快慢指针
  • 每次快指针增加两个，慢指针增加一个
  • 这样当快指针结尾时，慢指针指向了链表的中间
  • 用慢指针逆序链表的后半部分，利用Python交换的特性，不需要额外的tmp结点

  • 一个从头开始，一个从中间开始，判断两者是否相同

    def isPalindrome(head: ListNode) -> bool:
slow,fast,prev = head,head,None
while fast is not None:
    slow = slow.next
    fast = fast.next.next if fast.next is not None else fast.next
while slow is not None:
    slow.next, slow, prev= prev, slow.next, slow
while head and prev:
    if head.val != prev.val:
        return False
    head = head.next
    prev = prev.next
return True

237. Delete Node in a Linked List

Topic: Linked list

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Given linked list – head = [4,5,1,9], which looks like following:

 

Example 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Note:

  • The linked list will have at least two elements.
  • All of the nodes’ values will be unique.
  • The given node will not be the tail and it will always be a valid node of the linked list.
  • Do not return anything from your function.

Approach1

把当前结点的值用下一个节点的值覆盖, 然后跳过下一个节点 (相当于让当前节点冒充下一个节点)

def deleteNode(node):
    """
    :type node: ListNode
    :rtype: void Do not return anything, modify node in-place instead.
    """
    node.val = node.next.val
    node.next = node.next.next
    # print(node)
    '''
input:   
[4,5,1,9]
1

output:
[4,5,9]

print:
ListNode{val: 9, next: None}
    '''

242. Valid Anagram

Topic: Sort, Hash Table

Given two strings s and t , write a function to determine if t is an anagram of s. (判断 t 是否是 s 的字母异位词)

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false
Note:
You may assume the string contains only lowercase alphabets.

Follow up:

  • What if the inputs contain unicode characters? How would you adapt your solution to such case?

Approach1

my

def isAnagram(s: str, t: str) -> bool:
    # M1
    s = "".join((lambda x:(x.sort(),x)[1])(list(s)))
    t = "".join((lambda x:(x.sort(),x)[1])(list(t)))
    return s == t
    
    # M2
    # s = list(s)
    # t = list(t)
    # s.sort()
    # t.sort()
    # return s == t
    
    # M3
    # return sorted(s) == sorted(t)

Approach2

faster

def isAnagram(s: str, t: str) -> bool:
    # 定义默认布尔值参与后续运算
    result = True
    # 利用 Python 数据结构 set 去重去序
    set_tmp = set(s)
    # 先判断组成字符串的各个字符元素是否一致
    if set_tmp == set(t):
        for i in set_tmp:
            # 利用逻辑运算符判断各个字符元素的数量一致，均为 True 才输出 True
            result = result and (s.count(i) == t.count(i))
    else:
        result = False
    return (result)

268. Missing Number

Topic: Array, Math, Bit Manipulation

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:

  • Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Approach1

my

def missingNumber(nums: List[int]) -> int:
    nums.sort()
    for i in range(len(nums)):
        if i != nums[i]:
            return i
    return nums[len(nums)-1]+1  # 比如 nums 为[0], 就return 1

Approach2

直接理想总和（高斯累加，（首项+尾项*项数//2） 减去 数组总和 (原本序列应该的总和 减去 当前序列的总和)

def missingNumber(nums: List[int]) -> int:
    return (len(nums)+1)*len(nums)//2-sum(nums)

Approach3

假如我们数组不缺任何数 [0, 1, 2]，有 0−nums[0]+1−nums[1]+2−nums[2]=0. 即使打乱数据 [2, 0, 1], 0−nums[0]+1−nums[1]+2−nums[2]=0−2+1−0+2−1=0.

所以，在不缺少任何数字，不管如何打乱数组，我们都有 每个数 索引号和数相减的和都为零

def missingNumber(nums: List[int]) -> int:
    res = len(nums)
    for idx, num in enumerate(nums):
        res += idx - num
    return res

时间复杂度：O(n)

Approach4

二分法

def missingNumber(nums: List[int]) -> int:
    nums.sort()
    left = 0
    right = len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > mid:
            right = mid 
        else:
            left = mid + 1
    return left

时间复杂度：O(nlogn)