力扣<py>

977.有序数的平方

1. 使用python推导式+内置sort函数
   表达式:[表达式 for 变量 in 列表] or [表达式 for 变量 in 列表 条件] 使用推导式计算平方后的数据，再调用sort()方法完成排序

   class Solution:
       def sortedSquares(self, nums: List[int]) -> List[int]:
           res=[num**2 for num in nums]
           res.sort()
           return res

2. 采用快排超出时间限制

   class Solution:
   def Partion(self,res,low,high):
       i=(low - 1)
       pivot=res[high]
       for j in range(low,high):
           if res[j]<=pivot:
               i=i+1
               res[i],res[j]=res[j],res[i] # 小于pivot的往后移动
       res[i+1],res[high]=res[high],res[i+1] #把pivot放入合适位置
       return (i+1)
   def Qsort(self,res,low,high):
       if low <high :
           pi = self.Partion(res,low,high)
           self.Qsort(res,low,pi-1)
           self.Qsort(res,pi+1,high)
   def sortedSquares(self, nums: List[int]) -> List[int]:
       res=[num**2 for num in nums]
       self.Qsort(res,0,len(nums)-1)
       return res

3. 双指针
   采用双指针，left和right。先建立一个新的数组其值是nums数组平方后的，然后left指向第一个，right指向最后一个，在定义s为新指针，从当left<=right时，双向遍历，并将其值大的一个放入原数组nums的最后，当一次遍历完时，nums数组也完成了从小到大的排序。

   class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        res=[num**2 for num in nums]
        left=0
        right=len(nums)-1
        s=right #s是新指针，从后往前排
        # 大的往后排
        while left<=right:
            if res[left]<=res[right]:
                nums[s]=res[right]
                s-=1
                right-=1
            else:
                nums[s]=res[left]
                s-=1
                left+=1
        return nums

27.移除元素

1. 一次遍历把不等于val的值放入数组中

   class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if (nums == None and len(nums)==0):
            return 0
        s=0 # s的值代表数组的下标
        for f in range(0,len(nums)):
            if (nums[f]!=val):
                nums[s]=nums[f]
                s+=1
        return s

59.螺旋矩阵||

1. 采用四个循环每次循环解决一个方向
   初始化数组后先从左边开始解决，矩阵是n*n的大小，将矩阵第一个默认设置为1，设置一个变量cnt=2，从第二个开始依次填充，当下一位位置未被填充时填充cnt，当左边达到边界并且下一个是未被填充时，开始像下填充，同理，当向下填充达到边界且下一个未被填充后向左，再向上，当cnt==n^2时完成螺旋矩阵

   class Solution:
   def generateMatrix(self, n: int) -> List[List[int]]:
       nums = [[0] * n for _ in range(n)] # 初始化数组 n行n列
       i=0
       j=0
       cnt = 2
       nums[0][0]=1
       while cnt <= n*n:
           # left
           while j<n-1 and nums[i][j+1]==0:
               j +=1
               nums[i][j]=cnt
               cnt +=1
           # down
           while i<n-1 and nums[i+1][j]==0:
               i+=1
               nums[i][j]=cnt
               cnt+=1
           # left
           while j>0 and nums[i][j-1]==0:
               j-=1
               nums[i][j]=cnt
               cnt +=1
           # up
           while i>0 and nums[i-1][j]==0:
               i-=1
               nums[i][j]=cnt
               cnt +=1
       return nums

1.两数之和

1. 双重循环
   利用两个for循环完成查找

   class Solution:
   def twoSum(self, nums: List[int], target: int) -> List[int]:
       ans=[0] *2 
       for i in range(len(nums)):
           for j in range(i + 1, len(nums)):
               # 如果两个数相加等于target记录其下标
                if nums[i] + nums[j] == target:
                   ans[0] = i
                   ans[1] = j
       return ans

2. 字典+枚举
   从评论区看到的方法，利用字典的键值配对，和target0-val来找另一个val的方式，很巧妙
   字典+枚举的方式可以优化算法使得时间复杂度＜o(n^2)
   先使用dict()函数创建一个空的records字典，然后再用enumerate()函数将nums变成枚举类型，遍历nums，判断target - val是否在字典records里面(若数组中有两个数val加起来等于target，那么target-val的值也一定在数组中)，若不在则将val和其下标index记录字典，若在字典中则返回target-val值的下标和val的下标，即为所求，代码如下：

   class Solution:
   def twoSum(self, nums: List[int], target: int) -> List[int]:
       records=dict()
       for index,val in enumerate(nums):
           if target - val not in records:
               records[val]=index # 记录当前val的索引值到字典中
           else: 
               return [records[target-val],index]

