白筱汐

function bfs(root) {
    let queue = [root];
    while (queue.length) {
        let node = queue.shift();
        console.log(node.val);
        if (node.children) {
            node.children.forEach(child => {
                queue.push(child);
            })
        }
    }
}

const tree = {
    val: 'a',
    children: [
        {
            val: 'b',
            children: [
                {
                    val: 'd'
                },
                {
                    val: 'e'
                }
            ]
        },
        {
            val: 'c',
            children: [
                {
                    val: 'f'
                },
                {
                    val: 'g'
                }
            ]
        }
    ]
}

bfs(tree); // a b c d e f g

const tree = {
    val: 'a',
    children: [
        {
            val: 'b',
            children: [
                {
                    val: 'd'
                },
                {
                    val: 'e'
                }
            ]
        },
        {
            val: 'c',
            children: [
                {
                    val: 'f'
                },
                {
                    val: 'g'
                }
            ]
        }
    ]
}

// 递归实现
function dfs(root) {
    console.log(root.val);
    if (root.children) {
        root.children.forEach(child => {
            dfs(child);
        })
    }
}

// 栈实现
function dfsStack(root) {
    let stack = [root];
    while (stack.length > 0) {
        let node = stack.pop();
        console.log(node.val);
        if (node.children) {
            const children = node.children;
            // 为了保证和递归的访问顺序一致，反向遍历
            for (let i = children.length - 1; i >= 0; i--) {
                stack.push(children[i]);
            }
        }
    }
}

// 计算向量的内积
// A · B = a1 * b1 + a2 * b2 + ... + an * bn
function dotProduct(vector1, vector2) {
  let result = 0;
  for (let i = 0; i < vector1.length; i++) {
      result += vector1[i] * vector2[i];
  }
  return result;
}

// 计算向量的模
// ||V|| = sqrt(v1^2 + v2^2 + ... + vn^2)
function vectorNorm(vector) {
  let squaredSum = 0;
  for (let i = 0; i < vector.length; i++) {
      squaredSum += vector[i] * vector[i];
  }
  return Math.sqrt(squaredSum);
}

// 计算余弦相似度
function cosineSimilarity(vector1, vector2) {
  const dot = dotProduct(vector1, vector2);
  const norm1 = vectorNorm(vector1);
  const norm2 = vectorNorm(vector2);
  
  const similarity = (norm1 !== 0 && norm2 !== 0) ? dot / (norm1 * norm2) : 0;
  return similarity;
}

// 示例向量
const vectorA = [1, 2, 3];
const vectorB = [4, 5, 6];

// 计算余弦相似度
const similarity = cosineSimilarity(vectorA, vectorB);

console.log("余弦相似度：", similarity);

// 示例图的邻接表
const graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6, 7],
    4: [8],
    5: [9],
    6: [10],
};

// 递归实现
const visited = new Set();

function dfs(n) {
    console.log(n)
    visited.add(n)

    const neighbors = graph[n];
    if (neighbors) {
        for (let i = 0; i < neighbors.length; i++) {
            if (!visited.has(neighbors[i])) {
                dfs(neighbors[i])
            }
        }
    }
}

// 栈实现
function dfs2(start) {
    const stack = [start]
    const visited = new Set()
    while (stack.length) {
        const n = stack.pop()
        console.log(n)
        visited.add(n)

        const neighbors = graph[n]
        if (neighbors) {
            for (let i = neighbors.length - 1; i >= 0; i--) {
                if (!visited.has(neighbors[i])) {
                    stack.push(neighbors[i])
                }
            }
        }
    }
}

function findContentChildren(g,s) {
    // 升序排序
    const sort = (a,b) => a - b;
    g.sort(sort);
    s.sort(sort);
    let i = 0;
    s.forEach(n => {
        if (n >= g[i]) {
            i++;
        }
    })
    return i
}

// 吉他15磅 电脑20磅 音响30磅
const weight = [15,20,30]
// 吉他1500$ 电脑2000$ 音响3000$
const values = [1500,2000,3000]
const totalWeight = 35 // 总重量35磅

