LeetCode-7

刷啊，有点有心无力，有些题目可能之后再刷了。

318 最大单词长度乘积

刷题时间：2021-11-17

垃圾时间和垃圾空间，自己写的果然不行，主要拉在了单词对比上。

var maxProduct = function (words) {
    let res = 0;
    const n = words.length;
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            if (isUnique(words[i], words[j]) && res < words[i].length * words[j].length) {
                res = words[i].length * words[j].length;
            }
        }
    }
    return res;
};

const isUnique = function (a, b) {
    const num_a = 'a'.charCodeAt();
    const res = new Array(26).fill(0);

    for (const i of a) {
        res[i.charCodeAt() - num_a]++;
    }
    for (const j of b) {
        res[j.charCodeAt() - num_a]--;
    }
    let sum = 0;
    for (const r of res) {
        sum += Math.abs(r);
    }
    if (sum != a.length + b.length) {
        return false;
    }
    return true;
};

上个官解的，用了位运算，这样子预处理的时候还是要遍历word的每一字字符，只不过比较的时候，只需要与一下，这样子就能判断是不是相同的。比我的方法快了不知道哪里去了，我这也太慢了。

var maxProduct = function(words) {
    const length = words.length;
    const masks = new Array(length).fill(0);
    for (let i = 0; i < length; i++) {
        const word = words[i];
        const wordLength = word.length;
        for (let j = 0; j < wordLength; j++) {
            masks[i] |= 1 << (word[j].charCodeAt() - 'a'.charCodeAt());
        }
    }
    let maxProd = 0;
    for (let i = 0; i < length; i++) {
        for (let j = i + 1; j < length; j++) {
            if ((masks[i] & masks[j]) === 0) {
                maxProd = Math.max(maxProd, words[i].length * words[j].length);
            }
        }
    }
    return maxProd;
};

还有更优化一点的，因为字母相同，但是长度不相同的，比如meet和met，他们的掩码都一样，那么只需要最长的那个长度留下来，met就可以去掉了，用map来保存，给个go的解法

func maxProduct(words []string) (ans int) {
    masks := map[int]int{}
    for _, word := range words {
        mask := 0
        for _, ch := range word {
            mask |= 1 << (ch - 'a')
        }
        if len(word) > masks[mask] {
            masks[mask] = len(word)
        }
    }

    for x, lenX := range masks {
        for y, lenY := range masks {
            if x&y == 0 && lenX*lenY > ans {
                ans = lenX * lenY
            }
        }
    }
    return
}

39 组合总和

这类递归我真的不行，不知道为什么我这么菜，我之后一定要着重学习一下这类题目

var combinationSum = function (candidates, target) {
    const ans = [];
    const dfs = (target, combine, idx) => {
        if (idx === candidates.length) {
            return;
        }
        if (target === 0) {
            ans.push(combine);
            return;
        }
        // 直接跳过
        dfs(target, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            dfs(target - candidates[idx], [...combine, candidates[idx]], idx);
        }
    };
    dfs(target, [], 0);
    return ans;
};

这个方法更像我自己写的，我没有写个start，有点尿了

const combinationSum = (candidates, target) => {
  const res = [];
  const dfs = (start, temp, sum) => {
    if (sum >= target) {        // 爆掉了，不用继续选数了
      if (sum == target) {      // 加入解集
        res.push(temp.slice()); // temp的拷贝
      }
      return;                   // 结束当前递归
    }
    for (let i = start; i < candidates.length; i++) { // 枚举出选择，从start开始
      temp.push(candidates[i]);          // 加入“部分解”
      dfs(i, temp, sum + candidates[i]); // 往下继续选择，同时sum累加上当前数字
      temp.pop();                        // 撤销选择
    }
  };
  dfs(0, [], 0);
  return res;
};

40 组合总和 II

放弃了，以后把这类回溯问题都看一遍

