CareerCup 150 1.1 @1point3acres

1.1.c

/*
 * CareerCup 150 4/16-4/22 1.1
 *
 * slaink@1point3acres
 *
 */

/*
 * 首先想到的是排序，如果可以用其他数据结构的话，我倾向于使用一个二叉树，遇到重复节点时候，计算结束。
 * 既然不能使用其他数据结构，那么还是使用排序呗。剩下的就是算法复杂度的问题了。
 * 不知道大牛们用什么方法。
 * [del]本来想用qsort,但是不知道怎么总是badaccess。先发上来下个版本再修改。[/del]
 * Qsort已经添加。
 * 带注释的Qsort可以查看这里 https://gist.github.com/2396016 
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int dumb_way(char *string);
int word_count_way(char *string);
int split(char *string, int low, int high);
int quicksort(char *string, int low, int high);
int qsort_way(char *string);
int main(int argc, char **argv)
{
    if(argc != 3){
        printf("usage: <program name> <type 1:dumb-way 2:word_count 3:qsort> <string>\n");
        return 0;
    }
    switch(atoi(argv[1])) {
        case 1:
            if(dumb_way(argv[2]))
                printf("got dup\n");
            break;
        case 2:
            if(word_count_way(argv[2]))
                printf("got dup\n");
            break;
	case 3:
	    if(qsort_way(argv[2]))
		printf("got dup\n");
	    break;
    }
	
    return 0;
    
} 

int dumb_way(char *string)
{
    int i,j;
    int len = (int)strlen(string);
    
    i=0;
    while (i<len) {
        for (j=i+1; j<len; j++) {
            if(string[i] == string[j])
                return 1;
        }
        i++;
    }
    
    return 0;
}

int word_count_way(char *string)
{
    int i;
    char *chars;
    chars = malloc(sizeof(char) * 256);
    memset(chars, 0, sizeof(*chars));

    for(i=0;i<strlen(string);i++) {
        chars[(int)string[i]]++;
    }

    for(i=0;i<256;i++)
        if(chars[i]>1)
            return 1;

    return 0;
}

int qsort_way(char *string)
{
    return quicksort(string, 0, strlen(string) - 1);
}

int quicksort ( char *string, int low, int high )
{
	int i ;
	if ( high > low )
	{
		i = split ( string, low, high ) ;/* Split into two arrays */
		if(i == -1)
			return -1;
		if(quicksort ( string, low, i - 1 ) == -1)/* Sort both arrays */
			return -1;
		if(quicksort ( string, i + 1, high ) == -1)
			return -1;
	}
	
	return 0;
}

int split ( char *string, int low, int high )
{
	char i,t;
	int p, q;

	p = low + 1 ;
	q = high ;
	i = string[low] ;

	while ( q >= p )
	{
		while ( string[p] < i ) /* iterator, if left side element is less than i(split symbol), check next right one */
			p++ ;
		
		if(string[p] == i)
			return -1;
		
		while ( string[q] > i ) /* another iterator, if right side element is larger than i(split symobl), check left one */
			q-- ;
		
		if(string[q] == i && q != low)
			return -1;

		if ( q > p ) /* iterator over, at that time, elements before p is less than i (except i), and elements after q is greater than i */
		{
			t = string[p] ;
			string[p] = string[q] ;
			string[q] = t ;
		} /* switch p and q element, so p element is less than i and q element is greater than i */
	}
	
	/* after that while, the array looks like that(x<i,y>i)
	 * [i x x x x x y y y y y]
	 *____________^ ^
	 *____________q p
	 */

	//t = string[low] ;
	string[low] = string[q] ;
	string[q] = i ;
	
	/* after that swap, the array looks like that(x<i,y>i)
	 * [x x x x x i y y y y y]
	 *____________^ ^
	 *____________q p
	 */
	
	return q ;
}