力扣初级算法（Python）（一）-阿里云开发者社区

1概述

概述

这是由 LeetCode 官方推出的经典面试题目清单，我们将题目重新整理规划，从而为大家提供更好的练习体验和帮助大家找到理想的工作。我们将题目分为以下三个部分：

初级算法 - 帮助入门

中级算法 - 巩固训练

高级算法 - 提升进阶

这一系列 LeetBook 将帮助您掌握算法及数据结构，并提高您的编程能力。

编程能力就像任何其他技能一样，也是一个可以通过刻意练习大大提高的。

大多数经典面试题目都有多种解决方案。为了达到最佳的练习效果，我们强烈建议您至少将此清单里的题目练习两遍，如果可以的话，三遍会更好。

在第二遍练习时，你可能会发现一些新的技巧或新的方法。到第三遍的时候，你会发现你的代码要比第一次提交时更加简洁。如果你达到了这样的效果，那么恭喜你，你已经掌握了正确的练习方法！

记住：刻意练习并不意味着寻找答案并记住它，这种练习方法不是长久之计。在没有参考答案情况下，越能自主解决问题，才越能提高自身能力。

作者：力扣 (LeetCode)

链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x6w3ds/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2数组

2.1 删除排序数组中的重复项

思路：因为已经是排序数组，只要遍历一次就好。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        length = 0;
        for i in nums:
            if i != nums[length]:
                length+=1
                nums[length] = i
        return length+1

2.2 买卖股票的最佳时机 II

思路：只需要考虑股票上升曲线，因为只有上升曲线可能盈利。用上升曲线的最高点-最低点就是这段的最大利润。然后将所有的上升曲线盈利求和就是可能的最大利润。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if (prices == None or len(prices)<2):
            return 0
        profit = 0
        index = 0
        length = len(prices)
        while(index<length):
            while (index<length-1 and prices[index]>= prices[index+1]):
                index+=1
            min = prices[index]
            while (index<length-1 and prices[index]<= prices[index+1]):
                index+=1
            profit += prices[index]-min
            index +=1
        return profit

2.3 轮转数组

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        nums[:] = nums[n - k:] + nums[:n - k]

2.4 存在重复元素

先排序，再遍历

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        length = len(nums)
        for i in range(length-1):
            if nums[i] == nums[i+1]:
                return True
        return False

2.5 只出现一次的数字

和2.4 类似

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        length = len(nums)
        i = 0
        while i < (length-1):
            if nums[i] == nums[i+1]:
                i+=2
            else:
                return nums[i]
        return nums[length-1]

2.6 两个数组的交集||

排序+双指针

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        i = 0
        j = 0
        result = []
        while i<len(nums1) and j<len(nums2):
            if(nums1[i]<nums2[j]):
                i+=1
            elif(nums1[i]>nums2[j]):
                j+=1
            else:
                result.append(nums1[i])
                i+=1
                j+=1
            
        return  result

2.7 加一

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        length = len(digits)
        i = 0
        sum = 0
        while i<length:
           sum = sum*10+digits[i]
           i +=1
 
        sum +=1
        result = []
        while sum > 0:
            t = sum%10
            sum //=10
            result.insert(0,t)
        return result

2.8 移动零

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = 0
        num_zeros = 0
        while i < len(nums):
            if nums[i] == 0:
                nums.pop(i)
                num_zeros += 1
            else:
                i+=1
 
        for i in range(num_zeros):
            nums.append(0)

2.9 两数之和

没有想到好办法，就直接两层循环

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        first = 0
        while(first<length):
            second = first+1
            while(second<length):
                if(nums[first]+nums[second] == target):
                    return [first,second]
                second += 1
            first +=1
        return [first,second]

2.10 有效的数独

二维数组

编程常见问题 — Python 3.10.1 文档

