MS simulated written test

Tips ： When the article is finished , Directories can be generated automatically , How to generate it, please refer to the help document on the right

---

Preface

       This article records the answers of the written examination ：

One 、 Delete... From the string BALLON

	public int solution(String S) {
    
        // write your code in Java SE 11
        int[] v=new int[26];
        for(int i=0;i<S.length();i++)
            v[S.charAt(i)-'A']++;
        String ss="BALLOON";
        int res=0;
        while(true){
    
            boolean is=false;
            for(int i=0;i<ss.length();i++){
    
                if(v[ss.charAt(i)-'A']<=0){
    
                    is=true;
                    break;
                }
                else
                    v[ss.charAt(i)-'A']--;
            }
            if(is)
                break;
            res++;
        }
        return res;
    }

Two 、 Ask for two frog The longest distance of

 	public int solution(int[] blocks) {
    
        // write your code in Java SE 11
        int len=blocks.length;
        ArrayList<int[]> dp=new ArrayList<>(); // index , ld, rd
        int i=0,j=0;
        for(i=0;i<len;i++)
            dp.add(new int[]{
    i,0,0});

        dp.get(0)[1]=ld(blocks,0);
        for(i=1;i<len;i++){
    
            if(blocks[i]<=blocks[i-1])
                dp.get(i)[1]=dp.get(i-1)[1];
            else
                dp.get(i)[1]=ld(blocks,i);
        }

        dp.get(len-1)[2]=rd(blocks,len-1);
        for(i=len-2;i>=0;i--){
    
            if(blocks[i]<=blocks[i+1])
                dp.get(i)[2]=dp.get(i+1)[2];
            else
                dp.get(i)[2]=rd(blocks,i);
        }
        for(i=0;i<len;i++)
            j=Math.max(dp.get(i)[2]-dp.get(i)[1]+1,j);
        return j;
    }
    private int ld(int[] b,int i){
    
        int tmp=i-1;
        while(tmp>=0){
    
            if(b[tmp]>=b[i])
                tmp--;
            else
                break;
        }
        return tmp+1;
    }
    private int rd(int[] b,int i){
    
        int tmp=i+1;
        while(tmp<b.length){
    
            if(b[tmp]>=b[i])
                tmp++;
            else
                break;
        }
        return tmp-1;
    }

       Where the above code needs to be optimized ：
One 、dp.get(i)[1]=ld(blocks,i); and dp.get(i)[2]=rd(blocks,i); The values on the right can be directly changed to i .
Two 、dp Inside the triples It can be changed to Binary ,dp.get(0) You can get rid of .

3、 ... and 、 Judge the line formed by some points in the two-dimensional coordinates , The sum of the number of combinations of three points .

class Point2D{
    
    public int x,y;
    Point2D(int i,int j){
    
        x=i;
        y=j;
    }
}
public class Solution {
    
    public int solution(Point2D[] A) {
    
// write your code in Java SE 11
//  Two points form a line 
//
//  Take it out first   Positive infinity and negative infinity   That is horizontal and vertical .
        HashMap<String,Integer> Straights=new HashMap<>();
        HashMap<Integer,Integer> xs=new HashMap<>();
        HashMap<Integer,Integer> ys=new HashMap<>();

        int i=0,j=0,len=A.length;
        int MAX=100000000;
        for(i=0;i<len;i++){
    
            int x=A[i].x,y=A[i].y;
            xs.put(x,xs.getOrDefault(x,0)+1);
            ys.put(y,ys.getOrDefault(y,0)+1);
        }
        int res=0;
        for(int value:xs.values()){
    
            res+=getNum(value);
            if(res>MAX)
                return -1;
        }
        for(int value:ys.values()) {
    
            res+=getNum(value);
            if(res>MAX)
                return -1;
        }
        HashMap<String,HashSet<Point2D>> visited=new HashMap<>();

        for(i=0;i<len;i++){
    
            Point2D point=A[i];
            for(j=i+1;j<len;j++){
    
                Point2D point2=A[j];
                int y=point2.y-point.y;
                int x=point2.x-point.x;
                if(y==0||x==0)
                    continue;
                Double d= (double) (y);
                Double d1= (double) (x);
                double t=d/d1;
                double b= point.y-point.x*t;
                String s= Double.toString(t);
                s+=Double.toString(b);
                Straights.put(s,0); //  Number of straight lines .

                visited.put(s,new HashSet<>());
            }
        }


        for(i=0;i<len;i++){
    
            Point2D point=A[i];
            for(j=i+1;j<len;j++){
    
                Point2D point2=A[j];
                int y=point2.y-point.y;
                int x=point2.x-point.x;
                if(y==0||x==0)
                    continue;
                Double d= (double) (y);
                Double d1= (double) (x);
                double t=d/d1;
                String s= Double.toString(t);
                double b= point.y-point.x*t;
                s+=Double.toString(b);

                if(!visited.get(s).contains(point)){
    
                    Straights.put(s,Straights.get(s)+1);
                    visited.get(s).add(point);
                }

                if(!visited.get(s).contains(point2)){
    
                    Straights.put(s,Straights.get(s)+1);
                    visited.get(s).add(point2);
                }
            }
        }

        for(int value:Straights.values()){
    
            res+=getNum(value);
            if(res>MAX)
                return -1;
        }
        return res;
    }
    private int getNum(int nums){
    
        if(nums<2)
            return 0;
        if(nums==3)
            return 1;
        int tmp=nums*(nums-1)*(nums-2);
        return tmp/6;
    }
    public static void main(String[] args) {
    
        Solution s=new Solution();
        Point2D[] A={
    new Point2D(0,0),new Point2D(1,1),new Point2D(2,2),new Point2D(3,3),new Point2D(3,2)
                ,new Point2D(4,2),new Point2D(5,1)};
        int r=s.solution(A);
        System.out.println(r);
    }
}

---

summary

       I'll add later