function maxValue(weight, value, totalWeight) {
    const n = weight.length // n为物品个数
    // 创建一个二位数组来保存状态转移的结果
    // 注意数组的下标从0开始，需要对比上个单元格的值，所以二维数组的行数量为 n + 1,列数量为 totalWeight + 1
    const dp = new Array(n + 1).fill(0).map(() => new Array(totalWeight + 1).fill(0))

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= totalWeight; j++) {
            // 如果当前物品小于等于剩余空间
            if (weight[i - 1] <= j) {
                // 比较（上一个单元格的值）和（当前物品的重量 + 剩余空间的价值）两者中较大的那个
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1])
            } else {
                // 当前物品大于剩余空间
                dp[i][j] = dp[i - 1][j]
            }
        }
    }
    return dp[n][totalWeight];
}

function fib(n) {
    if (n === 0) {
        return 0
    } else if (n === 1) {
        return 1
    } else {
        return fib(n - 1) + fib(n - 2)
    }
}

function fib(n) {
    if (fib.cache[n]) {
        return fib.cache[n]
    } 
    return fib.cache[n] = fib(n - 1) + fib(n -2)
}
fib.cache = {
    0:1,
    1:1
}

function climbStairs(n) {
    if (n < 2) return 1
    const dp = [1,1]
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i -2]
    }
    return dp[n]
}

function climbStairs2(n) {
    if (n < 2) return 1
    let p = 1,q = 1
    for (let i = 2; i <= n; i++) {
        // 通过一个临时变量来转移状态,优化空间复杂度
        const temp = p
        p = q
        q = temp + q
    }
    return q
}

function dijkstra(graph,startNode) {
    const visited = new Set() // 保存访问过的节点
    const distance = {} // 记录起始节点到各个节点的最短距离
    const parents = {} // 记录每个节点对应的前一个节点

    // 初始化起始节点到其他节点的距离为正无穷大
    for (const node in graph) {
        distance[node] = Infinity
    }

    // 起始节点到自身的距离为0
    distance[startNode] = 0

    // 遍历所有节点
    while(visited.size < Object.keys(graph).length) {
        let minDistance = Infinity
        let closestNode = null;
        // 选择当前距离最小且未被访问过的节点
        for (const node in distance) {
            if (!visited.has(node) && distance[node] < minDistance) {
                minDistance = distance[node]
                closestNode = node
            }
        }

        // 标记选择的节点为已访问
        visited.add(closestNode);

        // 更新与选择节点相邻节点的最短距离和前驱节点
        for (const neighbor in graph[closestNode]) {
            const weight = graph[closestNode][neighbor];
            const newDistance = distance[closestNode] + weight;
            if (newDistance < distance[neighbor]) {
                distance[neighbor] = newDistance;
                parents[neighbor] = closestNode;
            }
        }
    }

    return { distance, parents }
}

// 回溯最短路径
function shortestPaths(parents,startNode,endNode) {
    const path = [endNode];
    let currentNode = endNode;

    // 从终点往前遍历最短路径
    while (currentNode !== startNode) {
        currentNode = parents[currentNode];
        path.unshift(currentNode);  // 在数组开头添加节点
    }

    return path;
}


// 示例数据
const graph = {
    A: { B: 5, C: 2 },
    B: { A: 5, C: 2, D: 3 },
    C: { A: 2, B: 2, D: 1 },
    D: { B: 3, C: 1 },
};

const startNode = 'A';
const endNode = 'D';

const { distance, parents } = dijkstra(graph, startNode);
console.log(distance)
console.log(shortestPaths(parents, startNode,endNode));

class A {
    b: B;
}
class B {
    c: C;
}
class C {
    hello() {
        console.log('hello world');
    }
}

const container = new Container();
const a = container.get(A);
// a.b.c.hello() === 'hello world'

class Container {
    
    get(Module) {
        // 创建对象
        const obj = new Module();
        // 拿到属性
        const properties = Object.getOwnPropertyNames(obj);
        for(let p of properties) {
            if (!obj[p]) {
                // 如果对象不存在，就往下创建
                if (p === 'b') {
                    obj[p] = this.get(B);
                } else if (p === 'c') {
                    obj[p] = this.get(C);
                } else {}
            }
        }
    }
}

class A {
    b: B;
    d: D;
}
class B {
    c: C;
}
class D {
    b: B;
    c: C;
}

class Container {
    
    cachae = {};
    
    getName(Module) {
        return Module.Name.toLowerCase();
    }
    
    get(Module) {
        // 弄个缓存
        if (this.cachae[this.getName(Module)]) {
            return this.cachae[this.getName(Module)];
        }
        
        // 创建对象
        const obj = new Module();
        // 缓存起来下次