3. 重新排序+双指针
   利用sorted()函数将数组重新排序，注意:不能直接排序nums数组，这这样会改变其原有的索引值，可以用下面两种方法来排序:1.利用numerate()函数将nums转换成元组，按照值来排序，这样不会改变其原有元素的索引值。2.直接排序原数组的下标，将待排序的数组利用range(len(nums))生产一个0~len(nums)-1的序列，按照nums数组的值来进行排序，这样就能得到一个按照值来排序的索引数组。排好序后，利用双指针head和tail一个从前往后一个从后往前，依次遍历判断和与target的关系，两种方式的代码如下:
   第一种：

   class Solution:
   def twoSum(self, nums: List[int], target: int) -> List[int]:
       sorted_list = sorted(enumerate(nums),key=lambda x: x[1]) # 排好序的元组
       head = 0
       tail = len(nums) - 1
       res = sorted_list[head][1] + sorted_list[tail][1] #用来判断与target的关系
       while res != target:
           if res > target: # 和比target大说明tail的值大了，tail向前移动
               tail -= 1
           if res < target: # 和比target小说明head的值小了，head向后移动
               head += 1
           res = sorted_list[head][1] + sorted_list[tail][1] # 每次移动完成后更新res
       return [sorted_list[head][0], sorted_list[tail][0]]

   第二种:

   class Solution:
   def twoSum(self, nums: List[int], target: int) -> List[int]:
       sorted_index=sorted(range(len(nums)),key = lambda x:nums[x]) # 排序nums，返回的索引序列
       head = 0
       tail = len(nums) - 1
       res = nums[sorted_index[head]] + nums[sorted_index[tail]] # sorted_index[head]其值对于nums索引位置
       while res != target:
           if res > target:
               tail  -= 1
           if res < target:
               head += 1
           res = nums[sorted_index[head]] + nums[sorted_index[tail]]
       return [sorted_index[head],sorted_index[tail]]

34.在排序数组中寻找元素的第一个和最后一个位置

1. 类二分查找
   类似于二分查找，找到第一个等于target的位置，记录后，再继续找到大于target的第一个位置记录，则这区间为所求，关键在于:边界控制条件。
   由于边界控制不好，导致代码无法运行，看了评论区代码后，依照写了两个函数searchleft和searchright分别查找左边界和有边界；后面看到另一位大神的代码后，发现可以更加简洁，只需一个函数searchleft找到左边界后，右边界依旧使用searchleft，查找值为target+1找到后再将结果-1这样就找到了target的右边界，非常巧妙！

   class Solution:
   def searchRange(self, nums: List[int], target: int) -> List[int]:
       # 找到左边界
       def SearchLeft(nums,target):
           low=0
           high=len(nums)-1
           while low<=high:
               mid = (low+high)//2
               # 判断条件必须加等号，防止漏掉元素
               if nums[mid]>=target:
                   high=mid-1
               else:
                   low=mid+1
           return low
       # 找右边界
       # def SearchRight(nums,target):
       #     low=0
       #     high=len(nums)-1
       #     while low<=high:
       #         mid = (low+high)//2
       #         if nums[mid]>target:
       #             high=mid-1
       #         else:
       #             low=mid+1
       #     return high
       # leftindex=SearchLeft(nums,target)
       # rightindex=SearchRight(nums,target)
       # searchleft找到的是第一个>target+1的数，数组是有序的；-1后即为target的右边界值
       leftindex=SearchLeft(nums,target)
       rightindex = SearchLeft(nums,target+1)-1
       if leftindex<=rightindex:
           return [leftindex,rightindex]
       else:
           return [-1,-1]

242.有效字母的异位词

1. 用数组记录出现字符串的个数，在比较数组
   定义一个数组arr初始化为0.用来记录s中字符出现的个数，利用ord()函数，将s中每个字符转换为Unicode值，再在数组相应位置+1操作，遍历s，这样就记录了s中所有字符出现的个数。同样再遍历t，不过这次数组再相应位置进行-1操作，如果两个字符串所含字符个数是相等的，那么arr数组应该为0，若不为0则不等，代码:

   class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # 判断s 和 t 的长度是否相等
        if (len(s)==len(t)):
            arr = [0] * 26 # 初始化数组用来记录 s 中出现字符的个数
            for i in s:
                arr[ord(i)-ord('a')]+=1
            for j in t:
                arr[ord(j)-ord('a')]-=1 # 若出现相同的字符贼减一
            # 判断arr数组是否为空
            for i in range(26):
                if arr[i]!=0:
                    return False
            return True
        else:
            return False

2. defaultdict
   defaultdict是python中的一个内置字典子类，重载了一个方法来实现默认值的设定。在创建defaultdict对象，需要提供一个参数作为默认值或者一个函数用来生成默认值。

   class Solution:
   def isAnagram(self, s: str, t: str) -> bool:
       from collections import defaultdict
       sdict=defaultdict(int)
       tdict=defaultdict(int)
       for i in s:
           sdict[i]+=1
       for j in t:
           tdict[j]+=1
       if sdict==tdict:
           return True
       else:
           return False

202.快乐数

1. 转为字符串计算平方，然后判断是否循环
   我一开始是想先把给的数字每次队10取余然后平方加起来，后面发现python可以更简单的实现这一步，就是把给的n转化为字符串然后遍历字符串将每次遍历的字符转换为int在平方相加，然后再定义一个列表，大小为n，将每次替换后的结果存入这个列表中，若此后的遍历出现了和列表中一样的数，那么这个数就不是快乐数，若循坏到1则为快乐数，代码如下:

   class Solution:
       def Caculate_Pow(self,num:int) -> int:
           n = 0 #用来返回的值
           # 将n变为字符串遍历再变为int求平方和
           for i in str(num):
               n += int(i)**2
           return n
       def isHappy(self,n:int) -> bool:
           ret = [n] #设置一个n大小的列表用来判断是否出现了循环
           while n!=1:
               n=Caculate_Pow(n)
               if n in ret:
                   return False
               else:
                   ret.append(n) # 若未出现再ret中且不等于1时，将其加入到ret中
           return True

454. 四数相加 II

