---

目录

1.打印空格和星号的规律

2.别样的多组输入

3.左旋字符串的多种解法

方法1：保存前移

方法2：临时数组

方法3： 三次反转

4.数组中出现次数超过一半的数字

方法1：哈希表法

方法2：排序中值法

方法3：消除异值法

---

近几年互联网受疫情影响，许多互联网都使用牛客网在线笔试招人

很多同学因为不熟悉牛客网的环境和使用，最后在线笔试面试中屡屡受挫

牛客网提供了语言巩固，算法提高等在线OJ题，更有面试真题，大厂内推！

链接附上点击链接注册牛客网

1.打印空格和星号的规律

点我做题：BC65 箭形图案

#include
int main()
{
    int n=0;
    while(~scanf("%d",&n))
    {
        //上半部分n+1行
        for(int i=1;i<=n+1;i++)
        {
            //空格
            for(int j=1;j<=n+1-i;j++)
            {
                printf("  ");
            }
            //星号
            for(int j=1;j<=i;j++)
            {
                printf("*");
            }
            printf("\n");
        }
        
        //下半部分n行
        for(int i=1;i<=n;i++)
        {
            //空格
            for(int j=1;j<=i;j++)
            {
                printf("  ");
            }
            //星号
            for(int j=1;j<=n+1-i;j++)
            {
                printf("*");
            }
            printf("\n");
        }
        
    }
    return 0;
}

这题的启示：

可以把两个空格作为一次性输出，只要for循环里的判断条件你好写，怎么样都行！！

 学习到牛客网：原来可以通过鼠标可以查看空格有多少个！！！

我的做题感悟：

1. 分为上下两部分，每行就是空格和星号组成也是老生常谈了
2. 形成自己的风格:for(int i=1;i<=N;i++)这样的题从1开始，然后<=某一个数
3. 找规律，空格和星号的循环判断条件:越来越多，用i，然后加减某一个数，越来越少，用n-i，然后加减某一个数，这个某一个数可以通过第一个外层循环的i带入来知晓。

2.别样的多组输入

点我做题：公务员面试

#include
int main()
{
    int score=0;//分数（整数）
    int max=0;
    int min=100;//最小值先给最大的
    int count=0;//计数器，7个一组
    int sum=0;//7个整数的和
    while(scanf("%d",&score)!=EOF)//一次输入一个
    {
        if(maxmax=score;
        if(min>score)  min=score;
        sum+=score;
        count++;
        if(count==7)//7个为一组，够了7个重新初始化
        {
            printf("%.2lf\n",(sum-min-max)/5.0);//格式输出：换行
            max=0;
            min=100;
            sum=0;
            count=0;
        }
    }
    return 0;
}

这题的提示：

对于多组输入，且是一组输入多个数据，可能大多数人想到的做法是：对于每一组数据一次性输完

 但是这样即不美观，当数据多了就...

3.左旋字符串的多种解法

题目：

实现一个函数，可以左旋字符串中的k个字符。

例如：

ABCD左旋一个字符得到BCDA

ABCD左旋两个字符得到CDAB

方法1：保存前移

#include
void LeftRound(char* str, int k)
{
	int len = strlen(str);
	k = k%len;
	for (int i = 0; i < k; i++)
	{
		char temp = str[0];
		for (int i = 1; i <= len - 1; i++)
		{
			str[i - 1] = str[i];
        }
		str[len - 1] = temp;
	}
}
 
int main()
{
	char str[20] = "hello world";
	int k = 0;
	scanf("%d", &k);
	LeftRound(str, k);
	printf("%s\n", str);
	return 0;
}

启发：

k=k%len；提高效率

方法2：临时数组

#include
void LeftRound(char* str, int k)
{
	int len = strlen(str);
	k = k % len;
	char* temp = (char*)malloc(sizeof(len + 1));
	if (temp == NULL)
	{
		perror(temp);
		return -1;
	}
	strcpy(temp, str + k);
	strncat(temp, str, k);
	strcpy(str, temp);
}
int main()
{
	char str[20] = "hello world";
	int k = 0;
	scanf("%d", &k);
	LeftRound(str, k);
	printf("%s\n", str);
	return 0;
}

方法3： 三次反转

void Rotate(char* str, int left, int right)
{
	while (left < right)
	{
		char temp = str[left];
		str[left] = str[right];
		str[right] = temp;
		left++;
		right--;
	}
}
 
void LeftRound(char* str, int k)
{
	int len = strlen(str);
	k = k % len;
	Rotate(str, 0, k - 1);
	Rotate(str, k, len - 1);
	Rotate(str, 0, len - 1);
}
 
int main()
{
	char str[20] = "hello world";
	int k = 0;
	scanf("%d", &k);
	LeftRound(str, k);
	printf("%s\n", str);
	return 0;
}

rotate:旋转
reverse:反转

4.数组中出现次数超过一半的数字

点我做题：NC73 数组中出现次数超过一半的数字

方法1：哈希表法

本题涉及到<数组元素，出现次数>之间的对应映射关系，这种方法应该不难想到，把数组元素出现的次数存到一个标记数组map里，然后遍历一遍map标记数组，找到次数>half的元素就行！

int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
    // write code here
    int map[10000]={0};
    int half=numbersLen/2;
    for(int i=0;i
    {
        map[numbers[i]]++;
    }
    for(int i=0;i
    {
        if(map[numbers[i]]>half)
        {
           return numbers[i];
        }
    }
    return 0;
}

时间复杂度:O(n)

空间复杂度:O(1) 

方法2：排序中值法

由于题目给定输入的数组"一定非空"，也就是numbersLen>=1,还给定"且保证有解",那么数组中一定存在一个出现次数超过一半的数组元素。

那么如果我们给数组先进行排序，然后取排完序的数组的中间元素，那一定就是目标值！

也就是快速排序+返回numbers[mid]的代码，简单！不写！

有人可能又要问数组元素取numbers[mid]的时候是否要分奇偶，不需要！(因为蓝色标注)

时间复杂度:O(nLogN)

空间复杂度:O(1)

方法3：消除异值法

只要我们把数组元素不同的两个值给消除掉，因为一定存在一个次数超过数组一半的元素，

所以最后留下来的那个数组值一定是目标值！

int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
    if(numbers==NULL) return -1;
    int time=1;
    int target=numbers[0];
    for(int i=1;i
    {
        if(time==0)
        {
            target=numbers[i];
            time=1;
            continue;
        }
        if(target==numbers[i])
        {
            time++;
        }
        else
        {
            time--;
        }
    }
    return target;
    return 0;
}

题目做的不过瘾，再来几道？牛客网