代码收藏家技术教程 2024-10-27

字节青训营 X 豆包MarsCode 技术训练营 2024 入营考核

更新

2024年10.23更新了java和python的提交后发现有的题目名称和最开始的有些不一样了

简单题

兔生兔兔群繁殖之谜

题目描述

# 问题描述
- 如果一对兔子每月生一对兔子；一对新生兔，从第二个月起就开始生兔子；假定每对兔子都是一雌一雄，试问一对兔子，第 `n` 个月能繁殖成多少对兔子？（举例，第1个月是1对兔子，第2个月是2对兔子）

## 输入格式
- 数字

## 输出格式
- 数字

## 输入样例
- 5

## 输出样例
- 8

## 数据范围
- `[1, 75]`

## 测试数据集
  - 样例1
    - 输入：`5`
    - 输出：`8`
  - 样例2
    - 输入：`1`
    - 输出：`1`
  - 样例3
    - 输入：`15`
    - 输出：`987`
  - 样例4
    - 输入：`50`
    - 输出：`20365011074`

方法

斐波拉切数列用递归的话记得写记忆化搜索保证时间复杂度

vis = [False for _ in range(76)]
F = [0 for _ in range(76)]
def calc_fbi(x):
    if vis[x] == True:
        return F[x]
    if x==1 or x==0 :
        return 1
    vis[x] = True
    F[x] = calc_fbi(x-1) + calc_fbi(x-2)
    return F[x]
def solution(A):
    # Edit your code here
    return calc_fbi(A)


if __name__ == "__main__":
    # Add your test cases here
    print(solution(5) == 8)
    print(solution(1) == 1)
    print(solution(15) == 987)
    print(solution(50) == 20365011074)

找单独的数

题目描述

# 问题描述
有一堆数字，除了一个数字，其它的数字都是成对出现。班上的每个同学拿一个数字，正好将这些数字全部拿完，问如何快速找到拿了单独数字的同学？

## 输入格式
- 空格分隔输入所有的数字

## 输出格式
- 单独的那个数字

## 输入样例(1)
```
1 1 2 2 3 3 4 5 5
```
## 输出样例(1)
4

## 输入样例(2)
```
0 1 0 1 2
```
## 输出样例(2)
2

方法

经典的异或

def solution(inp):
    # Edit your code here
    res = 0
    for x in inp:
        res = res ^ x
    return res


if __name__ == "__main__":
    # Add your test cases here

    print(solution([1, 1, 2, 2, 3, 3, 4, 5, 5]) == 4)
    print(solution([0, 1, 0, 1, 2]) == 2)

打点计数器的区间合并

问题描述

小明正在设计一台打点计数器，该计数器可以接受多个递增的数字范围，并对这些范围内的每个唯一数字打点。如果多个范围之间有重叠，计数器将合并这些范围并只对每个唯一数字打一次点。小明需要你帮助他计算，在给定的多组数字范围内，计数器会打多少个点。

例如，给定三个数字范围 [1, 4], [7, 10], 和 [3, 5]，计数器首先将这些范围合并，变成 [1, 5] 和 [7, 10]，然后计算这两个范围内共有多少个唯一数字，即从 1 到 5 有 5 个数字，从 7 到 10 有 4 个数字，共打 9 个点。

测试样例

样例1：

输入：inputArray = [[1, 4], [7, 10], [3, 5]]
输出：7

样例2：

输入：inputArray = [[1, 2], [6, 10], [11, 15]]
输出：9

样例3：

输入：inputArray = [[1, 3], [2, 6], [8, 10]]
输出：7

注意这里其实有个问题不知道题目是不是直接用ai生成的这里的区间应该是不包含一端的端点才对

方法

直接将区间按照左端点为第一关键字从小到大，右端点第一二键字从大到小排序，然后记录处理的区间和当前的区间求 ∪。

def solution(inputArray):
    # 使用 sorted 函数和 lambda 表达式进行排序
    sorted_array = sorted(inputArray, key=lambda x: (x[0], -x[1]))
    # 返回排序后的结果
    lenth = len(sorted_array)
    L, R = sorted_array[0][0], sorted_array[0][1]
    sum = R-L
    for i in range(1, lenth):
        l, r = sorted_array[i][0], sorted_array[i][1]
        if r <= R:
            continue
        if l >= R:
            sum += r - l
            L, R = l, r
        else :
            sum += r - R
            R = r
            
    # print(sum)
    return sum
    

