526. Beautiful Arrangement
2024-09-22 10:38:34
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:
- The number at the ith position is divisible by i.
- i is divisible by the number at the ith position.
Now given N, how many beautiful arrangements can you construct?
Example 1:
Input: 2
Output: 2
Explanation: The first beautiful arrangement is [1, 2]: Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1). Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2). The second beautiful arrangement is [2, 1]: Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1). Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
Note:
- N is a positive integer and will not exceed 15.
Approach #1: backtracking. [C++]
class Solution {
public:
int countArrangement(int N) {
vector<int> path; for (int i = 1; i <= N; ++i)
path.push_back(i); return helper(N, path);
} private:
int helper(int n, vector<int> path) {
if (n <= 0) return 1;
int ans = 0;
for (int i = 0; i < n; ++i) {
if (path[i] % n == 0 || n % path[i] == 0) {
swap(path[i], path[n-1]);
ans += helper(n-1, path);
swap(path[i], path[n-1]);
}
}
return ans;
}
};
最新文章
- Android Studio的SVN Performing VCS Refresh/Commit 长时间不结束
- 解决Python中不能输入汉字的问题
- Mifare系列6-射频卡与读写器的通信(转)
- scala变量
- MongoDB安装部署(一)
- SQLite详解
- js 逻辑运算符优化
- 爬虫 BeatifulSoup 模块
- centos7基于SVN+Apache+IF.svnadmin实现SVN的web管理
- eclipse php pdt插件安装
- .net 服务端 访问共享文件夹
- Stm32 资料
- TensorFlow 实现 RNN 入门教程
- 极限编程核心价值:沟通(Communication)
- 21天实战caffe笔记_第三天
- DevExpress中Tile Application窗体的模型架构图
- 十一、springcloud之链路追踪Sleuth
- makfile.am 和makefile.in 的使用
- (转)Opencv卷积操作
- FFT(快速傅里叶变换)