春招笔试总结

第一场笔试，后面做的懒得记录了

加油站

leetcode 原题，不过我没有做到过：https://leetcode.cn/problems/gas-station/description/

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

solution

思路很简单，直接贪心，先两个数组做差，算出每个点到下一个点的油量变化，然后遍历数组，从第一个正值开始，依次累加，当累加变成负值就继续找下一个正值。

遍历完如果最后累加结果是负值，说明找不到，直接返回 -1，如果为正值，就考虑把开始计算的节点前的所有盈亏加起来（因为是要跑一个环形）和 0 比较即可

所以其实是找到一个位置，使得左边的和与右边（包括当前点）的和相加 > 0，同时保证右边的子数组的前缀和不能有小于零的

做了两题发现可以用 C#，后面都是直接写 C# 了

输入按照实际笔试中的来写

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
	public static void Main(string[] args)
    {
		var n = int.Parse(Console.ReadLine());
        var gas = Console.ReadLine().Split().Select(int.Parse);
        var cost = Console.ReadLine().Split().Select(int.Parse);
        var sub = gas.Zip(cost, (g, c) => g - c).ToList();
        var start = -1;
        var leftSum = 0;
        var sum = 0;
        for (int i = 0; i < n; ++i) {
            var s = sub[i];
            if (s >= 0 && start == -1) {
                start = i;
                leftSum += sum;
                sum = s;
            } else {
                sum += s;
                if (sum < 0) start = -1;
            }
            if (i < start) leftSum += s;
        }
        if (leftSum + sum < 0) start = -1;
        return start;
    }
}

other

第四题样例没有全部通过，思路还是贪心。

题目大意：

给出 a b c 并且构造一个 nums 数组，要求满足：

• nums.length = a

• 0 <= a <= c <= 1e9

• nums[i] 是正整数（0 <= i < a ）

• abs(nums[i] - nums[i+1]) <= 1 (0 <= i < a - 1)

• 0 <= b < a

• 使得 nums[b] 最大

• sum(nums) <= c

最后返回 nums[b]

要找到符合全部要求的 nums，首先考虑极端情况，也就是从 b 位置开始，往两侧依次递减到 1，类似这种形状的数组 [1, 1, 2, 3, 2]， 在这种情况下，所有数值的和一定是最小的。

所以可以计算 x = b 处的 y_b 的值的范围，从大到小遍历，依次构造相应的函数 f(x) 并且判断其积分 F(x) <= c，返回第一个符合题意的 y_b 即可。

实际做的时候因为计算面积导致数量级会达到 1e18，超过了 int 的上限。（下次一定记得换 long）

然后如果 c 远远大于 a，就会导致遍历很久，所以我们根据差值来逼近目标值。

一个可能的解法（本地测了一些样例， 不确定行不行）：

public static void Main(string[] args)
{
    var abc = Console.ReadLine()!.Split().Select(long.Parse).ToArray();
    var (a, b, c) = (abc[0], abc[1], abc[2]);
    var maxNumsB = c - a + 1;
    for (var i = maxNumsB; i >= 1; i--)
    {
        var totalS = Calc(a, b, i);
        if (totalS <= c)
        {
            Console.WriteLine(i);
            return;
        }
        // approaching the target based on the difference
        var delta = totalS - c;
        i -= delta / (a + 1);
    }
}

public static long Calc(long a, long b, long y)
{
    // 0 <= b < a
    // calculate left triangle and right triangle (or trapezoid)
    // left is f(x) = x + r (y = b + r => r = y - b), so get f(x) = x + y - b
    var leftX = y - 1 > b ? 0 : b - y + 1;
    var leftY = leftX + y - b;
    // right is f(x) = -x + r (y = -b + r => r = y + b), so get f(x) = -x + y + b
    var rightX = y + b < a ? y - 1 + b : a - 1;
    var rightY = -rightX + y + b;
    // S = (Y + y) * abs(b - X) / 2
    // and add rest of the area (always 1)
    var leftS = (leftY + y) * (b - leftX + 1) / 2 + leftX;
    var rightS = (rightY + y) * (rightX - b + 1) / 2 + (a - rightX - 1);
    var totalS = leftS + rightS - y;
    // Console.WriteLine($"{y}: {leftX}, {leftY}, {rightX}, {rightY}, {leftS}, {rightS}, {totalS}");
    return totalS;
}