1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案

1
2
3
4
5
6
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):   
            for j in range(i+1,len(nums)):  #两数不重复
                if nums[i]+nums[j]==target:
                    return([i,j])

9. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。

1
2
3
4
5
6
7
8
9
class Solution:
    def isPalindrome(self, x: int) -> bool:
        #将x转化为字符串，再用切片进行翻转
        x=str(x)    
        y=x[::-1]
        if y==x:
            return True
        else:
            return False

13. 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def romanToInt(self, s: str) -> int:
        s=str(s)
        n=(s.count('IV')*4+s.count('IX')*9+s.count('XL')*40
        +s.count('XC')*90+s.count('CD')*400+s.count('CM')*900
        )   #计算非正常部分
        s=(s.replace('IV','').replace('IX','')
        .replace('XL','').replace('XC','')
        .replace('CD','').replace('CM','')
        )    #去除非正常部分
        n+=(s.count('I')*1+s.count('V')*5+s.count('X')*10+s.count('L')*50
        +s.count('C')*100+s.count('D')*500+s.count('M')*1000
        )     #计算正常部分
        return(n)

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        Flag=True
        if strs[0]=='':   #第一个元素为空时，输出空
            return('')
        else:
            strs_1=strs[0]
        if len(strs)==1:   #只有1个元素时，直接输出该元素
            return(strs_1)
        i=0
        while Flag:
            for j in range(1,len(strs)):
                strs_j=strs[j]
                Flag=Flag and strs_1[0:i]==strs_j[0:i] #判断前缀是否相同
            if not Flag:
                break
            i+=1
            if i==len(strs_1)+1:  #限制i的大小
                break
        if i==0:
            return('')
        else:
            return(strs_1[0:i-1])

20. 有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isValid(self, s: str) -> bool:
        d={
            ')':'(',
            ']':'[',
            '}':'{'
        }           #作字典，建立对应关系
        stack=[]
        for i in s:
            if i in d:
                if not stack or stack[-1]!=d[i]:    #如果栈为空或栈顶的左括号和右括号不符合，输出False              
                    return False
                stack.pop()  #栈不为空，且栈顶左括号与右括号匹配，删除这个左括号
            else:
                stack.append(i)
        return not stack   #栈为空，说明全部匹配，输出True；否则输出False

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head=ListNode()  #哨兵节点
        lst=head
        while list1 and list2:
            if list1.val <=list2.val: #判断大小，节点连接到较小的节点
                lst.next=list1
                list1=list1.next #取完节点后，指向下一个节点
            else:
                lst.next=list2
                list2=list2.next
            lst=lst.next  #判断下一个节点
        lst.next=list2 if not list1 else list1     #判断None情况
        return head.next

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

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i=1
        j=0
        while i in range(len(nums)):
            if nums[i]==nums[i-1]:
                nums.pop(i)
                i=i-1
                j=i
            i+=1
        return len(nums)
1
2
3
4
5
6
7
8
9
10
#优秀题解
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n=len(nums)
        j=0
        for i in range(n):
            if nums[i]!=nums[j]:
                j+=1
                nums[j]=nums[i]   #并不需要删除元素，只需要把不重复的元素移到最左边
        return j+1

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

1
2
3
4
5
6
7
8
9
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i=0
        while i <len(nums):
            if nums[i]==val:
                nums.pop(i)
                i=i-1
            i=i+1
        return len(nums)
1
2
3
4
5
6
7
8
9
10
#双指针的精髓是j来构造需要的结果
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        n=len(nums)
        j=0
        for i in range(n):
            if nums[i]!=val:
                nums[j]=nums[i]
                j+=1
        return j

28. 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

1
2
3
4
#python一行代码直接秒了，哭笑不得
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        #因为要求时间复杂度为O（log n),故使用二分法
        b=len(nums)
        a=0
        #先判断两个端点
        if target<=nums[a]: return a
        elif target>nums[b-1]: return b
        #再进行二分
        i=b//2
        while i-a:
            if target==nums[i]: return i
            if target<nums[a]: return a
            elif target>nums[b-1]: return b
            elif target<nums[i]: 
                b=i
                i=(a+b)//2
            elif target>nums[i]:
                a=i
                i=(a+b)//2
        return b

58. 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        #倒过来检索
        n=len(s)
        i=n-1
        while i:
            if s[i]!=' ': break
            i=i-1
        j=i-1
        while j>=0:
            if s[j]==' ': break
            j=j-1
        return i-j
1
2
3
4
5
6
7
8
9
10
11
#通过累加ans来确定非空格单词长度
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        ans = 0
        for c in s[::-1]:
            if c == ' ':
                if ans:
                    break
                continue
            ans += 1 
        return ans

66. 加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n=len(digits)
        m=1
        for i in range(-1,-(n+1),-1):  #逆向遍历，i同时也当作十进制的位数
            m+=digits[i]*10**(-(i+1))   #将数组转化为十进制int
            digits[i]+=1            #该位置的数字+1
            if m%(10**(-(i)))!=0:   #如果进位，遍历继续；如果不进位，则终止输出
                break
            digits[i]=0
        if set(digits)=={0}:   #所有位置都进位，此时digits变为了一个只含0的列表，此时在首位插入1
            digits.insert(0,1)
        return digits

