陣列專題：初始定義、運算、對撞指標、滑動視窗

初始定義

解題思路：遇到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