LeetCode day11

3 minutes read
LeetCode
#LeetCode
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

Follow up:

  • 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 -w562

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.

Follow up:

  • 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

时间复杂度：O(n+m) 空间复杂度：O(n+m)