if __name__ == "__main__":
    # 测试用例
    testArray1 = [[1, 4], [7, 10], [3, 5]]
    testArray2 = [[1, 2], [6, 10], [11, 15]]
    print(solution(testArray1) == 7 )
    print(solution(testArray2) == 9 )

判断数组是否单调

问题描述

小S最近在研究一些数组的性质，她发现有一种非常有趣的数组被称为 单调数组。如果一个数组是单调递增或单调递减的，那么它就是单调的。

当对于所有索引i <= j时，nums[i] <= nums[j]，数组nums是单调递增的。

当对于所有索引i <= j时，nums[i] >= nums[j]，数组nums是单调递减的。

你需要编写一个程序来判断给定的数组nums是否为单调数组。如果是，返回true，否则返回false。

测试样例

样例1：

输入：nums = [1, 2, 2, 3]
输出：True

样例2：

输入：nums = [6, 5, 4, 4]
输出：True

样例3：

输入：nums = [1, 3, 2, 4, 5]
输出：False

方法

反着想直接找到不上升或者不下降的时候打标记即可

def solution(nums: list) -> int:
    increasing = decreasing = True
    
    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            decreasing = False
        elif nums[i] < nums[i - 1]:
            increasing = False
            
    return 1 if increasing or decreasing else 0

if __name__ == '__main__':
    print(solution(nums=[1, 2, 2, 3]) == 1)
    print(solution(nums=[6, 5, 4, 4]) == 1)
    print(solution(nums=[1, 3, 2, 4, 5]) == 0)

找出整型数组中占比超过一半的数

问题描述

小R从班级中抽取了一些同学，每位同学都会给出一个数字。已知在这些数字中，某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。

测试样例

样例1：

输入：array = [1, 3, 8, 2, 3, 1, 3, 3, 3]
输出：3

样例2：

输入：array = [5, 5, 5, 1, 2, 5, 5]
输出：5

样例3：

输入：array = [9, 9, 9, 9, 8, 9, 8, 8]
输出：9

方法

排个序然后看一下这个数是不是和上个数相同，相同的话就将计数器加一如果超过了数组的一半就返回这个数

def solution(array):
    # Sort the array
    array.sort()
    
    # Initialize variables
    count = 1
    majority_count = len(array) // 2
    
    # Iterate through the sorted array
    for i in range(1, len(array)):
        if array[i] == array[i - 1]:
            count += 1
        else:
            count = 1  # Reset count for a new number
        
        # Check if the count exceeds half the length of the array
        if count > majority_count:
            return array[i]
    
    return 0  # Return 0 if no majority element is found

if __name__ == "__main__":
    # Add your test cases here
    print(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3)  # Should return True

版本号比较

问题描述

在某个项目中，每个版本都用版本号标记，由一个或多个修订号组成，修订号之间由点号.分隔。每个修订号可能有多位数字，并且可能会包含前导零。你需要根据两个版本号 version1 和 version2，判断哪个版本更新，或者它们是否相同。

例如，2.5.33 和 0.1 都是有效的版本号。

当比较两个版本时，从左到右依次比较它们的修订号。忽略每个修订号的前导零，直接比较修订号对应的整数值。如果其中一个版本没有足够的修订号，缺失部分默认补为0。

你需要根据以下规则返回比较结果：

如果 version1 > version2，返回 1。

如果 version1 < version2，返回 -1。

如果两个版本相等，返回 0。

测试样例

样例1：

输入：version1 = "0.1" , version2 = "1.1"
输出：-1

样例2：

输入：version1 = "1.0.1" , version2 = "1"
输出：1

样例3：

输入：version1 = "7.5.2.4" , version2 = "7.5.3"
输出：-1

样例4：

输入：version1 = "1.0" , version2 = "1.0.0"
输出：0

方法

把两个版本里按照 . 把所有的整数提取先比较两个共同的长度然后看另一个是否大于0

