今天见到一个题，让求两个字符串之间的距离，隐约记得之前在 php 中用过这个的现成函数，当时还查了一下原理，是一个俄罗斯的人搞的一个算法，原理是用矩阵，于是就往矩阵上去想，结果没想出来，后来听同学说那是个 dp，想想也是，唉，思路狭隘了
参考这里，http://www.java3z.com/cwbwebho…，写了一个矩阵的版本，…… 阅读全文
字符串距离
Reply
Tag Archives: C
字符串反转
今天遇到一个题，让反转字符串，简单题，注意下细节就好了
#include <stdio.h>
#include <string.h>
char *str_reverse(char *str) {
if (str == NULL) {
return NULL;
}
for (char *left=str, *right=str+strlen(str)-1;
left<right; left++, right--) {
char tmp = *left;
*left = *right…… 阅读全文
根据字符表穷举密码
今天遇到一个题，要求根据 a-z0-9 这些字符穷举出所有的可能的密码，搞了搞，代码如下
#include <stdio.h>
#include <string.h>
#define PWD_LEN (3)
char table[] = "abcdefghijklmnopqrstuvwxyz0123456789";
int table_len = strlen(table);
void f(char pwd[], int curr) {
if (curr == P…… 阅读全文
斐波那契数列
见到一个题，让算斐波那契数列的第 n 项，手工推通项没推出来，记忆化递归如下
#include <stdio.h>
#define MAX 1024
int F[MAX] = {0};
int f(int n) {
if (F[n] != 0) {
return F[n];
}
F[n] = f(n-1) + f(n-2);
return F[n];
}
int calc_f(int n) {
if (n <= 0) {
return -1;
}
F[1] = F[2]…… 阅读全文
创建一个指定大小的空白文件
这两天在做多线程下载文件的时候，遇到一个问题，需要在下载文件之前，新建一个同等大小的空白文件出来，好往里面写
#include <stdio.h>
int main() {
FILE *fp = fopen("empty_file", "wb");
fseek(fp, 2*1024-1, SEEK_SET);
char end = EOF;
fwrite(&end, sizeof(cha…… 阅读全文
struct 传参改变内容
今天想到一个问题，就是 struct 的传参和数组的传参的区别，先看代码
#include <stdio.h>
#include <string.h>
struct d {
int n;
char str[100];
};
void chg(struct d *a) {
a->n = 1;
strcpy(a->str, "changing");
printf("%dn", a->n);
printf…… 阅读全文
linux 下 fork 后的文件资源处理问题
我们都知道 linux 下 fork 一个子进程出来，他能够继承父进程的文件资源，网络资源等，也从父进程那里拷贝了代码段，数据段，缓冲区等等到自己这里有了新的一份，那么，如果父子进程对于打开的文件资源操作不同，会是怎样的结果呢，先看正常的使用代码
#include <stdio.h>
#include <unistd.h>
int main(i…… 阅读全文
printf 一定需要 stdio.h 吗
刚刚看到一个范例代码，调用了 printf 函数，但是却没有包含 stdio.h 的头文件，这种写法第一反应就应该是不对的啊，本着动手实验的原则，试了一下
zrj@vm:~/c/test$ cat test.c
int main() {
printf("hello worldn");
return 0;
}
zrj@vm:~/c/test$ gcc -o test test.c
test.c: 在函数‘main’中:
t…… 阅读全文
找出第一个不重复的字母
今天笔试，遇到一个题目要找出一个字符串中第一个不重复的字母，简单写了一下
#include <stdio.h>
void find(const char *str, char *result)
{
int count[128]={0}, pos[128]={0};
for (int i=0; str[i]!='\0'; i++)
{
int ascii = (int)(str[i]);
count[ascii]++;
if (pos[ascii] == 0)
{
…… 阅读全文
子数组最大和
昨天笔试看到一个求子数组最大和，参考这里，http://blog.csdn.net/v_JULY_v/…，写了一下，复杂度 O(n)
#include <stdio.h>
int max_sum(int *a, int n)
{
int max = a[0];
int sum = 0;
for (int i=0; i<n; i++)
{
if (sum < 0)
{
sum = a[i];
}
else
{
sum += a[i];
}
if…… 阅读全文