lwh20053276@163.com
BAN USERChecking each station in the circle from the head if the gas it provide can afford the distance to the next station. The gas count getting by gas minus distance I call it as gasAdded. The value can be positive or negative.
Starting from the first station and check the gasAdded in each station seeing if it is positive, if so, it can be considered as the start station. A counter will be set as the sum of gasAdded values. Going down the circle and add the gasAdded value of each station to the counter. Whenever the counter changed negative, the start station will be changed to the station next to the current checking one.
The stations between two start station can be considered as a big virtual station that can only provide negative gas than the distance. Since the total gas can cover all the distance, the gas in the left stations should larger than the left distance. Before the end of the checking, the matching station will be found.
//The CircuitLinkedList is implemented myself.
#include "CircuitLinkedList.h"
#include <iostream>
#include "malloc.h"
using namespace std;
struct Station
{
int gas;
int distance;
};
int main()
{
CircuitLinkedList<Station* > list;
Station ss[10]={{8,7},{9,6},{8,10},{5,7},{9,9},{8,2},{1,7},{6,4},{7,6},{9,10}};
for(int i = 0; i < 10; i++)
{
Station* s = (Station*)malloc(sizeof(Station));
s->distance = ss[i].distance;
s->gas = ss[i].gas;
list.inseartNode(new Node<Station*>(s));
}
Node<Station*>* current = list.head;
Node<Station*>* startPosition = list.head;
int currentGas = 0;
while(current != list.last)
{
if((currentGas+(current->data->gas - current->data->distance))< 0)
{
currentGas=0;
startPosition = current->next;
}
else
{
currentGas+= (current->data->gas - current->data->distance);
}
current= current->next;
}
cout<<"The start station is "<<startPosition->data->gas<<" , "<<startPosition->data->distance<<endl;
return 0;
}
The core of this algorithm is calculating two numbers of each string. In the first round, It will calculate the sum of each characters minus 'a', meanwhile the min character in the string will be found. In the second round, the sum of the squre differrence between the min character get in the first round and each character in the string. With these two sum values, it can be easliy told that if two strings are in the same group of anagrams
struct Pair
{
string name;
int sum;
int SquSum;
};
node* createNode(Pair* p)
{
node* n = (node*) malloc(sizeof(node));
n->pair = p;
return n;
}
vector<std::list<Pair*> > results;
vector<string> inputs;
void insertResult(node* n)
{
for(vector<std::list<Pair*> >::iterator it = results.begin(); it != results.end(); it++)
{
if(((*it->begin())->sum == n->pair->sum)&&((*it->begin())->SquSum==n->pair->SquSum))
{
it->push_back(n->pair);
return;
}
}
{
list<Pair*> list;
list.push_back(n->pair);
results.push_back(list);
}
}
void calculateString(string input, Pair*& pair)
{
int length = input.size();
int sum = 0, squSum = 0, min = 0;
for (int i = 0; i < length; i++)
{
min = input[min] > input[i] ? i : min;
sum += input[i] - 'a';
}
for (int i = 0; i < length; i++)
{
squSum += (input[min] - input[i]) * (input[min] - input[i]);
}
pair->sum = sum;
pair->SquSum = squSum;
pair->name = input;
cout << "The string " << input << " pair result: " << sum << " " << squSum << endl;
}
int main()
{
inputs.push_back("abc");
inputs.push_back("bcd");
inputs.push_back("cbd");
inputs.push_back("bac");
for (vector<string>::iterator it = inputs.begin(); it != inputs.end(); it++)
{
Pair* pair = (Pair*) malloc(sizeof(Pair));
calculateString(*it, pair);
insertResult(createNode(pair));
}
for(vector<std::list<Pair*> >::iterator it = results.begin(); it != results.end(); it++)
{
for(list<Pair*>::iterator iter = it->begin();iter != it->end(); iter++)
{
cout<<(*iter)->name<<" "<<(*iter)->sum<<" "<<(*iter)->SquSum<<endl;
}
cout<<endl;
}
}
The array is sorted by this way:
array[0]=1,array[1]=2...array[9]=10
After sorted, you will find the array with one duplicate number and one mussing one. Of course the sorting process can be stopped when the duplicate number is found.
/*
* BusSeat.cpp
*
* Created on: Dec 10, 2012
* Author: Kevin Li
*/
#include <cstdio>
#include <iostream>
using namespace std;
//This is the available seats in each row
int seatRow[10]={3,1,2,2,1,1,2,1,2,1};
bool flag=false;
//check if there is enough seat n for the request
bool seatsAvailable(int n)
{
for(int i =0; i< 10; i++)
{
if(seatRow[i]>=n)
{
seatRow[i]-=n;
return true;
}
}
return false;
}
int getSeat(int total,int n)
{
//check if request seat number available
if(seatsAvailable(n))
{
cout<<"get seat number"<<n<<endl;
if(total>n)
{
//if there is still more seat needed, search them
getSeat(total-n,total-n);
}
return 0;
}
else
{
int seat =getSeat(total,n-1);
}
return 0;
}
/*
* Created on: Dec 10, 2012
* Author: Kevin Li
*/
#include <cstdio>
#include <iostream>
using namespace std;
void findMissingNumber(int array[], int n)
{
int length = n;
int start = 0, stop = length - 1, mid = 0;
while (true)
{
mid = (start + stop) / 2;
if ((start == mid) || (start >= stop))
{
if (array[stop] - array[start] == stop - start)
{
cout << "no missing number";
return;
}
else
{
cout << "The missing number is " << array[start] + 1;
return;
}
}
if (array[mid] - array[start] == mid - start)
{
start = mid;
}
else
{
stop = mid;
}
}
}
Since the value in the array is restricted to 1--N, the array can be easily sort in the way:
array[tmp-1] = tmp. For example, array[5]=6, array[9]=10...
During sorting the array, the duplicate number can be checked if array[tmp-1]==tmp. If so, that means these two element array[i] and array[tmp-1] own the same value.
/*
* DuplicateNumber.cpp
*
* Created on: Dec 10, 2012
* Author: ewailli
*/
#include <cstdio>
#include <iostream>
using namespace std;
// Time o(N) Space o(1)
int main()
{
int array[]={10,6,3,4,7,5,2,7,9,1};
int tmp,i=0;
while(true)
{
tmp = array[i];
if(tmp == i+1)
{
i++;
continue;
}
if(i >=10)
{
return 0;
}
if(array[tmp-1]==tmp)
{
cout<<"duplicate number is "<<tmp;
return 0;
}
array[i]=array[tmp-1];
array[tmp-1]=tmp;
}
return 0;
}
using recursive function to check if the right or down one match the rule. If so, keep on. If not, set this direct not available for the check any more at this time, turn back check other direct.
/*
* Snake.cpp
*
* Created on: Dec 7, 2012
* Author: Kevin Li
*/
#include <cstdio>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <stack>
#include <malloc.h>
using namespace std;
enum
{
START, DOWN, RIGHT
};
int width = 5, height = 5, length = 1, maxlength = 0;
struct node
{
int value;
int index;
int direct;
node* next;
bool downAvailable;
bool rightAvailable;
};
node* createNode(int value, int index, int direct)
{
node* n = (node*) malloc(sizeof(node));
n->value = value;
n->index = index;
n->direct = direct;
n->downAvailable = true;
n->rightAvailable = true;
return n;
}
int grid[5][5] =
{
{ 0, 0, 1, 0, 1 },
{ 1, 1, 1, 1, 0 },
{ 1, 0, 1, 1, 1 },
{ 0, 1, 1, 1, 0 },
{ 1, 0, 1, 0, 1 } };
stack<node*> nodes, nodesBackup;
int getSnake(int subWidth, int subHeight)
{
//find the match one and push it into the stack
if (nodes.empty())
{
node* cur = createNode(grid[subWidth][subHeight], length, START);
nodes.push(cur);
}
if (((subWidth + 1) < width) && (abs(grid[subWidth][subHeight] - grid[subWidth + 1][subHeight]) == 1))
{
node* down = createNode(grid[subWidth + 1][subHeight], length, DOWN);
if (nodes.top()->downAvailable)
{
length++;
if (nodes.top() != NULL)
{
nodes.top()->next = down;
}
nodes.push(down);
getSnake(subWidth + 1, subHeight);
}
}
if (((subHeight + 1) < width) && (abs(grid[subWidth][subHeight] - grid[subWidth][subHeight + 1]) == 1))
{
node* right = createNode(grid[subWidth][subHeight + 1], length, RIGHT);
if (nodes.top()->rightAvailable)
{
length++;
if (nodes.top() != NULL)
{
nodes.top()->next = right;
}
nodes.push(right);
getSnake(subWidth, subHeight + 1);
}
}
// no match nodes available,check the length and pop the current ones. set the way to this node not
//available any more
if (nodes.top() != NULL)
{
if (nodes.top()->direct == DOWN)
{
nodes.top()->downAvailable = false;
nodes.top()->rightAvailable = true;
}
if (nodes.top()->direct == RIGHT)
{
nodes.top()->downAvailable = true;
nodes.top()->rightAvailable = false;
}
}
if (maxlength <= length)
{
maxlength = length;
cout << "The longest snake is: ";
while (!nodes.empty())
{
node* n = nodes.top();
cout << n->value << " ";
nodesBackup.push(n);
nodes.pop();
}
cout << "Maxlength is " << maxlength;
while (!nodesBackup.empty())
{
node* n = nodesBackup.top();
nodes.push(n);
nodesBackup.pop();
}
cout << endl << endl;
}
nodes.pop();
length--;
return maxlength;
}
int main()
{
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
cout << "starting point " << i << "," << j << endl;
length = 1;
maxlength = getSnake(i, j);
if (maxlength > (5 - i + 5 - j - 1))
{
return 0;
}
}
}
return 0;
}
I think the diagonal between left top point and right bottom point should also be taken into consideration. Find the biggest number smaller than the key .
- lwh20053276@163.com January 08, 2013The numbers up to the number and left to the number are all smaller than the key and can be removed from the matrix. This squre on the left top point can be ommitted.
For the same reason, another squre on the right bottom point can be omitted two.