1. 哈希表+分治
   这题没思路，做不出，听了老师的讲解，由题所给条件nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 –> nums1[i] + nums2[j] = - nums3[k] - nums4[j] 所以我们可以分别处理nums1 2 和nums3 4 并且定义两个字典dic_A 和 dic_B 分别记录两个数组组合的值和次数。再判断dic_A和中与dic_B相同的值，并且将两者出现的次数相乘，因为是组合问题所以应该是相乘而不是相加代码示例如下:

   class Solution:
   def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
       dic_A = {}
       dic_B = {}
       res = 0
       # 先求两个的交集
       #nums1[i] + nums2[j]  == - nums3[k] - nums4[l]
       for i in nums1:
           for j in nums2:
               sum_ij = i + j
               dic_A[sum_ij] = dic_A.get(sum_ij,0) + 1 # 记录sum_ij出现的次数
       
       for k in nums3:
           for l in nums4:
               sum_kl = -k-l
               dic_B[sum_kl] = dic_B.get(sum_kl,0) + 1
       
       # 如果dic_A和dic_B有交集，他们次数乘积累加后为所求，注意这是组合问题，不能相加
       for item in dic_A.items():
           if item[0] in dic_B:
               res += item[1] * dic_B[item[0]]
       return res

344. 反转字符串

1. 双指针原地逆转
   设置双指针i,j一个指向头部，一个指向尾部，再用tmp当中间变量交换，当i>=j时完成交换。

   class Solution:
   def reverseString(self, s: List[str]) -> None:
       """
       Do not return anything, modify s in-place instead.
       """
       i = 0
       j = len(s) - 1
       while i<=j:
           tmp = s[j]
           s[j] = s[i]
           s[i] = tmp
           i += 1
           j -= 1

876. 链表的中间结点

1. 快慢指针
   设置快慢指针，慢的为slow，快的为fast，慢的一次走一步，快的一次走两步，当fast走到末尾时，slow处于中间位置

   # Definition for singly-linked list.
   # class ListNode:
   #     def __init__(self, val=0, next=None):
   #         self.val = val
   #         self.next = next
   class Solution:
       def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
           if head == None:
               return None
           slow = head
           fast = head
           while fast and fast.next:
               slow = slow.next
               fast = fast.next.next
           return slow

206.反转链表

1. 双指针+临时变量记录
   我这里是重新返回了一个新的链表，按照头插法遍历原链表，就完成了链表的反转

   # Definition for singly-linked list.
   # class ListNode:
   #     def __init__(self, val=0, next=None):
   #         self.val = val
   #         self.next = next
   class Solution:
       def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
           # 链表为空直接返回
           if head == None:
               return head
           # i指针遍历head链表
           i = head
           NewNode = None
           # j指针指向新的链表
           j = NewNode
           # 头插法实现逆转
           while i!= None:
               tmp = i.next
               i.next = j
               j = i
               i = tmp
           return j
           

160. 相交链表

1. 先判断长度，然后从位置相同的结点同时遍历，找相同的结点
   先计算后两个链表的长度，然后利用一个变量计算差值，让长的那个链表与短的那个链表同时向后遍历，找到相同的结点

   # Definition for singly-linked list.
   # class ListNode:
   #     def __init__(self, x):
   #         self.val = x
   #         self.next = None
   
   class Solution:
       # 计算链表的长度
       def get_length(self,head:ListNode) -> int:
           count = 0
           i = head
           while i:
               count += 1
               i = i.next
           return count
       def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
           m = self.get_length(headA)
           n = self.get_length(headB)
           node_headA = headA
           node_headB = headB
           判断哪个链表长，记录差值，然后让长的链表先走，保证两个链表能在同一个位置向后遍历
           if m > n:
               cha = m - n
               i_headA = 0
               while i_headA < cha:
                   node_headA=node_headA.next
                   i_headA += 1
           else:
               cha = n - m
               i_headB = 0
               while i_headB < cha:
                   node_headB=node_headB.next
                   i_headB += 1
           # 如果遍历到相同的结点返回
           while node_headA and node_headB:
               if node_headA == node_headB:
                   return node_headA
               node_headA = node_headA.next
               node_headB = node_headB.next
           return None

20.有效的括号

一开始我是想记录每个字符出现的次数然后判断是否为奇数，当然通过不来，因为没要考虑到顺序问题，”([)]”这个测试用例就会失败

1. 使用replace()替换字符
   设置判断条件，遇到’{}’,’[]’,’()’,直接替换为空字符

   class Solution:
   def isValid(self, s: str) -> bool:
       while '{}' in s or '()' in s or '[]' in s:
           s=s.replace('{}','')
           s=s.replace('[]','')
           s=s.replace('()','')
       return s==''

2. 哈希+栈
   K神解答;先创建一个包含所需字符的字典dic，然后再定义一个stack数组用来模拟栈操作，遍历s看字符是否存在于dic中，若存在入栈(查找左括号的过程),当遍历到不是左括号的时候出栈，看出栈的元素与当前元素是否匹配，若不匹配直接返回False，需要注意的是，stack初始时应该添加一个变量进去，同理在dic中添加一个不属于s的字符，最后判断stack长度为1时，返回True

   class Solution:
   def isValid(self, s: str) -> bool:
       dic = {'[':']','(':')','{':'}','a':'a'}
       stack = ['a']
       for i in s:
           if i in dic:
               stack.append(i)
           elif dic[stack.pop()] != i:
               return False
       return len(stack) == 1

496. 下一个更大元素 I

