前言
这次算法练习是数组类型简单练习，以后LeetCode的练习会根据不同tags进行展开，先easy再到medium，一步一步打好基础。
题目：905. Sort Array By Parity
题目链接
题目大意：给出一个非负整数的数组A，返回一个由A的所有偶数元素组成的数组，后跟A的所有奇数元素
例如：Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
题目解析：
1.首先最直接的方法就是把数组A中的奇数和偶数元素分开给两个不同的数组对象，然后偶数对象+奇数对象
2.two pointer的快速排序思想，判断首尾元素的就行是否满足题目的要求，否则交换位置
3.运用Python中的sorted方法更有效
方法1：简单粗暴，新建两个数组对象存放偶数元素和奇数元素，然后再相加
class Solution:
def sortArrayByParity(self, A):
"""
:type A: List[int]
:rtype: List[int]
"""
arr1 = []
arr2 = []
for a in A:
if a % 2 == 0:
arr1.append(a)
else:
arr2.append(a)
return arr1 + arr2
# return ([a for a in A if a % 2 == 0] + [b for b in A if b % 2 == 1]) 一行代码实现
时间复杂度：O(N) N代表len(A)
空间复杂度：O(N)
方法2：应用快速排序的思想进行对位交换，即需要指向头部和尾部两个指针，判断是否为奇数偶数，然后交换位置
class Solution:
def sortArrayByParity(self, A):
s, e = 0, len(A)-1
while s < e:
while A[s] % 2 == 0 and s < e:
s += 1
while A[e] % 2 == 1 and s < e:
e -= 1
A[s], A[e] = A[e], A[s]
return A
时间复杂度：O(N) N代表len(A)
空间复杂度：O(1)
方法3：应用python中sorted函数，这也是最简单且高效率的方法
class Solution:
def sortArrayByParity(self, A):
"""
:type A: List[int]
:rtype: List[int]
"""
return sorted(A, key=lambda x: x % 2)
时间复杂度：O(NlogN) N代表len(A)
空间复杂度：O(N)
题目：922. Sort Array By Parity II
题目链接
题目大意：给出一个非负整数的数组A，一半是奇数，一半是偶数，返回数组的元素如果为奇数，它的下标也是奇数，如果是偶数，它是下标也是偶数
例如：Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.
题目解析：
这个题目是由上面的题目延伸过来的，与前者不同的是，返回的数据是奇偶相间的方式排序的
所以思路就是先把奇偶元素分为两部分，然后按照奇偶下标进行排列，排列的方式：1.直接判断下标为奇偶；2.切片思想；
方法1：通过判断下标为奇偶性来排序
class Solution:
def sortArrayByParityII(self, A):
"""
:type A: List[int]
:rtype: List[int]
"""
odd = []
even = []
output = [None] * len(A)
for i in A:
if i % 2 == 0:
even.append(i)
else:
odd.append(i)
return [even.pop() if i % 2 == 0 else odd.pop() for i in range(len(A))]
时间复杂度：O(N)
空间复杂度：O(N)
方法2：切片的思想
class Solution:
def sortArrayByParityII(self, A):
"""
:type A: List[int]
:rtype: List[int]
"""
odd = []
even = []
output = [None] * len(A)
for i in A:
if i % 2 == 0:
even.append(i)
else:
odd.append(i)
output[::2] = even
output[1::2] = odd
return output
时间复杂度：O(N)
空间复杂度：O(N)
题目：914. X of a Kind in a Deck of Cards
题目链接
题目大意：一副写着整数的牌,当返回True时，即可以把这副牌分为1组或者多组，没每组的牌数量X>=2：
1.每组牌数量为X
2.每组牌的数量都相同
例1：
输入：[1,2,3,4,4,3,2,1]
输出：true
说明：可能的分区[1,1]，[2,2]，[3,3]，[4,4]
例2：
输入：[1,1,1,2,2,2,3,3]
输出：false
说明：没有可能的分区。
例3：
输入：[1]
输出：false
说明：没有可能的分区。
例4：
输入：[1,1]
输出：true
说明：可能的分区[1,1]
例5：
输入：[1,1,2,2,2,2]
输出：true
说明：可能的分区[1,1]，[2,2]，[2,2]
题目解析：
一开始觉得有点难理解，题目主要是讲，给出一个数组，是否能分为1-n组，每一组的数据必须相同，且每一组数据有X个，X>=2。
首先第一步，先统计给出的数组的元素重复数量，运用collections模块的Counter类来统计
接着，求出其中的最大公约数，如果大于1，则为True，反之False
class Solution:
def hasGroupsSizeX(self, deck):
"""
:type deck: List[int]
:rtype: bool
"""
from functools import reduce
import collections
def gcd(a, b):
while b:
a, b = b, a % b
return a
count = collections.Counter(deck).values()
return reduce(gcd, count) > 1
时间复杂度：O(N)
总结
由于最近项目有点赶，又加上自己懒，还是没有按时每日一道题目，以后还是需要自己坚持坚持坚持。
网友评论