def solution(version1, version2): 
    # 将版本号按点分隔并转换为整数列表
    v1_parts = list(map(int, version1.split('.')))
    v2_parts = list(map(int, version2.split('.')))
    
    # 比较修订号，直到最短的版本号结束
    for v1, v2 in zip(v1_parts, v2_parts):
        if v1 > v2:
            return 1
        elif v1 < v2:
            return -1
    
    # 如果一个版本号比另一个长，比较剩下的部分（缺失部分默认为0）
    if len(v1_parts) > len(v2_parts):
        for v in v1_parts[len(v2_parts):]:
            if v > 0:
                return 1
    elif len(v2_parts) > len(v1_parts):
        for v in v2_parts[len(v1_parts):]:
            if v > 0:
                return -1
    
    return 0

if __name__ == "__main__":
    # 测试用例
    print(solution("0.1", "1.1") == -1)
    print(solution("1.0.1", "1") == 1)
    print(solution("7.5.2.4", "7.5.3") == -1)
    print(solution("1.0", "1.0.0") == 0)

比赛配对问题

问题描述

小R正在组织一个比赛，比赛中有 n 支队伍参赛。比赛遵循以下独特的赛制：

如果当前队伍数为偶数，那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛，且产生 n / 2 支队伍进入下一轮。

如果当前队伍数为奇数，那么将会随机轮空并晋级一支队伍，其余的队伍配对。总共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。

小R想知道在比赛中进行的配对次数，直到决出唯一的获胜队伍为止。

测试样例

样例1：

输入：n = 7
输出：6

样例2：

输入：n = 14
输出：13

样例3：

输入：n = 1
输出：0

方法

模拟题每次除2 下一轮加上这一轮的这个余数同时记录每次除2的和即可

def solution(n: int) -> int:
    match_count = 0  # 记录配对次数
    while n > 1:  # 只要队伍数大于1
        if n % 2 == 0:  # 当前队伍数为偶数
            match_count += n // 2  # 进行 n / 2 场比赛
            n //= 2  # 进入下一轮的队伍数
        else:  # 当前队伍数为奇数
            match_count += (n - 1) // 2  # 进行 (n - 1) / 2 场比赛
            n = (n - 1) // 2 + 1  # 进入下一轮的队伍数
    return match_count

if __name__ == '__main__':
    print(solution(7) == 6)
    print(solution(14) == 13)
    print(solution(1) == 0)

找出最长的神奇数列

问题描述

小F是一个好学的中学生，今天他学习了数列的概念。他在纸上写下了一个由 0 和 1 组成的正整数序列，长度为 n。这个序列中的 1 和 0 交替出现，且至少由 3 个连续的 0 和 1 组成的部分数列称为「神奇数列」。例如，10101 是一个神奇数列，而 1011 不是。现在，小F想知道在这个序列中，最长的「神奇数列」是哪一个。你能帮他找到吗？

如果有多个神奇数列，那么输出最先出现的一个。

测试样例

样例1：

输入：inp = "0101011101"
输出：'010101'

样例2：

输入：inp = "1110101010000"
输出：'10101010'

样例3：

输入：inp = "1010101010101010"
输出：'1010101010101010'

方法

模拟题直接便利找连续的01或者10 注意如果断掉了就从断了的地方重新记录而不是上一次开始的下一位

def solution(inp):
    n = len(inp)
    longest_magic = ""
    
    # Iterate through the string to find alternating patterns
    i = 0
    while i < n:
        # Find the start of a possible magic sequence
        start = i
        
        # Move to the next character while alternating
        while i + 1 < n and inp[i] != inp[i + 1]:
            i += 1
        
        # Length of the current alternating sequence
        length = i - start + 1
        
        # Check if it is a magic sequence (length >= 3)
        if length >= 3:
            current_magic = inp[start:i + 1]
            if len(current_magic) > len(longest_magic):
                longest_magic = current_magic
        
        # Move to the next character
        i += 1

    return longest_magic if longest_magic else ""

if __name__ == "__main__":
    # Test cases
    print(solution("0101011101") == "010101")  # Expected output: True
    print(solution("00110011") == "")          # Expected output: True
    print(solution("111000111") == "")         # Expected output: True
    print(solution("1010101010") == "1010101010")   # Expected output: True
    print(solution("1100") == "")

