[Mock] Random 22



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から開始し、前k2番目と後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前にk2番目の値を指し、last後ろにk2番目の値を指す
その後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_leftpre_rightleftrightの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 = tmp2swap時に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