📝 今日作った

プログラマの質問に対する回答-開始パスワード/整数降順に並べ替え/奇妙な文字の作成/最大公約数と最小公倍数

バイナリツリー/検索、挿入、削除/並べ替えの配列VSバイナリツリー

📖 学習資料

書『誰もが資料構造とアルゴリズムを持っている』

📚 学識

1.プログラマーの回答

1)レベル1の問題

(1) シーザーのパスワード

🔎 私の答え

function solution(s, n) {
  const lower = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'];
  const upper = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];

  const newArr = s.split('').map(item => {
    // 공백
    if (item === ' ') {
      return ' ';
    }
    
    if (lower.includes(item)) { // 소문자
      const stringIndex = lower.indexOf(item) + n
      if (stringIndex <= 25) {
        return lower[stringIndex];
      } else {
        const newIndex = stringIndex % 25 - 1;
        return lower[newIndex];
      }
    } else { // 대문자
      const stringIndex = upper.indexOf(item) + n
      if (stringIndex <= 25) {
        return upper[stringIndex];
      } else {
        const newIndex = stringIndex % 25 - 1;
        return upper[newIndex];
      }
    }
  });

  return newArr.join('');
}

🔎 他人の解答

私と同じ流れで解けて、ずっと短くなりました.条件3項演算子を用いてtextarr変数が上か下かを判断し,配列を割り当て,コードを一度に記述する.

問題を見てmap()を思い出し、文字列を配列に変更し、配列に変更する必要は全くありません.

function solution(s, n) {
  var upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  var lower = "abcdefghijklmnopqrstuvwxyz";
  var answer= '';

  for(var i =0; i <s.length; i++){
    var text = s[i];
    
    if(text == ' ') {
      answer += ' '; 
      continue;
    }
    
    var textArr = upper.includes(text) ? upper : lower;
    var index = textArr.indexOf(text) + n;
    if(index >= textArr.length) {
      index -= textArr.length;
    }

    answer += textArr[index];
  }
  
  return answer;
}

🔎 他人の解答2

nが1~25の点を用いて解く.1回に2回小文字と大文字を書きます.(2回目に書いたとき、最後のzは書かなかった)

function solution(s, n) {
  const chars = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY                          "
  return s.split('').map(e => chars[chars.indexOf(e)+n]).join('');
}

（2）整数降順で配置

🔎 私の答え

構文入力の代わりに+文字列を使用することもできます.文字列に+/-記号がある場合、文字列は数値になります.

function solution(n) {
  const string = (n + '').split('').sort((a, b) => b - a).join('');
  return parseInt(string);
  // return +string;
}

(3)制作奇妙的文字

🔎 私の答え
まず、split()を使用して、所与の文字列を配列に変換します.次に、map()を使用して配列内の各要素をサブ配列に再変換し、map()を使用してサブ配列内の各要素を条件に合致する要素に変換します.最後に、join()を使用してサブ配列を文字列に変更し、再びjoin()を使用して親配列を文字列に変更します.

function solution(s) {
  return s.split(' ').map(s => s.split('').map((s, i) => i % 2 === 0 ? s.toUpperCase() : s.toLowerCase()).join('')).join(' ');
}

（4）最大公倍数と最小公倍数

🔎 私の答え

function solution(n, m) {
  const limit = n < m ? m : n;
  const common_factor = [];

  for (let i = 1; i <= limit; i++) {
    if (n % i === 0 && m % i === 0) {
      common_factor.push(i);
    }
  }

  const gcf = Math.max(...common_factor);
  const lcm = gcf * (n / gcf) * (m / gcf);

  return [gcf, lcm];
}

第12章。バイナリツリーを使用して速度を上げる

📌 ソート配列:検索が速い(バイナリ検索)/挿入が遅い、削除が遅い
📌 ハッシュ・テーブル:検索、挿入、削除の高速/秩序性を維持できません.
📌 バイナリツリー:検索、挿入、削除の高速/秩序性を維持

1）バイナリツリー

(1)説明

🔎 ツリー(Tree)

ツリーは接続リストと同じ노드 기반 자료 구조です.

接続リストには、各ノードには別のノードへのリンクのみが含まれます.
ツリー内の各ノードは여러 노드로의 링크を含む.

一番上のノードをルートと呼びます.