充电总时间计算

问题描述

小R有nn部电脑，每部电脑的电池容量分别为aiai。她可以使用两种不同的充电方式来给电脑充电：

普通充电：每单位时间为电脑充电xx单位的电量。
闪充：每单位时间为电脑充电4x4x单位的电量。

现在，所有电脑的电量都为零。小R希望使用闪充给所有电脑充满电，计算她需要的总充电时间。请保留结果的小数点后两位。

测试样例

样例1：

输入：n = 4 ,x = 1 ,a = [2, 3, 4, 5]
输出：'3.50'

样例2：

输入：n = 3 ,x = 2 ,a = [4, 6, 8]
输出：'2.25'

样例3：

输入：n = 2 ,x = 1 ,a = [10, 5]
输出：'3.75'

方法

不知道这道题是不是在考高精度直接把a相加后除 2x 然后转字符串

def solution(n: int, x: int, a: list) -> str:
    tot = sum(a)
    res  = tot / (4*x)

    return "{:.2f}".format(res)

if __name__ == '__main__':
    print(solution(4, 1, [2, 3, 4, 5]) == '3.50')
    print(solution(3, 2, [4, 6, 8]) == '2.25')
    print(solution(2, 1, [10, 5]) == '3.75')

最大乘积区间问题

问题描述

小R手上有一个长度为 n 的数组 (n > 0)，数组中的元素分别来自集合 [0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]。小R想从这个数组中选取一段连续的区间，得到可能的最大乘积。

你需要帮助小R找到最大乘积的区间，并输出这个区间的起始位置 x 和结束位置 y (x ≤ y)。如果存在多个区间乘积相同的情况，优先选择 x 更小的区间；如果 x 相同，选择 y 更小的区间。

注意：数组的起始位置为 1，结束位置为 n。

测试样例

样例1：

输入：n = 5, arr = [1, 2, 4, 0, 8]
输出：[1, 3]

样例2：

输入：n = 7, arr = [1, 2, 4, 8, 0, 256, 0]
输出：[6, 6]

样例3：

输入：n = 8, arr = [1, 2, 4, 8, 0, 256, 512, 0]
输出：[6, 7]

方法

模拟题

只要不是0就肯定变大或者不变然后有一的情况注意如果存在多个区间乘积相同的情况，优先选择 x 更小的区间；如果 x 相同，选择 y 更小的区间。

def solution(n, data):
    max_prod = -float('inf')  # 存储全局最大乘积
    cur_prod = 1  # 当前区间的乘积
    start = 0  # 当前区间的起始位置
    result = [1, 1]  # 存储最终结果

    for i in range(n):
        if data[i] == 0:  # 遇到 0 时，重置乘积并更新起始位置
            cur_prod = 1
            start = i + 1  # 更新下一个区间的起点
            continue
        
        cur_prod *= data[i]  # 计算当前区间的乘积

        # 更新全局最大乘积及其区间
        if cur_prod > max_prod:
            max_prod = cur_prod
            result = [start + 1, i + 1]  # 起始位置和结束位置从 1 开始计算
        elif cur_prod == max_prod:
            # 如果乘积相等，选择起点更小的区间；如果起点相同，选择终点更小的区间
            if start + 1 < result[0] or (start + 1 == result[0] and i + 1 < result[1]):
                result = [start + 1, i + 1]

    return result

if __name__ == "__main__":
    # 测试用例
    print(solution(5, [1, 2, 4, 0, 8]) == [1, 3])
    print(solution(7, [1, 2, 4, 8, 0, 256, 0]) == [6, 6])

中等题

及格的组合方式探索

问题描述

小S在学校选择了3门必修课和n门选修课程来响应全面发展的教育政策。现在期末考核即将到来，小S想知道他所有课程的成绩有多少种组合方式能使他及格。及格的条件是所有课程的平均分不低于60分。每门课程的成绩是由20道选择题决定，每题5分，答对得分，答错不得分。为了计算方便，你需要将结果对202220222022取模。

测试样例

样例1：

输入：n = 3
输出：'19195617'

样例2：

