AlphaCamp Leetcode 訓練營 03. Map & Set — 觀念入門

課程資訊

此為Alphacamp的Leetcode訓練營，內文僅為個人心得。

Map

JS高階語言(註1)的部分，用於Hash Map，以鍵(key)取值(value)

註1：代表該功能並非任何語言都會有，例如C、C++無Map功能

1. MDM
2. 類似 object (key-value pairs)，但object的key限定字串，Map不受限制
3. Map 資料有序，依 key-value pairs 寫入的順序 (insertion order)；另外效率會比Object更好
4. 不要再把 Object 当作 Hash Map

Set

用於處理「合集」概念數學運算，元素 (element) 可以是任何資料型態，所有的值都是唯一的 (unique values)

1. MDN
2. Set 內部用 === 來判斷是否有重複值(例外：NaN，因為NaN !== NaN)

HashMap

1. 雜湊表（Hash table），是根據鍵（Key）而直接查詢在記憶體儲存位置的資料結構。
2. 通過計算一個關於鍵值的函數，將所需查詢的數據映射到表中一個位置來查詢記錄，這加快了查找速度。
3. 這個映射函數稱做雜湊函數，存放記錄的數組稱做雜湊表。
4. HashMap Collision：不同的key存放到同一個空間；解法1.Link-List、2.在該key的下一個位置存放多出的key
5. Dynamic Hash：當現有空間時，以不更動現有資料為基準，新增額外儲存空間給Hash使用，資料庫實作時會用到
6. hash table 操作的(時間)複雜度不一定是 O(1)，存取時間在最佳情況下是 O(1)

練習題：

242. Valid Anagram

link

題目說明：

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

給兩個字串s、t，如果這兩個字串互為相同字母異序詞，回傳true，反之傳false

條件：

• 1 <= s.length, t.length <= 5 * 104
• s and t consist of lowercase English letters.

解法：

961. N-Repeated Element in Size 2N Array

link

題目說明：

You are given an integer array nums with the following properties:

• nums.length == 2 * n.
• nums contains n + 1 unique elements.
• Exactly one element of nums is repeated n times.

Return the element that is repeated n times.

條件：

• 2 <= n <= 5000
• nums.length == 2 * n
• 0 <= nums[i] <= 104
• nums contains n + 1 unique elements and one of them is repeated exactly n times.

解法：

136. Single Number

link

題目說明：

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

條件：

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

解法：

80. Remove Duplicates from Sorted Array II (M)

link

題目說明：

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

條件：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums is sorted in non-decreasing order.

解法：

要求

• O(1) extra memory
• modifying the input array in-place
• 思考

1. 因為涉及in-place修改，操作array，第一個想到的是splice方法，因為splice會修改array，所以要從末端開始往前迭代，這樣才不用額外操作index
2. 用counter紀錄相同次數，如果目前迭代對象跟下一個對象相同，counter就加1
3. 當counter大於1的時候代表已經超過兩個了，開始刪除，直到迭代對象跟下一個對象不相同

260. Single Number III (M)

link

題目說明：

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

條件：

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• Each integer in nums will appear twice, only two integers will appear once.

解法：

非 constant extra space.