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.
A:
Idea is straightforward, just swap and check position.
class Solution { public: int countArrangement(int N) { vector<int> nums(N+1,0); for(int i=1;i<=N;i++ ){ nums[i]=i; } int res = 0; helper(nums, res, 1); return res; } private: void helper(vector<int> & nums, int &res, int start){ if(start >= nums.size()){ res++; return; } for(int end = start; end< nums.size();end++){ if( nums[end] % start ==0 || start % nums[end]==0){ // swap end with start if(end != start){ int tmp = nums[start]; nums[start] = nums[end]; nums[end] = tmp; } helper(nums, res, start+1); // swap back if(end != start){ int tmp = nums[start]; nums[start] = nums[end]; nums[end] = tmp; } } } } };
犯了一个极其SB的错误, swap的时候, nums[end] = tmp 写成 nums[end] = start;
就是为了图快,哎。
No comments:
Post a Comment