一道面试题,求解

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

外包信息请发到 /go/outsourcing 节点。

不要把相同的信息发到不同的节点

这是一个创建于 2755 天前的主题，其中的信息可能已经有所发展或是发生改变。

已知有这么一个数组

$a = array( 'a' => 1, 'b.b.c' => 2, 'b.b.d' => 3, 'b.b.e' => 4, 'f.g' => 5, );

处理后变为

$b = array( 'a' => 1, 'b' => array( 'b' => array( 'c' => 2, 'd' => 3, 'e' => 4, ), ), 'f' => array( 'g' => 5, ), );

请问该怎么处理,给点思路,谢谢

array

数组

求解

处理

10 条回复 2018-04-17 13:51:29 +08:00

namedfish

2018-04-03 00:05:13 +08:00 via iPhone

这结构看起来就像前缀树

johnhsm2333

2018-04-03 00:38:24 +08:00 via Android

单词查找树

blodside

2018-04-03 02:45:58 +08:00 via Android

字典树啊

4357

2018-04-03 07:22:47 +08:00

楼上的回答都不靠谱
简单的做法，遍历原来的 map 的 key，用'.'切分成字符串数组，然后遍历这个数组，一层层建立 map

shenqi

2018-04-03 09:39:05 +08:00

看不懂，为啥数组还给 key，如果是对象，直接用 lodash.set 算不算作弊。

yunfeifan

2018-04-03 09:45:39 +08:00

姑且认为你给的是个 map 吧！仅供参考一下！
var test_arr = {
'a': 1,
'b.b.c': 2,
'b.b.d': 3,
'b.b.e': 4,
'f.g': 5
}

expandArr = (arr) => {
let res = {};
let expand = (item, value) => {
let paths = item.split('.');
if (paths.length > 1) {
setChild(res, paths, value);
} else {
res[paths[0]] = value;
}
}
let setChild = (obj, paths, value) => {
if (paths.length === 0) {
return;
}
if (paths.length === 1) {
obj[paths] = value;
} else {
if (!(paths[0] in obj)) {
obj[paths[0]] = {};
}
setChild(obj[paths[0]], paths.slice(1,), value);
}
}
for(let item of Object.keys(arr)){
expand(item, arr[item]);
}
return res;
}

expandArr(test_arr)

enenaaa

2018-04-03 11:13:05 +08:00

直接写呗还能怎么处理

shenhhd

2018-04-03 12:33:52 +08:00

看语法有点像是 php 啊

$a = array(
'a' => 1,
'b.b.c' => 2,
'b.b.d' => 3,
'b.b.e' => 4,
'f.g' => 5,
);

$newarray=[];
foreach($a as $k =>$value){
$keys = explode('.',$k);
$a=$value;
$keys = array_reverse($keys);
foreach($keys as $v){
$a=[$v=>$a];
}

my_merge($newarray,$a);

}

function my_merge(&$a,$b){

foreach($a as $key=>&$val){
if(is_array($val) && array_key_exists($key, $b) && is_array($b[$key])){
my_merge($val,$b[$key]);
$val = $val + $b[$key];
}else if(is_array($val) || (array_key_exists($key, $b) && is_array($b[$key]))){
$val = is_array($val)?$val:$b[$key];
}
}
$a = $a + $b;
}

print_r($newarray);

dan2001go

2018-04-03 14:37:48 +08:00

早上看了一下，本来想写的，结果时间来不及，要赶着去面试。。
回来一看已经有人解答了，我写到一半，也贴出来吧，这个就是 PHP 了。
思路都差不多，用递归的方式求解。这块水平好差。。有一次面试直接让我机试，心里紧张，磨了半天当场写不出来，估计别人觉得我水平太 LOW 了。

<?php

date_default_timezone_set('Asia/Shanghai');

$a = array(
'a' => 1,
'b.b.c' => 2,
'b.b.d' => 3,
'b.b.e' => 4,
'f.g' => 5,
'b.q.e' => 6,
);

$obj = array();

foreach($a as $k=>$v){
$tree = explode('.',$k);
if(count($tree)>1){
$index = 1;
if(!isset($obj[$tree[0]])){
$obj[$tree[0]] = array();
}
loop($obj[$tree[0]],$tree,$index,$v);
}else{
$obj[$k] = $v;
}
}

function loop(&$obj,$src,$index,$value){

if($index == count($src)){
return false;
}
if($index == count($src)-1){
$tmp = $value;
}else{
$tmp = null;
}
$add = false;
if(!is_null($obj)){
if(array_key_exists($src[$index],$obj) === true){
$add = true;
}
}

if($add != true){
$obj[$src[$index]] = $tmp;
}

$offset = $src[$index];
$index++;
loop($obj[$offset],$src,$index,$value);
}

var_dump($obj);

JackZong

2018-04-17 13:51:29 +08:00

@shenqi PHP