69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def mySqrt(self, x: int) -> int:
        a,b,ans=0,x,0 #二分法
        while a<=b:
            c=(a+b)//2
            if c*c<=x:
                ans=c
                a=c+1
            else:
                b=c-1
        return ans

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

1
2
3
4
5
6
7
8
9
#使用递归解题正确，但是在n=44时超出时间限制，必须要加一个装饰器，避免出现重复计算
class Solution:
	@cache  #装饰器：简单的轻量级无限制缓存
    def climbStairs(self, n: int) -> int:
        if n==2:
            return 2
        elif n==1:
            return 1
        return Solution.climbStairs(self,n-1)+Solution.climbStairs(self,n-2)

·

1
2
3
4
5
6
7
#题解-动态规划
class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n - 1):
            a, b = b, a + b
        return b

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

1
2
3
4
5
6
7
8
9
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        del nums1[m:]
        for i in range(n):
            nums1.append(nums2[i])  #把nums2中的元素加到nums1中
        nums1.sort()  #排序

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 递归
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        return self.inorderTraversal(root.left)+[root.val]+self.inorderTraversal(root.right)   #左根右
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 迭代实现，模拟向左走的过程
class Solution(object):
	def inorderTraversal(self, root):
		"""
		:type root: TreeNode
		:rtype: List[int]
		"""
		res = []
		stack = []
		while stack or root:
			# 不断往左子树方向走，每走一次就将当前节点保存到栈中
			# 这是模拟递归的调用
			if root:
				stack.append(root)
				root = root.left
			# 当前节点为空，说明左边走到头了，从栈中弹出节点并保存
			# 然后转向右边节点，继续上面整个过程
			else:
				tmp = stack.pop()
				res.append(tmp.val)
				root = tmp.right
		return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#莫里斯遍历，将二叉树转为链表
class Solution(object):
	def inorderTraversal(self, root):
		"""
		:type root: TreeNode
		:rtype: List[int]
		"""
		res = []
		pre = None
		while root:
			# 如果左节点不为空，就将当前节点连带右子树全部挂到
			# 左节点的最右子树下面
			if root.left:
				pre = root.left
				while pre.right:
					pre = pre.right
				pre.right = root
				# 将root指向root的left
				tmp = root
				root = root.left
				tmp.left = None   #将移动节点的左子树移除，只剩下右子树
			# 左子树为空，则打印这个节点，并向右边遍历	
			else:
				res.append(root.val)
				root = root.right
		return res

100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        elif not p or not q:
            return False
        if p.val!=q.val:
            return False        
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cost, profit = float('+inf'), 0
        for price in prices:
            cost = min(cost, price)
            profit = max(profit, price - cost)
        return profit
1
2
3
4
5
6
7
8
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        f = [0] * n
        for i in range(1,n): 
            f[i] = prices[i] - prices[i-1] + max(0,f[i-1])
        #f[i]代表第i天卖出的最大利润，如果f[i-1]小于等于0，说明price[i-1]是最低价，若大于0，说明有比price[i-1]更低的价格
        return max(f)

191. 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

提示：

  • 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
  • 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 3 中，输入表示有符号整数 -3。
1
2
3
4
5
6
7
class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            if n & 1: res += 1
            n >>= 1
        return res

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

1
2
3
4
5
6
7
8
9
 #暴力破解
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        magazine = list(magazine)
        for item in ransomNote:
            if item in magazine:
                magazine.remove(item)
            else: return False
        return True
1
2
3
4
5
6
#Counter函数的使用，将对象生成一个可运算的字典
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(ransomNote) > len(magazine):
            return False
        return not collections.Counter(ransomNote) - collections.Counter(magazine)

412. Fizz Buzz

给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（下标从 1 开始）返回结果，其中：

  • answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数。
  • answer[i] == "Fizz" 如果 i 是 3 的倍数。
  • answer[i] == "Buzz" 如果 i 是 5 的倍数。
  • answer[i] == i （以字符串形式）如果上述条件全不满足。
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        #用字符串拼接减少了一次循环判断
        res = []
        for i in range(1,n+1):
            s = ''
            if i % 3 == 0: s += ('Fizz')
            if i % 5 == 0: s += ('Buzz')
            if s == '': s = str(i)
            res.append(s)
        return res

876. 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点

1
2
3
4
5
6
7
8
9
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur, sign = head, head, 1
        while pre.next:
            pre = pre.next
            if sign == 1:
                cur = cur.next
            sign = -sign
        return cur

1342. 将数字变成 0 的操作次数

给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

1
2
3
4
5
6
7
class Solution:
    def numberOfSteps(self, num: int) -> int:
        i = 0
        while num:
            i += 1
            num = num - 1 if num % 2 else num // 2
        return i

1480. 一维数组的动态和

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

1
2
3
4
5
6
7
8
class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        s = 0
        res = []
        for i in range(len(nums)):
            s += nums[i]
            res.append(s)     
        return res

1672. 最富有客户的资产总量

给你一个 m x n 的整数网格 accounts ，其中 accounts[i][j] 是第 i 位客户在第 j 家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。

客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。

1
2
3
4
5
6
class Solution:
    def maximumWealth(self, accounts: List[List[int]]) -> int:
        lst = []
        for item in accounts:
            lst.append(sum(item[i] for i in range(len(item))))
        return max(lst)