[クイックキャンパスNekaraku杯第2期]-11日目勉強

今日からこの快速キャンパスの内カラクーカップの授業が始まり、初めてオンラインで集まって授業を受けました.午前10時に聖水の快速キャンパスに到着し、教室に入ってオフラインOTの訓練を受けた.
OTはオフラインカリキュラムに関するガイドラインを紹介し,署名した시프티アプリケーションのダウンロードと使用方法などのトレーニングを受けた.
OT研修を受けた後は、昼前1時まではプライベートな時間なので、ここで割り付けのアルゴリズムの問題を解決し、1時まで昼食をとり、2時から資料構造/アルゴリズムレッスンを行います.
次の文章は、今日受講した資料構造/アルゴリズムの授業の内容と私の説明方法、講師の説明方法です.問題の著作権ですので、整理してアップロードした部分は参考にしてください.
文字列とハッシュ
デジタル統合
質問する
0と1からなる文字列を指定した場合、連続する部分を0または1に置き換え、0または1のみからなる文字列を作成した場合、置き換えの最小回数は?
📌 私の解決方法

function solution(s) {
    let answer;
    let zeroToOne = 0;
    let OneTozero = 0;
    let cnt = 0;

    for(let i = 0; i < s.length; i++)
    {
        if(cnt > 0)
        {
            if(s[i] === '0') {

            } else {
                zeroToOne++;
                cnt = 0;
            }
        }
        else {
            if(s[i] === '0') {
                cnt++;
            }
        }
        if((i === s.length-1) && (s[i] === '0')) {
            zeroToOne++;
        }
    }
    cnt = 0;
    for(let i = 0; i < s.length; i++)
    {
        if(cnt > 0)
        {
            if(s[i] === '1') {

            } else {
                OneTozero++;
                cnt = 0;
            }
        }
        else {
            if(s[i] === '1') {
                cnt++;
            }
        }
        if(i === s.length-1 && s[i] === '1') {
            OneTozero++;
        }
    }
    answer = Math.min(zeroToOne, OneTozero);
    return answer;
}

console.log(solution("100001111"))

私は問題を解く時、1つの変数が0から1に変わることと1つの変数が1から0になることの合計2つの要素が連続しているかどうかをチェックすることで連続を区別し、ZeroToOneとOneToZeroの値を増やし、最小値を見つけて問題を解決します.しかし、コードが乱れているようです.
📌 先生のやり方.

function solution(s) {
    let answer;
    let zero = 0;
    let one = 0;
    if (s[0] === "1") one++;
    else zero++;
    for (let i = 1; i < s.length; i++) {
      if (s[i - 1] !== s[i]) {
        if (s[i] === "1") one++;
        else zero++;
      }
    }
    answer = Math.min(one, zero);
    return answer;
  }
  console.log(solution("10010111100"));

講師のコードを見ると,文字列の要素を初めて知ると,0はゼロ変数の値を増やし,1は1変数の値を増やして開始する.
次に、s[i-1]とs[i]を比較し、2つの要素が異なる場合、他の要素の変数値を増やします.
このように解くともっときれいになるようです.
じょうたいへんか
質問する
0と1からなる文字列を与えます.
1.0または1の位置を変更
2.0を1に変更するか、1を0に変更します.
初期状態が11000111の文字列が与えられ、ターゲット状態が111001101の文字列が与えられた場合、初期状態からターゲット状態に変換される最小回数はいくらですか?
📌 私の解決方法

function solution(s1, s2) {
    let answer = 0;
    let s1Arr = [];
    let s2Arr = [];
    let s1zeroCount = 0;
    let s2zeroCount = 0;
    let difference = 0;

    for (let i = 0; i < s1.length; i++)
    {
        if(s1[i] !== s2[i]) {
            s1Arr.push(s1[i]);
            s2Arr.push(s2[i]);
            if(s1[i] === '0') {
                s1zeroCount++;
            }
            if(s2[i] === '0') {
                s2zeroCount++;
            }
        }
    }

    difference = Math.abs(s1zeroCount - s2zeroCount);
    answer += difference;

    if(difference !== 0) {
        if(s1zeroCount < s2zeroCount) {
            let i = 0;
            while(difference !== 0) {
                if(s1[i] === '1') {
                    s1[i] = '0';
                    difference--;
                    i++;
                }
            }
        } else {
            let i =0;
            while(difference !== 0) {
                if(s2[i] === '1') {
                    s2[i] = '0';
                    difference--;
                    i++;
                }
            }
        }
        for (let i = 0; i < s1Arr.length; i++)
        {
            if(s1[i] === s2[i]) {
                s1Arr.splice(i, 1);
                s2Arr.splice(i, 1);
            }
        }
    }

    answer += s1Arr.length / 2;

    return answer;
}
console.log(solution("11000111", "11100110"));

