58同城笔试0920

群友写出来几道，真的废了签到两道都没a出来

第一道 30%

package com.面试中的算法;

import java.util.ArrayList;
import java.util.List;

/**
 * @author
 * @version 1.0
 * @description: TODO
 * @date 2024/9/20 19:45
 */
public class Main {
    public static int[][] findIntersection (int[][] firstList, int[][] secondList) {
        List<int[]> ans=new ArrayList<>();
        int i=0,j=0;
        while(i<firstList.length&&j<secondList.length){
            int[] firtst=firstList[i];
            int[] seconds=secondList[j];
            if(firtst[1]>=seconds[0]&&seconds[1]>=firtst[0]){
                int start=Math.max(firtst[0],seconds[0]);
                int end=Math.max(firtst[1],seconds[1]);
                ans.add(new int[]{start,end});
                if(firtst[1]<seconds[1]){
                    i++;
                }else{
                    j++;
                }
            }else if(firtst[0]>seconds[1]){
                j++;
            }else {
                i++;
            }
        }
        int size=ans.size();
        int[][] res=new int[size][2];
        for (int k = 0; k < size; k++) {
            res[k]=ans.get(k);
        }
        return  res;

        // write code here
    }

    public static void main(String[] args) {
        findIntersection(new int[][]{{1,2},{3,4}},new int[][]{{2,3}});
    }
}

第二道10%

package com.面试中的算法;

/**
 * @author
 * @version 1.0
 * @description: TODO
 * @date 2024/9/20 20:13
 */
public class Mian2 {
    public static int StringSplit (String str) {
        int maxScore = 0;
        int countA = 0, countB = 0;
        for (char c : str.toCharArray()) {
            if (c == 'a') {
                countA++;
            }
        }
        for (int i = 1; i < str.length(); i++) {
            if (str.charAt(i - 1) == 'a') {
                countA--;
            }
            int score = countA + (str.length() - i - (str.substring(i).indexOf('b') == -1 ? 0 : 1) + str.substring(0, i).indexOf('b') == -1 ? 0 : 1);
            int countRight = 0;
            for (int j = i; j < str.length(); j++) {
                if (str.charAt(j) == 'b') {
                    countRight++;
                }
                score = countRight + countA;
                maxScore = Math.max(maxScore, score);

            }


        }
        return maxScore;
    }

}

第三道 ac

package com.面试中的算法;

/**
 * @author
 * @version 1.0
 * @description: TODO
 * @date 2024/9/20 19:58
 */
public class Main3 {
    private static final int MOD = 1000000007;

    public int numberOfWays (int startPos, int endPos, int k) {
        int max=Math.max(startPos,endPos)+k;
        int min=Math.min(startPos,endPos)-k;
        int[][] dp=new int[k+1][max-min+1];
        dp[0][startPos-min]=1;
        for(int i=1;i<=k;i++){
            for(int j=0;j<=max-min;j++){
                int pot=j+min;
                dp[i][j]=0;
                if(j>0){
                    dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD;
                }
                if(j<max-min) dp[i][j]=(dp[i][j]+dp[i-1][j+1])%MOD;
            }
        }
        return dp[k][endPos-min];
        // write code here
    }
}