您现在的位置是：首页 >技术杂谈 >【leetcode刷题总结】——代码随想录（数组总结）网站首页技术杂谈

【leetcode刷题总结】——代码随想录（数组总结）

Lingxw_w 2023-07-07 16:00:02
简介【leetcode刷题总结】——代码随想录（数组总结）

代码随想录按照数组-> 链表-> 哈希表->字符串->栈与队列->树->回溯->贪心->动态规划->图论->高级数据结构，再从简单刷起，做了几个类型题目之后，再慢慢做中等题目、困难题目。

以下是个人刷题总结，官方网站 https://programmercarl.com/

目录

数组理论基础

704. 二分查找

27. 移除元素

977.有序数组的平方

209.长度最小的子数组

59.螺旋矩阵II

总结

数组理论基础

数组是非常基础的数据结构，在面试中，考察数组的题目一般在思维上都不难，主要是考察对代码的掌控能力

也就是说，想法很简单，但实现起来 可能就不是那么回事了。

首先要知道数组在内存中的存储方式，这样才能真正理解数组相关的面试题

数组是存放在连续内存空间上的相同类型数据的集合。

数组可以方便的通过下标索引的方式获取到下标下对应的数据。

704. 二分查找

力扣题目链接

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1

提示：

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target < nums[0] or target > nums[len(nums) - 1]:
            return -1
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = int((right + left) / 2)
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                # 因为当前这个nums[middle]一定不是target，
                # 那么接下来要查找的左区间结束下标位置就是 middle - 1
                right = mid - 1
            elif nums[mid] < target:
                # 当前的mid一定不是target,所以左边的要+1
                left = mid + 1
        return -1


class Solution2:
    def search2(self, nums, target):
        left, right = 0, len(nums)  # 定义target在左闭右开的区间里，即：[left, right)

        while left < right:  # 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            middle = left + (right - left) // 2

            if nums[middle] > target:
                right = middle  # target 在左区间，在[left, middle)中
            elif nums[middle] < target:
                left = middle + 1  # target 在右区间，在[middle + 1, right)中
            else:
                return middle  # 数组中找到目标值，直接返回下标
        return -1  # 未找到目标值


if __name__ == '__main__':
    sol = Solution()
    a = [2, 7, 9, 11, 15]
    t = 13
    print(sol.search(a, t))

27. 移除元素

力扣题目链接

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

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

977.有序数组的平方

力扣题目链接(opens new window)

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

# 暴力简单解法：这个时间复杂度是 O(n + nlogn)
# 可以说是O(nlogn)的时间复杂度
class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        for i in range(len(nums)):
            nums[i] = nums[i]*nums[i]
        nums.sort()
        return nums

# 双指针法
# 数组其实是有序的， 只不过负数平方之后可能成为最大数了。
# 那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
# 此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
# 定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
# 如果nums[i] * nums[i] < nums[j] * nums[j] 那么result[k--] = nums[j] * nums[j];
# 如果nums[i] * nums[i] >= nums[j] * nums[j] 那么result[k--] = nums[i] * nums[i];
# 复杂度为O(n)


class Solution2(object):
    def sortedSquares2(self, nums):
        i = 0
        j = len(nums)-1
        k = len(nums)-1
        result = [0]*len(nums)
        while i <= j:
            # 先取到两边的平分值，因为是最大的数
            left, right = nums[i] ** 2, nums[j] ** 2
            # 然后将大的数放到数组的最后
            if left > right:
                result[k] = left
                i += 1
            else:
                result[k] = right
                j -= 1
            # 不断的将result数组填满
            k -= 1
        return result


if __name__ == '__main__':
    sol = Solution()
    a = [-4, -1, 0, 3, 10]
    # print(sol.sortedSquares(a))
    sol2 = Solution2()
    print(sol2.sortedSquares2(a))

209.长度最小的子数组

力扣题目链接(opens new window)

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

提示：

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

# 链接：https://leetcode.cn/problems/minimum-size-subarray-sum

# 暴力解法
class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        # 保存 最小长度
        result = 100000
        for i in range(len(nums)):
            minlen = 0
            for j in range(i, len(nums)):
                minlen += nums[j]
                if minlen >= target:
                    sublen = j - i + 1
                    result = result if result < sublen else sublen
                    break
        if result == 100000:
            return 0
        else:
            return result


class Solution2(object):
    def minSubArrayLen2(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        # 保存 最小长度
        result = 100000
        for i in range(len(nums)):
            minlen = 0
            for j in range(i, len(nums)):
                minlen += nums[j]
                if minlen >= target:
                    sublen = j - i + 1
                    result = result if result < sublen else sublen
                    break
        if result == 100000:
            return 0
        else:
            return result


if __name__ == '__main__':
    sol2 = Solution2()
    a = [2, 3, 1, 2, 4, 3]
    t = 7
    print(sol2.minSubArrayLen2(t, a))

59.螺旋矩阵II

力扣题目链接(opens new window)

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

# 模拟顺时针画矩阵的过程:
# 填充上行从左到右
# 填充右列从上到下
# 填充下行从右到左
# 填充左列从下到上

class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        nums = [[0]*n for _ in range(n)]
        startx, starty = 0, 0
        loop, mid = n//2, n//2   # 迭代的次数。矩阵的中心点
        count = 1

        for offset in range(1,loop+1):
            for i in range(starty, n - offset):  # 从左至右，左闭右开
                nums[startx][i] = count
                count += 1
            for i in range(startx, n - offset):  # 从上至下
                nums[i][n - offset] = count
                count += 1
            for i in range(n - offset, starty, -1):  # 从右至左
                nums[n - offset][i] = count
                count += 1
            for i in range(n - offset, startx, -1):  # 从下至上
                nums[i][starty] = count
                count += 1
            startx += 1  # 更新起始点
            starty += 1

        if n % 2 != 0:  # n为奇数时，填充中心点
            nums[mid][mid] = count
        return nums


if __name__ == '__main__':
    sol = Solution()
    print(sol.generateMatrix(4))

总结

参考链接：

https://programmercarl.com/

图是 代码随想录知识星球成员：海螺人

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