[leetcode]分治算法之beautiful Array

r囧r小猫 2021-09-28 12:08 291阅读 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 条评论，291人围观）

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

相关阅读

相关 Java算法之分治算法

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

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

相关经典算法之分治算法

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

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

相关 Leetcode 题解 - 分治算法

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

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

相关 Leetcode快速入门之第三节课: 分治算法

文章目录 1. 算法引入 2. 分治算法之归并排序 2.1 88题：合并两个有序数组 3. 分治算法之快速排序 3.1 Leet

不念不忘少年蓝@/ 2022年10月07日 04:57/ 0 赞/ 185 阅读

相关算法应用之分治法

一、分治法的基本概念在生活中当我们遇到复杂的问题时，我们通常会将这个复杂的问题分为几个小的问题或者分为几个步骤来解决，当我们将原问题拆分成若干个小问题或

刺骨的言语ヽ痛彻心扉/ 2022年02月23日 05:16/ 0 赞/ 258 阅读

相关 CodeForces-1155D Beautiful Array

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

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

相关 CodeForces-1155D Beautiful Array

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

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

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

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

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

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

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

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

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

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

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