【数据结构与算法】之数组系列-20240113

---

一、66. 加一

简单

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

示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：
输入：digits = [0]
输出：[1]

思路：
一次for循环解决问题
从数组尾部遍历
如果遇到数字不是9就+1，并返回
如果是9，则将当前数字置0，并进入下一轮循环
考虑特殊情况：9999
此时需要检查最后一次for循环的数字是不是0
即digits[0]是否为0，如果是0，则遇到了特殊情况
此时需要在数组最前面加一个数字1，然后返回即可

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits)-1, -1, -1):  #从数组尾部进行遍历
            if digits[i] is not 9:      #如果遇到数字不是9就+1，并且返回
                digits[i] += 1
                return digits
            else:
                digits[i] = 0           #如果遇到是9，则将当前数字置为0，并进入下一轮循环
                if digits[0] == 0:
                    digits.insert(0, 1)
                    return digits

s=Solution()
dogits = [9,9,9,9]
print(s.plusOne((dogits)))

二、121. 买卖股票的最佳时机

简单
相关标签
相关企业
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

首先让prices[0]表示当天购买的最小值，
遍历prices，如果i小于当前prices[0]，更新最小值
判断：如果prices中价格i-最小值min大于max，更新最大值max

def func7(prices):
    min = prices[0]
    max = 0
    for i in prices:
        if i < min:
            min = i
        if i - min > max:
            max = i - min
    return max

三、136. 只出现一次的数字

简单
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：
输入：nums = [2,2,1]
输出：1

示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：
输入：nums = [1]
输出：1

思路：使用位运算种的异或运算 任何数和自己做异或运算结果为0 任何数和0做异或运算结果为1 异或运算种，满足交换律和结合率

class Solution:
    def singleNumber(self, nums):
        return reduce(lambda x, y: x ^ y, nums)


s = Solution()
nums = [4, 1, 2, 1, 2]
print(s.singleNumber(nums))

四、268. 丢失的数字

简单

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
print(sum(range(len(nums) + 1)) - sum(nums))

五、350. 两个数组的交集 II

简单

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

🧠 解题思路
通过题意，寻找两数组是否有相同项，并且提示中说可以不要求交集的顺序。
既然如此，我们便可以先行将数组排序，方便我们查找，然后正式流程如下：
创建一个指针 i指向 nums1 数组首位，指针 j 指向 nums2 数组首位。
创建一个临时栈，用于存放结果集。
开始比较指针 i 和指针 j 的值大小，若两个值不等，则数字小的指针，往右移一位。
若指针 i 和指针 j 的值相等，则将交集压入栈。
若 nums1 或 nums2 有一方遍历结束，代表另一方的剩余值，都是唯一存在，且不会与之产生交集的。

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


s = Solution()
nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(s.interect(nums1, nums2))

---