var combinationSum2 = function(candidates, target) {
    const res = []; path = [], len = candidates.length;
    candidates.sort();
    backtracking(0, 0);
    return res;
    function backtracking(sum, i) {
        if (sum > target) return;
        if (sum === target) {
            res.push(Array.from(path));
            return;
        }
        let f = -1;
        for(let j = i; j < len; j++) {
            const n = candidates[j];
            if(n > target - sum || n === f) continue;
            path.push(n);
            sum += n;
            f = n;
            backtracking(sum, j + 1);
            path.pop();
            sum -= n;
        }
    }
};

594 最长和谐子序列

刷题时间：2021-11-20

最近两天有点忙，没有空刷题，今天重新开刷，这题目说实话有点难的，没想到是简单题目，先用排序进行排序，然后就没有然后了。

var findLHS = function (nums) {
    nums.sort((a, b) => a - b);
    let ans = 0,
        l = 0;

    for (let i = 0; i < nums.length; i++) {
        while (nums[i] - nums[l] > 1) {
            l++;
        }
        if (nums[i] - nums[l] == 1) {
            ans = Math.max(i - l + 1, ans);
        }
    }
    return ans;
};

用这个哈希表，有点牛逼的，直接统计每个数的个数，然后再遍历哈希表，找x+1，就很快

var findLHS = function(nums) {
    const cnt = new Map();
    let res = 0;
    for (const num of nums) {
        cnt.set(num, (cnt.get(num) || 0) + 1);
    }
    for (const key of cnt.keys()) {
        if (cnt.has(key + 1)) {
            res = Math.max(res, cnt.get(key) + cnt.get(key + 1));
        }
    }
    return res;
};

559 N 叉树的最大深度

刷题时间：2021-11-21

就这个多节点我是没想到是怎么表示的，没想到是遍历children来获取的

var maxDepth = function (root) {
    if (!root) return 0;
    let res = 0;
    for (const child of root.children) {
        res = Math.max(res, maxDepth(child));
    }
    return res + 1;
};

广度优先，这个也简单

var maxDepth = function (root) {
    if (!root) return 0;
    const queue = [];
    queue.push(root);
    let res = 0;
    while (queue.length) {
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            const children = node.children;
            for (const child of children) {
                queue.push(child);
            }
        }
        res++;
    }
    return res;
};

384 打乱数组

刷题时间：2021-11-22

每次遇到这种题目，我基本上都是直接看题解的，自己有点没思路的感觉，虽然挺简单的，不过我觉得OJ应该也不会出这种题目。

var Solution = function (nums) {
    this.nums = nums;
    this.original = nums.slice();
};

/**
 * @return {number[]}
 */
Solution.prototype.reset = function () {
    this.nums = this.original.slice();
    return this.nums;
};

/**
 * @return {number[]}
 */
Solution.prototype.shuffle = function () {
    const shuffled = new Array(this.nums.length).fill(0);
    const list = this.nums.slice();
    // const list = [];
    // this.nums.forEach((num) => list.push(num));
    for (let i = 0; i < this.nums.length; ++i) {
        const j = Math.random() * list.length;
        shuffled[i] = list.splice(j, 1);
    }
    this.nums = shuffled.slice();
    return this.nums;
};

Fisher-Yates 洗牌算法这个看起来挺牛的，就是原地洗牌，在第i次循环中，从[i,n)中随机抽取一个下标j；将第i个元素与第j个元素交换，这样子时间只用O(n)，来个Go版本的

type Solution struct {
	nums, original []int
}

func Constructor(nums []int) Solution {
	return Solution{nums, append([]int(nil), nums...)}
}

func (s *Solution) Reset() []int {
	copy(s.nums, s.original)
	return s.nums
}

func (s *Solution) Shuffle() []int {
	n := len(s.nums)
	for i := range s.nums {
		j := i + rand.Intn(n-i)
		s.nums[i], s.nums[j] = s.nums[j], s.nums[i]
	}
	return s.nums
}

17 电话号码的字母组合

刷题时间：2021-11-22

又是我想不出来，查看答案的一天，尿了。

var letterCombinations = function (digits) {
    if (digits == '') {
        return [];
    }
    const number = new Map([
        ['2', 'abc'],
        ['3', 'def'],
        ['4', 'ghi'],
        ['5', 'jkl'],
        ['6', 'mno'],
        ['7', 'pqrs'],
        ['8', 'tuv'],
        ['9', 'wxyz']
    ]);
    const res = [];
    const dfs = function (index, str) {
        if (index == digits.length) {
            res.push(str);
        } else {
            const tmp = number.get(digits[index]);
            for (let t of tmp) {
                dfs(index + 1, str + t);
            }
        }
    };
    dfs(0, '');
    return res;
};

22 括号生成

我可真是five，只能抄别人答案，算什么男人！

var generateParenthesis = function (n) {
    const res = [];
    const dfs = function (left, right, str) {
        if (left == n && right == n) {
            res.push(str);
        } else {
            if (left > right) {
                if (left < n) {
                    dfs(left + 1, right, str + '(');
                }
                dfs(left, right + 1, str + ')');
            } else if (left == right) {
                dfs(left + 1, right, str + '(');
            }
        }
    };
    dfs(0, 0, '');
    return res;
};

79 单词搜索

呜呜呜，错了几次总算写出来了，就这种题目真的是太难了。

var exist = function (board, word) {
    const m = board.length;
    const n = board[0].length;

    const flag = Array.from(new Array(m), () => {
        return new Array(n).fill(false);
    });
    const dfs = function (i, j, index) {
        if (index == word.length) return true;
        if (i < 0 || i >= m || j < 0 || j >= n || flag[i][j]) {
            return false;
        }
        if (word[index] == board[i][j] && !flag[i][j]) {
            flag[i][j] = true;
            if (dfs(i + 1, j, index + 1)) return true;
            if (dfs(i, j + 1, index + 1)) return true;
            if (dfs(i - 1, j, index + 1)) return true;
            if (dfs(i, j - 1, index + 1)) return true;
        }
        flag[i][j] = false;
        return false;
    };
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] == word[0]) {
                if (dfs(i, j, 0)) return true;
            }
        }
    }
    return false;
};

213 打家劫舍 II

刷题时间：2021-11-22

在打家劫舍1的基础上进行学习，其实就是遍历两遍，要么只要[0,n-1]，要么就是[1,n]。

const rob = function (nums) {
    const n = nums.length;
    if (n == 1) {
        return nums[0];
    } else if (n == 2) {
        return Math.max(nums[0], nums[1]);
    }
    return Math.max(func(nums, 0, n - 1), func(nums, 1, n));
};
const func = function (nums, start, end) {
    const n = nums.length;
    let q = 0,
        p = 0,
        r = nums[start];

    for (let i = start + 1; i < end; i++) {
        q = p;
        p = r;
        r = Math.max(p, q + nums[i]);
    }
    return Math.max(r, p);
};

859 亲密字符串

刷题日期：2021-11-23

就不贴一开始的代码了，优化了一下，直接先判断两个是不是相同的，然后找出不同之处，直接截断，这样子时间会大大加快。

var buddyStrings = function (s, goal) {
    if (s.length != goal.length) return false;
    const n = s.length;
    const map = new Map();
    let diff = [];
    if (s == goal) {
        for (let i of s) {
            if (map.get(i) == 1) {
                return true;
            } else {
                map.set(i, 1);
            }
        }
    }
    for (let i = 0; i < n; i++) {
        if (s[i] != goal[i]) {
            diff.push(s[i], goal[i]);
        }
    }
    if (diff.length == 4 && diff[0] == diff[3] && diff[1] == diff[2]) {
        return true;
    }
    return false;
};

55 跳跃游戏

dp为最远距离，也不知道为什么这么慢是怎么回事

var canJump = function (nums) {
    const n = nums.length;
    let dp = 0;
    for (let i = 0; i < n - 1; i++) {
        if (dp < i) return false;
        dp = Math.max(dp, nums[i] + i);
    }
    if (dp >= n - 1) {
        return true;
    }
    return false;
};

干，看了别人的，稍微优化了一下，就直接能行，确实，但时间怎么差的这么多

var canJump = function (nums) {
    const n = nums.length;
    let dp = 0;
    for (let i = 0; i < n; i++) {
        if (dp < i) return false;
        dp = Math.max(dp, nums[i] + i);
    }
    return true;
};

45 跳跃游戏 II

干，又要看提示，其实和我想的差不多，只不过还差一点意思。

var jump = function (nums) {
    const n = nums.length;
    let dp = 0;
    let res = 0;
    let end = 0;
    for (let i = 0; i < n - 1; i++) {
        dp = Math.max(dp, nums[i] + i);
        if (i == end) {
            end = dp;
            res++;
        }
    }
    return res;
};

62 不同路径

直接抄以前的C++解法，舒服了

var uniquePaths = function (m, n) {
    const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    return dp[m - 1][n - 1];
};

还有个组合数学的方法，就离谱，我不会

var uniquePaths = function(m, n) {
    let ans = 1;
    for (let x = n, y = 1; y < m; ++x, ++y) {
        ans = Math.floor(ans * x / y);
    }
    return ans;
};

5 最长回文子串

就最简单的思想，遍历每一个文字，从中间往外扩散看看有没有回文，需要注意要有两个，一个是单字符，还有一个是双字符，两种情况都是不一样的，都要考虑进去

var longestPalindrome = function (s) {
    const n = s.length;
    const expand = function (left, right) {
        while (left >= 0 && right < n && s[left] == s[right]) {
            --left;
            ++right;
        }
        // console.log(left);
        return [left + 1, right - 1];
    };
    let end = 0,
        start = 0;
    for (let i = 0; i < n; i++) {
        let arr = expand(i, i);
        let left = arr[0];
        let right = arr[1];
        if (right - left > end - start) {
            end = right;
            start = left;
        }
        arr = expand(i, i + 1);
        left = arr[0];
        right = arr[1];
        if (right - left > end - start) {
            end = right;
            start = left;
        }
    }
    return s.substring(start, end + 1);
};

413 等差数列划分

我直接背一遍题解，抄下来，tmp就是有点连续子序列的个数吧，如果连续的，那么就是上次连续的个数+1，比如，1234，123的个数是1，到4的时候，是1+1，也就是上一个连续次数的+1，如果还有5的话，那么就是2+1，就相当于直接把上次的拿来用，然后多出5这种情况，反正就有点怪怪的。

var numberOfArithmeticSlices = function (nums) {
    let dp = nums[0] - nums[1];
    let res = 0;
    let tmp = 0;
    for (let i = 2; i < nums.length; i++) {
        if (nums[i - 1] - nums[i] == dp) {
            tmp++;
        } else {
            dp = nums[i - 1] - nums[i];
            tmp = 0;
        }
        res += tmp;
    }
    return res;
};

91 解码方法

刷题时间：2021-11-23

这道题写了好久，干，就是有好多情况需要考虑，尽在不言处啊。

var numDecodings = function (s) {
    if (s[0] == '0') {
        return 0;
    }
    const dp = new Array(s.length + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    for (let i = 1; i < s.length; i++) {
        if ((s[i] != '0' && s[i - 1] == '1') || (['1', '2', '3', '4', '5', '6'].includes(s[i]) && s[i - 1] == '2')) {
            dp[i + 1] += dp[i] + dp[i - 1];
        } else if (s[i] == '0') {
            if (!['1', '2'].includes(s[i - 1])) {
                return 0;
            } else if (i - 2 >= 0 && (s[i - 2] == '1' || s[i - 2] == '2')) {
                dp[i + 1] = dp[i - 1];
            } else dp[i + 1] = dp[i];
        } else {
            dp[i + 1] = dp[i];
        }
    }
    return dp[s.length];
};

日，官解的好简单

var numDecodings = function (s) {
    const n = s.length;
    const f = new Array(n + 1).fill(0);
    f[0] = 1;
    for (let i = 1; i <= n; ++i) {
        if (s[i - 1] !== '0') {
            f[i] = f[i - 1];
        }
        if (i > 1 && s[i - 2] != '0' && (s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 26) {
            f[i] += f[i - 2];
        }
    }
    return f[n];
};

然后用三个变量进行替代，然后加上一个小剪枝。

var numDecodings = function (s) {
    const n = s.length;
    // a = f[i-2], b = f[i-1], c = f[i]
    let a = 0,
        b = 1,
        c = 0;
    for (let i = 1; i <= n; ++i) {
        if (b == 0) return 0;
        c = 0;
        if (s[i - 1] !== '0') {
            c += b;
        }
        if (i > 1 && s[i - 2] != '0' && (s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 26) {
            c += a;
        }
        a = b;
        b = c;
    }
    return c;
};

我再把我的方法精简一下，换成三个变量，这样子空间和用时都快多了。

var numDecodings = function (s) {
    if (s[0] == '0') {
        return 0;
    }
    let a = 1,
        b = 1,
        c = 0;

    for (let i = 0; i < s.length; i++) {
        c = 0;
        if ((s[i] != '0' && s[i - 1] == '1') || (['1', '2', '3', '4', '5', '6'].includes(s[i]) && s[i - 1] == '2')) {
            c += b + a;
        } else if (s[i] == '0') {
            if (!['1', '2'].includes(s[i - 1])) {
                return 0;
            } else if (i - 2 >= 0 && (s[i - 2] == '1' || s[i - 2] == '2')) {
                c = a;
            } else c = b;
        } else {
            c = b;
        }
        a = b;
        b = c;
    }
    return c;
};

139 单词拆分

就硬抄官解，自己只有一个很模糊的想法

var wordBreak = function (s, wordDict) {
    const n = s.length;
    const wordDictSet = new Set(wordDict);
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && wordDictSet.has(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
};

423 从英文中重建数字

刷题时间：2021-11-24

自己写的拉了，还是用官解好了

var originalDigits = function (s) {
    const c = new Map();
    for (const ch of s) {
        c.set(ch, (c.get(ch) || 0) + 1);
    }

    const cnt = new Array(10).fill(0);
    cnt[0] = c.get('z') || 0;
    cnt[2] = c.get('w') || 0;
    cnt[4] = c.get('u') || 0;
    cnt[6] = c.get('x') || 0;
    cnt[8] = c.get('g') || 0;

    cnt[3] = (c.get('h') || 0) - cnt[8];
    cnt[5] = (c.get('f') || 0) - cnt[4];
    cnt[7] = (c.get('s') || 0) - cnt[6];

    cnt[1] = (c.get('o') || 0) - cnt[0] - cnt[2] - cnt[4];

    cnt[9] = (c.get('i') || 0) - cnt[5] - cnt[6] - cnt[8];

    const ans = [];
    for (let i = 0; i < 10; ++i) {
        for (let j = 0; j < cnt[i]; ++j) {
            ans.push(String.fromCharCode(i + '0'.charCodeAt()));
        }
    }
    return ans.join('');
};

300 最长递增子序列

刷题时间：2021-11-24

O(n2)的方法，还行就。 dp[i] 严格比目前值小的长度

var lengthOfLIS = function (nums) {
    const n = nums.length;
    const dp = new Array(n).fill(1);
    for (let i = 0; i < n; i++) {
        let max = 0;
        for (let j = i; j >= 0; j--) {
            if (nums[j] < nums[i]) {
                max = Math.max(dp[j], max);
            }
        }
        dp[i] += max;
    }
    return Math.max.apply(null, dp);
};

这个O(nlogn)的速度是真的快啊

d[i] ，表示长度为 i的最长上升子序列的末尾元素的最小值

用 len 记录目前最长上升子序列的长度

var lengthOfLIS = function (nums) {
    const n = nums.length;
    if (n == 0) {
        return 0;
    }
    let len = 1;

    const d = new Array(n + 1).fill(0);
    d[len] = nums[0];
    for (let i = 1; i < n; ++i) {
        if (nums[i] > d[len]) {
            d[++len] = nums[i];
        } else {
            let l = 1,
                r = len,
                pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
            while (l <= r) {
                let mid = (l + r) >> 1;
                if (d[mid] < nums[i]) {
                    pos = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            d[pos + 1] = nums[i];
        }
    }
    return len;
};

673 最长递增子序列的个数

拉胯O(n2)

dp[i] 以nums[i]为结尾的，严格比目前值小的长度

cnt[i] 以nums[i]为结尾的，比目前小的最长序列的个数

var findNumberOfLIS = function (nums) {
    const n = nums.length;
    let maxLen = 0,
        ans = 0;
    const dp = new Array(n).fill(1);
    const cnt = new Array(n).fill(1);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    cnt[i] = cnt[j]; // 重置计数
                } else if (dp[j] + 1 === dp[i]) {
                    cnt[i] += cnt[j];
                }
            }
        }
        console.log(cnt);
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            ans = cnt[i]; // 重置计数
        } else if (dp[i] === maxLen) {
            ans += cnt[i];
        }
    }
    return ans;
};

1143 最长公共子序列

这题真的是二维动态数组的经典，虽然我写不出来，但可以回味复习，典中典。

dp[i][j]代表text1[0:i]和text2[0:j]的最长公共子序列长度。

var longestCommonSubsequence = function(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        const c1 = text1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = text2[j - 1];
            if (c1 === c2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
};

583 两个字符串的删除操作

就是最长公共子序列，最后返回那里改一下就行了，就这？

var minDistance = function (word1, word2) {
    const m = word1.length,
        n = word2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        const c1 = word1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = word2[j - 1];
            if (c1 === c2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return m + n - 2 * dp[m][n];
};

1091 二进制矩阵中的最短路径

居然是bfs，可惜我做不出来，不过这题看懂了就简单了

/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestPathBinaryMatrix = function (grid) {
    // 缓存矩阵的终点位置
    const m = grid.length - 1;
    const n = grid[0].length - 1;

    // 当起点和终点为1时，必然无法到达终点
    if (grid[0][0] === 1 || grid[m][n] === 1) {
        return -1;
    }

    // 如果矩阵只有1个点，且为0，路径为1
    if (m === 0 && n === 0 && grid[0][0] === 0) {
        return 1;
    }

    let queue = [[0, 0]]; // 使用队列进行BFS搜索
    let level = 1; // 缓存路径长度，起点的长度为1
    // 可以向四周所有方向行走，缓存8个方向
    const direction = [
        [-1, 1], // 右上
        [0, 1], // 右
        [1, 1], // 右下
        [1, 0], // 下
        [1, -1], // 左下
        [-1, 0], // 上
        [0, -1], // 左
        [-1, -1] // 左上
    ];

    // 如果队列中有值，则继续搜索
    while (queue.length) {
        // 缓存当前层的节点数量
        let queueLength = queue.length;

        // 每次只遍历当前一层的节点
        while (--queueLength >= 0) {
            // 出队一个坐标，计算它可以行走的下一步位置
            const [x, y] = queue.shift();

            for (let i = 0; i < direction.length; i++) {
                // 下一步可以向四周行走，计算出相应新坐标
                const newX = x + direction[i][0];
                const newY = y + direction[i][1];

                // 如果新坐标超出网格，或者被标记为1，表示无法行走，则跳过
                if (newX < 0 || newY < 0 || newX > m || newY > n || grid[newX][newY] === 1) {
                    continue;
                }

                // 如果新坐标是终点，表示找到路径，返回长度即可
                if (newX === m && newY === n) {
                    return level + 1;
                }
                // 将走过的位置标记为1，避免重复行走
                grid[newX][newY] = 1;
                // 将下一步的坐标存入队列，用于下一层循环
                queue.push([newX, newY]);
            }
        }

        level++; // 每向前走一层，将步数加1
    }

    return -1;
};