kevseb1993
BAN USER
I think a sorted hash map is the best option with key being the position of element in row-order or column-order format and value being the value of the element.
We can traverse the hash table in a sorted manner.
1) Sort all shards and keys
2) If key.x > shard.y shard++
3) else key++
1) Find shortest path using Djikstra
2) If shortest path > extra edge weight, add extra edge between start and end node
3) Else do not add extra edge since shortest path < extra edge weight
| A[i] - A[j] | > | i-j |
| A[i] - A[j] | - | i-j | > 0
Four cases arise:
a) (A[i] - i) > (A[j] - j)
b) (A[i] - i) > (A[j] + j)
c) (A[i] + i) > (A[j] - j)
d) (A[i] + i) > (A[j] + j)
for case a) replace A[i] in array by X[i] i.e A[i]-i
thus we need to get all elements where
X[i] > X[j]
which is an O(n) algo using Hash table
ector<int> get(string s,int digit)
{
vector<int> v;
int i=0;
while(i<s.size())
{
int x = atoi(s.substr(i,digit).c_str());
v.push_back(x);
i+=digit;
if(x+1/pow(10,digit)>0){digit++;}
}
return v;
}
int check(vector<int> v)
{
int cnt = 0;
for(int i=1;i<v.size();i++){if(v[i]!=v[i-1]+1){cnt++;}}
if(cnt!=1){return -1;}
int x = 0;
for(int i=1;i<v.size();i++){if(v[i]!=v[i-1]+1){return v[i-1]+1;}}
return -1;
}
int main()
{
string s;
cin>>s;
int i;
for(i=1;i<=6;i++)
{
int x = check(get(s,i));
if(x!=-1){cout<<x<<"\n";break;}
}
return 0;
}
Time complexity : O(n)
Space complexity : O(n)
Algo
call recursively for each position after adding every string in current position
//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
if(pos==n){print v;return;}
for i from 0 to list[pos].size()
v.push_back(list[pos][i])
print(pos+1,v);
v.pop_back();
}
Algo
call recursively for each position after adding every string in current position
//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
if(pos==n){print v;return;}
for i from 0 to list[pos].size()
v.push_back(list[pos][i])
print(pos+1,v);
v.pop_back();
}
Algo
call recursively for each position after adding every string in current position
//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
if(pos==n){print v;return;}
for i from 0 to list[pos].size()
v.push_back(list[pos][i])
print(pos+1,v);
v.pop_back();
}
Algo
call recursively for each position after adding every string in current position
//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
if(pos==n){print v;return;}
for i from 0 to list[pos].size()
v.push_back(list[pos][i])
print(pos+1,v);
v.pop_back();
}
Algo
call recursively for each position after adding every string in current position
//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
if(pos==n){print v;return;}
for i from 0 to list[pos].size()
v.push_back(list[pos][i])
print(pos+1,v);
v.pop_back();
}
Algo
call recursively for each position after adding every string in current position
//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
if(pos==n){print v;return;}
for i from 0 to list[pos].size()
v.push_back(list[pos][i])
print(pos+1,v);
v.pop_back();
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int n,i,j;
int dp1[20][2],dp2[20][2],a[20];
//memset(dp1,0,sizeof(dp1));
cin>>n;
for(i=0;i<n;i++){cin>>a[i];}
dp1[0][0]=a[0];
dp1[0][1]=a[0];
for(i=1;i<n;i++)
{
dp1[i][0]=min(a[i],a[i]+dp1[i-1][0]);
dp1[i][1]=max(a[i],a[i]+dp1[i-1][1]);
}
dp2[n-1][0]=a[n-1];
dp2[n-1][1]=a[n-1];
for(i=n-2;i>=0;i--)
{
dp2[i][0]=min(a[i],a[i]+dp2[i+1][0]);
dp2[i][1]=max(a[i],a[i]+dp2[i+1][1]);
}
int ans=0,p,q,r,s;
for(i=0;i<n-1;i++)
{
p=abs(dp1[i][0]-dp2[i+1][0]);
p=max(p,abs(dp1[i][1]-dp2[i+1][0]));
p=max(p,abs(dp1[i][0]-dp2[i+1][1]));
p=max(p,abs(dp1[i][1]-dp2[i+1][1]));
if(p>ans)
{
q=i;ans=p;
}
}
cout<<q<<" "<<ans<<"\n";
return 0;
O(n) algo.
1.Store position of leftmost b. If there are no b's then output any pair of indices
2.Find rightmost a of the longest substring of consecutive a's.
eg abaababa longest substring of consecutive a's is (3,4)
so reverse (2,4) to get aaabbaba
O(n) algo
get product of all elements
for each element display (product/element[i])
here's my code o(n) time o(1) space
bool oneeditapart(string s1,string s2)
{
int i;int f1;
int n=s1.size(),m=s2.size();
if(abs(n-m)>1){return false;}
if(s1.size()==s2.size())
{
f1=0;
for(i=0;i<s1.size();i++)
{
if(s1[i]!=s2[i])
{
f1++;
}
}
if(f1>1){return false;}else {return true;}
}
else
{
if(s2.size()>s1.size())
{
string s=s1;
s1=s2;
s2=s;
}
f1=0;
int j=0;i=0;
while(i<m && j<n)
{
if(s1[j]==s2[i]){i++;j++;}
else {f1++;j++;}
}
if(f1>1){return false;}
return true;
}
}
int main()
{
string s1,s2;
cin>>s1>>s2;
if(oneeditapart(s1,s2)){cout<<"Match\n";}
else {cout<<"NOT Match\n";}
return 0;
}
You don;t need another queue just store the minimum value in a separate variable or create a separate node at the end just to store minimum value.
Addition of new node all occur before last node after it is updated.
Here's my algo:
for string of length n
for i=0-n-1
1.Whenever a new character is encountered update index=i and char=string[i]
2.If string [i]!=char if(i-index+1>len){ans=index+1;}
3. len=max(len,i-index+1) index=i
O(n) time,O(1) space
It is the same as an deletion in an ordinary linked list.
- kevseb1993 July 20, 2014simple dfs whenever the letter 'S' is encountered.
//pat is the pattern to be searched.
//m is size of pattern,n1 & n2 dimensions of the 2-D array
void dfs(int x,int y,int index)
{
if(x<0 || y<0 || x>=n1 || y>=n2){return;}
if(vis[x][y]){return;}
vis[x][y]=1;
if(v[x][y]!=pat[index] && index==m-1){return;}
if(v[x][y]==pat[index] && index==m-1){ans++;}
dfs(x+1,y,index+1);
dfs(x-1,y,index+1);
dfs(x,y+1,index+1);
dfs(x,y-1,index+1);
return;
}
I think the million integers indicates complexity should be atmost nlogn.
Yours is way too slow O(n^3).
simple flood fill with DFS
keep a counter and increment it whenever a separate dfs is called
Simple solution
- kevseb1993 November 26, 2016The key is that all numbers are in range 0 to n-1
for i from 1 to n:
x = A[A[i]]%n
A[i]+=n*x
for i from 1 to n:
A[i]-= (A[i]%n)
A[i] = (A[i] / n)