请你判断一个9X9的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字1-9在每一行只能出现一次
数字1-9在每一列只能出现一次
数字1-9在每一个以粗实线分割的3X3宫内只能出现一次。
数独部分空格内已填入了数字，空白格用'.'表示

// 输入：nums = [4,5,2,1], queries = [3,10,21]
// 输出：[2,3,4]
// 解释：queries 对应的 answer 如下：
// - 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
// - 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
// - 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 
var answerQueries = function(nums, queries) {
    const n = nums.length, m = queries.length;
    nums.sort((a, b) => a - b);
    const f = new Array(n + 1).fill(0);
    for(let i = 0; i < n; i++) {
        f[i + 1] = f[i] + nums[i];
    }
    const answer = new Array(m).fill(0);
    for(let i = 0; i < m; i++) {
        answer[i] = binarySearch(f, queries[i]) - 1;
    }
    return answer;
}
const  binarySearch = (f, target) => {
    let low = 1, high = f.length;
    while (low < high) {
        const mid = low + Math.floor((high - low) / 2);
        if (f[mid] > target) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
};

// 输入：piles = [2,7,9,4,4]
// 输出：10
// 解释：如果一开始Alice取了一堆，Bob取了两堆，然后Alice再取两堆。爱丽丝可以得到2 + 4 + 4 = 10堆。如果Alice一开始拿走了两堆，那么Bob可以拿走剩下的三堆。在这种情况下，Alice得到2 + 7 = 9堆。返回10，因为它更大。
const stoneGameII = function(piles) {
    const prefixSum = new Array(piles.length + 1).fill(0);
    for(let i = 0; i < piles.length; i++) {
        prefixSum[i + 1] = prefixSum[i] + piles[i];
    }
    const memo = new Map();
    return Math.floor((prefixSum[piles.length] + dp(memo, piles, prefixSum, 0, 1)) / 2);
}
const dp = (memo, piles, prefixSum, i, m) => {
    if(i === piles.length) {
        return 0;
    }
    const key = i * 201 + m;
    if(!memo.has(key)) {
        let maxVal = -Number.MAX_VALUE;
        for(let x = 1; x <= 2 * m; x++) {
            if(i + x > piles.length) {
                break;
            }
            maxVal = Math.max(maxVal, prefixSum[i + x] - prefixSum[i] - dp(memo, piles, prefixSum, i + x, Math.max(m, x)));
        }
        memo.set(key, maxVal);
    }
    return memo.get(key);
}

// 如果一个密码满足以下所有条件，我们称它是一个 强 密码：

// 它有至少 8 个字符。
// 至少包含 一个小写英文 字母。
// 至少包含 一个大写英文 字母。
// 至少包含 一个数字 。
// 至少包含 一个特殊字符 。特殊字符为："!@#$%^&*()-+" 中的一个。
// 它 不 包含 2 个连续相同的字符（比方说 "aab" 不符合该条件，但是 "aba" 符合该条件）。
// 给你一个字符串 password ，如果它是一个 强 密码，返回 true，否则返回 false 。

// 输入：password = "IloveLe3tcode!"
// 输出：true
// 解释：密码满足所有的要求，所以我们返回 true 。
var strongPasswordCheckerII = password => {
    return /^(?=.*\d)(?=.*[a-z])(?=.*[A-Z])(?=.*[!@#$%^&*()\-+])(?!.*(.)\1+).{8,}$/.test(password)
}

let trap = height => {
    let stack = [];
    let ans = 0;
    let n = height.length;
    for(let i = 0; i < n; i++) {
        if(stack.length && height[i] > height[stack[stack.length - 1]]) {
            let top = stack.pop();
            if(!stack.length) break;
            let left = stack[stack.length - 1];
            let curWidth = i - left - 1;
            let curHeight = Math.min(height[left], height[i] - height[top]);
            ans += curWidth * curHeight;
        }
        stack.push(i);
    }
    return ans;
}

let graph = [
    [0, 2, 4, 0, 0, 0],
    [0, 0, 2, 4, 2, 0],
    [0, 0, 0, 0, 3, 0],
    [0, 0, 0, 0, 0, 2],
    [0, 0, 0, 3, 0, 2],
    [0, 0, 0, 0, 0, 0]
];
// a-b-c-d-e-f    b-a-b-c-d-e-f c-a-b-c-d-e-f ...
let INF = Number.MAX_SAFE_INTEGER // MAX_SAFE_INTEGER属性表示在JavaScript的最大安全整数

// 从尚未处理的顶点选出距离最近的顶点
function minDistance(dist, visited) {
    let min = INF;
    let minIndex = -1;
    for(let i = 0; i < dist.length; i++) {
        if(!visited[i] && dist[i] < min) {
            minIndex = i;
            min = dist[i];
        }
    }
    return minIndex;
}
function dijkstra(src) {
    let dist = [];
    let visited = [];
    let length = graph.length;
    for(let i = 0; i < length; i++) { // (1)
        dist[i] = INF;
        visited[i] = false;
    }
    dist[src] = 0; // (2);
    for(let j = 0; j < length - 1; j++) { // (3)
        let u = minDistance(dist, visited); // (4)
        visited[u] = true; // (5)
        for(let v = 0; v < length; v++) {
            if(
                !visited[v] && // (6)
                dist[u] != INF && // (7)
                graph[u][v] != 0 && // (8)
                dist[u] + graph[u][v] < dist[v] // (9)
            ) {
                dist[v] = dist[u] + graph[u][v] // (10)
            }
        }
    }
    return dist // (11)
}
const res = dijkstra(0);
console.log(res, 'res'); // [0, 2,4, 5, 4,6];
// 求B点到其他点的最短距离
// const res = dijkstra(1);
// Infinity表示点B与点A不相邻，从上图可知A与B相邻，而B与A不相邻
// [ Infinity, 0, 2, 4, 2, 4 ]