[Mock] Random 22
6830 ワード
2番目の問題は...別の質問だと勘違いして、わざと3問解答しました…^^
1710. Maximum Units on a Truck
You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:
numberOfBoxesi is the number of boxes of type i.
numberOfUnitsPerBoxi is the number of units in each box of the type i.
You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.
Return the maximum total number of units that can be put on the truck.
My Answer 1: Accepted (Runtime: 256 ms - 17.03% / Memory Usage: 14.7 MB - 70.80%)
class Solution:
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
ans = 0
boxTypes = sorted(boxTypes, key=lambda unit: unit[1], reverse=True)
for i in range(len(boxTypes)):
if truckSize < boxTypes[i][0]:
ans += truckSize * boxTypes[i][1]
break
else:
ans += boxTypes[i][0] * boxTypes[i][1]
truckSize -= boxTypes[i][0]
return ans
最大セルをセル数の昇順で並べ替えます.sorted(boxTypes, key=lambda unit: unit[1], reverse=True)
ソート方法についてboxTypes.sort(key=lambda x: -x[1])
=>reverseの代わりに負の値を使用することもできます大きな値から
truckSize
を減算し、개수 * units
を加算if truckSize < boxTypes[i][0]:
=>一部の箱のみを使用する必要がありますので、数量=truckSize
1721. Swapping Nodes in a Linked List
You are given the head of a linked list, and an integer k.
Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).
My Answer 1: Accepted (Runtime: 1168 ms - 25.72% / Memory Usage: 48.9 MB - 28.71%)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapNodes(self, head: ListNode, k: int) -> ListNode:
h1 = head
cnt = 0
n = 0
arr = []
while head:
n += 1
arr.append(head.val)
head = head.next
head = h1
while head:
cnt += 1
if cnt == k:
head.val = arr[-k]
elif cnt == n - k + 1:
head.val = arr[k-1]
head = head.next
return h1
swapはまず2つの値を知ってから、リストにすべての値をリストして+長さを求めます.再び
head
から開始し、前k
2番目と後k
で2番目の値を交換するSolution 1: Accepted (Runtime: 1144 ms - 30.07% / Memory Usage: 48.7 MB - 94.45%)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapNodes(self, head: ListNode, k: int) -> ListNode:
first = last = head
for i in range(1, k):
first = first.next
null_checker = first
while null_checker.next:
last = last.next
null_checker = null_checker.next
first.val, last.val = last.val, first.val
return head
first
前にk
2番目の値を指し、last
後ろにk
2番目の値を指すその後
val
値のみ交換Solution 2: Accepted (Runtime: 1352 ms - 14.14% / Memory Usage: 48.9 MB = 56.44%)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapNodes(self, head: ListNode, k: int) -> ListNode:
dummy = pre_right = pre_left = ListNode(next=head)
right = left = head
for i in range(k-1):
pre_left = left
left = left.next
null_checker = left
while null_checker.next:
pre_right = right
right = right.next
null_checker = null_checker.next
if left == right:
return head
pre_left.next, pre_right.next = right, left
left.next, right.next = right.next, left.next
return dummy.next
ダイレクトスイッチノードpre_left
、pre_right
、left
、right
の4つのポインタ.pre_left
,left
は、前にk-1
,k
の2番目の値を指す.pre_right
,right
の後にk+1
,k
の2番目の値を指すpreによるnode swap
24. Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)
My Answer 1: Accepted (Runtime: 64 ms - 5.47% / Memory Usage: 14.3 MB - 14.59%)
# 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: ListNode) -> ListNode:
pair = 0
h1 = ListNode(0, head)
h2 = h1
while h1:
if h1.next and h1.next.next:
tmp1 = ListNode(h1.next.val, h1.next.next.next)
tmp2 = ListNode(h1.next.next.val, tmp1)
h1.next = tmp2
h1 = h1.next.next
else:
h1 = h1.next
return h2.next
一番前にダミーノードnextとnextを追加nextの2つをチェックtmp1
戻る値を含む、tmp2
前進する値を含むnext = tmp2
swap時に2つのグリッドを移動問題は多くない...私はこの問題だと思って、理解して、やっと中間ではないことに気づいた.ほほほ
Solution 1: Accepted (Runtime: 76 ms - 5.47% / Memory Usage: 14.4 MB - 14.59%)
# 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: ListNode) -> ListNode:
pre, pre.next = self, head
while pre.next and pre.next.next:
a = pre.next
b = a.next
pre.next, b.next, a.next = b, a, b.next
pre = a
return self.next
これと同様に、pre.next and pre.next.next
をwhile文の条件として直接使用してください.swap時に新規ノードを作成しない
pre.next, b.next, a.next = b, a, b.next
Reference
この問題について([Mock] Random 22), 我々は、より多くの情報をここで見つけました https://velog.io/@jsh5408/Mock-Random-22テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol