月度归档: 2021年6月

LeetCode刷题【17】电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

 

示例 1:

输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2:

输入:digits = ""
输出:[]

示例 3:

输入:digits = "2"
输出:["a","b","c"]

 

提示:

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。
Related Topics
  • 哈希表
  • 字符串
  • 回溯
  • \n
  • 👍 1372
  • 👎 0
  • 题解

    看到题目第一印象是遍历多重循环,然后想了下好像不对,给定的字符串长度不定,瞅了一眼评论区,基本都是回溯,emmmmmmm

    想玩点花的,突然想到之前有做过一个转盘锁的,于是计上心来,动手开始撸,

    直白点的说明的话,就是说,从[0,0,0,0.....,0]枚举到[3,3,4,3,....4]这样的组合

    class Solution {
        private char[][] map = new char[][]{
                {97,98,99,0},    {100,101,102,0},
                {103,104,105,0},  {106,107,108,0}, {109,110,111,0},
                {112,113,114,115},{116,117,118,0}, {119,120,121,122}
        };
    
        public List<String> letterCombinations(String digits) {
    //        String n = "0123456789";//48-57
            char[] nCharArr = digits.toCharArray();
            int charLength = nCharArr.length;
            if (charLength ==0){
                return new ArrayList<>();
            }
            int count = 1;
            for (char c : nCharArr) {
                if (map[c-50][3]==0){
                    count = count * 3;
                }else{
                    count = count * 4;
                }
            }
            char[][] res = new char[count][charLength];
            int[] stepCount = new int[charLength];
            Arrays.fill(stepCount,0);
            for (int i = 0; i < count; i++) {
                for (int j = 0; j < stepCount.length; j++) {
                    res[i][j] = map[nCharArr[j]-50][stepCount[j]];
                }
                stepInc( nCharArr, stepCount );
            }
            List<String> resList = new ArrayList<>();
            for (char[] re : res) {
                resList.add(new String(re));
            }
    //        System.out.println(res);
            return resList;
        }
    
        private void stepInc(char[] nCharArr, int[] stepCount){
            boolean willPlus = true;
            for (int i = 0; i < stepCount.length; i++) {
                int index = stepCount.length - i - 1;
                if (willPlus){
                    stepCount[index] = stepCount[index]+1;
                    if(map[nCharArr[index]-50][3]==0){
                        //满3进
                        if (stepCount[index]==3){
                            stepCount[index]=0;
                        }else{
                            willPlus = false;
                        }
                    }else{
                        //满4进
                        if (stepCount[index]==4){
                            stepCount[index]=0;
                        }else{
                            willPlus = false;
                        }
                    }
                }
            }
        }
    }
    

    写完跑了下,居然过了,差点被自己笑到。。。

    LeetCode刷题【863】二叉树中所有距离为K的结点

    给定一个二叉树(具有根结点 root), 一个目标结点 target ,和一个整数值 K

    返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

     

    示例 1:

    输入:root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
    输出:[7,4,1]
    解释:
    所求结点为与目标结点(值为 5)距离为 2 的结点,
    值分别为 7,4,以及 1
    
    
    
    注意,输入的 "root" 和 "target" 实际上是树上的结点。
    上面的输入仅仅是对这些对象进行了序列化描述。
    

     

    提示:

    1. 给定的树是非空的。
    2. 树上的每个结点都具有唯一的值 0 <= node.val <= 500 。
    3. 目标结点 target 是树上的结点。
    4. 0 <= K <= 1000.
    Related Topics
  • 深度优先搜索
  • 广度优先搜索
  • 二叉树
  • \n
  • 👍 289
  • 👎 0
  • 题解

    二叉树结构借助新增的map,经过dfs存下父节点信息转成图结构,然后再以target节点向外扩散,记下距离k即可

    
    
    //leetcode submit region begin(Prohibit modification and deletion)
    
    
    
    
    import java.util.*;
    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
    
        public void dfs(TreeNode node, TreeNode parent) {
                parentMap.put(node, parent);
                if (node.right!=null){
                    dfs(node.right, node);
                }
                if (node.left!=null){
                    dfs(node.left, node);
                }
        }
    
    
        Map<TreeNode, TreeNode> parentMap;
    
        private List<Integer> res = new ArrayList<>();
    
        public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
            parentMap = new HashMap<>();
            dfs(root, null);
            Queue<TreeNode> queue = new LinkedList<>();
            int distance = 0;
            queue.offer(target);
            int stepSize;
            Set<TreeNode> visited = new HashSet<>();
            //多加一个null进来,把没有父节点为null和子节点为null的判断条件都加进去
            visited.add(null);
            //target也加入,自身已经访问过
            visited.add(target);
            while (!queue.isEmpty()){
                //距离为0就是自身,所以,当从queue头部开始遍历的时候,distance是0
                if (distance==k){
                    //存结果
                    for (TreeNode node : queue) {
                        res.add(node.val);
                    }
                    //这边有个小坑,没注意被绕了好久,上面for循环不会从queue中poll,
                    // 然后继续进入while循环,形成死循环
                    return res;
                }else{
                    distance ++;
                    stepSize = queue.size();
                    //继续走下一步,往queue里塞父,左,右3个结点
                    for (int i = 0; i < stepSize; i++) {
                        TreeNode current = queue.poll();
                        if (!visited.contains(parentMap.get(current))){
                            queue.offer(parentMap.get(current));
                            visited.add(parentMap.get(current));
                        }
                        if (!visited.contains(current.left)){
                            queue.offer(current.left);
                            visited.add(current.left);
                        }
                        if (!visited.contains(current.right)){
                            queue.offer(current.right);
                            visited.add(current.right);
                        }
                    }
                }
    
            }
            return res;
        }
    
    
    }
    //leetcode submit region end(Prohibit modification and deletion)
    

    另外一个可行的思路,与target距离为K的点的集合分为两部分【target的子节点】和【非target的子节点】

    打个比方,【target的子节点】就是从target往下的第K层的节点。【非target的子节点】的则是【target的父节点下面,非target这侧往下第K-1层的节点】+【target的父节的父节点下面,非target父节点这侧往下第K-2层的节点】+……

    依次类推直到到达根节点

    
    import java.util.*;
    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
    
        public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
            parentMap = new HashMap<>();
            dfs(root, null);
            goToK(target,null,k,0);
            TreeNode parent = parentMap.get(target);
            TreeNode excludeTarget = target;
            int distance = 0;
            while (null!= parent){
                distance++;
                goToK(parent,excludeTarget,k,distance);
                excludeTarget = parent;
                parent = parentMap.get(parent);
            }
            return res;
        }
    
        private void goToK(TreeNode node, TreeNode excludeTarget, int k, int distance){
            if (node==null){
                return;
            }
            if (null!= excludeTarget && node.val==excludeTarget.val){
                return;
            }
            if (k==distance){
                res.add(node.val);
                return;
            }
            distance = distance+1;
            goToK(node.left,excludeTarget,k,distance);
            goToK(node.right,excludeTarget,k,distance);
        }
        
        
        public void dfs(TreeNode node, TreeNode parent) {
                parentMap.put(node, parent);
                if (node.right!=null){
                    dfs(node.right, node);
                }
                if (node.left!=null){
                    dfs(node.left, node);
                }
        }
    
    
        Map<TreeNode, TreeNode> parentMap;
    
        private List<Integer> res = new ArrayList<>();
    
    }
    //leetcode submit region end(Prohibit modification and deletion)

    LeetCode刷题【51】N皇后

    n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

    给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

    每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q''.' 分别代表了皇后和空位。

     

    示例 1:

    输入:n = 4
    输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
    解释:如上图所示,4 皇后问题存在两个不同的解法。
    

    示例 2:

    输入:n = 1
    输出:[["Q"]]
    

     

    提示:

    • 1 <= n <= 9
    • 皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。
    Related Topics
  • 数组
  • 回溯算法
  • \n
  • 👍 914
  • 👎 0
  • 题解

    里面加了个printMap方法,可以看到每一步执行的情况。

    大概的输出情况如下

    
    			o	o	o	o
    			o	o	o	o
    			o	o	o	o
    			o	o	o	o
    			-0--------------------
    			Q	.	.	.
    			.	.	o	o
    			.	o	.	o
    			.	o	o	.
    			-1--------------------
    			Q	.	.	.
    			.	.	Q	.
    			.	.	.	.
    			.	o	.	.
    			-2--------------------
    			Q	.	.	.
    			.	.	.	Q
    			.	o	.	.
    			.	.	o	.
    			-2--------------------
    			Q	.	.	.
    			.	.	.	Q
    			.	Q	.	.
    			.	.	.	.

    根据题意,和皇后棋的特性,米字型方向,长度无限的走法。那么我们可以得出一个初步的结论,要想在NxN的棋盘上放满N个皇后,那必然满足的条件是在每一行上有且只有一个皇后,在每一列上也是有且只有一个皇后。

    按照这个思路我们就在棋盘上,从左上角,第一个格子开始排起,分别求出下一行可能的情况,如果下一行上摆放不了任何一个皇后棋子,那说明这个摆放方法是不可行的,就必须回退上一步,尝试另一种摆放方法。并按照这个规则,直至最后一行也能放下一颗皇后棋子,则说明这种摆放方法是可行的。

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<String>> solveNQueens(int n) {
            char[][] availableMap = new char[n][n];
            for (int i = 0; i < n; i++) {
                char[] a = new char[n];
                //设为空 empty
                Arrays.fill(a,'o');
                availableMap[i] = a;
            }
            List<List<String>> res = new ArrayList<>();
            resolve(res,availableMap,0);
    //        System.out.println(res);
            return res;
        }
    
    //    private void printMap(char[][] originMap, int row){
    //        return;
    ////        for (char[] chars : originMap) {
    ////            StringBuilder str = new StringBuilder();
    ////            for (char aChar : chars) {
    ////                str.append("\t\t").append(aChar);
    ////            }
    ////            System.out.println(str);
    ////        }
    ////        System.out.println("-"+row+"--------------------");
    ////        System.out.println("");
    //    }
    
    
        private void resolve(List<List<String>> res,char[][] originMap,int row){
            // 根据特征,我们以第一行的情况开始,每一行必定有一个,且一定只有一个,
            // 不能满足这种情况的摆放方法,必然不能满足这种条件
            int n = originMap.length;
    //        printMap(originMap,row);
            for (int x = 0; x < n; x++){
                boolean rowInsertQ = false;
                //每一行,每一列的不同选择都会派生出不同的分支
                char[][] map = cloneCharArr(originMap);
                for (int i = 0; i < n; i++) {
                    if ( map[row][i] != 'o'){
                        continue;
                    }
                    if (i==x){
                        map[row][i] = 'Q';
                        rowInsertQ = true;
                        //那么对应的所有行上的第i列,和对应行上的斜线坐标格子 都是不可用状态,
                        for (int j = row+1; j < n; j++) {
                            map[j][i] = '.';
                            int left = i-(j-row);
                            int right = i+(j-row);
                            if (left >= 0 && map[j][left]=='o'){
                                map[j][left] = '.';
                            }
                            if (right <n && map[j][right]=='o'){
                                map[j][right] = '.';
                            }
                        }
                    }else{
                        map[row][i] = '.';
                    }
                }
                if (!rowInsertQ){
                    //这行不能插入新皇后,可以提前终止了
                    continue;
                }
                //有插入了新的皇后,可以向下一行探测,如果没有下一行则表示当前行已经是最后一行,那边添加进res中
                if (row<n-1){
                    resolve(res,map,row+1);
                }else{
                    toResult(res,map);
                }
            }
        }
    
        private char[][] cloneCharArr(char[][] map){
            char[][] temp = new char[map.length][map[0].length];
            for (int i = 0; i < map.length; i++) {
                System.arraycopy(map[i], 0, temp[i], 0, map[0].length);
            }
            return temp;
        }
    
        private void toResult(List<List<String>> res, char[][]arr){
            List<String> stringList = new ArrayList<>();
            for (char[] chars : arr) {
                stringList.add(new String(chars));
            }
            res.add(stringList);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
    Continue reading

    LeetCode刷题 【剑指 Offer 13】机器人的运动范围

    地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?

     

    示例 1:

    输入:m = 2, n = 3, k = 1
    输出:3
    

    示例 2:

    输入:m = 3, n = 1, k = 0
    输出:1
    

    提示:

    • 1 <= n,m <= 100
    • 0 <= k <= 20
  • 👍 302
  • 👎 0
  • 题解

    依旧广搜实现,从右上角开始,移动方向必然只能向右或者向下,再排除掉重复的部分

    
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Set;
    
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int movingCount(int m, int n, int k) {
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{0,0});
            boolean[][] checked = new boolean[m][n];
            checked[0][0] = true;
            int count = 1;
            while (!queue.isEmpty()){
                int[] current = queue.poll();
                int[] nextToX = getToX(current);
                if (nextToX[0] < m && nextToX[1] < n && !checked[nextToX[0]][nextToX[1]] && isReachedAble(nextToX,k)){
                    checked[nextToX[0]][nextToX[1]]= true;
                    queue.offer(nextToX);
                    count++;
                }
    
                int[] nextToY = getToY(current);
                if (nextToY[0] < m && nextToY[1] < n && !checked[nextToY[0]][nextToY[1]] && isReachedAble(nextToY,k)){
                    checked[nextToY[0]][nextToY[1]]= true;
                    count++;
                    queue.offer(nextToY);
                }
    
            }
            return count;
        }
    
        private boolean isReachedAble(int[] position, int k){
            int sum = getSum(position[0]) + getSum(position[1]);
            return sum <=k;
        }
    
        private int getSum(int num){
            int sum = 0;
            while (num > 9){
                sum += num % 10;
                num /= 10;
            }
            return sum + num;
        }
    
        private int[] getToX(int[] position){
            return new int[]{position[0]+1,position[1]};
        }
        private int[] getToY(int[] position){
            return new int[]{position[0],position[1]+1};
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    从矩阵的最终表现上来说,这题中小机器人的可行走范围是有规律的

    思路:判断vis[i][j]是否可达,如果可达返回1,反之返回0;判断i+j是否⼤于k,如果⼤于k,vis[i][j]则不可达。
    我们只需要向下和向右搜索,因此我们到达(i,j)的路线只能从(i-1,j)或(i,j-1)⾛过(不考虑边界)。那么我
    们就得出了这样⼀个公式:

    vis[i][j] = vis[i − 1][j] OR vis[i][j − 1]

    只要有⼀个格⼦可以到达那么(i,j)就能到达。因此我们只需要遍历所有格⼦然后去计算他们是否可达,同时记
    录可达的格⼦数量即可。

    放个代码实现如下

    class Solution {
        public int movingCount(int m, int n, int k) {
            if (k == 0) return 1;
            boolean[][] vis = new boolean[m][n];
            int ans = 1;
            vis[0][0] = true;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == 0 && j == 0 || get(i) + get(j) > k) continue;
                    if (i - 1 >= 0) vis[i][j] |= vis[i - 1][j];
                    if (j - 1 >= 0) vis[i][j] |= vis[i][j - 1];
                    ans += vis[i][j] ? 1 : 0;
                }
            }
            return ans;
        }
        public int get(int x) {
            int res = 0;
            while (x != 0) {
                res += x % 10;
                x /= 10;
            }
            return res;
        }
    }

    LeetCode刷题【752】打开转盘锁

    你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转:例如把 '9' 变为 '0''0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

    锁的初始数字为 '0000' ,一个代表四个拨轮的数字的字符串。

    列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。

    字符串 target 代表可以解锁的数字,你需要给出最小的旋转次数,如果无论如何不能解锁,返回 -1。

     

    示例 1:

    输入:deadends = ["0201","0101","0102","1212","2002"], target = "0202"
    输出:6
    解释:
    可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
    注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的,
    因为当拨动到 "0102" 时这个锁就会被锁定。
    

    示例 2:

    输入: deadends = ["8888"], target = "0009"
    输出:1
    解释:
    把最后一位反向旋转一次即可 "0000" -> "0009"。
    

    示例 3:

    输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
    输出:-1
    解释:
    无法旋转到目标数字且不被锁定。
    

    示例 4:

    输入: deadends = ["0000"], target = "8888"
    输出:-1
    

     

    提示:

    1. 死亡列表 deadends 的长度范围为 [1, 500]
    2. 目标数字 target 不会在 deadends 之中。
    3. 每个 deadendstarget 中的字符串的数字会在 10,000 个可能的情况 '0000''9999' 中产生。
    Related Topics
  • 广度优先搜索
  • \n
  • 👍 264
  • 👎 0
  • 题解

    照旧,还是广搜题

    先撸一版代码如下

    import java.util.*;
    
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int openLock(String[] deadEnds, String target) {
            if ("0000".equals(target)) {
                return 0;
            }
            HashSet<String> deadSets = new HashSet<>(Arrays.asList(deadEnds));
            if (deadSets.contains("0000")){
                return -1;
            }
            HashSet<String> visited = new HashSet<>();
            Queue<String> nextQueue = new LinkedList<>();
            nextQueue.offer("0000");
            char[] upArr = new char[4];
            char[] downArr = new char[4];
            String upStr = null;
            String downStr = null;
            int stepCount = 0;
            while (!nextQueue.isEmpty()){
                int stepSize = nextQueue.size();
                for (int s = 0; s < stepSize; s++) {
                    String current = nextQueue.poll();
                    if (current.equals(target)){
                        return stepCount;
                    }
                    char[] chars = current.toCharArray();
                    for (int i = 0; i < 4; i++) {
                        char numUp = getUp(chars[i]);
                        char numDown = getDown(chars[i]);
                        for (int i1 = 0; i1 < 4; i1++) {
                            if (i1==i){
                                upArr[i1] = numUp;
                                downArr[i1] = numDown;
                            }else{
                                upArr[i1] = chars[i1];
                                downArr[i1] = chars[i1];
                            }
                        }
                        upStr = new String(upArr);
                        downStr = new String(downArr);
                        if (!deadSets.contains(upStr) && !visited.contains(upStr)){
                            nextQueue.offer(upStr);
                            visited.add(upStr);
                        }
                        if (!deadSets.contains(downStr) && !visited.contains(downStr)){
                            nextQueue.offer(downStr);
                            visited.add(downStr);
                        }
                    }
                }
                stepCount++;
            }
            return -1;
        }
    
    
    
        private char getUp(char num){
            if (num==57){
                return 48;
            }
            return (char) (num+1);
        }
        private char getDown(char num){
            if (num==48){
                return 57;
            }
            return (char) (num-1);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    直接明了,单向广搜,getUp,getDown处理的是char字符编码0-9的编码为48到57,写的时候int和char的转换有点绕进去了,算是给自己挖了个小坑

    相对的,更进一步优化,在出发点和目标点都已经明确了的情况下,其实可以用双向广搜来实现,这样每一步完成双向两份的工作,提升效率。相对的,内存占用可能会更高点,也可以理解成空间换时间的操作。具体代码后续补下

    【油猴脚本】关于用油猴脚本爬取考试题库这件事

    公司每隔一段时间都有一些规范性的内容的考试,略头疼,有一点还行的是事先都提供了题库,于是本着自己动手丰衣足食的精神,用React写了个题库搜题的小Web应用

    搜题小应用倒是好写,这个省去不说。但是题库的录入就有点费事了,从一开始写搜题Web应用到最终这个脚本诞生,中间经历了几个阶段

    1.手动录入题目,费事费力,是个重体力活

    2.手机给题目截图,用图片的方式展示搜题结果,工作量依旧很大,一开始设想的是图片保存后接一个ORC服务,来实现关键文字信息提取,但是接入ORC服务这依旧是一个费力的过程,还不说ORC服务是否需要付费,和手机上截图的背景对准确性产生的影响

    3.在经历了前面两次考试之后,刷题背题的过程中才发现是页面文字是可以复制出来的,于是这一代的就开始了一题题的复制题目,存在手机备忘录,然后再在电脑上取得一整个所有题目的大又长的字符串,再做一些字符串解析的工作,解析之后就可以使用了。看起来不错,不过一题题的复制,依旧还是一个不轻松的工作,而且后面的字符串解析也实现起来有点点麻烦,各个字段,题目之间的分割特征不是很明显

    4.抓包软件的应用,在实现3的时候其实想到了可以使用抓包软件来实现,不过最终没有走上这一步,而且如果要实现这一步的话,最终每次接口请求的数据也都需要人工收集

    5.经过观察确定,这个题库本质其实是个web页面,那么既然是web页面了,必然还是可以在电脑上用浏览器打开的吧,假如服务端没有做一些特别的限制的话,经过几次尝试果然,确实可以打开,那么我们的油猴脚本就有大展身手的机会了

    基本思路:

    实现一个自己的XMLHttpRequest方法,替换掉window上原本的XMLHttpRequest方法,并对特定的事件进行记录,那么我们需要的数据也就水到渠成的可以截取下来。中间还用到了CustomEvent 。具体的就可以看下面代码了,从一开始的初始版本可以截取信息,到最终用起来顺手,还是经过了几个版本的迭代的

    // ==UserScript==
    // @name         题库小柯基(科技)
    // @namespace    http://tampermonkey.net/
    // @version      1.3
    // @description  try to take over the world!
    // @author       You
    // @match        https://xxxxxx.com?*
    // @grant        none
    // ==/UserScript==
    
    //需要存下来的数据
    window.list = [];
    //题库问题唯一编码列表.用来去重以防重复存储
    window.subjectCodeList = []
    //中断执行标记
    window.ifInterrupt = true
    //总页数
    let totalCount = () => document.getElementsByClassName("examNumbers")[0].children[3].innerText
    //当前页码
    let currentNum = () => document.getElementsByClassName("examNumbers")[0].children[1].innerText
    let isEnd = () => (currentNum() - 0) >= (totalCount() - 0)
    let clearList = () => {
        window.list = []
        window.subjectCodeList = []
    }
    let goNext = () => {
        window.ifInterrupt = false
        !isEnd() && document.getElementsByClassName('nextBtnClass')[0].click()
    }
    
    /**
     * 在页面上创建一个按钮,用来触发实现对应需要的功能
     * @param func
     * @param btnText
     * @param top
     */
    let createButton = (func, btnText, top) => {
        let btn = document.createElement("button")
        btn.style.position = "fixed"
        btn.style.right = 0
        btn.style.top = top
        btn.style.padding = "10px"
        btn.style.zIndex = 99999
        btn.innerText = btnText
        btn.addEventListener("click", func)
        document.body.append(btn)
    }
    
    createButton(clearList, "清除缓存", "120px")
    createButton(goNext, "开始抓取", "80px")
    createButton(() => window.ifInterrupt = true, "暂停", "160px")
    
    ;(function () {
        if (typeof window.CustomEvent === "function") return false;
    
        function CustomEvent(event, params) {
            params = params || {bubbles: false, cancelable: false, detail: undefined};
            let evt = document.createEvent('CustomEvent');
            evt.initCustomEvent(event, params.bubbles, params.cancelable, params.detail);
            return evt;
        }
    
        CustomEvent.prototype = window.Event.prototype;
        window.CustomEvent = CustomEvent;
    })();
    ;(function () {
        function ajaxEventTrigger(event) {
            let ajaxEvent = new CustomEvent(event, {detail: this});
            window.dispatchEvent(ajaxEvent);
        }
    
        let oldXHR = window.XMLHttpRequest;
    
        function newXHR() {
            let realXHR = new oldXHR();
            realXHR.addEventListener('abort', function () {
                ajaxEventTrigger.call(this, 'ajaxAbort');
            }, false);
            realXHR.addEventListener('error', function () {
                ajaxEventTrigger.call(this, 'ajaxError');
            }, false);
            realXHR.addEventListener('load', function () {
                ajaxEventTrigger.call(this, 'ajaxLoad');
            }, false);
            realXHR.addEventListener('loadstart', function () {
                ajaxEventTrigger.call(this, 'ajaxLoadStart');
            }, false);
            realXHR.addEventListener('progress', function () {
                ajaxEventTrigger.call(this, 'ajaxProgress');
            }, false);
            realXHR.addEventListener('timeout', function () {
                ajaxEventTrigger.call(this, 'ajaxTimeout');
            }, false);
            realXHR.addEventListener('loadend', function () {
                ajaxEventTrigger.call(this, 'ajaxLoadEnd');
            }, false);
            realXHR.addEventListener('readystatechange', function () {
                ajaxEventTrigger.call(this, 'ajaxReadyStateChange');
            }, false);
            let send = realXHR.send;
            realXHR.send = function (...arg) {
                send.apply(realXHR, arg);
                realXHR.body = arg[0];
                ajaxEventTrigger.call(realXHR, 'ajaxSend');
            }
            let open = realXHR.open;
            realXHR.open = function (...arg) {
                open.apply(realXHR, arg)
                realXHR.method = arg[0];
                realXHR.orignUrl = arg[1];
                realXHR.async = arg[2];
                ajaxEventTrigger.call(realXHR, 'ajaxOpen');
            }
            let setRequestHeader = realXHR.setRequestHeader;
            realXHR.requestHeader = {};
            realXHR.setRequestHeader = function (name, value) {
                realXHR.requestHeader[name] = value;
                setRequestHeader.call(realXHR, name, value)
            }
            return realXHR;
        }
    
        window.XMLHttpRequest = newXHR;
    
    })();
    window.addEventListener("ajaxReadyStateChange", function (e) {
        let xhr = e.detail;
        if (xhr.readyState == 4 && xhr.status == 200) {
            // xhr.getAllResponseHeaders()  响应头信息
            // xhr.requestHeader            请求头信息
            // xhr.responseURL              请求的地址
            // xhr.responseText             响应内容
            // xhr.orignUrl                 请求的原始参数地址
            // xhr.body                     post参数,(get参数在url上面)
            let url = xhr.orignUrl
            //只需关注我们需要的url,其他忽略
            if ("/url-witch-need-to-be-listen.json" == url) {
                //最终监听到的接口返回的信息
                let json = JSON.parse(xhr.responseText);
                let {subjectCode} = json
                if (window.subjectCodeList.includes(subjectCode)){
                    return
                }
                window.list.push(createQuestionItem(json))
                window.subjectCodeList.push(subjectCode)
                console.log(window.list)
                //判断是否到了最后一页,以及是否需要中断本次执行
                if (!window.ifInterrupt && !isEnd()) {
                    //随机一个5秒内的时间,点击下一页按钮的操作。触发下一次请求
                    setTimeout(() => {
                        document.getElementsByClassName('nextBtnClass').length &&
                        document.getElementsByClassName('nextBtnClass')[0].click()
                    }, Math.random() * 5000)
                }
                if (isEnd()) {
                    console.warn("结束啦")
                    //最终创建一个新的window展示抓取下来的内容,方便后续录入题库操作
                    let newWindow = window.open('', '获取结果', 'height=300,width=400,top=0,left=0,toolbar=no,menubar=no,scrollbars=no,resizable=no,location=no,status=no')
                    newWindow.document.body.innerText = JSON.stringify(window.list)
                }
            }
        }
    });
    
    let createQuestionItem = ( questionInfo ) => {
        let type, question, answerArr, answer, desc;
        return { type, question, answerArr, answer, desc, questionInfo }
    }
    

    LeetCode刷题【1091】二进制矩阵中的最短路径

    给你一个 n x n 的二进制矩阵 grid 中,返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径,返回 -1

    二进制矩阵中的 畅通路径 是一条从 左上角 单元格(即,(0, 0))到 右下角 单元格(即,(n - 1, n - 1))的路径,该路径同时满足下述要求:

    • 路径途经的所有单元格都的值都是 0
    • 路径中所有相邻的单元格应当在 8 个方向之一 上连通(即,相邻两单元之间彼此不同且共享一条边或者一个角)。

    畅通路径的长度 是该路径途经的单元格总数。

     

    示例 1:

    输入:grid = [[0,1],[1,0]]
    输出:2
    

    示例 2:

    输入:grid = [[0,0,0],[1,1,0],[1,1,0]]
    输出:4
    

    示例 3:

    输入:grid = [[1,0,0],[1,1,0],[1,1,0]]
    输出:-1
    

     

    提示:

    • n == grid.length
    • n == grid[i].length
    • 1 <= n <= 100
    • grid[i][j]01
    Related Topics
  • 广度优先搜索
  • \n
  • 👍 105
  • 👎 0
  • 题解

    广度优先搜索基本应用,本来想着加一个变量保存当前走的步数,具体写起来的时候发现实现起来略复杂,需要记录每一轮的可选步数的数量,然后根据queue中的数量判断当前走到第几布

    稍微想了下,换个思路,把指定格子的走到的步数就记在格子上,这个值就表示了,到这个格子的最短步数,同时也标识了这个格子已经走过了,在后面的步骤的时候避免重新走回这个格子里

    
    import java.util.LinkedList;
    import java.util.Queue;
    
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private int[][] dist = { {0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1} };
    
        public int shortestPathBinaryMatrix(int[][] grid) {
            int[] start = {0,0};
            int[] target = {grid[0].length-1,grid.length-1};
            if (grid[start[0]][start[1]] !=0 || grid[target[0]][target[1]]!=0 ){
                return -1;
            }
            Queue<int[]> queue = new LinkedList<int[]>();
            queue.offer(start);
            grid[0][0]=1;
            while (!queue.isEmpty()){
                int[] currentPosition = queue.poll();
                if (currentPosition[0]==target[0] && currentPosition[1]== target[1]){
                    //抵达终点
                    return grid[currentPosition[0]][currentPosition[1]];
                }
                //广搜基本思路,在每一轮不断的循环中,找出下一轮能可能项,加进待处理队列中
                for (int[] ints : dist) {
                    int[] nextStep = {currentPosition[0]+ints[0],currentPosition[1]+ints[1]};
                    if (nextStep[0]<0 || nextStep[1]<0 || nextStep[0] > target[0] || nextStep[1] > target[1]){
                        continue;
                    }
                    if (grid[nextStep[0]][nextStep[1]] != 0){
                        continue;
                    }
                    queue.offer(nextStep);
                    grid[nextStep[0]][nextStep[1]] = grid[currentPosition[0]][currentPosition[1]]+1;
                }
    
            }
            return -1;
    
        }
    }