[筆記] Master The Coding Interview – 3

Posted on2020-09-202020-09-15AuthorANDY LIEN

章節連結

課程相關資訊
內容

背景知識

範例程式碼
相關文章

這篇是 Udemy 上的知名課程 – Master the Coding Interview 的部分進修心得。這篇對應的內容是「Data Structures: Array」關於陣列的簡介。

課程相關資訊

[連結]：https://www.udemy.com/course/master-the-coding-interview-data-structures-algorithms/

課程對應章節：62~66

請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。

內容

背景知識

1. Array 陣列，你可以想像成它是一個 List 列表，裡頭的資料依照 Index 有序排列
2. 如果你的需求是要一個個從頭到尾遍歷找東西，那麼這個結構是熱門選項
3. 若對陣列使用 lookup, push 的作法，其時間複雜度為 O(1)
4. 若對陣列使用 insert, delete 的作法，其時間複雜度為 O(n)
5. Dynamic Arrays：跟上述的陣列相比，其長度一開始就是由內部的元素數量設定好的，缺乏彈性。而動態陣列可以根據外部傳入的變數來調整陣列長度，減少多餘的記憶體浪費

範例程式碼

// 建造一個 Dynamic Array，在 ES6 以後，其實沒有想像中難
Array.from({length: 10}) // [undefined, undefined, undefined ......*8]

// 自己建造一個靜態 array
class MyArray {
  constructor(){
     this.length = 0;
     this.data = {};
  }
  get(index){
     return this.data[index];
  }
  push(item){
     this.data[this.length] = item;
     this.length++
     return this.data
  }
  pop(){ // 回傳最後一個元素，並將其從原本的陣列中移除
    const lastItem = this.data[this.length-1];
    delete this.data[this.length-1];
    this.length--;
    return lastItem
  },
  shiftItems(index){
    for (let i = index; i < this.length - 1; i++) {
      this.data[i] = this.data[i + 1];
    }
    delete this.data[this.length-1];
    this.length--
  }
  deleteAtIndex(index){
    // 此方法為 shiftItems 的特別版，會回傳被刪掉的值，且改變陣列長度
    const target = this.data[index];
    this.shiftItems(index);
    return item
  }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

// 建造一個 Dynamic Array，在 ES6 以後，其實沒有想像中難

Array.from({length: 10}) // [undefined, undefined, undefined ......*8]

// 自己建造一個靜態 array

class MyArray {

constructor(){

this.length = 0;

this.data = {};

}

get(index){

return this.data[index];

}

push(item){

this.data[this.length] = item;

this.length++

return this.data

}

pop(){ // 回傳最後一個元素，並將其從原本的陣列中移除

const lastItem = this.data[this.length-1];

delete this.data[this.length-1];

this.length--;

return lastItem

},

shiftItems(index){

for (let i = index; i < this.length - 1; i++) {

this.data[i] = this.data[i + 1];

}

delete this.data[this.length-1];

this.length--

}

deleteAtIndex(index){

// 此方法為 shiftItems 的特別版，會回傳被刪掉的值，且改變陣列長度

const target = this.data[index];

this.shiftItems(index);

return item

}

}

相關文章

★全文分享★ [筆記] Master The Coding Interview – 16

[筆記] Master The Coding Interview – 16

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 15

[筆記] Master The Coding Interview – 15

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 14

[筆記] Master The Coding Interview – 14

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 13

[筆記] Master The Coding Interview – 13

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 12

[筆記] Master The Coding Interview – 12

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 11

[筆記] Master The Coding Interview – 11

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 10

[筆記] Master The Coding Interview – 10

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 9

[筆記] Master The Coding Interview – 9

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 8

[筆記] Master The Coding Interview – 8

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 7

[筆記] Master The Coding Interview – 7

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 6

[筆記] Master The Coding Interview – 6

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 5

[筆記] Master The Coding Interview – 5

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 4

[筆記] Master The Coding Interview – 4

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 2

[筆記] Master The Coding Interview – 2

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 1

[筆記] Master The Coding Interview – 1

工程師的面試中，不免俗的會遇見用各種

按讚加入粉絲團

延伸閱讀

Blogimove部落格搬家技術服務