两数相加

Date: 2020-9-13 周日

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = p = ListNode(None)
        s=0
        while l1 or l2 or s:
            s +=(l1.val if l1 else 0)+(l2.val if l2 else 0)
            p.next=ListNode(s % 10)
            p= p.next
            s //= 10
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None 
        return dummy.next

采用双指针法，dummy为头指针，p为遍历指针。初始化时将dummy与p赋值为值为空的节点。s用来存储进位信息。在每次循环中，将s与l1 与 l2 的节点值相加，将s的个位数赋值为下一个节点，将s取模作为进位 供下次循环运算使用。
最后返回dummy的next，因为其本身为空节点。
因为有可能l1 、l2长度不同，所以分别需要判断。

无重复字符的最长子串*

Date: 2020-9-14 周一

暴力求解

class Solution:
    def isRepeat(self ,s:List,s_str:str) -> bool:
        if len(s)==0:
            return True
        for s_in in s:
            if s_str == s_in:
                return False
        return True
    def lengthOfLongestSubstring(self, s: str) -> int:
        length=len(s)
        i=0
        max=0
        while i<length:
            nums=[]
            j=i
            while j<length:
                if self.isRepeat(nums,s[j]):
                    nums.append(s[j])
                else:
                    break
                j+=1
            if len(nums)>max:
                max=len(nums)
            i+=1
        return max

暴力求解就是先从字符串的头开始遍历，使用双层循环。内层循环查找从头开始到尾的不连续的最大字符串。外循环则是将头缩进一个，并且将当前内循环的最大值与保存的max作比较，择大选择保存。
单纯的暴力虽然能做出来但是效率太差了。

滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left = 0
        lookup = set()
        n = len(s)
        max_len = 0
        cur_len = 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup: #在窗口中左移，直到s[i]在窗口中不重复
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len
            lookup.add(s[i])
        return max_len

寻找两个正序数组的中位数

Date: 2020-9-15 周二

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        mid=0
        nums=[]
        n1=len(nums1)-1
        n2=len(nums2)-1
        while n1>=0 and n2>=0:
            if nums1[n1]>nums2[n2]:
                nums.append(nums1[n1])
                n1-=1
            else:
                nums.append(nums2[n2])
                n2-=1
        while n1>=0:
            nums.append(nums1[n1])
            n1-=1
        while n2>=0:
            nums.append(nums2[n2])
            n2-=1
        print(nums)
        if len(nums)%2==0:
            mid=(nums[int(len(nums)/2)-1]+nums[int(len(nums)/2)])/2
        else:
            mid=nums[int(len(nums)/2)]
        return mid

思想就是先有序合并两个数组。然后直接从有序的数组中查找对应的中位数。

最长回文串*

Date: 2020-9-16 周三

暴力遍历

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length=len(s)
        if length<2:return s
        maxLen=1
        begin=0
        i=0
        #枚举所以长度严格大于1的子串
        while i<length-1:
            j=i+1
            while j<length:
                if j-i+1>maxLen and self.validPalindromic(s,i,j):
                    maxLen=j-i+1
                    begin=i
                j+=1
            i+=1
        return s[begin:begin+maxLen]
    def validPalindromic(self,s:str,left:int,right:int)->bool:
        while left<right:
            if s[left]!=s[right]:
                return False
            left+=1
            right-=1
        return True

暴力搜索匹配就是先将回文串判断函数写出。从字符串s的头部开始，判断所有子串，并且记录下是回文串的最长子串的起始位置和长度，最后通过起始位置和长度截取字符串输出。但是暴力运行效率太低，无法通过测试。

动态规划*

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = ""
        # 枚举子串的长度 l+1
        for l in range(n):
            # 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置
            for i in range(n):
                j = i + l
                if j >= len(s):
                    break
                if l == 0:
                    dp[i][j] = True
                elif l == 1:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
                if dp[i][j] and l + 1 > len(ans):
                    ans = s[i:j+1]
        return ans

中心扩展法*

class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

Z形变换

Date: 2020-9-19 周六

二维数组法

