脚本宝典收集整理的这篇文章主要介绍了677-键值映射(Map Sum Pairs),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
前言
前缀树同系列的题目,可以用前缀树的思路来存储,只需要基于之前的前缀树实现改造。原题目要求如下:
实现一个 MapSum 类里的两个方法,insert 和 sum。对于方法 insert,你将得到一对(字符串,整数)的键值对。字符串表示键,整数表示值。如果键已经存在,那么原来的键值对将被替代成新的键值对。
对于方法 sum,你将得到一个表示前缀的字符串,你需要返回所有以该前缀开头的键的值的总和。
示例 1:
输入: insert("apple", 3), 输出: Null
输入: sum("ap"), 输出: 3
输入: insert("app", 2), 输出: Null
输入: sum("ap"), 输出: 5
实现思路
实例代码
public class MapSum {
/**
* key的前缀字符
*/
char keyPrefix;
/**
* 子节点
*/
MapSum[] children;
/**
* 存储的值,不为0则为终止节点
*/
int value;
/** Initialize your data structure here. */
public MapSum() {
children=new MapSum[26];
value=0;
}
/**
* 字符串表示键,整数表示值。如果键已经存在,那么原来的键值对将被替代成新的键值对。
* @param key 键
* @param val 值
*/
public void insert(String key, int val) {
if(key!=null){
//分解成字符数组
char[] charArr=key.toCharArray();
//模拟指针操作,记录当前访问到的树的节点
MapSum currentNode=this;
for(int i=0;i<charArr.length;i++){
char currentChar=charArr[i];
//根据字符获取对应的子节点
MapSum node=currentNode.children[currentChar-97];
if(node!=null && node.keyPrefix==currentChar){//判断节点是否存在
currentNode=node;
}else{//不存在则创建一个新的叶子节点,并指向当前的叶子节点
node=new MapSum();
node.keyPrefix=currentChar;
currentNode.children[currentChar-97]=node;
currentNode=node;
}
}
//存储值
currentNode.value=val;
}else{
this.value=val;
}
}
/**
* 根据表示前缀的字符串,返回所有以该前缀开头的键的值的总和。
* @param prefix 前缀
* @return
*/
public int sum(String prefix) {
int result=0;
//前缀是否匹配
boolean match=true;
if(prefix!=null && !prefix.trim().equals("")){
char[] prefixChar=prefix.toCharArray();
MapSum currentNode=this;
for(int i=0;i<prefixChar.length;i++){
char currentChar=prefixChar[i];
MapSum node=currentNode.children[currentChar-97];
if(node!=null && node.keyPrefix==currentChar){//判断节点是否存在
currentNode=node;
}else{
match=false;
break;
}
}
if(match){//前缀匹配后开始检索这个匹配节点后续的子树
result=sumByFloor(currentNode);
}
}
return result;
}
/**
* 层序遍历(广度优先)方式访问树
* @param mapSum
* @return
*/
private int sumByFloor(MapSum mapSum){
int result=0;
if(mapSum==null){
return 0;
}else{
result+=mapSum.value;
MapSum[] mapSums=mapSum.children;
for(MapSum sum:mapSums){
if(sum!=null){
result+=sumByFloor(sum);
}else{
result+=sumByFloor(sum);
}
}
}
return result;
}
}
以上是脚本宝典为你收集整理的677-键值映射(Map Sum Pairs)全部内容,希望文章能够帮你解决677-键值映射(Map Sum Pairs)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。