Leetcode 667. Beautiful Arrangement II

Posted on | | 阅读数
Words count in article: 356 | Reading time ≈ 1

Quesiton

Solution1

对于一个序列[1,2,3,4]:

从index 1开始逆转序列 [1,4,3,2]，k = 2

从index 2开始逆转序列 [1,4,2,3]，k = 3

…

但是这样速度很慢。

1
2
3
4
5
6
class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        nums = list(range(1, n+1))
        for i in range(1, k):
            nums[i:] = nums[n-1:i-1:-1]
        return nums

Solution2

对于一个数列[1,2,3,4,5,6]。向一个空列表交错添加数列开头的元素和数列末位的元素，就可以得到尽可能大的k。

即，[1,6,2,5,3,4], 得到的是[5,4,3,2,1]，k为最大的情况。通过奇偶判断来不断添加元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        results = [0] * n
        start = 1
        end = n
        i = 0
        while start <= end: #判断是否已经添加完所有的数
            if k > 0: #判断是否还需要继续按照奇偶规则添加。
                if k & 1: #k为奇数
                    results[i] = end
                    end -= 1
                else:
                    results[i] = start
                    start += 1
                k -= 1
            else: #将剩余的元素添加到列表中
                results[i] = end
                end -= 1
            i += 1
        return results

Solution3

同样的思想，可以优化不必要的步骤。

1
2
3
4
5
6
7
8
9
class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        ans = list(range(1, n-k)) # 如果k小于n-1，则直接将1到n-k-1的元素添加到表中，节省时间。
        for i in range(0, k+1):
            if i % 2 == 0:
                ans.append(n-k + i//2)
            else:
                ans.append(n - i//2)
        return ans