1. 由题可知nums2包含了nums1，因此可以用index查找nums1中数在nums2中的下标，然后再判断从该处起是否有大于nums1的数，若有则赋值到nums1的相应位置，若没有则将nums1相应位置设置为-1

   class Solution:
   def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
       for i in range(len(nums1)):
           index = nums2.index(nums1[i]) + 1 # 查找nums1中的值再nums2中的位置，加一代表下一位
           flag = 0 # flag用来判断nums2中是否有符合条件的数
           while index < len(nums2):
               if nums2[index] > nums1[i]: # nums2的右边有大于nums1的数
                   nums1[i] = nums2[index] # 将第一个大于的数赋值到nums1相应的位置
                   flag = 1
                   break
               index += 1
           if flag == 0:
               nums1[i] = -1
       return nums1

2. 字典+双循环(同学解答)
   其实这种方式和我自己用index方式找下标本质上是一样的，不过这是用到了双循环，从nums2中去找第一个大于nums当前位置上的数。具体实现是:

   1.先初始化结果数组为-1 长度为nums1的长度
   2.然后将nums2中的数字和下标存入到字典当中
   3.遍历nums1，同时遍历nums2从nums1当前值在nums2中的下标开始往后找，若找到一个比nums1此时位置上的数大的数后将其赋值到结果数组

   class Solution:
   def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
       ans = [-1] * len(nums1)
       dic = {}
       # 将nums2的数字和下标存入字典
       for item in range(len(nums2)):
           dic[nums2[item]] = item
       # 遍历nums1 在nnums2中从nums1当前数字的下标往后找若有大于nums1的就赋值放入ans中
       for i in range(len(nums1)):
           for j in range(dic[nums1[i]],len(nums2)):
               if nums2[j] > nums1[i]:
                   ans[i] = nums2[j]
                   break # 找到一个就结束当前循环
       return ans

3. 字典+栈(同学解答)
   这个方法采用的是将nums2中存在后一个数大于前一个数的存入到字典中，key为待查找数，value为向后第一个大于key的数。当遍历完nums2后，从nums1开始遍历，并查找dic中是否存在该数，存在将其放到待放回数组中，具体代码实现:

   class Solution:
   def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
       stack = []
       dic = {}
       res = []
       for i in range(len(nums2)):
           # 当栈不为空，并且nums2[i]大于栈顶元素时，更新字典
           while stack and stack[-1]<nums2[i]:
               dic[stack.pop()] = nums2[i]
           stack.append(nums2[i]) # 更新栈顶、
       # 在nums2中查找nums1
       for i in nums1:
           res.append(dic.get(i,-1))
       return res

150. 逆波兰表达式求值

1. 使用栈来计算
   定义一个栈，设置条件判断，是运算符号就出栈，计算后后再入栈，这里注意的是在计算正数与负数相除时，要使用int进行取整，不能用 // 进行整除。再进行减法和除法运算时要先用一个临时变量记录出栈的数据，再用用出栈的数减去或者除以这个临时变量，遍历tokens计算得到最后的结果

   class Solution:
   def evalRPN(self, tokens: List[str]) -> int:
       if len(tokens) == 1:
           return int(tokens[0])
       stack = []
       res = 0
       for i in tokens:
           if i != '+' and i != '-' and i != '/' and i != '*':
               stack.append(int(i))
           elif i == '+':
               res = stack.pop() + stack.pop()
               stack.append(res)
           elif i == '-':
               temp = stack.pop() # 减数
               res = stack.pop() - temp
               stack.append(res)
           elif i == '*':
               res = stack.pop() * stack.pop()
               stack.append(res)
           elif i == '/':
               tmp = stack.pop() # 除数
               res = int(stack.pop()/tmp)
               stack.append(res)
       return res

2. LC官方解答(栈)

   class Solution:
       def evalRPN(self, tokens: List[str]) -> int:
           op_to_binary_fn = {
               "+":add,
               "-":sub,
               "*":mul,
               "/":lambda x,y:int(x/y),
           }
           stack = list() # 定义栈
           for token in tokens:
               try:
                   num = int(token) # 不是操作符
               except ValueError: # 遇到操作符执行相应的操作
                   num2 = stack.pop()
                   num1 = stack.pop()
                   num = op_to_binary_fn[token](num1,num2) # 注意num1和mum2的位置，先出栈的作为除数
               finally:
                   stack.append(num)
           return stack[0] # 最后的运算结果

347. 前 K 个高频元素

1. 排序+字典
   先将原数组排好序，再统计每个数字出现的次并将其存入到字典dict_nums中，再将dict_nums按照出现的次数来进行排序，最后将前k个赋值到list_r中即可

   代码如下

   class Solution:
   def topKFrequent(self, nums: List[int], k: int) -> List[int]:
       # 用来返回结果的列表
       list_r = []
       # 存放每个数字及出现的次数
       dict_nums = {}
       # 记录每个数字出现的次数
       cnt = 0
       # 先排序
       nums = sorted(nums)
       # 将每个数字出现的次数记录到dict_nums
       tmp = nums[0]
       i = 0
       while i < len(nums):
           if nums[i] == tmp:
               cnt += 1
           if nums[i] != tmp:
               dict_nums[nums[i - 1]] = cnt
               cnt = 1
               tmp = nums[i]
           i += 1
       i = 0
       # 记录最后一个数字的出现次数
       dict_nums[nums[len(nums) - 1]] = cnt
       # 如果原数组不止一个数的话，按照值的大小来排序字典
       if len(dict_nums) > 1:
           new_dict = sorted(dict_nums.items(), key=lambda x: x[1],reverse=True)
           new_dict = dict(new_dict)
       else:
           new_dict = dict_nums
       # 将原数组中出现次数前k的赋值到list_r
       for key, val in new_dict.items():
           if i < k:
               list_r.append(int(key))
               i += 1
       return list_r

   简洁版代码

   class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic = {}
        for i in nums:
            dic[i] = dic.get(i,0) + 1
        return([i for i,j in sorted(dic.items(),key=lambda x:x[1],reverse=True)][0:k])

