基础算法题总结10--数组

数组

相关练习

LeetCode中相关的题目：

1. 两数之和: 哈希表，一次遍历
15. 三数之和：排序+双指针

题目详细描述

两数之和

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap={}  ## 使用哈希表，以空间换时间，只用遍历一遍数组
        for i,num in enumerate(nums):
            if hashmap.get(target - num) is not None: ## 字典遍历只需O(1)
                return [hashmap.get(target - num),i]
            hashmap[num] = i

三数之和

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        if n < 3:
            return []
        res = []
        nums.sort()  ## 需要先排序
        
        ## 枚举a
        for first in range(n):
            ## 需要枚举的值和上次不一样
            if first > 0 and nums[first] == nums[first-1]: 
                continue
            third = n-1  ## 先让c指向数组的最右端
            target = -nums[first]
            ## 枚举b
            for second in range(first+1,n):
                ## 需要枚举的值和上次不一样
                if second > first+1 and nums[second] == nums[second-1]:
                    continue
                ## b指针一直在c指针的左边，并且当两者的和一直大于target，那c指针一直后退
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                ## 当遍历结束没有找到，则就结束这次循环
                if second == third:
                    break
                ## 当找到之后，保存到结果的数组中
                if nums[second] + nums[third] == target:
                    res.append([nums[first],nums[second],nums[third]])
        
        return res

有效的括号

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1: ## 当数组的长度不是偶数的时候，一定有括号是单个的
            return False

        pairs = {    ## 字典存放括号对
            ")":"(",
            "}":"{",
            "]":"["
        }
        stack = []
        for ch in s:
            if ch in pairs: ## 当前括号是后面的一部分
                ## 如果栈为空或者栈顶和当前括号不匹配，那么不匹配
                if not stack or stack[-1] != pairs[ch]:
                    return False
                stack.pop() ## 匹配则出栈
            else:
                stack.append(ch) ## 前半括号入栈

        return not stack  ## 如果栈为空，则全部匹配，否则就有多余的括号未匹配

合并两个有序链表
第一个方法，递归 O(n+m) O(n+m)

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:  ## 链表为空的话，就不用合并，直接返回另一个链表
            return l2
        if l2 is None:
            return l1
        ## 判断哪个链表的头结点的值更小，递归的决定下一个添加到结果里的节点
        if l1.val < l2.val:  
            l1.next = self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1,l2.next)
            return l2

第二个方法，迭代 O(n+m) O(1)

class Solution:
    def mergeTwoLists(self, l1, l2):
        prehead = ListNode(-1)  ## 哨兵节点

        prev = prehead
        while l1 and l2:
            if l1.val <= l2.val: ## 将l1当前节点的节点接在pre节点的后面
                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

2. 两数相加

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = curr = ListNode()
        carry = val = 0
        while carry or l1 or l2: ## 判断是否还有进位或者链表还未遍历结束
            val = carry

            if l1: l1,val = l1.next, l1.val + val ## l1存在，则值相加，指针后移
            if l2: l2,val = l2.next, l2.val + val

            ## 经过计算，两个链表节点相加是两个节点的值加上进位值的和为val
            ## 那么新链表出的相应位置的数字是val%10
            ## 而新的进位是val/10
            ## divmod(a,b)函数返回的是(a//b,a%b)
            carry, val = divmod(val, 10)
            curr.next = ListNode(val) ## 添加新的节点并指向这个节点
            curr = curr.next 
        # if carry > 0: ## 如果链表结束，则链表后面需要添加一个节点，这个在上面放在了while循环中
        #     curr.next = ListNode(carry)
        return head.next ## 头节点为空，所以从后一位开始作为头结点

6. Z 字形变换:

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1: return s  ## 当只有一行的时候只用输出就好了

        res = ["" for _ in range(numRows)] ## numRow行的数组
        curRow = 0  ## 初始指针为0
        flag = -1  ## 作为开始和边界的标志，来判断是否开始转

        for c in s:
            res[curRow] += c
            if curRow == 0 or curRow == numRows - 1: ## 当刚开始或者已经完要转弯
                flag = -flag
            curRow += flag  ## 更改数组内小数组的坐标

        return "".join(res)

7. 整数反转

