方法一：哈希表

使用哈希表统计 $\textit{nums}$ 中出现了两次的数字，返回结果。

###C++

class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums) {
        vector<int> res;
        unordered_map<int, int> count;
        for (int x : nums) {
            count[x]++;
            if (count[x] == 2) {
                res.push_back(x);
            }
        }
        return res;
    }
};

###Go

func getSneakyNumbers(nums []int) []int {
    res := []int{}
    count := make(map[int]int)
    for _, x := range nums {
        count[x]++
        if count[x] == 2 {
            res = append(res, x)
        }
    }
    return res
}

###Python

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        res = []
        count = {}
        for x in nums:
            count[x] = count.get(x, 0) + 1
            if count[x] == 2:
                res.append(x)
        return res

###Java

class Solution {
    public int[] getSneakyNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) {
            count.put(x, count.getOrDefault(x, 0) + 1);
            if (count.get(x) == 2) {
                res.add(x);
            }
        }
        return res.stream().mapToInt(i -> i).toArray();
    }
}

###TypeScript

function getSneakyNumbers(nums: number[]): number[] {
    const res: number[] = [];
    const count = new Map<number, number>();
    for (const x of nums) {
        count.set(x, (count.get(x) || 0) + 1);
        if (count.get(x) === 2) {
            res.push(x);
        }
    }
    return res;
}

###JavaScript

var getSneakyNumbers = function(nums) {
    const res = [];
    const count = new Map();
    for (const x of nums) {
        count.set(x, (count.get(x) || 0) + 1);
        if (count.get(x) === 2) {
            res.push(x);
        }
    }
    return res;
};

###C#

public class Solution {
    public int[] GetSneakyNumbers(int[] nums) {
        List<int> res = new List<int>();
        Dictionary<int, int> count = new Dictionary<int, int>();
        foreach (int x in nums) {
            if (!count.ContainsKey(x)) count[x] = 0;
            count[x]++;
            if (count[x] == 2) {
                res.Add(x);
            }
        }
        return res.ToArray();
    }
}

###C

int* getSneakyNumbers(int* nums, int numsSize, int* returnSize) {
    int* res = (int*)malloc(2 * sizeof(int));
    int* count = (int*)calloc(101, sizeof(int));
    *returnSize = 0;
    for (int i = 0; i < numsSize; i++) {
        int x = nums[i];
        count[x]++;
        if (count[x] == 2) {
            res[(*returnSize)++] = x;
        }
    }
    free(count);
    return res;
}

###Rust

impl Solution {
    pub fn get_sneaky_numbers(nums: Vec<i32>) -> Vec<i32> {
        let mut res = Vec::new();
        let mut count = std::collections::HashMap::new();
        for x in nums {
            let c = count.entry(x).or_insert(0);
            *c += 1;
            if *c == 2 {
                res.push(x);
            }
        }
        res
    }
}

复杂度分析

• 时间复杂度：$O(n)$。

• 空间复杂度：$O(n)$。

方法二：位运算

我们将 $\textit{nums}$ 的所有数字和 $0$ 到 $n - 1$ 的所有数字进行异或，那么计算结果为两个额外多出现一次的数字的异或值 $y$。那么两个数字最低不相同的位为 $\textit{lowBit} = y \land -y$，利用 $\textit{lowBit}$ 将 $\textit{nums}$ 的所有数字和 $0$ 到 $n - 1$ 的所有数字分成两部分，然后分别计算这两部分数字的异或值，即为结果。

###C++

class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums) {
        int n = (int)nums.size() - 2;
        int y = 0;
        for (int x : nums) {
            y ^= x;
        }
        for (int i = 0; i < n; i++) {
            y ^= i;
        }
        int lowBit = y & (-y);
        int x1 = 0, x2 = 0;
        for (int x : nums) {
            if (x & lowBit) {
                x1 ^= x;
            } else {
                x2 ^= x;
            }
        }
        for (int i = 0; i < n; i++) {
            if (i & lowBit) {
                x1 ^= i;
            } else {
                x2 ^= i;
            }
        }
        return {x1, x2};
    }
};

###Go

func getSneakyNumbers(nums []int) []int {
    n := len(nums) - 2
    y := 0
    for _, x := range nums {
        y ^= x
    }
    for i := 0; i < n; i++ {
        y ^= i
    }
    lowBit := y & -y
    x1, x2 := 0, 0
    for _, x := range nums {
        if x&lowBit != 0 {
            x1 ^= x
        } else {
            x2 ^= x
        }
    }
    for i := 0; i < n; i++ {
        if i&lowBit != 0 {
            x1 ^= i
        } else {
            x2 ^= i
        }
    }
    return []int{x1, x2}
}

###Python

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums) - 2
        y = 0
        for x in nums:
            y ^= x
        for i in range(n):
            y ^= i
        lowBit = y & -y
        x1 = x2 = 0
        for x in nums:
            if x & lowBit:
                x1 ^= x
            else:
                x2 ^= x
        for i in range(n):
            if i & lowBit:
                x1 ^= i
            else:
                x2 ^= i
        return [x1, x2]

###Java

class Solution {
    public int[] getSneakyNumbers(int[] nums) {
        int n = nums.length - 2;
        int y = 0;
        for (int x : nums) {
            y ^= x;
        }
        for (int i = 0; i < n; i++) {
            y ^= i;
        }
        int lowBit = y & -y;
        int x1 = 0, x2 = 0;
        for (int x : nums) {
            if ((x & lowBit) != 0) {
                x1 ^= x;
            } else {
                x2 ^= x;
            }
        }
        for (int i = 0; i < n; i++) {
            if ((i & lowBit) != 0) {
                x1 ^= i;
            } else {
                x2 ^= i;
            }
        }
        return new int[]{x1, x2};
    }
}

###TypeScript

function getSneakyNumbers(nums: number[]): number[] {
    const n = nums.length - 2;
    let y = 0;
    for (const x of nums) {
        y ^= x;
    }
    for (let i = 0; i < n; i++) {
        y ^= i;
    }
    const lowBit = y & -y;
    let x1 = 0, x2 = 0;
    for (const x of nums) {
        if (x & lowBit) {
            x1 ^= x;
        } else {
            x2 ^= x;
        }
    }
    for (let i = 0; i < n; i++) {
        if (i & lowBit) {
            x1 ^= i;
        } else {
            x2 ^= i;
        }
    }
    return [x1, x2];
}

###JavaScript

function getSneakyNumbers(nums) {
    const n = nums.length - 2;
    let y = 0;
    for (const x of nums) {
        y ^= x;
    }
    for (let i = 0; i < n; i++) {
        y ^= i;
    }
    const lowBit = y & -y;
    let x1 = 0, x2 = 0;
    for (const x of nums) {
        if (x & lowBit) {
            x1 ^= x;
        } else {
            x2 ^= x;
        }
    }
    for (let i = 0; i < n; i++) {
        if (i & lowBit) {
            x1 ^= i;
        } else {
            x2 ^= i;
        }
    }
    return [x1, x2];
}

###C#

public class Solution {
    public int[] GetSneakyNumbers(int[] nums) {
        int n = nums.Length - 2;
        int y = 0;
        foreach (int x in nums) {
            y ^= x;
        }
        for (int i = 0; i < n; i++) {
            y ^= i;
        }
        int lowBit = y & -y;
        int x1 = 0, x2 = 0;
        foreach (int x in nums) {
            if ((x & lowBit) != 0) {
                x1 ^= x;
            } else {
                x2 ^= x;
            }
        }
        for (int i = 0; i < n; i++) {
            if ((i & lowBit) != 0) {
                x1 ^= i;
            } else {
                x2 ^= i;
            }
        }
        return new int[] { x1, x2 };
    }
}

###C

int* getSneakyNumbers(int* nums, int numsSize, int* returnSize) {
    int n = numsSize - 2;
    int y = 0;
    for (int i = 0; i < numsSize; i++) {
        y ^= nums[i];
    }
    for (int i = 0; i < n; i++) {
        y ^= i;
    }
    int lowBit = y & -y;
    int x1 = 0, x2 = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] & lowBit) {
            x1 ^= nums[i];
        } else {
            x2 ^= nums[i];
        }
    }
    for (int i = 0; i < n; i++) {
        if (i & lowBit) {
            x1 ^= i;
        } else {
            x2 ^= i;
        }
    }
    int* res = (int*)malloc(2 * sizeof(int));
    res[0] = x1;
    res[1] = x2;
    *returnSize = 2;
    return res;
}

###Rust

impl Solution {
    pub fn get_sneaky_numbers(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len() as i32 - 2;
        let mut y = 0;
        for &x in &nums {
            y ^= x;
        }
        for i in 0..n {
            y ^= i;
        }
        let low_bit = y & -y;
        let mut x1 = 0;
        let mut x2 = 0;
        for &x in &nums {
            if x & low_bit != 0 {
                x1 ^= x;
            } else {
                x2 ^= x;
            }
        }
        for i in 0..n {
            if i & low_bit != 0 {
                x1 ^= i;
            } else {
                x2 ^= i;
            }
        }
        vec![x1, x2]
    }
}

复杂度分析

• 时间复杂度：$O(n)$。

• 空间复杂度：$O(1)$。

方法三：数学

令两个额外多出现一次的数字为 $x_1$ 和 $x_2$。$\textit{nums}$ 的和与平方和分别为 $\textit{sum}$ 和 $\textit{squaredSum}$，从 $0$ 到 $n-1$ 的整数和与平方和分别为 $\frac{n(n-1)}{2}$ 和 $\frac{n(n-1)(2n-1)}{6}$。记 $\textit{sum}_2 = \textit{sum} - \frac{n(n-1)}{2}$ 和 $\textit{squaredSum}_2 = \textit{squaredSum} - \frac{n(n-1)(2n-1)}{6}$，那么有以下方程：

$$
\begin{cases}
x_1 + x_2 = \textit{sum}_2 \
x_1^2 + x_2^2 = \textit{squaredSum}_2
\end{cases}
$$

解得：

$$
\begin{cases}
x_1 = \frac{\textit{sum}_2 - \sqrt{2 \times \textit{squaredSum}_2 - \textit{sum}_2^2}}{2} \
x_2 = \frac{\textit{sum}_2 + \sqrt{2 \times \textit{squaredSum}_2 - \textit{sum}_2^2}}{2}
\end{cases}
$$

###C++

class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums) {
        int n = (int)nums.size() - 2;
        int sum = 0, squaredSum = 0;
        for (int x : nums) {
            sum += x;
            squaredSum += x * x;
        }
        int sum2 = sum - n * (n - 1) / 2;
        int squaredSum2 = squaredSum - n * (n - 1) * (2 * n - 1) / 6;
        int x1 = (sum2 - sqrt(2 * squaredSum2 - sum2 * sum2)) / 2;
        int x2 = (sum2 + sqrt(2 * squaredSum2 - sum2 * sum2)) / 2;
        return {x1, x2};
    }
};

###Go

func getSneakyNumbers(nums []int) []int {
    n := len(nums) - 2
    sum, squaredSum := 0.0, 0.0
    for _, x := range nums {
        sum += float64(x)
        squaredSum += float64(x * x)
    }
    sum2 := sum - float64(n * (n - 1) / 2)
    squaredSum2 := squaredSum - float64(n * (n - 1) * (2 * n - 1) / 6)
    x1 := (sum2 - math.Sqrt(2 * squaredSum2 - sum2 * sum2)) / 2
    x2 := (sum2 + math.Sqrt(2 * squaredSum2 - sum2 * sum2)) / 2
    return []int{int(x1), int(x2)}
}

###Python

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums) - 2
        sum_ = sum(nums)
        squared_sum = sum(x*x for x in nums)
        sum2 = sum_ - n*(n-1)//2
        squared_sum2 = squared_sum - n*(n-1)*(2*n-1)//6
        x1 = (sum2 - math.sqrt(2*squared_sum2 - sum2*sum2)) / 2
        x2 = (sum2 + math.sqrt(2*squared_sum2 - sum2*sum2)) / 2
        return [int(x1), int(x2)]

###Java

class Solution {
    public int[] getSneakyNumbers(int[] nums) {
        int n = nums.length - 2;
        double sum = 0, squaredSum = 0;
        for (int x : nums) {
            sum += x;
            squaredSum += x * x;
        }
        double sum2 = sum - n * (n - 1) / 2.0;
        double squaredSum2 = squaredSum - n * (n - 1) * (2 * n - 1) / 6.0;
        int x1 = (int)((sum2 - Math.sqrt(2 * squaredSum2 - sum2 * sum2)) / 2);
        int x2 = (int)((sum2 + Math.sqrt(2 * squaredSum2 - sum2 * sum2)) / 2);
        return new int[]{x1, x2};
    }
}

###TypeScript

function getSneakyNumbers(nums: number[]): number[] {
    const n = nums.length - 2;
    let sum = 0, squaredSum = 0;
    for (const x of nums) {
        sum += x;
        squaredSum += x * x;
    }
    const sum2 = sum - n * (n - 1) / 2;
    const squaredSum2 = squaredSum - n * (n - 1) * (2 * n - 1) / 6;
    const x1 = (sum2 - Math.sqrt(2 * squaredSum2 - sum2 * sum2)) / 2;
    const x2 = (sum2 + Math.sqrt(2 * squaredSum2 - sum2 * sum2)) / 2;
    return [Math.floor(x1), Math.floor(x2)];
}

###JavaScript

function getSneakyNumbers(nums) {
    const n = nums.length - 2;
    let sum = 0, squaredSum = 0;
    for (const x of nums) {
        sum += x;
        squaredSum += x * x;
    }
    const sum2 = sum - n * (n - 1) / 2;
    const squaredSum2 = squaredSum - n * (n - 1) * (2 * n - 1) / 6;
    const x1 = (sum2 - Math.sqrt(2 * squaredSum2 - sum2 * sum2)) / 2;
    const x2 = (sum2 + Math.sqrt(2 * squaredSum2 - sum2 * sum2)) / 2;
    return [Math.floor(x1), Math.floor(x2)];
}

###C#

public class Solution {
    public int[] GetSneakyNumbers(int[] nums) {
        int n = nums.Length - 2;
        double sum = 0, squaredSum = 0;
        foreach (int x in nums) {
            sum += x;
            squaredSum += x * x;
        }
        double sum2 = sum - n * (n - 1) / 2.0;
        double squaredSum2 = squaredSum - n * (n - 1) * (2 * n - 1) / 6.0;
        int x1 = (int)((sum2 - Math.Sqrt(2 * squaredSum2 - sum2 * sum2)) / 2);
        int x2 = (int)((sum2 + Math.Sqrt(2 * squaredSum2 - sum2 * sum2)) / 2);
        return new int[]{x1, x2};
    }
}

###C

int* getSneakyNumbers(int* nums, int numsSize, int* returnSize) {
    int n = numsSize - 2;
    double sum = 0, squaredSum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
        squaredSum += nums[i] * nums[i];
    }
    double sum2 = sum - n * (n - 1) / 2.0;
    double squaredSum2 = squaredSum - n * (n - 1) * (2 * n - 1) / 6.0;
    int x1 = (int)((sum2 - sqrt(2 * squaredSum2 - sum2 * sum2)) / 2);
    int x2 = (int)((sum2 + sqrt(2 * squaredSum2 - sum2 * sum2)) / 2);
    int* res = (int*)malloc(2 * sizeof(int));
    res[0] = x1;
    res[1] = x2;
    *returnSize = 2;
    return res;
}

###Rust

