编程基础知识

算法复杂度

编写程序需要注重算法复杂度，刷题时也存在多解，如何找到最优解成为一个需要重点关注的方向。 

算法复杂度：是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。应用于数学和计算机导论。同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

时间频度：一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。

时间复杂度：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),存在一个正常数c使得f(n)*c>=T(n)恒成立。记作T(n)=O(f(n))，称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

按数量级递增排列，常见的时间复杂度有：

常数阶O(1),对数阶O(log2n)(以2为底n的对数，下同),线性阶O(n),

线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，

k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

举例：求两个n阶方阵的乘积 C=A×B,其算法如下

# define n 100 // n 可根据需要定义,这里假定为100
void MatrixMultiply(int A[n][n]，int B [n][n]，int C[n][n])
{ //右边列为各语句的频度int i ,j ,k;for(i=0; i<n;i++) //n+1                              (1)for (j=0;j<n;j++) { //n*(n+1)                    (2)C[i][j]=0; //n²                              (3)for (k=0; k<n; k++) //n²*(n+1)               (4)C[i][j]=C[i][j]+A[i][k]*B[k][j];//n³     (5)}
}

该算法中所有语句的频度之和(即算法的时间耗费)为：

T(n)=2n^3+3n^2+2n+1

分析：

语句(1)的循环控制变量i要增加到n，测试到i=n成立才会终止。故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句(1)循环体内的语句应该执行n次，但语句(2)本身要执行n+1次，所以语句(2)的频度是n(n+1)。同理可得语句(3)，(4)和(5)的频度分别是n^2，(n+1)n^2和n^3。当n充分大时，T(n)和n^3之比是一个不等于零的常数。即T(n)和n^3是同阶的，或者说T(n)和n^3的数量级相同。记作T(n)=O(n^3)是算法MatrixMultiply的渐近时间复杂度。主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。

空间复杂度：是指算法在计算机内执行时所需存储空间的度量。记作:S(n)=O(f(n))。

算法执行期间所需要的存储空间包括3个部分：

• 算法程序所占的空间；
• 输入的初始数据所占的存储空间；
• 算法执行过程中所需要的额外空间。

通常一个算法的复杂度是由其输入量决定的，随着输入的增加，复杂度不同算法的复杂度增长速度如下图所示。为了降低算法复杂度，应当同时考虑到输入量，设计较好的算法。

数据结构

列出一些最常见的数据结构：

• 数组
• 栈
• 队列
• 链表
• 树
• 图
• 堆
• 散列表（哈希表）

具体介绍在这篇博客链接里：leetcode刷题前必看算法基础和数据结构

介绍完算法基础知识，接下来是leetcode刷题部分。

1. 两数之和【简单难度】

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

 代码：

class Solution:def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""# 方法1：暴力法之两个循环遍历（高维数组，耗时长，不推荐）（6284 ms	14.8 MB）    O(n^2)for i in range(len(nums) - 1):for j in range(i + 1, len(nums)):if target - nums[i] == nums[j]:return [i,j]# 方法2：一个循环(1548 ms	14.7 MB) O(n)for i in range(len(nums)):if (target-nums[i]) in nums:j = nums.index(target-nums[i])if i == j:continueelse:return [i,j]# 方法3：字典存储差值(76 ms	15.2 MB)    O(n)d = {}for x in range(len(nums)): if nums[x] in d:return [d[nums[x]],x]else:d[target - nums[x]] = xcontinue# 方法4：列表变换为索引序列（1556 ms	14.8 MB）    O(n)for k, i in enumerate(nums):if target - i in nums[k + 1:]:return [k, nums[k + 1:].index(target - i) + k + 1]

方法一：暴力法（循环遍历），高维数组，耗时长，不推荐

很简单，遍历每个元素 xx，并查找是否存在一个值与 target - x  相等的目标元素

复杂度分析：

• 时间复杂度：O(n^2)，

对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)的时间。因此时间复杂度为 O(n^2)。

• 空间复杂度：O(1)。

方法二：基本同方法一

方法三：哈希表

两遍哈希表
为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。

通过以空间换取速度的方式，我们可以将查找时间从 O(n)降低到 O(1)。哈希表正是为此目的而构建的，它支持以 近似 恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到 O(n)。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 O(1)。

