上海做淘宝网站设计,西安百度推广外包,wordpress怎么改登陆,营销运营平台题目描述现在#xff0c;我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。使用三元组表示金字塔的堆砌规则如下#xff1a;对于三元组(A, B, C) #xff0c;“C”为顶层方块#xff0c;方块“A”、“B”分别作为方块“C”下一层的的左、右子块。当…题目描述现在我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。使用三元组表示金字塔的堆砌规则如下对于三元组(A, B, C) “C”为顶层方块方块“A”、“B”分别作为方块“C”下一层的的左、右子块。当且仅当(A, B, C)是被允许的三元组我们才可以将其堆砌上。初始时给定金字塔的基层 bottom用一个字符串表示。一个允许的三元组列表 allowed每个三元组用一个长度为 3 的字符串表示。如果可以由基层一直堆到塔尖就返回 true 否则返回 false 。示例1输入bottom “BCD”, allowed [“BCG”, “CDE”, “GEA”, “FFF”] 输出true 解析 可以堆砌成这样的金字塔: A / G E / \ / B C D 因为符合(‘B’, ‘C’, ‘G’), (‘C’, ‘D’, ‘E’) 和 (‘G’, ‘E’, ‘A’) 三种规则。示例2输入bottom “AABA”, allowed [“AAA”, “AAB”, “ABA”, “ABB”, “BAC”] 输出false 解析 无法一直堆到塔尖。 注意, 允许存在像 (A, B, C) 和 (A, B, D) 这样的三元组其中 C ! D。这个题个人感觉难度应该不算中等 属于看题解看半天都不是很懂的那种可能我太菜了QAQ 最开始看着示例结构 想用创建赫夫曼树的方法试一下忽略了最重要的一点一个子节点可以拥有多个父节点 所以才想到用dfs遍历每一种可能的情况 代码和思路如下// 思路// 判断是否可以堆砌成金字塔取决于是否可以达到塔顶只有一个数组// 注意1可能存在两个字母可以组合成多种字母的情况 所以考虑用Map映射来保存规则// 注意2: 和二叉树不同 一个节点可能有两个父节点排除赫夫曼树做法class Solution {public boolean pyramidTransition(String bottom, List allowed) {if(allowed.size() 0) return false;Map map getMap(allowed);// System.out.println(map);return dfs(map, bottom, );}/*参数说明*map 映射表*boom 当前构建层的基层*up 构建层*/public boolean dfs(Map map, String boom, String up) {if(up.length() 1 boom.length() 2) return true; // 完成最后一层构建if(up.length() boom.length() - 1) return dfs(map, up, ); // 开始构建下一层int start up.length();int end start 2;List values map.get(boom.substring(start, end));if(values null) { // 没有映射关系 当前两节点构造失败return false;}for(int i 0; i values.size(); i) {if(dfs(map, boom, up values.get(i))) return true; // 试探每一种父节点的可能性直到找到可以完整构建一行的}return false;}public Map getMap(List allowed) { // 转换映射Map map new HashMap(); // 用String比Char方便 所以选择Listfor(String s : allowed) {String key s.substring(0, 2); // 截取左右子块作为键String value s.substring(2,3);if(map.containsKey(key)) {map.get(key).add(value);} else {List values new ArrayList();values.add(value);map.put(key, values);}}return map;}}
