每日一题

1. 2022-05-18：假设数组a和数组b为两组信号：
   length(b) <= length(a)；
   对于任意0<=i<length(b), 有b[i+1] - b[i] == a[i+1] - a[i]。
   那么就称信号b和信号a一致，记为b==a，
   给你好多b数组，假设有m个: b0数组、b1数组…
   给你好多a数组，假设有n个: a0数组、a1数组…
   返回一个长度为m的结果数组ans，ans[i]表示 : bi数组和多少个a数组一致。
   来自字节飞书团队。
   ————————————————
   版权声明：本文为CSDN博主「福大大架构师每日一题」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
   原文链接：https://blog.csdn.net/weixin_48502062/article/details/124849363

public int[] sameTeamsArray(int[][] bs,int[][] as){        //预测 循环比较        //预测 新建一个类        //预测        //b数组的长度        int m = bs.length;        //新建节点        TrieNode root = new TrieNode();        //新建当前节点        TrieNode cur = null;        //循环b数组        for (int i=0;i<m;i++){            //获取其中子数组的长度            int k = bs[i].length;            //将root节点给当前节点            cur = root;            //循环其中的其中一个子数组            for (int j=1;j<k;j++){                //俩个元素的差值                int diff = bs[i][j] - bs[i][j-1];                //预判 当前节点不包含这个差值                if (!cur.nexts.containsKey(diff)){                     //将当前的差值给放入下一节点中                     cur.nexts.put(diff,new TrieNode());                }                //预判 当前的节点包含这个差值                //当前节点切换                cur = cur.nexts.get(diff);            }            //当前节点集合放入当前节点            cur.indices.add(i);        }        //新建返回数组        int[] ans = new int[m];        //定义a数组的长度        int n = as.length;        //循环a数组        for (int i=0;i<n;i++){            //其中一个子数组的长度            int k = as[i].length;            //定义当前节点            cur = root;            //循环其中的一个子数组            for (int j=1;j<k;j++){                //计算差值                int diff = as[i][j] - as[i][j-1];                //预判 当前节点不包含这个差值                if (!cur.nexts.containsKey(diff)){                    //这个子数组不行                    break;                }                //预判 是有这个节点的                cur = cur.nexts.get(diff);                //循环这个节点里面的b下标列表                for (int index : cur.indices) {                    ans[index]++;                }            }        }        return ans;    }    //新建前缀树节点    class TrieNode{        //新建列表        public ArrayList<Integer> indices;        //新建关系表        public HashMap<Integer, TrieNode> nexts;        //初始化        public TrieNode(){            indices = new ArrayList<>();            nexts = new HashMap<>();        }    }

1. 前缀树