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

01/28 11:33

#### 初始定义

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


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