求解连续子数组的最大和，问题可以分解为如下步骤： 数组长度为0，返回0 数组长度为1，返回数组第一个值 数组长度大于1，从前往后，判断数组（第i个值+第i-1个值）于（第i个值）的大小，将其中较大值赋值给当前数组的第i个值。即计算数组从第一个值，到第i个值的最大子数组。 def max_sum(n, dp): if n == 0: return 0 elif n == 1: return dp[0] else: for i in range(1, n): dp[i] = max(dp[...

利用一个数组dp来存储当前层的上一层元素，然后从前往后修改dp数组中的元素。 dp[j] = triangle[i][j] + min(dp[j],dp[j+1])，其中j表示当前层的第j个元素的下标。 通过从后往前遍历每一层，就找到了每一个点的最小值的路径，最终遍历至一底层，最小值存储在dp[0] # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param triangle int整型二维数组 # @return int整型 # class Solution: def minTrace(self , triangle: List...

从下往第n阶跳的方法数为F(n)，F(n)的前一步骤为F(n-1)或F(n-2) 故问题简化为斐波那契数列F(n) = F(n-1) + F(n-2) 使用动态规划的方式进行实现，用空间节约时间 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param number int整型 # @return int整型 # class Solution: def jumpFloor(self , number: int) -> int: # write code here if number == 1...

# @param q 询问次数 # @param a 乘数 # @param b 乘数 # @param p 除数 # @return res a*b对p取余数 def fast_add(a, b, p): res = 0 while b > 0: if b % 2 == 1: res = (res + a) % p b = b // 2 a = (a + a) % p return res % p q = int(input()) for i in range(q): s =...

若采用循环直接实现幂指数计算时间复杂度为O(n) 使用快速幂的方式，即计算的幂指数的指数部分每次减半，底数变为平方。通过对折的方式，减少指数部分，从而减少循环的次数。 （对指数奇偶性进行判断）当指数大于零的时候，对2取余数，余数为1的时候，此时计算的结果res乘一次底数，并将结果对p取余。 指数对2取整（变为原来的一半），底数取平方并对p取余数。 当指数<=0，跳出循环。 tips:计算中对p取余数，防止数值过大，造成内存溢出。 # @param q 询问次数 # @param a 底数 # @param b 指数 # @param p 除数 # @return res 幂指数...

汉诺塔问题：将n个盘子从left柱，借助mid柱，放至right柱（大的盘子不能放在小的盘子上） 可以分解为以下三个步骤： 把n-1个盘子，从left，借助mid，放至right上 把最大的盘子，从left，放至right上。 把n-1个盘子从mid，借助left，放至right上 tips：经过前两步操作，最大的盘子已经就位，无需移动且对问题不再产生影响。相当于问题已经重置，需要将剩下的n-1个盘子，移动至righ柱子上。盘子均放在mid柱上，相当于初始时的left。 # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param n int...

采用枚举的方式，将一天的时间转换为0 - 60 * 24 分钟并进行遍历，每个遍历值记为i 创建两个列表，分别存储两个输入时间的可能分钟数 分别判断遍历值i能否满足两个输入值的格式，若满足，则将i添加到对应的列表中 s1 = input() s2 = input() # 创建两个空列表存储可能的时间 list1 = [] list2 = [] # 遍历0 - 60 * 24 分钟 for i in range(0, 60 * 24): hour = int(i //60) # 获取小时 minute = int(i % 60) # 获取分钟 # 十位...

# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @param val int整型 # @return ListNode类 # class Solution: def deleteNode(self , head: ListNode, val: int) -> ListNode: ...

采用递归和非递归方式实现 # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param pHead1 ListNode类 # @param pHead2 ListNode类 # @return ListNode类 非递归方式 class Solution: def Merge(self , pHead1: ListNode, pHead2: ...

非递归与递归的方式： 非递归： # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # @param head ListNode类 # @return ListNode类 # 非递归方式 class Solution: def ReverseList(self , head: ListNode) -> ListNode: # write co...

class linkedlist: def __init__(self): self.items = [] def insert(self, x, y): if x in self.items: loc = self.items.index(x) self.items.insert(loc, y) else: self.items.append(y) def delete(self, x): if x...

基于普通的队列形式，增加队列长度的判断 class Cirque(): def __init__(self): self.items = [] def push(self, x): return self.items.append(x) def front(self): return self.items[0] def pop(self): return self.items.pop(0) def size(self): ...

采用双栈解题 建立两个栈 number_stack：存放字符串s中的数字 sign_stack：存放字符串中的括号，运算符 遍历字符串，将字符串中表示数字和符号的部分分别压入数字栈和符号栈中。 压入数字栈的时候，如数字123，遍历字符串依次得到"1","2","3"，故需要对相应的数字乘以相应的位数转化为对应的数值1×10×10+2×10+3。 压入符号栈的时候，规则如下： 判断左括号，压入符号栈 判断右括号，计算与之匹配的左括号之间的数值运算，并将结果压入数字栈中 判断乘号，当符号栈为空的时候，直接压入符号栈；符号栈非空，且栈顶为号，弹出数字栈顶两个数字，与符号栈顶符号，进行运...

采用栈的方式，依次将字符串s中的字符放入栈中。当栈顶元素与待放入元素相同时，弹出栈顶元素。 def deduplication(s): stack = [] for i in range(len(s)): if len(stack) == 0: # 栈为空时，直接放入字符 stack.append(s[i]) else: if stack[-1] == s[i]: # 栈顶元素与待放入元素相同时，弹出栈顶元素 stack.pop() else:...