devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：IT小白 | 2024-05-13 00:50:25

赞

踩

leetcode代码随想录

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

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

目录

数组理论基础

704. 二分查找

27. 移除元素

977.有序数组的平方

209.长度最小的子数组

59.螺旋矩阵II

总结

数组理论基础

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

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

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

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

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

704. 二分查找

力扣题目链接

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

示例 1:

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

示例 2:

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

提示：

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。
  1. class Solution(object):
  2.     def search(self, nums, target):
  3.         """
  4.         :type nums: List[int]
  5.         :type target: int
  6.         :rtype: int
  7.         """
  8.         if target < nums[0] or target > nums[len(nums) - 1]:
  9.             return -1
  10.         left = 0
  11.         right = len(nums) - 1
  12.         while left <= right:
  13.             mid = int((right + left) / 2)
  14.             if nums[mid] == target:
  15.                 return mid
  16.             elif nums[mid] > target:
  17.                 # 因为当前这个nums[middle]一定不是target，
  18.                 # 那么接下来要查找的左区间结束下标位置就是 middle - 1
  19.                 right = mid - 1
  20.             elif nums[mid] < target:
  21.                 # 当前的mid一定不是target,所以左边的要+1
  22.                 left = mid + 1
  23.         return -1
  24.  
  25.  
  26. class Solution2:
  27.     def search2(self, nums, target):
  28.         left, right = 0, len(nums)  # 定义target在左闭右开的区间里，即：[left, right)
  29.  
  30.         while left < right:  # 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
  31.             middle = left + (right - left) // 2
  32.  
  33.             if nums[middle] > target:
  34.                 right = middle  # target 在左区间，在[left, middle)中
  35.             elif nums[middle] < target:
  36.                 left = middle + 1  # target 在右区间，在[middle + 1, right)中
  37.             else:
  38.                 return middle  # 数组中找到目标值，直接返回下标
  39.         return -1  # 未找到目标值
  40.  
  41.  
  42. if __name__ == '__main__':
  43.     sol = Solution()
  44.     a = [2, 7, 9, 11, 15]
  45.     t = 13
  46.     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]

  1. # 暴力简单解法：这个时间复杂度是 O(n + nlogn)
  2. # 可以说是O(nlogn)的时间复杂度
  3. class Solution(object):
  4.     def sortedSquares(self, nums):
  5.         """
  6.         :type nums: List[int]
  7.         :rtype: List[int]
  8.         """
  9.         for i in range(len(nums)):
  10.             nums[i] = nums[i]*nums[i]
  11.         nums.sort()
  12.         return nums
  13.  
  14. # 双指针法
  15. # 数组其实是有序的， 只不过负数平方之后可能成为最大数了。
  16. # 那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
  17. # 此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
  18. # 定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
  19. # 如果nums[i] * nums[i] < nums[j] * nums[j] 那么result[k--] = nums[j] * nums[j];
  20. # 如果nums[i] * nums[i] >= nums[j] * nums[j] 那么result[k--] = nums[i] * nums[i];
  21. # 复杂度为O(n)
  22.  
  23.  
  24. class Solution2(object):
  25.     def sortedSquares2(self, nums):
  26.         i = 0
  27.         j = len(nums)-1
  28.         k = len(nums)-1
  29.         result = [0]*len(nums)
  30.         while i <= j:
  31.             # 先取到两边的平分值，因为是最大的数
  32.             left, right = nums[i] ** 2, nums[j] ** 2
  33.             # 然后将大的数放到数组的最后
  34.             if left > right:
  35.                 result[k] = left
  36.                 i += 1
  37.             else:
  38.                 result[k] = right
  39.                 j -= 1
  40.             # 不断的将result数组填满
  41.             k -= 1
  42.         return result
  43.  
  44.  
  45. if __name__ == '__main__':
  46.     sol = Solution()
  47.     a = [-4, -1, 0, 3, 10]
  48.     # print(sol.sortedSquares(a))
  49.     sol2 = Solution2()
  50.     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

  1. # 链接：https://leetcode.cn/problems/minimum-size-subarray-sum
  2.  
  3. # 暴力解法
  4. class Solution(object):
  5.     def minSubArrayLen(self, target, nums):
  6.         """
  7.         :type target: int
  8.         :type nums: List[int]
  9.         :rtype: int
  10.         """
  11.         # 保存 最小长度
  12.         result = 100000
  13.         for i in range(len(nums)):
  14.             minlen = 0
  15.             for j in range(i, len(nums)):
  16.                 minlen += nums[j]
  17.                 if minlen >= target:
  18.                     sublen = j - i + 1
  19.                     result = result if result < sublen else sublen
  20.                     break
  21.         if result == 100000:
  22.             return 0
  23.         else:
  24.             return result
  25.  
  26.  
  27. class Solution2(object):
  28.     def minSubArrayLen2(self, target, nums):
  29.         """
  30.         :type target: int
  31.         :type nums: List[int]
  32.         :rtype: int
  33.         """
  34.         # 保存 最小长度
  35.         result = 100000
  36.         for i in range(len(nums)):
  37.             minlen = 0
  38.             for j in range(i, len(nums)):
  39.                 minlen += nums[j]
  40.                 if minlen >= target:
  41.                     sublen = j - i + 1
  42.                     result = result if result < sublen else sublen
  43.                     break
  44.         if result == 100000:
  45.             return 0
  46.         else:
  47.             return result
  48.  
  49.  
  50. if __name__ == '__main__':
  51.     sol2 = Solution2()
  52.     a = [2, 3, 1, 2, 4, 3]
  53.     t = 7
  54.     print(sol2.minSubArrayLen2(t, a))

59.螺旋矩阵II

力扣题目链接(opens new window)

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

示例:

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

  1. # 模拟顺时针画矩阵的过程:
  2. # 填充上行从左到右
  3. # 填充右列从上到下
  4. # 填充下行从右到左
  5. # 填充左列从下到上
  6.  
  7. class Solution(object):
  8.     def generateMatrix(self, n):
  9.         """
  10.         :type n: int
  11.         :rtype: List[List[int]]
  12.         """
  13.         nums = [[0]*n for _ in range(n)]
  14.         startx, starty = 0, 0
  15.         loop, mid = n//2, n//2   # 迭代的次数。矩阵的中心点
  16.         count = 1
  17.  
  18.         for offset in range(1,loop+1):
  19.             for i in range(starty, n - offset):  # 从左至右，左闭右开
  20.                 nums[startx][i] = count
  21.                 count += 1
  22.             for i in range(startx, n - offset):  # 从上至下
  23.                 nums[i][n - offset] = count
  24.                 count += 1
  25.             for i in range(n - offset, starty, -1):  # 从右至左
  26.                 nums[n - offset][i] = count
  27.                 count += 1
  28.             for i in range(n - offset, startx, -1):  # 从下至上
  29.                 nums[i][starty] = count
  30.                 count += 1
  31.             startx += 1  # 更新起始点
  32.             starty += 1
  33.  
  34.         if n % 2 != 0:  # n为奇数时，填充中心点
  35.             nums[mid][mid] = count
  36.         return nums
  37.  
  38.  
  39. if __name__ == '__main__':
  40.     sol = Solution()
  41.     print(sol.generateMatrix(4))

总结

参考链接：

https://programmercarl.com/

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/561227
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号