输入：n = 6
输出：'135464411082'

样例3：

输入：n = 49
输出：'174899025576'

样例4：

输入：n = 201
输出：'34269227409'

样例5：

输入：n = 888
输出：'194187156114'

方法

题目要求是成绩有多少种不同的情况所以只需要就不需要知道得到同样的成绩是作对了哪些题了

直接
然后依次枚举每一门课作对的道数只要总道数大于等于 12 * （3+n)就加入答案中

MOD = 202220222022

def solution(n):
    n += 3  
    old_dp = [1] + [0] * 20  # 动态规划优化空间，2个一维dp即可
    for i in range(1, n + 1):
        MaxScore = 20 * i
        new_dp = [0] * (MaxScore + 1)
        for j in range(0, MaxScore + 1):
            for k in range(0, 21):
                if j - k <= (i - 1) * 20 and j - k >= 0:
                    if old_dp[j - k] > 0:
                        new_dp[j] = (new_dp[j] + old_dp[j - k]) % MOD
                elif j - k < 0:
                    break
        old_dp = new_dp[:]

    ans = 0
    for i in range(12 * n, 20 * n + 1):
        ans = (new_dp[i] + ans) % MOD
    # print(ans)
    return str(ans)
if __name__ == "__main__":
    #  You can add more test cases here
    print(solution(3) == "19195617" )
    print(solution(6) == "135464411082" )
    print(solution(49) == "174899025576" )
    print(solution(201) == "34269227409" )
    print(solution(888) == "194187156114" )

不得不说python是真的慢啊

和的逆运算问题

问题描述

n 个整数两两相加可以得到 n(n - 1) / 2 个和。我们的目标是：根据这些和找出原来的 n 个整数。

按非降序排序返回这 n 个数，如果无解，输出 "Impossible"。

测试样例

样例1：

输入：n = 3, sums = [1269, 1160, 1663]
输出："383 777 886"

样例2：

输入：n = 3, sums = [1, 1, 1]
输出："Impossible"

样例3：

输入：n = 5, sums = [226, 223, 225, 224, 227, 229, 228, 226, 225, 227]
输出："111 112 113 114 115"

样例4：

输入：n = 5, sums = [-1, 0, -1, -2, 1, 0, -1, 1, 0, -1]
输出："-1 -1 0 0 1"

样例5：

输入：n = 5, sums = [79950, 79936, 79942, 79962, 79954, 79972, 79960, 79968, 79924, 79932]
输出："39953 39971 39979 39983 39989"

方法

首先sums是 n(n – 1) / 2个数sum1…sumn(n – 1) / 2 他是n个整数相加我们把n个整数设为n个未知数x1.. xn

就有x1 + x2 = sum1;x1+ x3 = sum2

sum1 + sum2+… sum n-1 = （n-1）x1 + （x2 + x3 + … xn)

sum n + … + sum n(n – 1) / 2 = (n-2) (x2 + x3 + xn-1)

就可以算出 x1 然后递归算x2 到x n-1

必须要注意的一点就是这里的sum1 顺序并不是按照从小到大的所以需要枚举所有的sum顺序

这个方法必须n很小才行不知道有没有其他的快速的方法

import itertools

def solution(n, sums):

    # 枚举 sums 的所有排列
    for perm in itertools.permutations(sums):
        # 利用 sums 中前面3个值推导出 x1
        # perm[0] 是 x1 + x2, perm[1] 是 x1 + x3, perm[n-1] 是 x2 + x3
        x1 = (perm[0] + perm[1] - perm[n-1]) // 2

        # 利用 x1 来推导其他的 xi
        x = [x1]
        for i in range(n-1):
            xi = perm[i] - x1
            x.append(xi)

        # 验证 xi 和 xj 是否满足所有 sums 条件
        index = 0
        valid = True
        for i in range(n):
            for j in range(i+1, n):
                if x[i] + x[j] != perm[index]:
                    valid = False
                    break
                index += 1
            if not valid:
                break

        # 如果验证通过，返回结果
        if valid:
            return " ".join(map(str, sorted(x)))

    # 如果所有排列都不满足，返回 "Impossible"
    return "Impossible"