impl Solution {
    pub fn get_sneaky_numbers(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len() as i32 - 2;
        let sum: f64 = nums.iter().map(|&x| x as f64).sum();
        let squared_sum: f64 = nums.iter().map(|&x| (x*x) as f64).sum();
        let sum2 = sum - (n * (n - 1) / 2) as f64;
        let squared_sum2 = squared_sum - (n * (n - 1) * (2 * n - 1) / 6) as f64;
        let x1 = (sum2 - ((2.0 * squared_sum2 - sum2 * sum2).sqrt())) / 2.0;
        let x2 = (sum2 + ((2.0 * squared_sum2 - sum2 * sum2).sqrt())) / 2.0;
        vec![x1 as i32, x2 as i32]
    }
}

复杂度分析

• 时间复杂度：$O(n)$。

• 空间复杂度：$O(1)$。

方法一：暴力计算

记当前的天数是第 $\textit{week}$ 周的第 $\textit{day}$ 天。我们从第一周的星期一开始存钱，记 $\textit{week} = 1$，$\textit{day} = 1$。一周内，每一天比前一天多存 $1$ 块钱。而每个周一，会比前一个周一多存 $1$ 块钱。因此，每天存的钱等于 $\textit{week} + \textit{day} - 1$。把每天存的钱相加就可以得到答案。

###Python

class Solution:
    def totalMoney(self, n: int) -> int:
        week, day = 1, 1
        res = 0
        for i in range(n):
            res += week + day - 1
            day += 1
            if day == 8:
                day = 1
                week += 1
        return res

###Java

class Solution {
    public int totalMoney(int n) {
        int week = 1, day = 1;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            res += week + day - 1;
            ++day;
            if (day == 8) {
                day = 1;
                ++week;
            }
        }
        return res;
    }
}

###C#

public class Solution {
    public int TotalMoney(int n) {
        int week = 1, day = 1;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            res += week + day - 1;
            ++day;
            if (day == 8) {
                day = 1;
                ++week;
            }
        }
        return res;
    }
}

###C++

class Solution {
public:
    int totalMoney(int n) {
        int week = 1, day = 1;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            res += week + day - 1;
            ++day;
            if (day == 8) {
                day = 1;
                ++week;
            }
        }
        return res;
    }
};

###C

int totalMoney(int n){
    int week = 1, day = 1;
    int res = 0;
    for (int i = 0; i < n; ++i) {
        res += week + day - 1;
        ++day;
        if (day == 8) {
            day = 1;
            ++week;
        }
    }
    return res;
}

###go

func totalMoney(n int) (ans int) {
    week, day := 1, 1
    for i := 0; i < n; i++ {
        ans += week + day - 1
        day++
        if day == 8 {
            day = 1
            week++
        }
    }
    return
}

###JavaScript

var totalMoney = function(n) {
    let week = 1, day = 1;
    let res = 0;
    for (let i = 0; i < n; ++i) {
        res += week + day - 1;
        ++day;
        if (day === 8) {
            day = 1;
            ++week;
        }
    }
    return res;
};

复杂度分析

• 时间复杂度：$O(n)$。需要遍历一次 $n$ 得到答案。

• 空间复杂度：$O(1)$。只需要用到常数空间。

方法二：等差数列求和进行优化

因为每周七天存的钱之和比上一周多 $7$ 块，因此每周存的钱之和的序列是一个等差数列，我们可以用等差数列求和公式来求出所有完整的周存的钱总和。剩下的天数里，每天存的钱也是一个等差数列，可以用相同的公式进行求和。最后把两者相加可以得到答案。

###Python

class Solution:
    def totalMoney(self, n: int) -> int:
        # 所有完整的周存的钱
        weekNumber = n // 7
        firstWeekMoney = (1 + 7) * 7 // 2
        lastWeekMoney = firstWeekMoney + 7 * (weekNumber - 1)
        weekMoney = (firstWeekMoney + lastWeekMoney) * weekNumber // 2
        # 剩下的不能构成一个完整的周的天数里存的钱
        dayNumber = n % 7
        firstDayMoney = 1 + weekNumber
        lastDayMoney = firstDayMoney + dayNumber - 1
        dayMoney = (firstDayMoney + lastDayMoney) * dayNumber // 2
        return weekMoney + dayMoney

###Java

class Solution {
    public int totalMoney(int n) {
        // 所有完整的周存的钱
        int weekNumber = n / 7;
        int firstWeekMoney = (1 + 7) * 7 / 2;
        int lastWeekMoney = firstWeekMoney + 7 * (weekNumber - 1);
        int weekMoney = (firstWeekMoney + lastWeekMoney) * weekNumber / 2;
        // 剩下的不能构成一个完整的周的天数里存的钱
        int dayNumber = n % 7;
        int firstDayMoney = 1 + weekNumber;
        int lastDayMoney = firstDayMoney + dayNumber - 1;
        int dayMoney = (firstDayMoney + lastDayMoney) * dayNumber / 2;
        return weekMoney + dayMoney;
    }
}

###C#

public class Solution {
    public int TotalMoney(int n) {
        // 所有完整的周存的钱
        int weekNumber = n / 7;
        int firstWeekMoney = (1 + 7) * 7 / 2;
        int lastWeekMoney = firstWeekMoney + 7 * (weekNumber - 1);
        int weekMoney = (firstWeekMoney + lastWeekMoney) * weekNumber / 2;
        // 剩下的不能构成一个完整的周的天数里存的钱
        int dayNumber = n % 7;
        int firstDayMoney = 1 + weekNumber;
        int lastDayMoney = firstDayMoney + dayNumber - 1;
        int dayMoney = (firstDayMoney + lastDayMoney) * dayNumber / 2;
        return weekMoney + dayMoney;
    }
}

###C++

class Solution {
public:
    int totalMoney(int n) {
        // 所有完整的周存的钱
        int weekNumber = n / 7;
        int firstWeekMoney = (1 + 7) * 7 / 2;
        int lastWeekMoney = firstWeekMoney + 7 * (weekNumber - 1);
        int weekMoney = (firstWeekMoney + lastWeekMoney) * weekNumber / 2;
        // 剩下的不能构成一个完整的周的天数里存的钱
        int dayNumber = n % 7;
        int firstDayMoney = 1 + weekNumber;
        int lastDayMoney = firstDayMoney + dayNumber - 1;
        int dayMoney = (firstDayMoney + lastDayMoney) * dayNumber / 2;
        return weekMoney + dayMoney;
    }
};

###C

int totalMoney(int n){
    // 所有完整的周存的钱
    int weekNumber = n / 7;
    int firstWeekMoney = (1 + 7) * 7 / 2;
    int lastWeekMoney = firstWeekMoney + 7 * (weekNumber - 1);
    int weekMoney = (firstWeekMoney + lastWeekMoney) * weekNumber / 2;
    // 剩下的不能构成一个完整的周的天数里存的钱
    int dayNumber = n % 7;
    int firstDayMoney = 1 + weekNumber;
    int lastDayMoney = firstDayMoney + dayNumber - 1;
    int dayMoney = (firstDayMoney + lastDayMoney) * dayNumber / 2;
    return weekMoney + dayMoney;
}

###go

func totalMoney(n int) (ans int) {
    // 所有完整的周存的钱
    weekNum := n / 7
    firstWeekMoney := (1 + 7) * 7 / 2
    lastWeekMoney := firstWeekMoney + 7*(weekNum-1)
    weekMoney := (firstWeekMoney + lastWeekMoney) * weekNum / 2
    // 剩下的不能构成一个完整的周的天数里存的钱
    dayNum := n % 7
    firstDayMoney := 1 + weekNum
    lastDayMoney := firstDayMoney + dayNum - 1
    dayMoney := (firstDayMoney + lastDayMoney) * dayNum / 2
    return weekMoney + dayMoney
}

###JavaScript

var totalMoney = function(n) {
    // 所有完整的周存的钱
    const weekNumber = Math.floor(n / 7);
    const firstWeekMoney = Math.floor((1 + 7) * 7 / 2);
    const lastWeekMoney = firstWeekMoney + 7 * (weekNumber - 1);
    const weekMoney = Math.floor((firstWeekMoney + lastWeekMoney) * weekNumber / 2);
    // 剩下的不能构成一个完整的周的天数里存的钱
    const dayNumber = n % 7;
    const firstDayMoney = 1 + weekNumber;
    const lastDayMoney = firstDayMoney + dayNumber - 1;
    const dayMoney = Math.floor((firstDayMoney + lastDayMoney) * dayNumber / 2);
    return weekMoney + dayMoney;
};

复杂度分析

• 时间复杂度：$O(1)$。只需要用到常数时间。

• 空间复杂度：$O(1)$。只需要用到常数空间。

方法一：一次遍历

思路与算法

我们对数组 $\textit{nums}$ 进行一次遍历，在遍历的过程中，用 $\textit{cnt}$ 和 $\textit{precnt}$ 分别记录到当前位置严格递增的子数组的长度，以及上一个严格递增子数组的长度。

初始时，$\textit{cnt}$ 的值为 $1$，$\textit{precnt}$ 的值为 $0$。当遍历到 $\textit{nums}[i]$ 时，如果大于 $\textit{nums}[i-1]$，则 $\textit{cnt}$ 自增 $1$；否则子数组不再递增，将 $\textit{cnt}$ 的值赋予 $\textit{precnt}$，并将 $\textit{cnt}$ 置为 $1$。

满足题目要求的两个相邻子数组有两种情况：

1. 前一个子数组属于 $\textit{precnt}$，后一个子数组属于 $\textit{cnt}$，$k$ 值为 $\min(\textit{precnt}, \textit{cnt})$。

2. 两个子数组都属于 $\textit{cnt}$，$k$ 值为 $\lfloor \dfrac{\textit{cnt}}{2} \rfloor$，其中 $\lfloor \cdot \rfloor$ 表示向下取整。

根据这两种情况，不断更新 $k$ 的最大值即可。

代码

###C++

class Solution {
public:
    int maxIncreasingSubarrays(vector<int>& nums) {
        int n = nums.size();
        int cnt = 1, precnt = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) {
                ++cnt;
            }
            else {
                precnt = cnt;
                cnt = 1;
            }
            ans = max(ans, min(precnt, cnt));
            ans = max(ans, cnt / 2);
        }
        return ans;
    }
};

###Python

class Solution:
    def maxIncreasingSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        cnt, precnt, ans = 1, 0, 0
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                cnt += 1
            else:
                precnt, cnt = cnt, 1
            ans = max(ans, min(precnt, cnt))
            ans = max(ans, cnt // 2)
        return ans

###C#

public class Solution {
    public int MaxIncreasingSubarrays(IList<int> nums) {
        int n = nums.Count;
        int cnt = 1, precnt = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) {
                ++cnt;
            } else {
                precnt = cnt;
                cnt = 1;
            }
            ans = Math.Max(ans, Math.Min(precnt, cnt));
            ans = Math.Max(ans, cnt / 2);
        }
        return ans;
    }
}

###Go

func maxIncreasingSubarrays(nums []int) int {
    n := len(nums)
    cnt, precnt, ans := 1, 0, 0
    for i := 1; i < n; i++ {
        if nums[i] > nums[i-1] {
            cnt++
        } else {
            precnt = cnt
            cnt = 1
        }
        ans = max(ans, min(precnt, cnt))
        ans = max(ans, cnt/2)
    }
    return ans
}

###Python

class Solution:
    def maxIncreasingSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        cnt, precnt, ans = 1, 0, 0
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                cnt += 1
            else:
                precnt = cnt
                cnt = 1
            ans = max(ans, min(precnt, cnt))
            ans = max(ans, cnt // 2)
        return ans

###C

int maxIncreasingSubarrays(int* nums, int numsSize) {
    int cnt = 1, precnt = 0, ans = 0;
    for (int i = 1; i < numsSize; ++i) {
        if (nums[i] > nums[i - 1]) {
            ++cnt;
        } else {
            precnt = cnt;
            cnt = 1;
        }
        int min_val = precnt < cnt ? precnt : cnt;
        ans = ans > min_val ? ans : min_val;
        ans = ans > cnt / 2 ? ans : cnt / 2;
    }
    return ans;
}

###JavaScript

var maxIncreasingSubarrays = function(nums) {
    const n = nums.length;
    let cnt = 1, precnt = 0, ans = 0;
    for (let i = 1; i < n; ++i) {
        if (nums[i] > nums[i - 1]) {
            ++cnt;
        } else {
            precnt = cnt;
            cnt = 1;
        }
        ans = Math.max(ans, Math.min(precnt, cnt));
        ans = Math.max(ans, Math.floor(cnt / 2));
    }
    return ans;
};

###TypeScript

function maxIncreasingSubarrays(nums: number[]): number {
    const n = nums.length;
    let cnt = 1, precnt = 0, ans = 0;
    for (let i = 1; i < n; ++i) {
        if (nums[i] > nums[i - 1]) {
            ++cnt;
        } else {
            precnt = cnt;
            cnt = 1;
        }
        ans = Math.max(ans, Math.min(precnt, cnt));
        ans = Math.max(ans, Math.floor(cnt / 2));
    }
    return ans;
}

###Rust

impl Solution {
    pub fn max_increasing_subarrays(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut cnt = 1;
        let mut precnt = 0;
        let mut ans = 0;
        
        for i in 1..n {
            if nums[i] > nums[i - 1] {
                cnt += 1;
            } else {
                precnt = cnt;
                cnt = 1;
            }
            ans = ans.max(precnt.min(cnt));
            ans = ans.max(cnt / 2);
        }
        
        ans
    }
}

复杂度分析

• 时间复杂度：$O(n)$。

• 空间复杂度：$O(1)$。

方法一：二分查找

思路与算法

对于某一个咒语的能量，我们可以采用二分查找的方法来高效地找到符合条件的药水数量。首先，我们将 $\textit{potions}$ 数组进行排序，以便能够利用有序性进行二分查找。然后，对于每个咒语 $\textit{spells}[i]$，$0 \le i < n$，其中 $n$ 为数组 $\textit{spells}$ 的长度，我们计算出目标值

$$target = \lceil \frac{\textit{success}}{\textit{spells}[i]} \rceil$$

其中 $\lceil x \rceil$ 表示不小于 $x$ 的最小整数。$\textit{target}$ 代表了在当前咒语强度下，药水需要达到的最低强度。接下来，我们使用「二分查找」来在数组 $\textit{potions}$ 中找到第一个大于等于 $target$ 的元素的索引 $\textit{idx}$，进一步可以得到此时表示成功组合的药水数量为 $m - \textit{idx}$，其中 $m$ 表示数组 $\textit{potions}$ 的长度。

代码

###C++

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(), potions.end());
        vector<int> res;
        for (auto& i : spells) {
            long long t = (success + i - 1) / i - 1;
            res.push_back(potions.size() - (upper_bound(potions.begin(), potions.end(), t) - potions.begin()));
        }
        return res;
    }
};

###Java

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int n = spells.length, m = potions.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            long t = (success + spells[i] - 1) / spells[i] - 1;
            res[i] = m - binarySearch(potions, 0, m - 1, t);
        }
        return res;
    }

    public int binarySearch(int[] arr, int lo, int hi, long target) {
        int res = hi + 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] > target) {
                res = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return res;
    }
}

###C#

public class Solution {
    public int[] SuccessfulPairs(int[] spells, int[] potions, long success) {
        Array.Sort(potions);
        int n = spells.Length, m = potions.Length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            long t = (success + spells[i] - 1) / spells[i] - 1;
            res[i] = m - BinarySearch(potions, 0, m - 1, t);
        }
        return res;
    }

    public int BinarySearch(int[] arr, int lo, int hi, long target) {
        int res = hi + 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] > target) {
                res = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return res;
    }
}