3行2列：3个列表，每个列表的长度是2
w, h = 2, 3
A = [[None] * w for i in range(h)]

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        n = len(board)
        m = len(board[0])
        row = [[]  for _ in range(9)]
        col = [[]  for _ in range(9)]
        nine = [[]  for _ in range(9)]
        for i in range(n):
            for j in range(m):
                tmp = board[i][j]
                if not tmp.isdigit():
                    continue
                if tmp in row[i]:
                    return False
                if tmp in col[j]:
                    return False
                if tmp in nine[(j // 3) * 3 + (i // 3)]:
                    return False
                row[i].append(tmp)
                col[j].append(tmp)
                nine[(j // 3) * 3 + (i // 3)].append(tmp)
        return True

2.11旋转图像

用了底下“数据结构和算法”的方法，先上下交换，再按照对角线交换。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        length = len(matrix);
        #先上下交换
        for  i in range(length // 2):
            temp = matrix[i]
            matrix[i] = matrix[length - i - 1]
            matrix[length - i - 1] = temp
        #在按照对角线交换
        for i in range(length):
            for  j in range(i + 1, length):
                temp = matrix[i][j]
                matrix[i][j] = matrix[j][i]
                matrix[j][i] = temp

3 字符串

3.1 反转字符串

直接s.reverse()也是可以通过的

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        #s.reverse()-_-
        length = len(s)
        for i in range(length//2):
            t = s[i]
            s[i] = s[length-1-i]
            s[length-1-i] = t

3.2 整数反转

这个需要考虑特殊情况：负数和越界-2**31、2**31-1

正常情况就是将字符串当成序列切片s[::-1]。

class Solution:
    def reverse(self, x: int) -> int:
        s = str(x)
        if s[0] == '-':
            s_rev = s[0] + s[-1:-len(s):-1]
        else:
            s_rev = s[::-1]
        x_rev = int(s_rev)
        if -2 ** 31 <= x_rev <= 2 ** 31 - 1:
            return x_rev
        return 0

3.3 字符串中第一个唯一字符

方法一：利用find()和rfind(),

class Solution:
    def firstUniqChar(self, s: str) -> int:
        for x in s:
            if s.find(x) == s.rfind(x):
                return s.index(x)
        return -1

方法二：利用count()，效率低

class Solution:
    def firstUniqChar(self, s: str) -> int:
        for x in s:
            if s.count(x) == 1:
                return s.index(x)
        return -1

3.4 有效的字母异位词

每个字母的频率相同，可以（转成列表）排序比较，或者用哈希表（字典）来做

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        list_s = list(s)
        list_s.sort()
        list_t = list(t)
        list_t.sort()
        length = len(list_s)
        if length != len(list_t):
            return False
        for i in range(len(list_s)):
            if list_s[i] != list_t[i]:
                return False
 
        return True

3.5 验证回文串

忽略大小写(s = s.lower())，只考虑字母和数字( s[i].isalpha() or s[i].isdigit())

1.双指针

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        head = 0
        tail = len(s)-1
        while tail>head:
            if not (s[head].isalpha() or s[head].isdigit()):
                head +=1
                continue
            if not (s[tail].isalpha() or s[tail].isdigit()):
                tail -=1
                continue
            else:
                if s[head] != s[tail]:
                    return False
                else:
                    head +=1
                    tail -=1
        return True

2.去掉字母数字后，遍历一半元素

class Solution:
    def isPalindrome(self, s: str) -> bool:
        list_s = []
        s = s.lower()
        length_s = len(s)
        for i in  range(length_s):
            if s[i].isalpha() or s[i].isdigit():
                list_s.append(s[i])
        print(list_s)
        length_list = len(list_s)
        for i in range(length_list//2):
            if list_s[i] != list_s[length_list-1-i]:
                return  False
        return True

3.6 字符串转整数

题目步骤比较清楚，按顺序处理空格，+-号，数字，截断超范围数字。

class Solution:
    def myAtoi(self, s: str) -> int:
        res = 0
        i = 0
        flag = 1
        length = len(s)
        #处理空格
        while i < length and s[i] == ' ':
            i += 1
        #处理符号
        if i < length and s[i] == '-':
            flag = -1
            i += 1
        elif i < length and s[i] == '+':
            flag = 1
            i += 1
    
        #读取数字
        while i < length and s[i].isdigit():
            r = int(s[i])
            res = res*10 + r
            i += 1
        res *= flag
        #截断超过范围的结果
        if res>= -2**31 and res <= 2**31-1 :
            return res
        else:
            return -2**31 if res<-2**31 else 2**31-1

3.7 实现 strStr()

开始想用双指针遍历，超时了。评论里看到截取子串的方法，看着简单而且用时短。

库函数s.find(n)效率更高，但是属于作弊了。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(haystack)
        left = 0
        right = len(needle)
        if right == 0:
            return 0
        while right <= n:
            if haystack[left: right] == needle:
                return left
            left += 1
            right += 1
        return -1

3.8 外观数列

一个递归问题

countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return '1'
        s = self.countAndSay(n - 1)
        ans = ''
        start, end = 0, 0
        while end < len(s):
            while end < len(s) and s[start] == s[end]:
                end += 1
            ans += str(end - start) + s[start]
            start = end
 
        return ans

3.9 最长公共前缀

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if strs is None or len(strs) == 0:
            return ""
        result = ""
        minLength = len(strs[0])
        for s in strs:
            if len(s) < minLength:
                minLength = len(s)
        for i in range(minLength):
            c = strs[0][i]
            for s in strs:
                if s[i] != c:
                    return result
            result += c
        return result

4 链表

链表题有一种偷懒的方法就是转成数组做。这样可以利用数组的任意位置读取，但是失去链表插入、删除数据的高效。另外，数组要求连续的存储空间。

4.1 删除链表中的节点

删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

由于是单向链表，且没有头节点信息，所以实际上是无法删除该节点的。

然而答案给了一种间接的方法，就是删除该节点的后面一个节点。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

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

双指针法。一个快指针先走n步，然后慢指针一起走。当快指针走到末尾时，慢指针就到了倒数第n个节点。

需要注意，在头节点前加上一个假节点dummy可以让特殊情况（例如链表只有一个元素）变得一般化。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        
        dummy = ListNode(0,head)
        fast = dummy
        slow = dummy
        #fast先走n步
        for i in range(n):
            fast = fast.next
        while fast.next != None:
            fast = fast.next
            slow = slow.next
        
        slow.next = slow.next.next
        return dummy.next

4.3 反转列表

可以用递归实现。（但是递归效率会低）

#Python中类内函数的递归用self调用：self.f(...)

# 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: ListNode) -> ListNode:
        if head is None or head.next is None:
            return  head
 
        res = self.reverseList(head.next) #剩下的
        head.next = None #断开第一个
        t = res
        while  t.next != None:
            t = t.next
        t.next = head #剩下的+第一个
        return  res

方法二：构建新链表，每次将原链表的头变成新链表的头（类似与进栈操作）

作者：数据结构和算法

链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnhm6/?discussion=0NDu5u

来源：力扣（LeetCode）

4.4 合并两个有序链表

遍历链表。需要考虑列表为空的情况

# 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]:
        dummy = ListNode(0)
        if  list2 is None:
            return list1
        elif list1 is None:
            return list2
 
        cur = dummy
 
        while list1 is not None and list2 is not None:
            if (list1.val <= list2.val):
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
 
        if list1 is not None:
            cur.next = list1
        elif list2 is not None:
            cur.next = list2
 
        return dummy.next

4.5 回文链表

反转后半部分链表，与前面半部分链表比较。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        fast, slow = head,head
        while fast != None and fast.next !=None:
            slow = slow.next
            fast = fast.next.next
        #链表节点个数为奇数
        if fast != None:
            slow = slow.next
        second = self.reverseList(slow)
        while second!=None and head != None:
            if head.val != second.val:
                return False
            head= head.next
            second = second.next
        return True
 
 
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        while head !=None:
            next = head.next
            head.next = prev
            prev = head
            head = next
        return prev

4.6 环形链表

经典问题，方法之一是用快慢指针遍历，如果两个指针相遇说明存在环。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        fast, slow = head, head
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

5 树

和树相关的问题大多可以用递归

5.1 二叉树的最大深度

递归

# 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 root == None: 
            return 0
        else:
            return 1+max(self.maxDepth(root.left), self.maxDepth(root.right))

5.2 验证二叉搜索树

二叉搜索树，中序遍历的结果是递增的。

# 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 isValidBST(self, root: TreeNode) -> bool:
        inorder_list = []
        self.inorder(root,inorder_list)
        for i in range(len(inorder_list)-1):
            if inorder_list[i].val >=inorder_list[i+1].val:
                return False
        return True
 
    def inorder(self,root,list_m):
        if root == None:
            return
        self.inorder(root.left,list_m)
        list_m.append(root)
        self.inorder(root.right, list_m)
        return list_m

5.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 isSymmetric(self, root: TreeNode) -> bool:
        if root == None:
            return True
        else:
            return self.isSymmetricHelper(root.left,root.right)
    def isSymmetricHelper(self, left:TreeNode, right:TreeNode) -> bool: 
        #如果左右子节点都为空，说明当前节点是叶子节点，返回true
        if left == None and right == None:
            return True
        #如果当前节点有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
        if (left == None or right == None or left.val != right.val):
            return False
        #然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
        return self.isSymmetricHelper(left.left, right.right) and self.isSymmetricHelper(left.right, right.left)

5.4 二叉树的层序遍历

层序遍历，可用队列实现

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        queue = [root]
        res = []
        while queue:
            sub_list = []
            for i in range(len(queue)):
                t = queue.pop(0)
                sub_list.append(t.val)
                if t.left:
                    queue.append(t.left)
                if t.right:
                    queue.append(t.right)
            res.append(sub_list)
        return res

5.5 将有序数组转换为二叉搜索树

递归

# 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 sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if len(nums) == 0: 
            return None
        mid = len(nums)//2
        root = TreeNode(nums[mid])
        root.left = Solution.sortedArrayToBST(self,nums[:mid])
        root.right =  Solution.sortedArrayToBST(self,nums[mid+1:])
        return root

力扣初级算法（Python）（二）：https://developer.aliyun.com/article/1538131

力扣初级算法（Python）（一）

1概述

2数组