中级农民
- 积分
- 125
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2015-9-14
- 最后登录
- 1970-1-1
|
攒个RP,字母二叉树代码:- <pre style="background-color:#2b2b2b;color:#a9b7c6;font-family:'Consolas';font-size:12.0pt;"><span style="color:#cc7832;">private </span>String <span style="color:#ffc66d;">sExpression</span>(<span style="color:#cc7832;">char</span>[][] pairs<span style="color:#cc7832;">, char </span>node<span style="color:#cc7832;">, </span>String res) {
- <span style="color:#cc7832;">char </span>left = <span style="color:#6a8759;">'l'</span><span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> char </span>right = <span style="color:#6a8759;">'r'</span><span style="color:#cc7832;">;
- </span><span style="color:#cc7832;">
- </span><span style="color:#cc7832;"> for </span>(<span style="color:#cc7832;">char</span>[] pair : pairs) {
- <span style="color:#cc7832;">if </span>(pair[<span style="color:#6897bb;">0</span>] == node && left == <span style="color:#6a8759;">'l'</span>) {
- left = pair[<span style="color:#6897bb;">1</span>]<span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> </span>} <span style="color:#cc7832;">else if </span>(pair[<span style="color:#6897bb;">0</span>] == node && left != <span style="color:#6a8759;">'l'</span>) {
- right = pair[<span style="color:#6897bb;">1</span>]<span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> </span>}
- }
- String leftTree = left == <span style="color:#6a8759;">'l' </span>? <span style="color:#6a8759;">"" </span>: sExpression(pairs<span style="color:#cc7832;">, </span>left<span style="color:#cc7832;">, </span>res)<span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> </span>String rightTree = right == <span style="color:#6a8759;">'r' </span>? <span style="color:#6a8759;">"" </span>: sExpression(pairs<span style="color:#cc7832;">, </span>right<span style="color:#cc7832;">, </span>res)<span style="color:#cc7832;">;
- </span><span style="color:#cc7832;">
- </span><span style="color:#cc7832;"> return </span><span style="color:#6a8759;">"(" </span>+ node + leftTree + rightTree + <span style="color:#6a8759;">")"</span><span style="color:#cc7832;">;
- </span><span style="color:#cc7832;">
- </span><span style="color:#cc7832;"> </span>}
- <span style="color:#cc7832;">public </span>String <span style="color:#ffc66d;">validTree</span>(<span style="color:#cc7832;">char</span>[][] pairs) {
- <span style="color:#808080;">//sort the input pairs in ascending order
- </span><span style="color:#808080;"> </span>Arrays.<span style="font-style:italic;">sort</span>(pairs<span style="color:#cc7832;">, new </span>Comparator<<span style="color:#cc7832;">char</span>[]>() {
- <span style="color:#bbb529;">@Override
- </span><span style="color:#bbb529;"> </span><span style="color:#cc7832;">public int </span><span style="color:#ffc66d;">compare</span>(<span style="color:#cc7832;">char</span>[] o1<span style="color:#cc7832;">, char</span>[] o2) {
- <span style="color:#cc7832;">if </span>(o1[<span style="color:#6897bb;">0</span>] == o2[<span style="color:#6897bb;">0</span>]) <span style="color:#cc7832;">return </span>(<span style="color:#6897bb;">0 </span>+ o1[<span style="color:#6897bb;">1</span>] - o2[<span style="color:#6897bb;">1</span>])<span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> else return </span>(<span style="color:#6897bb;">0 </span>+ o1[<span style="color:#6897bb;">0</span>] - o2[<span style="color:#6897bb;">0</span>])<span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> </span>}
- })<span style="color:#cc7832;">;
- </span><span style="color:#cc7832;">
- </span><span style="color:#cc7832;"> </span><span style="color:#808080;">//check if there are nodes who have more than 2 children, or if the input has duplicate edges
- </span><span style="color:#808080;"> </span>HashMap<Character<span style="color:#cc7832;">, </span>Set<Character>> map = <span style="color:#cc7832;">new </span>HashMap<>()<span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> for </span>(<span style="color:#cc7832;">char</span>[] pair : pairs) {
- <span style="color:#cc7832;">if </span>(map.get(pair[<span style="color:#6897bb;">0</span>]) == <span style="color:#cc7832;">null</span>) map.put(pair[<span style="color:#6897bb;">0</span>]<span style="color:#cc7832;">, new </span>HashSet<>())<span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> boolean </span>addSucceed = map.get(pair[<span style="color:#6897bb;">0</span>]).add(pair[<span style="color:#6897bb;">1</span>])<span style="color:#cc7832;">;
- </span><span style="color:#cc7832;">
- </span><span style="color:#808080;">// System.out.println("Key: " + pair[0] + " value: " + pair[1]);
- </span><span style="color:#808080;">
- </span><span style="color:#808080;"> </span><span style="color:#cc7832;">if </span>(map.get(pair[<span style="color:#6897bb;">0</span>]).size() >= <span style="color:#6897bb;">3</span>) {
- <span style="color:#cc7832;">return </span><span style="color:#6a8759;">"E1: More than 2 children"</span><span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> </span>}
- <span style="color:#cc7832;">if </span>(!addSucceed) {
- <span style="color:#cc7832;">return </span><span style="color:#6a8759;">"E2: Duplicate Edges"</span><span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> </span>}
- }
- <span style="color:#808080;">//check if there are cycle present
- </span><span style="color:#808080;"> </span><span style="color:#cc7832;">for </span>(<span style="color:#cc7832;">char </span>key : map.keySet()) {
- <span style="color:#cc7832;">for </span>(<span style="color:#cc7832;">char </span>value : map.get(key)) {
- <span style="color:#cc7832;">if </span>(map.get(value) != <span style="color:#cc7832;">null </span>&& map.get(value).contains(key)) <span style="color:#808080;">//children point to their parents
- </span><span style="color:#808080;"> </span>{
- <span style="color:#cc7832;">return </span><span style="color:#6a8759;">"E3: Cycle present"</span><span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> </span>}
- }
- }
- <span style="color:#808080;">//check if there are multiple roots
- </span><span style="color:#808080;"> //the method is to check if there are more than 2 nodes who don't have parent
- </span><span style="color:#808080;"> </span><span style="color:#cc7832;">int </span>count = <span style="color:#6897bb;">0</span><span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> for </span>(<span style="color:#cc7832;">char </span>key : map.keySet()) {
- <span style="color:#cc7832;">boolean </span>root = <span style="color:#cc7832;">true;
- </span><span style="color:#cc7832;"> for </span>(<span style="color:#cc7832;">char </span>k : map.keySet()) {
- <span style="color:#cc7832;">if </span>(map.get(k).contains(key)) root = <span style="color:#cc7832;">false;
- </span><span style="color:#cc7832;"> </span>}
- <span style="color:#cc7832;">if </span>(root) {
- count++<span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> </span>}
- }
- <span style="color:#cc7832;">if </span>(count >= <span style="color:#6897bb;">2</span>) {
- <span style="color:#cc7832;">return </span><span style="color:#6a8759;">"E4: Multiple roots"</span><span style="color:#cc7832;">;
- </span><span style="color:#cc7832;"> </span>}
- <span style="color:#808080;">//get the result string
- </span><span style="color:#808080;"> </span>String res = sExpression(pairs<span style="color:#cc7832;">, </span>pairs[<span style="color:#6897bb;">0</span>][<span style="color:#6897bb;">0</span>]<span style="color:#cc7832;">, </span><span style="color:#6a8759;">""</span>)<span style="color:#cc7832;">;
- </span><span style="color:#cc7832;">
- </span><span style="color:#cc7832;"> return </span>res<span style="color:#cc7832;">;
- </span><span style="color:#cc7832;">
- </span><span style="color:#cc7832;"> </span>}</pre>
复制代码 |
|