AlphaCamp Leetcode 訓練營 02. String、Array、Object

課程資訊

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

資料結構(Data Structure)

定義：元素所組成的有限集合

目的：有效使用、貯存資料(降低記憶體的使用)

資料

定義：元素的集合

類型：

1. 單元型：數字、整數、字串等等
2. 容器型：一個變數存很多資料(Array、Object)

結構

定義：元素之間的組成關係(在某些語言稱為collection、Container)

資料型態Data Type

描述資料如何貯存的方法，會有下列兩種定義

1. 有哪些資料，這組資料是怎麼組成的 例如依序、依照key值(定義)
2. 這個資料可以怎樣操作、運算(方法)

Abstract Data Type (ADT)

抽象的資料型態

在定義一個資料結構時，資料結構會包含資料本身以及運算方法，而這些要怎麼實作是各個程式語言處理，跟資料結構無關。例如JS並沒有node-tree，但只要知道定義，就能實作

String/Array/Object

String

基於index組成的文字，可以根據index得到特定的字

方法：length、substr、indexof…

Array

基於index組成的資料結構，可以根據index得到特定資料

String與array差別：

1. String 為inmutable，反之array是mutable, call by reference
2. Array 存放於一個連續記憶體空間bigO(n)
3. String 一個變數表面上是bigO(1)實際上是bigO(n)

Object

1. 基於key與value組成的資料結構，沒有順序
2. 複製Object跟Array：slice、JSON轉換、Object.assign、展開運算子
3. Object等同於hash map?實作上不同，但本質相同，hash map的key並非如object限定為字串

Q344. Reverse String (E)

1. in-place：不改動原本資料的方法
2. O(1) extra memory 固定的記憶體空間，不因數量上升而增加記憶體空間

變數交換

練習題：

1160. Find Words That Can Be Formed by Characters

連結

題目說明：

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

給予字串陣列words與字串chars，若words內元素可以被chars的字母組成，就是good字串，回傳所有good字串的長度

條件：

• 1 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• words[i] and chars consist of lowercase English letters.

解法：

1. 用hash map紀錄所有可用的字母
2. 檢查每個單字，跟map比較
3. 當單字有沒有列在chars裡面的字，或有超過chars的字母數量，直接略過
4. 當符合條件時，記下該單字長度

442. Find All Duplicates in an Array

link

題目說明：

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

給予一整數數字陣列nums，元素長度n，數字值在1~n之間，每個數字最多出現兩次，回傳一整數數字陣列，該數字為出現兩次的數字

條件：

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n
• Each element in nums appears once or twice.
• 演算法時間要O(n)，空間則是O(1)

解法：

287. Find the Duplicate Number

link

題目說明：

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

給予一整數數字陣列nums，元素長度n+1，數字值在1~n之間，在這些數字中只有一個數字會重複一次，請返回該重複數字

條件：

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.
• 空間則是O(1)，不能修改nums陣列

優化：

• How can we prove that at least one duplicate number must exist in nums?
• Can you solve the problem in linear runtime complexity?

解法：