目录
前言
2021-10-25
题目
1.最大子序和
2.搜索插入位置
3.检测大写字母
4.最后一个单词长度
5.搜索二维矩阵
6.有效的字母异位词
题解
1.最大子序和
2.搜索插入位置
3.检测大写字母
4.最后一个单词长度
5.搜索二维矩阵
6.有效的字母异位词
代码
1.最大子序和
2.搜索插入位置
3.检测大写字母
4.最后一个单词长度
5.搜索二维矩阵
6.有效的字母异位词
总结
每日一语！！！
前言
紧接上一周的活动哦，大家可以看看我之前发的博客。
活动地址：https://blink.csdn.net/details/1253757?spm=1001.2014.3001.5501
2021-10-25
题目
1.最大子序和
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
总结
今天就是第三周，真的没想到能坚持这么久，而且我发现我现在也慢慢把刷题当作了一种习惯，每天都必要刷几题，我也很喜欢刷题带来的成就感，能让我得到满足感，人生何尝不是如此在一方面做成功了，也会得到一定的成就感和满足感！！！
加油！！！肝就完事！！！
每日一语！！！
- 耐心之树，结黄金之果。
- 耐心之树，结黄金之果。
