1041. 困於環中的機器人

題庫鏈接: 1041. 困於環中的機器人.

題乾

在無限的平面上，機器人最初位於 (0, 0) 處，面朝北方。機器人可以接受下列三條指令之一：

• "G"：直走 1 個單位
• "L"：左轉 90 度
• "R"：右轉 90 度
• 機器人按順序執行指令 instructions，並一直重覆它們。

只有在平面中存在環使得機器人永遠無法離開時，返回 true。否則，返回 false。

示例

示例 1

輸入："GGLLGG" 輸出：true 解釋：機器人從 (0,0) 移動到 (0,2)，轉 180 度，然後回到 (0,0)。 重覆這些指令，機器人將保持在以原點為中心，2 為半徑的環中進行移動。

示例 2

輸入："GG" 輸出：false 解釋：機器人無限向北移動。

示例3

輸入："GL" 輸出：true 解釋： 機器人按 (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ... 進行移動。

提示

• 1 <= instructions.length <= 100
• instructions[i] 在 {'G', 'L', 'R'} 中

思路

• 只要迴圈一次之後方向不是在向北或一次之後就在原點，
• 那麼迴圈四次或者四次之內之後就可以回到初始位置
• 使用兩個變數記錄點的位置，使用兩個變數記錄機器人的方向。
• 遍歷指令，如果為‘L’， 執行dx, dy = -dy, dx（橫坐標為縱坐標的相反數，縱坐標為橫坐標），如果為‘R’，執行dx, dy = dy, -dx（橫坐標為縱坐標，縱坐標為橫坐標的相反數）。
• 最後只要方向不向北或已經在原點機器人就可以離開。

代碼解析

class Solution(object):
    def isBoomerang(self, points):
        """
        :type points: List[List[int]]
        :rtype: bool
        """

        A,B,C=points
        return (A[0]-B[0])*(B[1]-C[1])-(A[1]-B[1])*(B[0]-C[0])!=0

運行結果

237. 刪除鏈表中的節點

題庫鏈接: 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(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val, node.next = node.next.val, node.next.next

運行結果

1. 兩數之和

題庫鏈接: 1. 兩數之和.

題乾

給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那 兩個 整數，並返回他們的數組下標。

你可以假設每種輸入只會對應一個答案。但是，你不能重覆利用這個數組中同樣的元素。

示例

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

解法1

思路：

• 暴力破解，遍歷每一個元素，並查找是否存在兩個數和為target

代碼解析

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for k in range(i + 1, len(nums)):
                if nums[i] + nums[k] == target:
                    return [i, k]
                    break

運行結果

當然解法一是非常暴力的會消耗很長時間和記憶體空間，接下來介紹一個更好的解法。

解法2

• 使用一個字典記錄list裡面的值和索引，遍歷list，如果target-num在字典裡面返回兩個索引值，否則返回None

代碼解析

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for index, num in enumerate(nums):
            another_num = target - num
            if another_num in hashmap:
                return [hashmap[another_num], index]
            hashmap[num] = index
        return None

結尾

• 雞湯：人的一生，既不是想象中的那麼好，也不是想象中的那麼壞。每個人的背後都會有心酸，都會有無法言說的艱難。每個人都會有自己的淚要擦，都會有自己的路要走。

歡迎加入公眾號學習交流，公眾號會分享，爬蟲，數據分析和Python後端等內容。