解答する時たくさん考えましたまず、問題をより容易に見せるために、s 1とs 2の同じインデックスの同じ要素を除外し、別の要素を別の配列に配置します.
その後、s 1とs 2の0と1の個数は、文字列を所望の形式にするために同じでなければならないので、0と1の個数を一致させるためには、カウントは文字列の中で任意に0から1または1から0に変化しなければならないので、答えに加算しなければならない.
最後に、[1,0],[0,1]のように位置が異なる場合には、大まかに計算すると、配列長が2の倍数であれば、1個ずつ増加する、すなわち配列長が2の場合には、1番の位置を移動する必要があり、3人が1,4の場合には、2,5の場合には、2,6の場合には、このようにs 1 Arrが増加する.length/2、答えに加えます.
📌 先生のやり方.

function solution(s1, s2) {
  let zero = 0, one = 0;
  for (let i = 0; i < s1.length; i++) {
      if(s1[i] !== s2[i]) {
          if(s1[i] === '0') zero++;
          else one++;
      }
  }

  return Math.abs(zero - one) + Math.min(zero, one);
}

2人は違う個数(zero,one)まで数えて、減算した値を加えて、他の要素のように最小位置を変えるので、Math.1分足す
これはもっと簡単な方法のようです.
コア解答-->他のものを数えてから交換するMath.minを追加(0,1)
接尾辞の位置合わせ
与えられた文字列sの場合、s文字列のすべての接尾辞が求められ、辞書順に出力される.
📌 私の解決方法

function solution(s) {
    let answer = [];
    let sArr = s.split("");

    for (let i = 0 ; i<s.length; i++)
    {
        answer.push(sArr.join(""));
        sArr.splice(0, 1);
    }
    return answer.sort();
}

console.log(solution("kseaedu"));

まず受信した文字列を並べ、その値を応答配列にプッシュし、前に要素を切り取り、もう一度プッシュして応答配列を形成します.
次に、答え配列をソートして出力します.
📌 先生のやり方.

function solution(s) {
    let answer = [];
    for(let i = 0; i<s.length; i++)
    {
      answer.push(s.substring(i,s.length))
    }
    return answer.sort();
  }
  
console.log(solution("kseaedu"));

substring関数を使用して文字列を答え配列に入れ、同様にsort!
共通文字のない単語
N文字列がある場合は、共通文字のない2つの文字列を選択し、2つの文字列の長さを乗算したときに最大値を出力します.
📌 私の解決方法

function solution(arr)
{
    let answer = 0;
    let currentValue;
    let compareArr;
    let compareLength;
    let compareValue = 0;

    for (let i = 0; i<arr.length; i++)
    {
        currentValue = arr[i].split("");
        for(let j = i+1; j<arr.length; j++)
        {
            compareArr = arr[j].split("");
            compareLength = currentValue.filter(x => compareArr.includes(x));
            if(compareLength.length === 0)
            {
                compareValue = currentValue.length * compareArr.length;
            }
            answer = Math.max(answer, compareValue);
        }
    }
    return answer;
}

const arr = ["kk", "k", "kkk", "kkkkk", "kkkk"];

console.log(solution(arr));

filterとincludeを使用して共通の要素があるかどうかを検索し、compareLengthに共通の要素がある場合は入れ、ない場合はこの2つの配列を乗算する方法で最大値を見つけ、比較して答えに入れて解く.
📌 先生のやり方.

function isUnique(short, long) {
    for (let x of short) {
        if (long.indexOf(x) !== -1) {
            return false;
        } else {
            return true;
        }
    }
}

function solution(words) {
    let answer = 0;
    let len = words.length;
    words.sort((a, b) => a.length - b.length);

    for (let i = 0; i < len - 1; i++) {
        for (let j = i + 1; j < len; j++) {
            if (isUnique(words[i], words[j])) {
                let tmp = words[i].length * words[j].length;
                answer = Math.max(answer, tmp);
            }
        }
    }

    console.log(words);

    return answer;
}

const arr = ["skudy", "kstue", "time", "back", "good"];

console.log(solution(arr));

