Java 转行,目前加起来 Java 开发经验一年多一点,HR 给我发了两道题,第一道是具有层级关系的城市,例如"中国 广州","中国 浙江 杭州" 一个 List 最后应该是转成树状图输出,最后还是没答完,后面去 leetcode 上看了一下,应该是属于 hard 难度的。想到前景越来越黯淡,emo 了。而且面的是外包,面试官都没见到。
1
unregister OP 上家公司项目很简单,主要就是 crud 。
|
2
corningsun 2022-02-09 22:36:21 +08:00 via iPhone
这不是 hard 吧,构造 一个 tree 对象就行了
|
3
rabbbit 2022-02-09 22:38:06 +08:00
原题是啥?看描述不是很难...
|
4
unregister OP @rabbbit 就是有多个具有层级关系的城市对,比如"中国 浙江 杭州”,"中国“,"中国 广东","中国 广东 广州 越秀区”这样的 list 。把他转成树状结构的行政区树,以 Json 的形式输出。
|
5
ufan0 2022-02-09 22:43:42 +08:00
这个描述让我想到了百家互联,校招终面给的算法题描述的还不如你说的,输入值是一大串 json 。
我:输入值是已经定义的数据结构还是啥? 面试官:你没见过 json 吗? 我:可以使用 json 解析工具吗? 面试官:这是白板,如果你确定你能引入包,随便你用。 然后我就挂了...... |
6
whileFalse 2022-02-09 22:44:22 +08:00 5
这……很难吗……
|
7
unregister OP @corningsun 嗯,但是对递归这个概念理解的不是很清晰,树的数据结构了解的不是很透彻,具体实现起来还是有一定难度,主要是题目一开始没明白,后面我的思路始,取每一个 item 的最后两位,存入一个 map 。然后每一个节点里面有一个 List 子节点。
|
8
unregister OP @whileFalse 297. 二叉树的序列化与反序列化 我看这里面的难度是困难。他的题目比较烦我觉得。
|
9
unregister OP @ufan0 是的,提供的输入数据,这些城市对都不加双引号的,之间逗号也没有,就是空格。我问她,她说不是我作答,我觉得这道题也没有什么意义,正常行政区树直接查父级的行政区编号就行了吗?
|
10
sagaxu 2022-02-09 23:03:06 +08:00 1
这就是最简单的递归啊,十多年前 PHP 面试官们把这个叫做“无限分类”,“无限菜单”
|
11
jmc891205 2022-02-09 23:04:12 +08:00
构造一个 trie ?
|
12
unregister OP @sagaxu 嗯,他没有 pid,id 只有行政区的名称,而且那个像这样的数据 中国 广东 广州 越秀区 感觉还要自己处理获取 parentName, name.不过吃一堑长一智。
|
13
az467 2022-02-09 23:17:45 +08:00 1
再怎么卷外包也不会一面 hard 吧
|
14
Keyi 2022-02-09 23:23:33 +08:00 via Android 1
我看这个描述,应该是想要按照空格拆开转成 Map 嵌套?
|
15
interim 2022-02-09 23:53:13 +08:00 1
递归可解,Java 再怎么卷,外包也不至于 hard 难度连面试都没把...
|
16
rabbbit 2022-02-09 23:55:50 +08:00
试着写了一下,不知道是不是这个意思.
我前端,写的可能有些丑... import java.util.*; public class App { public static Map<String, Map> map; public static void main(String[] args) { map = new HashMap(); String[] cityList = {"中国 浙江 杭州","中国","中国 广东", "中国 广东 广州 越秀区"}; for (String cityStr: cityList) { String[] itemList = cityStr.split(" "); if(itemList.length > 0) { addMap(itemList[0], map); } if(itemList.length > 1) { for (int i = 1; i < itemList.length; i++) { String beforeKey = itemList[i - 1]; String key = itemList[i]; Map mapOfBeforeKey = addMap(beforeKey, map); Map mapOfKey = addMap(key, map); if(!mapOfBeforeKey.containsKey(key)) { mapOfBeforeKey.put(key, mapOfKey); } } } } for(String key: (ArrayList<String>)new ArrayList(map.keySet())) { if(!key.equals("中国")) { map.remove(key); } } System.out.println(toJSON(map, 2)); } public static Map<String, Map> addMap(String key,Map<String, Map> map ) { if(!map.containsKey(key)) { map.put(key, new HashMap<String, Map>()); } return map.get(key); } public static String toJSON(Map<String, Map> map, int intend) { String str = "{"; List<String> keys = new ArrayList(map.keySet()); if( keys.size() > 0) { str += "\r\n"; } for (int i = 0; i < keys.size(); i++) { str += "\r\n" + geneSpace(intend); String key = keys.get(i); str += geneSpace(intend) + key + ": " + toJSON(map.get(key), intend + 2); if(i < keys.size() - 1) { str += ","; } str += "\r\n"; } if( keys.size() > 0) { str += geneSpace(intend); } str += "}"; return str; } public static String geneSpace(int len) { return new String(new char[len]).replace('\0', ' '); } } |
17
rabbbit 2022-02-09 23:59:35 +08:00
唔,好像不太对.
|
18
rabbbit 2022-02-10 00:05:14 +08:00 1
这回对了
import java.util.*; public class App { public static Map<String, Map> map; public static void main(String[] args) { map = new HashMap(); String[] cityList = {"中国 浙江 杭州","中国","中国 广东", "中国 广东 广州 越秀区"}; for (String cityStr: cityList) { String[] itemList = cityStr.split(" "); if(itemList.length > 0) { addMap(itemList[0], map); } if(itemList.length > 1) { for (int i = 1; i < itemList.length; i++) { String beforeKey = itemList[i - 1]; String key = itemList[i]; Map mapOfBeforeKey = addMap(beforeKey, map); Map mapOfKey = addMap(key, map); if(!mapOfBeforeKey.containsKey(key)) { mapOfBeforeKey.put(key, mapOfKey); } } } } for(String key: (ArrayList<String>)new ArrayList(map.keySet())) { if(!key.equals("中国")) { map.remove(key); } } System.out.println(toJSON(map, 0)); } public static Map<String, Map> addMap(String key,Map<String, Map> map ) { if(!map.containsKey(key)) { map.put(key, new HashMap<String, Map>()); } return map.get(key); } public static String toJSON(Map<String, Map> map, int intend) { String str = "{"; List<String> keys = new ArrayList(map.keySet()); if( keys.size() > 0) { str += "\r\n"; } for (int i = 0; i < keys.size(); i++) { String key = keys.get(i); str += geneSpace(intend + 2) + key + ": " + toJSON(map.get(key), intend + 2); if(i < keys.size() - 1) { str += ","; } str += "\r\n"; } if( keys.size() > 0) { str += geneSpace(intend); } str += "}"; return str; } public static String geneSpace(int len) { return new String(new char[len]).replace('\0', ' '); } } 输出 { 中国: { 广东: { 广州: { 越秀区: {} } }, 浙江: { 杭州: {} } } } |
19
rabbbit 2022-02-10 00:39:55 +08:00
想到个问题,要是有不同省市地下有重名的就坏了,所以还是不对...
|
21
xiadong1994 2022-02-10 02:12:13 +08:00 via iPhone
@unregister 序列化与反序列化是 hard 是因为给的输入是遍历的结果,你的这道题给的是从 root 到某一个 node 的 path ,提供了更多的 tree 结构信息,顶多是个 medium 。
|
22
msg7086 2022-02-10 06:56:36 +08:00 1
撑死 medium ,我觉得算 easy 都可以。
如果不懂递归,那至少懂面向对象吧。 自己建一个类 Region ,然后类成员 List<Region> subRegions ,类方法 append(String fullRegionPath),把字符串的第一段切出来添加进 subRegions ,然后把剩下的交给 subRegion.append()不就行了。 如果我是面试官,我更希望面试者用面向对象的方法去实现递归,而不是像上面一位老哥那样开个 for 循环去搞。 |
23
kran 2022-02-10 08:23:53 +08:00 via Android
map+引用,单次循环就可以了
|
24
VeryZero 2022-02-10 09:00:58 +08:00
这就是最基本的递归啊,而且工作中很常用。比如分类树,目录树
|
25
fpure 2022-02-10 09:39:04 +08:00
@unregister 这个题我觉得递归都可以不用吧
|
26
Junzhou 2022-02-10 09:44:32 +08:00
@unregister 这个感觉没想象中的麻烦,可能力扣中等难度? 遍历这个列表,拿到每一条记录,通过字符分割,中国 广东 广州 越秀 ,拿到四个不同级别的行政区,然后处理下一个,中国 广东 深圳 南山 广东已经存在了,直接把深圳加入到广东的子节点,南山加到深圳的子节点,如果是 中国 广东 深圳 宝安 根据中国找到广东,找到深圳,宝安不存在,将宝安加入到深圳的子节点。以此类推?
|
28
illuz 2022-02-10 09:46:45 +08:00 via Android
水题,老哥多刷刷算法吧
这种树状结构工程里还是挺常见的,这就 emo 说明水平一般 |
29
fpure 2022-02-10 10:10:11 +08:00
package com.example;
import java.util.Arrays; import java.util.HashMap; import java.util.List; import com.google.gson.GsonBuilder; public class x { @SuppressWarnings("unchecked") public static void main(String[] args) { List<String> list = Arrays.asList("中国 广州", "中国 浙江 杭州"); HashMap<String, Object> root = new HashMap<>(); for (String s : list) { HashMap<String, Object> node = root; String[] ss = s.split(" "); for (int i = 0; i < ss.length; i++) { HashMap<String, Object> subNode = (HashMap<String, Object>) node.get(ss[i]); if (subNode == null) { subNode = new HashMap<>(); node.put(ss[i], subNode); } node = subNode; } } System.out.println(new GsonBuilder() .setPrettyPrinting() .serializeNulls() .create().toJson(root)); } } |
30
Vegetable 2022-02-10 10:16:00 +08:00
这是 hard 吗...
|
31
OldCarMan 2022-02-10 10:23:11 +08:00 1
@unregister #8 不知道我有没有理解错,这道题最终目的是以树状结构的 json 数据输出,而不是中间一定要套上树这种数据结构,如果是这样的话,直接用 map 多层嵌套+递归和判断 就行了,个人觉得(暗中观察够🐶)。
|
32
dqzcwxb 2022-02-10 11:05:24 +08:00 1
所有的递归都可以写成循环 |
33
rabbbit 2022-02-10 11:06:30 +08:00
@Junzhou 呃,我是说我写的那个不对啦.
昨天太晚了,改成这样就好了. import java.util.*; public class App { public static void main(String[] args) { Map<String, Map> map = new HashMap(); String[] cityList = {"中国 浙江 杭州","中国","中国 广东", "中国 广东 广州 越秀区", "中国 达拉崩吧 广州"}; for (String cityStr: cityList) { Map<String, Map> parentMap = map; for (String key: cityStr.split(" ")) { Map mapOfKey = addMap(key, parentMap); parentMap = mapOfKey; } } System.out.println(toJSON(map, 0)); } public static Map<String, Map> addMap(String key,Map<String, Map> map ) { if(!map.containsKey(key)) { map.put(key, new HashMap<String, Map>()); } return map.get(key); } public static String toJSON(Map<String, Map> map, int intend) { String str = "{"; List<String> keys = new ArrayList(map.keySet()); if( keys.size() > 0) { str += "\r\n"; } for (int i = 0; i < keys.size(); i++) { String key = keys.get(i); str += geneSpace(intend + 2) + key + ": " + toJSON(map.get(key), intend + 2); if(i < keys.size() - 1) { str += ","; } str += "\r\n"; } if( keys.size() > 0) { str += geneSpace(intend); } str += "}"; return str; } public static String geneSpace(int len) { return new String(new char[len]).replace('\0', ' '); } } |
34
cassyfar 2022-02-10 11:25:51 +08:00
@rabbbit 你这个数据结构是错的吧,题主已经说明了最后要存进一个树里面。
数据结构用这个,然后每查看一组,就遍历插入新节点即可。 class Node { String id; List<Node> children ; } |
35
unregister OP |
36
rabbbit 2022-02-10 11:32:07 +08:00
|
37
unregister OP @cassyfar 这个应该是用 Map 实现的,只是需要按照要求输出那个树状图就行了。
|
38
Tianyan 2022-02-10 13:14:20 +08:00
灵活就业者(失业者)超过 2 亿
|
39
unregister OP @whileFalse 嗯,对我来说有一点,这也知道和别人的差距在哪里。
|
40
aikilan 2022-02-10 16:11:44 +08:00 1
const data = ["中国 广州 深圳", "中国 广州 佛山", "中国 浙江 杭州"];
const onStart = (data) => { const res = {}; const onGen = (result, row) => { if(!row.length){ return } const item = row[0]; if(result[item]){ onGen(result[item], row.slice(1)) }else{ result[item] = {}; onGen(result[item], row.slice(1)) } } for(let i in data){ onGen(res, data[i].split(' ')); } return res } onStart(data) //{ '中国': { '广州': { '深圳': {}, '佛山': {} }, '浙江': { '杭州': {} } } } |
41
Chinsung 2022-02-10 17:15:56 +08:00
这种确定层级的,直接 map 塞就完事了吧,没必要非用树
|
42
msg7086 2022-02-10 17:24:51 +08:00 via Android
( map 嵌套就是树)
|
43
Aganzo 2022-02-10 17:36:49 +08:00
力扣也水了 1000 多题了,HARD 题一般会组合 DP 、UF 、单调栈、贪心、二分、划窗、Trie 、回溯等知识点中的一个或多个,按文中描述的题目内容评级应为 EASY
|
44
jguo 2022-02-10 20:54:19 +08:00
那就抓紧学,递归都搞不明白别说自己是程序员
|
45
unregister OP @Aganzo 我愿称之你为大佬。
|