2. 字典+堆
   先用字典记录每个数字及其出现次数，在将其出现次数都*-1，然后根据次数来建立小根堆，遍历小根堆，则为前k个高频元素

   代码如下

   class Solution:
   def topKFrequent(self, nums: List[int], k: int) -> List[int]:
       dic = {}
       res = [] # 用来返回结果
       heap = [] # 建立小根堆
       # 记录每个数字及其出现次数
       for i in nums:
           dic[i] = dic.get(i,0) + 1
       # 将其转换成列表，并且将键值反转，并且-1*出现次数，以便后面建立小根堆
       ls = [(-1 * value,key) for key,value in dic.items()]
       # 建立小根堆
       heapq.heapify(ls)
       for i in range(k):
           res.append(heapq.heappop(ls)[1])
       return res

278. 第一个错误的版本

1. 二分查找
   如果直接用for循环进行遍历的话，会超出时间复杂度，所以这里可以选择采用二分查找的方式，时间复杂度为O(log n),不过针对这个题目，不能直接套用二分查找，应作相应的改变，最后返回的值不是mid而是first，因为可能不止一个错误的版本，而题目要求返回第一个错误的版本，所以当isBadVersion(mid)为True时last = mid - 1查找左半部分是否还存在错误版本，反之则first = mid + 1,当first>last时，first的位置就为第一个错误版本

   # The isBadVersion API is already defined for you.
   # def isBadVersion(version: int) -> bool:
   
   class Solution:
       def firstBadVersion(self, n: int) -> int:
           first = 1
           last = n
           while first <= last:
               mid = (first + last) // 2
               if isBadVersion(mid):
                   last = mid -1 # 查找左半部分是否还存在错误版本
               else:
                   first = mid + 1
           return first # 当first>last时first所在位置就是首个错误版本

704. 二分查找

1. 二分查找
   非常典型的二分查找题目，直接使用二分查找的相关代码即可

   class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) - 1
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                high = mid -1
            else:
                low = mid + 1
        # 不存在返回-1
        return -1

240.搜索二维矩阵 II

1. 暴力二分法
   整个二维矩阵又可以看成是m个含有n个元素的一维数组组成，因此可以遍历真个m个数组，在遍历每一个数组的时候采用二分查找减少时间消耗，这样的时间复杂度为mlogn

   class Solution:
   # 二分查找
   def func(self,nums,target):
       low = 0 # 首
       high = len(nums) - 1 # 尾
       while low <= high:
           mid = (low + high ) // 2
           if nums[mid] == target:
               return True
           elif nums[mid] > target:
               high = mid - 1
           else:
               low = mid + 1
       return False
   def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
       m = len(matrix) # 行数，表示又多少个一维数组
       n = len(matrix[0]) # 列数，表示每个一维数组中所含元素的个数
       # 遍历每个一个一维数组使用二分查找去查找
       for i in range(m):
           if self.func(matrix[i],target):
               return True
       return False

2. 分治法
   整个二维数组左下角的第一个数是第一列的最大数，是最后一行的最小数；因此可以从左下角开始向上，右遍历；从右上角也是一样的，但是不能从另外两个角去遍历，因为数组的增大方向是从上到小，从左到右，不管先遍历哪个方向，当遇到大于或者小于target时，另一个方向去遍历时，下一个数依旧是大于或者小于target，因为在增大方向上下一个数必定是比前一个数大的，因此可以选择从左下角或者右上角遍历；这里拿左下角举例:如果左下角第一个数大于target那么就像上遍历，当上方向上的数小于target时，就想右遍历，若右方向的数大于target的话，再在此基础上向上遍历，直至找到target，若不存在target则直接返回False
   时间复杂度O(m+n)

   class Solution:
   def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
       m = len(matrix) # 行
       n = len(matrix[0]) # 列
       # 行列为空的话直接返回false
       if m == 0:
           return False
       if n == 0:
           return False
       # i 代表上下方向，j代表左右方向
       i = m - 1 
       j = 0
       while i>=0 and j < n:
           if matrix[i][j] == target:
               return True
           # 小于target时向右移动，否则向上移动
           elif matrix[i][j] < target:
               j = j + 1
          else:
               i = i - 1
       return False

275. H 指数 II

1. 二分法，关键是返回的区间
   理解好题目后才好下手,要理解h 指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次；题目的意思是返回满足条件的个数不是刚好满足条件的那个个论文引用次数，是所有大于这个条件的个数，比如[1,2]那么返回的就是1，引用次数大于2的为0，大于1的为1，又比如[0,1,3,5,6,8,9]返回的就是4，表示至少有四篇论文引用次数大于4其余的论文引用次数小于4。所以就可以用二分法的变式来解决该问题，时间复杂度为logn

   class Solution:
       def hIndex(self, citations: List[int]) -> int:
           low = 0
           high = len(citations) - 1
           while low <= high:
               mid = (low + high) // 2
               # 判断当前论文引用次数是否大于当前引用次数论文的个数
               if citations[mid] >= len(citations) - mid:
                   high = mid - 1
               else:
                   low =  mid + 1
           # 当循环结束时low位置所指向的值的下一个就是第一个满足的值，因此用数组长度-当前low值就是所有满足的个数
           return len(citations) - low

