class Solution:
"""
@param nums: A list of integers
@return: A integer indicate the sum of max subarray
"""
def maxSubArray(self, nums):
# write your code here
‘‘‘
做两步判断:
1.第一步判断:当n > 0 的时候，继续加。如果n小于0，则n取最新的数，之前的舍弃
2.第二步判断：sum 和 继续加的n作比较，如果sum < n,那么sum = n，否则sum保持。
‘‘‘
sum = nums[0]
n = nums[0]
for i in range(1,len(nums)):
if n > 0:
n = n + nums[i]
else: #一旦n < 0,舍弃，取新的值n进行继续相加
n = nums[i]
if sum < n:
sum = n
return sum
第二种解法:O(n2)时间复杂度
def MaxSumArray(nums):
‘‘‘
1.取出所有符合条件的顺序数组
2.然后将所有顺序数组的值放在一个大的数组[]里面，最后返回里面的最大值max
:param nums:
:return:
‘‘‘
array = []
for i in range(len(nums)):
for j in range(i + 1,len(nums)):
array.append(sum(nums[i:j]))
return max(array)
result = MaxSumArray([-2,2,-3,4,-1,2,1,-5,3])
print(result)
二. 最小子数组
给定一个整数数组，找到一个具有最小和的连续子数组。返回其最小和。
样例
样例 1
输入：[1, -1, -2, 1]
输出：-3
样例 2
输入：[1, -1, -2, 1, -4]
输出：-6
注意事项
子数组最少包含一个数字
class Solution:
"""
@param: nums: a list of integers
@return: A integer indicate the sum of minimum subarray
"""
def minSubArray(self, nums):
# write your code here
‘‘‘
1.负数一直相加，一旦大于0，则被替换
2.sum 记录之前保存最小值的和，如果一旦有出现更小的和的话，则被替换
:param nums:
:return:
‘‘‘
n = nums[0]
sum = nums[0]
for i in range(1,len(nums)):
if n < 0:
n = n + nums[i]
else:
n = nums[i]
if sum > n:
sum = n
return sum
class Solution:
"""
@param: nums: Given an integers array A
@return: A longlong array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
"""
def productExcludeItself(self, nums):
# write your code here
array = []
for i in range(len(nums)):
sum = 1for j in range(len(nums)):
if i != j:
sum = sum * nums[j]
array.append(sum)
return array
四. 翻转字符串中的单词
给定一个字符串，逐个翻转字符串中的每个单词。
样例
样例 1:
输入: "the sky is blue"
输出: "blue is sky the"
样例解释:
返回逐字反转的字符串.
样例 2:
输入: "hello world"
输出: "world hello"
样例解释:
返回逐字反转的字符串
说明
单词的构成：无空格字母构成一个单词，有些单词末尾会带有标点符号
输入字符串是否包括前导或者尾随空格？可以包括，但是反转后的字符不能包括
如何处理两个单词间的多个空格？在反转字符串中间空格减少到只含一个
输入测试数据 (每行一个参数)如何理解测试数据？
输出: "world hello" 样例解释: 返回逐字反转的字符串.
说明
单词的构成：无空格字母构成一个单词，有些单词末尾会带有标点符号
输入字符串是否包括前导或者尾随空格？可以包括，但是反转后的字符不能包括
如何处理两个单词间的多个空格？在反转字符串中间空格减少到只含一个
class Solution:
"""
@param: s: A string
@return: A string"""
def reverseWords(self, s):
# write your code here
array = s.split(‘‘)
new_s = ‘‘for i in range(len(array)):
if array[i] != ‘‘:
new_s = array[i] + ‘‘ + new_s
return new_s
注释:
1.‘hello word xiao li ‘.split(‘ ‘) 结果为[‘hello‘,‘‘,world‘,‘‘,‘‘,‘xiao‘,‘‘,‘li‘,‘‘]
五. 比较字符串
比较两个字符串A和B，确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母
样例
给出 A = "ABCD" B = "ACD"，返回 true
给出 A = "ABCD" B = "AABC"， 返回 false
注意事项
在 A 中出现的 B 字符串里的字符不需要连续或者有序。
class Solution:
"""
@param A: A string
@param B: A string
@return: ifstring A contains all of the characters in B returntrueelsereturnfalse"""
def compareStrings(self, A, B):
# write your code here
for n in B:
if n not in A:
return False
A = A.replace(n,‘‘,1) ##每次校验完之后，要去除掉首个校验通过的字符(即校验在A里面的字符,字符位置不固定，但固定是首次出现的字符)
return True
