2020快手笔试 4.12
第一题
计算圆括号的配对数、落单左括号数、落单右括号数
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; }
第四题
#快手2020春招笔试##快手##笔试题目#