小米笔试

我是先构造一颗二叉树，然后再用中序遍历写，后来发现，其实没必要这么复杂，直接对原字符串递归写就可以实现

 /*  用了一个栈 遍历字符串 不同情况不同处理  */ static String solution(String input) {      if(input==null||input.length()<2){      return input;      }         Stack<Character> number=new Stack<Character>();         StringBuilder builder=new StringBuilder();         for(int i=0;i<input.length();i++){          char c=input.charAt(i);          if(c>='0'&&c<='9'){          char c1=input.charAt(i+1);          if(c1==','){          builder.append(c);          builder.append(number.pop());          i++;          continue;          }          number.push(c);          }          if(c=='('){          char c1=input.charAt(i+1);          if(c1==','){          builder.append(number.pop());          i++;          }                }          if(c==')'){            builder.append(number.isEmpty()?"":number.pop());          }         }         return builder.toString();

用两个栈实现，用例过了，不知道对不对，没时间交上去呜呜呜 static String solution(String input) {         Stack<Character> stack1 = new Stack<>();         Stack<Character> stack2 = new Stack<>();         String s = "";         char[] chars = input.toCharArray();         for (int i = 0; i < chars.length; i++) {             if (chars[i] >= '1' && chars[i] <= '9') {                     stack2.push(chars[i]);             } else {                 if (stack1.empty()) {                     stack1.push(chars[i]);                 } else {                     if (chars[i] == '(') {                         stack1.push(chars[i]);                     } else if (chars[i] == ')') {                         stack1.pop();                         if (!stack2.empty())                             s +=  stack2.pop();                     } else {                         if (!stack2.empty())                             s += stack2.pop();                     }                 }             }         }         return s;     }

// 递归 全A public class Solution { //1(2(3,4(,5)),6(7,)) /*请完成下面这个函数，实现题目要求的功能 当然，你也可以不按照下面这个模板来作答，完全按照自己的想法来 ^-^  ******************************开始写代码******************************/     public static String getLeft(String s) {         if(s.charAt(2) == ',')             return null;         if(s.charAt(3) == ',')             return s.substring(2, 3);         Stack<Character> stack = new Stack<Character>();         for (int i = 2; i < s.length(); i++) {             char c = s.charAt(i);             if(c == '(')                 stack.push(c);             else if(c == ')') {                 stack.pop();                 if(stack.isEmpty()) {                     return s.substring(2, i+1);                 }             }         }         return s.substring(2, s.indexOf(','));     }          public static String getRight(String s) {         if(s.charAt(2) == ',')             return s.substring(s.indexOf(',') + 1, s.length() - 1);         if(s.charAt(3) == ',')             return s.substring(s.indexOf(',') + 1, s.length() - 1);         Stack<Character> stack = new Stack<Character>();         for (int i = 2; i < s.length(); i++) {             char c = s.charAt(i);             if(c == '(')                 stack.push(c);             else if(c == ')') {                 stack.pop();                 if(stack.isEmpty()) {                     return s.substring(i + 2, s.length() - 1);                 }             }         }         return s.substring(s.indexOf(',') + 1, s.length() - 1);     }          public static void Travese(String s) {         if(s == null || s.equals("")) return;                  if(s.length() == 1) {             System.out.print(s.charAt(0));             return;         }         String left = getLeft(s);         Travese(left);         System.out.print(s.charAt(0));         String right = getRight(s);         Travese(right);     }      //    static String solution(String input) { //         //    } /******************************结束写代码******************************/     public static void main(String[] args){         Scanner in = new Scanner(System.in);         String res;                      String _input;         try {             _input = in.nextLine();         } catch (Exception e) {             _input = null;         }            Travese(_input);         //res = solution(_input);         //System.out.println(res);     } }

。。

同求,写了好久0ac😂

看到二叉树就往递归想，如果能递归就简单的

我是递归重建二叉树的，遇到左括号就递归，遇到右括号停止递归

public static String test2pro(String str) { int i=0; String temp=""; while(i<str.length()&&str.charAt(i)!='(') { i++; } if(i==str.length()) { temp= str.substring(0); }else if(str.charAt(i)=='(') { temp = str.substring(0,i); String rest = str.substring(i+1,str.length()-1); i=0; int count=0; while(i<rest.length()) { char t =rest.charAt(i); if(t=='(') { count++; }else if(t==')') { count--; }else if(t==',') { if(count==0) break; } i++; } if(i==0) { temp+=test2pro(rest.substring(i+1,rest.length())); }else if(i==temp.length()-1) { temp = test2pro(rest.substring(0,i))+temp; }else { temp+=test2pro(rest.substring(i+1,rest.length())); temp = test2pro(rest.substring(0,i))+temp; } } return temp; } 这个是我改进的代码，不用去构造二叉树了，直接遍历字符串加递归，应该没什么问题。

没学好，不会这道

为啥我也是开发岗，移动端，第二题就是一个状态dp。。。。

构建二叉树 mirror中序遍历 A了     static String solution(String input) {         TreeNode node = solutionSub(input);         String result = treeMid(node);         return result;     }     public static String treeMid(TreeNode head) {         StringBuilder sb = new StringBuilder();         if (head == null) return null;         TreeNode cur1 = head;         TreeNode cur2 = null;         while (cur1 != null) {             cur2 = cur1.left;             if (cur2 != null) {                 while (cur2.right != cur1 && cur2.right != null) {                     cur2 = cur2.right;                 }                 if (cur2.right != cur1) {                     cur2.right = cur1;                     cur1 = cur1.left;                     continue;                 } else {                     cur2.right = null;                 }             }             sb.append(cur1.val);             cur1 = cur1.right;         }         return sb.toString();     }     static TreeNode solutionSub(String input) {         if (input == null || input.length() == 0) return null;         Integer i = Integer.valueOf(input.substring(0, 1));         TreeNode node = new TreeNode(i);         if (input.length() > 1) {             String child = input.substring(2, input.length() - 1);             int left = 0;             int right = 0;             int mid = 0;             for (int j = 0; j < child.length(); j++) {                 if (child.charAt(j) == '(') {                     left++;                     continue;                 }                 if (child.charAt(j) == ')') {                     right++;                     continue;                 }                 if (child.charAt(j) == ',' && left == right) {                     mid = j;                     break;                 }             }             String leftChild = child.substring(0, mid);             String rightChild = child.substring(mid + 1);             TreeNode le = solutionSub(leftChild);             TreeNode ri = solutionSub(rightChild);             node.left = le;             node.right = ri;         }         return node;     }

static String solution(String input) {      if(input.equals("") || input == null) {      return input;      }          return func(input);     }     static String func(String input) {      if(!input.contains("(")) {      return input;      }           int one = input.indexOf("(");      int two = input.lastIndexOf(")");           int len = 0;      int flag = -1;      for(int i = one+1; i < two; i++) {      if(input.charAt(i) == ',' && len == 0) {      flag = i;      }      if(input.charAt(i) == '(') {      len++;      }      if(input.charAt(i) == ')') {      len--;      }      }      return func(input.substring(one+1, flag))+input.substring(0, one)+func(input.substring(flag+1, two));          }

#include <iostream> #include <vector> #include <numeric> #include <limits> #include <string> using namespace std; void helper (string input,string& res) { if (input.size() == 0) return; else if (input.size() == 1) { res += input; return; } int n = input.find('('); char head = input[0]; int count = 0,i; for (i = 1; i < input.size(); i++) { if (input[i] == '(') count++; else if (input[i] == ',') count--; if (count == 0) break; } string left = input.substr(2,i - 2); string right = input.substr(i+1,input.size() - 2- i); helper (left,res); res += head; helper (right,res); } /*请完成下面这个函数，实现题目要求的功能 当然，你也可以不按照下面这个模板来作答，完全按照自己的想法来 ^-^ ******************************开始写代码******************************/ string solution(string input) {      string res; if (input.size() == 0) return res; helper (input,res); } /******************************结束写代码******************************/ int main() { string res; string _input; getline(cin, _input); res = solution(_input); cout << res << endl; return 0; }