# 测试用例
if __name__ == "__main__":
    print(solution(3, [1269, 1160, 1663]) == "383 777 886")
    print(solution(3, [1, 1, 1]) == "Impossible")
    print(solution(5, [226, 223, 225, 224, 227, 229, 228, 226, 225, 227]) == "111 112 113 114 115")
    print(solution(5, [-1, 0, -1, -2, 1, 0, -1, 1, 0, -1]) == "-1 -1 0 0 1")
    print(solution(5, [79950, 79936, 79942, 79962, 79954, 79972, 79960, 79968, 79924, 79932]) == "39953 39971 39979 39983 39989")

数字翻译成字符串的可能性

题目

最开始的时候题目有范围的 num是2^31之内的

数字翻译成字符串的可能性
问题描述
小M获得了一个任务，需要将数字翻译成字符串。翻译规则是：0对应"a"，1对应"b"，依此类推直到25对应"z"。一个数字可能有多种翻译方法。小M需要一个程序来计算一个数字有多少种不同的翻译方法。

例如：数字12258可以翻译成 "bccfi", "bwfi", "bczi", "mcfi" 和 "mzi"，共5种方式。

测试样例
样例1：

输入：num = 12258
输出：5

样例2：

输入：num = 1400112
输出：6

样例3：

输入：num = 2110101
输出：10

样例4：

输入：num = 25
输出：2

样例5：

输入：num = 1023
输出：4

方法

动态规划

F[i] 表示前i位的所有翻译可能由于是只有0-25可以翻译那么

F[i] = F[i-1] + F[i-2] 当 i-1和i-2两位数拼起来大于10且小于25的

python不熟写的c++让gpt改成py

这里的数据转换和num_str[i – 2:i]是真方便

F = [0 for _ in range(35)]

def solution(num):
    num_str = str(num)
    length = len(num_str)
    
    # 初始化 F 数组
    F[0] = 1  # 空字符串的情况
    F[1] = 1  # 只有一位的情况
    
    for i in range(2, length + 1):
        F[i] = F[i - 1]  # 处理单个字符
        
        # 检查两个字符的组合
        if 10 <= int(num_str[i - 2:i]) <= 25:
            F[i] += F[i - 2]  # 处理两个字符的组合
    
    return F[length]

if __name__ == "__main__":
    print(solution(12258) == 5)
    print(solution(1400112) == 6)
    print(solution(2110101) == 10)

快乐时间最大化

问题描述

小C喜欢在电子书城阅读书籍，并希望获得尽可能多的满足感。每本书的满意程度books[i]表示小C阅读这本书的评分。如果按照顺序阅读书籍，time[i]定义为阅读第i本书及之前所有书所花费的时间，即第i本书的快乐时间系数为time[i] * books[i]。小C可以按照任意顺序调整书籍的阅读顺序，以获得最大的【快乐时间】总和。

例如，给定的书籍评分是 [4, 3, 2]，如果按评分升序排序来安排阅读，则小C可以获得最大的快乐时间系数。

测试样例

样例1：

输入：books = [4, 3, 2]
输出：20

样例2：

输入：books = [-1, -4, -5]
输出：0

样例3：

输入：books = [-1, -8, 0, 5, -9]
输出：14

方法

还不知道这个time是怎么来的

P整数生成问题

问题描述

小S正在玩一个数字游戏，游戏中要求生成所有小于或等于 m 的 P整数。一个整数如果可以表示为 x^i + y^j，其中 i >= 0 且 j >= 0，我们称之为强整数。请帮小S找到所有满足条件的强整数，并将结果从小到大返回，每个值最多出现一次。

测试样例

样例1：

输入：x = 2 ,y = 3 ,m = 10
输出：[2, 3, 4, 5, 7, 9, 10]

样例2：

输入：x = 3 ,y = 5 ,m = 15
输出：[2, 4, 6, 8, 10, 14]

样例3：

输入：x = 2 ,y = 1 ,m = 20
输出：[2, 3, 5, 9, 17]

方法

直接枚举i,j即可但是注意x,y为1的情况

