raz0r89
BAN USERMy brute force searching solution.
#include <stdio.h>
#define M 100
#define N 50
char str[M + 1][M + 1];
char pat[N + 1];
int lp;
char flag[M + 1][M + 1];
int n, m;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int do_dfs(int x, int y, int idx) {
int i, tx, ty;
if (idx == lp - 1) {
return 1;
}
else {
for (i = 0; i < 8; i++) {
tx = (x + dx[i] + n) % n;
ty = (y + dy[i] + m) % m;
if ((!flag[tx][ty]) && (str[tx][ty] == pat[idx + 1])) {
flag[tx][ty] = 1;
if (do_dfs(tx, ty, idx + 1)) {
return 1;
}
else {
flag[tx][ty] = 0;
}
}
}
}
return 0;
}
int is_matching()
{
int x, y, i, j;
for (x = 0; x < n; x++) {
for (y = 0; y < m; y++) {
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
flag[i][j] = 0;
}
}
if (str[x][y] == pat[0]) {
flag[x][y] = 1;
if (do_dfs(x, y, 0)) {
return 1;
}
}
}
}
return 0;
}
int main()
{
int i;
n = 5, m = 5;
str[0][0] = 'a', str[0][1] = 'c', str[0][2] = 'p', str[0][3] = 'r', str[0][4] = 'c';
str[1][0] = 'x', str[1][1] = 's', str[1][2] = 'o', str[1][3] = 'p', str[1][4] = 'c';
str[2][0] = 'v', str[2][1] = 'o', str[2][2] = 'v', str[2][3] = 'n', str[2][4] = 'i';
str[3][0] = 'w', str[3][1] = 'g', str[3][2] = 'f', str[3][3] = 'm', str[3][4] = 'n';
str[4][0] = 'q', str[4][1] = 'a', str[4][2] = 't', str[4][3] = 'i', str[4][4] = 't';
gets(pat);
lp = strlen(pat);
printf("%d\n", is_matching());
return 0;
}
My solution need to construct a map between each character of ordered string and its index, the problem can be tackled by quick sort using customized comparison function that compare the index of a pair of characters instead of value.
However, counting sort can be used to get a better algorithm whose time complexity is O(n) because the index set is limited. Two version solutions are below:
#include <stdio.h>
#include <stdlib.h>
#define AL_SIZE 26
int idx[AL_SIZE];
char table[AL_SIZE + 1];
int cmp(const void* a, const void* b)
{
return idx[*((char*)a) - 'a'] - idx[*((char*)b) - 'a'];
}
void create_idx()
{
int i;
for (i = 0; table[i] != '\0'; i++) {
idx[table[i] - 'a'] = i;
}
}
void sort_char_by_quick_sort(char* s)
{
qsort(s, strlen(s), sizeof(char), cmp);
}
void sort_char_by_counting_sort(char* s)
{
int i, j, k;
int l = strlen(s);
int count[AL_SIZE];
memset(count, 0, sizeof(int) * AL_SIZE);
for (i = 0; s[i] != '\0'; i++) {
count[idx[s[i] - 'a']]++;
}
for (i = j = 0; i < AL_SIZE && j < l; i++){
for (k = 0; k < count[i]; k++) {
s[j++] = table[i];
}
}
}
int main()
{
char s[100];
gets(s);
gets(table);
create_idx();
sort_char_by_counting_sort(s);
printf("%s\n", s);
return 0;
}
#include <stdio.h>
#define MAX_ROW_NUM 3
#define MAX_K 100
int num[MAX_ROW_NUM][MAX_K + 1];
int calculate(int x, int y)
{
int i = 0, j = 1, k = 2;
int p, q;
for (p = 0; p <= 1; p++) {
for (q = 0; q <= y; q++) {
num[p][q] = 0;
}
}
num[0][0] = num[1][0] = num[1][1] = 1;
for (p = 2; p <= x; p++) {
for (num[p][0] = 1, q = 1; q <= y; q++) {
num[k][q] = num[j][q] + num[i][q - 1];
// printf("%d ", num[k][q]);
}
// printf("\n");
q = i; i = j;
j = k; k = q;
}
return num[j][y];
}
int main()
{
int i, j, x, y;
scanf("%d%d", &x, &y);
printf("%d\n", calculate(x, y));
return 0;
}
The solution can be written as (ak * 10 ^ k + .... a0) % 3 = [ak * (9,,,9 + 1) + ... + a0] % 3 = [ak + a(k - 1) + ... + a0] % 3. So we just need to add all digits of decimal of the binary number and then use the sum to module 3. Saw a similar problem in leetcode.
- raz0r89 March 09, 2017