数组专题:初始定义、运算、对撞指针、滑动窗口

01/28 11:33
阅读数 32

初始定义

在这里插入图片描述
解题思路:遇到0直接删除掉,在末尾添加一个0,定义两个变量,一个记录索引值,一个记录跟0比较的次数。

class Solution:
    def moveZeroes(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        index = 0
        opCount = 0
        while(opCount < n):
            if nums[index] == 0:
                nums.pop(index)
                nums.append(0)
            else:
                index +=1
            opCount += 1
#         return nums

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
定义四个变量:操作数,索引值,记录当前数出现的次数(不得超过2),当前连续出现的值

class Solution:
    def removeDuplicates(self, nums):
        n = len(nums)
        opCount = 0
        index = 0
        recodeNum = 0
        tempNum = nums[0]
        while(opCount <n):
            # 如果该数等于当前的连续值,且出现次数小于2,那么出现次数值加一,索引值加一
            if nums[index] == tempNum and recodeNum < 2:
                recodeNum += 1
                index += 1
            # 如果该数等于当前的连续值,且出现次数不小于2,根据索引从数组中剔除掉
            elif nums[index] == tempNum:
                nums.pop(index)
            # 如果该数不等于当前的连续值,更新当前的连续值,索引值加一,重新计算出现次数的值(一定先更新值再索引加一)
            else:
                tempNum = nums[index]
                recodeNum = 1
                index += 1
            opCount += 1
        return len(nums)

在这里插入图片描述

运算

在这里插入图片描述

class Solution:
    def sortColors(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        index = 0
        opCount = 0
        while(opCount < n):
            # 如果当前数是2,那么把2放到末尾
            if nums[index]==2:
                nums.pop(index)
                nums.append(2)
            else:
                # 如果当前数是0,那么,0放到开头
                if nums[index] == 0:
                    nums.pop(index)
                    nums.insert(0,0)
                index += 1
            opCount += 1

在这里插入图片描述
在这里插入图片描述

class Solution:
    def findKthLargest(self, nums, k):
        return sorted(nums)[len(nums)-k]

在这里插入图片描述

在这里插入图片描述
粗暴点。。。。。。。

class Solution:
    def merge(self, nums1, m, nums2, n):
        """
        Do not return anything, modify nums1 in-place instead.
        """
        tempList = sorted(nums1[:m] + nums2[:n])
        nums1.clear()
        for t in tempList:
            nums1.append(t)
#         print(nums1)

在这里插入图片描述

对撞指针

在这里插入图片描述
方法一:单索引查找

class Solution:
    def twoSum(self, numbers, target):
        length = len(numbers)
        for i in range(length):
            n = numbers[i]
            if n > target:
                return []
            try:
                return [numbers.index(n)+1, i + 1 + numbers[i+1:].index(target - n)+1]
            except:
                continue
        return []

在这里插入图片描述
方法二:使用所索引进行前后查找

class Solution:
    def twoSum(self, numbers, target):
        i = 0
        j = len(numbers) - 1
        while(i<j):
            temp = numbers[i] + numbers[j]
            if temp == target:
                return [i+1,j+1]
            elif temp > target:
                j-=1
            else:
                i+=1
        return []

在这里插入图片描述
在这里插入图片描述

class Solution:
    def isPalindrome(self, s):
        if s=='':
            return True
        allChar = '1234567890zxcvbnmasdfghjklpoiuytrewq'
        s = s.lower()
        newS = ''
        for ch in s:
            if ch in allChar:
                newS += ch
        return newS == newS[::-1]

在这里插入图片描述

在这里插入图片描述

class Solution:
    def reverseVowels(self, s):
        vowels = 'aoeiuAOEIU'
        i = 0
        j = len(s) - 1
        s = list(s)
        temp = ''
        while(i<j):
            if s[i].lower() in vowels and s[j].lower() in vowels:
                temp = s[i]
                s[i] = s[j]
                s[j] = temp
                i += 1
                j -= 1
            if s[i] not in vowels:
                i += 1
            if s[j] not in vowels:
                j -= 1
        result = ''
        for s_ in s:
            result+=s_
        return result

在这里插入图片描述

滑动窗口

在这里插入图片描述

class Solution:
    def minSubArrayLen(self, s, nums):
        
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            if nums[0] > s:
                return 1
            else:
                return 0
        if nums[0] >=s:
            return 1
        if sum(nums) < s:
            return 0
        
        temp = 0
        leftIndex = 0
        rightIndex = 1
        minLen = n
        temp = nums[leftIndex] + nums[rightIndex]
        while(rightIndex <n and leftIndex <n):
            # 比s大,左索引动,减去左值
            if temp >= s :
                if rightIndex - leftIndex + 1 <= minLen:
                    minLen = rightIndex - leftIndex + 1
                temp -= nums[leftIndex]
                leftIndex += 1
            # 比s小,右索引动,加上右值
            else:
                rightIndex += 1
                if rightIndex <n:
                    temp += nums[rightIndex]
        return minLen

在这里插入图片描述

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部