2. 逆转数组后一次遍历
   逆转数组后通过比较元素的索引和值来确定h值，逆转数组为了方便计算，i+1是因为要比较引用次数而索引下标是从0开始所以用i+1,然后从头开始遍历

   class Solution:
       def hIndex(self, citations: List[int]) -> int:
           # 反转
           citations = citations[::-1]
           length = len(citations)
           index = 0
           for i in range(length):
               if citations[i] >= i+1:
                   index = i+1
           return index

81. 搜索旋转排序数组 II

1. 直接遍历数组找target
   时间复杂度O(n),用for循环遍历数组看target是否在其中

      class Solution:
       def search(self, nums: List[int], target: int) -> bool:
           for i in range(len(nums)):
               if nums[i] == target:
                   return True
           return False
      ```  
   
   2. 二分查找(官方解答)
      由于数组中元素是可以有重复的，因此可能会出现`nums[left]=nums[mid]=nums[right]`的情况，对于这种情况，对区间的左边界减一，右边界加一来进行新的二分查找
   
      ```python
       class Solution:
       def search(self,nums,target):
           # 数组为空时，直接返回False
           if len(nums)==0:
               return False
           # 数组进一个元素时，直接判断
           if len(nums)==1:
               return True if nums[0]==target else False
           left,right=0,len(nums)-1
           while left<=right:
               mid=(left+right)//2
               if nums[mid]==target:
                   return True
               # 划分数组,并判断
               # 左边界的值=中间位置值=右边界的值时，构建新数组
               if nums[left]==nums[mid]==nums[right]:
                   left+=1
                   right-=1
               elif nums[left]<=nums[mid]:
                   # 左边的数组是有序数组，且target存在于区间内，则移动右指针；否则，移动左指针
                   if nums[left]<=target<=nums[mid]:
                       right=mid-1
                   else:
                       left=mid+1
               else:
                   # 右边的数组是有序数组，且target存在于区间内，则移动左指针；否则，移动否指针
                   if nums[mid]<target<=nums[len(nums)-1]:
                       left=mid+1
                   else:
                       right=mid-1
           return False

53. 最大子数组和

1. 贪心算法
   刚开始我是用的双循环去统计最大和，但是会超出时间复杂度，贪心算法的思想是:在每一步选择中都采用当前状态下最优的选择，而不考虑之后的结果,定义一个sum用来记录当前值与当前值和下一个数相加的大小，返回值大的那个给sum,这个sum就是前几项的和最大值，然后再将sum与待返回的数res做比较将值的那个赋值给res。

   class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            if not nums:
                return NULL
            res = sum = nums[0]
            for i in range(1,len(nums)):
                sum = max(nums[i],sum+nums[i]) # 更新前i个数中的最大和
                res = max(sum,res) # 更新最大和
            return res

2. 动态规划
   动态规划是一种解决复杂问题的算法思想，通常用于解决具有重叠子问题和最优子结构的问题。基本思想是将问题分解为更小的子问题，通过解决子问题来解决原始问题；将原数组在遍历时如果前一个数大于0则加到这个数上小于0则不变，最后遍历数组找出最大那个即可

   class Solution:
       def maxSubArray(self, nums: List[int]) -> int:
           n = len(nums)
           for i in range(1,n):
               if nums[i-1] > 0:
                   nums[i] += nums[i-1]
           return max(nums)

1480. 一维数组的动态和

1. 后一个加上前一个的累加，动态规划

   class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        for i in range(1,len(nums)):
            nums[i] = nums[i] + nums[i-1]
        return nums

1991. 找到数组的中间位置

1. 动态规划
   用right_sum记录数组的和，然后再遍历数组，遍历一个减去一个，用left_sum记录遍历数组的和，当左等于右时，即为中间位置

   class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        left_sum,right_sum = 0,sum(nums)
        for i in range(len(nums)):
            right_sum -= nums[i]
            if left_sum == right_sum:
                return i
            left_sum += nums[i]
        return -1

560. 和为 K 的子数组

1. 使用字典(看评论区大神解决思想)
   可以使用一个字典dic来记录数组的前缀和的个数,用变量sums记录前i个数的前缀和,存入字典当中,再定义变量res用来返回和为k的连续子数组个数，注意的是dic字典需要初始为{0:1},代表连续子数组本身，代码如下:

   class Solution:
    def subarraySum(self,nums:List[int],k:int) -> int:
        res = sums = 0
        dic = {0:1}
        for i in range(len(nums)):
            sums += nums[i]
            res += dic.get(sums - k,0) # sums - k 表示前i项和减去k的结果若存在再dic中，则说明前i项和中包含和为k的连续子数组，个数为sums - k 的值再dic中的次数
            dic[sums] = dic.get(sums,0) + 1 # 记录每个前缀和出现的次数
        return res

739. 每日温度

