c刷题[6]

目录

杨辉三角

杨氏矩阵

字符串左旋

判断字符串 

公务员面试

改数字

数字三角形

输出不重复序列

---

杨辉三角

在屏幕上打印杨辉三角。

先转化成二维数组：

1

1 1

1 2 1

1 3 3 1

规律：每行第一个元素和最后一个元素为1(主对角),从第三行开始，中间元素等于左上方元素和正上方元素相加。

	int arr[10][10] = { 0 };
	int i = 0;
	int j = 0;
	for (i = 0; i < 10; i++)
	{
		for (j = 0; j <= i; j++)//打印一半三角即可
		{
			if (j == 0 || i == j)
				arr[i][j] = 1;
			else
			{
				arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
			}
		}
	}
		for (i = 0; i < 10; i++)
		{
			for (j = 0; j < 10-i; j++)
			{
				printf(" ");
			}
			for (j = 0; j <= i; j++)
			{
				printf("%2d ", arr[i][j]);
			}
			printf("\n");
		}

打印效果：

杨氏矩阵

有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。

要求：时间复杂度小于O(N);

bool find_square_n(int(*arr)[3], int* r, int* c, int n)
{
	//按行找
	int i = 0;
	int j = *c - 1;
	while (i < *r && j >= 0)
	{
		if (n > arr[i][j])
			i++;
		else if (n
			< arr[i][j])
			j--;
		else
		{
			*r = i;//返回型参数
			*c = j;
			return true;
		}
	}
	return false;
}

如果我们想一次性返回多个值，不如传递实参的地址过去，通过返回型参数实现多个值的返回。

测试：

字符串左旋

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

例如：

ABCD左旋一个字符得到BCDA

ABCD左旋两个字符得到CDAB

方法一：
每次旋转一个字符，其他元素依次往前移。

void left_spin(char* arr, int k)
{
	assert(arr);
	int len = strlen(arr);
	assert(len);//0不能做余数且旋转无意义
	k %= len;//避免重复旋转
	for (int i = 0; i < k; i++)
	{
		int tmp = arr[0];//接收旋转元素
		for (int j = 0; j -1;j++ )//从前往后
			arr[j] = arr[j + 1];
		arr[len - 1] = tmp;
	}
}

右旋与左旋差不多，如果左旋k次，向右旋转len-k次即可。  

方法二：

逆序前k个数和后len-k个数，然后整体逆序 

void reverse(char*left, char*right)
{
	assert(left && right);
	while (left < right)
	{
		char tmp = *left;
		*left = *right;
		*right = tmp;
		left++;
		right--;
	}
}

测试： 

判断字符串 

写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。

例如：给定s1 =AABCD和s2 = BCDAA，返回1

给定s1=abcd和s2=ACBD，返回0.

AABCD左旋一个字符得到ABCDA

AABCD左旋两个字符得到BCDAA

AABCD右旋一个字符得到DAABC

方法一：逐个旋转对比

bool is_str(char* arr1, const char* arr2)
{
	int len = strlen(arr2);
	assert(arr1 && arr2);
	for (int i = 0; i < len; i++)
	{
		int tmp = arr1[0];//接收旋转元素
		for (int j = 0; j < len - 1; j++)//从前往后
			arr1[j] = arr1[j + 1];
		arr1[len - 1] = tmp;
		if (strcmp(arr1, arr2) == 0)
		{
			return true;
		}
	}
	return false;
}

测试： 

 

方法二：

在原字符串后补上源字符串，再查找是否存在相应的字串。

ABCDEFABCDEF

例：

CDEFAB -——>ABCDEFABCDEF

EFABCD——->ABCDEFABCDEF

bool is_str(char* arr1, const char* arr2)
{
	assert(arr1 && arr2);
	int len1 = strlen(arr1);
	int len2 = strlen(arr2);
	assert(len1 - len2 == 0);//长度是否相等
	strncat(arr1, arr1, len1);//,注意arr1有充足空间，不能用strcat
	char* arr = strstr(arr1, arr2);
	if (arr == NULL)
		return false;
	else
		return true;
 
}

公务员面试

公务员面试_牛客题霸_牛客网

这道题不难，主要想说的是多组输入如果遇到输入过多数据该怎么解决：
我们可以一个数据一个数据地读入并执行相关操作，直到输入个数为要求的个数时再进行结果输出，缺陷就是必须输入完一组数据得重置变量。

#include 
int main() 
{
    int max = 0, min = 100;
    int sum=0,score,count=0;
    while (scanf("%d", &score) != EOF)
    {
        if (max < score)
            max = score;
         if (min > score)
            min = score;
        sum += score;
        if (++count == 7)
            {
                printf("%.2f\n",(sum-max-min)/5.0);
                max=0;
                score=0;
                min=100;
                count=0;
                sum=0;
            }
    }
    return 0;
}

改数字

小乐乐改数字_牛客题霸_牛客网

方法一：使用pow函数

#include 
#include 
int main() {
    int sum = 0;
    int n;
    int i = 0;
    scanf("%d",&n);
    while(n)
    {
        int ret = n%10%2;
        if(ret==1)
        {
            sum+=1 * (int)pow(10,i);
        }
        n/=10;
        i++;
        //偶数啥也不做
    }
    printf("%d",sum);
    
    return 0;
}

 方法二，使用递归：
 

int modify(int n)
{
    if(n/10==0)
    {
        return n%2;
    }
    else {
    {
        return modify(n/10)*10 + n%2;//偶数取决于最后一位
    }
    }
}

数字三角形

按行： 

#include 
 
int main()
{
    int n = 0;
    //多组输入
    while (~scanf("%d", &n))
    {
        //控制行数
        for (int i = 1; i <= n; i++)
        {
            //打印一行
            for (int j = 1; j <= i; j++)
            {
                printf("%d ", j);
            }
            printf("\n");
        }
    }
 
    return 0;
}

除了按行输出，我还发现每列也有规律，于是试着自己去实现了一下：

#include 
#include 
int main() {
   int n;
    while(scanf("%d",&n))
  {
    int num = 1;
    int arr[n][n];//不会初始化
  // memset(arr,0,(n*n)* sizeof(int));//
   for(int i = 0;i//存放于数组
   {
    for(int j = i;j< n;j++)
    {
        
        arr[j][i] = num;
    }
    num++;
   }
    for (int i = 0; i < n; i++)
        {
            //打印一行
            for (int j = 0; j <= i; j++)
            {
                printf("%d ", arr[i][j]);
            }
            printf("\n");
        }
  }
}

输出不重复序列

小乐乐与序列_牛客题霸_牛客网

创建一个数组，初始化为0。将对应大小的数字放入对应的下标，然后输出非0的数组元素。

静态版本： 

#include 
 
int main() {
   int arr[100001] = {0};//初始化
   int n;
   int num;
   scanf("%d",&n);
   for(int i = 0;i
   {
    scanf("%d",&num);
    arr[num] = num;
   }
   for(int i = 0;i<100001;i++)
   {
   if(arr[i] !=0)
   {
    printf("%d ",arr[i]);
   }
   }
    return 0;
}

C99标准：

#include 
 
int main() {
    int n;
    scanf("%d",&n);
   int arr[n];
   memset(arr,0,n*sizeof(int));
   int num;
   for(int i = 0;i
   {
    scanf("%d",&num);
    arr[num-1] = num;//从0开始以便放下所有数据
   }
   for(int i = 0;i
   {
   if(arr[i] !=0)
   {
    printf("%d ",arr[i]);
   }
   }
    return 0;
}