携程笔试87%+100%+0%,顺便求第3道答案
1. 链表排序(87%):不知道哪里没考虑到,没ac
static ListNode partition(ListNode head,int m) { if(head == null) { return null; } boolean first = true; ListNode insertNode = head, cur = head, prev = null; while(cur != null) { if(cur.val <= m && cur == head) { // 链表头即满足(不需要移动) first = false; prev = cur; cur = cur.next; }else if(cur.val <= m && first){ // 非链表头,第一次满足条件需要移动 first = false; prev.next = cur.next; cur.next = head; head = cur; insertNode = cur; cur = prev.next; }else if(cur.val <= m) { // 非链表头,非首次满足条件需要移动 prev.next = cur.next; cur.next = insertNode.next; insertNode.next =cur; insertNode = cur; cur = prev.next; }else { // 不满足条件,下一个 prev = cur; cur = cur.next; } } return head; }2. 表达式解析(100%):比较明显的栈使用场景
static String resolve(String expr) { if(expr == null || expr == "") { return ""; } Stack<Character> stack = new Stack<>(); char[] c = expr.toCharArray(); int len = c.length; if(len == 1) { if(c[0] == '(' || c[0] == ')') { return ""; }else { return expr; } } String res = ""; for(int i=0;i<len;i++) { if(c[i] == ')') { // 需要弹栈 String s = ""; while(stack.peek() != '(') { s += stack.pop(); } if(stack.peek() != '(') { return ""; }else { stack.pop(); } if(stack.isEmpty()) { res += s; }else { for(int j=0;j<s.length();j++) { stack.push(s.charAt(j)); } } }else if(c[i] == '(' || !stack.isEmpty()){ stack.push(c[i]); }else{ res += c[i]; } } return stack.isEmpty() ? res : ""; }3.国际惯例第3道时间不够,没想出来也,大佬们有写出来的说说吧😅