###C

static int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int binarySearch(const int *arr, int lo, int hi, long long target) {
    int res = hi + 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] > target) {
            res = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return res;
}

int* successfulPairs(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* returnSize) {
    qsort(potions, potionsSize, sizeof(int), cmp);
    int *res = (int *)calloc(spellsSize, sizeof(int));
    for (int i = 0; i < spellsSize; i++) {
        long long t = (success - 1) / spells[i];
        res[i] = potionsSize - binarySearch(potions, 0, potionsSize - 1, t);
    }
    *returnSize = spellsSize;
    return res;
}

###Python

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        return [len(potions) - bisect.bisect_right(potions, (success - 1) // i) for i in spells]

###Go

func successfulPairs(spells []int, potions []int, success int64) []int {
    sort.Ints(potions)
    res := make([]int, len(spells))
    for i, x := range spells {
        res[i] = len(potions) - sort.SearchInts(potions, (int(success) - 1) / x + 1)
    }
    return res
}

###JavaScript

var successfulPairs = function(spells, potions, success) {
    function binarySearch(nums, lo, hi, target) {
        let res = hi + 1;
        while (lo <= hi) {
            const mid = lo + Math.floor((hi - lo) / 2);
            if (nums[mid] > target) {
                res = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return res;
    }

    potions.sort((a, b) => a - b);
    return spells.map((item) => {
        return potions.length - binarySearch(potions, 0, potions.length - 1, (success - 1) / item)
    })
};

复杂度分析

• 时间复杂度：$O(m \times \log m + n \times \log m)$，其中 $n$ 为数组 $\textit{spells}$ 的长度，$m$ 是数组 $\textit{postion}$ 的长度，主要为对数组 $\textit{potions}$ 排序和对数组 $\textit{spells}$ 中每一个元素对数组 $\textit{potions}$ 进行「二分查找」的时间开销。
• 空间复杂度：$O(\log m)$，主要为对 $\textit{potions}$ 排序的空间开销，其中返回的答案不计入空间复杂度。

方法二：双指针

思路与算法

同样我们也可以通过「双指针」来解决这个问题：

首先我们对数组 $\textit{spells}$ 下标按照其位置上的能量强度进行 升序排序，假设其排序后的数组为 $\textit{idx}$，对数组 $\textit{potions}$ 按照能量强度进行 降序排序。并初始化一个结果数组 $\textit{res}$，长度为 $n$，$n$ 为数组 $\textit{spells}$ 的长度，用于记录每个咒语成功组合的药水数目。

我们使用两个指针 $i$ 和 $j$ 分别指向数组 $\textit{idx}$ 和 $\textit{potions}$ 的起始位置，用指针 $i$ 遍历数组 $\textit{idx}$，对于当前 $i$ 指向的咒语 $\textit{spells}[\textit{idx}[i]]$，若有

$$
\textit{spells}[\textit{idx}[i]] \times \textit{potions}[j] \ge \textit{sucess} \tag{1}
$$

成立，则对于任意 $i < k < n$，都有

$$
\textit{spells}[\textit{idx}[k]] \times \textit{potions}[j] \ge \textit{sucess} \tag{2}
$$

成立。对于每一个 $i$，指针 $j$ 不断右移直至 $j$ 不满足条件 $(1)$（其中右移前需要满足 $j < m$ 成立，$m$ 为 $\textit{potions}$ 的长度）。对于指针 $i$，指针 $j$ 移动操作结束后，那么此时能成功组合的药水数量 $\textit{res}[\textit{idx}[i]] = j$。并且由于随着指针 $i$ 位置不断增大，指针 $j$ 的位置单调不减，所以指针 $i$ 不断右移的整个过程时间复杂度为 $O(n)$。

代码

###C++

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        vector<int> res(spells.size());
        vector<int> idx(spells.size());
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b) {
            return spells[a] < spells[b];
        });
        sort(potions.begin(), potions.end(), [](int a, int b) {
            return a > b;
        });
        for (int i = 0, j = 0; i < spells.size(); ++i) {
            int p = idx[i];
            int v = spells[p];
            while (j < potions.size() && (long long) potions[j] * v >= success) {
                ++j;
            }
            res[p] = j;
        }
        return res;
    }
};

###Java

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length, m = potions.length;
        int[] res = new int[n];
        int[][] idx = new int[n][2];
        for (int i = 0; i < n; ++i) {
            idx[i][0] = spells[i];
            idx[i][1] = i;
        }
        Arrays.sort(potions);
        for (int i = 0, j = m - 1; i < j; ++i, --j) {
            int temp = potions[i];
            potions[i] = potions[j];
            potions[j] = temp;
        }
        Arrays.sort(idx, (a, b) -> a[0] - b[0]);
        for (int i = 0, j = 0; i < n; ++i) {
            int p = idx[i][1];
            int v = idx[i][0];
            while (j < m && (long) potions[j] * v >= success) {
                ++j;
            }
            res[p] = j;
        }
        return res;
    }
}

###C#

public class Solution {
    public int[] SuccessfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.Length, m = potions.Length;
        int[] res = new int[n];
        int[][] idx = new int[n][];
        for (int i = 0; i < n; ++i) {
            idx[i] = new int[2];
            idx[i][0] = spells[i];
            idx[i][1] = i;
        }
        Array.Sort(potions);
        for (int i = 0, j = m - 1; i < j; ++i, --j) {
            int temp = potions[i];
            potions[i] = potions[j];
            potions[j] = temp;
        }
        Array.Sort(idx, (a, b) => a[0] - b[0]);
        for (int i = 0, j = 0; i < n; ++i) {
            int p = idx[i][1];
            int v = idx[i][0];
            while (j < m && (long) potions[j] * v >= success) {
                ++j;
            }
            res[p] = j;
        }
        return res;
    }
}

###C

static int cmp1(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

static int cmp2(const void *a, const void *b) {
    return ((int *)a)[0] - ((int *)b)[0];
}

int* successfulPairs(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* returnSize) {
    int *res = (int *)calloc(spellsSize, sizeof(int));
    int idx[spellsSize][2];
    for (int i = 0; i < spellsSize; i++) {
        idx[i][0] = spells[i];
        idx[i][1] = i;
    }

    qsort(potions, potionsSize, sizeof(int), cmp1);
    qsort(idx, spellsSize, sizeof(idx[0]), cmp2);
    for (int i = 0, j = 0; i < spellsSize; ++i) {
        int p = idx[i][1];
        int v = idx[i][0];
        while (j < potionsSize && (long long) potions[j] * v >= success) {
            ++j;
        }
        res[p] = j;
    }
    *returnSize = spellsSize;
    return res;
}

###Python

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        res = [0] * len(spells)
        idx = [i for i in range(len(spells))]
        idx.sort(key = lambda x: spells[x])
        potions.sort(key = lambda x : -x)
        j = 0
        for p in idx:
            v = spells[p]
            while j < len(potions) and potions[j] * v >= success:
                j += 1
            res[p] = j
        return res

###Go

func successfulPairs(spells []int, potions []int, success int64) []int {
    res := make([]int, len(spells))
    idx := make([]int, len(spells))
    for i, _ := range idx {
        idx[i] = i
    }
    sort.Slice(potions, func(i, j int) bool {
        return potions[i] > potions[j]
    })
    sort.Slice(idx, func(i, j int) bool {
        return spells[idx[i]] < spells[idx[j]]
    })
    j := 0
    for _, p := range idx {
        v := spells[p]
        for j < len(potions) && int64(potions[j]) * int64(v) >= success {
            j++
        }
        res[p] = j
    }
    return res
}

###JavaScript

var successfulPairs = function(spells, potions, success) {
    const res = new Array(spells.length).fill(0);
    const idx = new Array(spells.length).fill(0).map((_, i) => i);
    idx.sort((a, b) => spells[a] - spells[b]);
    potions.sort((a, b) => b - a);
    let j = 0;
    for (p of idx) {
        let v = spells[p];
        while (j < potions.length && potions[j] * v >= success) {
            j++;
        }
        res[p] = j;
    }
    return res;
};

复杂度分析

• 时间复杂度：$O(n \times \log n + m \times \log m)$，其中 $n$ 为数组 $\textit{spells}$ 的长度，$m$ 是数组 $\textit{postion}$ 的长度，主要为对数组 $\textit{potions}$ 和 $\textit{idx}$ 排序的时间开销。
• 空间复杂度：$O(n + \log n + \log m)$，主要为数组 $\textit{idx}$ 的空间开销和对数组 $\textit{potions}$ 排序的空间开销，其中返回的答案不计入空间复杂度。

方法一：贪心 + 二分查找

思路与算法

我们要思考如何在洪水即将发生时，有选择地对湖泊进行抽干操作。为了做到这一点，我们使用有序集合 $\textit{st}$ 来存储了那些在某些日期没有下雨的日子。这些晴天日子可以被用来在湖泊即将发生洪水时，有选择地抽干湖泊，从而阻止洪水的发生。有序集合 $\textit{st}$ 的排序方式是按照晴天日子的顺序排列的，这就确保了我们总是在最早的晴天日子中进行抽干操作，以最大程度地避免洪水的发生。对于最后剩余的晴天，我们可以将它们用于抽干任意一个湖泊，为了方便，我们令其为 $1$。现在我们初始化一个大小和 $\textit{rains}$ 一样的答案数组 $\textit{ans}$，并初始化为 $1$，然后从左到右来遍历数组 $\textit{rains}$：

• 若 $\textit{rains}[i] = 0$，则将 $i$ 加入有序集合 $\textit{st}$。
• 若 $\textit{rains}[i] > 0$，表示第 $\textit{rains}[i]$ 湖泊将下雨，令 $\textit{ans}[i] = -1$ 表示这一天的湖泊不可抽干：
  • 若第 $\textit{rains}[i]$ 是第一次下雨，则此时不会发生洪水。
  • 否则我们需要在有序集合 $\textit{st}$ 中找到大于等于该湖泊上一次下雨天数的最小索引 $\textit{idx}$（可以用二分查找实现），如果 $\textit{idx}$ 不存在（即没有晴天可以用于抽干），此时不能避免洪水的发生，按照题目要求返回一个空数组。否则我们令 $\textit{ans}[\textit{idx}] = \textit{rains}[i]$，并在 $\textit{st}$ 中删除 $\textit{idx}$，表示我们会在第 $\textit{idx}$ 天抽干 $\textit{rains}[i]$ 湖泊的水来避免第 $i$ 天洪水的发生。

代码

###C++

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        vector<int> ans(rains.size(), 1);
        set<int> st;
        unordered_map<int, int> mp;
        for (int i = 0; i < rains.size(); ++i) {
            if (rains[i] == 0) {
                st.insert(i);
            } else {
                ans[i] = -1;
                if (mp.count(rains[i])) {
                    auto it = st.lower_bound(mp[rains[i]]);
                    if (it == st.end()) {
                        return {};
                    }
                    ans[*it] = rains[i];
                    st.erase(it);
                }
                mp[rains[i]] = i;
            }
        }
        return ans;
    }
};

###Java

class Solution {
    public int[] avoidFlood(int[] rains) {
        int[] ans = new int[rains.length];
        Arrays.fill(ans, 1);
        TreeSet<Integer> st = new TreeSet<Integer>();
        Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
        for (int i = 0; i < rains.length; ++i) {
            if (rains[i] == 0) {
                st.add(i);
            } else {
                ans[i] = -1;
                if (mp.containsKey(rains[i])) {
                    Integer it = st.ceiling(mp.get(rains[i]));
                    if (it == null) {
                        return new int[0];
                    }
                    ans[it] = rains[i];
                    st.remove(it);
                }
                mp.put(rains[i], i);
            }
        }
        return ans;
    }
}

###Python

from sortedcontainers import SortedList

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        ans = [1] * len(rains)
        st = SortedList()
        mp = {}
        for i, rain in enumerate(rains):
            if rain == 0:
                st.add(i)
            else:
                ans[i] = -1
                if rain in mp:
                    it = st.bisect(mp[rain])
                    if it == len(st):
                        return []
                    ans[st[it]] = rain
                    st.discard(st[it])
                mp[rain] = i
        return ans

###Go

func avoidFlood(rains []int) []int {
    n := len(rains)
    ans := make([]int, n)
    st := []int{} 
    mp := make(map[int]int)
    for i := 0; i < n; i++ {
        ans[i] = 1
    }
    for i, rain := range rains {
        if rain == 0 {
            st = append(st, i)
        } else {
            ans[i] = -1
            if day, ok := mp[rain]; ok {
                it := sort.SearchInts(st, day)
                if it == len(st) {
                    return []int {}
                }
                ans[st[it]] = rain
                copy(st[it : len(st) - 1], st[it + 1 : len(st)])
                st = st[: len(st) - 1]
            }
            mp[rain] = i
        }
    }
    return ans
}

复杂度分析

• 时间复杂度：$O(n \times \log n)$，其中 $n$ 为数组 $\textit{rains}$ 的长度。每次有序集合的插入和查询的时间复杂度为 $O(\log n)$，最坏情况下会进行 $n$ 次有序集合的插入操作，所以总的时间复杂度为 $O(n \times \log n)$。
• 空间复杂度：$O(n)$，其中 $n$ 为数组 $\textit{rains}$ 的长度。主要为哈希表和有序集合的空间开销。

前言

记一开始有 $b$ 瓶水，$e$ 个空瓶换一瓶水。

方法一：模拟

思路与算法

首先我们一定可以喝到 $b$ 瓶水，剩下 $b$ 个空瓶。接下来我们可以拿瓶子换水，每次拿出 $e$ 个瓶子换一瓶水，然后再喝完这瓶水，得到一个空瓶。以此类推，我们可以统计得到答案。

代码

###C++

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int bottle = numBottles, ans = numBottles;
        while (bottle >= numExchange) {
            bottle -= numExchange;
            ++ans;
            ++bottle;
        }
        return ans;
    }
};

###Java

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int bottle = numBottles, ans = numBottles;
        while (bottle >= numExchange) {
            bottle -= numExchange;
            ++ans;
            ++bottle;
        }
        return ans;
    }
}

###C#

public class Solution {
    public int NumWaterBottles(int numBottles, int numExchange) {
        int bottle = numBottles, ans = numBottles;
        while (bottle >= numExchange) {
            bottle -= numExchange;
            ++ans;
            ++bottle;
        }
        return ans;
    }
}

###Python

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        bottle, ans = numBottles, numBottles
        while bottle >= numExchange:
            bottle -= numExchange
            ans += 1
            bottle += 1
        return ans

###C

int numWaterBottles(int numBottles, int numExchange){
    int bottle = numBottles, ans = numBottles;
    while (bottle >= numExchange) {
        bottle -= numExchange;
        ++ans;
        ++bottle;
    }
    return ans;
}

###Go

func numWaterBottles(numBottles int, numExchange int) int {
    bottle, ans := numBottles, numBottles
    for bottle >= numExchange {
        bottle = bottle - numExchange
        ans++
        bottle++
    }
    return ans
}

###JavaScript

var numWaterBottles = function(numBottles, numExchange) {
    let bottle = numBottles, ans = numBottles;
    while (bottle >= numExchange) {
        bottle -= numExchange;
        ++ans;
        ++bottle;
    }
    return ans;
};

复杂度分析

• 时间复杂度：$O\Big(\dfrac{b}{e}\Big)$。因为 $e \geq 2$，而循环迭代时，每次 $b$ 的变化为 $e - 1$，故这里的渐进上界为 $O\Big(\dfrac{b}{e}\Big)$。

• 空间复杂度：$O(1)$。

