BeautifulArrangementII2 [source code]
public class BeautifulArrangementII2 {
static
/******************************************************************************/
class Solution {
public int[] constructArray(int n, int k) {
int[] res = new int[n];
int l = 1, r = k + 1, i = 0;
while (l <= r) {
res[i++] = l++;
if (l <= r)
res[i++] = r--;
}
for (int j = 0; j + i < n; j++) {
res[j + i] = k + 2 + j;
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
BeautifulArrangementII2.Solution tester = new BeautifulArrangementII2.Solution();
}
}
之前backtracking的做法超时了, 然后开始看discussion里面O(N)的做法;
最后写出来的这个解法是根据discussion2写出来的, 速度是7ms (24%), 不算太好, 但是这个题目大概就是这个思路了, 没有必要继续纠结了;
这个是discussion的最优解:
@alexander said in [C++] [Java] Clean Code 4-liner:
if you have
nnumber, the maximumkcan ben - 1;
ifnis 9, maxkis 8.
This can be done by picking numbers interleavingly from head and tail,// start from i = 1, j = n; // i++, j--, i++, j--, i++, j-- 1 2 3 4 5 9 8 7 6 out: 1 9 2 8 3 7 6 4 5 dif: 8 7 6 5 4 3 2 1This is a case where
kis exactlyn - 1
When k is less than that, simply lay out the rest(i, j)in incremental
order(all diff is 1). Say if k is 5:i++, j--, i++, j--, i++, i++, i++ ... 1 9 2 8 3 4 5 6 7 8 7 6 5 1 1 1 1
class Solution {
public int[] constructArray(int n, int k) {
int[] res = new int[n];
for (int i = 0, l = 1, r = n; l <= r; i++)
res[i] = k > 1 ? (k-- % 2 != 0 ? l++ : r--) : (k % 2 != 0? l++ : r--);
return res;
}
}
这个算法总体还是很聪明的, 注意看这个人自己在写算法的时候是怎么思考的: 人家思考的时候脑子里用的也是9这样一个很具体的数字, 而不是一个n这样一个很抽象的你自己都不知道是多少的数量; 这个也是之前一再强调的;
这个算法老实说我自己想的时候是一点头绪都没有沾到的, 不过还是可以马后炮一下他的思考方式, 我这个问题自己思考的时候一个很大的失误就是没有彻底的贯彻笨办法人逻辑. 对n进行举例的做法其实我自己有想过, 但是没有具体去落实到位, 具体表现在, 比如我想了一个n是9, 然后对于一个k, 比如是5, 我就懒得自己去做一次, 或者说这么一个(9,5)的array我从头到尾都是没有自己去做的; 这样的话, 人逻辑这个就是完全没有去实践了; 而Google的题目本身就比较经常出人逻辑的题目的; 这种题目就是典型的一个intuition, 抓住了题目就能做出来; 而往往抓住这个intuition的关键就是在人逻辑自己做的过程中去模拟性的思考和总结;
另外这个题目感觉属于一类result variation的题目, 这里的一个思路可以认为, 比如是对于n等于9的时候, 我们考虑一种k, 就是8, 然后想一下这个array做出来的结果, result是什么样的; 然后从这个特殊的result的基础上, 去变化到其他更一般的情形下的result; 忘记是什么题目了, 不过这种思考类型肯定是见过的;
当然, 我自己还是认为我最后的这个穷搜的backtracking方法是不丢人的, 虽然超时, 不过我觉得真正面试的时候要是碰到这个题目不至于一点思路都没有; 这个题目本身是一个search类的题目, 但是不是一个find all*, 而是一个find any**的题目, 这种题目就类似之前的wiggle sort一样, 往往都是有deterministic strategy的; 这里的这个作者给的这个方法, 一定程度上可以认为是greedy, 当然实际上没有那么玄乎, 因为这里greed的这个概念并不好定义;
具体来说, 他这里把自己的想法转化为代码的过程也是做的非常不错; l和r两个指针类似于一个2pointer的结构, 不过这两个其实是用来取数的pointer, 分别从两头取数; 然后根据观察出来的规律, 在k等于奇偶的时候分别决定从哪一头取; 另外一个技巧就是对k进行减法更新, 并且在1的时候停止, 这个也是因为对题目的逻辑深入理解之后才能想到; 另外一个不太好理解的地方, 就是header里面的termination condition, 是要求的l <= r, 为什么可以取这个等号? 这个有点奇怪, 不过我自己trace了一下, 确实是这样的, 核心就是为什么l == r这个iteration还是一个yes-itration; 当然你可以牵强的解释一下说, 因为这里有两个取数指针, 所以一般来说当我们比如在这个iteration里面处理的是l的时候, r指向的其实还是一个yet to be picked的数, 而l当前这个指向的数, 马上就要被pick, 所以这时候l和r相等是无所谓的, 因为r的这个数还没有被pick, 而我们把l这个pick了之后(并且l++, 导致下一个iteration停止), 就可以保证最后没有哪个数字是被重复pick的;
另外, 这里是自己用到的几个trace:
n = 9, k = 9:
0 1 2 3 4 //i
1 2 3 4 //l
9 8 7 //r
9 8 7 6 5 5 //k
1 9 2 8 3 //entry
n = 5, k = 3:
0 1 2 3 4 //i
1 2 3 4 5(end) //l
5 4 //r
3 2 1 //k
1 5 2 3 4 //entry
另外, 这个人这一行:
res[i] = k > 1 ? (k-- % 2 != 0 ? l++ : r--) : (k % 2 != 0? l++ : r--);
其实可以精简一下:
res[i] = k > 1 ? (k-- % 2 != 0 ? l++ : r--) : l++;
这个是底下改写的一个更易读的版本:
class Solution {
public int[] constructArray(int n, int k) {
int[] result = new int[n];
int left=1, right=n;
for(int i=0; i<n; i++){
result[i] = k%2 !=0 ? left++ : right--;
if(k>1)
k--;
}
return result;
}
}
但是这个版本其实并没有修改在k等于1的时候可以简化操作的问题;
这个是discussion另外一个解法:
@zestypanda said in C++, concise code, O(n):
The requirement of k distinct distance can be achieved from 1, 2, ..., k+1 (<= n), by the following strategy:
1, k+1, 2, k, 3, k-1 ...; The distance of this sequence is k, k-1, k-2, ..., 2, 1Then append the remaining numbers to the list.
class Solution {
public:
vector<int> constructArray(int n, int k) {
int l = 1, r = k+1;
vector<int> ans;
while (l <= r) {
ans.push_back(l++);
if (l <= r) ans.push_back(r--);
}
for (int i = k+2; i <= n; i++)
ans.push_back(i);
return ans;
}
};
这个算法的思路跟上面那个算法实际上是类似的, 至少思考过程类似, 都是从一个类似(9,8)的例子开始, 用人逻辑分析, 然后应用result variation的思路; 区别在于, 上面第一种解法是在(9,8)的基础上, 降低k, 然后完成一个"不完整取数"的过程; 而这里这个方法, 则是在(9,8)的基础上, 增加n: 用(9,8)的结果来解决所有k等于8, 但是n大于9的case;
最后整个算法本身还是比较聪明的, 而且实现起来比上面那个方法其实要简单; 不过这个算法其实要稍微证明一下, 比如(5,3), 按照他的解法, 是先做出来1,4,2,3, 然后把5加上去; 这里1,4,2,3的部分有3个diff这个是正确的, 但是最后一个3和5之间的这个diff会不会引入新的diff呢? 答案是不会, 因为[1,k+1]跟k+2之间的diff肯定在[1,k]之间, 所以肯定不会导致增加新的diff; 这里一个小问题, 为什么(k+2) - 1 = k+1没有被包含进去? 因为k+2最后肯定是跟1..k+1这个序列的最后一个位置产生这个新diff的, 而1永远不会处于最后的这个位置: 即使k等于1, 那么这个最后的位置也是2;
Problem Description
Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n and obeys the following requirement:
Suppose this list is [a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k distinct integers.
If there are multiple answers, print any of them.
Example 1:
Input: n = 3, k = 1
Output: [1, 2, 3]
Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.
Example 2:
Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.
Note:
- The n and k are in the range 1 <= k < n <= 10^4.
Difficulty:Medium
Total Accepted:1K
Total Submissions:2.2K
Contributor: CDY_Saikou
Companies
google
Related Topics
array
Similar Questions
Beautiful Arrangement