親ノードには子ノードがあります.

ツリーには「レベル」があります.

🔎 이진 트리(Binary Tree)

各ノードのサブノードは0～2個です.

1つのノードに2つのサブノードがある場合、1つのノードは親ノードより小さい値を有し、もう1つのノードは親ノードより大きい値を有しなければならない.

(2)コード実装

p.241
Python実装のコードに変換→JavaScript

class TreeNode {
  constructor(data, left_child = null, right_child = null) {
    this.data = data;
    this.left_child = left_child;
    this.right_child = right_child;
  }
}

// 왼쪽 노드와 오른쪽 노드를 만들고
const node_1 = new TreeNode(1);
const node_2 = new TreeNode(10);

// 이를 이용해 루트(가장 상위 노드)를 만든다
const root = new TreeNode(5, node_1, node_2);

console.log(root);
// TreeNode {data: 5, left_child: TreeNode, right_child: TreeNode}

(3)バイナリツリーの演算

ツリー検索は、루트から開始する必要があります.

pp.242 ~ 257
Python実装のコードに変換→JavaScript

class TreeNode {
  constructor(value, left_child = null, right_child = null) {
    this.value = value;
    this.left_child = left_child;
    this.right_child = right_child;
  }
}

// 트리 노드 생성
const node_1 = new TreeNode(1);
const node_2 = new TreeNode(10);
const root = new TreeNode(5, node_1, node_2);
console.log(root); // TreeNode {value: 5, left_child: TreeNode, right_child: TreeNode}



// 검색 ❗ (찾는 값이 어떤 노드에 있는지를 검색)
function search(value, node) {
  if (node === null || node.value === value) {
    return node;
  } else if (node.value < value) {
    return search(value, node.right_child);
  } else {
    return search(value, node.left_child);
  }
}

const search8 = search(8, root); // 트리 검색은 반드시 '루트'부터 시작해야 함
console.log(search8); // null



// 삽입 ❗
function insert(value, node) {
  if (node.value < value) { // 대소 비교
    if (node.right_child === null) { // 더 이상 자식 노드가 없으면
      node.right_child = new TreeNode(value); // 그 위치에 새 노드 추가
    } else {
      insert(value, node.right_child); // 자식 노득가 있으면 다시 대소 비교
    }
  } else if (node.value > value) { // 대소 비교
    if (node.left_child === null) { // 더 이상 자식 노드가 없으면
      node.left_child = new TreeNode(value); // 그 위치에 새 노드 추가
    } else {
      insert(value, node.left_child); // 자식 노득가 있으면 다시 대소 비교
    }
  }
}

const insert13 = insert(13, root);
console.log(root); // 값이 10인 노드의 오른쪽 자식 노드에 값이 13인 노드가 추가됨



// 🔥 '왜' 재귀 함수를 사용해서 구현하는가? 어떻게 이진 트리의 의미를 안 후에 재귀 함수를 사용해서 구현해야 겠다고 생각할 수 있는 걸까.
// 🔥 테스트 케이스를 추가해 호출 스택을 그림으로 그려서 차근차근 따라가면 이해가 되는 것도 같은데 코드만 보면 막막하다. 결국 이해 안된다는 뜻.
// 삭제 ❗
function remove(valueToRemove, node) {
  // 기저 조건
  if (node === null) {
    return null;
  } else if (valueToRemove < node.value) {
    node.left_child = remove(valueToRemove, node.left_child);
  } else if (valueToRemove > node.value) {
    node.right_child = remove(valueToRemove, node.right_child);
  } else { // 현재 노드가 삭제하려는 노드인 경우
    if (node.left_child === null) {
      return node.right_child;
    } else if (node.right_child === null) {
      return node.left_child;
    } else { // 현재 노드에 자식 노드가 둘이면
      node.right_child = lift(node.right_child, node);
      return node;
    }
  }
}

function lift(node, nodeToRemove) {
  if (node.left_child) {
    node.left_child = lift(node.left_child, nodeToRemove);
    return node;
  } else {
    nodeToRemove.value = node.value;
    return node.right_child;
  }
}

const remove5 = remove(10, root);
console.log(root); // 값이 10인 노드가 삭제되고, 값이 13인 노드가 그 자리에 위치하게 됨