方法二：数学

思路与算法

第一步，首先我们一定可以喝到 $b$ 瓶水，剩下 $b$ 个空瓶。

第二步，接下来我们来考虑空瓶换水，换完再喝，喝完再换的过程——每次换到一瓶水就意味着多一个空瓶，所以每次损失的瓶子的数量为 $e - 1$，我们要知道这个过程能得到多少瓶水，即希望知道第一个打破下面这个条件的 $n$ 是多少：

$$ b - n(e - 1) \geq e $$

即我们要找到最小的 $n$ 使得：

$$ b - n(e - 1) < e $$

我们得到 $n_{\min} = \lfloor \dfrac{b - e}{e - 1} + 1\rfloor$。

当然我们要特别注意这里的前提条件是 $b \geq e$，试想如果 $b < e$，没有足够的瓶子再换水了，就不能进行第二步了。

代码

###C++

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        return numBottles >= numExchange ? (numBottles - numExchange) / (numExchange - 1) + 1 + numBottles : numBottles;
    }
};

###Java

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        return numBottles >= numExchange ? (numBottles - numExchange) / (numExchange - 1) + 1 + numBottles : numBottles;
    }
}

###C#

public class Solution {
    public int NumWaterBottles(int numBottles, int numExchange) {
        return numBottles >= numExchange ? (numBottles - numExchange) / (numExchange - 1) + 1 + numBottles : numBottles;
    }
}

###Python

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        return (numBottles - numExchange) // (numExchange - 1) + 1 + numBottles if numBottles >= numExchange else numBottles

###C

int numWaterBottles(int numBottles, int numExchange){
    return numBottles >= numExchange ? (numBottles - numExchange) / (numExchange - 1) + 1 + numBottles : numBottles;
}

###Go

func numWaterBottles(numBottles int, numExchange int) int {
    if numBottles < numExchange {
        return numBottles
    }
    return (numBottles - numExchange) / (numExchange - 1) + 1 + numBottles
}

###JavaScript

var numWaterBottles = function(numBottles, numExchange) {
    return numBottles >= numExchange ? Math.floor((numBottles - numExchange) / (numExchange - 1)) + 1 + numBottles : numBottles;
};

复杂度分析

• 时间复杂度：$O(1)$。

• 空间复杂度：$O(1)$。

前言

本题是一道非常经典且历史悠久的动态规划题，其作为算法题出现，最早可以追溯到 1994 年的 IOI（国际信息学奥林匹克竞赛）的 The Triangle。时光飞逝，经过 20 多年的沉淀，往日的国际竞赛题如今已经变成了动态规划的入门必做题，不断督促着我们学习和巩固算法。

在本题中，给定的三角形的行数为 $n$，并且第 $i$ 行（从 $0$ 开始编号）包含了 $i+1$ 个数。如果将每一行的左端对齐，那么会形成一个等腰直角三角形，如下所示：

[2]
[3,4]
[6,5,7]
[4,1,8,3]

方法一：动态规划

思路与算法

我们用 $f[i][j]$ 表示从三角形顶部走到位置 $(i, j)$ 的最小路径和。这里的位置 $(i, j)$ 指的是三角形中第 $i$ 行第 $j$ 列（均从 $0$ 开始编号）的位置。

由于每一步只能移动到下一行「相邻的节点」上，因此要想走到位置 $(i, j)$，上一步就只能在位置 $(i - 1, j - 1)$ 或者位置 $(i - 1, j)$。我们在这两个位置中选择一个路径和较小的来进行转移，状态转移方程为：

$$
f[i][j] = \min(f[i-1][j-1], f[i-1][j]) + c[i][j]
$$

其中 $c[i][j]$ 表示位置 $(i, j)$ 对应的元素值。

注意第 $i$ 行有 $i+1$ 个元素，它们对应的 $j$ 的范围为 $[0, i]$。当 $j=0$ 或 $j=i$ 时，上述状态转移方程中有一些项是没有意义的。例如当 $j=0$ 时，$f[i-1][j-1]$ 没有意义，因此状态转移方程为：

$$
f[i][0] = f[i-1][0] + c[i][0]
$$

即当我们在第 $i$ 行的最左侧时，我们只能从第 $i-1$ 行的最左侧移动过来。当 $j=i$ 时，$f[i-1][j]$ 没有意义，因此状态转移方程为：

$$
f[i][i] = f[i-1][i-1] + c[i][i]
$$

即当我们在第 $i$ 行的最右侧时，我们只能从第 $i-1$ 行的最右侧移动过来。

最终的答案即为 $f[n-1][0]$ 到 $f[n-1][n-1]$ 中的最小值，其中 $n$ 是三角形的行数。

细节

状态转移方程的边界条件是什么？由于我们已经去除了所有「没有意义」的状态，因此边界条件可以定为：

$$
f[0][0] = c[0][0]
$$

即在三角形的顶部时，最小路径和就等于对应位置的元素值。这样一来，我们从 $1$ 开始递增地枚举 $i$，并在 $[0, i]$ 的范围内递增地枚举 $j$，就可以完成所有状态的计算。

###C++

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> f(n, vector<int>(n));
        f[0][0] = triangle[0][0];
        for (int i = 1; i < n; ++i) {
            f[i][0] = f[i - 1][0] + triangle[i][0];
            for (int j = 1; j < i; ++j) {
                f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
            }
            f[i][i] = f[i - 1][i - 1] + triangle[i][i];
        }
        return *min_element(f[n - 1].begin(), f[n - 1].end());
    }
};

###Java

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] f = new int[n][n];
        f[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            f[i][0] = f[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; ++j) {
                f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);
            }
            f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int minTotal = f[n - 1][0];
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, f[n - 1][i]);
        }
        return minTotal;
    }
}

###Python

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        f = [[0] * n for _ in range(n)]
        f[0][0] = triangle[0][0]

        for i in range(1, n):
            f[i][0] = f[i - 1][0] + triangle[i][0]
            for j in range(1, i):
                f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]
            f[i][i] = f[i - 1][i - 1] + triangle[i][i]
        
        return min(f[n - 1])

###Go

func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    f := make([][]int, n)
    for i := 0; i < n; i++ {
        f[i] = make([]int, n)
    }
    f[0][0] = triangle[0][0]
    for i := 1; i < n; i++ {
        f[i][0] = f[i - 1][0] + triangle[i][0]
        for j := 1; j < i; j++ {
            f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]
        }
        f[i][i] = f[i - 1][i - 1] + triangle[i][i]
    }
    ans := math.MaxInt32
    for i := 0; i < n; i++ {
        ans = min(ans, f[n-1][i])
    }
    return ans
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

###C

int minimumTotal(int** triangle, int triangleSize, int* triangleColSize) {
    int f[triangleSize][triangleSize];
    memset(f, 0, sizeof(f));
    f[0][0] = triangle[0][0];
    for (int i = 1; i < triangleSize; ++i) {
        f[i][0] = f[i - 1][0] + triangle[i][0];
        for (int j = 1; j < i; ++j) {
            f[i][j] = fmin(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
        }
        f[i][i] = f[i - 1][i - 1] + triangle[i][i];
    }
    int ret = f[triangleSize - 1][0];
    for (int i = 1; i < triangleSize; i++)
        ret = fmin(ret, f[triangleSize - 1][i]);
    return ret;
}

###C#

public class Solution {
    public int MinimumTotal(IList<IList<int>> triangle) {
        int n = triangle.Count;
        int[][] f = new int[n][];
        for (int i = 0; i < n; i++) {
            f[i] = new int[n];
        }
        f[0][0] = triangle[0][0];
        for (int i = 1; i < n; ++i) {
            f[i][0] = f[i - 1][0] + triangle[i][0];
            for (int j = 1; j < i; ++j) {
                f[i][j] = Math.Min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
            }
            f[i][i] = f[i - 1][i - 1] + triangle[i][i];
        }
        return f[n - 1].Min();
    }
}

###JavaScript

var minimumTotal = function(triangle) {
    const n = triangle.length;
    const f = Array(n).fill(0).map(() => Array(n).fill(0));
    f[0][0] = triangle[0][0];
    for (let i = 1; i < n; ++i) {
        f[i][0] = f[i - 1][0] + triangle[i][0];
        for (let j = 1; j < i; ++j) {
            f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
        }
        f[i][i] = f[i - 1][i - 1] + triangle[i][i];
    }
    return Math.min(...f[n - 1]);
};

###TypeScript

function minimumTotal(triangle: number[][]): number {
    const n = triangle.length;
    const f: number[][] = Array(n).fill(0).map(() => Array(n).fill(0));
    f[0][0] = triangle[0][0];
    for (let i = 1; i < n; ++i) {
        f[i][0] = f[i - 1][0] + triangle[i][0];
        for (let j = 1; j < i; ++j) {
            f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
        }
        f[i][i] = f[i - 1][i - 1] + triangle[i][i];
    }
    return Math.min(...f[n - 1]);
};

###Rust

impl Solution {
    pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
        let n = triangle.len();
        let mut f = vec![vec![0; n]; n];
        f[0][0] = triangle[0][0];
        for i in 1..n {
            f[i][0] = f[i - 1][0] + triangle[i][0];
            for j in 1..i {
                f[i][j] = std::cmp::min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
            }
            f[i][i] = f[i - 1][i - 1] + triangle[i][i];
        }
        *f[n - 1].iter().min().unwrap()
    }
}

复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 是三角形的行数。

• 空间复杂度：$O(n^2)$。我们需要一个 $n*n$ 的二维数组存放所有的状态。

方法二：动态规划 + 空间优化

思路与算法

在题目描述中的「进阶」部分，提到了可以将空间复杂度优化至 $O(n)$。

我们回顾方法一中的状态转移方程：

$$
\begin{aligned}
f[i][j] = \begin{cases}
f[i-1][0] + c[i][0], & j=0\
f[i-1][i-1] + c[i][i], & j=i \
\min(f[i-1][j-1], f[i-1][j]) + c[i][j], & \text{otherwise}
\end{cases}
\end{aligned}
$$

可以发现，$f[i][j]$ 只与 $f[i-1][..]$ 有关，而与 $f[i-2][..]$ 及之前的状态无关，因此我们不必存储这些无关的状态。具体地，我们使用两个长度为 $n$ 的一维数组进行转移，将 $i$ 根据奇偶性映射到其中一个一维数组，那么 $i-1$ 就映射到了另一个一维数组。这样我们使用这两个一维数组，交替地进行状态转移。

###C++

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> f(2, vector<int>(n));
        f[0][0] = triangle[0][0];
        for (int i = 1; i < n; ++i) {
            int curr = i % 2;
            int prev = 1 - curr;
            f[curr][0] = f[prev][0] + triangle[i][0];
            for (int j = 1; j < i; ++j) {
                f[curr][j] = min(f[prev][j - 1], f[prev][j]) + triangle[i][j];
            }
            f[curr][i] = f[prev][i - 1] + triangle[i][i];
        }
        return *min_element(f[(n - 1) % 2].begin(), f[(n - 1) % 2].end());
    }
};

###Java

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] f = new int[2][n];
        f[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            int curr = i % 2;
            int prev = 1 - curr;
            f[curr][0] = f[prev][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; ++j) {
                f[curr][j] = Math.min(f[prev][j - 1], f[prev][j]) + triangle.get(i).get(j);
            }
            f[curr][i] = f[prev][i - 1] + triangle.get(i).get(i);
        }
        int minTotal = f[(n - 1) % 2][0];
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, f[(n - 1) % 2][i]);
        }
        return minTotal;
    }
}

###Python

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        f = [[0] * n for _ in range(2)]
        f[0][0] = triangle[0][0]

        for i in range(1, n):
            curr, prev = i % 2, 1 - i % 2
            f[curr][0] = f[prev][0] + triangle[i][0]
            for j in range(1, i):
                f[curr][j] = min(f[prev][j - 1], f[prev][j]) + triangle[i][j]
            f[curr][i] = f[prev][i - 1] + triangle[i][i]
        
        return min(f[(n - 1) % 2])

###Go

func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    f := [2][]int{}
    for i := 0; i < 2; i++ {
        f[i] = make([]int, n)
    }
    f[0][0] = triangle[0][0]
    for i := 1; i < n; i++ {
        curr := i % 2
        prev := 1 - curr
        f[curr][0] = f[prev][0] + triangle[i][0]
        for j := 1; j < i; j++ {
            f[curr][j] = min(f[prev][j - 1], f[prev][j]) + triangle[i][j]
        }
        f[curr][i] = f[prev][i - 1] + triangle[i][i]
    }
    ans := math.MaxInt32
    for i := 0; i < n; i++ {
        ans = min(ans, f[(n-1)%2][i])
    }
    return ans
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

###C

int minimumTotal(int** triangle, int triangleSize, int* triangleColSize) {
    int f[2][triangleSize];
    memset(f, 0, sizeof(f));
    f[0][0] = triangle[0][0];
    for (int i = 1; i < triangleSize; ++i) {
        int curr = i % 2;
        int prev = 1 - curr;
        f[curr][0] = f[prev][0] + triangle[i][0];
        for (int j = 1; j < i; ++j) {
            f[curr][j] = fmin(f[prev][j - 1], f[prev][j]) + triangle[i][j];
        }
        f[curr][i] = f[prev][i - 1] + triangle[i][i];
    }
    int ret = f[(triangleSize - 1) % 2][0];
    for (int i = 1; i < triangleSize; i++)
        ret = fmin(ret, f[(triangleSize - 1) % 2][i]);
    return ret;
}

###C#

public class Solution {
    public int MinimumTotal(IList<IList<int>> triangle) {
        int n = triangle.Count;
        int[][] f = new int[2][];
        f[0] = new int[n];
        f[1] = new int[n];
        f[0][0] = triangle[0][0];
        
        for (int i = 1; i < n; ++i) {
            int curr = i % 2;
            int prev = 1 - curr;
            f[curr][0] = f[prev][0] + triangle[i][0];
            for (int j = 1; j < i; ++j) {
                f[curr][j] = Math.Min(f[prev][j - 1], f[prev][j]) + triangle[i][j];
            }
            f[curr][i] = f[prev][i - 1] + triangle[i][i];
        }
        
        return f[(n - 1) % 2].Take(n).Min();
    }
}

###JavaScript

var minimumTotal = function(triangle) {
    const n = triangle.length;
    const f = Array.from({length: 2}, () => new Array(n).fill(0));
    f[0][0] = triangle[0][0];
    
    for (let i = 1; i < n; ++i) {
        const curr = i % 2;
        const prev = 1 - curr;
        f[curr][0] = f[prev][0] + triangle[i][0];
        for (let j = 1; j < i; ++j) {
            f[curr][j] = Math.min(f[prev][j - 1], f[prev][j]) + triangle[i][j];
        }
        f[curr][i] = f[prev][i - 1] + triangle[i][i];
    }
    
    return Math.min(...f[(n - 1) % 2].slice(0, n));
};

###TypeScript

function minimumTotal(triangle: number[][]): number {
    const n = triangle.length;
    const f: number[][] = Array.from({length: 2}, () => new Array(n).fill(0));
    f[0][0] = triangle[0][0];
    
    for (let i = 1; i < n; ++i) {
        const curr = i % 2;
        const prev = 1 - curr;
        f[curr][0] = f[prev][0] + triangle[i][0];
        for (let j = 1; j < i; ++j) {
            f[curr][j] = Math.min(f[prev][j - 1], f[prev][j]) + triangle[i][j];
        }
        f[curr][i] = f[prev][i - 1] + triangle[i][i];
    }
    
    return Math.min(...f[(n - 1) % 2].slice(0, n));
};

