2020.08.07 晚上 笔试 1h

1）leetcode 1190 反转每对括号间的子串

import java.util.Stack;

public class Solution {
    public String reverseParentheses(String s) {
        StringBuilder sb = new StringBuilder();
        int n = s.length();
        Stack<Integer> stack = new Stack<>();
        int[] pair = new int[n];

        for (int i = 0; i < n; i++) {
            if(s.charAt(i) == '(') {
                stack.push(i);
            } else if(s.charAt(i) == ')') {
                int j = stack.pop();
                pair[i] = j;
                pair[j] = i;
            }
        }

        for(int i = 0, d = 1; i < n; i += d) {
            if(s.charAt(i) == '(' || s.charAt(i) == ')') {
                i = pair[i];
                d = -d;
            } else {
                sb.append(s.charAt(i));
            }
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        String s = "(u(love)i)";

        System.out.println(new Solution().reverseParentheses(s));
    }
}

2）leetcode 21 合并两个有序链表

public class Solution {
    public static class Node {
        int data;
        Node next;
        public Node(int data) {
            this.data = data;
        }
    }

    public Node mergeTwoLists (Node n1, Node n2) {
        if(n1 == null && n2 == null) {
            return null;
        }

        if(n1 == null) {
            return n2;
        }

        if(n2 == null) {
            return n1;
        }

        Node dummyHead = new Node(0);
        Node p = dummyHead;
        Node p1 = n1;
        Node p2 = n2;

        while (p1 != null && p2 != null) {
            if(p1.data <= p2.data) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }

            p = p.next;
        }

        if(p1 != null) {
            p.next = p1;
        }

        if(p2 != null) {
            p.next = p2;
        }

        return dummyHead.next;
    }

    public static void main(String[] args) {
        Node n1 = new Node(2);
        n1.next = new Node(5);
        n1.next.next = new Node(6);

        Node n2 = new Node(1);
        n2.next = new Node(3);
        n2.next.next = new Node(5);

        Node p = new Solution().mergeTwoLists(n1, n2);
        while(p != null) {
            System.out.print(p.data + " ");
            p = p.next;
        }
    }
}