905. Sort Array by Parity

Approach: In-place swap

This problem can be solved by sorting or two passing. But in-place swap comes with less space complexity. Set two pointers i, j, and every element below i should be even and every element above j should be odd. Instead of judge whether a number is odd or even by using x%2, bit-wise operation x&1 might be faster. Here is the code:

class Solution:    def sortArrayByParity(self, A: 'List[int]') -> 'List[int]':        i, j = 0, len(A)-1        while i < j:            if A[i]&1 and not A[j]&1:                 A[i], A[j] = A[j], A[i] # in this case, swap            if not A[i]&1: i+=1 # i continue move to next right            if A[j]&1: j-=1 # j continue move to next left        return A

766. Toeplitz Matrix

Approach1: Compare

For every element M[i][j], just compare it with M[i+1][j+1].

class Solution:    def isToeplitzMatrix(self, matrix: 'List[List[int]]') -> 'bool':        for i in range(len(matrix)-1):            for j in range(len(matrix[0])-1):                if matrix[i][j] != matrix[i+1][j+1]:                    return False        return True

More pythonic:

class Solution:    def isToeplitzMatrix(self, matrix: 'List[List[int]]') -> 'bool':       	return all(r1[:-1]==r2[1:] for r1, r2 in list(zip(m, m[1:])))

author:

In python, if not using numpy, zip is a good choice to manipulate matrix (not complex operations), and the speed is fast. In this case, if a matrix is Toeplitz, then its every pair of rows (

row_i

row_{i+1}

) from i=0 to the number of rows must have the property of

row_i[:-1]==row_{i+1}[1:]

. For example, row1 after deleting last element must equal to row2 after deleting first element, so for row2 and row3, row3 and row4, ect… zip(m, m[1:]) perfectly does the constructions of every pair of rows.

448. Find all numbers disappeared in an array

Approach 1: Mark missing index

It is important to notice that 1<= a[i]<=n(size of array). From this point, we know that an ideal array is [1,2,3…n], but the given array might miss some elements, and the task is to find them. If we see every element in the array as index, out job becomes finding missing index. To finish this, the idea is that we iterate this array, mark all value we have ever seen as negative(or other flag). Then in the second iteration, the unmarked positions will be the numbers disappeared in an array.

class Solution:    def findDisappearedNumbers(self, nums):        for num in nums:            nums[abs(num)-1] = -abs(nums[abs(num)-1])        return [i+1 for i in range(len(nums)) if nums[i]>0]

or:

class Solution:    def findDisappearedNumbers(self, nums):        seen = [0] * (len(nums) + 1)        for i in nums:            seen[i] = 1 #make missing index as 1         return [i for i in range(1,len(nums)+1) if not seen[i]]

Approach 2: Hash Table

The idea is that iterating [1,2,3,4…n] and checking whether the element in the hash table build from given array.

class Solution:    def findDisappearedNumbers(self, nums):        L, hashtable = len(nums), set(nums)        return [x for x in range(1,L+1) if x not in hashtable]

转载地址：http://fwksi.baihongyu.com/

你可能感兴趣的文章