做网站公司好做吗,惠州私人做网站联系人,wordpress文章插广告,郑州企业网站优化公司648. 单词替换(中等)
思路#xff1a;前缀树匹配
// 思路#xff1a;前缀树匹配#xff0c;成功返回前缀#xff0c;失败返回 null#xff0c;保留原来单词值
// 多个词根时使用最短词根#xff0c;不需要 fail 指针
// string 处理使用 stringBuilder#xff0c;避…648. 单词替换(中等)
思路前缀树匹配
// 思路前缀树匹配成功返回前缀失败返回 null保留原来单词值
// 多个词根时使用最短词根不需要 fail 指针
// string 处理使用 stringBuilder避免 string 运算带来过大开销
class Solution {class Node{public Node[] children;public boolean isEnd;public String word;public Node (){children new Node[26];isEnd false;word null;}}class TrieTree {public Node root;public TrieTree(){root new Node();}public void insert(String word){Node current root;for(char c : word.toCharArray()){Node temp current.children[c-a];if(tempnull){temp new Node();current.children[c-a] temp;}current temp;}current.isEnd true;current.word word;}public String match(String word){Node current root;for(char c :word.toCharArray()){Node temp current.children[c-a];if(tempnull){return current.word;}if(temp.isEnd){return temp.word;}current temp;}return current.word;}}public String replaceWords(ListString dictionary, String sentence) {TrieTree tree new TrieTree();for(String w:dictionary){tree.insert(w);}StringBuilder res new StringBuilder();StringBuilder tempWord new StringBuilder();sentence ;for(char c:sentence.toCharArray()){if(c tempWord.length()!0){String temp tempWord.toString();tempWord.setLength(0);String match tree.match(temp);res.append(matchnull?temp:match);res.append( );}else {tempWord.append(c);}}res.deleteCharAt(res.length()-1);return res.toString();}
}662. 二叉树最大宽度(中等)
问题一开始没有仔细审题犯大忌 // 思路层序遍历带 for 循环的层序遍历另开节点存储完全二叉树的 id
class Solution {class Node{public TreeNode tn;public int id;public Node(TreeNode treeNode,int i){tn treeNode;id i;}}public int widthOfBinaryTree(TreeNode root) {QueueNode queue new LinkedList();queue.offer(new Node(root,1));int max 1;while(queue.size()0){int len queue.size();int first 0,last 0;for(int i0;ilen;i){Node temp queue.poll();if(temp.tn.left!null){if(first0)first temp.id*2;queue.offer(new Node(temp.tn.left,temp.id*2));last temp.id*2;}if(temp.tn.right!null){if(first0)first temp.id*21;queue.offer(new Node(temp.tn.right,temp.id*21));last temp.id*21;}if(last-first1max)max last-first1;}}return max;}
}1631. 最小体力消耗路径(中等)
思路
一开始考虑到路径是全局最优贪心可能不行就没有考虑使用 BFS直接DFS然后超时又考虑记忆化搜索剪枝还是超时可能没有优化好最后看了一眼题解原来可以用 dij就思考 dij 关键点在于 visit 这个节点的时候一定要保证这个节点是最优距离不能再被更新成更好的不然以他为起点搜索的都白费了。所以采用优先队列选择每次只选择最优的节点去处理如果按照传统的 dij 方法搜索距离最短且 visit 为 false的节点需要 m*n 遍历节点太慢采用了优先队列采用优先队列有个问题就是每次更新了一个节点的距离值这个节点会再次入队但是出队的时候一定是最优解先出来。但是后续的非最优解也会出队接受 visit这里就需要判断访问过就不要再访问了。同时优先队列的 Compator 方法不能把外部变量作为比较值外部变量变化会导致排序出问题
class Solution {public int minimumEffortPath(int[][] heights) {int n heights.length;int m heights[0].length;int length[][] new int[n][m];int direct[][] new int[][]{{1,0},{0,1},{-1,0},{0,-1}};Queueint[] pq new PriorityQueue(Comparator.comparingInt(o - o[2]));boolean visit[][] new boolean[n][m];for(int i0;in;i)for(int j0;jm;j)length[i][j] 1000001;length[0][0] 0;pq.offer(new int[]{0,0});while(!pq.isEmpty()){int[] point pq.poll();if(visit[point[0]][point[1]]) continue;visit[point[0]][point[1]] true;for (int i0;i4;i){int tx point[0] direct[i][0];int ty point[1] direct[i][1];if(tx0||txn||ty0||tym||visit[tx][ty])continue;int difference Math.abs(heights[point[0]][point[1]]-heights[tx][ty]);int tp Math.max(length[point[0]][point[1]],difference);if(tplength[tx][ty]){length[tx][ty] tp;pq.offer(new int[]{tx,ty,tp});}}}return length[n-1][m-1];}
}
