Valid Palindrome
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
if not s:
return True
start, end = 0, len(s) - 1
while start < end:
while start < end and not self.isChar(s[start]):
start += 1
while start < end and not self.isChar(s[end]):
end -= 1
if start < end and s[start].lower() != s[end].lower():
return False
start += 1
end -= 1
return True
def isChar(self, c):
return c >= 'a' and c <= 'z' or c >= 'A' and c <= 'Z' or c >= '0' and c <= '9'
Window Sum
" def winSum(self, nums, k):
# Write your code here
n = len(nums)
if n<k or k<=0:
return []
sums = [0] * (n - k + 1)
for i in xrange(k):
sums[0] += nums[i]
for i in xrange(1, n-k+1):
sums[i] = sums[i-1] - nums[i-1] + nums[i+k-1]
return sums"
move zeros
" def moveZeroes(self, nums):
# Write your code here
start, end = 0, 0
while end < len(nums):
if nums[end]:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end += 1
return nums
"
Remove Duplicate Numbers in Array
" def deduplication(self, nums):
# Write your code here
if not nums:
return 0
nums.sort()
left, right = 1, 1
while left < len(nums):
if nums[left] != nums[left-1]:
nums[right] = nums[left]
right += 1
left += 1
return right"
Two Sum - Input array is sorted
" def twoSum(self, nums, target):
# Write your code here
left, right = 0, len(nums)-1
while left < right:
if nums[left] + nums[right] == target:
return [left+1, right+1]
elif nums[left] + nums[right] < target:
left += 1
elif nums[left] + nums[right] > target:
right -= 1
return [-1, -1]"
Minimum Size Subarray Sum
"def minimumSize(self, nums, s):
# write your code here
n = len(nums)
if n==0: return -1
left = right = total = 0
ans = n+1
while right < n:
while right < n and total < s:
total += nums[right]
right += 1
if total < s: break
while left < right and total >= s:
total -= nums[left]
left += 1
ans = min(ans, right - left + 1)
if ans ==n+1: return -1
else:
return ans
"
Trapping Rain Water
" if not height or len(height) < 3:
return 0
left, right = 0, len(height)-1
volume = 0
l_max, r_max = height[left], height[right]
while left< right:
l_max, r_max = max(l_max, height[left]), max(r_max, height[right])
if l_max <= r_max:
volume += l_max - height[left]
left += 1
else:
volume += r_max - height[right]
right -= 1
return volume"
Two Sum - Less than or equal to target
class Solution:
# @param nums {int[]} an array of integer
# @param target {int} an integer
# @return {int} an integer
def twoSum5(self, nums, target):
# Write your code here
l, r = 0, len(nums)-1
cnt = 0
nums.sort()
while l < r:
value = nums[l] + nums[r]
if value > target:
r -= 1
else:
cnt += r - l
l += 1
return cnt
3sum
class Solution:
"""
@param numbersbers : Give an array numbersbers of n integer
@return : Find all unique triplets in the array which gives the sum of zero.
"""
def threeSum(self, numbers):
# write your code here
numbers.sort()
res = []
for i in xrange(len(numbers) - 2):
if i > 0 and numbers[i] == numbers[i-1]:
continue
l, r = i+1, len(numbers) - 1
while l < r:
s = numbers[i] + numbers[l] + numbers[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
res.append((numbers[i], numbers[l], numbers[r]))
while l < r and numbers[l] == numbers[l+1]:
l += 1
while l < r and numbers[r] == numbers[r-1]:
r -= 1
l += 1
r -= 1
return res
4sum
class Solution:
"""
@param numbersbers : Give an array numbersbersbers of n integer
@param target : you need to find four elements that's sum of target
@return : Find all unique quadruplets in the array which gives the sum of
zero.
"""
def fourSum(self ,numbers, target):
# write your code here
res = []
numbers.sort()
for i in xrange(0, len(numbers)-3):
if i > 0 and numbers[i] == numbers[i-1]:
continue
for j in xrange(i+1, len(numbers)-2):
if j != i+1 and numbers[j] == numbers[j-1]:
continue
tmp = target - numbers[i] - numbers[j]
left, right = j+1, len(numbers)-1
while left < right:
if numbers[left] + numbers[right] < tmp:
left += 1
elif numbers[left] + numbers[right] > tmp:
right -= 1
else:
res.append([numbers[i], numbers[j], numbers[left], numbers[right]])
right -= 1
left += 1
while left<right and numbers[left] == numbers[left-1]:
left += 1
while left<right and numbers[right] == numbers[right+1]:
right -=1
return res
class Solution:
# @return a list of lists of length 4, [[val1,val2,val3,val4]]
def fourSum(self, num, target):
numLen, res, dict = len(num), set(), {}
if numLen < 4: return []
num.sort()
for p in range(numLen):
for q in range(p+1, numLen):
if num[p]+num[q] not in dict:
dict[num[p]+num[q]] = [(p,q)]
else:
dict[num[p]+num[q]].append((p,q))
for i in range(numLen):
for j in range(i+1, numLen-2):
T = target-num[i]-num[j]
if T in dict:
for k in dict[T]:
if k[0] > j: res.add((num[i],num[j],num[k[0]],num[k[1]]))
return [list(i) for i in res]