permuation sequence 超时# JobHunting - 待字闺中
q*m
1 楼
我先写的那个 next permutation, 然后call 它 k次， 结果超时。
有什么好的方法吗？
谢谢
有什么好的方法吗？
谢谢
l*a
2 楼
那说明你的next permutation没写好
我就这么做的，没超时
【在 q****m 的大作中提到】
: 我先写的那个 next permutation, 然后call 它 k次， 结果超时。
: 有什么好的方法吗？
: 谢谢
我就这么做的，没超时
【在 q****m 的大作中提到】
: 我先写的那个 next permutation, 然后call 它 k次， 结果超时。
: 有什么好的方法吗？
: 谢谢
q*m
3 楼
能把你的贴一下吗？ 这是我的code.
class Solution {
public:
void nextPermutation(vector &num) {
int i = num.size() - 1;
while(i >= 1 && num[i - 1] >= num[i])
{
--i;
}
if(i == 0)
{
int l = 0, r = num.size() -1 ;
while(l <= r)
{
swap(num[l], num[r]);
++l;
--r;
}
return;
}
int left = i, right = num.size() - 1, target = num[i - 1];
while(left < right)
{
int mid = (left + right) / 2;
if(num[mid] > target)
{
left = mid + 1;
}
else
{
right = mid;
}
}
int tmp = left;
if(num[tmp] <= target)
{
tmp = left - 1;
}
swap(num[i - 1], num[tmp]);
left = i, right = num.size() - 1;
while(left <= right)
{
swap(num[left], num[right]);
++left;
--right;
}
}
string getPermutation(int n, int k) {
vectorv(n, 0);
for(int i = 1; i <= n; ++i)
{
v[i - 1] = i;
}
for(int i = 2; i <= k; ++i)
{
nextPermutation(v);
}
string s;
for(int i = 0; i < n; ++i)
{
s.append(1, v[i] + '0');
}
return s;
}
};
【在 l*****a 的大作中提到】
: 那说明你的next permutation没写好
: 我就这么做的，没超时
class Solution {
public:
void nextPermutation(vector
int i = num.size() - 1;
while(i >= 1 && num[i - 1] >= num[i])
{
--i;
}
if(i == 0)
{
int l = 0, r = num.size() -1 ;
while(l <= r)
{
swap(num[l], num[r]);
++l;
--r;
}
return;
}
int left = i, right = num.size() - 1, target = num[i - 1];
while(left < right)
{
int mid = (left + right) / 2;
if(num[mid] > target)
{
left = mid + 1;
}
else
{
right = mid;
}
}
int tmp = left;
if(num[tmp] <= target)
{
tmp = left - 1;
}
swap(num[i - 1], num[tmp]);
left = i, right = num.size() - 1;
while(left <= right)
{
swap(num[left], num[right]);
++left;
--right;
}
}
string getPermutation(int n, int k) {
vector
for(int i = 1; i <= n; ++i)
{
v[i - 1] = i;
}
for(int i = 2; i <= k; ++i)
{
nextPermutation(v);
}
string s;
for(int i = 0; i < n; ++i)
{
s.append(1, v[i] + '0');
}
return s;
}
};
【在 l*****a 的大作中提到】
: 那说明你的next permutation没写好
: 我就这么做的，没超时
l*a
4 楼
经典算法，查得到吧
扫了一眼，你中间插了一段两分，是想干吗
【在 q****m 的大作中提到】
: 能把你的贴一下吗？ 这是我的code.
: class Solution {
: public:
: void nextPermutation(vector &num) {
: int i = num.size() - 1;
:
: while(i >= 1 && num[i - 1] >= num[i])
: {
: --i;
: }
扫了一眼，你中间插了一段两分，是想干吗
【在 q****m 的大作中提到】
: 能把你的贴一下吗？ 这是我的code.
: class Solution {
: public:
: void nextPermutation(vector
: int i = num.size() - 1;
:
: while(i >= 1 && num[i - 1] >= num[i])
: {
: --i;
: }
l*a
5 楼
不是有序的吧？
直接loop就可以啊
exist,
直接loop就可以啊
exist,
o*n
6 楼
这道题不需要算permutation.
直接找下一个数. 关键是找出最大位.
比如, 1365 -> 1536, 12837 -> 12873
直接找下一个数. 关键是找出最大位.
比如, 1365 -> 1536, 12837 -> 12873
相关阅读
职位：PHP Developer at San Jose, CAapple三轮电面正常吗？NetApp一下强行裁掉这么多？？元芳哥们咋看？？？可以问秘书technical interview的问题类型么？h1b transfer到底要多久？终于收到拒信，但是...麻烦帮忙分析下面试一周以后follow up，是不是被当备胎了？该move on吧跟一个组面试完之后，hr把offer递上去没有批请教大家，H1B批准之后生效之前就可以tranfer工作吗？这种transfer流程和生效后一样吗？今天发现原来KMP挺简单的H1b 批准后是不是leetcode上的4Sum一问感觉G家面试还是和面的组工作内容略微相关的问个f家的设计题请问 KMP算法重要吗？自费在纽约念master，打黑工够得支付生活费吗？Re: 进ANR亏废掉了！！ (转载)湾区求个entry level java的internString Match一定要用KMP吗？大家接offer之后都签non-competition, non-solitation agreement么？