如何用vs2012做网站,上饶便宜的网站建设,注册公司注册资金多少为好,江西建网站做优化系列文章目录
【LeetCode算法题】各类基础排序算法的Python实现 【LeetCode算法题】数组经典题目分析 文章目录 系列文章目录前言一、二分查找#xff08;704#xff09;二、移除元素#xff08;27#xff09;三、有序数组的平方#xff08;977#xff09;四、长度最小…系列文章目录
【LeetCode算法题】各类基础排序算法的Python实现 【LeetCode算法题】数组经典题目分析 文章目录 系列文章目录前言一、二分查找704二、移除元素27三、有序数组的平方977四、长度最小的子数组209五、螺旋矩阵59总结 前言 本文对LeetCode中的数组类的经典题目进行分析题目序号分别为 704.二分查找27.移除元素977.有序数组的平方209.长度最小的子数组59.螺旋矩阵ll 一、二分查找704 Q给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。 分析有序数组查询特定值一般的折半查找思路。
class Solution(object):def search(self, nums, target)::type nums: List[int]:type target: int:rtype: intlow 0;high (len(nums) - 1);while (low high):mid (low high) // 2;if (nums[mid] target): return mid;if (nums[mid] target):low mid 1;if (nums[mid] target):high mid - 1;return -1;二、移除元素27 Q给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。 注不要使用额外的数组空间你必须仅使用 O(1) 额外空间并原地修改输入数组。 分析利用快慢指针的思维当 fast 所指的值等于 val仅向后移动 fast 当 fast 所指的值不等于 val 时 fast 与 slow 均向前移动一位且将 fast 所指的值赋给 slow 所指的地址。
class Solution(object):def removeElement(self, nums, val)::type nums: List[int]:type val: int:rtype: intslow 0;fast 0;while (fast len(nums)):if (nums[fast] ! val):nums[slow] nums[fast];slow 1;fast 1;return slow;三、有序数组的平方977 Q给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。 注初始整数数组存在负数 分析基本思路是先将数组元素平方然后再对数组进行排序这里的排序可以用各种排序算法参考【LeetCode算法题】各类基础排序算法的Python实现。但该思路一般会导致时间超时可以采用双指针思维创建一个空数组仅在数组两头才可能取最大值建立左右指针 left 与 right将大的添加到空数组头并将对应指针向里移一单位直到指针重合。
class Solution(object):def sortedSquares(self, nums)::type nums: List[int]:rtype: List[int]low 0;high len(nums) - 1;nums_ [];while (low high):if (nums[low]**2 nums[high]**2):nums_.insert(0, nums[high] ** 2);high high - 1;else:nums_.insert(0, nums[low] ** 2);low low 1;return nums_;四、长度最小的子数组209 Q给定一个含有 n 个正整数的数组和一个正整数 s 找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组并返回其长度。如果不存在符合条件的子数组返回 0。 分析基本思路是用两层 for 循环将所有可能的子数组遍历找到满足条件的最小长度该方式时间复杂度较高改进思路是减少循环次数双循环是同时限制了子数组的起止单循环仅限制子数组的止。核心思路是创建两个指针startend初始两指针均在数组头之后推进 end 指针当出现 sum(array[start, end]) val 时停止end后移开始后移 start直到达到最小满足条件的范围并记录之后继续后移 end 循环操作并每次取最小的范围直至 end 达到数组尾。
class Solution(object):def minSubArrayLen(self, target, nums)::type target: int:type nums: List[int]:rtype: inti 0;n len(nums);min_ n 1;total 0;for j in range(n): # 不直接使用sum(数组切片),可以加快速度.total nums[j];while (total target):min_ min(min_, j - i 1);total - nums[i];i 1;return 0 if min_ n 1 else min_;五、螺旋矩阵59 Q给定一个正整数 n生成一个包含 1 到 n^2 所有元素且元素按顺时针顺序螺旋排列的正方形矩阵。 分析这个题目的思路非常巧妙创建一个空的二维数组限制数组矩阵四边的起始位置按照顺时针依次填入数据。
class Solution(object):def generateMatrix(self, n)::type n: int:rtype: List[List[int]]mat [[0 for i in range(n)] for i in range (n)]w, s, a, d, m 1, n, 1, n, 0;len_ n**2;while(m len_):j_a a - 1;while(j_a d):mat[w - 1][j_a] m 1;m 1;j_a 1;w w 1;j_w w - 1;while (j_w s):mat[j_w][d - 1] m 1;m 1;j_w 1;d d - 1;j_s d ;while(j_s a):mat[s - 1][j_s - 1] m 1;m 1;j_s - 1;s s - 1;j_a s ;while (j_a w):mat[j_a - 1][a - 1] m 1;m 1;j_a - 1;a a 1;return mat 总结 数组除了较为经典的查找、排序算法外比较常用的思想还有以空间换时间、双指针等。
