【DW組隊學習—LeetCode】day16

237. 删除連結清單中的節點

請編寫一個函數，使其可以删除某個連結清單中給定的（非末尾）節點。傳入函數的唯一參數為 要被删除的節點 。

現有一個連結清單 – head = [4,5,1,9]，它可以表示為:

【示例 1】輸入：head = [4,5,1,9], node = 5 輸出：[4,1,9]

解釋：給定你連結清單中值為 5 的第二個節點，那麼在調用了你的函數之後，該連結清單應變為 4 -> 1 -> 9.

【示例 2】 輸入：head = [4,5,1,9], node = 1 輸出：[4,5,9]

解釋：給定你連結清單中值為 1 的第三個節點，那麼在調用了你的函數之後，該連結清單應變為 4 -> 5 -> 9.

提示：

• 連結清單至少包含兩個節點。
• 連結清單中所有節點的值都是唯一的。
• 給定的節點為非末尾節點并且一定是連結清單中的一個有效節點。
• 不要從你的函數中傳回任何結果。

嘗試思路：

将要删除的節點直接換成下一節點

代碼：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, 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
           

238. 除自身以外數組的乘積

給你一個長度為 n 的整數數組 nums，其中 n > 1，傳回輸出數組 output ，其中 output[i] 等于 nums 中除

nums[i] 之外其餘各元素的乘積。

【示例】輸入: [1,2,3,4] 輸出: [24,12,8,6]

提示： 題目資料保證數組之中任意元素的全部字首元素和字尾（甚至是整個數組）的乘積都在 32 位整數範圍内。

說明: 請不要使用除法，且在 O(n) 時間複雜度内完成此題。

**進階：**你可以在常數空間複雜度内完成這個題目嗎？（ 出于對空間複雜度分析的目的，輸出數組不被視為額外空間。）

嘗試思路1：暴力法

連乘時判斷是否跳過目前元素

代碼：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = []    
        for i in range(len(nums)):
            a = 1 
            for j in range(len(nums)):
                if i == j:
                    a = a
                else:
                    a = a*nums[j]
            result.append(a)
        return result
           

【錯誤】複雜度較高，逾時

292. Nim 遊戲

你和你的朋友，兩個人一起玩 Nim 遊戲：

桌子上有一堆石頭。 你們輪流進行自己的回合，你作為先手。 每一回合，輪到的人拿掉 1 - 3 塊石頭。 拿掉最後一塊石頭的人就是獲勝者。

假設你們每一步都是最優解。請編寫一個函數，來判斷你是否可以在給定石頭數量為 n 的情況下赢得遊戲。如果可以赢，傳回 true；否則，傳回 false 。

【示例 1】輸入：n = 4 輸出：false

解釋：如果堆中有 4 塊石頭，那麼你永遠不會赢得比賽；因為無論你拿走 1 塊、2 塊 還是 3 塊石頭，最後一塊石頭總是會被你的朋友拿走。

【示例 2】輸入：n = 1 輸出：true

【示例 3】輸入：n = 2 輸出：true

提示：

• 1 <= n <= 231 - 1

嘗試思路：

若能被4整除，則赢不了

代碼：

class Solution:
    def canWinNim(self, n: int) -> bool:
        return False if n % 4 == 0 else True