2923.找到冠军(简单)
法1:
class Solution:
def findChampion(self, grid: List[List[int]]) -> int:
Winner = 0
n = len(grid)
loser = [0 for _ in range(n)]
for i in range(n):
for j in range(n):
if grid[i][j] == 1 and i != j:
loser[j] = 1
for index in range(n):
if loser[index] == 0:
return index
法2:
class Solution:
def findChampion(self, grid: List[List[int]]) -> int:
n = len(grid)
for i, line in enumerate(grid):
if sum(line) == n - 1:
return i
22.括号生成(中等)
思路1→暴力法:
把所有可能的组合列出,去除不合格的可能。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def generate(A):
if len(A) == 2 * n:
if valid(A):
ans.append("".join(A))
else:
A.append('(')
generate(A)
A.pop()
A.append(')')
generate(A)
A.pop()
def valid(A):
bal = 0
for c in A:
if c =='(':
bal += 1
else:
bal -= 1
if bal < 0:
return False
return bal == 0
ans = []
generate([])
return ans
思路2→回溯法:
对思路1
进行改进,我们可以只在序列仍然保持有效时才添加 ‘(’
或 ‘)’
,而不是每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
def backtrack(S, left, right):
if len(S) == 2 * n:
ans.append(''.join(S))
return
if left < n:
S.append('(')
backtrack(S, left + 1, right)
S.pop()
if right < left:
S.append(')')
backtrack(S, left, right + 1)
S.pop()
backtrack([], 0, 0)
return ans
思路3→递归法:
class Solution:
@lru_cache(None)
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return ['']
ans = []
for c in range(n):
for left in self.generateParenthesis(c):
for right in self.generateParenthesis(n - 1 - c):
ans.append('({}){}'.format(left, right))
return ans
23. 合并K个升序链表(困难)
思路:
把链表元素全部加到数组中,对数组排序,然后将数组元素组成链表。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
nums = []
head = ListNode(0)
current = head
for li in lists:
while li:
nums.append(li.val)
li = li.next
nums.sort()
for num in nums:
current.next = ListNode(num)
current = current.next
return head.next
2924. 找到冠军 II (中等)
思路:
把所有节点的degree
值设为0
,意为没输过,如果遍历到一个节点没输过,且当前没有冠军节点,那么这个节点就是冠军,否则就是没有冠军。
class Solution:
def findChampion(self, n: int, edges: List[List[int]]) -> int:
degree = [0] * n
for x, y in edges:
degree[y] += 1
champion = -1
for i, d in enumerate(degree):
if d == 0:
if champion == -1:
champion = i
else:
return -1
return champion
24.两两交换链表中的节点 (中等)
关键思路:
需要额外的节点来记录prev, cur, temp, next
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head == None or head.next == None:
return head
temp = ListNode(0)
next_one = ListNode(0)
prev = ListNode(0)
newhead = ListNode(0)
newhead.next = head
prev = newhead
cur = head
while cur != None and cur.next != None:
next_one = cur.next.next
temp = cur.next
cur.next = temp.next
temp.next = cur
prev.next = temp
prev = cur
cur = next_one
return newhead.next
25. K 个一组翻转链表(困难)
关键思路:
分为两个函数去实现:
函数1
:把K
个链表全部倒转,需要四个辅助指针。
函数2
:找到K
个链表,把K
个链表取下再装回,需要四个辅助指针。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverse(self, head:ListNode, tail:ListNode):
prev = tail.next
p = head
while prev != tail:
nex = p.next
p.next = prev
prev = p
p = nex
return tail, head
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
hair = ListNode(0)
hair.next = head
pre = hair
while head:
tail = pre
# 查看剩余部分长度是否大于等于 k
for i in range(k):
tail = tail.next
if not tail:
return hair.next
nex = tail.next
head, tail = self.reverse(head, tail)
# 把子链表重新接回原链表
pre.next = head
tail.next = nex
pre = tail
head = tail.next
return hair.next
26.删除有序数组中的重复项(简单)
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
index = 0
for i in range(1, n):
if nums[i] != nums[index]:
index += 1
nums[index] = nums[i]
return index + 1
27. 移除元素 (简单)
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
index = 0
for i in range(len(nums)):
if nums[i] != val:
nums[index] = nums[i]
index += 1
return index
28. 找出字符串中第一个匹配项的下标 (简单)
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
h = len(haystack)
n = len(needle)
i = 0
index = 0
while i <= h - n:
for j in range(n):
if haystack[i + j] == needle[j]:
index += 1
if index == n:
return i
index = 0
i += 1
return -1
29. 两数相除 (中等)
关键思路:
为方便运算,将除数和被除数的符号统一;又为了不溢出,故将除数和被除数变为负数。
同样,在运算过程中为了避免溢出,把 A+B < C
的比较换为 A < C - B
。
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
INT_MIN, INT_MAX = -2**31, 2 ** 31 - 1
if dividend == INT_MIN:
if divisor == 1:
return INT_MIN
if divisor == -1:
return INT_MAX
if divisor == INT_MIN:
return 1 if dividend == INT_MIN else 0
if dividend == 0:
return 0
rev = False
if dividend > 0:
dividend = -dividend
rev = not rev
if divisor > 0 :
divisor = -divisor
rev = not rev
def quickAdd(y:int, z:int, x:int) -> bool:
result, add = 0, y
while z > 0:
if (z & 1) == 1:
if result < x - add:
return False
result += add
if z != 1:
if add < x - add:
return False
add += add
z >>= 1
return True
left, right, ans = 1, INT_MAX, 0
while left <= right:
# 注意溢出,并且不能使用除法
mid = left + ((right - left) >> 1)
check = quickAdd(divisor, mid, dividend)
if check:
ans = mid
# 注意溢出
if mid == INT_MAX:
break
left = mid + 1
else:
right = mid - 1
return -ans if rev else ans