def solution(x: int, y: int, m: int) -> list:
    strong_integers = set()
    
    # 计算 x 的所有幂次
    i = 0
    while (x**i) <= m:
        # 计算 y 的所有幂次
        j = 0
        while (x**i + y**j) <= m:
            strong_integers.add(x**i + y**j)
            j += 1
            if y == 1:  # 防止 y=1 的死循环
                break
        i += 1
        if x == 1:  # 只需计算一次，因为 1 的幂总是 1
            break

    return sorted(strong_integers)

if __name__ == '__main__':
    print(solution(x=2, y=3, m=10) == [2, 3, 4, 5, 7, 9, 10])
    print(solution(x=3, y=5, m=15) == [2, 4, 6, 8, 10, 14])
    print(solution(x=2, y=1, m=20) == [2, 3, 5, 9, 17])
    print(solution(x=1, y=1, m=10) == [2])  # 示例测试

最大乘积问题

问题描述

小R最近遇到了一个数组问题。他有一个包含 NN 个元素的数组，记作 a1,a2,…,aNa1,a2,…,aN。为了分析这个数组的特性，小R定义了两个函数 L(i)L(i) 和 R(i)R(i)，并希望通过这两个函数来找到一些有趣的结论。

L(i)L(i) 是满足以下条件的最大的 jj 值：

j<ij<i

a[j]>a[i]a[j]>a[i]

如果找不到这样的 jj，那么 L(i)=0L(i)=0；如果有多个满足条件的 jj，选择离 ii 最近的那个。

R(i)R(i) 是满足以下条件的最小的 kk 值：

k>ik>i

a[k]>a[i]a[k]>a[i]

如果找不到这样的 kk，那么 R(i)=0R(i)=0；如果有多个满足条件的 kk，选择离 ii 最近的那个。

最终，小R定义 MAX(i)=L(i)∗R(i)MAX(i)=L(i)∗R(i)，他想知道在 1≤i≤N1≤i≤N 的范围内，MAX(i)MAX(i) 的最大值是多少。

测试样例

样例1：

输入：n = 5, array = [5, 4, 3, 4, 5]
输出：8

样例2：

输入：n = 6, array = [2, 1, 4, 3, 6, 5]
输出：15

样例3：

输入：n = 7, array = [1, 2, 3, 4, 5, 6, 7]
输出：0

方法

就是找到这个数左边右两边大于他的最近的位置相乘

直接用单调栈来o(n)找到左边大于他的和右边大于他的第一数的位置

石子移动问题

问题描述

小S正在玩一个关于石子的游戏，给定了一些石子，它们位于一维数轴的不同位置，位置用数组 stones 表示。如果某个石子处于最小或最大的一个位置，我们称其为端点石子。

在每个回合，小S可以将一颗端点石子移动到一个未占用的位置，使其不再是端点石子。游戏继续，直到石子的位置变得连续，无法再进行任何移动操作。

你需要帮助小S找到可以移动的最大次数。

测试样例

样例1：

输入：stones = [7, 4, 9]
输出：2

样例2：

输入：stones = [6, 5, 4, 3, 10]
输出：3

样例3：

输入：stones = [1, 2, 3, 4, 5]
输出：0

方法

这个题难度绝对不应该弄成中等是1040. 移动石子直到连续 II – 力扣（LeetCode）

最开始想着就是模拟左边的点跳到第一空的点但是发现不对

比如这个数据

stones = [12,15,7,2,13] answer = 8 的

想了一下这个可以从最后的答案往回推

排好序是 2, 7, 12 ，13 15 最后的答案范围是肯定小于 [2，15]的但是我们需要将其尽可能的落在大的空区间上比如这个题有 [3,6] [8,11] [14,14]这三个空区间如果有一个空区间大于这个5个数那么应该将其放进去但是这里的空区间没有那么多只能将其两个大的长度为4的拼在一起

难题

二进制之和

问题描述
小U和小R喜欢探索二进制数字的奥秘。他们想找到一个方法，将两个二进制字符串相加并以十进制的形式呈现。这个过程需要注意的是，他们的二进制串可能非常长，所以常规的方法可能无法处理大数。小U和小R希望你帮助他们设计一个算法，该算法能在保证时间复杂度不超过O(n^2)的前提下，返回两个二进制字符串的十进制求和结果。

测试样例
样例1：

