CareerCup 1.1

1.c

/**************************************************
1.最简单的方法就是两层循环，复杂度O(n^2)
2.使用排序，然后找重复。复杂度为O(nlgn)+O(n)=O(nlgn)
3.直接使用快排，在排序过程中，如果发现有重复的，立即结束递归
****************************************************/

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

int repeat;

/* exchange two char */
void swap(char *a, char *b)
{
	char temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

/* quick sort */
void qsort(char str[], int p, int r)
{
	if(p < r)
	{
		int q = partition(str, p, r);
		if(q == -1)
			return;
		qsort(str, p, q - 1);
		qsort(str, q + 1, r);
	}
}

/* partition */
int partition(char str[], int p, int r)
{
	char ch = str[r];
	int i = p - 1;
	int j;
	for(j = p; j < r; j++)
	{
		if(str[j] == ch) /* find a same char, return */
		{
			repeat = 1;
			return -1;
		}
		else if(str[j] < ch)
		{
			i++;
			swap(&str[i], &str[j]);
		}
	}
	swap(&str[i + 1], &str[r]);
	return i + 1;
}

int main()
{
	char str[100];
	scanf("%s", str);
	repeat = 0;
	qsort(str, 0, strlen(str) - 1);
	if(repeat)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}