4AC快手笔试4.12

1. left记录左括号数目，res记录匹配括号对数，right记录右括号数目
2. 遇到左括号left++
3. 遇到右括号：当left不为0，表示匹配，res++，left--；当left为0表示不匹配，right++

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String cals = sc.next();
    sc.close();
    int left = 0, res = 0, right = 0;
    HashSet<Character> khs = new HashSet<>();
    khs.add('(');
    khs.add(')');
    for (int i = 0; i < cals.length(); i++) {
        if(khs.contains(cals.charAt(i))){
            if(cals.charAt(i) == '(') left++;
            else {
                if(left > 0){
                    left--;
                    res++;
                }else {
                    right++;
                }
            }
        }
    }
    System.out.println(res + " " + left + " " + right);
}

第二题

public static int[] GetPowerFactor (int R, int N) {
    // write code here

    if(R == 1) return new int[]{0};
    if(N > R) return new int[0];
    int count = 0, curr = 1;
    while (curr < R){
        curr *= N;
        count++;
    }
    if(curr == R) return new int[]{count};
    curr /= N;
    count--;
    ArrayList<Integer> res = new ArrayList<>();
    while (R >= N){
        boolean added = false;
        if (R >= curr){
            res.add(count);
            R -= curr;
            added = true;
        }
        if(added && R >= curr) return new int[0];
        curr /= N;
        count--;
    }
    if(R > 1) return new int[0];
    else if(R == 1) res.add(0);
    int[] ans = new int[res.size()];
    int j = 0;
    for (int i = res.size() - 1; i >= 0; i--) {
        ans[j++] = res.get(i);
    }
    return ans;
}

第三题

public int[] WaitInLine (int[] a, int[] b) {
    // write code here

    int n = a.length;
    cumer[] cumers = new cumer[n];
    for (int i = 0; i < n; i++) {
        cumers[i] = new cumer(a[i], b[i], i);
    }
    sortQ(cumers, 0, n - 1);
    int[] res = new int[n];
    for (int i = 0; i < n; i++) {
        res[i] = cumers[i].getNum() + 1;    //注意这里需要加1
    }
    return res;
}

private void sortQ(cumer[] cumers, int l, int h) {    //基于类cumer的快排
    if(h <= l) return;
    int j = partition(cumers, l, h);
    sortQ(cumers, l, j - 1);
    sortQ(cumers, j + 1, h);
}

private int partition(cumer[] cumers, int l, int h) {
    int i = l, j = h + 1;
    while (true){
        while (i != h){
            cumer curr = cumers[++i];
            if(curr.getSum() + cumers[l].getSum2() >= curr.getSum2() + cumers[l].getSum()){
                break;
            }
        }
        while (j != l){
            cumer curr = cumers[--j];
            if(curr.getSum() + cumers[l].getSum2() <= curr.getSum2() + cumers[l].getSum()){
                break;
            }
        }
        if(i >= j) break;
        swap(cumers, i, j);
    }
    swap(cumers, l, j);
    return j;
}

private void swap(cumer[] cumers, int i, int j) {
    cumer temp = cumers[i];
    cumers[i] = cumers[j];
    cumers[j] = temp;
}

private class cumer{    //记录顾客满意度用到的类
    private int ai;
    private int bi;
    private int num;
    private int sum;
    private int sum2;

    public cumer(int ai, int bi, int num) {
        this.ai = ai;
        this.bi = bi;
        this.num = num;
        this.sum = ai + bi * 2;
        this.sum2 = ai * 2 + bi * 1;
    }

    public int getNum() { return num; }

    public int getSum() { return sum; }
    public int getSum2() { return sum2; }
}

public int GetMaxStaffs (char[][] pos) {
    // write code here

    int m = pos.length, n = pos[0].length;
    int res = 0;
    map = pos;
    visited = new boolean[m + 1][n + 1];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if(!visited[i][j] && pos[i][j] == '.'){
                count = 0;
                mov(m, n, i, j);
                if(count % 2 == 0) res += (count / 2);
                else res += (count / 2) + 1;
            }else visited[i][j] = true;
        }
    }
    return res;
}
private int count = 0;
private boolean[][] visited = null;
private char[][] map = null;
private void mov(int rows, int cols, int row, int col) {
    if(row >= rows || col >= cols || visited[row][col]) return;
    if(map[row][col] == '*'){
        visited[row][col] = true;
        return;
    }
    visited[row][col] = true;
    char curr = map[row][col];
    count++;
    if(row > 0) mov(rows, cols, row - 1, col);
    if(row < rows - 1) mov(rows, cols, row + 1, col);
    if(col > 0) mov(rows, cols, row, col - 1);
    if(col < cols - 1) mov(rows, cols, row, col + 1);
}