Dự án cuối khoá: 3 bài toán DSA

duong-di.ts · BFS có ghi cha để dựng lại đường ngắn nhất

const dothi: Record<string, string[]> = {
  A: ['B', 'C'], B: ['A', 'D', 'E'], C: ['A', 'F'],
  D: ['B'], E: ['B', 'F'], F: ['C', 'E', 'G'], G: ['F'],
};

function duongNganNhat(g: Record<string, string[]>, start: string, goal: string) {
  if (start === goal) return [start];
  const cha = new Map<string, string>();     // bang bam: con -> cha
  const seen = new Set([start]);
  const queue = [start];                      // hang doi cho BFS
  while (queue.length) {
    const cur = queue.shift()!;
    for (const nb of g[cur]) {
      if (seen.has(nb)) continue;
      seen.add(nb); cha.set(nb, cur);
      if (nb === goal) {                       // tim thay: lan nguoc theo 'cha'
        const path = [goal]; let p = goal;
        while (cha.has(p)) { p = cha.get(p)!; path.unshift(p); }
        return path;
      }
      queue.push(nb);
    }
  }
  return null;                                 // khong toi duoc
}

console.log(duongNganNhat(dothi, 'A', 'G').join(' → '));

A → C → F → G

kiem-ngoac.ts · ngăn xếp soát ngoặc trong code

function ngoacCan(s: string): boolean {
  const stack: string[] = [];
  const cap: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') stack.push(ch);
    else if (ch in cap) {
      if (stack.pop() !== cap[ch]) return false; // dong khong khop mo gan nhat
    }
  }
  return stack.length === 0; // con ngoac mo chua dong -> chua can
}

for (const code of ['f(a[0], b[1])', 'arr[(i+1])', 'if (x) { y(); }'])
  console.log(`${ngoacCan(code)}\t${code}`);

true	f(a[0], b[1])
false	arr[(i+1])
true	if (x) { y(); }

xep-hang.ts · gom điểm bằng Map rồi sắp xếp

function bangXepHang(diem: [string, number][]): [string, number][] {
  const tong = new Map<string, number>();
  for (const [ten, d] of diem)
    tong.set(ten, (tong.get(ten) ?? 0) + d);  // bang bam: cong don theo ten
  return [...tong].sort((a, b) => b[1] - a[1]); // sap giam dan theo diem
}

const diem: [string, number][] = [
  ['Miu', 3], ['Bun', 5], ['Miu', 4], ['Ngao', 2], ['Bun', 1],
];

bangXepHang(diem).forEach(([ten, d], i) => console.log(`${i + 1}. ${ten}: ${d}`));

1. Miu: 7
2. Bun: 6
3. Ngao: 2