专栏首页Bingo的深度学习杂货店Leetcode【526、667、932】

Leetcode【526、667、932】

题目描述:【DFS】526. Beautiful Arrangement
解题思路:

这道题是一道构造题,即构造一个长度为 N 的自然序列,满足整除关系: i % nums[i] = 0nums[i] % i = 0(i 为第 i 个位置)。由于看到数据范围 N <= 15,因此很容易想到这道题用深搜(DFS)去做。

刚开始的做法是先通过 DFS 构造出一个个完整的序列,然后再对完整序列判断每个位置是否满足要求,结果 TLE 了。后来又想了一下,其实可以在构造的过程中就判断当前构造的这个序列的每个位置是否满足上述整除关系,如果有一个位置不满足,就不用继续构造下去了(即相当于剪枝操作)。这样省了一大笔时间,题目就 AC 了。

Python3 实现:
class Solution:
    def __init__(self):
        self.b = [False] * 16  # 标记数字 i 是否被使用过
        self.ans = 0  # 结果
    
    def countArrangement(self, N: int) -> int:
        self.search(N, 1)
        return self.ans
        
    def search(self, N, r):
        for i in range(1, N+1):
            if self.b[i] == False and (i % r == 0 or r % i == 0):  # 如果不满足整除关系,就不用继续搜索该组解
                self.b[i] = True
                if N == r:  # 找到一组解
                    self.ans += 1
                else:
                    self.search(N, r+1)
                self.b[i] = False  # 恢复,回溯一步

题目描述:【Math】667. Beautiful Arrangement II
解题思路:

这道题是一道构造题,即构造一个长度为 n 的自然序列,这个序列相邻元素差的绝对值的数量为 k 个。看到数据范围是 10^4,首先排除用 DFS 的方法构造序列,然后判断是否满足题意的这种做法。

但是,乍一看也没有什么思路。因此需要从数学的角度找找规律。首先可以确定一点:对于长度为 n 的序列,元素差最多为 n-1 个,且这 n-1 个差分别为 1~(n-1)。这 n-1 个差的构成也很容易发现,较小的数和较大的数交替形成的序列就满足要求。

举个例子,假设 n = 8,k = 7,那么这个序列就是 1 8 2 7 3 6 4 5,形成的 k 个元素差为:7 6 5 4 3 2 1;若 k 不等于 n-1,假设 k = 4,我们只需要按上述规律形成满足长度为 k+1 的序列,剩余元素按递增顺序安排即可(剩余数的差值都为 1),最终得到的序列是:(1 5 2 4 3) 6 7 8,形成的 k 个元素差为:(4 3 2 1) 3 1 1(后面 3 个数的差值为 1)。

时间复杂度为 O(n)。

Python3 实现:
class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        ans = [1]
        cnt = 1
        for i in range(n):
            if k > 0:
                if cnt % 2 == 1:  # 下一个数为较大的数
                    ans.append(ans[-1]+k)
                else:  # 下一个数为较小的数
                    ans.append(ans[-1]-k)
                k -= 1
                cnt += 1
            else:
                break
        for i in range(cnt+1, n+1):  # 如果k<n-1,则安排剩余的数按递增顺序排列
            ans.append(i)
        return ans

题目描述:【Math】932. Beautiful Array
解题思路:

这道题也是一道构造题,即构造一个长度为 N 的自然序列,这个序列满足条件: 对于任意的 i < j < k,有 2 * A[k] != A[i] + A[j]。这个序列叫做美丽数组看到数据范围是 1000,首先也先排除用 DFS 的方法构造序列,然后判断是否满足题意的这种做法。