class Solution:
    def findCols(self,length:int , numRows:int):
        mid = numRows*2 - 2 #每组数据的元素个数
        cols = 0
        cols = int(length / mid) * (numRows - 1) #完整分组所占的列数
        #求不完整分组所占的列数
        if length % mid == 0: #能够整除 
            cols +=0
        else: #如果不能整除
            mid_y = length % mid
            if mid_y <= numRows:
                cols +=1
            else:
                cols += (mid_y - numRows +1)
        return cols
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        cols = self.findCols(len(s),numRows) #生成矩阵列数
        V = [["#"] * cols for _ in range(numRows)]
        index = 0
        j = 0
        while j < cols:
            if index>len(s):
                    break
            for i in range(numRows): 
                if index <len(s):
                    V[i][j] = s[index]
                    index +=1
                    if i!=0 and i!=numRows-1:
                        vi = i
                        vj = j+numRows - i -1
                        s_index = 2*vj +vi
                        if vj < cols and s_index < len(s):
                            V[vi][vj] = s[s_index]
            index +=(numRows-2)
            j +=(numRows-1)           
        ans = ""
        for i in range(numRows):
            for j in range(cols):
                if V[i][j] !="#":
                    ans +=V[i][j]
        return ans

我的思路是先生成一个合适的矩阵，在遍历这个矩阵的时候逐个往其中填入相应的字符。最后在遍历矩阵输出。
矩阵的行数由外部指定，列数则通过相应的计算公式得到。时间复杂度和空间复杂度都是n的平方。。。。

字符串转换整数

Date: 2020-9-22 周二

class Solution:
    def judeNumScope(self,num:int) ->int:
        if num>0:
            if num>=2147483648:
                return 2147483647
        elif num<0:
            if num<=-2147483648:
                return -2147483648
        return  num
    def isNumber(self,str:str) :
        return {'0':0,'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9}.get(str,-1)
    def myAtoi(self, str: str) -> int:
        #去除左边空格
        str = str.lstrip()
        if str == "":
            return 0
        symbol = "+"
        num = "#"
        if self.isNumber(str[0]) == -1 and not(str[0] == "+" or str[0] == "-"):
            return 0
        index = 0
        for s in str:
            if s == "-" or s == "+":
                if index ==0:
                    symbol = s
                else:
                    return 0      
            else:
                break
            index += 1
        str = str[index:len(str)]
        for s in str:
            if s == "-" or s == "+":
                if s != str[0]:
                    return  0 if num == "#" else self.judeNumScope(int(num))  if symbol=="+" else self.judeNumScope(-int(num))
                continue
            if self.isNumber(s) == -1:
                return  0 if num == "#" else self.judeNumScope(int(num))  if symbol=="+" else self.judeNumScope(-int(num))
            if num =="#":
                num = s
            else :
                num+=s 
        return  0 if num == "#" else self.judeNumScope(int(num)) if symbol=="+" else self.judeNumScope(-int(num))

思路很简单，就是先截取，然后用字符串保留住数值部分，最后再通过int()方法转换成数值。但是需要注意多种特殊情况，比如：”+-1” “++1” “+9999999999999”等。

正则表达式匹配**

Date: 2020-9-22 周二

别人家的思路：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        s_len = len(s)
        p_len = len(p)
        # dp[i][j] 表示 s[:i] 与 p[:j] 是否匹配，各自前 i、j 个是否匹配
        dp = [[False] * (p_len + 1) for _ in range(s_len + 1)]
        dp[0][0] = True
        #就是确定上边最后的base case的情况  s 为空串时 如果p中有*可以干掉一个字符 
        for j in range(1, p_len + 1):
            # 若 p 的第 j 个字符 p[j - 1] 是 '*'
            # 说明第 j - 1、j 位可有可无
            # 那么如果前 j - 2 个已经匹配上，前 j 个也可以匹配上
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]
        for i in range(1, s_len + 1):
            for j in range(1, p_len + 1):
                if p[j - 1] in {s[i - 1], '.'}:
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    if p[j - 2] in {s[i - 1], '.'}:
                        dp[i][j] = dp[i][j - 2] or dp[i - 1][j - 2] or dp[i - 1][j]
                    else:
                        dp[i][j] = dp[i][j - 2]
        return dp[s_len][p_len]

