busycai
BAN USERyou solution canot get the right answer in some case.
for example, N=(10110)2, in your case, you will get (11010)2, am i right? but the right answer is (11001)2, which is smaller than (11010)2.
so your step (3) of flip is just not enough, the right way is set the 0 you find in (2) to 1, and rearrange the 1's on the right side of this 0 to the lowest positions if there exist.
I will still use N=(10110)2 to demonstrate that. the 0 you find at (2) is at pos 3(pos 0 is the rightmost bit), so you flip it to 1, and there are 2-1=1(you already use one of it) 1's left on the right side of pos 3, so you set this 1 to the pos 0,then we'll get (11001)2 as the right answer.
you can use bit operation to solve it, assume the pos you find zero is i, there are j 1's on rightside, then the answer is: res = (N&(~(1<<i-1)))|(1<<(j-1)-1)
convert A+B+C=D to A+B=D-C, where A,B,C,D are numbers in array.
calculate all the A+B,D-C need two double loops.
we can calculate A+B and hash it, remember to record A,B pos in array.
for each D-C, check if it exist in hash, besides the 4 pos are different.
overall complexity is O(n*n), with O(n) space.
another way is calc A+B and sort it, then for each D-C do a binary search,to find if it exist in A+B array.
a solution for more general situation.
int count(int left, vector<int> coins, int curidx)
{
if(left == 0) return 1;
if(curidx >= coins.size()) return 0;
int res = 0;
for(int i = 0;;++i)
{
if(i*coins[curidx] <= left)
res+= count(left-i*coins[curidx],coins,curidx+1);
}
return res;
}
cout << count(28,<25,10,5,1>,0);
you cant use naive recursive to solve it, that's too inefficient, and is absolutely not the interviewer want. actually, the formula is straightforward.
let <a,b> denotes 0 and 1 call times.
f(n=0) <a,b>=<1,0>
f(n=1) <a,b>=<0,1>
f(n=2)=f(n=1)+f(n=0)=<1,1>
f(n=3)=f(n=2)+f(n=1)=<1,2>
f(n=4)=f(n=3)+f(n=2)=<2,3>
we can solve it with O(n) complexity and O(1) space:
pair<int,int> count(int n)
{
if(n<0) return make_pair(0,0);
pair<int,int> a,b;
a = make_pair(1,0);
b = make_pair(0,1);
if(n == 0) return a;
if(n == 1) return b;
pair<int,int> c;
for(int i = 2; i <= n; ++i)
{
c.make_pair(a.first+b.first,a.second+b.second);
a = b;
b = c;
}
return c;
}
the problem is a little abstract, you should confirm with the inteviewer further,maybe he/she is waiting for you. :)
1. is the array sorted? then we can solve it in O(M+N) complexity and O(1) space.
2. is the array number in certain arrange? for example, between 1-100, then we can use counting sort, with O(M+N) complexity and O(1) space.
3. if we count the same common element only once or actually occurence.
4. if all of these are not guaranteed, then maybe hashmap is possibly the best one.
int getwordcount(const string &str)
{
int res = 0;
string prestr = "";
for(int i = 0; i < str.length(); ++i)
{
if(ispunctuationorseperatechar(str[i]))
{
if(prestr != "") res++;
prestr = "";
}
else
{
prestr += s[i];
}
}
return res;
}
void printCounts(string &filename)
{
if(filename == "") return;
int linecount = 0, wordcount = 0, charcount = 0;
ifstream ifs(filename.c_str());
while(!ifs.eof())
{
string line;
getline(ifs, line);
if(line.length() <= 1) continue;
linecount++;
charcount += line.length();
wordcount += getwordcount(line);
}
ifs.close();
cout << linecount<<","<<wordcount<<","<<charcount<<endl;
}
if the word is given, a brute force solution is check each point(i,j) in the matrix, and if m[i][j]=word[0],then check three directions with length equals word.length(). this is a O(mnk) complexity, where m,n is matrix size, k is word size.
if the word finding process will execute multi times,then maybe generate all prefix of rows,cols,dialogues of the matrix, and use trie is a better idea.
without help of suffix array or a trie, i can think of a solution with O(n*n),where n is string len.
1) for palindromic str len %2 == 1, we can iterate through each index i of str, and check how many substring is palindromic if str[i] is the centre of the substr. the check process is as follow: if str[i-1]==str[i+1],then str[i-1,i,i+1] is a palindromic substr, we can continue to check if str[i-2]==str[i+2], if it is not, quit this iterator.
2) for palindromic str len%2 == 0, the process is similar except that str[i-1]=str[i],then check how many substr is palindromic.
Arr-k is formed by eliminating x*k elements from Arr-(k-1),NOT Arr-1。
- busycai December 17, 2013I dont think anyone really undertand what it means, except the author.