byPaco
BAN USER- 1of 1 vote
AnswersCounting the islands.
- byPaco in United States
Given a map N x N, 2-D array
0 - sea
X - land
Land is connected by 4-Neighbor connections, i.e.: above, down, left and right.
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
0000000000000000000X000000000000000
000000000000000000XXX00000000000000
000XX000000000000000000000000000000
000XXXX0000000000000000000000000000
0000000X000000000000000000000000000
00000000000000000000000000000000000
000000000000000000000X0000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
Output of this map: 4 (totally 4 islands on the map)| Report Duplicate | Flag | PURGE
Google iOS Developer
I came out whit this answer in C++:
int countIslands (int *array[], int n) {
int count = 0;
bool hasNeighbour;
for (int i =0; i<n; i++) {
for (int j=0; j<n; j++) {
if (array[i][j]) {
hasNeighbour = false;
if (i>0) {
if (array[i-1][j])
hasNeighbour = true;
}
if (j>0) {
if (array[i][j-1])
hasNeighbour = true;
}
while (++j < n) {
if (array[i][j]) {
if (i>0) {
if (array[i-1][j])
hasNeighbour = true;
}
} else {
break;
}
}
if (!hasNeighbour)
count++;
}
}
}
return count;
}
Test it with
1 1 1 0 1 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1
Count islands : 9
I came out with this answer in C++.
void printCompression (int *array, int size) {
int a, b;
a= array[0];
b = a;
for (int i=1 ; i<size; i++) {
if (array[i] == b+1)
{
b = array[i];
} else {
if (a == b) {
printf("%d,", a);
} else {
printf("%d-%d,", a, b);
}
a = array[i];
b = a;
}
}
if (a == b) {
printf ("%d\n", a);
} else {
printf("%d-%d\n", a, b);
}
}
I came out with this solution, it is O(2*n), first you traverse every string to know how many occurrence of every character from ‘a' to ‘z’, then you compose the palindrome. Since there is no rule to compose the palindrome I’m supposing alphabetical order. For example string: “rrrraaffttt" will return “afrrtttrrfa”.
Test these lines:
char *strings[] = {"ddd", "deeee", "weee", "fjff", "rrrraaffttt"};
int size = sizeof(strings)/sizeof(char*);
palindromes(strings, size);
char * palindrome (char *string) {
size_t size = strlen(string);
if (size < 2) {
return string;
}
int buffer[26];
std::fill(buffer, buffer+26, 0);
for (int i=0; i<size; i++) {
buffer[string[i] - 'a'] += 1;
}
char * output = new char [size];
std::fill(output, output+size, '0');
bool flag = false;
int k = 0;
for (int i=0; i<26; i++) {
int count = buffer[i];
if (count > 0) {
if ((count%2 == 1 && size%2 == 0) ||
(count%2 == 1 && flag)) {
output[0] = '-';
output[1] = '1';
output[2] = '\0';
break;
} else {
if (count & 1) {
output[size/2] = 'a' + i;
flag = true;
}
for (int j=0; j<(count/2); j++) {
output[k++] = 'a' + i;
output[size-k] = 'a' + i;
}
}
}
}
return output;
}
void palindromes (char *strings[], size_t size) {
for (int i = 0; i<size; i++) {
strings[i] = palindrome(strings[i]);
}
}
You need to find the first two bits with different value, 0 and 1, or 1 and 0, for that porpuose you need XOR, then toggle those bits using XOR again.
For example:
number = 11
Bit representation: 1011
Posible answers:
0111 = 7
1110 = 12
1101 = 13
All these numbers have the same amount of 1’s, but according to restriction, the answer is 1110 = 12.
Using toggle(int n) you will encounter than 1011 the LSB and third LSB are different, so just toggle those bits using XOR, and that is the answer.
int toggle (int n) {
if (n == 0)
return 0;
int i = 0;
while (true) {
if ((n & 1) ^ ((n >> ++i) & 1))
{
n ^= 1 << 0;
n ^= 1 << i;
return n;
}
}
return n;
}
This is my answer, the only thing you need to understand before starting is what lexicographical order is, and how it works.
This function traverses the string twice, so, is O(2*n) = O(n). The first time we check if an specific letter has been found before, if it has been found then selected the position with less weight, for example:
abcd = 0(10^3) + 1(10^2) + 2(10^1) + 3(10^0) = 123
or
bcda = 1(10^3) + 2(10^2) + 3(10^1) + 0(10^0) = 1230
because 123 < 1230 we select the first position.
Once you have all position with the less weight you can compose the final string only picking the character using your position array.
Just traversing twice.
char * lexicoGraphicalOrderCompression (char * string) {
size_t size = strlen(string);
int chart[26]; // only lowercase
std::fill(chart, chart + 26, -1); // init buffer with known value
int weight=0;
for (int i=0; i<size; i++) {
int value = string[i]-'a';
int position = chart[value];
if (position < 0) {
chart[value] = i; // set initial position
} else {
// another position for the same character has been found
int temp = weight*10 + value;
int k = i - position;
temp = pow(10,k-1)*((temp / int(pow(10,k))) - value) + temp%int(value * pow(10,k));
// if the weight for the current position is less than the previous one, then update position in buffer
if (temp < weight) {
chart[value] = i;
}
}
weight = weight*10 + value;
}
// compose final string
int j=0;
for (int i=0; i<size; i++) {
int value = string[i]-'a';
if (chart[value] == i){
string[j++] = string[i];
}
}
string[j] = '\0';
return string;
}
Could you describe your solution, please?
- byPaco September 21, 2015