标签：head return int res self next 指针
面试题 16.06. 最小差
class Solution:
def smallestDifference(self, a: List[int], b: List[int]) -> int:
a.sort(); b.sort()
i = j = 0
res = float('inf')
while i < len(a) and j < len(b):
res = min(res, abs(a[i]-b[j]))
if a[i] == b[j]:
return 0
elif a[i] < b[j]:
i += 1
else:
j += 1
return res
面试题 16.21. 交换和
class Solution:
def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:
'''
假设array1 中 a 与 array2 中 b 交换
s1 = sum(array1)
s2 = sum(array2)
交换后
s1 - a + b = s2 - b + a
即 s1 - s2 = 2(a - b)
'''
d = sum(array1) - sum(array2)
d /= 2
array1.sort(); array2.sort()
i = j = 0
while i < len(array1) and j < len(array2):
if array1[i] - array2[j] == d: return [array1[i], array2[j]]
elif array1[i] - array2[j] < d: i += 1
elif array1[i] - array2[j] > d: j += 1
return []
19. 删除链表的倒数第 N 个结点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
h = ListNode(0, head)
slow = h; fast = head
for i in range(n):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return h.next
581. 最短无序连续子数组
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
n = sorted(nums)
if nums == n: return 0
l = 0; r = len(nums) - 1
while nums[l] == n[l]: l += 1
while nums[r] == n[r]: r -= 1
return r - l + 1
392. 判断子序列
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
n, m = len(s), len(t)
i = j = 0
while i < n and j < m:
if s[i] == t[j]:
i += 1
j += 1
return i == n
61. 旋转链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
pre = ListNode(0)
pre.next = slow = fast = head
while k > 0:
fast = fast.next
k -= 1
while fast:
pre = pre.next
slow = slow.next
fast = fast.next
return pre, slow
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
cur = head
cnt = 0
if not head or not head.next: return head
while cur:
cur = cur.next
cnt += 1
k = k % cnt
if k == 0: return head
pre, res = self.getKthFromEnd(head, k)
pre.next = None
p = res
while p.next:
p = p.next
p.next = head
return res
54. 螺旋矩阵
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix: return []
m = len(matrix); n = len(matrix[0])
l, r, t, b = 0, n - 1, 0, m - 1
res = []
num, tar = 1, m * n
while num <= tar:
for i in range(l, r + 1): # left to right
if num <= tar:
res.append(matrix[t][i])
num += 1
t += 1
for i in range(t, b + 1): # top to bottom
if num <= tar:
res.append(matrix[i][r])
num += 1
r -= 1
for i in range(r, l - 1, -1): # right to left
if num <= tar:
res.append(matrix[b][i])
num += 1
b -= 1
for i in range(b, t - 1, -1): # bottom to top
if num <= tar:
res.append(matrix[i][l])
num += 1
l += 1
return res
59. 螺旋矩阵 II
class Solution:
def generateMatrix(self, n: int) -> [[int]]:
l, r, t, b = 0, n - 1, 0, n - 1
res = [[0 for _ in range(n)] for _ in range(n)]
num, tar = 1, n * n
while num <= tar:
for i in range(l, r + 1): # left to right
res[t][i] = num
num += 1
t += 1
for i in range(t, b + 1): # top to bottom
res[i][r] = num
num += 1
r -= 1
for i in range(r, l - 1, -1): # right to left
res[b][i] = num
num += 1
b -= 1
for i in range(b, t - 1, -1): # bottom to top
res[i][l] = num
num += 1
l += 1
return res
328. 奇偶链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
if not head:
return head
evenHead = head.next
odd, even = head, evenHead
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = evenHead
return head
剑指 Offer II 029. 排序的循环链表
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
"""
class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
if not head:
head = Node(insertVal, head)
head.next = head
return head
p = head
while True:
# 合适位置，插入
if p.val <= insertVal <= p.next.val:
p.next = Node(insertVal, p.next)
return head
# 走到了循环点
elif p.next.val < p.val:
# 需要插入的点比最小值还小/比最大值还大
if insertVal >= p.val or insertVal <= p.next.val:
p.next = Node(insertVal, p.next)
return head
else:
# 走回原点了，还是没找到插入位置，只有一种可能：整个链表只有一种val
# 此时原地插入返回即可
if p.next == head:
p.next = Node(insertVal, p.next)
return head
p = p.next
283. 移动零
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 左指针左边均为非零数；右指针左边直到左指针处均为零。
# 因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。
l = r = 0
while r < len(nums):
if nums[r] != 0:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r += 1
面试题 10.01. 合并排序的数组
class Solution:
def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
"""
Do not return anything, modify A in-place instead.
"""
c = list()
p = q = 0
while p < m and q < n:
if A[p] < B[q]:
c.append(A[p])
p += 1
else:
c.append(B[q])
q += 1
c.extend(A[p:m]) if q >= n else c.extend(B[q:])
A[:] = c
class Solution:
def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
"""
Do not return anything, modify A in-place instead.
"""
A[m:] = B
A.sort()
面试题 01.06. 字符串压缩
class Solution:
def compressString(self, S: str) -> str:
return min(S, "".join(k + str(len(list(v))) for k, v in itertools.groupby(S)), key=len)
class Solution:
def compressString(self, S: str) -> str:
i, j, k = 0, 0, len(S)
res = ""
# 「外层循环」i 指向每个首次出现的字符
while i < k:
# 「内层循环」j 向前遍历，直到字符串末尾或找到与 s[i] 不同的字符时跳出
while j < k and S[i] == S[j]:
j += 1
# 压缩字符串，添加至 res
res += (S[i])
res += (str(j - i))
# 令 i 指向下一个首次出现的字符
i = j
# 对比「压缩字符串」和「原字符串」长度，返回较短的
return res if len(res) < k else S
面试题 16.16. 部分排序
class Solution:
def subSort(self, array: List[int]) -> List[int]:
a = sorted(array)
if a == array: return [-1,-1]
left = 0; right = len(array) - 1
while array[left] == a[left]: left += 1
while array[right] == a[right]: right -= 1
return [left, right]
标签：head,
return,
int,
res,
self,
next,
指针
From： https://blog.51cto.com/u_15905340/5919330