Krizai
BAN USERIf I'm not wrong, here is another O(n) solution without intervals, but by just calculating moves on which item will get/lose "amazing" property.
int maxIdeal(vector<int> list){
long n = list.size();
vector<int> itemsToLostIdeal(n);
vector<int> itemsToGetIdeal(n);
int initialIdeal = 0;
for(int i =0; i < n; i++){
if(list[i] <= 0 || list[i] >= n ){
continue;
}
if(list[i] <= i){
initialIdeal++;
itemsToLostIdeal[i - list[i]+1] ++;
}else{
itemsToLostIdeal[n - list[i] + i +1] ++;
}
if(i + 1 < n){
itemsToGetIdeal[i+1] ++;
}
}
int maxMoreIdeal = 0;
int maxMoreIdealIndex = 0;
int moreIdeal = 0;
for(int i =1; i < n; i++){
moreIdeal += itemsToGetIdeal[i]-itemsToLostIdeal[i];
if(moreIdeal > maxMoreIdeal){
maxMoreIdeal = moreIdeal;
maxMoreIdealIndex = i;
}
}
return maxMoreIdealIndex;
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSString* str = @"11111";
int num = 1;
int numPrev = 1;
for(int i = 1; i <str.length; i++){
int numOld = num;
if([str characterAtIndex:i] != '0'){
NSString* substr = [str substringWithRange:NSMakeRange(i-1, 2)];
int subsStrValue = [substr intValue];
if(subsStrValue <=26){
num = num + numPrev;
}
}
numPrev = numOld;
}
NSLog(@"%d", num);
}
return 0;
}
Almost O(n). At least can be easily improved to O(n) by using deque instead of queue.
- Krizai November 27, 2016