快手笔试第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);

    }

}

#快手校招##笔试题目##快手#