526. Beautiful Arrangement and 254. Factor Combina

I_Am 发布于2019-08-14 18:01 / 3274人阅读

摘要：用的思想，加上题目的特殊意思，来解决问题。如果个数字，有种结果。这里对原题多加了一个输出的要求，代码如下。也是为了去重，两个分解的解法是对称的，乘法对称的重点就是

用combination的思想，加上题目的特殊意思，来解决问题。

526 Beautiful Arrangement

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ≤ i ≤ N) in this array:

1.The number at the ith position is divisible by i.
2.i is divisible by the number at the ith position.

如果3个数字，有3种结果。
[1, 2, 3]
[2, 1, 3]
[3, 2, 1]
3
这里对Leetcode原题多加了一个输出的要求，代码如下。

public Solution{
    int count = 0;

    public int countArrangement(int N) {
        if (N == 0) return 0;
        helper(N, 1, new int[N + 1], new ArrayList());
        return count;
    }

    private void helper(int N, int pos, int[] used, List list) {
        if (pos > N) {
            count++;
            System.out.println(list.toString());
            return;
        }

        for (int i = 1; i <= N; i++) {
            if (used[i] == 0 && (i % pos == 0 || pos % i == 0)) {
                used[i] = 1;
                list.add(i);
                helper(N, pos + 1, used, list);
                list.remove(list.size()-1);
                used[i] = 0;
            }
        }
    }
}

254 Factor Combinations

比如给出的数字是12，质因数分解的结果如下：
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

public class Solution {
    public List> getFactors(int n) {
        List> res = new ArrayList>();
        if(n <= 3) return res;
        dfs(n, res, new ArrayList(), -1);
        return res;
    }
    
    public void dfs(int n, List> res, List path, int lower){
        // 和一般combination不同的是，每一步都要导入到结果中。
        if(lower != -1){
            path.add(n);
            res.add(new ArrayList<>(path));
            path.remove(path.size()-1);
        }
        
        // lower 是为了解决重复分解的问题，比如12 = 2*2*3 = 3*2*2，但是后一个是重复的， 所以分解之后factor不能变小。
        // upper 也是为了去重，12 = 3*4 = 4*3, 两个分解的解法是对称的，乘法对称的重点就是sqrt(n).
        int upper = (int) Math.sqrt(n);
        for(int i=Math.max(2, lower); i<= upper; i++){
            if(n%i == 0){
                path.add(i);
                dfs(n/i, res, path, i);
                path.remove(path.size()-1);
            }
        }
    }
}

服务器托管私有云 Arrangement Beautiful Factor And

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66950.html

Leetcode 相似题只有题号不含代码。

找出string里的单词。 186. Reverse Words in a String II, 434. Number of Segments in a String combination类型题 77. Combinations 39. Combination Sum 40. Combination Sum II 216. Combination Sum III 494. Target S...

StonePanda 2019-08-14 18:01 评论0 收藏0
[LeetCode] 526. Beautiful Arrangement

Problem Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position ...

GeekQiaQia 2019-08-16 13:44 评论0 收藏0
[LeetCode] 254. Factor Combinations

Problem Numbers can be regarded as product of its factors. For example, 8 = 2 x 2 x 2; = 2 x 4.Write a function that takes an integer n and return all possible combinations of its factors. Note: You ...

Leck1e 2019-08-16 13:44 评论0 收藏0
容器最大盛水量

摘要：容器最大盛水量给定个非负整数，，，，其中每个表示坐标，处的点。找到两条线，它们与轴一起形成一个容器，使得容器含有最多的水。容器最大盛水量 Container With Most Water 给定n个非负整数a1，a2，...，an，其中每个表示坐标（i，ai）处的点。绘制n条垂直线，使得线i的两个端点在（i，ai）和（i，0）处。找到两条线，它们与x轴一起形成一个容器，使得容器...

luckyw 2019-07-25 12:04 评论0 收藏0
如何使用ABSL代码调用Web service

摘要：需求在里创建，然后通过代码消费。创建一个新的基于这个标准的创建一个因为我是在当前系统上的里调用当前系统提供的，所以选择当然这个的也是需要在这个地方自己创建一个的可以维护成给该创建的维护的将该的下载到本地。基于前一步创建的创建一个。需求：在C4C UI里创建web service(maintain ticket)，然后通过ABSL代码消费。1. 创建一个新的Communication ...

ASCH 2019-08-16 11:07 评论0 收藏0