###Rust

impl Solution {
    pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
        let n = triangle.len();
        let mut f = vec![vec![0; n]; 2];
        f[0][0] = triangle[0][0];
        
        for i in 1..n {
            let curr = i % 2;
            let prev = 1 - curr;
            f[curr][0] = f[prev][0] + triangle[i][0];
            for j in 1..i {
                f[curr][j] = std::cmp::min(f[prev][j - 1], f[prev][j]) + triangle[i][j];
            }
            f[curr][i] = f[prev][i - 1] + triangle[i][i];
        }
        
        *f[(n - 1) % 2][..n].iter().min().unwrap()
    }
}

上述方法的空间复杂度为 $O(n)$，使用了 $2n$ 的空间存储状态。我们还可以继续进行优化吗？

答案是可以的。我们从 $i$ 到 $0$ 递减地枚举 $j$，这样我们只需要一个长度为 $n$ 的一维数组 $f$，就可以完成状态转移。

为什么只有在递减地枚举 $j$ 时，才能省去一个一维数组？当我们在计算位置 $(i, j)$ 时，$f[j+1]$ 到 $f[i]$ 已经是第 $i$ 行的值，而 $f[0]$ 到 $f[j]$ 仍然是第 $i-1$ 行的值。此时我们直接通过

$$
f[j] = \min(f[j-1], f[j]) + c[i][j]
$$

进行转移，恰好就是在 $(i-1, j-1)$ 和 $(i-1, j)$ 中进行选择。但如果我们递增地枚举 $j$，那么在计算位置 $(i, j)$ 时，$f[0]$ 到 $f[j-1]$ 已经是第 $i$ 行的值。如果我们仍然使用上述状态转移方程，那么是在 $(i, j-1)$ 和 $(i-1, j)$ 中进行选择，就产生了错误。

这样虽然空间复杂度仍然为 $O(n)$，但我们只使用了 $n$ 的空间存储状态，减少了一半的空间消耗。

###C++

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> f(n);
        f[0] = triangle[0][0];
        for (int i = 1; i < n; ++i) {
            f[i] = f[i - 1] + triangle[i][i];
            for (int j = i - 1; j > 0; --j) {
                f[j] = min(f[j - 1], f[j]) + triangle[i][j];
            }
            f[0] += triangle[i][0];
        }
        return *min_element(f.begin(), f.end());
    }
};

###Java

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] f = new int[n];
        f[0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            f[i] = f[i - 1] + triangle.get(i).get(i);
            for (int j = i - 1; j > 0; --j) {
                f[j] = Math.min(f[j - 1], f[j]) + triangle.get(i).get(j);
            }
            f[0] += triangle.get(i).get(0);
        }
        int minTotal = f[0];
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, f[i]);
        }
        return minTotal;
    }
}

###Python

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        f = [0] * n
        f[0] = triangle[0][0]

        for i in range(1, n):
            f[i] = f[i - 1] + triangle[i][i]
            for j in range(i - 1, 0, -1):
                f[j] = min(f[j - 1], f[j]) + triangle[i][j]
            f[0] += triangle[i][0]
        
        return min(f)

###Go

func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    f := make([]int, n)
    f[0] = triangle[0][0]
    for i := 1; i < n; i++ {
        f[i] = f[i - 1] + triangle[i][i]
        for j := i - 1; j > 0; j-- {
            f[j] = min(f[j - 1], f[j]) + triangle[i][j]
        }
        f[0] += triangle[i][0]
    }
    ans := math.MaxInt32
    for i := 0; i < n; i++ {
        ans = min(ans, f[i])
    }
    return ans
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

###C

int minimumTotal(int** triangle, int triangleSize, int* triangleColSize) {
    int f[triangleSize];
    memset(f, 0, sizeof(f));
    f[0] = triangle[0][0];
    for (int i = 1; i < triangleSize; ++i) {
        f[i] = f[i - 1] + triangle[i][i];
        for (int j = i - 1; j > 0; --j) {
            f[j] = fmin(f[j - 1], f[j]) + triangle[i][j];
        }
        f[0] += triangle[i][0];
    }
    int ret = f[0];
    for (int i = 1; i < triangleSize; i++) ret = fmin(ret, f[i]);
    return ret;
}

###C#

public class Solution {
    public int MinimumTotal(IList<IList<int>> triangle) {
        int n = triangle.Count;
        int[] f = new int[n];
        f[0] = triangle[0][0];
        
        for (int i = 1; i < n; ++i) {
            f[i] = f[i - 1] + triangle[i][i];
            for (int j = i - 1; j > 0; --j) {
                f[j] = Math.Min(f[j - 1], f[j]) + triangle[i][j];
            }
            f[0] += triangle[i][0];
        }
        
        return f.Min();
    }
}

###JavaScript

var minimumTotal = function(triangle) {
    const n = triangle.length;
    const f = new Array(n).fill(0);
    f[0] = triangle[0][0];
    
    for (let i = 1; i < n; ++i) {
        f[i] = f[i - 1] + triangle[i][i];
        for (let j = i - 1; j > 0; --j) {
            f[j] = Math.min(f[j - 1], f[j]) + triangle[i][j];
        }
        f[0] += triangle[i][0];
    }
    
    return Math.min(...f);
};

###TypeScript

function minimumTotal(triangle: number[][]): number {
    const n = triangle.length;
    const f: number[] = new Array(n).fill(0);
    f[0] = triangle[0][0];
    
    for (let i = 1; i < n; ++i) {
        f[i] = f[i - 1] + triangle[i][i];
        for (let j = i - 1; j > 0; --j) {
            f[j] = Math.min(f[j - 1], f[j]) + triangle[i][j];
        }
        f[0] += triangle[i][0];
    }
    
    return Math.min(...f);
};

###Rust

impl Solution {
    pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
        let n = triangle.len();
        let mut f = vec![0; n];
        f[0] = triangle[0][0];
        
        for i in 1..n {
            f[i] = f[i - 1] + triangle[i][i];
            for j in (1..i).rev() {
                f[j] = std::cmp::min(f[j - 1], f[j]) + triangle[i][j];
            }
            f[0] += triangle[i][0];
        }
        
        *f.iter().min().unwrap()
    }
}

复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 是三角形的行数。

• 空间复杂度：$O(n)$。

结语

本题还有一些其它的动态规划方法，例如：

• 从三角形的底部开始转移，到顶部结束；

• 直接在给定的三角形数组上进行状态转移，不使用额外的空间。

读者可以自行尝试。如果在面试中遇到类似的题目，需要和面试官进行沟通，可以询问「是否有空间复杂度限制」「是否可以修改原数组」等问题，给出符合条件的算法。

方法一：长除法

题目要求根据给定的分子和分母，将分数转成整数或小数。由于给定的分子和分母的取值范围都是 $[-2^{31}, 2^{31}-1]$，为了防止计算过程中产生溢出，需要将分子和分母转成 $64$ 位整数表示。

将分数转成整数或小数，做法是计算分子和分母相除的结果。可能的结果有三种：整数、有限小数、无限循环小数。

如果分子可以被分母整除，则结果是整数，将分子除以分母的商以字符串的形式返回即可。

如果分子不能被分母整除，则结果是有限小数或无限循环小数，需要通过模拟长除法的方式计算结果。为了方便处理，首先根据分子和分母的正负决定结果的正负（注意此时分子和分母都不为 $0$），然后将分子和分母都转成正数，再计算长除法。

计算长除法时，首先计算结果的整数部分，将以下部分依次拼接到结果中：

1. 如果结果是负数则将负号拼接到结果中，如果结果是正数则跳过这一步；

2. 将整数部分拼接到结果中；

3. 将小数点拼接到结果中。

完成上述拼接之后，根据余数计算小数部分。

计算小数部分时，每次将余数乘以 $10$，然后计算小数的下一位数字，并得到新的余数。重复上述操作直到余数变成 $0$ 或者找到循环节。

• 如果余数变成 $0$，则结果是有限小数，将小数部分拼接到结果中。

• 如果找到循环节，则找到循环节的开始位置和结束位置并加上括号，然后将小数部分拼接到结果中。

如何判断是否找到循环节？注意到对于相同的余数，计算得到的小数的下一位数字一定是相同的，因此如果计算过程中发现某一位的余数在之前已经出现过，则为找到循环节。为了记录每个余数是否已经出现过，需要使用哈希表存储每个余数在小数部分第一次出现的下标。

假设在计算小数部分的第 $i$ 位之前，余数为 $\textit{remainder}i$，则在计算小数部分的第 $i$ 位之后，余数为 $\textit{remainder}{i+1}$。

假设存在下标 $j$ 和 $k$，满足 $j \le k$ 且 $\textit{remainder}j = \textit{remainder}{k+1}$，则小数部分的第 $k+1$ 位和小数部分的第 $j$ 位相同，因此小数部分的第 $j$ 位到第 $k$ 位是一个循环节。在计算小数部分的第 $k$ 位之后就会发现这个循环节的存在，因此在小数部分的第 $j$ 位之前加上左括号，在小数部分的末尾（即第 $k$ 位之后）加上右括号。

###Java

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        long numeratorLong = (long) numerator;
        long denominatorLong = (long) denominator;
        if (numeratorLong % denominatorLong == 0) {
            return String.valueOf(numeratorLong / denominatorLong);
        }

        StringBuffer sb = new StringBuffer();
        if (numeratorLong < 0 ^ denominatorLong < 0) {
            sb.append('-');
        }

        // 整数部分
        numeratorLong = Math.abs(numeratorLong);
        denominatorLong = Math.abs(denominatorLong);
        long integerPart = numeratorLong / denominatorLong;
        sb.append(integerPart);
        sb.append('.');

        // 小数部分
        StringBuffer fractionPart = new StringBuffer();
        Map<Long, Integer> remainderIndexMap = new HashMap<Long, Integer>();
        long remainder = numeratorLong % denominatorLong;
        int index = 0;
        while (remainder != 0 && !remainderIndexMap.containsKey(remainder)) {
            remainderIndexMap.put(remainder, index);
            remainder *= 10;
            fractionPart.append(remainder / denominatorLong);
            remainder %= denominatorLong;
            index++;
        }
        if (remainder != 0) { // 有循环节
            int insertIndex = remainderIndexMap.get(remainder);
            fractionPart.insert(insertIndex, '(');
            fractionPart.append(')');
        }
        sb.append(fractionPart.toString());

        return sb.toString();
    }
}

###C#

public class Solution {
    public string FractionToDecimal(int numerator, int denominator) {
        long numeratorLong = (long) numerator;
        long denominatorLong = (long) denominator;
        if (numeratorLong % denominatorLong == 0) {
            return (numeratorLong / denominatorLong).ToString();
        }

        StringBuilder sb = new StringBuilder();
        if (numeratorLong < 0 ^ denominatorLong < 0) {
            sb.Append('-');
        }

        // 整数部分
        numeratorLong = Math.Abs(numeratorLong);
        denominatorLong = Math.Abs(denominatorLong);
        long integerPart = numeratorLong / denominatorLong;
        sb.Append(integerPart);
        sb.Append('.');

        // 小数部分
        StringBuilder fractionPart = new StringBuilder();
        Dictionary<long, int> remainderIndexDic = new Dictionary<long, int>();
        long remainder = numeratorLong % denominatorLong;
        int index = 0;
        while (remainder != 0 && !remainderIndexDic.ContainsKey(remainder)) {
            remainderIndexDic.Add(remainder, index);
            remainder *= 10;
            fractionPart.Append(remainder / denominatorLong);
            remainder %= denominatorLong;
            index++;
        }
        if (remainder != 0) { // 有循环节
            int insertIndex = remainderIndexDic[remainder];
            fractionPart.Insert(insertIndex, '(');
            fractionPart.Append(')');
        }
        sb.Append(fractionPart.ToString());

        return sb.ToString();
    }
}

###JavaScript

var fractionToDecimal = function(numerator, denominator) {
    if (numerator % denominator == 0) {
        return '' + Math.floor(numerator / denominator);
    }

    const sb = [];
    if (numerator < 0 ^ denominator < 0) {
        sb.push('-');
    }

    // 整数部分
    numerator = Math.abs(numerator);
    denominator = Math.abs(denominator);
    const integerPart = Math.floor(numerator / denominator);
    sb.push(integerPart);
    sb.push('.');

    // 小数部分
    const fractionPart = [];
    const remainderIndexDic = new Map();
    let remainder = numerator % denominator;
    let index = 0;
    while (remainder !== 0 && !remainderIndexDic.has(remainder)) {
        remainderIndexDic.set(remainder, index);
        remainder *= 10;
        fractionPart.push(Math.floor(remainder / denominator));
        remainder %= denominator;
        index++;
    }
    if (remainder !== 0) { // 有循环节
        let insertIndex = remainderIndexDic.get(remainder);
        fractionPart.splice(insertIndex, 0, '(');
        fractionPart.push(')');
    }
    sb.push(fractionPart.join(''));

    return sb.join('');
}

###go

func fractionToDecimal(numerator, denominator int) string {
    if numerator%denominator == 0 {
        return strconv.Itoa(numerator / denominator)
    }

    s := []byte{}
    if numerator < 0 != (denominator < 0) {
        s = append(s, '-')
    }

    // 整数部分
    numerator = abs(numerator)
    denominator = abs(denominator)
    integerPart := numerator / denominator
    s = append(s, strconv.Itoa(integerPart)...)
    s = append(s, '.')

    // 小数部分
    indexMap := map[int]int{}
    remainder := numerator % denominator
    for remainder != 0 && indexMap[remainder] == 0 {
        indexMap[remainder] = len(s)
        remainder *= 10
        s = append(s, '0'+byte(remainder/denominator))
        remainder %= denominator
    }
    if remainder > 0 { // 有循环节
        insertIndex := indexMap[remainder]
        s = append(s[:insertIndex], append([]byte{'('}, s[insertIndex:]...)...)
        s = append(s, ')')
    }

    return string(s)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

###C++

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        long numeratorLong = numerator;
        long denominatorLong = denominator;
        if (numeratorLong % denominatorLong == 0) {
            return to_string(numeratorLong / denominatorLong);
        }

        string ans;
        if (numeratorLong < 0 ^ denominatorLong < 0) {
            ans.push_back('-');
        }

        // 整数部分
        numeratorLong = abs(numeratorLong);
        denominatorLong = abs(denominatorLong);
        long integerPart = numeratorLong / denominatorLong;
        ans += to_string(integerPart);
        ans.push_back('.');

        // 小数部分
        string fractionPart;
        unordered_map<long, int> remainderIndexMap;
        long remainder = numeratorLong % denominatorLong;
        int index = 0;
        while (remainder != 0 && !remainderIndexMap.count(remainder)) {
            remainderIndexMap[remainder] = index;
            remainder *= 10;
            fractionPart += to_string(remainder / denominatorLong);
            remainder %= denominatorLong;
            index++;
        }
        if (remainder != 0) { // 有循环节
            int insertIndex = remainderIndexMap[remainder];
            fractionPart = fractionPart.substr(0,insertIndex) + '(' + fractionPart.substr(insertIndex);
            fractionPart.push_back(')');
        }
        ans += fractionPart;

        return ans;
    }
};

