Datawhale | 編程第6期 Test 2

數(shù)組

1. 實(shí)現(xiàn)一個(gè)支持動(dòng)態(tài)擴(kuò)容的數(shù)組

class MyArray {
  constructor(capacity = 10) {
    this.data = new Array(capacity);
    this.size = 0;
  }

  // 獲取數(shù)組中的元素實(shí)際個(gè)數(shù)
  getSize() {
    return this.size;
  }

  // 數(shù)組的容量
  getCapacity() {
    return this.data.length;
  }

  // 是否為空
  isEmpty() {
    return this.size === 0;
  }

  resize(size) {
    let newArray = new Array(size);

    for (let i = 0; i < this.size; i++) {
      newArray[i] = this.data[i];
    }

    this.data = newArray;
  }

  insert(index, element) {
    // 判斷數(shù)組是否滿了
    if (this.size == this.getCapacity) {
      this.resize(this.size * 2);
    }

    // 判斷索引是否符合要求
    if (index < 0 || index > this.size) {
      throw new Error('insert error! require index < 0 || index > size');
    }

    // 從索引出開始所有元素后移一位
    for (let i = this.size - 1; i < index; i--) {
      this.data[i + 1] = this.data[i];
    }

    // 指定索引處，插入元素
    this.data[index] = element;

    // 維護(hù)size
    this.size++;
  }

  push(element) {
    // this.data[this.size++] = data;
    this.insert(this.size, element);
  }

  unshift(element) {
    this.insert(0, element);
  }

  // 添加元素，相當(dāng)于在數(shù)組最后面插入一個(gè)元素
  add(element) {
    if (this.size == this.getCapacity) {
      throw new Error('add error! Array is full');
    }

    this.data[this.size++] = element;
  }

  get(index) {
    if (index < 0 || index >= this.size) {
      throw new Error('get error. index < 0 || index >= this.size');
    }

    return this.data[index];
  }

  set(index, element) {
    if (index < 0 || index >= this.size) {
      throw new Error('set error. index < 0 || index >= this.size');
    }

    this.data[index] = element;
  }

  // 包含
  // 若元素存在，返回 true;否則，返回 false
  contain(element) {
    for (let i = 0; i < this.size; i++) {
      if (this.data[i] === element) {
        return true;
      }
    }

    return false;
  }

  // 搜索功能
  // return 元素的索引
  find(element) {
    for (let i = 0; i < this.size; i++) {
      if (this.data[i] === element) {
        return i;
      }
    }

    return -1;
  }

  // 搜索全部 element
  // 返回等價(jià)于 element元素的所有索引
  findAll(element) {
    let indexArray = new MyArray(this.size);

    for (let i = 0; i < this.size; i++) {
      if (this.data[i] === element) {
        indexArray.push(i);
      }
    }

    return indexArray;
  }

  // 刪除指定索引元素
  remove(index) {
    if (index < 0 || index >= this.size) {
      throw new Error('remove error, index < 0 || index >= this.size')
    }

    let element = this.data[index];

    // 索引后面的元素往前移一位
    for (let i = index; i < this.size - 1; i++) {
      this.data[i] = this.data[i + 1];
    }

    this.data[this.size - 1] = undefined;
    this.size--;

    // Resize
    // 若 size 為容量一半，則進(jìn)行縮容
    if (Math.floor(this.getCapacity() / 2) === this.size
      && this.size !== 0
    ) {
      this.resize(Math.floor(this.getCapacity() / 2));
    }

    return element;
  }

  shift() {
    return this.remove(0);
  }

  pop() {
    return this.remove(this.size - 1);
  }

  removeElement() {

  }

  removeAllElement() {

  }
}

2. 實(shí)現(xiàn)一個(gè)大小固定的有序數(shù)組，支持動(dòng)態(tài)增刪改操作

class MyArray {
  constructor(capacity = 10) {
    this.data = new Array(capacity);
    this.size = 0;
  }

  // 查
  find(index) {
    if (index < 0 || index >= this.size) {
      throw new Error('find error. index < 0 || index >= this.size');
    }

    return this.data[index];
  }

  // 插入
  insert(index, element) {
    if(this.size == this.data.length) {
      this.resize(this.size * 2);
    }

    if (index < 0 || index > this.size) {
      throw new Error('insert error!');
    }

    // 從索引位后往后移一位
    for (let i = index; i < this.size; i++) {
      this.data[i + 1] = this.data[i];
    }

    this.data[index] = element;

    this.size++;
  }

