167. Two Sum II - Input array is sorted (Easy)
Given an array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.
Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
first = 0
last = len(numbers)-1
while first<last:
sum = numbers[first]+numbers[last]
if sum<target:
first=first+1
elif sum>target:
last=last-1
else:
return [first+1, last+1]
return [-1,-1]
633. Sum of Square Numbers (Easy)
Given a non-negative integer c, decide whether there’re two integers a and b such that a2 + b2 = c.
class Solution:
def judgeSquareSum(self, c: int) -> bool:
low = 0
high = int(c**0.5)
while low <=high:
sum=low*low+high*high
if sum<c:
low+=1
elif sum>c:
high-=1
else:
return True
return False
345. Reverse Vowels of a String
Given a string s, reverse only all the vowels in the string and return it.
The vowels are ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’, and they can appear in both cases.
我的答案
class Solution:
def reverseVowels(self, s: str) -> str:
s=list(s)
high = len(s)-1
low = 0
while low<high:
str1 = s[low]
str2 = s[high]
if str1 in "aeiouAEIOU":
if str2 in "aeiouAEIOU":
s[low]=str2
s[high]=str1
low+=1
high-=1
else:
high-=1
else:
low+=1
return ''.join(s)
更好的答案，優點：
1.String的in操作不如set的in操作快
2.三個While比我的一個While減少了指派的過程
3.s[left], s[right] = s[right], s[left] py的交換方式。
class Solution:
def reverseVowels(self, s: str) -> str:
vowel_set = set(["a","e","i","o","u","A","E","I","O","U"])
s = list(s)
left = 0
right = len(s) - 1
while left < right:
while left < right and s[left] not in vowel_set:
left += 1
while left < right and s[right] not in vowel_set:
right -= 1
if s[right] in vowel_set and s[left] in vowel_set:
s[left], s[right] = s[right], s[left]
left +=1
right -=1
return "".join(s)
#notes
#check indexes BEFORE access
#iterate after while loops
#.join
#check for capitals
680. Valid Palindrome II (Easy)
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
我的答案：
class Solution:
def validPalindrome(self, s: str) -> bool:
def validHelper(s,low,high,delNum) -> bool:
if low >= high:
return delNum<=1
if delNum>1:
return False
elif s[low] == s[high]:
return validHelper(s,low+1,high-1,delNum)
else:
delNum+=1
return validHelper(s,low+1,high,delNum) or validHelper(s,low,high-1,delNum)
result = validHelper(s,0,len(s)-1,0)
return result
更好的答案：
class Solution:
def validPalindrome(self, s: str) -> bool:
rever = s[::-1]
if s == rever:
return True
else:
for i, j in enumerate(s):
if rever[i] != j:
# Tag 1
rever = rever[0:i] + rever[i+1:]
if rever == rever[::-1]:
return True
# Tag 2
s = s[0:i] + s[i+1:]
return s == s[::-1]
88. Merge Sorted Array
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
我的答案：
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p1 = m-1
p2 = n-1
p3 = m+n-1
while p1>=0 and p2>=0:
if nums1[p1]>nums2[p2]:
nums1[p3]=nums1[p1]
p1-=1
else:
nums1[p3]=nums2[p2]
p2-=1
p3-=1
while p2>=0:
nums1[p3]=nums2[p2]
p2-=1
p3-=1
更快的答案， 一個非常好的答題模範：
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
return self.threePtrs_spaceOpt(nums1, m, nums2, n)
#return self.threePtrs(nums1, m, nums2, n)
#return self.bruteForce(nums1, m, nums2, n)
# Algorithm: Space optimized three ptrs
# Intuition: Use "threePtrs" algorithm except we iterate nums1 and nums2 in backwards so that
# we will NOT need the extra data structure.
# We will insert a bigger number from the back of nums1 this time
def threePtrs_spaceOpt(self, nums1, m, nums2, n):
ptr1 = m-1
ptr2 = len(nums2) - 1
writePtr = len(nums1) - 1
while writePtr >= 0:
if ptr2 < 0 or (ptr1 >= 0 and nums1[ptr1] >= nums2[ptr2]):
nums1[writePtr] = nums1[ptr1]
ptr1 -= 1
else:
nums1[writePtr] = nums2[ptr2]
ptr2 -= 1
writePtr -= 1
# Algorithm: three pointers
# 1. Create "num1copy" list, and copy the numbers in num1 there
# 2. Create two pointers: ptr1 -> nums1copy, ptr2 -> nums2
# 3. Iterate over "nums1", compare nums1copty[ptr1] and nums2[ptr2], and insert into nums1[i]
#
# Time: O(n + m)
# Space: O(m)
def threePtrs(self, nums1, m, nums2, n):
# Copy nums1 into nums1copy
nums1copy = []
for i in range(m):
nums1copy.append(nums1[i])
ptr1 = 0 # nums1copy
ptr2 = 0 # nums2
for i in range(len(nums1)):
if ptr2 >= n or (ptr1 < m and nums1copy[ptr1] <= nums2[ptr2]):
nums1[i] = nums1copy[ptr1]
ptr1 += 1
else:
nums1[i] = nums2[ptr2]
ptr2 += 1
# Algorithm: built-in sort()
# 1. Put nums2 into the end of nums1
# 2. sort() nums1
#
# Time: O((n+m) log (n+m))
# Space: O(n)
def bruteForce(self, nums1, m, nums2, n):
for i in range(n):
nums1[i+m] = nums2[i]
return nums1.sort()
141. Linked List Cycle
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
return self.hasCycleSolver(head)
# Algorithm: two pointers
# 1.Create slow and fast pointer at head
# 2.Every time fast go 2 step, slow go 1 step.
# 3.Terminate when fast go to None(which means has no cycle) or fast meet the slow again (has cycle).
# Time:O(n)
# Space:O(1)
def hasCycleSolver(self,head:ListNode) -> bool:
slow = head
fast = head
# fast is not None is faster than fast != None
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False