isUniqueという関数を作成し、配列内の要素が別の配列にあるかどうかを確認します.ない場合はtrueを返して最大値を検索して解析します.
回文文字列2
与えられた文字列sの場合、sは最大1文字消去可能であり、回文文字列になった場合は「YES」を出力し、そうでなければ「NO」を出力する
📌 私の解決方法

function solution(s)
{
    let answer;
    let leftValue;
    let rightValue;
    let compareValue = 0;
    let sArr = s.split("");
    let arrLength;
    
    for (let i = 0; i < parseInt(s.length / 2, 10); i++)
    {
        leftValue = sArr.shift();
        rightValue = sArr.pop();

        if(leftValue === rightValue) {
            answer = "YES";
            continue;
        } else {
            answer = "NO";
            break;
        }
    }
    if (answer == "YES") {
        return answer;
    }

    for (let i = 0; i < s.length; i++)
    {
        sArr = s.split("");
        arrLength = sArr.length;
        sArr.splice(i, 1);
        for(let j = 0; j<parseInt((arrLength-1) /2, 10); j++) {
            leftValue = sArr.shift();
            rightValue = sArr.pop();

            if(leftValue === rightValue) {
                compareValue++;
                if(sArr.length === 1) {
                    compareValue++;
                    break;
                }
            } else {
                answer = "NO";
                break;
            }

            
        }
        if (compareValue >= parseInt(((arrLength-1) / 2))) {
            answer = "YES";
            break;
        }
        compareValue = 0;
    }

    return answer;
}


const s = "abcacbakcba";
console.log(solution(s))

回文文字列であると判断するために、まず左値と右値を長さの半分比較し、確認後、ない場合は文字列要素を1つずつ切り取り、除外した文字列が回文文字列であるか否かを判断し、compareValueを算出し配列の長さと比較する.
問題は複雑すぎるようだ.
📌 先生のやり方.

function solution(s) {
    let answer = "YES";
    let lt = 0,
      rt = s.length - 1;
    while (lt < rt) {
      if (s[lt] !== s[rt]) {
        let s1 = s.substring(lt, rt);
        let s2 = s.substring(lt + 1, rt + 1);
        if (s1.split("").reverse().join("") !== s1 && s2.split("").reverse().join("") !== s2) {
          answer = "NO";
        }
        break;
      } else {
        lt++;
        rt--;
      }
    }
    return answer;
  }
  
  console.log(solution("aebccba"));

最大1文字を削除して、回文文字列となる場合をYESと呼ぶので、s[lt]とs[rt]が異なる値を表す場合、ltとrtの回文文字列がどれではないかをチェックするためにif文を以下のように記述した後、1つだけ削除してはいけない場合、=NOと答えてwhile文を終了する.
班長
班長を選んで、A、B、C、D、E候補から申し込みます.
投票後に以下の文字列(「BACBACCACBDEE」)を提供し、最も得票の多い候補者を出力します.
📌 私の解決方法

function solution() {
    let answer;
    let sArr = s.split("");
    let index = 0;
    let maxVote = 0;

    const sObject = sArr.reduce((acc, cur) => {
        if(acc[cur]) {
            acc[cur]++;
        } else {
            acc[cur] = 1;
        }
        return acc;
    }, {})

    for(let i = 0; i<Object.values(sObject).length; i++)
    {
        if(Object.values(sObject)[i] > maxVote)
        {
            maxVote = Object.values(sObject)[i];
            index = i;
        }
    }

    answer= Object.keys(sObject)[index];
    return answer;
}

const s = "BACBACCACCBDEDE"

console.log(solution(s));

reduce関数を使用して、各候補オブジェクトをキーとし、受信した投票数を値としてオブジェクトを生成し、オブジェクトの値をクエリーして最大値のインデックスを取得し、インデックス内のキーを出力します.
📌 先生のやり方.

function solution(s) {
    let answer;
    let sh = new Map();
    for (let x of s) {
      sh.set(x, sh.get(x) + 1 || 1);
    }
    let max = 0;
    for (let [key, val] of sh) {
      if (val > max) {
        max = val;
        answer = key;
      }
    }
    return answer;
  }
  
  console.log(solution("BACBACCACCBDEDE"));

