题目描述
小U和小R喜欢探索二进制数字的奥秘。他们想找到一个方法，将两个二进制字符串相加并以十进制的形式呈现。这个过程需要注意的是，他们的二进制串可能非常长，所以常规的方法可能无法处理大数。小U和小R希望你帮助他们设计一个算法，该算法能在保证时间复杂度不超过O(n^2)的前提下，返回两个二进制字符串的十进制求和结果。
def solution(binary1, binary2):# 反转字符串以便从最低位开始相加binary1 = binary1[::-1]binary2 = binary2[::-1]max_length = max(len(binary1), len(binary2))carry = 0result = []for i in range(max_length):bit1 = int(binary1[i]) if i < len(binary1) else 0bit2 = int(binary2[i]) if i < len(binary2) else 0# 计算当前位的和total = bit1 + bit2 + carryresult.append(str(total % 2)) # 当前位的结果carry = total // 2 # 计算进位# 如果最后还有进位，添加到结果中if carry:result.append(str(carry))# 反转结果并转换为十进制result.reverse()decimal_result = str(int(''.join(result), 2))return decimal_resultif __name__ == "__main__":# 你可以添加更多的测试用例print(solution("101", "110") == "11")print(solution("111111", "10100") == "83")print(solution("111010101001001011", "100010101001") == "242420")print(solution("111010101001011", "10010101001") == "31220")题目描述
给定一段受损的 DNA 碱基序列 dna1，在每次只操作一个碱基的情况下，将其以最少的操作步骤将其还原到未受损的 DNA 碱基序列 dna2。
只可以对 DNA 碱基序列中的一个碱基进行三种操作：
- 增加一个碱基
- 去除一个碱基
- 替换一个碱基
输入描述:
输入两段 DNA 碱基序列，每段分一行输入
第一行为第一段受损的 DNA 碱基序列 dna1
第二行为第二段未受损的 DNA 碱基序列 dna2
输出描述:
最小操作步骤数
备注:
0 <= dna1.length, dna2.length <= 500
dna1 和 dna2 由大写英文字母 A、G、C、T 组成
示例 1
输入
AGCTTAGC
AGCTAGCT
def solution(dna1, dna2):# 初始化动态规划表len1, len2 = len(dna1), len(dna2)dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]# 初始化边界条件for i in range(len1 + 1):dp[i][0] = ifor j in range(len2 + 1):dp[0][j] = j# 填充动态规划表for i in range(1, len1 + 1):for j in range(1, len2 + 1):if dna1[i - 1] == dna2[j - 1]:dp[i][j] = dp[i - 1][j - 1]else:dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1return dp[len1][len2]# 测试用例
if __name__ == "__main__":print(solution("AGT", "AGCT") == 1)print(solution("AGCCGAGC", "GCTAGCT") == 4)题目描述
小U面临一个有趣的任务：在一个 n×nn×n 的方阵中填入 11 到 n×nn×n 这些数字，并要求按照蛇形顺序从右上角开始，沿着方阵的边界顺时针进行填充。蛇形填充的特殊排列方式使得每一层数字呈现出波浪形的排列方式。
例如，当 n=4n=4 时，方阵应如下所示：
10 11 12 1
9 16 13 2
8 15 14 3
7 6 5 4
def solution(n: int) -> list:maxn = 20a = [[0] * maxn for _ in range(maxn)]x, y, tot = 0, n - 1, 1a[x][y] = totwhile tot < n * n:while x + 1 < n and a[x + 1][y] == 0:x += 1tot += 1a[x][y] = totwhile y - 1 >= 0 and a[x][y - 1] == 0:y -= 1tot += 1a[x][y] = totwhile x - 1 >= 0 and a[x - 1][y] == 0:x -= 1tot += 1a[x][y] = totwhile y + 1 < n and a[x][y + 1] == 0:y += 1tot += 1a[x][y] = totreturn [row[:n] for row in a[:n]]
