雲林SONG

LeetCode 解題練習：Merge Sorted Array

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/merge-sorted-array/

中文描述

給定兩個由小排到大的陣列 nums1, nums2，以及兩個整數m, n 分別來表示陣列 nums1 與 nums2 的元素有多少個。請將 nums1與 nums2 合併成新的由小排到大之陣列。請將此陣列存到 nums1 裡，因此 nums1 長度為 m + n，其中最後 n 個元素都是 0。

範例一：

輸入 nums1 = [1, 3, 5, 7, 0, 0, 0], m = 4, nums2 = [2, 4, 6], n = 3

輸出 [1, 2, 3, 4, 5, 6, 7]

範例二：

輸入 nums1 = [1, 3, 5, 7], m = 4, nums2 = [], n = 0

輸出 [1, 3, 5, 7]

範例三：

輸入 nums1 = [], m = 0, nums2 = [2, 4, 6], n = 3

輸出 [2, 4, 6]

解法：

比較兩陣列最右邊的元素nums1[a] 與 nums2[b]，merged 的最右邊元素merged[w]設定為較大的那一個。請參考下圖動畫：

Python Code

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        w, a, b = m + n - 1, m - 1, n - 1

        while b >= 0:
            if a >= 0 and nums1[a] > nums2[b]:
                nums1[w] = nums1[a]
                a -= 1
            else:
                nums1[w] = nums2[b]
                b -= 1
            w -= 1
        

LeetCode 解題練習：Swap Nodes in Pairs

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/swap-nodes-in-pairs/

中文描述

給定一個鏈結串列(linked list)，將兩個相鄰節點交換後回傳開頭的節點。注意不得修改節點內的值。

範例一：

輸入 head = [1, 3, 5, 7]

輸出 [3, 1, 7, 5]

解法：

用一個變數 t 作為交換相鄰兩個節點的暫時替代空間，用來交換第一個節點 head 與第二個節點head.next 。依照下列步驟來交換相鄰的兩個節點：

t 先設定為 head.next。
head.next 設定為 swap(t.next)。
t.next 設定為 head。

Python Code

# 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: # 目前節點或下一個節點為 None
            return head # 傳回 head

        t = head.next # 節點 t 指向目前的相鄰的第二個節點
        head.next = self.swapPairs(t.next) # 目前節點指向下一組交換完的第一個節點
        t.next = head # 節點 t 指向目前的相鄰的第一個節點

        return t # 傳回相鄰的第一個節點

C++ Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if( head == nullptr || head->next == nullptr) // 目前節點或下一個節點為 null
            return head; // 回傳 head
        
        ListNode *t = head->next; // 節點 t 指向目前的相鄰的第二個節點
        head->next = swapPairs(t->next); // 目前節點指向下一組交換完的第一個節點
        t->next = head; // 節點 t 指向目前的相鄰的第一個節點

        return t; // 傳回相鄰的第一個節點
    }
};

LeetCode 解題練習：Reverse String

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/reverse-string/

中文描述

給定一個字元陣列 s ，撰寫一個函式來反轉此字串。

注意請修改此陣列來完成程式碼。

範例一：

輸入 s = [ "a", "b", "c", "d", "e"]

輸出 ["e", "d", "c", "b", "a"]

範例二：

輸入 s = [ "G", "o", "o", "d", "s"]

輸出 ["s", "d", "o", "o", "G"]

解法：

使用兩個指標 left 與 right 分別表示陣列的頭與尾，從最左邊與最右邊依序互換。

Python Code

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left = 0
        right = len(s) - 1
        while left <= right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
        

C++ Code

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while(left < right)
        {
            swap(s[left], s[right]);
            left++;
            right--;
        }
    }
};