###Python

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator % denominator == 0:
            return str(numerator // denominator)

        s = []
        if (numerator < 0) != (denominator < 0):
            s.append('-')

        # 整数部分
        numerator = abs(numerator)
        denominator = abs(denominator)
        integerPart = numerator // denominator
        s.append(str(integerPart))
        s.append('.')

        # 小数部分
        indexMap = {}
        remainder = numerator % denominator
        while remainder and remainder not in indexMap:
            indexMap[remainder] = len(s)
            remainder *= 10
            s.append(str(remainder // denominator))
            remainder %= denominator
        if remainder:  # 有循环节
            insertIndex = indexMap[remainder]
            s.insert(insertIndex, '(')
            s.append(')')

        return ''.join(s)

复杂度分析

• 时间复杂度：$O(l)$，其中 $l$ 是答案字符串的长度，这道题中 $l \le 10^4$。对于答案字符串中的每一个字符，计算时间都是 $O(1)$。

• 空间复杂度：$O(l)$，其中 $l$ 是答案字符串的长度，这道题中 $l \le 10^4$。空间复杂度主要取决于答案字符串和哈希表，哈希表中的每个键值对所对应的下标各不相同，因此键值对的数量不会超过 $l$。

方法一：字符串分割

我们可以将版本号按照点号分割成修订号，然后从左到右比较两个版本号的相同下标的修订号。在比较修订号时，需要将字符串转换成整数进行比较。注意根据题目要求，如果版本号不存在某个下标处的修订号，则该修订号视为 $0$。

###Python

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        for v1, v2 in zip_longest(version1.split('.'), version2.split('.'), fillvalue=0):
            x, y = int(v1), int(v2)
            if x != y:
                return 1 if x > y else -1
        return 0

###Java

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        for (int i = 0; i < v1.length || i < v2.length; ++i) {
            int x = 0, y = 0;
            if (i < v1.length) {
                x = Integer.parseInt(v1[i]);
            }
            if (i < v2.length) {
                y = Integer.parseInt(v2[i]);
            }
            if (x > y) {
                return 1;
            }
            if (x < y) {
                return -1;
            }
        }
        return 0;
    }
}

###C#

public class Solution {
    public int CompareVersion(string version1, string version2) {
        string[] v1 = version1.Split('.');
        string[] v2 = version2.Split('.');
        for (int i = 0; i < v1.Length || i < v2.Length; ++i) {
            int x = 0, y = 0;
            if (i < v1.Length) {
                x = int.Parse(v1[i]);
            }
            if (i < v2.Length) {
                y = int.Parse(v2[i]);
            }
            if (x > y) {
                return 1;
            }
            if (x < y) {
                return -1;
            }
        }
        return 0;
    }
}

###go

func compareVersion(version1, version2 string) int {
    v1 := strings.Split(version1, ".")
    v2 := strings.Split(version2, ".")
    for i := 0; i < len(v1) || i < len(v2); i++ {
        x, y := 0, 0
        if i < len(v1) {
            x, _ = strconv.Atoi(v1[i])
        }
        if i < len(v2) {
            y, _ = strconv.Atoi(v2[i])
        }
        if x > y {
            return 1
        }
        if x < y {
            return -1
        }
    }
    return 0
}

###JavaScript

var compareVersion = function(version1, version2) {
    const v1 = version1.split('.');
    const v2 = version2.split('.');
    for (let i = 0; i < v1.length || i < v2.length; ++i) {
        let x = 0, y = 0;
        if (i < v1.length) {
            x = parseInt(v1[i]);
        }
        if (i < v2.length) {
            y = parseInt(v2[i]);
        }
        if (x > y) {
            return 1;
        }
        if (x < y) {
            return -1;
        }
    }
    return 0;
};

• 时间复杂度：$O(n+m)$（或 $O(\max(n,m))$，这是等价的），其中 $n$ 是字符串 $\textit{version1}$ 的长度，$m$ 是字符串 $\textit{version2}$ 的长度。

• 空间复杂度：$O(n+m)$，我们需要 $O(n+m)$ 的空间存储分割后的修订号列表。

方法二：双指针

方法一需要存储分割后的修订号，为了优化空间复杂度，我们可以在分割版本号的同时解析出修订号进行比较。

###Python

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        n, m = len(version1), len(version2)
        i, j = 0, 0
        while i < n or j < m:
            x = 0
            while i < n and version1[i] != '.':
                x = x * 10 + ord(version1[i]) - ord('0')
                i += 1
            i += 1  # 跳过点号
            y = 0
            while j < m and version2[j] != '.':
                y = y * 10 + ord(version2[j]) - ord('0')
                j += 1
            j += 1  # 跳过点号
            if x != y:
                return 1 if x > y else -1
        return 0

###C++

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int n = version1.length(), m = version2.length();
        int i = 0, j = 0;
        while (i < n || j < m) {
            long long x = 0;
            for (; i < n && version1[i] != '.'; ++i) {
                x = x * 10 + version1[i] - '0';
            }
            ++i; // 跳过点号
            long long y = 0;
            for (; j < m && version2[j] != '.'; ++j) {
                y = y * 10 + version2[j] - '0';
            }
            ++j; // 跳过点号
            if (x != y) {
                return x > y ? 1 : -1;
            }
        }
        return 0;
    }
};

###Java

class Solution {
    public int compareVersion(String version1, String version2) {
        int n = version1.length(), m = version2.length();
        int i = 0, j = 0;
        while (i < n || j < m) {
            int x = 0;
            for (; i < n && version1.charAt(i) != '.'; ++i) {
                x = x * 10 + version1.charAt(i) - '0';
            }
            ++i; // 跳过点号
            int y = 0;
            for (; j < m && version2.charAt(j) != '.'; ++j) {
                y = y * 10 + version2.charAt(j) - '0';
            }
            ++j; // 跳过点号
            if (x != y) {
                return x > y ? 1 : -1;
            }
        }
        return 0;
    }
}

###C#

public class Solution {
    public int CompareVersion(string version1, string version2) {
        int n = version1.Length, m = version2.Length;
        int i = 0, j = 0;
        while (i < n || j < m) {
            int x = 0;
            for (; i < n && version1[i] != '.'; ++i) {
                x = x * 10 + version1[i] - '0';
            }
            ++i; // 跳过点号
            int y = 0;
            for (; j < m && version2[j] != '.'; ++j) {
                y = y * 10 + version2[j] - '0';
            }
            ++j; // 跳过点号
            if (x != y) {
                return x > y ? 1 : -1;
            }
        }
        return 0;
    }
}

###go

func compareVersion(version1, version2 string) int {
    n, m := len(version1), len(version2)
    i, j := 0, 0
    for i < n || j < m {
        x := 0
        for ; i < n && version1[i] != '.'; i++ {
            x = x*10 + int(version1[i]-'0')
        }
        i++ // 跳过点号
        y := 0
        for ; j < m && version2[j] != '.'; j++ {
            y = y*10 + int(version2[j]-'0')
        }
        j++ // 跳过点号
        if x > y {
            return 1
        }
        if x < y {
            return -1
        }
    }
    return 0
}

###JavaScript

var compareVersion = function(version1, version2) {
    const n = version1.length, m = version2.length;
    let i = 0, j = 0;
    while (i < n || j < m) {
        let x = 0;
        for (; i < n && version1[i] !== '.'; ++i) {
            x = x * 10 + version1[i].charCodeAt() - '0'.charCodeAt();
        }
        ++i; // 跳过点号
        let y = 0;
        for (; j < m && version2.charAt(j) !== '.'; ++j) {
            y = y * 10 + version2[j].charCodeAt() - '0'.charCodeAt();
        }
        ++j; // 跳过点号
        if (x !== y) {
            return x > y ? 1 : -1;
        }
    }
    return 0;
};

复杂度分析

• 时间复杂度：$O(n+m)$，其中 $n$ 是字符串 $\textit{version1}$ 的长度，$m$ 是字符串 $\textit{version2}$ 的长度。

• 空间复杂度：$O(1)$，我们只需要常数的空间保存若干变量。

方法一：使用合适的数据结构

提示 $1$

对于一部电影，每个商店至多有一部它的拷贝，因此我们可以将 $(\textit{shop}, \textit{movie})$ 这一二元组作为数组 $\textit{entries}$ 中电影的唯一标识。

因此，我们可以使用一个哈希映射 $\textit{t_price}$ 存储所有的电影。对于哈希映射中的每一个键值对，键表示 $(\textit{shop}, \textit{movie})$，值表示该电影的价格。

提示 $2$

我们可以考虑禁止修改 $\textit{t_price}$，即在任何情况下（例如 $\texttt{rent}$ 操作或者 $\texttt{drop}$ 操作），我们都不会去修改 $\textit{t_price}$ 本身。因此，我们需要两个额外的数据结构，一个存储未借出的电影 $\textit{t_valid}$，一个存储已借出的电影 $\textit{t_rent}$。

我们应该使用何种数据结构呢？

提示 $3$

对于未借出的电影，我们需要支持以下的三种操作：

• $\texttt{search(movie)}$ 操作，即给定 $\textit{movie}$ 查找出最便宜的 $5$ 个 $\textit{shop}$。因此，$\textit{t_valid}$ 最好「相对于 $\textit{movie}$」是一个有序的数据结构。

  我们可以考虑将 $\textit{t_valid}$ 设计成一个哈希映射，键表示 $\textit{movie}$，值为一个有序集合（例如平衡树），存储了所有拥有 $\textit{movie}$ 的 $\textit{shop}$。由于在 $\texttt{search}$ 操作中，我们需要按照 $\textit{price}$ 为第一关键字，$\textit{shop}$ 为第二关键字返回结果，因此我们可以在有序集合中存储 $(\textit{price}, \textit{shop})$ 这一二元组。

• $\texttt{rent(shop, movie)}$ 操作。我们只需要通过 $\textit{t_price}[(\textit{shop}, \textit{movie})]$ 得到 $\textit{price}$，从 $\textit{t_valid}[\textit{movie}]$ 中删除 $(\textit{price}, \textit{shop})$ 即可。

• $\texttt{drop(shop, movie)}$ 操作。我们只需要通过 $\textit{t_price}[(\textit{shop}, \textit{movie})]$ 得到 $\textit{price}$，将 $(\textit{price}, \textit{shop})$ 加入 $\textit{t_valid}[\textit{movie}]$ 即可。

对于已借出的电影，我们需要支持以下的三种操作：

• $\texttt{report()}$ 操作，即查找出最便宜的 $5$ 部电影。由于我们需要按照 $\textit{price}$ 为第一关键字，$\textit{shop}$ 为第二关键字，$\textit{movie}$ 为第三关键字返回结果，因此我们同样可以使用一个有序集合表示 $\textit{t_rent}$，存储三元组 $(\textit{price}, \textit{shop}, \textit{movie})$。

• $\texttt{rent(shop, movie)}$ 操作。我们只需要通过 $\textit{t_price}[(\textit{shop}, \textit{movie})]$ 得到 $\textit{price}$，将 $(\textit{price}, \textit{shop}, \textit{movie})$ 加入 $\textit{t_rent}$ 即可。

• $\texttt{drop(shop, movie)}$ 操作。我们只需要通过 $\textit{t_price}[(\textit{shop}, \textit{movie})]$ 得到 $\textit{price}$，从 $\textit{t_rent}$ 中删除 $(\textit{price}, \textit{shop}, \textit{movie})$ 即可。

思路与算法

我们使用提示部分提及的数据结构 $\textit{t_price}$，$\textit{t_valid}$，$\textit{t_rent}$。

• 对于 $\texttt{MovieRentingSystem(n, entries)}$ 操作：我们遍历 $\textit{entries}$ 中的 $(\textit{shop}, \textit{movie}, \textit{price})$，将 $(\textit{shop}, \textit{movie})$ 作为键、$\textit{price}$ 作为值加入 $\textit{t_price}$，并且将 $(\textit{price}, \textit{shop})$ 加入 $\textit{t_valid}[\textit{movie}]$。

• 对于 $\texttt{search(movie)}$ 操作，我们遍历 $\textit{t_valid}[\textit{movie}]$ 中不超过 $5$ 个 $(\textit{price}, \textit{shop})$，并返回其中的 $\textit{shop}$。

• 对于 $\texttt{rent(shop, movie)}$ 操作，我们通过 $\textit{t_price}[(\textit{shop}, \textit{movie})]$ 得到 $\textit{price}$，从 $\textit{t_valid}[\textit{movie}]$ 中删除 $(\textit{price}, \textit{shop})$，并且将 $(\textit{price}, \textit{shop}, \textit{movie})$ 加入 $\textit{t_rent}$。

• 对于 $\texttt{drop(shop, movie)}$ 操作，我们通过 $\textit{t_price}[(\textit{shop}, \textit{movie})]$ 得到 $\textit{price}$，将 $(\textit{price}, \textit{shop})$ 加入 $\textit{t_valid}[\textit{movie}]$，并且从 $\textit{t_rent}$ 中删除 $(\textit{price}, \textit{shop}, \textit{movie})$。

• 对于 $\texttt{report()}$ 操作，我们遍历 $\textit{t_rent}$ 中不超过 $5$ 个 $(\textit{price}, \textit{shop}, \textit{movie})$，并返回其中的 $(\textit{shop}, \textit{movie})$。

代码

###C++

class MovieRentingSystem {
private:
    // 需要自行实现 pair<int, int> 的哈希函数
    static constexpr auto pairHash = [fn = hash<int>()](const pair<int, int>& o) {return (fn(o.first) << 16) ^ fn(o.second);};
    unordered_map<pair<int, int>, int, decltype(pairHash)> t_price{0, pairHash};

    unordered_map<int, set<pair<int, int>>> t_valid;

    set<tuple<int, int, int>> t_rent;

public:
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for (const auto& entry: entries) {
            t_price[{entry[0], entry[1]}] = entry[2];
            t_valid[entry[1]].emplace(entry[2], entry[0]);
        }
    }
    
    vector<int> search(int movie) {
        if (!t_valid.count(movie)) {
            return {};
        }
        
        vector<int> ret;
        auto it = t_valid[movie].begin();
        for (int i = 0; i < 5 && it != t_valid[movie].end(); ++i, ++it) {
            ret.push_back(it->second);
        }
        return ret;
    }
    
    void rent(int shop, int movie) {
        int price = t_price[{shop, movie}];
        t_valid[movie].erase({price, shop});
        t_rent.emplace(price, shop, movie);
    }
    
    void drop(int shop, int movie) {
        int price = t_price[{shop, movie}];
        t_valid[movie].emplace(price, shop);
        t_rent.erase({price, shop, movie});
    }
    
    vector<vector<int>> report() {
        vector<vector<int>> ret;
        auto it = t_rent.begin();
        for (int i = 0; i < 5 && it != t_rent.end(); ++i, ++it) {
            ret.emplace_back(initializer_list<int>{get<1>(*it), get<2>(*it)});
        }
        return ret;
    }
};

###Python

class MovieRentingSystem:

    def __init__(self, n: int, entries: List[List[int]]):
        self.t_price = dict()
        self.t_valid = defaultdict(sortedcontainers.SortedList)
        self.t_rent = sortedcontainers.SortedList()
        
        for shop, movie, price in entries:
            self.t_price[(shop, movie)] = price
            self.t_valid[movie].add((price, shop))

    def search(self, movie: int) -> List[int]:
        t_valid_ = self.t_valid
        
        if movie not in t_valid_:
            return []
        
        return [shop for (price, shop) in t_valid_[movie][:5]]
        
    def rent(self, shop: int, movie: int) -> None:
        price = self.t_price[(shop, movie)]
        self.t_valid[movie].discard((price, shop))
        self.t_rent.add((price, shop, movie))

    def drop(self, shop: int, movie: int) -> None:
        price = self.t_price[(shop, movie)]
        self.t_valid[movie].add((price, shop))
        self.t_rent.discard((price, shop, movie))

    def report(self) -> List[List[int]]:
        return [(shop, movie) for price, shop, movie in self.t_rent[:5]]