  // 添加
  add(element) {
    this.insert(this.size, element);
  }

  // 刪除
  remove(index) {
    if (index < 0 || index >= this.size) {
      throw new Error('remove error');
    }

    let element = this.data[index];

    for (let i = index; i < array.length; i++) {
      this.data[i] = this.data[i + 1];
    }

    this.data[this.size - 1] = undefined;
    this.size--;

    if (Math.floor(this.getCapacity() / 2) === this.size
      && this.size !== 0
    ) {
      this.resize(Math.floor(this.getCapacity() / 2));
    }
    
    return element;
  }

  // 動(dòng)態(tài)擴(kuò)容
  resize(capacity) {
    const newArray = new Array(capacity);

    for (let i = 0; i < this.size; i++) {
      newArray[i] = this.data[i];
    }

    this.data = newArray;
  }
}

3. 實(shí)現(xiàn)兩個(gè)有序數(shù)組合并為一個(gè)有序數(shù)組

const merge = (array1, m, array2, n) => {
  // 交換數(shù)組位置和大小
  // 始終保證 n > m
  if (m > n) {
    const temp = array1;
    const temp_size = m;
    m = n;
    n = temp_size;

    array1 = array2;
    array2 = temp;
  }

  let num = m + n - 1;
  --m;
  --n;

  while (m >= 0 && n >= 0) {
    if (array2[n] > array1[m]) {
      array1[num--] = array2[n--];
    } else {
      array1[num--] = array1[m--];
    }
  }

  // 將剩余元素加入到 array1 中
  while(n >= 0) {
    array1[num--] = array2[n--];
  }

  return array1;
};

// TEST
// [ 1, 7, 10, 20, 39, 45, 46, 49, 80 ]
console.log(merge([1,20,39,46], 4, [7,10, 45, 49,80], 5))

字符串

1. 實(shí)現(xiàn)一個(gè)字符集，只包含 a～z 這 26 個(gè)英文字母的 Trie 樹

class TrieNode {
    constructor(data){
        this.data = data;
        this.children = new Array(26);
        this.isEndingChar = false
    }
}

class TrieTree {

    constructor(data){
        this.root = new TrieNode('/')
    }

    insert (text) {
        let node = this.root;
        for (let char of text) {
            let index = char.charCodeAt() - 'a'.charCodeAt();
            if(!node.children[index]) {
                node.children[index] = new TrieNode(char);
            }
            node = node.children[index];
        }

        node.isEndingChar = true;
    }

    find (text) {
        let node = this.root;

        for(let char of text) {
            let index = char.charCodeAt() - 'a'.charCodeAt();
            if(node.children[index]) {
                node = node.children[index];
            } else {
                return false;
            }
        }

        return node.isEndingChar;
    }
}

2. 實(shí)現(xiàn)樸素的字符串匹配算法

參考資料

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 第5章 引用類型(返回首頁) 本章內(nèi)容 使用對(duì)象 創(chuàng)建并操作數(shù)組 理解基本的JavaScript類型 使用基本類型...
    大學(xué)一百閱讀 3,667評(píng)論 0贊 4
  • 概要 64學(xué)時(shí) 3.5學(xué)分 章節(jié)安排 電子商務(wù)網(wǎng)站概況 HTML5+CSS3 JavaScript Node 電子...
    阿啊阿吖丁閱讀 9,793評(píng)論 0贊 3
  • ??引用類型的值（對(duì)象）是引用類型的一個(gè)實(shí)例。 ??在 ECMAscript 中，引用類型是一種數(shù)據(jù)結(jié)構(gòu)，用于將數(shù)...
    霜天曉閱讀 1,213評(píng)論 0贊 1
  • 1、用C語言實(shí)現(xiàn)一個(gè)revert函數(shù)，它的功能是將輸入的字符串在原串上倒序后返回。 2、用C語言實(shí)現(xiàn)函數(shù)void ...
    希崽家的小哲閱讀 6,675評(píng)論 0贊 12
  • 什么是“Trie樹”? Trie樹，又稱前綴樹或字典樹，是一種有序樹，用于保存關(guān)聯(lián)數(shù)組，其中的鍵通常是字符串。與二...
    尼桑麻閱讀 912評(píng)論 0贊 2

友情鏈接更多精彩內(nèi)容