【算法】算法题-20231205

一、LCS 01. 下载插件

简单
小扣打算给自己的 VS code 安装使用插件，初始状态下带宽每分钟可以完成 1 个插件的下载。假定每分钟选择以下两种策略之一:
使用当前带宽下载插件
将带宽加倍（下载插件数量随之加倍）
请返回小扣完成下载 n 个插件最少需要多少分钟。
注意：实际的下载的插件数量可以超过 n 个

示例 1：
输入：n = 2
输出：2
解释： 以下两个方案，都能实现 2 分钟内下载 2 个插件
方案一：第一分钟带宽加倍，带宽可每分钟下载 2 个插件；第二分钟下载 2 个插件
方案二：第一分钟下载 1 个插件，第二分钟下载 1 个插件

示例 2：
输入：n = 4
输出：3
解释： 最少需要 3 分钟可完成 4 个插件的下载，以下是其中一种方案: 第一分钟带宽加倍，带宽可每分钟下载 2 个插件; 第二分钟下载 2 个插件; 第三分钟下载 2 个插件。

解题思路
逻辑似乎是这样的：如果你下载两分钟，那么肯定加倍+1分钟下载完。 如果你下载4分钟，那么肯定两次加倍+1分钟下载完。 所以，加倍永远是最优解。 所以，加倍

class Solution:
    def leastMinutes(self, n: int) -> int:
        time_count = 0
        width = 1
        while n > width:
            width = width * 2
            time_count = time_count + 1
        time_count = time_count + 1
        return time_count

二、已知一个由数字组成的列表，请将列表中的所有0移到右侧

已知一个由数字组成的列表，请将列表中的所有0移到右侧。
例如 move_zeros([1, 0, 1, 2, 0, 1, 3]) ，预期返回结果： [1, 1, 2, 1, 3, 0, 0]

def test(nums):
    fast = 0
    slow = 0
    while fast < len(nums):
        if nums[fast]:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1
        fast += 1
    return nums


nums = [1, 0, 1, 2, 0, 1, 3]
print(test(nums))

三、实现一个trim()函数，去除字符串首尾的空格（不能使用strip()方法）

题目：实现一个trim()函数，去除字符串首尾的空格（不能使用strip()方法）
例：
1.字符串为空的情况，输入trim(’ ‘) 预期返回结果 ‘’
2.字符串首尾空格数大于1的情况，输入trim(’ a bc ') 预期返回结果 ‘a bc’

def trim(super):
    a = 0
    b = 0
    for i in range(len(super)):
        if super[i] == ' ':
            a += 1
        else:
            break
    for i in range(len(super)):
        if super[-(i + 1)] == ' ':
            b += 1
        else:
            break
    print(super[a:-b])


trim('        23 2    1231  123  ')