class Solution:
    def reverse(self, x: int) -> int:
        rev = 0
        y = abs(x)  ## 先取正
        while y != 0:
            pop = y % 10  ## 获取最后一个数字
            y = int(y/10) ## 获取剩下的数字
            ## 判断溢出，当rev>max/10,一定会溢出；或者rev=max/10,那么pop>7就会溢出
            ## 7 = max%10  -8= min%10
            if rev > (pow(2,31)-1)/10 or (rev > (pow(2,31)-1)/10 and pop > 7):
                return 0
            ## 判断溢出，当rev<min/10,一定会溢出；或者rev=min/10,那么pop<-8就会溢出
            if rev < -pow(2,31)/10 or (rev < -pow(2,31)/10 and pop < -8):
                return 0
            ## 
            rev = rev * 10 + pop ## 反转逐个求和
        
        return rev if x>0 else -rev ## 加符号

12. 整数转罗马数字

class Solution:
    def intToRoman(self, num: int) -> str:
        list1 = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
        list2 = ['M','CM','D','CD','C','XC','L','XL','X','IX','V','IV','I']
        result = ""
        length = len(list1)
        for i in range(length):
            while num >= list1[i]:  ## 贪心算法
                result += list2[i]
                num -= list1[i]
        return result

13. 罗马数字转整数:把一个小值放在大值的左边，就是做减法，否则为加法。

class Solution:
    def romanToInt(self, s: str) -> int:
        luoma = {
            'I':1,
            'V':5,
            'X':10,
            'L':50,
            'C':100,
            'D':500,
            'M':1000
        }
        i = 0
        value = 0
        length = len(s)
        while(i < length-1):
            if  luoma[s[i]] >= luoma[s[i+1]]:  ## 正常顺序做加法
                value += luoma[s[i]]
                i += 1
            else:  ## 否则把一个小值放在大值的左边，就是做减法
                value -= luoma[s[i]]
                i += 1
        if i == length-1: ## 最后一个数的时候，需要加上
            value += luoma[s[i]]
        return value

14. 最长公共前缀

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        length,count = len(strs[0]),len(strs)
        for i in range(length):
            c = strs[0][i]  ## 第一个字符的第i位，纵向扫描
            ## any()函数用于判断给定的可迭代参数 iterable 是否全部为 False，则返回 False，如果有一个为 True，则返回 True。
            if any(i==len(strs[j]) or strs[j][i] != c for j in range(1,count)):
                return strs[0][:i]
        return strs[0]

26. 删除有序数组中的重复项 双指针法

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        lens = len(nums)
        if lens == 0:
            return 0
        i = 0 ## 慢指针
        for j in range(0,lens): ## 快指针，当相等，则j不断增加
            if nums[i] != nums[j]: ## 遇到不重复项
                i += 1
                nums[i] = nums[j] ## ，将其赋值到i+1这个位置上
        return i+1

27. 移除元素 双指针法

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int: 
        i= 0  ## 慢指针
        n = len(nums)
        for j in range(n): ## 快指针
            if nums[j] != val: ## 当不是删除的元素，就转移到慢指针所在的位置
                nums[i] = nums[j]
                i += 1

        return i

28. 实现 strStr() 暴力破解法

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n,L = len(haystack),len(needle)

        for start in range(n - L + 1):
            if haystack[start:start+L] == needle:
                return start
        return -1

64. 最小路径和 动态规划
状态dp[i][j]表示的是从开始到(i,j)的最小路径和

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m,n = len(grid),len(grid[0])  ## 计算行数列数

        dp = [[0]*n for _ in range(m)] ## 里面乘的是列，外面的是行
        dp[0][0] = grid[0][0]  ## 初始化开始

        for j in range(1,n):  ## 填充第1列，每次前面和当前的和
            dp[0][j] =  dp[0][j-1] + grid[0][j]

        for i in range(1,m):  ## 填充第1行，每次前面和当前的和
            dp[i][0] = dp[i-1][0] + grid[i][0]
        
        for i in range(1,m):
            for j in range(1,n):
                ## 最小的和当前的和
                dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]  
        
        return dp[m-1][n-1]  ## 返回最后一个值

62. 不同路径
状态dp[i][j]表示的是从左上角走到(i,j)的路径数量

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n] + [[1] + [0]*(n-1) for _ in range(m-1)]

        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[m-1][n-1]