一道面试题,求解

V2EX = way to explore

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

现在注册

已注册用户请登录

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

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

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

已知有这么一个数组

$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