本文FROM 微软 软开 笔试题

题目

您将获得两个银行之间的N次转账列表（编号0到N-1）：银行A和银行B，第K次传输由两个值描述：

• R[K]（A或B）代表收款人（转账发送到的银行）；
• V[K]表示通过传输发送的值。

所有转移均按他们在列表中出现的顺序完成。银行不想负债（即他们的账户余额可能不会低于0）。每家银行的初始账户余额最低是多少才能完成转账？

编写一个函数：

int[] solution(String R, int[] V);

给定一个字符串R和一个长度均为N的整数数组V，返回一个由两个整数组成的数组。证书应按以下顺序表示银行A和B的最小初始账户余额：[银行A, 银行B]。

结果数组应作为整数向量返回。

例子：

1. 给定R = “BAABA”且V=[2,4,1,1,2]，函数应该返回[2, 4]。每次转账后的银行账户余额如下表所示：

	A	B
初始余额	2	4
A -> B：转移 2	0	6
B -> A：转移 4	4	2
B -> A：转移 1	5	1
A -> B：转移 1	4	2
B -> A：转移 2	6	0

1. 给定R = “ABAB”且V=[10,5,10,15]，函数应返回[0, 15]。
2. 给定R = “B”且V=[100]，函数应返回[100, 0]。

为以下假设编写有效算法。

解

以例1为例，设计银行A的初始余额为X，银行B的初始余额为Y。则每一次转账后A的余额分别为：

X-2, X+2, X+3, X+2, X+4；B的余额分别为：

Y+2, Y-2, Y-3, Y-2, Y-4；

根据题目要求得any(X, X-2, X+2, X+3, X+2, X+4) >=0 && any(Y, Y+2, Y-2, Y-3, Y-2, Y-4)>=0

即要求X-2>=0; Y-4>=0;

题目求最小初始余额，可得，X=2； Y=4

下面是代码实现。

Java实现

int[] solution(String R, int[] V) {
    int n = V.length;
    int[] A = new int[n];
    int[] B = new int[n];

    //base case
    if(R.charAt(0) == 'B') {
        B[0] = V[0];
        A[0] = -V[0];
    } else {
        B[0] = -V[0];
        A[0] = V[0];
    }
    int min_A = A[0];
    int min_B = B[0];
    for(int i = 1; i < n; i++) {
        if(R.charAt(i) == 'B') {
            A[i] = A[i-1] - V[i];
            B[i] = B[i-1] + V[i];

        } else {
            A[i] = A[i-1] + V[i];
            B[i] = B[i-1] - V[i];
        }
        min_A = Math.min(min_A, A[i]);
        min_B = Math.min(min_B, B[i]);
    }
    //min_A和min_B不能是负数
    min_A = Math.max(0, -min_A);
    min_B = Math.max(0, -min_B);
    return new int[]{min_A, min_B};
}

参考资料