leetcode刷题之暴力求解

leetcode刷题,使用python

1, 加油站 —— 0134 暴力求解 没通过

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

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

from typing import List

# 暴力求解  不通过
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        j = 0
        remain = 0

        # 总油量 < 总耗油量，一定无解
        if sum(gas) < sum(cost):
            return -1

        for i in range(n):
            j = i
            remain = gas[i]
            # 判断当前剩余的油能否到达下一个点
            while(remain-cost[j]>=0):
                # 减去花费的加上新的点的补给
                remain = remain - cost[j] + gas[(j+1)%n]
                j = (j+1) % n
                # j 回到了 i 即绕了一圈
                if j == i:
                    return i

        # 任何点都不可以
        return -1

S = Solution()
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

print(S.canCompleteCircuit(gas, cost))

2, 整数替换 —— 0397 遍历所有情况
给定一个正整数 n ，你可以做如下操作：
如果 n 是偶数，则用 n / 2替换 n 。
如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
返回 n 变为 1 所需的 最小替换次数 。

示例 1：
输入：n = 8
输出：3
解释：8 -> 4 -> 2 -> 1

class Solution:
    def integerReplacement(self, n: int) -> int:
        if n == 1:
            return 0

        if n % 2 == 0:
            return 1 + self.integerReplacement(n//2)

        return 2 +  min(self.integerReplacement(n//2), self.integerReplacement(n//2 + 1))


S = Solution()
n = 8
print(S.integerReplacement(n))