1. 双循环暴力解(超出时间限制)
   使用两个for循环暴力求解，时间复杂度为O(n^2),核心思想就是在第二个for循环中去找下一个比当前值大的那个，使其下标相减即为相差的天数

   class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0 for _ in range(len(temperatures))]
        for i in range(len(temperatures)):
            for j in range(i+1,len(temperatures)):
                if temperatures[j] > temperatures[i]:
                    answer[i] = j - i
                    break
        return answer

2. 单调栈(评论区解答)
   创建个栈，用来判断温度的高低，栈中存放的是元素的下标，遍历原数组，若此时遍历元素大于栈中的元素，则栈中元素出栈，并记录，再用当前元素下标值减去出栈元素的值，然后放入结果数组ans的相应位置，若小于的情况下直接入栈。具体代码如下:

   class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = [] # 存放元素的下标值
        res = [0 for _ in range(len(temperatures))] # 初始化结果数组
        for i in range(len(temperatures)):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                tmp = stack.pop()
                res[tmp] = i - tmp
            stack.append(i)
        return res

503. 下一个更大元素 II

1. 单调栈
   由于给定的是循环数组，那么在进行查找下个更大元素时，可以定义一个新的数组new_nums其大小为nums + nums形成一个循环数组，然后在同样的定义一个栈，用来判断元素的大小，栈中的存入的元素为数组的下标值，小于入栈，大于出栈，再把相应的值赋值给结果数组ans即可。注意的是最后只返回ans数组的len(nums)大小，而不是返回新数组的长度大小。代码如下:

   class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        new_nums = nums + nums # 新数组
        stack = []
        ans = [-1 for _ in range(len(new_nums))] # 初始化结果数组
        for i in range(len(new_nums)):
            while stack and new_nums[i] > new_nums[stack[-1]]: # 判断元素的大小
                tmp = stack.pop()
                ans[tmp] = new_nums[i] # 存放的元素为上一个最大的元素
            stack.append(i)
        return ans[0:len(nums)] # 注意返回的长度

2. 使用取余优化操作(评论区大神)
   再判断数组值的大小的时候用i%len(nums)来判断，就可以减少结果数组占用的空间，防止操作过程中，数组溢出。

   class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        N = len(nums)
        res = [-1] * N # 初始化结果数组
        stack = []
        for i in range(N * 2):
            while stack and nums[stack[-1]] < nums[i%N]: # 这个取余没想到，刚好满足数组长度的大小，不会造成溢出
                res[stack.pop()] = nums[i%N]
            stack.append(i%N)
        return res

42.接雨水

1. 左右向最高点遍历(评论区大神思想)
   总体思路是先找出数列中最高点的值和位置，若有多个相同最高点任取其一即可，在定义变量left_max记录左边的最高点，从左开始向数列最高点处遍历，若当前值大于left_max则更新left_max若小于这储水量res=left_max - height[i]。遍历完左边走再将left_max初始化为0，再从右边向最高点遍历，最后返回res

   class Solution:
    def trap(self, height: List[int]) -> int:
        left_max = 0 # 左最高点
        max_high = max(height) # 最高点
        max_index = height.index(max_high) # 最高点下标
        res = 0
        # 从左向最高点遍历
        for i in range(max_index):
            if height[i] >= left_max:
                left_max = height[i] # 更新左最高
            else:
                res += left_max - height[i]
        left_max = 0
        # 从右向最搞点遍历
        for j in range(len(height)-1,max_index,-1):
            if height[j] >= left_max:
                left_max = height[j]
            else:
                res += left_max - height[j]
        return res

2. 单调栈
   使用单调栈求解，横向求储水高度，首先定义栈stack并先存入第一个元素,(注意栈中存放的数组的下标值),再从第一号元素开始遍历数组，若小于或者等于栈中的元素则入栈，保持递增栈的状态，若大于则说明存在空隙，出栈并使用变量mid记录当前的栈顶元素，再比较当前元素与栈顶元素的大小，取最小的减去mid位置的值，得到雨水的高度，再使用当前变量i减去栈顶元素的值，再减一得到当前雨水的宽度，要再减一是因为只要计算空袭位置的宽度，将宽度乘以高度即为空隙处的储水量；再使用while循环遍历这个过程，当循环结束后要把当前i值入栈；用于后续的计算；

   class Solution:
    def trap(self, height: List[int]) -> int:
        stack = [0] # 存放下标
        res = 0 # 记录储水量
        for i in range(1,len(height)):
            # 递增栈
            while stack and height[i] > height[stack[-1]]:
                mid = stack.pop()
                if stack:
                    h = min(height[i],height[stack[-1]]) - height[mid] # 计算高
                    w = i - stack[-1] -1 # 计算宽
                    res += h * w
            stack.append(i)
        return res

145. 二叉树的后序遍历

1. 递归
   在函数内部定义一个新的函数postoder用来实现递归调用，并使用res数组记录每一次递归调用的值，完成后序遍历

   # Definition for a binary tree node.
   # class TreeNode:
   #     def __init__(self, val=0, left=None, right=None):
   #         self.val = val
   #         self.left = left
   #         self.right = right
   class Solution:
       def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
           res = []
           def postorder(root):
               # 判空
               if not root:
                   return list()
               # 递归后序遍历，左右根
               postorder(root.left)
               postorder(root.right)
               res.append(root.val)
           postorder(root)
           return res