输入：binary1 = "101" ,binary2 = "110"
输出：'11'

样例2：

输入：binary1 = "111111" ,binary2 = "10100"
输出：'83'

样例3：

输入：binary1 = "111010101001001011" ,binary2 = "100010101001"
输出：'242420'

样例4：

输入：binary1 = "111010101001011" ,binary2 = "10010101001"
输出：'31220'

样例5：

输入：binary1 = "11" ,binary2 = "1"
输出：'4'

方法

简单的模拟题，先将短的左补齐然后从右到左依次记录进位相加的同时转换为10进制数

def solution(binary1, binary2):
    # 找到最长的字符串长度
    max_length = max(len(binary1), len(binary2))
    
    # 在左边补0对齐
    binary1 = binary1.zfill(max_length)
    binary2 = binary2.zfill(max_length)
    
    carry = 0
    result = []
    
    # 从右往左进行相加
    for i in range(max_length - 1, -1, -1):
        b1 = int(binary1[i])
        b2 = int(binary2[i])
        total = b1 + b2 + carry
        
        # 计算当前位的和和进位
        if total >= 2:
            result.append(str(total % 2))
            carry = total // 2
        else:
            result.append(str(total))
            carry = 0
    
    # 如果有进位剩余
    if carry:
        result.append(str(carry))
    
    # 反转结果并转换为十进制字符串
    return str(int(''.join(reversed(result)), 2))

if __name__ == "__main__":
    print(solution("101", "110") == "11")
    print(solution("111111", "10100") == "83")
    print(solution("111010101001001011", "100010101001") == "242420")
    print(solution("111010101001011", "10010101001") == "31220")

查找热点数据问题

查找热点数据问题
问题描述
给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

1 <= nums.length <= 10^5
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
你所设计算法的时间复杂度必须优于 O(n log n)，其中 n 是数组大小。

测试样例
样例1：

输入：nums = [1, 1, 1, 2, 2, 3], k = 2
输出：[1, 2]

样例2：

输入：nums = [1], k = 1
输出：[1]

样例3：

输入：nums = [4, 4, 4, 2, 2, 2, 3, 3, 1], k = 2
输出：[4, 2]

方法

按照c++之前的想法就是先排序排序完成之后映射每个数出现了多少次然后找到出现频率前k高的

结果py都不用这样麻烦

from collections import Counter

def solution(nums, k):
    # 统计每个数字的出现次数
    count = Counter(nums)
    # 按出现次数从大到小排序，并提取前k个不同的数字
    most_common = count.most_common(k)
    # 返回前k个数字，以逗号分隔
    return ",".join(str(num) for num, _ in most_common)

if __name__ == "__main__":
    print(solution([1, 1, 1, 2, 2, 3], 2) == "1,2")
    print(solution([1], 1) == "1")

作者：Tankoldbang

物联沃分享整理
物联沃-IOTWORD物联网 » 字节青训营 X 豆包MarsCode 技术训练营 2024 入营考核

代码收藏家普通

分享到：

更新

简单题

兔生兔 兔群繁殖之谜

题目描述

方法

找单独的数

题目描述

方法

打点计数器的区间合并

问题描述

测试样例

方法

判断数组是否单调

问题描述

测试样例

方法

找出整型数组中占比超过一半的数

问题描述

测试样例

方法

版本号比较

问题描述

测试样例

方法

比赛配对问题

问题描述

测试样例

方法

找出最长的神奇数列

问题描述

测试样例

方法

充电总时间计算

问题描述

测试样例

方法

最大乘积区间问题

问题描述

测试样例

方法

中等题

及格的组合方式探索

问题描述

测试样例

方法

和的逆运算问题

问题描述

测试样例

方法

数字翻译成字符串的可能性

题目

方法

快乐时间最大化

问题描述

测试样例

方法

P整数生成问题

问题描述

测试样例

方法

最大乘积问题

问题描述

测试样例

方法

石子移动问题

问题描述

测试样例

方法

难题

二进制之和

方法

查找热点数据问题

方法

代码收藏家 普通

相关推荐

发表回复 取消回复

兔生兔兔群繁殖之谜

代码收藏家普通

发表回复取消回复