2023牛客暑期多校训练营2

**2023牛客暑期多校训练营2**

**前言**

2023年是机器学习和人工智能的元年，各大公司纷纷投入大量资源来开发和应用这些技术。作为一名程序员，你一定希望能够掌握这些最新的技能，以便在竞争激烈的市场中脱颖而出。

牛客暑期多校训练营2是为此目的而设立的一项挑战，旨在帮助你提高编程能力、学习机器学习和人工智能等知识，并且能够应对各种算法题目。下面是本次训练营的内容。

**第一天：基础算法**

###1.1 快速幂快速幂（Fast Exponentiation）是一种常见的算法，它可以用来计算一个数的幂。例如，计算 $2^{10}$ 的值，可以使用快速幂算法得到结果。

def power(base, exponent):
 """
 Calculate the power of a number using fast exponentiation.

 Args:
 base (int): The base number.
 exponent (int): The exponent to which the base is raised.

 Returns:
 int: The result of the power operation.
 """
 if exponent ==0:
 return1 elif exponent %2 ==0:
 half_power = power(base, exponent //2)
 return half_power * half_power else:
 half_power = power(base, (exponent -1) //2)
 return base * half_power * half_power# Example usage:
print(power(2,10)) # Output:1024

def max_subarray_sum(arr):
 """
 Find the maximum subarray sum in a given array.

 Args:
 arr (list): The input array.

 Returns:
 int: The maximum subarray sum.
 """
 if not arr:
 return0 current_sum = max_sum = arr[0]
 for num in arr[1:]:
 current_sum = max(num, current_sum + num)
 max_sum = max(max_sum, current_sum)

 return max_sum# Example usage:
arr = [-2, -3,4, -1, -2,1,5, -3]
print(max_subarray_sum(arr)) # Output:7

class MinStack:
 def __init__(self):
 self.stack = []
 self.min_stack = []

 def push(self, x):
 self.stack.append(x)
 if not self.min_stack or x <= self.min_stack[-1]:
 self.min_stack.append(x)

 def pop(self):
 if self.stack:
 popped_value = self.stack.pop()
 if popped_value == self.min_stack[-1]:
 self.min_stack.pop()
 return popped_value else:
 return None def top(self):
 if self.stack:
 return self.stack[-1]
 else:
 return None def getMin(self):
 if self.min_stack:
 return self.min_stack[-1]
 else:
 return None# Example usage:
min_stack = MinStack()
min_stack.push(5)
min_stack.push(4)
min_stack.push(2)
print(min_stack.getMin()) # Output:2