8.9字节跳动笔试（1，3）

1. 完美字符串

长度为n的字符串，均为小写字母，修改m个位置的字母，修改完毕后选取这个字符串的连续子串，

满足这个子串只有一种字母，这个子串就是完美子串 求最长完美子串长度

#include<stdio.h>
#include<string.h>
#define maxsize 100000
int max(int a, int b);
int main(void)
{
	char str1[maxsize];
	int m;
	scanf("%d",&m);
	scanf("%s", str1);
	int len = strlen(str1);
	int result = 0;
	for (char ch1 = 'a';ch1<= 'z'; ch1++)
	{
		int left = 0, right = 0;
		int k = m;
		while (right < len)
		{
			if (str1[right] == ch1)
				right++;
			else
			{
				if (k > 0)
				{
					k--;
					right++;
				}
				else  //k==0 [left,right)
				{
					result = max(result, right - left);
					while (str1[left] == ch1)
						left++;
					left++;
					right++;
				}

			}
		
		}
		result = max(result, right - left);
	}
	printf("%d",result);
	return 0;
}
int max(int a, int b)
{
	return a > b ? a : b;
}

3.多骨诺米牌

要求 排在后面的牌的高和宽都要大于前面的牌，问最多能选几张牌

#include<stdio.h>
int cmp(const void* a, const void* b);
int main(void)
{
	int n;
	scanf("%d",&n);
	int** nums = malloc(sizeof(int*) * n);
	/*读入牌的信息*/
	for (int i = 0; i < n; i++)
	{
		nums[i] = malloc(sizeof(int) * 2);
		scanf("%d %d",&nums[i][0],&nums[i][1]);
	}
	/*快排 将该问题转换为最长上升子串问题*/
	qsort(nums, n, sizeof(int*), cmp);
	int* q = malloc(sizeof(int) * n);//q[i] 长度为i+1的上升子串的末尾值的最小值
	int count = 0;
	q[count] = nums[0][1];
	for (int i = 1; i < n; i++)
	{
		if (nums[i][1] > q[count])
		{
			q[++count] = nums[i][1];
		}

		else// 找到q中第一个大于等于nums[i][1]的值 并 替换它  （二分法）
		{
			int left = 0, right = count;
			while (left < right)
			{
				int mid = left + (right - left) / 2;
				if (q[mid] < nums[i][1])//[mid+1,right]
					left = mid + 1;
				else //q[mid]>=nums[i][1] [left,mid]
					right = mid;
			}
			q[left] = nums[i][1];
		}
		
	}
	printf("%d",count+1);
	return 0;
}
int cmp(const void* a, const void* b)
{
	if ((*(int**)a)[0] == (*(int**)b)[0])
		return (*(int**)b)[1]-(*(int**)a)[1];
	return(*(int**)a)[0] - (*(int**)b)[0];
}