盛最多水的容器

Date: 2020-9-23 周四

暴力（但是会超时）

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max = 0
        for i in range(len(height)):
            for j in range(i+1,len(height)):
                num = (j - i) * (height[i] if height[i] < height[j] else height[j])
                if num > max:
                    max = num
        return max

双指针法

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max = 0
        hLen = len(height) - 1
        i = 0
        while i < hLen :
            num = (hLen - i) * min(height[i],height[hLen])
            if num > max:
                max = num
            if height[i] < height[hLen]:
                i += 1  
            else:
                 hLen -= 1
        return max

整数转罗马数字

Date: 2020-9-24 周四

逐位转换

class Solution:  
    def intToRoman(self, num: int) -> str:
        roman = ""
        numStr = str(num)
        nLen = len(numStr)
        for i in range(len(numStr)):
            numMid = 10 ** (nLen-1)
            Num = int(numStr[i]) * numMid
            sym =self.changeStr(numMid)
            if Num == 0:
                nLen -= 1
                continue
            if Num == (5 * numMid):
                roman += self.changeStr(Num)
            elif Num > (5 * numMid): #在左边拼接
                if int(numStr[i]) == 9:
                    symMid = self.changeStr(numMid*10)
                    for _ in range(10-int(numStr[i])):
                        roman += sym
                    roman +=symMid
                else:
                    symMid = symMid = self.changeStr(numMid*5)
                    roman +=symMid
                    for _ in range(int(numStr[i])-5):
                        roman += sym
                # sym =self.changeStr(numMid)
            else : #在右边
                if int(numStr[i]) == 4:
                    symMid = self.changeStr(5 * numMid)
                    for _ in range(5-int(numStr[i])):
                        roman += sym
                    roman +=symMid
                else:
                    symMid = ""    
                    for _ in range(int(numStr[i])):
                        roman += sym
            nLen -= 1
        return roman
    def changeStr(self, num:int) ->str:
        return {1:"I",5:"V",10:"X",50:"L",100:"C",500:"D",1000:"M"}.get(num,"")

三数之和

Date: 2020-9-24 周四

暴力（超时）

import numpy as np
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        list = []
        for i in range(len(nums)-2):
            for j in range(i+1 , len(nums)-1):
                for z in range(j+1 , len(nums)):
                    if (nums[i] + nums[j] + nums[z]) == 0:
                        listMid = [nums[i],nums[j],nums[z]]
                        if self.isHas(list,listMid):
                            list.append(listMid)  
        return list
    def isHas(self,list:List[List[int]],check:List[int]) -> bool:
        if len(list) == 0:
            return True 
        check = np.sort(np.array(check))
        for i in range(len(list)):
            listMid = np.sort(np.array(list[i]))
            if (listMid == check).all():
                return False
        return True

排序+双指针法*

Date: 2020-9-24 周四

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        # 枚举 a
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合，随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        return ans

最接近的三数之和

Date: 2020-9-24 周四

双指针+排序

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        min = -1
        listNum = 0
        nums.sort()
        for first in range(len(nums)):
            third = len(nums) - 1
            scecond = first + 1
            if min == 0 :
                break
            while scecond < third:
                sum = nums[first] + nums[scecond] + nums[third]
                if min == -1 or abs(sum - target) < min:
                    min = abs(sum - target)
                    listNum = sum
                if (sum - target) > 0:
                    third -= 1
                else:
                    scecond += 1            
        return listNum

电话号码的字母组合**

Date：2020-9-25 周五

