企业官网建设流程全解析

wordpress个人站,绍兴seo公司,做一个平台网站的预算,wordpress小米主题LeekCode面试经典150题之删除有序数组中的重复项 本篇博文我将针对删除有序数组中的重复项问题#xff08;I,II)#xff0c;给出一些解决的方法。两个问题我将分开进行讲解。有些方法是我自己想的#xff08;所以有不合理的地方很乐意与大家一起讨论#xff09;#xff0…LeekCode面试经典150题之删除有序数组中的重复项本篇博文我将针对删除有序数组中的重复项问题I,II)给出一些解决的方法。两个问题我将分开进行讲解。有些方法是我自己想的所以有不合理的地方很乐意与大家一起讨论有些方法是参照的之前的博文中的。本片博文我们还引进了一种新的方法快慢指针法一、题目1 题目描述给你一个 非严格递增排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。考虑 nums 的唯一元素的数量为 k。去重后返回唯一元素的数量 k。nums 的前 k 个元素应包含 排序后 的唯一数字。下标 k - 1 之后的剩余元素可以忽略。分析这是移到删除元素的题目。我们可以采用遍历数组然后直接求每个元素的出现次数将出现多次的元素删掉。这种方法我在这个题目里面不给出具体的代码。在下面的拿到题目里面会具体给出代码。可以进行参照。还可以使用之前的博文中用到的栈的思想来解决之前用到栈的思想解决的问题还可以用我们今天重点要介绍的快慢指针法。接下来我会一一介绍。1.栈的思想的解决方法defremoveDuplicates(self,nums): :type nums: List[int] :rtype: int stack_pointer0lengthlen(nums)foriinrange(length-1):ifnums[i]!nums[i1]:nums[stack_pointer]nums[i]stack_pointer1ifilength-2:nums[stack_pointer]nums[i1]returnstack_pointer1这里我们判断数组中的元素如果当前元素和后面那个元素不一样话我们就把当前的元素压入栈中如果相同的话会直接跳到后一个元素。若现在已经是最后一个元素的话就直接将其压入栈中。这里我想在进一步解释一下为什么是最后一个元素就可以直接压入栈中因为在倒数第二个元素的时候我们已经判断了倒数第二个数和倒数第一个数是否相等如果不相等的话那么这两个数都应该压入栈中那么到最后一个数的时候直接将它压入栈中是没有问题的。如果他们不相等那么我们不会将倒数第二数压入栈中而是会直接来到倒数第一个数所以将倒数第一个压入栈中也是合理的。其实从上面我们可以看出为我们在每次压入的都是一串相同的数中的最后一个。2.快慢指针法defremoveDuplicates(self,nums): :type nums: List[int] :rtype: int slow,fast0,1whilefastlen(nums):ifnums[slow]!nums[fast]:slow1nums[slow]nums[fast]fast1returnslow1在这个方法里面我们给定快慢两个指针。快的指针总是往后移动直至移动到和当前慢指针所指的数不一样的时候我们就将慢指针往后移动一个单位再将这个不一样的数填入到慢指针当前所指的位置。然后快指针继续往后移动重复这个操作。最后返回的数组长度就是慢指针1。这是因为慢指针从零开始所以1才是数组的真实长度。二、题目二题目描述给你一个有序数组 nums 请你 原地 删除重复出现的元素使得出现次数超过两次的元素只出现两次 返回删除后数组的新长度。不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。分析这个题目和刚才那个题目的思路基本一致但是又比之前的那个题目更难了。这里我们需要控制最多能够重复的次数并且必须要在原地进行要在额外空间为 O(1) 下完成。下面我将介绍四种方法。除了第一种方法比较暴力其他的方法的核心思想其实是共通的。当然这里也包含了栈的方法和快慢指针法供大家参考学习。1.暴力方法defremoveDuplicates(self,nums): :type nums: List[int] :rtype: int foriinnums:whilenums.count(i)2:nums.remove(i)returnlen(nums)这种方法效率很低但是也能够完成题目的要求。核心思想就是对数组中的每个数进行计数如果数量大于2就删除数组中碰到的第一个这个数。用这种方式就能够达到题目的要求了。如果要求的数量不是2的话我们直接将while nums.count(i)2这里的2改成要求的数量即可。2.快慢指针法defremoveDuplicates(self,nums): :type nums: List[int] :rtype: int iflen(nums)2:returnlen(nums)slow1fast2whilefastlen(nums):ifnums[fast]!nums[slow-1]:slow1nums[slow]nums[fast]fast1returnslow1这里和之前不一样的是两个指针要从1和2开始然后我们需要判断快指针所指的和慢指针的前面那个是否相同如果相同说明快指针后面可能还有和它相同的因此我们要将快指针后移直至快指针指向的不是和慢指针前面的数相同的数我们就将慢指针后移然后将快指针当前所指的数赋给慢指针。后面重复此流程。这里说一下为什么这样做能够控制每个数重复不超过两次 因为数组是有序的因此要想快指针与慢指针之前的指针指向的数是相同的除非慢指针当前所指的数也是相同的。这样慢指针加上慢指针前面的那个数者两个是六十相同的了那么慢指针的下一个位置需要指向一个不一样的数这个数我们通过快指针找到了。在这种方法下如果我们要控制的最多出现次数变化的话我们可以通过改变快慢指针的初始位置和每次与快指针比较的数的位置来实现。3.栈的方法defremoveDuplicates(self,nums): :type nums: List[int] :rtype: int stack_pointer1forxinnums[2:]:ifx!nums[stack_pointer-1]:stack_pointer1nums[stack_pointer]xreturnmin(stack_pointer1,len(nums))在栈的方法下我们不需要对于数组的零号元素进行判断因为不论再怎样它都会留下。因此我们的栈顶指针要从1开始。然后我们要判断从数组的第三个位置开始是否与当前栈顶指针指向的前一个位置的数相同如果相同那我们找到数组的下一个位置直至找到与其不同的数我们就把它放到栈顶指针的下一个位置。然后我们最后返回当前栈顶指针1和数组长度这两者之间的最小值。4.计数法defremoveDuplicates(self,nums): :type nums: List[int] :rtype: int indexcount1foriinrange(1,len(nums)):ifnums[i]nums[i-1]:count1else:count1ifcount2:nums[index]nums[i]index1returnindex对于这类问题我们很容易想到要对每个数字重复的次数进行计数。根据重复次数的不同对数字进行不同的操作。初始计数器为1如果当前的数字和后一个数字相同计数器加一。若当前的次数小于等于2的话会继续往将当前的数赋给index指针所指的数并且index指针后移。赋值给index指针的数都是确定了会保留下来的数如果大于计数器大于2的话不会管它会继续往后读取数字直至读到新的相邻的相同的数重复上面的操作。因为每次给index位置赋值的时候index都会往后移动所以最后返回index即可。以上就是本次博文的所有内容如果有什么问题欢迎来和我讨论。