第一题

计算圆括号的配对数、落单左括号数、落单右括号数

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str = sc.next();
    Stack<Character> stack = new Stack<>();
    //遇到左括号进入，遇到右括号弹出
    int pairnum = 0,leftnum = 0,rightnum = 0;
    for(int i = 0;i<str.length();i++){
      if(str.charAt(i) == '('){
        stack.push('(');
      }else if(str.charAt(i) == ')'){
        if(!stack.isEmpty()) {
          stack.pop();
          pairnum++;
        }else {
          rightnum++;
        }
      }
    }
    leftnum = stack.size();
    System.out.printf("%d %d %d\n",pairnum,leftnum,rightnum);
  }

第二题

通过样例 66.7%

public static List<Integer> GetPower (int R, int N) {
    // write code here
    List<Integer> list = new ArrayList<>();
    int tempR = R,k =0;
    while (tempR%N == 0){
      tempR /= N;
      k++;
    }
    //如果R是整数幂
    if((int)Math.pow(N,k) == R){
      list.add(k);
      return list;
    }
    //27 3 3
    //如果R不是整数幂
    int i = 0;
    int tempval = (int)Math.pow(N,i);
    while(tempval < R) {
      List<Integer> templist = GetPower(R - tempval,N);
      if(!templist.isEmpty()&&!templist.contains(i)) {
        templist.add(i);
        return templist;
      }
      i++;
      tempval = (int)Math.pow(N,i);
    }
    return list;
  }

  public static int[] GetPowerFactor (int R, int N) {
    // write code here
    List<Integer> list = GetPower(R,N);
    if(list.isEmpty()){
      return null;
    }
    int[] result = new int[list.size()];
    int k = 0;
    for(Integer val:list){
      result[k++] = val;
    }
    Arrays.sort(result);
    return result;
  }

第三题

通过样例 20%

//重新安排每个顾客的位置，使得顾客不满意度最小
  //n个顾客，ai * (j-1) + bi * (n-j)
  public int[] WaitInLine (int[] a, int[] b) {
    // write code here
    //动态规划，如果n-1确定了，
    //dp[i] = dp[i-1] + min();
    //如何从i-1到i
    //首先按照每个位置选当前最小
    //如果该最小已选，需要考虑是否替换成第2小
    int n = a.length;
    int[] result = new int[n];
    //int[] secondminresult = new int[n];
    if(n == 1){
      result[0] = 1;
      return result;
    }
    //int r = 0;
    Set<Integer> myset = new HashSet<>();
    for(int i=1;i<=n;i++){
      int min = Integer.MAX_VALUE;
      int mini = -1;
      int secondmin = Integer.MAX_VALUE;
      int secondmini = -1;
      //按照每个位置选当前最小
      for(int j=0;j < n;j++){
        int temp = a[j] * (i-1) + b[j] * (n-i);
        if(temp < min){
          min = temp;
          mini = j;
        }
        else if(temp < secondmin){
          secondmin = temp;
          secondmini = j;
        }
      }
      //secondminresult[i] = secondmini;
      if(myset.contains(mini)){
        //交换计算代价
        //如果该最小已选，需要考虑是否替换成第2小
        //替换为第2小
//       int cost1 = a[secondmini] * (i-1) + b[secondmini] * (n-i);
//
//       //置换为第1小
//       int cost2 = 0;
//
//       if(cost1 <= cost2){
         result[i - 1] = secondmini;
//       }else {
//         //交换
//         result[i-1] = mini;
//       }
      }else {
        result[i - 1] = mini;
      }

    }
    return result;
  }

第四题