chshda
BAN USERHere is a c++ solution using bit operation.
#include <cstdio>
int get(unsigned int sokudo, int index) {
unsigned int mask1 = 1 << (2 * index), mask2 = 1 << (2 * index + 1);
return (sokudo & (mask1 | mask2)) >> (2 * index);
}
unsigned int set(unsigned int sokudo, int index, int val) {
int bit1 = val & 1, bit2 = val >> 1;
unsigned int mask1 = 1 << (2 * index), mask2 = 1 << (2 * index + 1);
unsigned int mask3 = bit1 << (2 * index), mask4 = bit2 << (2 * index + 1);
return sokudo & (~(mask1 | mask2)) | (mask3 | mask4);
}
void print(int sokudo) {
static int count = 0;
printf("%d solution:\n", ++count);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
printf("%d ", get(sokudo, i*4+j));
}
printf("\n");
}
printf("\n");
}
void dfs(int index, unsigned int sokudo, unsigned int row, unsigned int column, unsigned int block) {
if (index == 16) {
print(sokudo);
return;
}
int x = index / 4, y = index % 4;
for (int i = 0; i < 4; i++) {
unsigned int mask1 = 1 << (4 * x + i);
unsigned int mask2 = 1 << (4 * y + i);
unsigned int mask3 = 1 << (4 * (x/2*2+y/2) + i);
if ((row & mask1) || (column & mask2) || (block & mask3)) continue;
sokudo = set(sokudo, index, i);
row |= mask1, column |= mask2, block |= mask3;
dfs(index + 1, sokudo, row, column, block);
row ^= mask1, column ^= mask2, block ^= mask3;
}
}
int main() {
dfs(0, 0, 0, 0, 0);
}
The problem actually whats to find out the first common node in two single lists.
- chshda March 26, 2015For both nodes, traverse down to the root to get their lengths, let's say the length of node 1 is len1, the length of node 2 is len2, and len1 < len2.
Let p and q point to node 1 and node 2 respectively, q moves forward len2-len1 steps first, then p and q both move step by step until they reach the same node, which is their lease common ancestor.