但是,乍一看也没有什么思路。因此需要从数学的角度找找规律。注意到,美丽数组有如下数学性质: 1、A 是一个漂亮数组,对于 A 中的位置 k,k 左边的都是奇数,k 右边的都是偶数(或者 k 左边的都是偶数,k 右边的都是奇数),因为这样安排就一定能保证 2 * A[k] != A[i] + A[j] (偶数 != 奇数 + 偶数 或 偶数 != 偶数 + 奇数); 2、A 是一个漂亮数组,如果对 A 中所有元素加(或减)一个常数,那么 A 还是一个漂亮数组; 3、A 是一个漂亮数组,如果对 A 中所有元素乘上一个常数,那么 A 还是一个漂亮数组; 4、A 是一个漂亮数组,如果删除A 中的一些元素,那么 A 还是一个漂亮数组,因为是对于任意的 i < k < j 都有 2 * A[k] != A[i] + A[j],删除一些元素并不会改变这种顺序; 5、A 是一个由奇数构成的漂亮数组,B 是一个偶数构成的漂亮数组,那么 A + B 也是一个漂亮数组,如: {1,5,3,7} + {2,6,4,8} = {1,5,3,7,2,6,4,8} 也是一个漂亮数组。

有了上述几条性质,我们就可以解决本题的构造问题了。

我们知道一个漂亮数组 A 可以分为奇数部分 A1 和偶数部分 A2(性质 1)。此时如果有一个漂亮数组 B,那么 2*B-1 是一个漂亮数组(性质 2、3)并且是奇数数组,而 2*B 也是一个漂亮数组(性质 2)并且是偶数数组。那么我们通过[2*B-1] + [2*B] 得到的必然也是一个漂亮数组(性质 5)。

所以我们从最简单的 ans = [1] 开始推导,构造奇数 [(2*i-1) for i in ans] + 偶数 [2*i for i in ans]拼接在一起成为新的美丽数组;如果当前构造的美丽数组的长度小于 N,就继续这个操作,就能使得得到的一直是美丽数组。因为每次构造的美丽数组的长度是 2 的整数次方,所以最后要把结果中小于等于 N 的留下来,大于 N 的数字删除即可(性质 4)。

因为构造的美丽数组的长度是随着 2 的整数次方增长的,因此外层循环是 O(logN) 级别,内层循环是 O(N) 级别,总时间复杂度为 O(N*logN);空间复杂度为 O(N)。

Python3 实现:
class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        ans = [1]  # 从[1]开始构造
        while len(ans) < N:  # 美丽数组长度小于N
            ans = [(2 * i -1) for i in ans] + [(2 * i) for i in ans]  # 性质2、3、5
        return [i for i in ans if i <= N]  # 性质4

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode【470、478、497、519、528】

    这道题是用等概率的 Rand7()([1, 7])产生等概率的 Rand10()([1, 10])。

    echobingo
  • Leetcode【429、559、589、590、669】

    二叉树的最大深度为 max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1,拓展到 N 叉树,...

    echobingo
  • 清除浮动的方法

    本章主要介绍三种常用的清除浮动的方法,主要包括: ---- [1] 增加一个空 div, 使用 clear:both 将浮动元素 "挤到" 父元素中 [2] ...

    echobingo
  • 使用cell ranger拆分10X单细胞转录组原始数据

    cell ranger是10X genomics公司提供的,专门用于分析10X 单细胞转录组数据的pipeline, 包含了原始数据拆分,表达定量,聚类分析等多...

    生信修炼手册
  • 02 . Vue入门基础之条件渲染,列表渲染,事件处理器,表单控件绑定

    如果想注册局部指令,组件中接受一个directives的选项,位于vue实例参数里面,局部指令只能在本组件使用

    常见_youmen
  • 0458-Hive数据类型校验问题分析

    使用Hive时大家都会遇到数据类型校验的问题,相比传统关系型数据库会严格要求数据的Schema,数据的列数、每一列的字段类型都有严格的规定,因此数据的存储必须按...

    Fayson
  • 什么是数组?

    今天要介绍的主角就是-数组,数组也是数据呈线性排列的一种数据结构。与前一节中的链表不同,在数组中,访问数据十分简单,而添加和删除数据比较耗工夫。这和什么是数据结...

    武培轩
  • js实现截图并保存图片(html转canvas、canvas转image)

    从入门到进错门
  • vue常用指令代码实例总结

    砸漏
  • 聊聊skywalking的TopNDatabaseStatement

    skywalking-6.6.0/oap-server/server-core/src/main/java/org/apache/skywalking/oap/...

    codecraft

扫码关注云+社区

领取腾讯云代金券