回溯

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:    
        if not digits:
            return list()
        phoneMap = {"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
        def backtrack(index:int):
            if index == len(digits):
                combinations.append("".join(comination))
            else:
                digit = digits[index]
                for letter in phoneMap[digit]:
                    comination.append(letter)
                    backtrack(index+1)
                    comination.pop()
        comination = list()
        combinations = list()
        backtrack(0)
        return combinations

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:    
        if not digits:
            return list()
        phoneMap = {"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
        groups = (phoneMap[digit] for digit in digits) #生成Generator（生成器）类型
        return ["".join(combination) for combination in itertools.product(*groups)] #product 类似于求多个可迭代对象的笛卡尔积 join将list元素拼接成字符串

四数之和

Date：2020-9-25 周五

双层循环+双指针

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        numsLen = len(nums)
        result = []
        for i in range(numsLen-3):
            for j in range(i + 1,numsLen-2):
                right = numsLen - 1
                left = j + 1
                while left < right:
                    sum = nums[i] + nums[j] + nums[left] +nums[right]
                    if sum == target:
                        resultMid = [nums[i] , nums[j] , nums[left] , nums[right]]
                        if self.checkedList(result,resultMid):
                            result.append(resultMid)
                        while nums[right] == nums[right-1] and left < right:
                            right -= 1
                        while nums[left] == nums[left+1] and left < right:
                            left += 1 
                        right -= 1
                        left += 1  
                    elif sum > target:
                        right -= 1
                    else:
                        left += 1
        return result
    def checkedList(self,result:List[List[int]],check:List[int]) -> bool:
        for i in range(len(result)):
            if result[i] == check:
                return False
        return True

删除链表的倒数第N个节点

Date：2020-9-25 周五

一次遍历法（双指针）

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if head.next == None and n>=1:
            return None
        headNode = head
        endNode = headNode
        startNode = None
        for _ in range(n):
            endNode = endNode.next 
        if endNode == None and startNode == None:
            return headNode.next
        else:
            while endNode != None:
                endNode = endNode.next
                if startNode == None:
                    startNode = headNode
                else:
                    startNode = startNode.next
        startNode.next = startNode.next.next
        return headNode

合并两个有序链表

Date：2020-9-25 周五

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 == None and l2 == None:
            return l1
        elif l1 == None:
            return l2
        elif l2 == None:
            return l1
        resultListNode = None
        result = None
        l1Node = l1
        l2Node = l2
        while l1Node != None and l2Node != None:
            if l1Node.val <= l2Node.val:
                node = l1Node
                l1Node = l1Node.next
                node.next = None
                if resultListNode == None:
                    resultListNode = node
                    result = resultListNode
                else:
                    resultListNode.next = node
                    resultListNode = resultListNode.next
            else:
                node = l2Node
                l2Node = l2Node.next
                node.next = None
                if resultListNode == None:
                    resultListNode = node
                    result = resultListNode
                else:
                    resultListNode.next = node
                    resultListNode = resultListNode.next
        if l1Node!=None:
            if resultListNode == None:
                resultListNode = l1Node
                result = resultListNode
            else:
                resultListNode.next = l1Node
                resultListNode = resultListNode.next
        if l2Node!=None:
            if resultListNode == None:
                resultListNode = l2Node
                result = resultListNode
            else:
                resultListNode.next = l2Node
                resultListNode = resultListNode.next
        return result

或者：

class Solution:
    def mergeTwoLists(self, l1, l2):
        prehead = ListNode(-1)
        prev = prehead
        while l1 and l2:
            if l1.val <= l2.val:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next            
            prev = prev.next
        # 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 if l1 is not None else l2
        return prehead.next

括号生成**

Date：2020-9-28 周一

暴力

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(A):
            if len(A) == 2 * n:
                if valid(A):
                    ans.append("".join(A))
            else:
                A.append("(")
                generate(A)
                A.pop()
                A.append(")")
                generate(A)
                A.pop()
        def valid(A):
            bal = 0
            for c in A:
                if c == "(":bal += 1
                else: bal -= 1
                if bal < 0:return False
            return bal == 0
        ans = []
        generate([])
        return ans

回溯法

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def backtrack(S, left, right):
            if len(S) == 2 * n:
                ans.append(''.join(S))
                return
            if left < n:
                S.append('(')
                backtrack(S, left+1, right)
                S.pop()
            if right < left:
                S.append(')')
                backtrack(S, left, right+1)
                S.pop()
        backtrack([], 0, 0)
        return ans

按括号序列的长度递归

class Solution:
    @lru_cache(None)#lru_cache使用了LRU算法，在maxsize=None大小的空间内缓存函数的结果
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return ['']
        ans = []
        for c in range(n):
            for left in self.generateParenthesis(c):
                for right in self.generateParenthesis(n-1-c):
                    ans.append('({}){}'.format(left, right))
        return ans

合并K个升序链表

Date：2020-9-29 周二

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        nodeList = []
        for i in range(len(lists)):
            node = lists[i]
            while node!=None:
                nodeList.append(node.val)
                node = node.next
        nodeList.sort()
        node = ListNode(-1)
        indexNode = node
        for value in nodeList:
            indexNode.next = ListNode(value)
            indexNode = indexNode.next
        return node.next

思路就是先把列表中的所有链表的值放到一个List中，然后排序在生成一条升序链表。返回即可。

两两交换链表中的节点

Date：2020-9-29 周二

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head == None:
            return None
        index = 0
        start = ListNode(-1)
        start.next = head
        result = start
        while start.next != None:
            if index % 2 == 0 and start.next.next != None:
                left = start.next
                right = left.next
                left.next = right.next
                right.next = left
                start.next = right
            start = start.next
            index +=1
        return result.next

K个一组翻转链表

Date：2020-9-29 周二

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if head == None:
            return None
        listLen = 0
        nodeList = []
        start = ListNode(-1)
        start.next = head
        nodeIndex = head
        while nodeIndex != None:
            listLen += 1
            nodeIndex = nodeIndex.next
        for _ in range(int(listLen / k)):
            listMid = []
            for _ in range(k):
                node = start.next
                start.next = node.next
                listMid.append(node)
            nodeList.append(listMid)
        lastNodeList = start.next
        reuslt =start
        for i in range(int(listLen / k)):
            index = k - 1
            while index >= 0:
                node = nodeList[i][index]
                node.next = None
                start.next = node
                start = start.next
                index -=1
        start.next = lastNodeList
        return reuslt.next

两数相除

Date：2020-9-29 周二

暴力

class Solution:
        def divide(self, dividend: int, divisor: int) -> int:
            if dividend == 0: return 0
            num = 0
            symbols = 0 #0代表负数 1代表正数 
            if (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0) :
                symbols = 1
            dividend = abs(dividend)
            divisor = abs(divisor)
            index = divisor
            while index <= dividend:
                num += 1
                index +=divisor
            if dividend > 2**31 -1:
                if symbols == 1:
                    dividend = 2**31 -1
                else:
                    dividend = 2**31
            return num if symbols == 1 else -num

暴力虽然可行，但是会导致超时

他人的思路

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        def recursion(dividend, divisor):
            if dividend < divisor:
                return 0
            if dividend == divisor:
                return 1
            nn = 1
            dd = divisor
            while True:
                if dividend > dd:
                    n = nn
                    nn += nn
                    d = dd
                    dd += dd
                elif dividend == dd:
                    return nn
                else:
                    return n + recursion(dividend-d, divisor)
        if dividend >= 0:
            if divisor > 0:
                positive = True
            else:
                positive = False
        else:
            if divisor > 0:
                positive = False
            else:
                positive = True 
        ans = recursion(abs(dividend), abs(divisor))
        if positive:
            if ans > 2**31 -1:
                return 2**31 -1
            else:
                return ans
        else:
            return -ans

串联所有单词的子串**

Date：2020-9-29 周二

我的思路（错误）

最开始我的思路是先把字母列表排列组合，并且去重后得到所有可能的字母组合。然后逐个看是否在字符串S中出现过，通过他出现的次数进行处理。但是Python的字符串的count方法会有问题，比如在“aaa”中“aa”出现的次数是多少次？应该是2次，但是count返回的是1次。就直接导致我的整个方法崩塌掉。其实如果手动实现count方法的话估计也能pass，但是时间复杂度上肯定不如自带函数好用。可惜了

#错误代码
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        wordsList = []
        resultList = []
        for i in itertools.permutations(words,len(words)): #排列组合字母
            wordsList.append("".join(list(i)))
        wordsList = set(wordsList)
        wordsList = list(wordsList)

        if len(set(s)) == 1 and len(set(wordsList[0])) == 1: #处理aaaaaa的情况
            print(len(words)-len(wordsList))
            for i in range(len(s)-len(wordsList[0])+ 1):
                resultList.append(i)
            return resultList
        for i in range(len(wordsList)):
            if wordsList[i] in s:
                if s.count(wordsList[i]) == 1:
                    # print("==1 :%d"%s.find(wordsList[i]))
                    resultList.append(s.find(wordsList[i]))
                else:
                    sIndex = s
                    # count = 0
                    move = 0
                    while sIndex.count(wordsList[i]) !=0:
                        print("wordsList[i]:%s"%wordsList[i])
                        index = sIndex.find(wordsList[i])
                        # print("index:%d count%d"%(index,count))
                        resultList.append(move + index)
                        # print("find index:%d"%(index + len(wordsList[i])*count))
                        sIndex = sIndex[index + len(wordsList[i]):]
                        move += index + len(wordsList[i])
                        print("move:%d"%move)
                        # count += 1
                        print(sIndex)
        resultList = set(resultList)
        resultList = list(resultList)
        return resultList

别人的思路

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        from collections import Counter
        if not s or not words:return []
        one_word = len(words[0])
        all_len = len(words) * one_word
        n = len(s)
        words = Counter(words)
        res = []
        for i in range(0, n - all_len + 1):
            tmp = s[i:i+all_len]
            c_tmp = []
            for j in range(0, all_len, one_word):
                c_tmp.append(tmp[j:j+one_word])
            if Counter(c_tmp) == words:
                res.append(i)
        return res

下一个排列*

Date：2020-9-30 周三

class Solution:
    def changeList(self,nums:List[int],left:int,right:int):
        mid = nums[left]
        nums[left] = nums[right]
        nums[right] = mid
    def nextPermutation(self, nums: List[int]) -> None:
        index = len(nums) - 1
        while index >= 1: #从后向前查看逆序区域
            if nums[index] > nums[index - 1]:
                break
            index -= 1        
        if index == 0: #倒序
            nums.sort()
        elif index == len(nums) - 1: #正序
            self.changeList(nums,index - 1,index)
        else:
            head = index - 1 #找到逆序区域的前一位，也就是数字置换的边界
            i = len(nums) - 1
            while i > index:
                if nums[i] > nums[head]:
                    break
                i -= 1
            self.changeList(nums,head,i) #把逆序区域的前一位和逆序区域中刚刚大于它的数字交换位置
            i = head + 1
            j = len(nums) - 1
            while i < j: #把原来的逆序区域转为顺序
                self.changeList(nums,i,j)
                i +=1
                j -=1

字典序

这个题需要先搞懂什么是字典序，也可以称为换位数。

要想获得最近换位数的核心思想是：

最长有效括号**

Date：2020-9-30 周三

这道题感觉难在求连续子串的长度。如果是单纯求总共有多少个括号可以匹配比较容易。
看一下大佬的思路：

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s: return 0

        stack = []
        ans = 0
        for i in range(len(s)):
            # 入栈条件
            if not stack or s[i] == '(' or s[stack[-1]] == ')':
                stack.append(i)     # 下标入栈
            else:
                # 计算结果
                stack.pop()
                ans = max(ans, i - (stack[-1] if stack else -1))
        return ans

搜索旋转排序数组

Date：2020-9-30 周三

眼瞎没看到时间复杂度限制

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        try:
            return nums.index(target)
        except Exception:
            return -1

二分法

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[0] <= nums[mid]:
                if nums[0] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target <= nums[len(nums) - 1]:
                    l = mid + 1
                else:
                    r = mid - 1
        return -1

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

Date：2020-9-30 周三

二分法

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start , end = -1 , len(nums)
        left , right = 0, len(nums) - 1  
        while left <= right :
            mid = int((right + left) / 2)
            if nums[mid] == target:
                start = end = mid
                while start!=0 and nums[start - 1] == target :
                    start -= 1
                while end !=(len(nums) - 1) and nums[end + 1] == target :
                    end += 1
                break   
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        if start != -1:
            return [start,end]
        else:
            return [-1,-1]