データ構造を再認識する

1. 概念#

データ構造とアルゴリズムは、コンピュータサイエンスの重要な基礎知識です。
データ構造とは、相互に特定の関係を持つデータ要素の集合を指します。これはデータの保存、組織、管理に関わります。一般的なデータ構造には、配列、リンクリスト、スタック、キュー、木、グラフなどがあります。
アルゴリズムは、特定のタスクを完了するための手順または命令のシーケンスです。これは本質的にデータ操作の説明です。アルゴリズムは主に入力、出力、および入力を出力に変換する手順を含みます。
データ構造とアルゴリズムの間には密接な関係があります。アルゴリズムの設計は選択されたデータ構造に依存し、異なるデータ構造は異なるアルゴリズムに適しています。また、データ構造の組織方法はアルゴリズムの効率に直接影響します。
データ構造とアルゴリズムを習得することは、高品質なプログラムを開発する上で非常に重要です。これらは開発者の技術能力を評価する重要な基準です。データ構造とアルゴリズムの知識は、面接でも一般的な試験ポイントです。多くのプログラミング言語は、さまざまなデータ構造とアルゴリズムを実装し、使用する必要があります。
したがって、データ構造とアルゴリズムはすべてのプログラマーにとって必須の基礎知識であり、真に習得するには多くの学習、練習、使用が必要です。これらは開発者が重点的に向上させるべきコア競争力の一つです。

データ構造構成#

スタック構造
キュー
配列
リンクリスト
木
グラフ
ヒープ構造

1.1 スタック構造の実装#

実装方法：配列ベースとリンクリストベース。ts/js にはリンクリストが存在しないため、再実装が必要です。

interface IStack<T>{
  push():void;
  pop():void;
  size():number
  peek():T
  isEmpty():bollean
}

class Stack<T=any> immplements IStack{
  private arr:T[]=[]
  push(element:T):void{
     this.arr.push(element)
  }
  pop():void{
     this.arr.pop()
  }
  size():number{
    return this.arr.length();
  }
  peek():T|undefined{
    return this.arr.pop()
  }
  isEmpty():bollean{
    return this.arr.length===0?true:false
  }
}

面接問題 1. 10 進数を 2 進数に変換する関数を実装する#

function toBinary(count:number):string{
  let stack =new Stack()
  let binary=""
  while(count>0){
    stack.push(count%2)   
    count= Math.floor((count/2))
  }
  while(!stack.isEmpty()){
    binary+=stack.pop()
  }
  return binary;
}

面接問題 2. 文字 “（”，“{”，“[” と "}","]",#

")" の対称性を実装する
例えば： valid ("(){}[]") true
valid("({[]})") true
valid("{()]}") false

function valid(str:string):boolean{
  const stack=new Stack()
  for(let i=0;i<str.length;i++){
    switch(str[i]){
      case "(":
        stack.push(")")
        break;
      case "{":
        stack.push("}")
        break;
      case "[";
        stack.push("]")
        break;
      default:
         if(str[i]!==stack.pop()) return false
        
    }
  }
  return stack.isEmpty()
}

ドラムを叩いて花を渡す#

一群の人が円を囲み、数え始め、停止したとき、その人が淘汰され、最後の勝者の初期位置を得る。

思考：キューに従って順次出栈し、呼ばれた人でなければ再度スタックに入れる。#

function findLast(arr:string[],loop:number){
  if (arr.length === 0) return -1;
  const queue=new Queue()
  for(let i=0;i<arr.length;i++){
     queue.enqueue(arr[i])
  }
  while(queue.size()>1){
  for(let i=1;i<loop;i++){
    const name=queue.dequeue()
    queue.enqueue(name)
  }
  queue.dequeue()
  }
  return queue.dequeue()
}

リンクリスト構造#

概念：配列と同様に線形構造であり、一連の要素を保存するために使用できますが、リストと配列の実装メカニズムは完全に異なります。配列またはリンクリストを使用するシナリオは、アプリケーションシナリオの操作に依存します。

配列：空間内に固定サイズの連続スペースを割り当ててデータを保存しますが、配列の前、中に要素を挿入する場合、すべての後続の要素は対応するメモリアドレスを後ろに移動する必要があります。配列の要素が特に多い場合、オーバーヘッドは非常に大きくなります。

リンクリスト：リンクリストは、作成時にサイズを決定する必要がなく、head ポインタがリンクリスト内の next 要素を指します。head=>next=>next2=>next3=>next4
大量の削除、挿入操作が関与する場合、next のポインタの指向を変更するだけで済み、時間計算量は O (1) ですが、その欠点は明らかです。配列はインデックスを通じてアドレス指定できますが、リンクリストは先頭から進む必要があります。

リンクリストの実装#

class Node<T=any>{
  value:T;
  next:Node<T>|null
  constructor(value:T){
    this.value=value
  }
}
class LinkList<T>{
  head:T|null=null;
  size:number=0;
  get length():number{
    return this.size
  }
  add(element):void{
    const newNode=new Node<T>(element)
    if(!this.head){
      this.head=newNode
    }else{
      let current=this.head
      while(current.next){
        current=current.next
      }
      current.next=newNode
    }
    this.size++
  }
  traverse(){
   let values:T[]=[]
   let current=this.head
   while(current){
      values.push(current.value)
      current=current.next
   }
    console.log(values.join("->"))
  }
  insert(elememt:T,position:number):boolean{
    if(position<0||position>this.size) return false
    const value=new Node(element)
    if(position===0){
      value.next=this.head
      this.head=value
    }else{
      let prev:Node<T>|null=null
      let current=this.head
      let index=0
      while(index++<position){
        prev= current;
        current=current.next
      }
      prev.next=value
      value.next=current
    }
    this.size++
    return true
  }
  //特定の位置のノードを削除する
  removeAt(position:number):T|null{
    if(position<0||position>=this.size)
      return null
    if(position===0){
      this.head=this.head.next
    }else{
      let prev:Node<T>|null=null
      let current =this.head
      let index=0
      while(index++<position){
        prev=current
        current=current.next
      }
      prev.next=current?.next ?? null
    }
    this.size--;
    return null;
  }
  //特定の位置のノードを取得する
  get(position:number):T|null{
     if(position>size||position<0) return null
    let current=this.head
    let index=0
    while(index++<position){
      current=current.next ?? null
    }
    return current.value??null
  }
  //特定のノードの要素を更新する
  update(element:T,position:number):boolean{
    if(position>=size||position<0) return false
    let current=this.head
    let index=0
    while(index++<position&&current){
       current=current.next
    }
    current.value=element
    return true;
  }
  //要素に基づいてインデックスを検索する
  indexOf(element:T){
    let current=this.head
    let index=0;
    while(current){
      if(current.value===element){
        return index;
      }
      current=current.next
      index++
    }
    return -1;
  }
   remove(element: T): T | null {
    const first = this.indexOf(element);
    //方法一：
    // if (first > 0) {
    //   let prev: Node<T> | null = null;
    //   let current = this.head;
    //   let index = 0;
    //   while (index++ < first && current) {
    //     prev = current;
    //     current = current.next;
    //   }
    //   prev!.next = current!.next ?? null;
    //   return true;
    // } else {
    //   return false;
    // }
    return this.removeAt(first);
  }
  isEmpty(): boolean {
    return this.size === 0 ? true : false;
  }
}

面接問題リンクリストを反転する（スタック構造実装）#

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}
function reverseList(head: ListNode | null): ListNode | null {
  if (head === null) return null;
  //ノードが1つだけの場合
  if (!head.next) return head;
  //スタック構造を使用
  let stack: ListNode[] = [];
  while (head) {
    stack.push(head);
    head = head.next;
  }
  const newhead: ListNode = stack.pop()!;
  let newheadCurrent = newhead;
  while (stack.length) {
    const node = stack.pop();
    newheadCurrent.next = node!;
    newheadCurrent = newheadCurrent!.next;
  }
  newheadCurrent.next = null; //最後の要素はnullを指す必要がある。前の要素を指すと循環参照になる。
  return newhead;
}
export {};

リンクリストを反転する（非再帰実装）#

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}
function reverseList(head: ListNode | null): ListNode | null {
 if(head===null ||!head.next) return head
 let newHead:ListNode|null=null
  while(head){
    
    let current:ListNode |null=head.next
    //最初のノードをnullを指すようにする
    head.next=newHead
    //後ろに進めて、順次繰り返す
    newHead=head
    head=current
  }
  return newHead;
}

