首页 > 试题广场 >

有长度为length（0length≤100000)的一个

[问答题]

有长度为length（0<length≤100000)的一个括号序列sequence，只有“（”或者“）”两种字符，每个括号的左右两边都能插一个括号，总共有length+1个位置可以插入括号，在第i个位置插入任意括号的代价是cost[i](0<cost[i]≤10000)同一个位置只能插入一个括号，求使得括号序列合法的最小代价，并给出解法的时间复杂度和空间复杂度。

例如输入length=6,sequence="()))((",cost=[1,2,5,5,3,4,1],输出8.

// C/C++
public int getMinimumCost(int length, char[] sequence, int cost[]) {
       // TODO
}

// Java
public int getMinimumCost(int length, List<Character> sequence, List<Integer> cost) {
       //TODO
}

jinyukk

public static int getMininumCost(int length, List<Character> sequence, List<Integer> cost){
        int res = 0;
        boolean[] visited = new boolean[length+1];
        Stack<Integer> stack = new Stack<>();
        for (int i=0;i<sequence.size();i++){
            if (sequence.get(i) == '('){
                stack.push(i); // 插入的是左括号的索引
            }else {
                if (stack.isEmpty())
                    res += minCost(cost,visited,0,i);
                else {
                    stack.pop();
                }
            }
        }
        while (!stack.isEmpty()){
            int start = stack.pop()+1;
            res += minCost(cost,visited,start,length);
        }
        return res;
    }

public static int minCost(List<Integer> cost, boolean[] visited, int start, int end){
    int index = -1, min = Integer.MAX_VALUE;
    for (int i=start;i<=end;i++){
        if (!visited[i]){
            if (cost.get(i) < min){
                min = cost.get(i);
                index = i;
            }
        }
    }
    visited[index] = true;
    return min;
}

编辑于 2019-07-31 17:19:04 回复(0)