94.二叉树中序遍历

leetcode链接：添加链接描述
数的三种深度遍历、层次遍历：添加链接描述

# Definition for a binary tree node.法一，递归
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        def helper(root):
            if not root:
                return
            helper(root.left)
            res.append(root.val)
            helper(root.right)
        helper(root)
        return res

class Solution:#非递归，模拟指针
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        # 用p当做指针
        p = root
        while p or stack:
            # 把左子树压入栈中
            while p:
                stack.append(p)
                p = p.left
            # 输出 栈顶元素
            p = stack.pop()
            res.append(p.val)
            # 看右子树
            p = p.right
        return res

144. 二叉树的前序遍历

leetcode链接：添加链接描述
思路:
递归:就是依次输出根,左,右,递归下去
迭代:使用栈来完成,我们先将根节点放入栈中,然后将其弹出,依次将该弹出的节点的右节点,和左节点,**注意顺序,**是右,左,为什么?因为栈是先入后出的,我们要先输出左节点,所以让它先进栈.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        if not root:#注意如果没有，输出空数组！！
            return res
        stack = [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res

145. 二叉树的后序遍历

leetcode链接：添加链接描述
思路：
递归:同理,顺序:左,右,根
迭代:这就很上面的先序一样,我们可以改变入栈的顺序,刚才先序是从右到左,我们这次从左到右,最后得到的结果取逆.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        if not root:#注意如果没有，输出空数组！！
            return res
        stack=[root]
        while stack:
            node=stack.pop()
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
            res.append(node.val)
        return res[::-1]

102. 二叉树的层序遍历

leetcode链接：添加链接描述

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res,cur_level=[],[root]
        while cur_level:
            temp=[]
            next_level=[]
            for i in cur_level:
                temp.append(i.val)
                if i.left:
                    next_level.append(i.left)
                if i.right:
                    next_level.append(i.right)
            res.append(temp)
            cur_level=next_level
        return res

72. 编辑距离(动态规划-自底向上）

leetcode链接：添加链接描述

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1=len(word1)
        n2=len(word2)
        dp=[[0]*(n2+1) for i in range(n1+1)]
        for i in range(n1+1):
            dp[i][0]=i
        for j in range(n2+1):
            dp[0][j]=j
        for i in range(1,n1+1):
            for j in range(1,n2+1):
                if word1[i-1]==word2[j-1]:
                    dp[i][j]=dp[i-1][j-1]
                else:
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
        return dp[-1][-1]

1431. 拥有最多糖果的孩子

题目链接

面试题58 - II. 左旋转字符串

题目链接

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
    	#法一：字符串切片
    	return s[n:]+s[:n]

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
    	#法二：列表遍历拼接
        res=[]
        for i in s[n:]:
            res.append(i)
        for i in s[:n]:
            res.append(i)
        return ''.join(res)
 #利用取余可以简化操作
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
    	#法二：列表遍历拼接
        res=[]
        for i in range(n:n+len(s)):
            res.append(s[i%len(s)])
        return ''.join(res)

#方法三：字符串遍历拼接
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        res=''
        for i in s[n:]:
            res+=i
        for i in s[:n]:
            res+=i
        return res 

面试题 01.03. URL化

leetcode链接
题目坑点：字符串真实长度length和字符串不是一个长度，需要先切片。
（1）Python replace() 方法把字符串中的 old（旧字符串） 替换成 new(新字符串)，如果指定第三个参数max，则替换不超过 max 次。
replace()方法语法：str.replace(old, new[, max])
（2）join()方法语法：
str.join(sequence)
sequence – 要连接的元素序列
详细可学习：添加链接描述

str = "-";
seq = ("a", "b", "c"); # 字符串序列
print str.join( seq );
#以上实例输出结果如下：
a-b-c

class Solution:
    def replaceSpaces(self, S: str, length: int) -> str:
        s=S[:length]
        return s.replace(' ','%20',length)
class Solution:
    def replaceSpaces(self, S: str, length: int) -> str:
        return '%20'.join(S[:length].split(' '))        

面试题 01.04. 回文排列

牛客链接

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        times=collections.Counter(s)
        num=[d%2 for d in times.values()]
        if num.count(1)>1:
            return False
        return True

面试题 01.05. 一次编辑

链接

class Solution:
    def oneEditAway(self, first: str, second: str) -> bool:
        if abs(len(first)-len(second))>1:
            return False
        count=0
        if len(first)==len(second):
            for i in range(len(first)):
                if first[i]!=second[i]:
                    count+=1
                    if count>=2:
                        return False
            return True
        if len(first)<len(second):
            first,second=second,first 
        if len(first)>len(second):
            for i in range(len(first)):
                if first[0:i]+first[i+1:]==second:
                    return True 
            return False 

面试题 01.06. 字符串压缩

添加链接描述

class Solution:
    def compressString(self, S: str) -> str:
        n=len(S)
        res=''
        i=0
        while i<n:
            j=i
            while j<n and S[i]==S[j]:
                j+=1
            res+=S[i]+str(j-i)
            i=j
        if len(res)<len(S):
            return res
        else:
            return S

面试题 01.07. 旋转矩阵

添加链接描述

#法一：空间和时间复杂度都是O(N^2)
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        # Python 这里不能 matrix_new = matrix 或 matrix_new = matrix[:] 因为是引用拷贝
        matrix_new = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                matrix_new[j][n - i - 1] = matrix[i][j]
        # 不能写成 matrix = matrix_new
        matrix[:] = matrix_new

#法二：时间复杂度是O(N^2)，空间复杂度O(1)
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n // 2):
            for j in range((n + 1) // 2):
                temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp

面试题 01.08. 零矩阵

添加链接描述

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        res=[]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j]==0:
                    res.append(i)
                    res.append(j)
        for i in range(len(res)):
            if i%2==0:
                for j in range(len(matrix[0])):
                    matrix[res[i]][j]=0
            elif i%2==1:
                for j in range(len(matrix)):
                    matrix[j][res[i]]=0

面试题 01.09. 字符串轮转

添加链接描述

class Solution:
    def isFlipedString(self, s1: str, s2: str) -> bool:
        if len(s1)!=len(s2):
            return False
        if len(s1)==0 and len(s2)==0 :
                return True
        else:
            for i in range(len(s1)):
                if s1[i:]+s1[0:i]==s2:
                    return True
            return False

class Solution:
    def isFlipedString(self, s1: str, s2: str) -> bool:
        return len(s1)==len(s2) and s1 in s2*2

面试题 02.01. 移除重复节点

未排序链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None 双指针
class Solution:
    def removeDuplicateNodes(self, head: ListNode) -> ListNode:
        if not (head and head.next):
            return head
        cur=head
        res={
    head.val}
        while head.next:
            if head.next.val in res:
                head.next=head.next.next
            else:
                res.add(head.next.val)
                head=head.next
        return cur

相似题目：排序链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None 不占用额外空间 可利用上题的解法求解

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        node=head
        while node and node.next:
            if node.val==node.next.val:
                node.next=node.next.next
            else:
                node=node.next
        return head

5. 最长回文子串

学习动态规划
添加链接描述

#法一：暴力解法--切片
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if s==s[::-1]:
            return s 
        max_len=1
        res=s[0]
        for i in range(len(s)-1):
            for j in range(i,len(s)):
                if j-i+1>max_len and s[i:j+1]==s[i:j+1][::-1]:
                    max_len=j-i+1
                    res=s[i:j+1]
        return res

class Solution:
    def longestPalindrome(self, s: str) -> str:   
# 马拉车算法
# 先在字符串中间加符号隔开，使得奇偶回文数的形式统一
# 然后用kmp的思想去优化中心扩散
        if len(s)== 0:return ""
        s_new  = '#' + '#'.join(s) + '#'
        #print(s_new)
        #已遍历的最大右边界
        mx = 0
        #对应的中心点
        mid = 0  
        l = len(s_new)
        # 扩散半径数组，初始值1或者0都可以，只是代表刚开始的时候扩散半径是多少而已
        p = [1]*l
        for i in range(l):
            if i<mx:
                # 这个时候可以用已经计算过的值
                # 不能超过已遍历的右边界
                # i对应的镜像 = 2*mid - i
                # 由mx定义可知半径最长不会超过mx-i
                p[i] = min(mx-i,p[2*mid-i])        
            # 主要的优化已经在上面节省了时间，接下来就是正常的扩散
            while( i-p[i]>=0 and i+p[i]<l and s_new[i-p[i]] == s_new[i+p[i]]):
                p[i] += 1
            # 记录一下mx和mid
            if i+p[i] > mx:
                mx = i+p[i]
                mid = i
        maxr = max(p)
        ans = p.index(maxr)
        # 因为跳出循环的时候多加了1，所以实际上的扩散半径应该减1
        maxr -= 1
        return s_new[ans-maxr:ans+maxr+1].replace('#',"")

13. 罗马数字转整数

添加链接描述

#假设了从左到右位数越来越小，高位在左低位在右
class Solution:
    def romanToInt(self, s: str) -> int:
        romanint={
    'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        n=len(s)
        result=0
        for i in range(n-1):
            if romanint[s[i]]<romanint[s[i+1]]:
                result-=romanint[s[i]]
            else:
                result +=romanint[s[i]]
        return result+romanint[s[-1]]

14. 最长公共前缀

原题链接
参考题解
zip学习
首先是对不定量参数*args，**kwargs传参进行简单的说明：
*args：用来发送一个非键值对的可变数量的参数列表给一个函数
**kwargs：是将不定长的键值对作为参数传递给一个函数

#法一：Python zip特性，取每一个单词的同一位置的字母，看是否相同。
#解题思路：先使用zip(*li)对字符串数组进行元素打包，然后使用set()函数去重，如果去重后的元素长度为1，则是公共前缀。
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res=''
        for tmp in zip(*strs):
            tmp_set=set(tmp)
            if len(tmp_set)==1:
                res+=tmp[0]
            else:
                break 
        return res

#法三：按字典排序数组，比较第一个，和最后一个单词，有多少前缀相同。注意是排序后的数组
class Solution:
    def longestCommonPrefix(self, s: List[str]) -> str:
        if not s:
            return ''
        s.sort()
        n=len(s)
        a=s[0]
        b=s[n-1]
        res=''
        for i in range(len(a)):
            if i<len(b) and a[i]==b[i]:
                res+=a[i]
            else:
                break
        return res 

20. 有效的括号

题目
题解

class Solution:
    def isValid(self, s: str) -> bool:
        stack=[]
        mapping={
    ')':'(','}':'{',']':'['}
        for char in s:
            if char in mapping:
                top_element=stack.pop() if stack else'#' #注意只有一个字符的情况
                if mapping[char]!=top_element:
                    return False
            else:
                stack.append(char)
        return not stack

21. 合并两个有序链表

添加链接描述

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None 法一：递归
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        elif not l2:
            return l1
        elif l1.val<=l2.val:
            l1.next=self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next=self.mergeTwoLists(l1,l2.next)
            return l2          

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 创建哑节点作为 结果链表 的开头
        dummy = ListNode(0)
        # 有个游标，标识 结果链表 的结尾
        move = dummy
        # l1 和 l2 都未遍历结束
        while l1 and l2:
            # 如果 l1 的数值比较小
            if l1.val <= l2.val:
                # 把 l1 头部节点拼接到 结果链表 的结尾
                move.next = l1
                # l1 指向下一个节点
                l1 = l1.next
            else:
                # 把 l2 头部节点拼接到 结果链表 的结尾
                move.next = l2
                # l2 指向下一个节点
                l2 = l2.next
            # 移动 结果链表 的结尾指针
            move = move.next
        # l1 或者 l2 尚未使用完，拼接到 结果链表 的最后
        move.next = l1 if l1 else l2
        # 返回哑节点的下一个位置
        return dummy.next

171. Excel表列序号

添加链接描述

class Solution:
    def titleToNumber(self, s: str) -> int:
        tmp ={
    'A':1,'B':2,'C':3,'D':4,'E':5,'F':6,'G':7,'H':8,'I':9,'J':10,'K':11,'L':12,'M':13,'N':14,'O':15,'P':16,'Q':17,'R':18,'S':19,'T':20,'U':21,'V':22,'W':23,'X':24,'Y':25,'Z':26}
        s=[i for i in s]
        res=0
        p=1
        while s:
            res+=tmp[s.pop()]*p 
            p=p*26
        return res 

class Solution:
    def titleToNumber(self, s: str) -> int:
        res=0
        bit=1
        for i in s[::-1]:
            res+=(ord(i)-64)*bit
            bit*=26
        return res

7. 整数反转

题目链接
题解链接

#数值计算，注意限定范围约束
class Solution:
    def reverse(self, x: int) -> int:
        y,res=abs(x),0
        # 则其数值范围为 [−2^31,  2^31 − 1]
        boundry=(1<<31)-1 if x>0 else (1<<31)
        while y!=0:
            tmp=y%10
            res=res*10+tmp
            if res>boundry:
                return 0
            y//=10
        return res if x>0 else -res

#字符串切片，注意限定范围约束
class Solution:
    def reverse(self, x: int) -> int:
        str_num=str(x)[::-1]
        if str_num.endswith('-'):
            str_num=str_num[-1]+str_num[:-1]
            return int(str_num) if int(str_num)>=-2**31 else 0
        return int(str_num) if int(str_num)<=2**31-1 else 0

9. 回文数

题目链接
题解

    # 方法一：字符串切片
class Solution:
    def isPalindrome(self, x: int) -> bool:
        x=str(x)
        if x==x[::-1]:
            return True
        return False

    # 方法二: 将int转化成str类型: 双指针 (指针的性能一直都挺高的),转字符串
    # 复杂度: O(n)
class Solution:
    def isPalindrome(self, x: int) -> bool:
        x=str(x)
        left,right=0,len(x)-1
        while left<right:
            if x[left]!=x[right]:
                return False
            left+=1
            right-=1
        return True

题解下述方法

#取模运算
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x<0:
            return False
        res=0
        old=x
        while x:
            tmp=res%10
            res=res*10+tmp 
            x//=10
        if res==old:
            return True
        return False

#旋转一半的数，约束条件 res<x，奇偶判断 return res==x or x==(res//10)
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x<0 or(x%10==0 and x!=0):
            return False
        res=0
        while res<x:
            tmp=x%10
            res=res*10+tmp
            x//=10
        return res==x or x==(res//10)

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

添加链接描述

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        i=0
        for j in range(1,len(nums)):
            if nums[i]!=nums[j]:
                i+=1#先i增加，再赋值
                nums[i]=nums[j]
        return i+1

27. 移除元素

添加链接描述
与26题相似

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i=0
        for j in range(0,len(nums)):
            if nums[j]!=val:
                nums[i]=nums[j]
                i+=1
        return i

28. 实现 strStr()

题目
题解

#方法一：子串逐一比较 - 线性时间复杂度
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        h,n=len(haystack),len(needle)
        for i in range(h-n+1):
            if haystack[i:i+n]==needle:
                return i 
        return -1

35. 搜索插入位置

解析链接(有练习整理）
题目链接

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n=len(nums)
        if target>nums[-1]:
            return n
        left=0
        right=n-1
        while left<right:
            #mid=(left+right)//2 (left、right大的时候容易发生溢出)
            mid=left+(right-left)//2
            if target==nums[mid]:
                return mid 
            elif target<nums[mid]:
                right=mid
            else:
                left=mid+1
        return left

38. 外观数列

题目
题解1

class Solution:
    def countAndSay(self, n: int) -> str:
        prev_person='1'
        for i in range(1,n):
            next_person,num,count='',prev_person[0],1
            for j in range(1,len(prev_person)):
                if prev_person[j]==num:
                    count+=1
                else:
                    next_person+=str(count)+num 
                    num=prev_person[j]
                    count=1
            next_person+=str(count)+num 
            prev_person=next_person
        return prev_person

题解
groupby学习资料

from itertools import groupby
class Solution:
    def countAndSay(self, n: int) -> str:
        result='1'
        for i in range(1,n):
            result=''.join([str(len(list(g)))+k for k,g in groupby(result)])
        return result

53. 最大子序和

添加链接描述

#动态规划，空间时间复杂度都是O(N)
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        result=[nums[0]]
        for i in range(1,len(nums)):
            maxsum=max(result[i-1]+nums[i],nums[i])
            result.append(maxsum)
        return max(result)

空间O（1）的情况
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums)==1:
            return nums[0]
        res=nums[0]
        for i in range(1,len(nums)):
            nums[i]=max(nums[i-1]+nums[i],nums[i])
            res=max(res,nums[i])
        return res

58. 最后一个单词的长度

添加链接描述
题解

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        if not s:
            return 0
        return len(s.strip().split(' ')[-1])

66. 加一

添加链接描述

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        res=0
        multi=1
        for i in digits:
            res=res*10+i
        res+=1
        return [int(i) for i in str(res)]

69. x 的平方根

题目链接

# 袖珍计算器算法
class Solution:
    def mySqrt(self, x: int) -> int:
        if x==0:
            return 0
        ans=int(math.exp(0.5*math.log(x)))
        return ans+1 if (ans+1)*2<=x else ans

# 二分法
class Solution:
    def mySqrt(self, x: int) -> int:
        l,r,ans=0,x,-1
        while l<=r:
            mid=(l+r)//2
            if mid**2<=x:
                ans=mid
                l=mid+1
            else:
                r=mid-1
        return ans

# 牛顿迭代法
class Solution:
    def mySqrt(self, x: int) -> int:
        if x==0:
            return 0
        C,x0=float(x),float(x)
        while True:
            xi=0.5*(x0+C/x0)
            if abs(xi-x0)< 1e-7: 
                break
            x0=xi
        return int(x0)

67. 二进制求和

题目链接：添加链接描述
题解链接：添加链接描述
int函数说明：添加链接描述
字符串格式化(format)：添加链接描述

# 内置函数法 先转成十进制再转成二进制
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return '{0:b}'.format(int(a,2)+int(b,2))

# 位操作
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        x,y=int(a,2),int(b,2)
        while y:
            x,y=x^y,(x&y)<<1
        return bin(x)[2:]

137. 只出现一次的数字 II

题目链接： 添加链接描述
题解

# hashmap
from collections import Counter
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hashmap=Counter(nums)
        for k in hashmap.keys():
            if hashmap[k]==1:
                return k

#hashset
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return (3*sum(set(nums))-sum(nums))//2