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

忘是亡心i 2022-09-02 01:14 9阅读 0赞

## 题目 ##

[https://leetcode.com/problems/beautiful-array/][https_leetcode.com_problems_beautiful-array]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

没想出来，最后参考了[【分治】通俗的官解分析][Link 1] 的思路。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

##### 推理过程 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

##### 草稿 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 4]

class Solution { 
        public int[] beautifulArray(int n) { 
            HashMap<Integer, List<Integer>> map = new HashMap<>();
            List<Integer> f1 = new ArrayList<>(); // init f(1)
            f1.add(1);
            map.put(1, f1);
    
            for (int i = 2; i <= n; i++) { 
                int even = i / 2; // size: 奇部=偶部 or 奇部=偶部+1
                int odd = i - even;
                
                List<Integer> oddList = map.get(odd); // 奇部
                List<Integer> evenList = map.get(even); // 偶部
                
                ArrayList<Integer> list = new ArrayList<>();
                for (Integer num : evenList) { 
                    list.add(num * 2);
                }
                for (Integer num : oddList) { 
                    list.add(num * 2 - 1);
                }
                map.put(i, list);
            }
    
            int[] res = new int[n];
            List<Integer> list = map.get(n);
            for (int i = 0; i < list.size(); i++) { 
                res[i] = list.get(i);
            }
            return res;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 5]

[https_leetcode.com_problems_beautiful-array]: https://leetcode.com/problems/beautiful-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/85f2cf01c8c9419db3ec5217056d7cf5.png
[Link 1]: https://leetcode-cn.com/problems/beautiful-array/solution/c-fen-zhi-fa-dai-tu-pian-jie-shi-by-avphn4vwuo/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/c71936040234447781486bac96219cbb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/cf1bbbef061443729b7cca2b3f7f35b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20220829/42edf3057dcf4927a157e06a8d9b9127.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/eb0872b7e97a4ecab84c0fd5ad8879bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 4]: /images/20220829/1f7d0456376a460984d47e4aa91a93af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 5]: /images/20220829/196d4240d08b4bae89809a5d8640f262.png