Leetcode初级算法系列——记录

leetcode初级算法系列

数组

1.删除排序数组中的重复项

题目

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

题解

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        length = len(nums)
        if length > 1:
            pos = 1
            for i in range(1,length):
                if nums[i] == nums[i-1]:
                    continue
                else:
                    nums[pos] = nums[i]
                    pos += 1
            length = pos
        return length

要注意的一点是题目给的数组是排序过的数组，我们要做的就是使最后数组的前pos个元素都是 不同的，那么就是上面的方法，遍历比较相邻的元素，不同的话就将其值给nums[pos]。这样又能找到新的元素又能修改了前pos个元素，因为是排序过的数组，也就是两个相同元素交界处会触发else条件：[1,1,2,2,3,3]这种

2.买卖股票的最佳时机 II

题目

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

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

提示：

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

解答

解题思路
追求最大收益，那么在连续上涨的时候，例如D1～D3是连续上涨，那么我们的最大收益就是D3-D1的价格，和D2-D1 加 D3-D2是一样的，也就是连续的买了第二天卖；在连续跌跌时候，不买卖的情况收益最大，不亏就是赚。

策略是所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）。所以比较第二天是不是上涨，上涨就买了第二天卖，跌了就不交易，连续的上涨也就相当于上涨这几日的连续的买卖。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max = 0
        if len(prices) == 0:
            return 0
        for i in range(len(prices) - 1):
            if prices[i] <= prices[i+1]:
                max += prices[i+1] - prices[i]
        return max

3.旋转数组

题目

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

解答

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

4.存在重复元素

题目

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

输入: [1,2,3,1]
输出: true

示例 2:

输入: [1,2,3,4]
输出: false

示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

解答

解题思路

注释中的代码超时了，后采取方法是采用set进行数组去重然后比较长度。

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

5.只出现一次的数字

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

题解

我的题解：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        length = len(nums)
        setnums = set(nums)
        for i in setnums:
            if nums.count(i) == 1:
                return i

更优解：

题目提到了要求线性时间复杂度，并且不使用额外的空间来实现。我的代码不满足不使用额外空间的要求，那么看如下解法：

使用异或运算，因为相同的数异或后为0，数组中除了目标是出线一次，其他都是2次，a^a=0,a^a^b=b，所以可以依次异或运算，最后运算的结果就是答案。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for i in nums:
            result ^= i
        return result

6.两个数组的交集 II

题目

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

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

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

说明：

• 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
• 我们可以不考虑输出结果的顺序。

进阶：

• 如果给定的数组已经排好序呢？你将如何优化你的算法？
• 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
• 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

题解

首先有个比较容易迷惑的点是只要找出都在两者中出现的元素就行而且元素数量还可能大于1，顺序没有要求，也在说明中说了就是可能会理解出现偏差，看个例子就明白了：

输入：
[2,4,3]
[2,3,4,2,4,5,4]
输出：[2,4,3]

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) < len(nums2):
            minnums = nums1
            maxnums = nums2
        else:
            minnums = nums2
            maxnums = nums1
        res = []
        for i in minnums:
            for j in range(len(maxnums)):
                if i == maxnums[j]:
                    res.append(i)
                    maxnums.pop(j)
                    break
        return res

7.加一

题目

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 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]

提示：

1 <= digits.length <= 100
0 <= digits[i] <= 9

题解

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        numstr = ''
        result = []
        for i in digits:
            numstr += str(i)
        nums = int(numstr)
        res = nums + 1
        restr = str(res)
        for i in restr:
            result.append(int(i))
        return result

8.移动零

题目

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

题解

注意一点，循环遍历的时候从后向前，因为如果从前向后的话遇到0拿走到最后的话，后面的值会向前移动一位补位，从后向前就解决了这个问题。

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

9.两数之和

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题解

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N) 降低到 O(1)O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

时间复杂度：O(N)，其中 NN 是数组中的元素数量。对于每一个元素 x，我们可以 O(1)O(1) 地寻找 target - x。

空间复杂度：O(N)，其中 NN 是数组中的元素数量。主要为哈希表的开销。

10.有效的数独

题目

请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。

示例 1：

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'

题解

直接进行判断，可以解决但是不优雅

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # 分别提取出来每一列和每一个3X3的格子
        line = [[0 for i in range(9)] for j in range(9)]
        cell = [[0 for i in range(9)] for j in range(9)]            
        for i in range(9):
            for j in range(9):
                line[j][i] = board[i][j]
                k = i//3*3 + j//3
                q = i%3*3 + j%3
                cell[k][q] = board[i][j]
        for i in range(9):
            for j in range(9):
                if board[i][j] != "." and board[i].count(board[i][j]) > 1:
                    # 不为空而且这一行有不止一个这个数字
                    return False
                if line[i][j] != "." and line[i].count(line[i][j]) > 1:
                    # 不为空而且这一列有不止一个这个数字
                    return False
                if cell[i][j] != "." and cell[i].count(cell[i][j]) > 1:
                    # 不为空而且这一3X3有不止一个这个数字
                    return False
        return True