リンクリストを反転する（再帰）#

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}
function reverseList(head: ListNode | null): ListNode | null {
  if(head===null || head.next===null) return head
  const newhead=reverseList(head.next??null)
  head.next.next=head
  head.next=null
  return newhead
}

ハッシュテーブル#

ハッシュテーブルは配列に基づいて実装されていますが、配列とは異なる多くの利点があります。

利点#

非常に迅速な検索、削除、挿入操作を提供します。
データの数に関わらず、挿入、削除の時間はほぼ定数 O (1) に近く、実際には数行の機械命令で済みます。
ハッシュテーブルの速度は木よりも速く、基本的に瞬時に目標要素を検索できます。
ハッシュテーブルは木構造よりも簡単に記述できます。

欠点#

ハッシュテーブルのデータ構造は無秩序であるため、要素を遍歴する固定の方法はありません。
通常、ハッシュテーブルのキーは重複できず、同じキーを持つ異なる要素を保存することはできません。

本質#

その構造は配列構造ですが、その神秘的な点は配列のインデックス値の変換にあります。この変換はハッシュ関数を使用して行い、ハッシュ関数を通じて hashCode を取得します。

例えば、50000 冊の書籍情報を保存する場合、配列：複雑度 o (n)、順次検索インデックス値、もちろん、二分探索を利用して複雑度を O (logn) に下げることができますが、ハッシュ関数を利用することで、各書籍の各項目を対応するインデックス値に取得できます。この関数のルールは私たち自身で制定できます。
例えば、各書籍に対応する保存文字列 "abc" を使用し、ascii コードに従ってルールを得ます。インデックス = 97+98+99,=== その配列のインデックス値。

明らかに、このような保存方法の重複率は非常に高いため、提案 b がこの問題を解決できます。累乗の連乗
例えば、“abc"=271^3+272^3......
しかし、こうすることで、唯一性は保持されますが、配列スペースを非常に浪費します。例えば、“zzzzzzzzzzzzzzzzzzz” は天文学的な数字の保存スペースを割り当てる必要があり、これは科学的ではありません。

したがって、チェーンアドレス法とオープンアドレス法があります。

キーワード key にハッシュ関数を計算し、ハッシュアドレスを取得します。
そのハッシュアドレスを確認し、空であれば直接挿入します。
空でない場合、そのアドレスのリストに同じ key の要素が存在するか確認します。
存在する場合、内容を修正します。存在しない場合、そのリストの先頭に新しい要素を挿入します。
新しい要素を挿入する際には、ノードを作成し、新しいノードをリストの先頭に挿入する必要があります。
要素を検索する際には、リストを遍歴し、キーワードを逐一比較します。
チェーンアドレス法は衝突を解決しますが、検索効率は低く、リストを遍歴する必要があります。平均検索長は約 O (1+α)、α はリストの長さです。