###Java

class Pair {
    int first, second;
    Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Pair pair = (Pair) o;
        return first == pair.first && second == pair.second;
    }
    
    @Override
    public int hashCode() {
        return (first << 16) ^ second;
    }
}

class Triple implements Comparable<Triple> {
    int price, shop, movie;
    Triple(int price, int shop, int movie) {
        this.price = price;
        this.shop = shop;
        this.movie = movie;
    }
    
    @Override
    public int compareTo(Triple o) {
        if (price != o.price) {
            return Integer.compare(price, o.price);
        }
        if (shop != o.shop) {
            return Integer.compare(shop, o.shop);
        }
        return Integer.compare(movie, o.movie);
    }
}

class MovieRentingSystem {
    private Map<Pair, Integer> tPrice = new HashMap<>();
    private Map<Integer, TreeSet<Pair>> tValid = new HashMap<>();
    private TreeSet<Triple> tRent = new TreeSet<>();

    public MovieRentingSystem(int n, int[][] entries) {
        for (int[] entry : entries) {
            Pair p = new Pair(entry[0], entry[1]);
            tPrice.put(p, entry[2]);
            tValid.computeIfAbsent(entry[1], k -> new TreeSet<>(
                (a, b) -> a.first != b.first ? Integer.compare(a.first, b.first) 
                                             : Integer.compare(a.second, b.second)
            )).add(new Pair(entry[2], entry[0]));
        }
    }
    
    public List<Integer> search(int movie) {
        if (!tValid.containsKey(movie)) {
            return Collections.emptyList();
        }
        return tValid.get(movie).stream()
            .limit(5)
            .map(p -> p.second)
            .collect(Collectors.toList());
    }
    
    public void rent(int shop, int movie) {
        int price = tPrice.get(new Pair(shop, movie));
        tValid.get(movie).remove(new Pair(price, shop));
        tRent.add(new Triple(price, shop, movie));
    }
    
    public void drop(int shop, int movie) {
        int price = tPrice.get(new Pair(shop, movie));
        tValid.get(movie).add(new Pair(price, shop));
        tRent.remove(new Triple(price, shop, movie));
    }
    
    public List<List<Integer>> report() {
        return tRent.stream()
            .limit(5)
            .map(t -> Arrays.asList(t.shop, t.movie))
            .collect(Collectors.toList());
    }
}

###C#

struct Pair : IEquatable<Pair> {
    public int First { get; }
    public int Second { get; }
    
    public Pair(int first, int second) {
        First = first;
        Second = second;
    }
    
    public bool Equals(Pair other) => First == other.First && Second == other.Second;
    public override bool Equals(object obj) => obj is Pair other && Equals(other);
    public override int GetHashCode() => (First << 16) ^ Second;
}

public class MovieRentingSystem {
    private Dictionary<Pair, int> tPrice = new Dictionary<Pair, int>();
    private Dictionary<int, SortedSet<Pair>> tValid = new Dictionary<int, SortedSet<Pair>>();
    private SortedSet<(int price, int shop, int movie)> tRent = new SortedSet<(int, int, int)>();
    
    public MovieRentingSystem(int n, int[][] entries) {
        foreach (var entry in entries) {
            var p = new Pair(entry[0], entry[1]);
            tPrice[p] = entry[2];
            if (!tValid.ContainsKey(entry[1])) {
                tValid[entry[1]] = new SortedSet<Pair>(Comparer<Pair>.Create((a, b) => 
                    a.First != b.First ? a.First.CompareTo(b.First) : a.Second.CompareTo(b.Second)));
            }
            tValid[entry[1]].Add(new Pair(entry[2], entry[0]));
        }
    }
    
    public IList<int> Search(int movie) {
        if (!tValid.ContainsKey(movie)) {
            return new List<int>();
        }
        return tValid[movie].Take(5).Select(p => p.Second).ToList();
    }
    
    public void Rent(int shop, int movie) {
        var p = new Pair(shop, movie);
        int price = tPrice[p];
        tValid[movie].Remove(new Pair(price, shop));
        tRent.Add((price, shop, movie));
    }
    
    public void Drop(int shop, int movie) {
        var p = new Pair(shop, movie);
        int price = tPrice[p];
        tValid[movie].Add(new Pair(price, shop));
        tRent.Remove((price, shop, movie));
    }
    
    public IList<IList<int>> Report() {
        return tRent.Take(5).Select(t => new List<int> { t.shop, t.movie }).ToList<IList<int>>();
    }
}

###Rust

use std::collections::{HashMap, BTreeSet};
use std::cmp::Ordering;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
struct Pair {
    first: i32,
    second: i32,
}

impl Pair {
    fn new(first: i32, second: i32) -> Self {
        Pair { first, second }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Triple {
    price: i32,
    shop: i32,
    movie: i32,
}

impl Triple {
    fn new(price: i32, shop: i32, movie: i32) -> Self {
        Triple { price, shop, movie }
    }
}

struct MovieRentingSystem {
    t_price: HashMap<Pair, i32>,
    t_valid: HashMap<i32, BTreeSet<Pair>>,
    t_rent: BTreeSet<Triple>,
}

impl MovieRentingSystem {
    fn new(n: i32, entries: Vec<Vec<i32>>) -> Self {
        let mut t_price = HashMap::new();
        let mut t_valid = HashMap::new();
        
        for entry in entries {
            let shop = entry[0];
            let movie = entry[1];
            let price = entry[2];
            t_price.insert(Pair::new(shop, movie), price);
            t_valid.entry(movie)
                .or_insert_with(BTreeSet::new)
                .insert(Pair::new(price, shop));
        }
        
        MovieRentingSystem {
            t_price,
            t_valid,
            t_rent: BTreeSet::new(),
        }
    }
    
    fn search(&self, movie: i32) -> Vec<i32> {
        self.t_valid.get(&movie)
            .map_or_else(Vec::new, |set| {
                set.iter()
                    .take(5)
                    .map(|p| p.second)
                    .collect()
            })
    }
    
    fn rent(&mut self, shop: i32, movie: i32) {
        let price = self.t_price[&Pair::new(shop, movie)];
        self.t_valid.get_mut(&movie).unwrap().remove(&Pair::new(price, shop));
        self.t_rent.insert(Triple::new(price, shop, movie));
    }
    
    fn drop(&mut self, shop: i32, movie: i32) {
        let price = self.t_price[&Pair::new(shop, movie)];
        self.t_valid.get_mut(&movie).unwrap().insert(Pair::new(price, shop));
        self.t_rent.remove(&Triple::new(price, shop, movie));
    }
    
    fn report(&self) -> Vec<Vec<i32>> {
        self.t_rent.iter()
            .take(5)
            .map(|t| vec![t.shop, t.movie])
            .collect()
    }
}

复杂度分析

• 时间复杂度：

  • $\texttt{MovieRentingSystem(n, entries)}$ 操作：$O(n \log n)$。

  • $\texttt{search(movie)}$ 操作：$O(\log n)$。

  • $\texttt{rent(shop, movie)}$ 操作：$O(\log n)$。

  • $\texttt{drop(shop, movie)}$ 操作：$O(\log n)$。

  • $\texttt{report()}$ 操作：$O(\log n)$。

• 空间复杂度：$O(n)$。

方法一：模拟

思路与算法

根据题意可知，我们可以直接使用行数为 $\textit{rows}$，列数为 $26$ 的二维数组 $\textit{grid}$ 来保存每个单元格的值，此时查询和更新单元格时，直接查询和更新二维数组中的元素即可，$\text{Spreadsheet}$ 类实现如下：

• 初始化：调用 $\text{Spreadsheet(int rows)}$，创建行数为 $\textit{rows}$，列数为 $26$ 的二维数组 $\textit{grid}$，并将数组元素初始化为 $0$；

• $\text{void setCell(String cell, int value)}$：设置指定单元格的值为 $\textit{value}$，按照规则从 字符串 $\textit{cell}$ 中解析出单元格对应的行数与列数，并将对应的二维数组 $\textit{grid}$ 对应元素的值设置为 $\textit{value}$；

• $\text{void resetCell(String cell)}$：重置指定单元格的值为 $0$。按照规则从字符串 $\textit{cell}$ 中解析出单元格对应的行数与列数，并将对应的二维数组 $\textit{grid}$ 对应元素的值设置为 $0$；

• $\text{int getValue(String formula)}$：计算一个公式的值。根据题目为可知公式格式为："=X+Y"，从 $\textit{formula}$ 按照给定格式解析出 $\text{X}$ 与 $\text{Y}$。如果 $\text{X}$ 或 $\text{Y}$ 的首字母为字母，则其为单元格，此时从二维数组中 $\textit{grid}$ 读取对应的值；如果其首字母为数字，则其为整数，分别求出 $\text{X}$ 与 $\text{Y}$ 对应的值，并返回二者相加的和即为答案。

代码

###C++

class Spreadsheet {
public:
    Spreadsheet(int rows) {
        this->grid = vector<vector<int>>(rows + 1, vector<int>(26));
    }

    void setCell(string cell, int value) {
        auto [x, y] = getPos(cell);
        grid[x][y] = value;
    }
    
    void resetCell(string cell) {
        auto [x, y] = getPos(cell);
        grid[x][y] = 0;
    }
    
    int getValue(string formula) {
        int i = formula.find('+');
        string cell1 = formula.substr(1, i - 1);
        string cell2 = formula.substr(i + 1);
        return getCellVal(cell1) + getCellVal(cell2);
    }

private:
    vector<vector<int>> grid;

    pair<int, int> getPos(const string &cell) {
        int x = stoi(cell.substr(1));
        int y = cell[0] - 'A';
        return {x, y};
    }

    int getCellVal(string &cell) {
        if (isalpha(cell[0])) {
            auto [x, y] = getPos(cell);
            return grid[x][y];
        } else {
            return stoi(cell);
        }
    }
};

###Java

public class Spreadsheet {
    private int[][] grid;

    public Spreadsheet(int rows) {
        this.grid = new int[rows + 1][26];
    }

    public void setCell(String cell, int value) {
        int[] pos = getPos(cell);
        grid[pos[0]][pos[1]] = value;
    }
    
    public void resetCell(String cell) {
        int[] pos = getPos(cell);
        grid[pos[0]][pos[1]] = 0;
    }
    
    public int getValue(String formula) {
        int i = formula.indexOf('+');
        String cell1 = formula.substring(1, i);
        String cell2 = formula.substring(i + 1);
        return getCellVal(cell1) + getCellVal(cell2);
    }

    private int[] getPos(String cell) {
        int x = Integer.parseInt(cell.substring(1));
        int y = cell.charAt(0) - 'A';
        return new int[]{x, y};
    }

    private int getCellVal(String cell) {
        if (Character.isLetter(cell.charAt(0))) {
            int[] pos = getPos(cell);
            return grid[pos[0]][pos[1]];
        } else {
            return Integer.parseInt(cell);
        }
    }
}

###C#

public class Spreadsheet {
    private int[,] grid;

    public Spreadsheet(int rows) {
        this.grid = new int[rows + 1, 26];
    }

    public void SetCell(string cell, int value) {
        var pos = GetPos(cell);
        grid[pos.Item1, pos.Item2] = value;
    }
    
    public void ResetCell(string cell) {
        var pos = GetPos(cell);
        grid[pos.Item1, pos.Item2] = 0;
    }
    
    public int GetValue(string formula) {
        int i = formula.IndexOf('+');
        string cell1 = formula.Substring(1, i - 1);
        string cell2 = formula.Substring(i + 1);
        return GetCellVal(cell1) + GetCellVal(cell2);
    }

    private Tuple<int, int> GetPos(string cell) {
        int x = int.Parse(cell.Substring(1));
        int y = cell[0] - 'A';
        return Tuple.Create(x, y);
    }

    private int GetCellVal(string cell) {
        if (char.IsLetter(cell[0])) {
            var pos = GetPos(cell);
            return grid[pos.Item1, pos.Item2];
        } else {
            return int.Parse(cell);
        }
    }
}

###Python

class Spreadsheet:

    def __init__(self, rows: int):
        self.grid = [[0] * 27 for _ in range(rows + 1)]

    def setCell(self, cell: str, value: int) -> None:
        x, y = self.getPos(cell)
        self.grid[x][y] = value

    def resetCell(self, cell: str) -> None:
        x, y = self.getPos(cell)
        self.grid[x][y] = 0

    def getValue(self, formula: str) -> int:
        i = formula.find('+')
        cell1 = formula[1:i]
        cell2 = formula[i + 1:]
        return self.getCellVal(cell1) + self.getCellVal(cell2)

    def getPos(self, cell):
        x = int(cell[1:])
        y = ord(cell[0]) - ord('A')
        return (x, y)

    def getCellVal(self, cell):
        if cell[0].isalpha():
            x, y = self.getPos(cell)
            return self.grid[x][y]
        else:
            return int(cell)

###Go

type Spreadsheet struct {
grid [][]int
}

func Constructor(rows int) Spreadsheet {
    grid := make([][]int, rows+1)
for i := range grid {
grid[i] = make([]int, 27)
}
return Spreadsheet{grid: grid}
}

func (this *Spreadsheet) SetCell(cell string, value int)  {
    x, y := this.getPos(cell)
this.grid[x][y] = value
}

func (this *Spreadsheet) ResetCell(cell string)  {
    x, y := this.getPos(cell)
this.grid[x][y] = 0
}

func (this *Spreadsheet) GetValue(formula string) int {
    i := strings.Index(formula, "+")
cell1 := formula[1:i]
cell2 := formula[i+1:]
return this.getCellVal(cell1) + this.getCellVal(cell2)
}

func (this *Spreadsheet) getPos(cell string) (int, int) {
x, _ := strconv.Atoi(cell[1:])
y := int(cell[0] - 'A')
return x, y
}

func (this *Spreadsheet) getCellVal(cell string) int {
if cell[0] >= 'A' && cell[0] <= 'Z' {
x, y := this.getPos(cell)
return this.grid[x][y]
} else {
val, _ := strconv.Atoi(cell)
return val
}
}

###C

#define COLUMNS 26

typedef struct {
    int** grid;
    int rows;
} Spreadsheet;

void getPos(const char* cell, int* x, int* y) {
    *x = atoi(cell + 1);
    *y = toupper(cell[0]) - 'A';
}

Spreadsheet* spreadsheetCreate(int rows) {
    Spreadsheet* obj = (Spreadsheet*)malloc(sizeof(Spreadsheet));
    obj->rows = rows + 1;
    obj->grid = (int**)malloc(obj->rows * sizeof(int*));
    for (int i = 0; i < obj->rows; i++) {
        obj->grid[i] = (int*)calloc(COLUMNS, sizeof(int));
    }
    return obj;
}

void spreadsheetSetCell(Spreadsheet* obj, char* cell, int value) {
    int x, y;
    getPos(cell, &x, &y);
    obj->grid[x][y] = value;
}

void spreadsheetResetCell(Spreadsheet* obj, char* cell) {
    int x, y;
    getPos(cell, &x, &y);
    obj->grid[x][y] = 0;
}

int getCellVal(Spreadsheet* obj, const char* cell) {
    if (isalpha(cell[0])) {
        int x, y;
        getPos(cell, &x, &y);
        return obj->grid[x][y];
    } else {
        return atoi(cell);
    }
}

int spreadsheetGetValue(Spreadsheet* obj, char* formula) {
    char* plus = strchr(formula, '+');
    char* cell1 = (char*)malloc(plus - formula);
    strncpy(cell1, formula + 1, plus - formula - 1);
    cell1[plus - formula - 1] = '\0';
    char* cell2 = strdup(plus + 1);
    int val1 = getCellVal(obj, cell1);
    int val2 = getCellVal(obj, cell2);
    free(cell1);
    free(cell2);
    return val1 + val2;
}

void spreadsheetFree(Spreadsheet* obj) {
    for (int i = 0; i < obj->rows; i++) {
        free(obj->grid[i]);
    }
    free(obj->grid);
    free(obj);
}

###JavaScript

var Spreadsheet = function(rows) {
    this.grid = Array.from({length: rows + 1}, () => new Array(27).fill(0));
};

Spreadsheet.prototype.setCell = function(cell, value) {
    const [x, y] = this.getPos(cell);
    this.grid[x][y] = value;
};

Spreadsheet.prototype.resetCell = function(cell) {
    const [x, y] = this.getPos(cell);
    this.grid[x][y] = 0;
};

Spreadsheet.prototype.getValue = function(formula) {
    const i = formula.indexOf('+');
    const cell1 = formula.substring(1, i);
    const cell2 = formula.substring(i + 1);
    return this.getCellVal(cell1) + this.getCellVal(cell2);
};

Spreadsheet.prototype.getPos = function(cell) {
    const x = parseInt(cell.substring(1));
    const y = cell.charCodeAt(0) - 'A'.charCodeAt(0);
    return [x, y];
}

Spreadsheet.prototype.getCellVal = function(cell) {
    if (/[A-Z]/.test(cell[0])) {
        const [x, y] = this.getPos(cell);
        return this.grid[x][y];
    } else {
        return parseInt(cell);
    }
}

###TypeScript

class Spreadsheet {
    private grid: number[][];

    constructor(rows: number) {
        this.grid = Array.from({length: rows + 1}, () => new Array(27).fill(0));
    }

    setCell(cell: string, value: number): void {
        const [x, y] = this.getPos(cell);
        this.grid[x][y] = value;
    }

    resetCell(cell: string): void {
        const [x, y] = this.getPos(cell);
        this.grid[x][y] = 0;
    }

    getValue(formula: string): number {
        const i = formula.indexOf('+');
        const cell1 = formula.substring(1, i);
        const cell2 = formula.substring(i + 1);
        return this.getCellVal(cell1) + this.getCellVal(cell2);
    }

    private getPos(cell: string): [number, number] {
        const x = parseInt(cell.substring(1));
        const y = cell.charCodeAt(0) - 'A'.charCodeAt(0);
        return [x, y];
    }

    private getCellVal(cell: string): number {
        if (/[A-Z]/.test(cell[0])) {
            const [x, y] = this.getPos(cell);
            return this.grid[x][y];
        } else {
            return parseInt(cell);
        }
    }
}

###Rust

pub struct Spreadsheet {
    grid: Vec<Vec<i32>>,
}

impl Spreadsheet {
    pub fn new(rows: i32) -> Self {
        Spreadsheet {
            grid: vec![vec![0; 27]; (rows + 1) as usize],
        }
    }
    
    pub fn set_cell(&mut self, cell: String, value: i32) {
        let (x, y) = self.get_pos(&cell);
        self.grid[x][y] = value;
    }
    
    pub fn reset_cell(&mut self, cell: String) {
        let (x, y) = self.get_pos(&cell);
        self.grid[x][y] = 0;
    }
    
    pub fn get_value(&self, formula: String) -> i32 {
        let i = formula.find('+').unwrap();
        let cell1 = &formula[1..i];
        let cell2 = &formula[i+1..];
        self.get_cell_val(cell1) + self.get_cell_val(cell2)
    }

    fn get_pos(&self, cell: &str) -> (usize, usize) {
        let x = cell[1..].parse::<usize>().unwrap();
        let y = cell.chars().next().unwrap() as usize - 'A' as usize;
        (x, y)
    }

    fn get_cell_val(&self, cell: &str) -> i32 {
        if cell.chars().next().unwrap().is_ascii_alphabetic() {
            let (x, y) = self.get_pos(cell);
            self.grid[x][y]
        } else {
            cell.parse().unwrap()
        }
    }
}

复杂度分析

• 时间复杂度：初始化表格时对应的时间复杂度为 $O(C \times \textit{rows})$，其余操作对应的时间复杂度为 $O(1)$，其中 $\textit{rows}$ 表示给定的电子表格的行数，$C$ 表示给定的二维表格的列数，在本题中 $C = 26$。初始化时需要创建一个行数为 $\textit{rows}$，列数为 $26$ 的二维数组，此时需要的时间为 $O(C \times \textit{rows})$，其余操作仅涉及到解析字符串，并定位到单元格需要的时间为 $O(1)$。

• 空间复杂度：$O(C \times \textit{rows})$，其中 $\textit{rows}$ 表示给定的电子表格的行数，$C$ 表示给定的二维表格的列数，在本题中 $C = 26$。创建一个行数为 $\textit{rows}$，列数为 $26$ 的二维数组，需要的空间为 $O(C \times \textit{rows})$。

方法二：哈希表

思路与算法

根据题意可知，由于每个单元格的标识均不同，我们直接使用哈希表来保存单元格的值，此时更新和充值单元格时，直接更新哈希表即可，$\text{Spreadsheet}$ 类实现如下：

• 初始化：调用 $\text{Spreadsheet(int rows)}$：初始化单元格。此时直接初始化哈希表 $\textit{cellValues}$。

• $\text{void setCell(String cell, int value)}$：设置指定单元格的值为 $\textit{value}$，将哈希表中索引 $\textit{cell}$ 对应的元素值设置为 $\textit{value}$；

• $\text{void resetCell(String cell)}$：重置指定单元格的值为 $0$。从哈希表中删除索引为 $\textit{cell}$ 的元素；

• $\text{int getValue(String formula)}$：计算一个公式的值。根据题目为可知公式格式为："=X+Y"，从 $\textit{formula}$ 按照给定格式解析出 $\text{X}$ 与 $\text{Y}$。如果 $\text{X}$ 或 $\text{Y}$ 的首字母为字母，则其为单元格，此时从哈希表 $\textit{cellValues}$ 读取对应的值；如果其首字母为数字则将其转换为整数，分别求出 $\text{X}$ 与 $\text{Y}$ 对应的值，并返回二者相加的和即为答案。

代码

###C++

class Spreadsheet {
public:
    Spreadsheet(int) {}

    void setCell(string cell, int value) {
        cellValues[cell] = value;
    }

    void resetCell(string cell) {
        cellValues.erase(cell);
    }

    int getValue(string formula) {
        int i = formula.find('+');
        string cell1 = formula.substr(1, i - 1);
        string cell2 = formula.substr(i + 1);
        return (isalpha(cell1[0]) ? cellValues[cell1] : stoi(cell1)) +
               (isalpha(cell2[0]) ? cellValues[cell2] : stoi(cell2));
    }

private:
    unordered_map<string, int> cellValues;
};

###Java

public class Spreadsheet {
    private Map<String, Integer> cellValues = new HashMap<>();

    public Spreadsheet(int size) {

    }

    public void setCell(String cell, int value) {
        cellValues.put(cell, value);
    }

    public void resetCell(String cell) {
        cellValues.remove(cell);
    }

    public int getValue(String formula) {
        int i = formula.indexOf('+');
        String cell1 = formula.substring(1, i);
        String cell2 = formula.substring(i + 1);
        int val1 = Character.isLetter(cell1.charAt(0)) ? cellValues.getOrDefault(cell1, 0) : Integer.parseInt(cell1);
        int val2 = Character.isLetter(cell2.charAt(0)) ? cellValues.getOrDefault(cell2, 0) : Integer.parseInt(cell2);
        return val1 + val2;
    }
}

###C#

public class Spreadsheet {
    private Dictionary<string, int> cellValues = new Dictionary<string, int>();

    public Spreadsheet(int size) {}

    public void SetCell(string cell, int value) {
        cellValues[cell] = value;
    }

    public void ResetCell(string cell) {
        cellValues.Remove(cell);
    }

    public int GetValue(string formula) {
        int i = formula.IndexOf('+');
        string cell1 = formula.Substring(1, i - 1);
        string cell2 = formula.Substring(i + 1);
        int val1 = char.IsLetter(cell1[0]) ? cellValues.GetValueOrDefault(cell1) : int.Parse(cell1);
        int val2 = char.IsLetter(cell2[0]) ? cellValues.GetValueOrDefault(cell2) : int.Parse(cell2);
        return val1 + val2;
    }
}

###Go

type Spreadsheet struct {
    cellValues map[string]int
}

func Constructor(rows int) Spreadsheet {
    return Spreadsheet{
cellValues: make(map[string]int),
}
}

func (this *Spreadsheet) SetCell(cell string, value int)  {
    this.cellValues[cell] = value
}

func (this *Spreadsheet) ResetCell(cell string)  {
    delete(this.cellValues, cell)
}

func (this *Spreadsheet) GetValue(formula string) int {
    i := strings.Index(formula, "+")
cell1 := formula[1:i]
cell2 := formula[i + 1:]

var val1, val2 int
if unicode.IsLetter(rune(cell1[0])) {
val1 = this.cellValues[cell1]
} else {
val1, _ = strconv.Atoi(cell1)
}
if unicode.IsLetter(rune(cell2[0])) {
val2 = this.cellValues[cell2]
} else {
val2, _ = strconv.Atoi(cell2)
}

return val1 + val2
}

###Python

class Spreadsheet:

    def __init__(self, rows: int):
        self.cell_values = {}

    def setCell(self, cell: str, value: int) -> None:
        self.cell_values[cell] = value

    def resetCell(self, cell: str) -> None:
        if cell in self.cell_values:
            del self.cell_values[cell]

    def getValue(self, formula: str) -> int:
        i = formula.find('+')
        cell1 = formula[1:i]
        cell2 = formula[i + 1:]
        val1 = self.cell_values.get(cell1, 0) if cell1[0].isalpha() else int(cell1)
        val2 = self.cell_values.get(cell2, 0) if cell2[0].isalpha() else int(cell2)
        return val1 + val2

###C

typedef struct {
    char *key;
    int val;
    UT_hash_handle hh;
} HashItem; 

HashItem *hashFindItem(HashItem **obj, const char *key) {
    HashItem *pEntry = NULL;
    HASH_FIND_STR(*obj, key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, char *key, int val) {
    if (hashFindItem(obj, key)) {
        return false;
    }
    HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
    pEntry->key = strdup(key);
    pEntry->val = val;
    HASH_ADD_STR(*obj, key, pEntry);
    return true;
}

bool hashSetItem(HashItem **obj, char *key, int val) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        hashAddItem(obj, key, val);
    } else {
        pEntry->val = val;
    }
    return true;
}

int hashGetItem(HashItem **obj, const char *key, int defaultVal) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        return defaultVal;
    }
    return pEntry->val;
}

