Leetcode 3437
Given an integer n, an alternating permutation is a permutation of the first n positive integers such that no two adjacent elements are both odd or both even.
Return all such alternating permutations sorted in lexicographical order.
Example 1:
Input: n = 4
Output: [[1,2,3,4],[1,4,3,2],[2,1,4,3],[2,3,4,1],[3,2,1,4],[3,4,1,2],[4,1,2,3],[4,3,2,1]]
Example 2:
Input: n = 2
Output: [[1,2],[2,1]]
Example 3:
Input: n = 3
Output: [[1,2,3],[3,2,1]]
Constraints:
1 <= n <= 10
此题正常情况是靠模拟就能过，但是由于Leetcode对Ruby进行判定的机制很不友好，基础内存都是206MB往上走，导致n等于10的时候，内存直接爆了。但是Python是没有问题的，如下是相同算法的Ruby和Python实现。
这是Ruby
# @param {Integer} n
# @return {Integer[][]}
def permute(n)
m = (1..n).to_a.permutation(n).to_a
ans = []
m.each do |a|
flag = false
a.each_with_index do |a1, i|
if i < a.length - 1 && (a1 % 2) == (a[i + 1] % 2)
flag = true
break
end
end
unless flag
ans << a
end
end
ans
end
这是Python
from itertools import permutations
class Solution:
def permute(self, n: int) -> List[List[int]]:
p = permutations([i for i in range(1,n+1)])
ans = []
for p1 in p:
flag = False
for i in range(len(p1)):
if i < len(p1) - 1 and (p1[i]%2) == (p1[i+1]%2):
flag = True
break
if not flag:
ans.append(p1)
return ans