🙋‍♀️ Q1. 上記のコードのバイナリツリーの「削除」部分は理解できません.

(4)ビオ

検索
ステップを実行するたびに、サイズ比較によって値の半分を含むスペースを削除します.
したがって、이진 트리 검색의 효율성はO(logN)である.
+)はソート後の配列探索(バイナリ探索)の効率因子O(logn)と同じである.

挿入
まず、新しいノードが入る正しい位置を見つけなければなりません.
ステップを実行するたびにサイズ比較を行います.
このとき,ソート後のデータをツリーに挿入すると,バランスのとれたツリーになり,効率が悪くなる可能性が高い.→最悪案O(N)
1から5(右側のノードのみ)を順番に挿入するツリーでは、5を検索するには、O(N)という5つのステップが必要です.
逆に、무작위に並べられたデータをツリーに挿入すると、通常はバランスのとれたツリーとなり、効率が高い.→平均シナリオO(logn)
ex)3,2,4,1,5を順番に挿入したツリーで5を検索するには3つのステップしか必要ありません.
子供がいなくなるまで、サイズの比較を続けます.
サブノードがないノード、すなわち正しい位置が見つかった場合は、第1のフェーズで挿入します.(ビクオ無視定数)
したがって、平均では이진 트리 삽입의 효율성はO(logN)である.
+)はソート挿入の効率因子O(N)と比較して非常に良好であった.
💡 ソートされた配列をバイナリツリーに変換する場合は、まずデータの順序を무작위に設定することが望ましい.

削除
削除するノードには없으면のサブノードがあり、直接削除します.
削除するノード上でサブノード하나면を削除し、ノードを削除し、サブノードを削除ノードの位置に配置する.
削除するノードには둘이면のサブノードがあり、削除したノードを後続のサブノードに置き換えます.
後続ノードは、削除ノードよりも高い値を持つサブノードです.
ただし、後続ノードに右側のサブノードがある場合は、後続ノードを削除ノードの位置に配置し、後続ノードの右側のサブノードを後続ノードの元の親ノードの左側のサブノードとします.이진 트리 삭제의 효율성はO(logN)です.
+)はソート削除の効率因子O(N)と比較して非常に良い.

（5）効率比較

-シナリオVS接続リスト

計算スキーム接続リストO(1)O(N)探索O(N)挿入O(N)の読み出し

-整列配列VSバイナリツリー

計算ソート配列バイナリツリーO(1)O(N)探索O(logn)O(logn)挿入O(N)O(logn)(ソートデータ挿入時にO(N)O(N)O(logn)O(logn)O(logn)を削除)

(6)バイナリツリーの巡回

資料構造巡回とは、자료 구조에서 모든 노드를 방문を行うプロセスを指す.
ツリー遍歴の効率はO(N)である.
[例]
ブック名リストを管理するアプリケーションを作成します.
以下の機能を実現すべき

プログラムは、書名

をアルファベット順に出力できる必要がある.

プログラムは、リスト

を変更し続けることができる必要がある.

ユーザは、リストから書名

を検索できる必要がある.
→リストが頻繁に変更されない場合は、ソートされた配列(挿入、削除が頻繁ではなく、検索速度が速い)を使用することをお勧めします.
→ただし、リストが随時変更される場合は、이진 트리(挿入、削除が頻繁に発生)を使用します.
→2番と3番の機能は,先に学習したバイナリツリーの検索,挿入,削除コードで実現できる.
→1番機能を実現するためにはバイナリツリーのすべてのノードにアクセスする必要がある.この場合,中位順を利用した.
pp.259
Python実装のコードに変換→JavaScript
🙋‍♀️ Q2. コードは簡単ですが、これも理解できません.また、李金樹めぐりでは、この本は中尉巡りに関連している.まずバイナリツリーの削除コードを知ってから、バイナリツリーの巡りもさらに勉強します!

// 중위 순회 ❗ (왼쪽 )
function traverse_and_print(node) {
  if (node === null) {
    return;
  }
  traverse_and_print(node.left_child);
  console.log(node.value);
  traverse_and_print(node.right_child);
}

🙋‍♀️ n.問題

ここです。ショートカット(バイナリツリーを削除)

ここです。ショートカット(バイナリツリー中尉巡り)

明日作った

プログラマ

読み続ける