mapという関数は初めて見ましたが、mapはキー付きデータを格納する点でオブジェクトと似ていますが、mapはキー上で複数のデータ型を許可する点で違いがあります.
mapでは、次の関数を使用できます.
mapを使用してreduceに値がなければキーと値を生成するように、jsのショートカット評価論理計算法により、shにxという要素がなければ1と計算され、ある場合はsh.get(x)(x)と計算される(xキーの値を取得して1を加える)+1.
その後、[key,val]で保存して値maxを返したときのkeyにアクセスします.
//let sh = new Map();
//sh.set(b,1)-->bはキー、1は値
//get(b)-->キーを使用して値をインポート
//delete(b)-->キーの取り消し
//sh.has("B")-->Bキーは存在しますか?
//sh.size()-->キーの数
//mapアクセス時、for(let[key,val]ofsh)
アナック
Anagramは,2文字列のアルファベット配列順序が異なるが,それらの構造が一致する場合,2つの単語をAnagramと呼ぶ.「YES」または「NO」と印刷し、アナックかどうかを確認します.
アルファベットとその個数が一致-->アナック
(文字列の長さが異なる場合は、構文ではありません!-->必須条件)
📌 私の解決方法

function solution(s1, s2) {
    let answer = "YES";
    let s1Arr = s1.split("");
    let s2Arr = s2.split("");

    s1Arr.sort();
    s2Arr.sort();

    for(let i = 0; i<s1Arr.length; i++)
    {
        if(s1Arr[i] !== s2Arr[i]){
            answer = "NO";
            break;
        }
    }
    return answer;
}

const s1 = "abaCC";
const s2 = "Caaab";

console.log(solution(s1, s2));

2つの文字列をシーケンス化してsortを行い、配列内をナビゲートし、同じ値がない場合はNOを返し、そうでない場合はYESを返します.
📌 先生のやり方.

function solution(s1, s2) {
    let answer = "YES";
    let sh = new Map();
  
    for (let x of s1) {
      sh.set(x, sh.get(x) + 1 || 1);
    }
    for (let x of s2) {
      if (!sh.has(x) || sh.get(x) === 0) {
        return "NO";
      } else {
        sh.set(x, sh.get(x) - 1);
      }
    }
    return answer;
  }
  
  const s1 = "abaCC";
  const s2 = "Caaab";
  
console.log(solution(s1, s2));

mapを使用してs 1情報を含むオブジェクトを作成し、s 2を迂回してs 1情報を含むオブジェクトからキー計算値を削除し、値が適切でないかキーがない場合はNOを返し、そうでない場合は値から-1のみを返します.
文字列の区別
N文字列がある場合は、すべての文字列を区別できる最小長接頭辞を検索します.
「abcdef」、「abdbfer」、「abowls」などの文字列が配列に存在する場合、「ab」で文字列を区切ることはできませんが、3番目の文字列からのみ3を返します.
📌 私の解決方法

function solution(words)
{
    let answer = 100;
    let minCount = 0;

    let arr = new Array(words.length);

    for(let i = 0; i < words.length; i++)
    {
        arr[i] = words[i].split("");
    }

    for(let i = 0; i < words.length-1; i++)
    {
        for(let j = 0; j<words[i].length; j++)
        {
            if (arr[i][j] === arr[i+1][j]) {
                minCount++;
            } else {
                break;
            }
        }
        answer = Math.min(answer, minCount);
        minCount = 0;
    }
    return answer+1;
}

const words = ["longlong", "longtong", "longbig"];

console.log(solution(words));

words配列を2次元配列として作成し、すべての要素にアクセスできるようにし、配列内の要素を1つずつ比較します.要素が同じ場合は、minCountをカウントした後すぐに終了し、答えとminCountの最小値を比較して保存し、最後に+1を加えてインデックスから文字列を分割します.やりがいがある.
📌 先生のやり方.

function solution(words) {
    let answer, i;
  
    let sH = new Map();
    for (i = 0; i < words[0].length; i++) {
      let flag = true;
      for (let j = 0; j < words.length; j++) {
        let x = words[j].substring(0, i + 1);
        if (sH.has(x)) {
          flag = false;
          break;
        }
        sH.set(x, 1);
      }
      if (flag) break;
    }
    answer = i + 1;
    return answer;
  }
  
  const words = ["seeasue", "sesseysu", "semeas"];
  
  console.log(solution(words));

mapを使用して単語の要素を0から比較し、要素が存在する場合はflagをfalseに設定し、breakで次のfor文(iを条件)を直接実行します.区別する文字が一度も現れない場合はflagがtrueになるため、自動的にbreakが発生し、文字列長単位のiが現れ、+1が加算されます.