力扣初级算法(Python)(一)

简介: 力扣初级算法(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

相关文章
|
7天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
5天前
|
搜索推荐 C++ Python
Python排序算法大PK:归并VS快速,谁才是你的效率之选?
【7月更文挑战第13天】归并排序** 使用分治法,稳定且平均时间复杂度O(n log n),适合保持元素顺序和并行处理。
13 5
|
6天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
26 4
|
7天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
|
5天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
10 1
|
7天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
7天前
|
机器学习/深度学习 数据采集 算法
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
|
7天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机回归模型(LinearSVR算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机回归模型(LinearSVR算法)项目实战
|
7天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
|
7天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战