2021-10-25
题目
1.最大子序和
2.搜索插入位置
3.检测大写字母
4.最后一个单词长度
5.搜索二维矩阵
6.有效的字母异位词
题解
1.最大子序和
本题是一个一维dp问题，我们可以用双指针，或者分治法来解本题。
首先我们先定义一个最大值和当前最大值，然后经行循环相加，并经行判断，如果当前数和下一位数相加的话大于下一位数，我们就把指针向右继续移动，在当前最大值和下一个数进行对比，谁大就把谁赋值给最大值，反之小于的话，我么就直接从下一个数从头开始相加，直到找到最大值！！！
2.搜索插入位置
在python本题思路比较好写，我们可以先把数组里面的数和插入数进行对比，如果数组中有第一个数大于插入值然后直接返回该数的下标，如果数组中都没有大于插入数的我们就直接可以返回原数组的长度。
3.检测大写字母
这个题开始我准备用双指针来写的，但是最后几个例子总是出错，然后我就直接看了题解，题解就职直接用的就是函数，我觉得这个就没啥意思了，我就先不说这个题的题解了。
4.最后一个单词长度
此题和我之前做的返回字符串的中的单词数很类似，我们可以把这个字符串里面的所有单词给添加到一个列表里面去，最后返回列表里面的最后一个单词的长度，如何添加单词大家可以看我上面的那个题的题解哦！！！
5.搜索二维矩阵
这个题在python中其实能卡一个bug----用 in 一下子就出来了，时间复杂度也是n。
但是我们刷算法的目的是什么？就是为了最优的解决这个问题，让它的效率最大化！！
所以我们不应该取巧的。
这个题主要的思路就是以右上角开始，如果目标变量比右上角的数小，就向左移一列，如果目标标量比右上角的数大就下一移动到下一行的数组中，由此来判断，最后是否能够在这个二维数组里面找到这个目标变量！
两者的复杂度：
6.有效的字母异位词
t是 ss 的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 ss 和 tt 分别排序，看排序后的字符串是否相等即可判断。此外，如果 ss 和 tt 的长度不同，tt 必然不是 ss 的异位词。
代码
1.最大子序和
class Solution: def maxSubArray(self, nums: List[int]) -> int: temp = nums[0] max1 = temp for i in range(1,len(nums)): if temp + nums[i]> nums[i]: max1 = max(max1,temp+nums[i]) temp = temp + nums[i] else : max1= max(max1,nums[i],temp,temp +nums[i]) temp = nums[i] return max1
2.搜索插入位置
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: for index,i in enumerate(nums): if i >= target: return index else: return len(nums)
3.检测大写字母
class Solution: def detectCapitalUse(self, word: str) -> bool: return word.islower() or word.isupper() or word.istitle()
4.最后一个单词长度
class Solution: def lengthOfLastWord(self, s: str) -> int: list1 = [] string = '' for i in s: if i!=' ': string = string + i elif i == ' ': if string != '': list1.append(string) string = '' if string != '': list1.append(string) return len(list1[-1])
5.搜索二维矩阵
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: x = 0 y = len(matrix[0])-1 while x<=len(matrix) -1 and y>=0: t = matrix[x][y] if target >t: x += 1 elif target < t: y -= 1 else : return True return False
6.有效的字母异位词
class Solution(object): def isAnagram(self, s, t): """ :type s: str :type t: str :rtype: bool """ dic1={c:s.count(c) for c in set(s)} dic2={d:t.count(d) for d in set(t)} if dic1==dic2: return True else:return False
