theother.cpp

常见算法的代码包

//给定函数 d(n) = n + n 的各位之和，n 为正整数，如 d(78) = 78+7+8=93。 
//这样这个函数可以看成一个生成器，如 93 可以看成由 78 生成。
//定义数 A：数 A 找不到一个数 B 可以由 d(B)=A，即 A 不能由其他数生成。
//现在要写程序，找出 1 至 10000 里的所有符合数 A 定义的数。
//========================================================================
int IntSum(int n)
{
	int sum = 0;
	while(n)
	{
		sum += n % 10;
		n /= 10;
	}
	return sum;
}

void showResult()
{
	char tag[10001] = {0};
	int i, j;
	for(i = 1; i < 10001; i++)
	{
		j = i + IntSum(i);
		if(j < 10001)
			tag[j] = 1;
	}
	for(i = 1; i < 10001; i++)
	{
		if(tag[i] == 0)
			printf("%d\n", i);
	}
}

//求数组中连续最大和
//========================================================================

int maxListValue(int data[], int n)
{
	int sum = data[n -1];
	int maxSum = sum;
	for(int i = n - 2; i >= 0; i--)
	{
		if(sum < 0)
			sum = 0;
		sum += data[i];
		if(sum > maxSum)
			maxSum = sum;
	}
	return maxSum;
}

//有n + 2个大小为1至n的数，其中有两个数重复，其它数只出现一次。求出这两个重复的数。
//========================================================================

void getTwoRepeatNO(int *data, int n)      //1...n, 共 n + 2 个数
{
	int a = 0;
	int b = 0;
	int i;
	int k = 0;
	int h = 0;
	int m;
	for(i = 1; i <= n; i++)
	{
		k ^= i; 
	}
	for(i = 0; i < n + 2; i++)
	{
		k ^= data[i];
	}
	while(1)
	{
		h++;
		if(k & 1)
			break;
		else
			k = k >> 1;
	}
	m = 1 << (h - 1);
	for(i = 1; i <= n; i++)
	{
		if(i & m)
			a ^= i;
		else
			b ^= i;
	}
	for(i = 0; i < n + 2; i++)
	{
		if(data[i] & m)
			a ^= data[i];
		else
			b ^= data[i];
	}
	printf("%d  %d\n", a, b);
}

int main(int argc, char* argv[])
{
	int data[] = {1, 2, 3, 4, 5, 6, 7, 6, 8, 9, 8, 10};
	getTwoRepeatNO(data,  sizeof(data)/sizeof(int) - 2); //输出6 8
	return 0;
}

//输入一个链表的头结点，从尾到头反过来输出每个结点的值。
//========================================================================

void PrintListReversely(ListNode* pListHead)
{
      if(pListHead != NULL)
      {
            // Print the next node first
            if (pListHead->m_pNext != NULL)
            {
                  PrintListReversely(pListHead->m_pNext);
            }
 
            // Print this node
            printf("%d\n", pListHead->m_nKey);
      }
}

//从尾到头输出一个字符串
//========================================================================

void printStr(char *str)
{
	assert(str != NULL);
	if(*str)
	{
		if(*(str + 1))
		{
			printStr(str + 1);
		}
		printf("%c", *str);
	}
}

//定义一个函数求字符串的长度，要求该函数体内不能声明任何变量。
//========================================================================

unsigned int StrLen(char *str)
{
	if(*str=='\0')
		return 0;
	else
		return 1 + StrLen(str + 1);
}

//给定一个字符串，例如abc123de4f67,把里面所有的数字字串找出来，并且存贮起
//来，例如你要把123，4，67找出来，放到3个char型数组里。
//========================================================================

int getDigit(const char *str, char dst[][100])
{
	int n = 0;
	char *begin = NULL;
	while(*str)
	{
		if(*str >= '0' && *str <= '9')
		{
			begin = (char *)str;
			while(*str && *str >= '0' && *str <= '9')
			{
				str++;
			}
			strncpy(dst[n], begin, str - begin);
			dst[n++][str - begin] = '\0';
			str--;
		}
		str++;
	}
	return n;
}

