58同城笔试 - 0920

BraumAce2024年9月21日约 1273 字大约 4 分钟

58同城笔试 - 0920

第一题

题面

我们正在为一个日程安排管理系统开发一个关键功能，在这个系统中，有两个不同的用户群体，分别有他们各自的空闲日程区间列表。
第一个用户群体的空闲日程区间列表记为 firstList，其中 firstList[i] = [start_i, end_i]；
同样地，第二个用户群体的日程区间列表记为 secondList，secondList[j] = [start_j, end_j]。
每个用户群体的日程区间都是成对出现且不相交的，并且两个列表都已经按照时间顺序排好序。

现在，为了找到两个用户群体都有空闲时间可以进行共同活动的时间段，需要设计一个算法来返回这两个日程区间列表的交集，将其找出来以便系统可以安排共同的活动。

请你设计一个高效的算法来解决这个问题。

补充说明：
输入中的每个日程区间为：[start_i, end_i]
题目确保： $0 < start_i < end_i < start_{i+1} < 10000$

示例：

输入：[[0,3],[5,9],[11,13]],[[2,6],[8,10]]
输出：[[2,3],[5,6],[8,9]]

思路与代码

双指针遍历两个列表，找到它们的共同交集。

import java.util.*;

public class Solution {
    public List<int[]> findFreeTimeIntersections(int[][] firstList, int[][] secondList) {
        List<int[]> res = new ArrayList<>();
        int i = 0, j = 0;
        
        while (i < firstList.length && j < secondList.length) {
            int s_i = firstList[i][0], e_i = firstList[i][1];
            int s_j = secondList[j][0], e_j = secondList[j][1];
            
            if (e_i < s_j) {
                i++;
            } else if (e_j < s_i) {
                j++;
            } else {
                int start = Math.max(s_i, s_j);
                int end = Math.min(e_i, e_j);
                result.add(new int[]{start, end});
                
                if (e_i < e_j) {
                    i++;
                } else {
                    j++;
                }
            }
        }
        
        return res;
    }
}

第二题

题面

给你一个由若干 a 和 b 组成的字符串 $s$ ，请你计算并返回将该字符串分割成两个非空子字符串（即左子字符串和右子字符串）所能获得的最大得分。

「分割字符串的得分」为左子字符串中 a 的数量加上右子字符串中 b 的数量。

补充说明：
$2 \leq s.length \leq 500$
字符串 $s$ 仅由字符 a 和 b 组成。

示例：

输入：abbbab
输出：5
说明：将字符串 s 划分为两个非空子字符串的可行方案：
      左子字符串 = "a" 且 右子字符串 = "bbbab"，得分 = 1 + 4 = 5
      左子字符串 = "ab" 且 右子字符串 = "bbab"，得分 = 1 + 3 = 4
      左子字符串 = "abb" 且 右子字符串 = "bab"，得分 = 1 + 2 = 3
      左子字符串 = "abbb" 且 右子字符串 = "ab"，得分 = 1 + 1 = 2
      左子字符串 = "abbba" 且 右子字符串 = "b"，得分 = 2 + 1 = 3
      最大得分为5

思路与代码

直接遍历即可。

public class Solution {
    public int maxScore(String str) {
        int sumA = 0, sumB = 0;
        for (char c : str.toCharArray()) {
            if (c == 'a') sumA++;
            else sumB++;
        }
        
        int ans = 0;
        int leftA = 0, leftB = 0;
        
        for (int i = 0; i < str.length() - 1; i++) {
            if (str.charAt(i) == 'a') leftA++;
            else leftB++;
            
            int rightB = sumB - leftB;
            int res = leftA + rightB;
            ans = Math.max(ans, res);
        }
        
        return ans;
    }
}

第三题

题面

最初，你站在无限数轴上位置 startPos 处。
给你两个正整数 startPos 和 endPos 。
在一次移动中，你可以向左或者向右移动一个位置。
给你一个正整数 $k$ ，返回从 startPos 出发，恰好移动 $k$ 步并到达 endPos 的不同方法数目。

答案可能会很大，返回对 $10^9 + 7$ 取余的结果。
如果所执行移动的顺序不完全相同，则认为两种方法不同。
注意：数轴包含负整数。

补充说明：
$1 \leq startPos, endPos, k \leq 1000$

示例：

输入：1,2,3
输出：3
说明：存在 3 种从 1 到 2 且恰好移动 3 步的方法：
      1 -> 2 -> 3 -> 2.
      1 -> 2 -> 1 -> 2.
      1 -> 0 -> 1 -> 2.

思路与代码

尝试用数学的方法，通过计算 $C^m_n$ 求解，但只能过 $54.44\%$ 。

于是采用动态规划求解。

定义一个二维DP数组，其中 dp[i][j] 表示从起点移动 $i$ 步到达位置 $j$ 的不同方法数。通过分析每一步的移动情况，我们可以得出状态转移方程，然后逐步计算出最终结果。

步骤：

初始化DP数组 dp[k + 1][maxPos - minPos + 1]，其中 maxPos 和 minPos 是可能达到的最远和最近的位置。
设置初始状态：dp[0][startPos - minPos] = 1，表示一开始在起点的方法数为 $1$ 。
遍历步数 $i$ $i$ 从 $1$ $1$ 到 $k$ $k$ ：
- 对于每个可能的位置 $j$ ，计算 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]，表示到达 $j$ 的方法数等于从 $j - 1$ 向右移动和从 $j + 1$ 向左移动的方法数之和
- 最终结果为 dp[k][endPos - minPos]
所有计算过程中都需要对 $10^9 + 7$ 取模，防止溢出

class Solution {
    public int numberOfWays(int startPos, int endPos, int k) {
        final int mod = 1000000007;
        int maxPos = Math.max(startPos, endPos) + k;
        int minPos = Math.min(startPos, endPos) - k;
        int offset = -minPos;
        
        long[][] dp = new long[k + 1][maxPos - minPos + 1];
        dp[0][startPos + offset] = 1;
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                if (j > 0) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % mod;
                }
                if (j < dp[i].length - 1) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % mod;
                }
            }
        }
        
        return (int) dp[k][endPos + offset];
    }
}