2. 迭代(知道原理写不出代码，菜！)
   借助辅助栈实现，首先先遍历到二叉树的左边第一个结点，并把从途经结点存入栈中，再判断当前结点是否存在右孩子或者是否已经遍历过，若不存在右孩子，则出栈记录该节点，并把当前root设置为None；若不为None则无法完成继续操作，因为当前结点出栈记录后，接着应该继续出栈结点，来判断改该节点的右孩子和遍历情况；若该节点有右孩子，则入栈并且将root指向它的右孩子，再接着判断其右孩子的左右孩子情况；依次迭代

   # Definition for a binary tree node.
   # class TreeNode:
   #     def __init__(self, val=0, left=None, right=None):
   #         self.val = val
   #         self.left = left
   #         self.right = right
   class Solution:
       def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
           if not root:
               return list()
           prev = None # 记录前驱
           stack = []
           res = []
           while root or stack:
               # 找到二叉树最左边的第一个元素
               while root:
                   stack.append(root)
                   root=root.left
               # 更新root的值
               root=stack.pop()
               # 判断改结点是否存在右子树或者是否已经遍历过
               if not root.right or root.right==prev:
                   res.append(root.val)
                   prev = root # 记录遍历过的元素
                   root = None # 方便继续弹出栈元素进行判断处理
               # 当前结点存在右子树
               else:
                   stack.append(root)
                   root=root.right
           return res

3. Morris遍历(大概率以后又忘了…)
   一种巧妙的方法在O(n)时间复杂度和O(1)空间复杂度情况下完成二叉树遍历，由J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出。其具体思想就是利用树的空闲指针，实现其空间开销的极限缩减(类似于线索二叉树?),其规则具体如下:

   1. 新建临时结点，root;
   2. 如果当前结点左子为空，则遍历当前结点的右子节点；
   3. 如果当前结点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱结点；
      • 如果前驱结点的右子节点为空，将前驱结点的右子节点设置为当前节点,当前节点更新为当前节点的左子节点。
      • 如果前驱节点的右子节点为当前节点，将它的右子节点重新设置为空。倒序输出从当前节点的左子节点到该前驱节点这条路径上的所有结点，当前结点更新为当前结点的右子节点。
   4. 重复步骤2和3，直到遍历结束

   # Definition for a binary tree node.
   # class TreeNode:
   #     def __init__(self, val=0, left=None, right=None):
   #         self.val = val
   #         self.left = left
   #         self.right = right
   class Solution:
       def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
           def addpath(node:TreeNode):
               count = 0
               while node:
                   count += 1
                   res.append(node.val)
                   node = node.right
               i,j = len(res) - count, len(res) - 1 # i,j 默认初始值为res的第一个和最后一个值
               # 逆置res 
               while i<j:
                   res[i],res[j] = res[j],res[i]
                   i += 1
                   j -= 1
           if not root:
               return list()
           res = list()
           p1 = root
   
           # 类似线索化二叉树，记录结点在中序遍历中的前驱位置
           while p1:
               p2=p1.left
               if p2:
                   # 找到p2的最右节点
                   while p2.right and p2.right!=p1:
                       p2 = p2.right
                   # 若p2不存在右孩子了，则将p2的右指针指向p1，p1指向其左孩子，继续循环
                   if not p2.right:
                       p2.right = p1
                       p1 = p1.left
                       continue
                   # p2 存在其右孩子 而且p2的右指针指向当前p1节点，那么将p2的右孩子重新置为空，利用addpath函数逆序记录当前节点的左子节点到其前驱节点的所有结点
                   else:
                       p2.right = None
                       addpath(p1.left)
               # 更新当前结点指向其右子节点，在其右子节点重复上述操作
               p1 = p1.right
           
           # 剩下结点为将root到最右结点的路径，逆序记录到res，即可完成后序遍历
           addpath(root)
           return res

104. 二叉树的最大深度

1. 动态规划 （参考以前提交的c++代码)
   定义left_depth和right_depth分别记录左右子树的深度，然后调用自身函数，返回左右子树深度最大的一个再加一(加上跟根节点的高度)

   # Definition for a binary tree node.
   # class TreeNode:
   #     def __init__(self, val=0, left=None, right=None):
   #         self.val = val
   #         self.left = left
   #         self.right = right
   class Solution:
       def maxDepth(self, root: Optional[TreeNode]) -> int:
           if not root:
               return 0
           left_depth = self.maxDepth(root.left)
           right_depth = self.maxDepth(root.right)
           # 加一是因为还有根节点的高度
           return max(left_depth,right_depth)+1

2. 广度优先搜索(LC官方题解)
   使用辅助队列queue将每一层的元素存入队列，在使用ans记录层数，sz记录每一层的个数，用while循环来判断，判断每一个结点是否有左右孩子，若有则入队，每判断一个元素，sz减一，当一层的元素全部判断完后，层数ans加一.

   # Definition for a binary tree node.
   # class TreeNode:
   #     def __init__(self, val=0, left=None, right=None):
   #         self.val = val
   #         self.left = left
   #         self.right = right
   class Solution:
       def maxDepth(self, root: Optional[TreeNode]) -> int:
           if not root:
               return 0
           queue=[]
           # 将根结点先入队，否则层数会少一层
           queue.append(root)
           ans = 0
           while len(queue):
               sz = len(queue) # 记录每一层的元素个数
               # 判断每一个元素是否有左右孩子，有则入队
               while sz>0:
                   Node = queue.pop(0)
                   if Node.left:
                       queue.append(Node.left)
                   if Node.right:
                       queue.append(Node.right)
                   sz -= 1
               # 每一层元素判断完毕后，层数加一
               ans += 1
           return ans