2023.9.16 58同城笔试

第一题

//通过80%
 public class Solution {
        public int calculate(int m, int n, int[] scores) {
            Arrays.sort(scores); // 将项目组得分排序
            int left = 0;
            int right = scores[scores.length - 1];
            int result = -1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                int aboveCount = countAbove(scores, mid);

                if (aboveCount >= m && aboveCount <= n&& scores.length-aboveCount>=m&&l-aboveCount<=n) {
                    result = mid; // 找到一个可能的分数线
                    right = mid - 1; // 继续搜索更低的分数线
                } else if (aboveCount < m) {
                    right = mid - 1; // 分数线太低，增加分数线
                } else {
                    left = mid + 1; // 分数线太高，降低分数线
                }OK
            }

            return result;
        }

        private int countAbove(int[] scores, int target) {
            int count = 0;
            for (int score : scores) {
                if (score > target) {
                    count++;
                }
                
            }
            return count;
        }
    }

第二题

//通过85%
import java.util.Arrays;

public class Solution {
    public int maximumScore(int[] nums, int k) {
         Arrays.sort(nums);
        int n = nums.length;
        int maxScore = 0;

        for (int i = 0; i < n; i++) {
            int lowerBound = nums[i] - k;
            int upperBound = nums[i] + k;
            int count = 0;

            for (int j = 0; j < n; j++) {
                if (nums[j] >= lowerBound && nums[j] <= upperBound) {
                    count++;
                }
            }

            maxScore = Math.max(maxScore, count);
        }

        return maxScore;
    }
}

第三题

//通过100%
public class Solution {
    public int subsequence(String source, String pattern) {
        int sourceLen = source.length();
        int patternLen = pattern.length();

        // 创建一个二维数组dp，dp[i][j]表示source的前i个字符中与pattern的前j个字符匹配的子序列数量
        int[][] dp = new int[sourceLen + 1][patternLen + 1];

        // 初始化dp数组
        for (int i = 0; i <= sourceLen; i++) {
            dp[i][0] = 1; // 空字符串是任何字符串的子序列
        }

        // 填充dp数组
        for (int i = 1; i <= sourceLen; i++) {
            for (int j = 1; j <= patternLen; j++) {
                if (source.charAt(i - 1) == pattern.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[sourceLen][patternLen];
    }
}