[leetcode]分治算法之beautiful Array

r囧r小猫 2021-09-28 12:08 308阅读 0赞

### 分治算法之Beautiful Array ###

*  题目
 *  解析
 *  答案

# 题目 #

[leetcode入口][leetcode]

# 解析 #

一个基本的思想是：  
因为2\*A\[k\]是偶数，  
如果奇数在左，偶数在右，那么(奇数+偶数)/2就是奇数，就不会等于A\[k\]。

但是如果左边全是奇数，右边全是偶数，也会出现问题。  
因此需要利用 **分治算法** 对左边和右边进行处理。

由于偶数有  N 2 \\frac\{N\}\{2\} 2N 个，偶数的表示方法是 2*i  
奇数有  N + 1 2 \\frac\{N+1\}\{2\} 2N\+1 个，奇数的表示方法是 2*i-1  
因此分治的两个分支可以是  
左边（奇数） function((N+1)/2) ,  
右边 function(N/2)  
再对返回的数进行还原（奇数是2*i，偶数是2*i-1）  
由于都是线性的还原，因此原来的beautifulArray的性质保持不变  
(线性的意思是加入有 2*A\[k\]!=A\[i\]+A\[j\]，那么2*2*A\[k\]!=2*(A\[i\]+A\[j\]))

# 答案 #

class Solution { 
    public:
        vector<int> beautifulArray(int N) { 
            //递归终止条件
            if(N==1){ 
                return vector<int>(1,1);
            }
            
            //奇数在左，偶数在右
            vector<int> left=beautifulArray((N+1)/2);
            vector<int> right=beautifulArray(N/2);
            
            vector<int> res;
            res.clear();
            
            for(int i=0;i<left.size();i++){ 
                res.push_back(2*left[i]-1);
            }
            
            for(int i=0;i<right.size();i++){ 
                res.push_back(2*right[i]);
            }
            
            return res;
        }
    };

[leetcode]: https://leetcode.com/problems/beautiful-array/

发表评论取消回复

表情：

评论列表（有 0 条评论，308人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java算法之分治算法

目录 1.算法的介绍 2.能够解决的问题 3.分治算法基本步骤 4.分治算法最佳实践-汉诺塔 1)汉诺塔的传说编辑 2)思路分析 3)代码实现 ------

水深无声/ 2024年04月01日 17:15/ 0 赞/ 70 阅读

相关 LeetCode题解——分治算法

文章目录 241. 为运算表达式设计优先级分治算法 95. 不同的二叉搜索树 II 241. 为运算表达式设计优先级

川长思鸟来/ 2023年06月08日 05:59/ 0 赞/ 7 阅读

相关经典算法之分治算法

分治算法前言分治法适用的场景经典案例：二分查找或折半查找

阳光穿透心脏的1/2处/ 2022年10月31日 15:59/ 0 赞/ 197 阅读

相关 Leetcode 题解 - 分治算法

其实，回溯、分治和动态规划算法可以划为一类，因为它们都会涉及递归。回溯算法就一种简单粗暴的算法技巧，说白了就是一个暴力穷举算法，比如让你用回溯算法求子集、全排列、组合，你就

落日映苍穹つ/ 2022年10月16日 06:21/ 0 赞/ 195 阅读

相关 leetcode 932. Beautiful Array | 932. 漂亮数组（分治法）

题目 [https://leetcode.com/problems/beautiful-array/][https_leetcode.com_problems_beaut

忘是亡心i/ 2022年09月02日 01:14/ 0 赞/ 11 阅读

相关 CodeForces-1155D Beautiful Array

Description You are given an array \\(a\\) consisting of \\(n\\) integers. Beauty of

红太狼/ 2022年01月12日 06:27/ 0 赞/ 220 阅读

相关 CodeForces-1155D Beautiful Array

题目传送门：[CodeForces-1155D Beautiful Array][][ ][Link 1] 题目大意：数组的美值是此数组的某个连续子数组的最大总

比眉伴天荒/ 2022年01月05日 13:49/ 0 赞/ 215 阅读

相关 [leetcode]分治算法之Median of Two Sorted Arrays

分治算法之Median of Two Sorted Arrays 题干思想归类代码题干 [leetcode入口][leetcode]

灰太狼/ 2021年09月28日 14:00/ 0 赞/ 266 阅读

相关 [leetcode]分治算法之beautiful Array

分治算法之Beautiful Array 题目解析答案题目 [leetcode入口][leetcode] 解析一个基本的思想是：

r囧r小猫/ 2021年09月28日 12:08/ 0 赞/ 309 阅读

相关 [leetcode]分治算法之Different Ways to Add Parenthese

分治算法之Different Ways to Add Parentheses 分治的思考其他的学习题干答案分治的思考分治：把问题

╰+哭是因爲堅強的太久メ/ 2021年09月28日 12:08/ 0 赞/ 255 阅读