快手笔试第1,2,4题答案 4-12下午场B卷
做题的熟练度不够，思路不是特别清晰，代码有很多可以优化的空间
希望大家一起讨论
第一题：数括号数量，用一个栈保存
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s=in.nextLine();
char[] chars=s.toCharArray();
int pair=0;
int l=0;
int r=0;
Deque<Character> stack=new LinkedList<>();
for (int i = 0; i <chars.length ; i++) {
if(chars[i]=='('){
stack.addLast(chars[i]);
}else if(chars[i]==')'){
if(!stack.isEmpty()&&stack.peekLast()=='('){
stack.pollLast();
pair+=1;
}else {
stack.addLast(chars[i]);
}
}
}
for (char c:stack ) {
if(c=='('){
l+=1;
}else if(c==')'){
r+=1;
}
}
StringJoiner sj=new StringJoiner(" ");
sj.add(String.valueOf(pair));
sj.add(String.valueOf(l));
sj.add(String.valueOf(r));
System.out.println(sj.toString());
}
} 第二题：AC，但是代码写的很杂乱 完美数的因子：
例如完美数R=39，底数N=3
39=3^1 + 3^2 +3^3
输出[1,2,3]
public class Solution {
/**
* 返回无重复幂因子的 N进制完美数之和的所有幂因子
* @param R int整型
* @param N int整型 N进制
* @return int整型一维数组
*/
public int[] GetPowerFactor (int R, int N) {
// write code here
List<Integer> res=helper(R,N);
if(res==null){
return new int[0];
}
int[] result=new int[res.size()];
for (int i = 0; i <res.size() ; i++) {
result[i]=res.get(i);
}
return result;
}
public List<Integer> helper (int R, int N){
if(R%N!=0&& (R-1)%N!=0){
return null;
}
List<Integer> res;
if(R==0){
return new ArrayList<>();
}
if((R-1)%N==0){
res=helper(R-1,N);
if(res==null){
return res;
}
res.add(0,0);
return res;
}
if(R%N==0){
res=helper(R/N,N);
if(res==null){
return res;
}
for (int i = 0; i < res.size() ; i++) {
res.set(i,res.get(i)+1);
}
return res;
}
return null;
}
} 第三题： 没有时间做了，希望有大佬能补充思路
第四题：
输入二维数组，找到不相邻位置的数量
类似于8皇后问题，使用回溯法
public class Main4 {
/**
* 获取最大可同事办公员工数
* @param pos char字符型二维数组 工位分布
* @return int整型
*/
int maxNum=0;
int N;
int M;
public int GetMaxStaffs (char[][] pos) {
// write code here
N=pos.length;
M=pos[0].length;
trace(0,pos,new boolean[N][M],0);
return maxNum;
}
public void trace(int p,char[][] pos,boolean[][] bitmap,int num){
if(p>=N*M){
maxNum=Math.max(maxNum,num);
return;
}
// System.out.println(p);
if(pos[p/M][p%M]=='*'){
trace(p+1, pos, bitmap, num);
return;
}
if((p%M>0 && bitmap[p/M][p%M-1]) || (p/M>0&&bitmap[p/M-1][p%M])){
trace(p+1, pos, bitmap, num);
return;
}
boolean[][] bitmap2=new boolean[N][M];
for (int k = 0; k <N; k++) {
bitmap2[k]=bitmap[k].clone();
}
trace(p+1, pos, bitmap2, num);
bitmap[p/M][p%M]=true;
trace(p+1, pos, bitmap, num+1);
}
}