2022.8.6微软笔试test1

1.xxxx.....xx.....一条路最多能填多少坑，X代表坑，.代表没有坑。
import java.util.*;
class Solution {
    public int solution(String S, int B) {
        // write your code in Java 11 (Java SE 11)
        int N = S.length();
        List<Integer> count = new ArrayList<>();
        int req = 0;
        for (int i = 0; i < N; i++) {
            if(i ==0 && S.charAt(i) == 'x'){
                req++;
                if(i == N-1){
                    count.add(req);
                }
            }else if(i > 0 && S.charAt(i)=='x' && S.charAt(i-1) == 'x'){
                req++;
                if(i == N-1){
                    count.add(req);
                }
            }else if(i > 0 && S.charAt(i)=='x' && S.charAt(i-1) != 'x'){
                req++;
                if(i == N-1){
                    count.add(req);
                }
            }else {
                if(req != 0)count.add(req);
                req = 0;
            }
        }
        if(count.size() == 0){
            return 0;
        }
        Collections.sort(count);
        int res = 0;
        for (int i = count.size()-1; i >=0; i--) {
            if(count.get(i) >= B){
                return B-1 + res ;
            }else{
                B-=(count.get(i)+1);
                res+=count.get(i);
            }
        }
        return res;
    }
}


2.RWWWRRRR白球红球问题，所有红球相邻移动的最大次数，一次只能交换相邻的球
import java.util.*;
class Solution {
    public int solution(String S) {
        // write your code in Java 8 (Java SE 8)
        int RCount = 0;
        for (int i = 0; i < S.length(); i++) {
            if(S.charAt(i)=='R'){
                RCount++;
            }
        }
        if(RCount==1||RCount==0){
            return 0;
        }
        int start = 0, end = S.length() - 1;
        for (int i = 0; i < S.length(); i++) {
            if(S.charAt(i) == 'R'){
                start = i;
                break;
            }
        }
        for (int i = S.length()-1; i >=0; i--) {
            if(S.charAt(i) == 'R'){
                end = i;
                break;
            }
        }
        String s = S.substring(start,end+1);
        int l = 0, r = s.length()-1;
        int lnum = 0, rnum = 0;
        long res = 0;
        while(l<=r){
            if(s.charAt(l) == 'R' && s.charAt(r) == 'R'){
                lnum++;
                rnum++;
                l++;
                r--;
            }else if(s.charAt(l) == 'R' && s.charAt(r) == 'W'){
                lnum++;
                l++;
            }else if(s.charAt(l) == 'W' && s.charAt(r) == 'R'){
                rnum++;
                r--;
            }else {
                if(lnum<=rnum){
                    res+=lnum;
                    l++;
                }else{
                    res+=rnum;
                    r--;
                }
            }
        }
        return res>1000000000?-1:(int)res;
    }
}

3.看病问题，每个病人i有A[i]B[i]两个预约时段，S代表预约时间，判断每个人是不是都能预约上。
import java.util.*;
class Solution {
    public boolean solution(int[] A, int[] B, int S) {
        // write your code in Java 8 (Java SE 8)
        boolean[] dict = new boolean[S];
        for (int i = 0; i < S; i++) {
            dict[i] = true;
        }
        return dfs(dict,A,B,0);
    }
    public static  boolean dfs(boolean[] dict,int[] A, int[] B,int k){
        if(k==A.length){
            return true;
        }
        int a = A[k];
        int b = B[k];
        boolean flag1 = false;
        if(dict[a-1] == true){
            dict[a-1] = false;
            flag1 = dfs(dict,A,B,++k);
            k--;
            dict[a-1] = true;
        }
        boolean flag2 = false;
        if(dict[b-1] == true){
            dict[b-1] = false;
            flag2 = dfs(dict,A,B,++k);
            k--;
            dict[b-1] = true;
        }
        return flag1||flag2;
    }
}
测试用例都过了，给不给面随缘吧~