## LeetCode day10

views 713 words

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

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

### Approach1

my, 堆栈

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

### Approach2

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

def isPalindrome(head: ListNode) -> bool:
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
return False
prev = prev.next
return True

## 237. Delete Node in a Linked List

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

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.

• 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

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

### Approach3

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

### 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