4AC快手笔试4.12
第三题写比较器的时候卡住了，一二四40分钟写完，第三题写了50分钟。。。改bug还是太菜了
第一题
- left记录左括号数目，res记录匹配括号对数，right记录右括号数目
- 遇到左括号left++
- 遇到右括号：当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);
} 第二题
思路：题目所描述的xx特殊幂，实际上就是R转化为N进制后的表示中不能出现大于1的数，如39转为3进制为111符合，33转为3进制为102不符合
运用类似于十进制转二进制的除二取余法，从大到小减N的k次方，边界条件注意判断即可
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;
} 第三题
思路：一种特殊的排序方式，利用快排，比较器实际上就是比较[(ai1*1+bi1*2)+(ai2*2+bi2*1)]和[(ai1*2+bi1*1)+(ai2*1+bi2*2)]的大小，可以理解为：我只有两组数，第一个中括号表示的是[ai1,ai2],[bi1,bi2]的满意度，第二个中括号表示的是[ai2,ai1],[bi2,bi1]的满意度，将满意度从小到大排序，楼主的比较器用的不熟，所以直接撕了一个快排。
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; }
} 第四题 简单的机器人最大能走过的路径问题BFS/DFS
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);
} 