bool hashErase(HashItem **obj, char *key) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        return false;
    }
    HASH_DEL(*obj, pEntry);
    free(pEntry->key);
    free(pEntry);
    return true;
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);  
        free(curr->key);
        free(curr);             
    }
}

typedef struct {
    HashItem *cellValues;
} Spreadsheet;


Spreadsheet* spreadsheetCreate(int rows) {
    Spreadsheet *obj = (Spreadsheet *)malloc(sizeof(Spreadsheet));
    obj->cellValues = NULL;
    return obj;
}

void spreadsheetSetCell(Spreadsheet* obj, char* cell, int value) {
    hashSetItem(&obj->cellValues, cell, value);
}

void spreadsheetResetCell(Spreadsheet* obj, char* cell) {
    hashErase(&obj->cellValues, cell);
}

int getCellVal(Spreadsheet* obj, const char* cell) {
    if (isalpha(cell[0])) {
        return hashGetItem(&obj->cellValues, cell, 0);
    } else {
        return atoi(cell);
    }
}

int spreadsheetGetValue(Spreadsheet* obj, char* formula) {
    char* plus = strchr(formula, '+');
    char* cell1 = (char*)malloc(plus - formula);
    strncpy(cell1, formula + 1, plus - formula - 1);
    cell1[plus - formula - 1] = '\0';
    char* cell2 = strdup(plus + 1);
    int val1 = getCellVal(obj, cell1);
    int val2 = getCellVal(obj, cell2);
    free(cell1);
    free(cell2);
    return val1 + val2;
}

void spreadsheetFree(Spreadsheet* obj) {
    hashFree(&obj->cellValues);
    free(obj);
}

###JavaScript

var Spreadsheet = function(rows) {
    this.cellValues = {};
};

Spreadsheet.prototype.setCell = function(cell, value) {
    this.cellValues[cell] = value;
};

Spreadsheet.prototype.resetCell = function(cell) {
    delete this.cellValues[cell];
};

Spreadsheet.prototype.getValue = function(formula) {
    const i = formula.indexOf('+');
    const cell1 = formula.substring(1, i);
    const cell2 = formula.substring(i + 1);
    const val1 = /[a-z]/i.test(cell1[0]) ? (this.cellValues[cell1] || 0) : parseInt(cell1);
    const val2 = /[a-z]/i.test(cell2[0]) ? (this.cellValues[cell2] || 0) : parseInt(cell2);
    return val1 + val2;
};

###TypeScript

class Spreadsheet {
    private cellValues: {[key: string]: number} = {};

    constructor(size: number) {}

    setCell(cell: string, value: number): void {
        this.cellValues[cell] = value;
    }

    resetCell(cell: string): void {
        delete this.cellValues[cell];
    }

    getValue(formula: string): number {
        const i = formula.indexOf('+');
        const cell1 = formula.substring(1, i);
        const cell2 = formula.substring(i + 1);
        const val1 = /[a-z]/i.test(cell1[0]) ? (this.cellValues[cell1] || 0) : parseInt(cell1);
        const val2 = /[a-z]/i.test(cell2[0]) ? (this.cellValues[cell2] || 0) : parseInt(cell2);
        return val1 + val2;
    }
}

###Rust

use std::collections::HashMap;

struct Spreadsheet {
    cell_values: HashMap<String, i32>,
}

impl Spreadsheet {
    fn new(rows: i32) -> Self {
        Spreadsheet {
            cell_values: HashMap::new(),
        }
    }
    
    fn set_cell(&mut self, cell: String, value: i32) {
        self.cell_values.insert(cell, value);
    }
    
    fn reset_cell(&mut self, cell: String) {
        self.cell_values.remove(&cell);
    }
    
    fn get_value(&self, formula: String) -> i32 {
        let i = formula.find('+').expect("Formula must contain '+'");
        let (cell1, cell2) = formula.split_at(i);
        let cell1 = cell1[1..].to_string();
        let cell2 = cell2[1..].to_string();
        
        let val1 = if cell1.chars().next().unwrap().is_alphabetic() {
            *self.cell_values.get(&cell1).unwrap_or(&0)
        } else {
            cell1.parse().unwrap_or(0)
        };
        let val2 = if cell2.chars().next().unwrap().is_alphabetic() {
            *self.cell_values.get(&cell2).unwrap_or(&0)
        } else {
            cell2.parse().unwrap_or(0)
        };
        
        val1 + val2
    }
}

复杂度分析

• 时间复杂度：所有操作的时间复杂度为 $O(1)$。每次操作时仅需查询和更新哈希表即可，其余操作仅涉及到解析字符串，需要的时间为 $O(1)$。

• 空间复杂度：$O(\textit{cellsCount})$，其中 $\textit{cellsCount}$ 表示电子表格中的非 $0$ 元素个数，取决于方法 $\textit{setCell}$ 的调用次数。哈希表中最多有 $O(\textit{cellsCount})$ 个元素。