views 538 words

## 283. Move Zeroes

Topic: Array, Two pointer

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

• You must do this in-place without making a copy of the array. Minimize the total number of operations.

### Approach1

my, 第一个循环把非0的数都排前面, 第二个循环把剩下的数都为0

def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if nums:
tmp = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[tmp] = nums[i]
tmp += 1
for j in range(tmp,len(nums)):
nums[j] = 0

## 326. Power of Three

Topic: Math

Given an integer, write a function to determine if it is a power of three.

Example 1:

Input: 27
Output: true

Example 2:

Input: 0
Output: false

Example 3:

Input: 9
Output: true

Example 4:

Input: 45
Output: false

• Could you do it without using any loop / recursion?

### Approach1

def isPowerOfThree(n: int) -> bool:
if n == 0:
return False
while n % 3 == 0:
n //= 3
return n == 1:

### Approach2

def isPowerOfThree(n: int) -> bool:
if n<=0:
return False
else:
ans=math.log(n,3)
if n==3**round(ans):
return True
else:
return False

## 344. Reverse String

Topic: String, Two Pointer

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

### Approach1

my

def reverseString(s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
for i in range(len(s)//2):
s[i],s[len(s)-1-i] = s[len(s)-1-i],s[i]

### Approach2

neat, but slower

def reverseString(s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
# one step by python
s[:] = s[::-1]

## 350. Intersection of Two Arrays II

Topic: Array, Math, Bit Manipulation

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

### Approach1

def intersect(nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
l,r = 0,0
res = []
while len(nums1)>l and len(nums2) > r:
if nums1[l] > nums2[r]:
r += 1
elif nums1[l] < nums2[r]:
l += 1
else:
res.append(nums2[r])
l += 1
r += 1
return res

### Approach2

def intersect(nums1: List[int], nums2: List[int]) -> List[int]:
n1,n2=collections.Counter(nums1),collections.Counter(nums2)
print(n1,n2) # Counter({1: 2, 2: 2}), Counter({2: 2})
res=[]
for i in n1:
# print(i)  # 1 , 2
tmp=min(n1[i],n2[i]) # 0 , 2
print(tmp)
while tmp>0:
res.append(i)
tmp-=1
return res