一个简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target - nums[i]）是否存在于表中。注意，该目标元素不能是 nums[i] 本身！比如nums=[3,3]，target=6，两遍哈希表会报错，因为存储为字典时，key相同只能存一个value，故使用一遍哈希表来解决此问题。

复杂度分析：

• 时间复杂度：O(n)，

我们把包含有 n个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1)，所以时间复杂度为 O(n)。

• 空间复杂度：O(n)，

所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n个元素。

一遍哈希表
事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

复杂度分析：

• 时间复杂度：O(n)，

我们只遍历了包含有 nn 个元素的列表一次。在表中进行的每次查找只花费 O(1)的时间。

• 空间复杂度：O(n)，

所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。

7. 反转整数

给定一个 32 位有符号整数，将整数中的数字进行反转。

示例 1:

输入: 123
输出: 321

 示例 2:

输入: -123
输出: -321

示例 3:

输入: 120
输出: 21

注意:

假设我们的环境只能存储 32 位有符号整数，其数值范围是   。根据这个假设，如果反转后的整数溢出，则返回 0。

代码：

class Solution:def reverse(self, x):""":type x: int:rtype: int"""if -10 < x < 10:return xelif (x < (-2**31)) or (x > 2**31 -1):return 0else:a = abs(x)b = str(a)c = b[::-1]d = int(c)if x < 0:return -delse:return dif __name__ == '__main__':x = -120out = Solution()output = out.reverse(x)print(output)    #-21

9. 回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121
输出: true

示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:

你能不将整数转为字符串来解决这个问题吗？

代码：

class Solution:def isPalindrome(self, x):""":type x: int:rtype: bool"""a = str(x)b = a[::-1]return a==bif __name__ == '__main__':x = 101out = Solution()output = out.isPalindrome(x)print(output)     #True

13. 罗马数字转整数

罗马数字包含以下七种字符：I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: "III"
输出: 3

示例 2:

输入: "IV"
输出: 4

示例 3:

输入: "IX"
输出: 9

示例 4:

输入: "LVIII"
输出: 58
解释: C = 100, L = 50, XXX = 30, III = 3.

示例 5:

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

代码：

