一家公司让做 4 个面试题,投入不少精力做完之后,就回了句代码风格不规范,再问就没回应了。不知道具体哪里不规范应该怎样改进?贴出来题目和我的答案,请大家指点赐教。
第一题, TreeNode 查询 已知有如下⼀一个树状数据结构:
let tree = {
id: '1',
label: 'first',
children: [
{
id: '2',
label: 'second'
},
{
id: '3',
label: 'third',
children: [
{
id: '4',
label: 'fourth'
},
{
id: '5',
label: 'fifth'
}
]
}
]
};
请实现⼀一个查询函数,通过输⼊入 Tree 的 Root Node 和 Id,返回与其匹配的节点,函数原型如 下(注意:请不不要在函数内部直接⽤用 console.log 打印出来):
findNodeById(root: TreeNode, id: string): TreeNode;
这是第一题我的答案(虽然题目不是 java 的,但他们邮件里提到可以用任意语言作答):
public class GetTreeNode {
public static void main(String[] args) {
String json1 = "{\r\n" +
" id: '1',\r\n" +
" label: 'first',\r\n" +
" children: [\r\n" +
" {\r\n" +
" id: '2',\r\n" +
" label: 'second'\r\n" +
" },\r\n" +
" {\r\n" +
" id: '3',\r\n" +
" label: 'third',\r\n" +
" children: [\r\n" +
" {\r\n" +
" id: '4',\r\n" +
" label: 'fourth'\r\n" +
" },\r\n" +
" {\r\n" +
" id: '5',\r\n" +
" label: 'fifth'\r\n" +
" }\r\n" +
" ]\r\n" +
" }\r\n" +
" ]\r\n" +
"}";
JSONObject jObject1 = new JSONObject(json1);
String id = "2";
JSONObject returnNode = findNodeById(jObject1, id);
System.out.println(returnNode);
}
private static JSONObject findNodeById(JSONObject jObject1, String id) {
JSONObject returnNode = null;
for (int i = 0; i < jObject1.names().length(); i ++) {
String key = jObject1.names().getString(i);
if (key.equals("id")) {
String value = jObject1.getString(key);
if (((String) value).equals(id)) {
returnNode = new JSONObject(jObject1.toString());
return returnNode;
}
} else {
Object value = jObject1.get(key);
if (returnNode == null) {
returnNode = handleValue(value, id);
} else {
handleValue(value, id);
}
}
}
return returnNode;
}
private static JSONObject handleValue(Object value, String id) {
JSONObject returnNodeh = null;
if (value instanceof JSONObject) {
returnNodeh = findNodeById((JSONObject) value, id);
} else if (value instanceof JSONArray) {
returnNodeh = handleJSONArray((JSONArray) value, id);
}
return returnNodeh;
}
private static JSONObject handleJSONArray(JSONArray jsonArray, String id) {
JSONObject returnNodea = null;
for (int i = 0; i < jsonArray.length(); i ++) {
if (returnNodea == null) {
returnNodea = handleValue(jsonArray.get(i), id);
} else {
handleValue(jsonArray.get(i), id);
}
}
return returnNodea;
}
}
第二题:学⽣生按成绩分组 实现⼀一个 groupBy 函数,将学⽣生按照成绩等级进⾏行行分组。
// 成绩等级分为 A 、B 和 C 三级
function getGrade(score){
return score < 60 ? 'C' : score < 80 ? 'B' : 'A';
};
// 学⽣生及其成绩
let students = [
{name: '张三', score: 84},
{name: '李李四', score: 58},
{name: '王五', score: 99},
{name: '赵六', score: 69}
];
实现该函数:groupBy(students); 输出为:
{
'A': [
{name: '王五', score: 99},
{name: '张三', score: 84}
],
'B': [{name: '赵六', score: 69}],
'C': [{name: '李李四', score: 58}]
}
第二题答案:
public class GroupByStudents {
public static void main(String[] args) {
String input = "[\r\n" + "{name: '张三', score: 84},\r\n" + "{name: '李李四', score: 58},\r\n"
+ "{name: '王五', score: 99},\r\n" + "{name: '赵六', score: 69}\r\n" + "];";
JSONArray students = new JSONArray(input);
JSONObject studentGroups = groupBy(students);
System.out.println(studentGroups);
}
private static String getGrade(int score) {
return score < 60 ? "C" : score < 80 ? "B" : "A";
}
private static JSONObject groupBy(JSONArray students) {
JSONObject studentGroups = new JSONObject("{}");
for (int i = 0; i < students.length(); i ++) {
JSONObject student = students.getJSONObject(i);
int score = student.getInt("score");
String grade = getGrade(score);
studentGroups.append(grade, student);
}
return studentGroups;
}
}
第三题:字符串串 Parse 请设计⼀一个字符串串 parse 函数,可以将输⼊入的字符串串分解为对应的树状结构,⽐比如:
// 例子 1
let input = 'int';
let result = parse(intput);
// result 结果为:
// {
// type: 'int'
// };
// 例子 2
let input = 'Array<bool>';
let result = parse(intput);
// {
// type: 'Array',
// typeArgs: [{
// type: 'bool'
// }]
// };
// 例子 3
let input = 'Array<Array<string>>';
let result = parse(intput);
// {
// type: 'Array',
// typeArgs: [{
// type: 'Array',
// typeArgs: [{
// type: 'string'
// }]
// }]
// };
// 例子 4
let input = 'Map<string, Array<bool>>';
let result = parse(intput);
// {
// type: 'Map',
// typeArgs: [{
// type: 'string'
// }, {
// type: 'Array',
// typeArgs: [{
// type: 'bool'
// }]
// }]
// };
同理理,该 parse 函数可以分解如下任意情况,⽐比如:
"int"
"string"
"bool"
"Array<int>"
"Array<Array<int>>"
"Array<Array<Array<int>>>"
"Map<string, Map<string, bool>>"
"Map<Map<string, bool>, bool>"
第三题答案:
public class ParseString {
public static void main(String[] args) {
String input = "Map<string, Map<string, bool>>";
JSONObject result = parse(input);
System.out.println(result);
}
private static JSONObject parse(String input) {
JSONObject jsonObj = new JSONObject("{}");
String[] inputSplit = input.split("<", 2);
jsonObj.append("type", inputSplit[0]);
if (inputSplit.length == 2) {
loopParse(inputSplit[1].substring(0, inputSplit[1].length() - 1), jsonObj);
}
return jsonObj;
}
private static void loopParse(String string, JSONObject jsonObj) {
List<String> result = new ArrayList<String>();
Stack<String> stackInQuotes = new Stack<>();
int start = 0;
boolean inQuotes = false;
for (int current = 0; current < string.length(); current++) {
if (string.charAt(current) == '<') {
stackInQuotes.add("<");
} else if (string.charAt(current) == '>') {
stackInQuotes.pop();
}
boolean atLastChar = (current == string.length() - 1);
if (atLastChar) {
result.add(string.substring(start));
} else if (string.charAt(current) == ',' && stackInQuotes.isEmpty()) {
result.add(string.substring(start, current));
start = current + 1;
}
}
JSONArray substringJsonArr = new JSONArray();
for (int i = 0; i < result.size(); i ++) {
String substring = result.get(i);
String[] substringSplit = substring.split("<", 2);
JSONObject substringJsonObj = new JSONObject();
substringJsonObj.append("type", substringSplit[0]);
if (substringSplit.length == 2) {
loopParse(substringSplit[1].substring(0, substringSplit[1].length() - 1), substringJsonObj);
}
substringJsonArr.put(substringJsonObj);
}
jsonObj.append("typeArgs", substringJsonArr);
}
}
第四题:⾃自增 ID 已知有如下⼀一个树状数据结构:
let tree = {
id: '1',
type: 'View',
name: 'view',
children: [
{
id: '2',
type: 'Button',
name: 'button'
},
{
id: '3',
type: 'View',
name: 'view_1',
children: [
{
id: '4',
type: 'Button',
name: 'button_1'
},
{
id: '5',
type: 'View',
name: 'view_2'
}
]
}
]
};
name 字段的规则为整棵树不不能重复,如果遇到重复,则添加 _n 作为结尾。如果因为删除某 些节点,名字出现了了空隙,⽐比如 Tree 中有 button_1 和 button_3,但是没有 button_2,下⼀一 次插⼊入时,需要优先使⽤用 button_2,⽽而不不是 button_4 。 请实现⼀一个唯⼀一名称算法,当向整棵树的任意 children 插⼊入⼀一个新的 Node 时,可以保证 name 不不重复。 srcName 是计划向 Tree 中插⼊入节点的 name,⽐比如 button 、view, rootTreeNode 是整棵树
function getIncName(srcName: string, rootTreeNode : TreeNode): string;
第四题答案:
public class GetIncName {
public static void main(String[] args) {
String json1 = "{\r\n" + " id: '1',\r\n" + " type: 'View',\r\n" + " name: 'view',\r\n"
+ " children: [\r\n" + " {\r\n" + " id: '2',\r\n"
+ " type: 'Button',\r\n" + " name: 'button'\r\n" + " },\r\n"
+ " {\r\n" + " id: '3',\r\n" + " type: 'View',\r\n"
+ " name: 'view_1',\r\n" + " children: [\r\n" + " {\r\n"
+ " id: '4',\r\n" + " type: 'Button',\r\n"
+ " name: 'button_1'\r\n" + " },\r\n" + " {\r\n"
+ " id: '5',\r\n" + " type: 'View',\r\n"
+ " name: 'view_5'\r\n" + " }\r\n" + " ]\r\n"
+ " }\r\n" + " ]\r\n" + "}";
JSONObject jObject1 = new JSONObject(json1);
String srcName = "view";
String string = getIncName(srcName, jObject1);
System.out.println(string);
}
private static String getIncName(String srcName, JSONObject jObject1) {
Map<String, ArrayList<Integer>> namesMap = new LinkedHashMap<String, ArrayList<Integer>>();
handleJSONObject(jObject1, namesMap);
String incName = checkSrcName(srcName, namesMap);
return incName;
}
private static void handleJSONObject(JSONObject jObject1, Map<String, ArrayList<Integer>> namesMap) {
jObject1.keys().forEachRemaining(key -> {
Object value = jObject1.get(key);
if (key.equals("name")) {
String[] nameSplit = ((String) value).split("_");
if (namesMap.containsKey(nameSplit[0])) {
if (nameSplit.length == 2) {
ArrayList<Integer> nameList = namesMap.get(nameSplit[0]);
nameList.add(Integer.valueOf(Integer.parseInt(nameSplit[1])));
namesMap.put(nameSplit[0], nameList);
} else {
ArrayList<Integer> nameList = namesMap.get(nameSplit[0]);
nameList.add(Integer.valueOf(Integer.parseInt("0")));
namesMap.put(nameSplit[0], nameList);
}
} else {
if (nameSplit.length == 2) {
ArrayList<Integer> newNameList = new ArrayList<Integer>();
newNameList.add(Integer.valueOf(Integer.parseInt(nameSplit[1])));
namesMap.put(nameSplit[0], newNameList);
} else {
ArrayList<Integer> newNameList = new ArrayList<Integer>();
newNameList.add(Integer.valueOf(Integer.parseInt("0")));
namesMap.put(nameSplit[0], newNameList);
}
}
}
handleValue(value, namesMap);
});
}
private static void handleValue(Object value, Map<String, ArrayList<Integer>> namesMap) {
if (value instanceof JSONObject) {
handleJSONObject((JSONObject) value, namesMap);
} else if (value instanceof JSONArray) {
handleJSONArray((JSONArray) value, namesMap);
}
}
private static void handleJSONArray(JSONArray jsonArray, Map<String, ArrayList<Integer>> namesMap) {
jsonArray.iterator().forEachRemaining(element -> {
handleValue(element, namesMap);
});
}
private static String checkSrcName(String srcName, Map<String, ArrayList<Integer>> namesMap) {
String[] nameSplit = srcName.split("_");
if (namesMap.containsKey(nameSplit[0])) {
ArrayList<Integer> nameList = namesMap.get(nameSplit[0]);
Collections.sort(nameList);
int availablenum = 0;
for (int i = 0; i < nameList.size(); i ++) {
if (nameList.get(i).intValue() != i) {
availablenum = i;
break;
} else {
availablenum = i + 1;
}
}
return nameSplit[0]+"_"+availablenum;
} else {
return srcName;
}
}
}
1
mumbler 2020-04-10 22:09:38 +08:00 via Android
代码都没有注释啊
|
2
sxxkgoogle OP @mumbler 嗯没注释,之前在网上搜好像说做面试题一般不需要吧。
|
3
also24 2020-04-10 22:25:36 +08:00
怎么感觉题目是 TypeScript 的,楼主你这面的是什么岗位?
|
4
sxxkgoogle OP @also24 是全栈的岗位。
|
5
mcfog 2020-04-10 22:46:54 +08:00 via Android
你看你就这样贴了题目出来,还有猎头也会收集题目,培训班也有一个个安排面试拿题目给下一个的操作,所以一般不会解释过多的
|
6
raymanr 2020-04-10 22:53:49 +08:00
呃,我不是专业程序员,好奇自己的水平在专业人员眼里是啥样的,做了下第一题,各位大佬点评下
``` function findNodeById(root, id) { let result = []; function findOne(node, id) { if (node["id"] == id) { result.push(node); } if (node.hasOwnProperty("children")) { node["children"].forEach(child => findOne(child, id)); } return false; } findOne(root, id); return result; } ``` |
7
swulling 2020-04-10 22:54:07 +08:00 via iPad
代码长度相比于出题人的预期略长了
|
8
aureole999 2020-04-10 23:05:26 +08:00
为什么不管什么都用 JsonObject 做呢?
题目只说有个树状结构,例子给的是 js,不代表非要用 json 来实现树,你可以自己定义 TreeNode Class 啊。如果题目要求必须用 json,那也应该把 json 映射成 java bean 再写处理的方法吧。要不你就别用 java,直接用 js 。 |
9
aureole999 2020-04-10 23:13:49 +08:00
@raymanr 第一题返回值不需要用数组。一般来说叫函数名 byId 的返回值就是唯一的,而且人家给的函数原型的返回值也不是数组。
|
10
ASpiral 2020-04-11 00:26:11 +08:00
试着做了下第一题,感觉没必要写那么长的代码吧…
const findNodeById = (root, id) => { let target = null; const findNode = (root, id) => { if (target !== null) { return; } if (root.id === id) { target = root; } else if (root.children) { root.children.forEach(node => findNode(node, id)); } }; findNode(root, id); return target; }; |
11
lithbitren 2020-04-11 02:33:06 +08:00
代码没细看,java 选手好可怕,感觉 python 都是几行以内解决的,js 写起来也就是多了半对大括号的行数。。
|
12
rabbbit 2020-04-11 03:36:06 +08:00 1
1
interface TreeNode { ...id: String, ...label: String, ...children?: TreeNode[] } function findNodeById(root: TreeNode, id: string): TreeNode { ...if (root.id === id) { ......return root; ...} ... ...if (root.children) { ......for (let i of root.children) { .........const child = findNodeById(i, id); .........if (child) { ............return child .........} ......} ...} else { ... return null; ...} } console.assert(findNodeById(tree, '1').label === 'first', '1') console.assert(findNodeById(tree, '2').label === 'second', '2') console.assert(findNodeById(tree, '3').label === 'third', '3') console.assert(findNodeById(tree, '4').label === 'fourth', '4') console.assert(findNodeById(tree, '5').label === 'fifth', '5') |
13
rabbbit 2020-04-11 03:51:58 +08:00
2
interface Student { ...name: string, ...score: number } function groupBy(students: Student[]) { ...const group: { [propName: string]: Student[] } = {}; ...for (let i of students) { ......const grade = getGrade(i.score); ......if (!group[grade]) { .........group[grade] = [] ......} ......group[grade].push(i) ...} ...return group; } |
14
6IbA2bj5ip3tK49j 2020-04-11 04:03:08 +08:00 via iPhone
1,不要硬编码数据,从文件读取。方便测试,修改。
2,lambda 反正我作为 Java 开发,这样的代码风格,我是接受不了的。 |
15
lithbitren 2020-04-11 04:35:31 +08:00
几行夸张了,手撕中等题也要十行左右了。
宽搜扩展完事,这里就用字典代替树了,如果树是对象的话就更改获取属性的语句就行。 def findNodeById(root, id): ㅤㅤd = root and [root] ㅤㅤwhile d: ㅤㅤㅤㅤr = next((r for r in d if r['id'] == id), None) ㅤㅤㅤㅤif r: ㅤㅤㅤㅤㅤㅤreturn r ㅤㅤㅤㅤd = sum((r['children'] for r in d if 'children' in r), []) ㅤㅤreturn None 第二题最简单 def getGrade(score): ㅤㅤreturn score < 60 and 'C' or score < 80 and 'B' or 'A' def groupBy(students): ㅤㅤres = {'A': [], 'B': [], 'C': []} # res = collections.defaultdict(list) ㅤㅤfor student in students: ㅤㅤㅤㅤres[getGrade(student['score'])].append(student) ㅤㅤreturn res 语法题栈实现 def parse(args): ㅤㅤstack = [{'type': ''}] ㅤㅤfor c in args: ㅤㅤㅤㅤif c == ' ': ㅤㅤㅤㅤㅤㅤcontinue ㅤㅤㅤㅤelif c == '<': ㅤㅤㅤㅤㅤㅤstack[-1]['typeArgs'] = [{'type': ''}] ㅤㅤㅤㅤㅤㅤstack.append(stack[-1]['typeArgs'][0]) ㅤㅤㅤㅤelif c == ',': ㅤㅤㅤㅤㅤㅤstack[-2]['typeArgs'].append({'type': ''}) ㅤㅤㅤㅤㅤㅤstack[-1] = stack[-2]['typeArgs'][-1] ㅤㅤㅤㅤelif c == '>': ㅤㅤㅤㅤㅤㅤdel stack[-1] ㅤㅤㅤㅤelse: ㅤㅤㅤㅤㅤㅤstack[-1]['type'] += c ㅤㅤreturn stack[0] O(N)的在线算法,深搜遍历,计数判断,如果离线的话可以优化到 O(logN) def getIncName(srcName, rootTreeNode): ㅤㅤd = set() ㅤㅤdef dfs(r): ㅤㅤㅤㅤr['name'].rsplit('_', 1)[0] == srcName and d.add(r['name']) ㅤㅤㅤㅤif 'children' in r: ㅤㅤㅤㅤㅤㅤfor child in r['children']: ㅤㅤㅤㅤㅤㅤㅤㅤdfs(child) ㅤㅤrootTreeNode and dfs(rootTreeNode) ㅤㅤif srcName not in d: ㅤㅤㅤㅤreturn srcName ㅤㅤfor i in range(1, len(d) + 1): ㅤㅤㅤㅤres = srcName + '_' + str(i) ㅤㅤㅤㅤif res not in d: ㅤㅤㅤㅤㅤㅤreturn res |
16
rabbbit 2020-04-11 05:24:58 +08:00
@lithbitren 空格是怎么打出来的?
|
17
lithbitren 2020-04-11 05:34:27 +08:00 1
@rabbbit 随便找了个空白字符,ascii 码 12644
|
19
tyx1703 2020-04-11 05:42:39 +08:00 via iPhone
题目用的 ts,你用 java 作答我寻思着起码手动把 TreeNode 的数据结构实现一下吧
一坨坨 json 感官上就很不舒服,更加无心阅读代码质量了 |
20
yazoox 2020-04-11 08:10:40 +08:00 via Android
有意思,关注一下
|
21
alphatoad 2020-04-11 08:11:25 +08:00
别想太多,可能只是因为面试有 kpi
|
22
easylee 2020-04-11 08:15:53 +08:00 via Android
别想太多,你能来发帖,大概率不是你的问题。
我面过一些公司,面试题竟然有线性代数,还有多积分的! 还有一些公司面试题很快的写完了,结果不给回复了。 |
23
yhxx 2020-04-11 09:27:09 +08:00
可能因为出题的是前端,看到你实现 json 的方式觉得有点丑?
|
24
wangbot1 2020-04-11 11:47:28 +08:00
Java 的还是定义类型比较好, JsonNode 看起来不直观
import com.fasterxml.jackson.databind.ObjectMapper; import com.fasterxml.jackson.databind.type.CollectionType; import lombok.Data; import lombok.NonNull; import java.io.IOException; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.Map; import java.util.stream.Collectors; public class Main { @Data static class TreeNode < T extends TreeNode > { private List < T > children; } @Data static class Label extends TreeNode < Label > { private String id; private String label; } @Data static class OrderNameTreeNode extends TreeNode < OrderNameTreeNode > { private String id; private String type; private String name; } @Data static class Student { private String name; private double score; } @Data static class Type { private String type = ""; private List < Type > typeArgs = new ArrayList < > (); } @FunctionalInterface public interface Recursion < T > { void go(T t, Recursion < T > self); } private static Label question1(@NonNull Label root, @NonNull String id) { if (id.equals(root.getId())) { return root; } else if (null != root.getChildren()) { for (Label child: root.getChildren()) { Label tartget = question1(child, id); if (tartget != null) { return tartget; } } } return null; } private static Map < String, List < Student >> question2(@NonNull List < Student > students) { return students .stream() .collect(Collectors.groupingBy(student - > student.getScore() < 60 ? "C" : student.getScore() < 80 ? "B" : "A")); } private static Type question3(@NonNull String typeArgs) { List < Type > types = new ArrayList < > (); Type root = new Type(); types.add(root); for (int i = 0, len = typeArgs.length(); i < len; i++) { char c = typeArgs.charAt(i); if (c == '<') { Type type = new Type(); types.get(types.size() - 1).getTypeArgs().add(type); types.add(type); } else if (c == ',') { types.remove(types.size() - 1); Type type = new Type(); types.get(types.size() - 1).getTypeArgs().add(type); types.add(type); } else if (c == ' ') { continue; } else if (c == '>') { types.remove(types.size() - 1); } else { Type type = types.get(types.size() - 1); type.setType(type.getType() + c); } } return root; } private static String question4(@NonNull String srcName, @NonNull OrderNameTreeNode root) { List < Integer > existsIndexs = new ArrayList < > (); Recursion < OrderNameTreeNode > func = (treeNode, self) - > { if (treeNode.getName().startsWith(srcName)) { String substring = treeNode.getName().substring(srcName.length()); if ("".equals(substring)) { existsIndexs.add(0); } else { existsIndexs.add(Integer.parseInt(substring.substring(1))); } } if (null != treeNode.getChildren()) { treeNode.getChildren().forEach(child - > self.go(child, self)); } }; func.go(root, func); if (existsIndexs.isEmpty()) { return srcName; } existsIndexs.sort(Comparator.comparingInt(o - > o)); if (existsIndexs.get(0) != 0) { return srcName; } for (int i = 1; i < existsIndexs.size(); i++) { if (existsIndexs.get(i) - existsIndexs.get(i - 1) > 1) { return String.format("%s_%d", srcName, i + 1); } } return String.format("%s_%d", srcName, existsIndexs.size()); } public static void main(String[] args) throws IOException { ObjectMapper mapper = new ObjectMapper(); String treeNodeJson = "{\"id\":\"1\",\"label\":\"first\",\"children\":[{\"id\":\"2\",\"label\":\"second\"},{\"id\":\"3\",\"label\":\"third\",\"children\":[{\"id\":\"4\",\"label\":\"fourth\"},{\"id\":\"5\",\"label\":\"fifth\"}]}]}"; Label treeNode = mapper.readValue(treeNodeJson, Label.class); for (int i = 1; i < 5; i++) { System.out.println(question1(treeNode, String.valueOf(i))); } String studentJson = "[{\"name\":\"张三\",\"score\":84},{\"name\":\"李李四\",\"score\":58},{\"name\":\"王五\",\"score\":99},{\"name\":\"赵六\",\"score\":69}]"; CollectionType collectionType = mapper.getTypeFactory().constructCollectionType(List.class, Student.class); List < Student > students = mapper.readValue(studentJson, collectionType); System.out.printf(mapper.writerWithDefaultPrettyPrinter().writeValueAsString(question2(students))); System.out.println(mapper.writerWithDefaultPrettyPrinter().writeValueAsString(question3("int"))); System.out.println(mapper.writerWithDefaultPrettyPrinter().writeValueAsString(question3("bool"))); System.out.println(mapper.writerWithDefaultPrettyPrinter().writeValueAsString(question3("Array<int>"))); System.out.println(mapper.writerWithDefaultPrettyPrinter().writeValueAsString(question3("Array<Array<int>>"))); System.out.println(mapper.writerWithDefaultPrettyPrinter().writeValueAsString(question3( "Array<Array<Array<int>>>"))); System.out.println(mapper.writerWithDefaultPrettyPrinter().writeValueAsString(question3( "Map<string, Map<string, bool>>"))); System.out.println(mapper.writerWithDefaultPrettyPrinter().writeValueAsString(question3( "Map<Map<string, bool>, bool>"))); String orderNameTreeNodeJson = "{\"id\":\"1\",\"type\":\"View\",\"name\":\"view\",\"children\":[{\"id\":\"2\",\"type\":\"Button\",\"name\":\"button\"},{\"id\":\"3\",\"type\":\"View\",\"name\":\"view_1\",\"children\":[{\"id\":\"4\",\"type\":\"Button\",\"name\":\"button_1\"},{\"id\":\"5\",\"type\":\"View\",\"name\":\"view_2\"}]}]}"; OrderNameTreeNode orderNameTreeNode = mapper.readValue(orderNameTreeNodeJson, OrderNameTreeNode.class); System.out.println(question4("view", orderNameTreeNode)); System.out.println(question4("button", orderNameTreeNode)); } } |
25
wangbot1 2020-04-11 11:52:57 +08:00
import com.fasterxml.jackson.databind.ObjectMapper;
import com.fasterxml.jackson.databind.type.CollectionType; import lombok.Data; import lombok.NonNull; import java.io.IOException; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.Map; import java.util.stream.Collectors; public class Main { ㅤ......@Data ㅤ......static class TreeNode < T extends TreeNode > { ㅤ......ㅤ......private List < T > children; ㅤ......} ㅤ......@Data ㅤ......static class Label extends TreeNode < Label > { ㅤ......ㅤ......private String id; ㅤ......ㅤ......private String label; ㅤ......} ㅤ......@Data ㅤ......static class OrderNameTreeNode extends TreeNode < OrderNameTreeNode > { ㅤ......ㅤ......private String id; ㅤ......ㅤ......private String type; ㅤ......ㅤ......private String name; ㅤ......} ㅤ......@Data ㅤ......static class Student { ㅤ......ㅤ......private String name; ㅤ......ㅤ......private double score; ㅤ......} ㅤ......@Data ㅤ......static class Type { ㅤ......ㅤ......private String type = ""; ㅤ......ㅤ......private List < Type > typeArgs = new ArrayList < > (); ㅤ......} ㅤ......@FunctionalInterface ㅤ......public interface Recursion < T > { ㅤ......ㅤ......void go(T t, Recursion < T > self); ㅤ......} ㅤ......private static Label question1(@NonNull Label root, @NonNull String id) { ㅤ......ㅤ......if (id.equals(root.getId())) { ㅤ......ㅤ......ㅤ......return root; ㅤ......ㅤ......} else if (null != root.getChildren()) { ㅤ......ㅤ......ㅤ......for (Label child: root.getChildren()) { ㅤ......ㅤ......ㅤ......ㅤ......Label tartget = question1(child, id); ㅤ......ㅤ......ㅤ......ㅤ......if (tartget != null) { ㅤ......ㅤ......ㅤ......ㅤ......ㅤ......return tartget; ㅤ......ㅤ......ㅤ......ㅤ......} ㅤ......ㅤ......ㅤ......} ㅤ......ㅤ......} ㅤ......ㅤ......return null; ㅤ......} ㅤ......private static Map < String, List < Student >> question2(@NonNull List < Student > students) { ㅤ......ㅤ......return students ㅤ......ㅤ......ㅤ.......stream() ㅤ......ㅤ......ㅤ.......collect(Collectors.groupingBy(student - > ㅤ......ㅤ......ㅤ......ㅤ......student.getScore() < 60 ? "C" : student.getScore() < 80 ? "B" : "A")); ㅤ......} ㅤ......private static Type question3(@NonNull String typeArgs) { ㅤ......ㅤ......List < Type > types = new ArrayList < > (); ㅤ......ㅤ......Type root = new Type(); ㅤ......ㅤ......types.add(root); ㅤ......ㅤ......for (int i = 0, len = typeArgs.length(); i < len; i++) { ㅤ......ㅤ......ㅤ......char c = typeArgs.charAt(i); ㅤ......ㅤ......ㅤ......if (c == '<') { ㅤ......ㅤ......ㅤ......ㅤ......Type type = new Type(); ㅤ......ㅤ......ㅤ......ㅤ......types.get(types.size() - 1).getTypeArgs().add(type); ㅤ......ㅤ......ㅤ......ㅤ......types.add(type); ㅤ......ㅤ......ㅤ......} else if (c == ',') { ㅤ......ㅤ......ㅤ......ㅤ......types.remove(types.size() - 1); ㅤ......ㅤ......ㅤ......ㅤ......Type type = new Type(); ㅤ......ㅤ......ㅤ......ㅤ......types.get(types.size() - 1).getTypeArgs().add(type); ㅤ......ㅤ......ㅤ......ㅤ......types.add(type); ㅤ......ㅤ......ㅤ......} else if (c == ' ') { ㅤ......ㅤ......ㅤ......ㅤ......continue; ㅤ......ㅤ......ㅤ......} else if (c == '>') { ㅤ......ㅤ......ㅤ......ㅤ......types.remove(types.size() - 1); ㅤ......ㅤ......ㅤ......} else { ㅤ......ㅤ......ㅤ......ㅤ......Type type = types.get(types.size() - 1); ㅤ......ㅤ......ㅤ......ㅤ......type.setType(type.getType() + c); ㅤ......ㅤ......ㅤ......} ㅤ......ㅤ......} ㅤ......ㅤ......return root; ㅤ......} ㅤ......private static String question4(@NonNull String srcName, @NonNull OrderNameTreeNode root) { ㅤ......ㅤ......List < Integer > existsIndexs = new ArrayList < > (); ㅤ......ㅤ......Recursion < OrderNameTreeNode > func = (treeNode, self) - > { ㅤ......ㅤ......ㅤ......if (treeNode.getName().startsWith(srcName)) { ㅤ......ㅤ......ㅤ......ㅤ......String substring = treeNode.getName().substring(srcName.length()); ㅤ......ㅤ......ㅤ......ㅤ......if ("".equals(substring)) { ㅤ......ㅤ......ㅤ......ㅤ......ㅤ......existsIndexs.add(0); ㅤ......ㅤ......ㅤ......ㅤ......} else { ㅤ......ㅤ......ㅤ......ㅤ......ㅤ......existsIndexs.add(Integer.parseInt(substring.substring(1))); ㅤ......ㅤ......ㅤ......ㅤ......} ㅤ......ㅤ......ㅤ......} ㅤ......ㅤ......ㅤ......if (null != treeNode.getChildren()) { ㅤ......ㅤ......ㅤ......ㅤ......treeNode.getChildren().forEach(child - > self.go(child, self)); ㅤ......ㅤ......ㅤ......} ㅤ......ㅤ......}; ㅤ......ㅤ......func.go(root, func); ㅤ......ㅤ......if (existsIndexs.isEmpty()) { ㅤ......ㅤ......ㅤ......return srcName; ㅤ......ㅤ......} ㅤ......ㅤ......existsIndexs.sort(Comparator.comparingInt(o - > o)); ㅤ......ㅤ......if (existsIndexs.get(0) != 0) { ㅤ......ㅤ......ㅤ......return srcName; ㅤ......ㅤ......} ㅤ......ㅤ......for (int i = 1; i < existsIndexs.size(); i++) { ㅤ......ㅤ......ㅤ......if (existsIndexs.get(i) - existsIndexs.get(i - 1) > 1) { ㅤ......ㅤ......ㅤ......ㅤ......return String.format("%s_%d", srcName, i + 1); ㅤ......ㅤ......ㅤ......} ㅤ......ㅤ......} ㅤ......ㅤ......return String.format("%s_%d", srcName, existsIndexs.size()); ㅤ......} } |