albinoadriano
BAN USEROn top of that cout << f; can't work because cout takes a pointer to the beginning of the string not the end, right? the return will not return the wanted string for the same reason.
- albinoadriano April 28, 2015It should be
O(n)
where n is the number of digits in the input x.
- albinoadriano March 20, 2015public static long MaxIntergerFromAlgarithmsIn(long x){
long tens = 1;
while(tens <= x)
{
tens*=10;
}
int[] hist = new int[10];
for(long t = tens; t>=1 ;t /=10){
hist[x/t]++;
x -= (x/t)*t;
}
long res = 0;
for(int j = 9 ; j>=0 ; --j){
while(hist[j]>0){
tens /=10;
res += tens*j;
hist[j]--;
}
}
return res;
}
- albinoadriano March 20, 2015Please, where it says FindLongestSubstring read FindLongestSubSequence
- albinoadriano March 06, 2015Can anybody good at analysing complexity take a look in the C# code bellow. I understand it's o(n^2) in the worst case. Is there a way to estimate the average complexity? Suggestions for a good read on complexity?anyone?
using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
public static List<int> FindLongestSubstring(List<int> list){
if(list == null || list.Count<=1) return list;
//keys are elements from the list and values are the number of times they appear in the current window
Dictionary<int,int> bst = new Dictionary<int,int>();
for(int j = 0 ; j < list.Count ; ++j){
int v = list[j];
if(bst.ContainsKey(v))
bst[v]++;
else
bst[v] = 1;
}
int N = list.Count;
int windowSize = N, offset, outValue, inValue;
while(windowSize >= 2){
//Current window size make a pass from left->right
for(offset = 0; windowSize + offset <= N ; ++offset)
{
if(offset>0){
outValue = list[offset-1];
inValue = list[offset+windowSize-1];
if(--bst[outValue] == 0){
bst.Remove(outValue);
}
if(bst.ContainsKey(inValue))
bst[inValue]++;
else
bst[inValue] = 1;
}
if(bst.Keys.Count <=2 && Math.Abs(bst.Keys.Last() - bst.Keys.First()) <= 1 ){
return list.GetRange(offset, windowSize);
}
}
outValue = list[N - windowSize];
if(--bst[outValue] == 0){
bst.Remove(outValue);
}
--windowSize;
//Make a pass right->left
for(offset = 0; windowSize + offset <= N ; ++offset)
{
if(offset>0){
outValue = list[N - offset];
inValue = list[N-(offset+windowSize)];
if(--bst[outValue] == 0){
bst.Remove(outValue);
}
if(bst.ContainsKey(inValue))
bst[inValue]++;
else
bst[inValue] = 1;
}
if(bst.Keys.Count <=2 && Math.Abs(bst.Keys.Last() - bst.Keys.First()) <= 1 ){
return list.GetRange(N - windowSize - offset, windowSize);
}
}
outValue = list[windowSize-1];
if(--bst[outValue] == 0){
bst.Remove(outValue);
}
--windowSize;
}
//any single element is a valid solution
return new List<int>{list[0]};
}
public static void Main()
{
var list = new List<int>(new[]{1,2,1,2,3,4,2,2,2,2,1,1,2,3,4,5,5,4,5,4,5,5,5,5,5,6,6,6,6,6});
//list = new List<int>(new []{1, 5, 6, 6, 6, 7, 7, 9});
var res = FindLongestSubstring(list);
res.Dump();
Console.WriteLine(res.Count);
Console.WriteLine("Hello World");
}
}
the question restricts to no recursion solutions
- albinoadriano February 21, 2015
I don't think it works if insert point is at the head or head is null.
- albinoadriano May 01, 2015