class Solution:def romanToInt(self, s):""":type s: str:rtype: int"""sum = 0romanDict = {'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1}for i in range(len(s)-1):if romanDict[s[i]] < romanDict[s[i+1]]:sum = sum - romanDict[s[i]]else:sum = sum + romanDict[s[i]]result = sum + romanDict[s[-1]]if 1 <= result <= 3999:return resultelse:return 'out of range'if __name__ == '__main__':s = 'MCMXCIV'out = Solution()output = out.romanToInt(s)print(output)    #1994

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

代码：

import osclass Solution:# 方法一：直接调用现有函数def longestCommonPrefix_use_os(self, strs):""":type strs: List[str]:rtype: str"""prefix = os.path.commonprefix(strs)    # 返回list中，所有元素共有的最长的前缀return prefix# 方法二：循环遍历每个字符串相同索引处的字符是否一致def longestCommonPrefix(self, strs):""":type strs: List[str]:rtype: str"""# 列表按照各个元素的长度排序strs = sorted(strs, key=lambda i: len(i))prefix = ''# 判断是否为空列表if not strs:return prefixelse:for i in range(len(strs[0])):tmp = strs[0][i]for item in strs:if item[i] != tmp:return prefixprefix += tmpreturn prefix# 方法三：def longestCommonPrefix_use_zip(self, strs):""":type strs: List[str]:rtype: str"""prefix = ''# enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)# 组合为一个索引序列，同时列出数据和数据下标for _, item in enumerate(zip(*strs)):if len(set(item)) > 1:return prefixelse:prefix += item[0]return prefixif __name__ == '__main__':strs = ["flower","flow","flight",'flop']out = Solution()output = out.longestCommonPrefix_use_os(strs)print(output)    #fl

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

代码：

class Solution:def isValid1(self, s):""":type s: str:rtype: bool"""if len(s)%2 != 0 or len(s) ==0:return FalsesDict = {'(':1, ')':1, '{':2, '}':2, '[':3, ']':3}result = 0for i in range(0, len(s)-1, 2):result += sDict[s[i]] - sDict[s[i+1]]return result==0def isValid2(self, s):""":type s: str:rtype: bool"""# 排除空列表和奇数个元素的列表 if len(s) % 2 == 1 or len(s) == 0:return Falsed = {'{': '}', '[': ']', '(': ')'}stack = []for i in s:if i in d:stack.append(i)else:# 若第一个就是右括号直接排除，不是右括号再入栈if not stack or d[stack.pop()] != i:return Falsereturn stack == []def isValid3(self, s):""":type s: str:rtype: bool"""a = {')':'(', ']':'[', '}':'{'}l = [None]for i in s:if i in a and a[i] == l[-1]:l.pop()else:l.append(i)return len(l)==1if __name__ == '__main__':s = '{[]}'out = Solution()output = out.isValid1(s)print(output)    #True

21. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

代码：

# Definition for singly-linked list.
class ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:# 方法1：递归方法def mergeTwoLists1(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""# 判断l1和l2是否存在空链表，有空链表就可以直接返回if l1==None and l2==None:return Noneif l1==None:return l2if l2==None:return l1# 找出l1和l2中最小的结点，作为新链表的表头结点# 然后依次比较遍历l1和l2，将较小的结点插入在新链表的后面if l1.val<=l2.val:l1.next=self.mergeTwoLists(l1.next,l2)return l1else:l2.next=self.mergeTwoLists(l1,l2.next)return l2# 方法2：非递归方法def mergeTwoLists2(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""head = ListNode(0)first = headwhile l1!=None and l2!=None:if l1.val <= l2.val:head.next = l1l1 = l1.nextelse:head.next = l2l2 = l2.nexthead = head.nextif l1 != None:head.next = l1elif l2 != None:head.next = l2return first.next

26. 删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {print(nums[i]);
}

代码： 

class Solution:# 方法一，不按照元素大小顺序排列def removeDuplicates1(self, nums):""":type nums: List[int]:rtype: int"""        x = [][x.append(i) for i in nums if not i in x]return x# 方法二，按照元素大小顺序排列def removeDuplicates2(self, nums):""":type nums: List[int]:rtype: int"""        x = list(set(nums))return xif __name__ == '__main__':nums = [0,0,1,1,1,4,2,2,3,3,4]out = Solution()output = out.removeDuplicates2(nums)print(output)    #[0, 1, 2, 3, 4]

27. 移除元素

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {print(nums[i]);
}

代码：

class Solution:def removeElement(self, nums, val):""":type nums: List[int]:type val: int:rtype: int"""while val in nums:nums.remove(val)return len(nums)if __name__ == '__main__':nums = [0,1,2,2,3,0,4,2]val = 2out = Solution()output = out.removeElement(nums, val)print(output)    #5

28. 实现strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

代码：

class Solution:def strStr1(self, haystack, needle):""":type haystack: str:type needle: str:rtype: int"""return haystack.find(needle)# Python index() 方法检测字符串中是否包含子字符串 str ，# 如果指定 beg（开始） 和 end（结束） 范围，则检查是否包含在指定范围内，# 该方法与 python find()方法一样，只不过如果str不在 string中会报一个异常。def strStr2(self, haystack, needle):""":type haystack: str:type needle: str:rtype: int"""try:return haystack.index(needle)except:return -1if __name__ == '__main__':haystack = 'hello'needle = 'll'out = Solution()output = out.strStr1(haystack, needle)print(output)    #2

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2

示例 2:

输入: [1,3,5,6], 2
输出: 1

示例 3:

输入: [1,3,5,6], 7
输出: 4

示例 4:

输入: [1,3,5,6], 0
输出: 0

代码：

class Solution:def searchInsert(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""nums.append(target)# 列表去重后排序nums = sorted(set(nums))return nums.index(target)if __name__ == '__main__':nums = [1,3,5,6]target = 7out = Solution()output = out.searchInsert(nums, target)print(output)    #4

38. 报数

报数序列是指一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 被读作  "one 1"  ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2",  "one 1" （"一个二" ,  "一个一") , 即 1211。

给定一个正整数 n ，输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

示例 1:

输入: 1
输出: "1"

示例 2:

输入: 4
输出: "1211"

代码：

class Solution:def countAndSay(self, n):""":type n: int:rtype: str"""if n <= 0 or not str(n).isdigit():return Falseif n == 1:return "1"if n == 2:return "11"# 进行i=3时的循环时，它的上一项为'11'result = '11'# 用for循环不断去计算逼近最后一次for i in range(3, n+1):res = ""    # 结果，每次报数都要初始化count = 1   # 计数变量for j in range(1, len(result)):if result[j-1] == result[j]:count += 1  # 相等则加一else:# 一旦遇到不同的变量，就更新结果res += str(count) + result[j-1]count = 1   # 重置为1# 把最后一项及它的数量加上res += str(count) + result[j]# 保存上一次的结果result = resreturn resultif __name__ == '__main__':n = 5out = Solution()output = out.countAndSay(n)print(output)    #111221

class Solution(object):# 不递归方法def countAndSay(self, n):""":type n: int:rtype: str"""basic_count_say = "1"for num in range(n - 1):  # 从第二个报数开始计算basic_count_say = self.transform(basic_count_say)  # 调用报数变换函数return basic_count_saydef transform(self, basic_count_say):  # 报数变换count = 0  # 某个数字连续出现的次数temp_cha = basic_count_say[0]  # 当前数字new_str = ""  # 新的报数序列for cha in basic_count_say:  # 遍历旧的报数序列if temp_cha == cha:  # 相同连续数字累加count += 1else:  # 出现不相同数字就补充新报数序列new_str = new_str + str(count) + temp_chatemp_cha = cha  # 清零，从头累加新的数字count = 1new_str = new_str + str(count) + temp_cha  # 最后一个数字补充到新报数序列中return new_strif __name__ == '__main__':n = 5out = Solution()output = out.countAndSay(n)print(output)

class Solution:# 递归方法def countAndSay(self, n):""":type n: int:rtype: str"""if n == 1:return "1"s = self.countAndSay(n - 1)  # !!!!递归count = 0  # 某个数字连续出现的次数temp_cha = s[0]  # 当前数字new_str = ""  # 新的报数序列for cha in s:  # 遍历旧的报数序列if temp_cha == cha:  # 相同连续数字累加count += 1else:  # 出现不相同数字就补充新报数序列new_str = new_str + str(count) + temp_chatemp_cha = cha  # 清零，从头累加新的数字count = 1new_str = new_str + str(count) + str(temp_cha)  # 最后一个数字补充到新报数序列中return new_strif __name__ == '__main__':n = 5out = Solution()output = out.countAndSay(n)print(output)

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

代码：

class Solution:# 穷举法，时间复杂度：O(N^2)def maxSubArray_enu(self, nums):""":type nums: List[int]:rtype: int"""# 若列表元素均小于0，则最大子序列为值最大的元素if max(nums) < 0:return max(nums)# 若列表元素不全小于0l = len(nums)maxres = 0for i in range(0, l):temp = 0for j in range(i, l):temp += nums[j]if temp > maxres:maxres = tempreturn maxres# 动态规划法，时间复杂度：O(N)# 最大连续的子序列和必须是在位置0-(n-1)之间的某个位置结束# 将一个问题用动态规划方法处理的准则：# “最优子结构”、“子问题重叠”、“边界”和“子问题独立”def maxSubArray_dyn(self, nums):""":type nums: List[int]:rtype: int"""# 若列表元素均小于0，则最大子序列为值最大的元素if max(nums) < 0:return max(nums)# 若列表元素不全小于0l = len(nums)maxres = 0temp = 0for i in range(l):# 当循环遍历到第i个位置时，如果其前面的连续子序列和小于等于0，# 那么以位置i结尾的最大连续子序列和就是第i个位置的值即nums[i]if temp < 0:maxres = nums[i]# 如果其前面的连续子序列和大于0，# 则以位置i结尾的最大连续子序列和为maxres[i] = max{ maxres[i-1]+nums[i]，nums[i]}else:temp += nums[i]if temp > maxres:maxres = tempreturn maxresif __name__ == '__main__':nums = [-2,1,-3,4,-1,2,1,-5,4]# nums = [-2, -1, -3, -4, -1, -2, -1, -5, -4]out = Solution()output = out.maxSubArray_dyn(nums)print(output)     #6

58. 最后一个单词的长度

给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。

如果不存在最后一个单词，请返回 0 。

说明：一个单词是指由字母组成，但不包含任何空格的字符串。

示例:

输入: "Hello World"
输出: 5

代码：

class Solution:def lengthOfLastWord(self, s):""":type s: str:rtype: int"""word = s.split(' ')return len(word[-1])if __name__ == '__main__':s = "Hello World"out = Solution()output = out.lengthOfLastWord(s)print(output)    #5