给定一个整数 N,你必须找到 N 的最小倍数,其中仅包含数字 0 和 1。由于这个倍数可能很大,因此以字符串形式返回。
返回的字符串不应包含前导零。
例如,
对于 N = 55,110 是由数字 0 和 1 组成的最小倍数。 对于 N = 2,答案是 10。
我看到了几个相关的问题,但我找不到我的代码的问题。 这是我的代码,即使在使用 map 而不是 set 之后,也能在某些情况下提供 TLE。
#define ll long long
int getMod(string s, int A)
{
int res=0;
for(int i=0;i<s.length();i++)
{
res=res*10+(s[i]-'0');
res%=A;
}
return res;
}
string Solution::multiple(int A) {
if(A<=1)
return to_string(A);
queue<string>q;
q.push("1");
set<int>st;
string s="1";
while(!q.empty())
{
s=q.front();
q.pop();
int mod=getMod(s,A);
if(mod==0)
{
return s;
}
else if(st.find(mod)==st.end())
{
st.insert(mod);
q.push(s+"0");
q.push(s+"1");
}
}
}
最佳答案
这是 Raku 中的实现。
my $n = 55;
(1 .. Inf).map( *.base(2) ).first( * %% $n );
(1 .. Inf)
是一个从一到无穷大的惰性列表。 “任意星号”*
建立一个闭包并代表 map
中的当前元素。
base
是 Rakus Num
类型的方法,它返回所需基数中给定数字的字符串表示形式,此处为二进制字符串。
first
当“whatever star”闭包成立时返回当前元素。
%%
是可被
整除的运算符,它隐式地将其左侧转换为Int
。
哦,最重要的是。 并行化非常容易,因此您的代码可以使用多个 CPU 核心:
(1 .. Inf).race( :batch(1000), :degree(4) ).map( *.base(2) ).first( * %% $n );
关于algorithm - 给定数字的最小倍数 仅包含数字 0 和 1,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59840680/