int main(int argc, char* argv[])
{
    char dst[10][100];
	char str[] = "123guo4567kang8p9ing10";
	int n = getDigit(str, dst);
	for(int i = 0; i < n; i++)
		puts(dst[i]);
	return 0;
}

//给定两字符串，判定一个是否在另一个中
//========================================================================

int isSub(const char *dst, const char *src)
{
	while(*dst)
	{
		if(*dst == *src)
		{
			src++;
			if(*src == '\0')
				return 1;
		}
		dst++;
	}
	return 0;
}

int main(int argc, char* argv[])
{
    char str1[] = "guokangping";
	char str2[] = "gkp";
	printf("%s\n", isSub(str1, str2) ? "Yes" : "No");  //yes
	return 0;
}

//把一个有序整数数组放到二叉树中
//========================================================================

typedef struct BiTNode
{
	int data;
	struct BiTNode *lChild, *rChild;
}BiTNode, *BiTree;

BiTree treeFromList(int *data, int low, int high)
{
	if(low <= high)
	{
		BiTree root = (BiTree)malloc(sizeof(BiTNode));
		if(!root)
			exit(1);
		int mid = (low + high)/2;
		root->data = data[mid];
		root->lChild = treeFromList(data, low, mid - 1);
		root->rChild = treeFromList(data, mid + 1, high);
		return root;
	}
	else
		return NULL;
}

void InOrderTraverse(BiTree root)
{
	if(root)
	{
		InOrderTraverse(root->lChild);
		printf("%d\n", root->data);
		InOrderTraverse(root->rChild);
	}
}

int main(int argc, char* argv[])
{
    int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
	BiTree root;
	root = treeFromList(data, 0, sizeof(data)/sizeof(int) - 1);
	InOrderTraverse(root);
	return 0;
}

//有一个由大小写组成的字符串，现在需要对他进行修改，
//将其中的所有小写字母排在大谢字母的前面
//(或用快排的partition也行)
//========================================================================

void proc(char *str)
{
	char c;
	char *start = str;
	while(*str)
	{
		str++;
	}
	str--;
	while(start < str)
	{
		while(start < str && *start >= 'a' && *start <= 'z')
		{
			++start;
		}
		while(start < str && *str >= 'A' && *str <= 'Z')
		{
			--str;
		}
		c = *start;
		*start++ = *str;
		*str-- = c;
	}
}

//正整数序列Q中的每个元素都至少能被正整数a和b中的一个整除，现给定a和b，
//需要计算出Q中的前几项，例如，当a=3，b=5，N=6时，序列为3，5，6，9，10，12 
//========================================================================

void generate(int a, int b, int N, int *Q)
{
	int i = 1;
	int j = 1;
	int *start = Q;
	int *end = Q;
	while(end - start < N)
	{
		if( a * i < b * j)
		{
			*end++ = a * i++;
		}
		else if( a * i > b * j)
		{
			*end++ = b * j++;
		}
		else
		{
			*end++ = a * i;
			i++;
			j++;
		}
	}
}

//找第K大的数
//========================================================================

int partition(int *data, int low, int high)
{
	int pivotKey = data[low];
	while(low < high)
	{
		while(low < high && data[high] >= pivotKey)
			--high;
		data[low] = data[high];
		while(low < high && data[low] <= pivotKey)
			++low;
		data[high] = data[low];
	}
	data[low] = pivotKey;
	return low;
}

int findKth(int *data, int low, int high, int K)
{
	int pivot;
	pivot = partition(data, low, high);
	if(K < (pivot - low + 1))
		return findKth(data, low, pivot - 1, K);
	else if(K > (pivot - low + 1))
		return findKth(data, pivot + 1, high, K - (pivot - low + 1));
	else 
		return data[pivot];		
}

int main(int argc, char* argv[])
{
	int data[]  = {-1, 1, 3, 4,  5, 2, 6, 7, 8, 10, 9};
	printf("%d\n" , findKth(data, 0, sizeof(data)/sizeof(int) - 1, 5));
	return 0;
}