（C语言）杨氏矩阵 / 逆转字符串 / 左旋字符串

墨蓝 2022-02-18 15:53 187阅读 0赞

### 文章目录 ###

*   *  1、杨氏矩阵
     *   *   *  一般方法：
             *   *  运行效果：
             *  时间复杂度小于O(N) ：
             *   *  运行效果：
     *  2、逆转字符串
     *  3、左旋字符串
     *   *   *   *  运行效果：

## 1、杨氏矩阵 ##

**题目：有一个二维数组，数组的每行从左到右是递增的，每列从上到下是递增的，在这样的数组中查找一个数字是否存在**

#### 一般方法： ####

#define _CRT_SECURE_NO_WARNINGS 1
    #include <stdio.h>
    #include <stdlib.h>
    #include <windows.h>
    
    #define Col 4
    
    int Yang(int arr[][Col], int val)
    {
        
    	int i = 0;
    	int j = Col - 1;
    	int tmp = arr[i][j];//找到左上角的数
    	while (1)
    	{
        
    		if (tmp == val)
    		{
        
    			return 1;
    		}
    		else if (tmp<val && j >= 0)//小于要找的数，在下一行寻找
    		{
        
    			tmp = arr[++i][j];
    		}
    		else if (tmp>val && j >= 0)//大于要找的数，从该列向前找
    		{
        
    			tmp = arr[i][--j];
    		}
    		else
    			return 0;
    	}
    }
    int main()
    {
        
    	int i, j;
    	int a;
    	int arr[4][Col] = {
         1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 5, 6, 7, 8, 9 };
    	printf("数组为：\n");
    	for (i = 0; i < 4; i++)
    	{
        
    		for (j = 0; j < 4; j++)
    		{
        
    			printf("%3d", arr[i][j]);
    		}
    		printf("\n");
    	}
    	printf("请输入一个数：");
    	scanf_s("%d", &a);
    	if (Yang(arr, a))
    	{
        
    		printf("\n%d在该矩阵中\n", a);
    	}
    	else
    	{
        
    		printf("\n%d不在该矩阵中\n", a);
    	}
    	printf("\n");
    	system("pause");
    	return 0;
    }

##### 运行效果： #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDU3NDQz_size_16_color_FFFFFF_t_70]

#### 时间复杂度小于O(N) ： ####

int StepWise(int arr[100][100],int row,int col,int target){
        
    	//判断是否小于数组中最小的值或大于数组中最大的值
    	if (target <arr[0][0]||target > arr[row - 1][col - 1]){
        
    		return 0;
    	}
    	int i = 0;//从第0行开始
    	int j = col - 1;//从最后一列开始
    	while (i < row && j >= 0){
        
    		if (target > arr[i][j]){
        
    			i++;//排除前一行
    		}
    		else if (target < arr[i][j]){
        
    			j--;//排除后一列
    		}
    		else{
        
    			return 1;
    		}
    	}
    	return 0;//循环执行完毕仍没找到
    }
    int main(){
        
    	int row = 0;
    	int col = 0;
    	int target = 0;
    	printf("请输入数组的行长度、列长度：");
    	scanf("%d %d", &row, &col);
    	int arr[100][100] = {
         0 };
    	printf("请输入数组内容：\n");
    	for (int i = 0; i < row; i++){
        
    		for (int j = 0; j < col; j++){
        
    			scanf("%d", &arr[i][j]);
    		}
    	}
    	printf("请输入需要搜索的值：");
    	scanf("%d", &target);
    	if (StepWise(arr, row, col, target)){
        
    		printf("%d存在于数组中。\n", target);
    	}
    	else{
        
    		printf("%d不存在于数组中。\n", target);
    	}
        system("pause");
    	return 0;
    }

##### 运行效果： #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDU3NDQz_size_16_color_FFFFFF_t_70 1]

## 2、逆转字符串 ##

**有一个字符数组的内容为:“student a am i”,  
将数组的内容改为"i am a student".**

#define _CRT_SECURE_NO_WARNINGS 1
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<assert.h>
    #include <windows.h>
    
    void reverse(char *start, char *end){
        
    	assert(start);
    	assert(end);
    	while (start < end){
        
    		char temp = *start;
    		*start = *end;
    		*end = temp;
    		start++;
    		end--;
    	}
    }
    void reverse_str(char *str, int sz){
        
    	assert(str);               //检测传入的字符串
    	char *str1 = str;
    	char *left = str;
    	char *right = str + sz - 1;
    	reverse(left, right);         //先将字符串整体反转
    	while (*str1){
        
    		left = str1;
    		while ((*str1 != '\0') && (*str1 != ' ')){
         //找到单词，此处一定要加(*str1 != '\0')条件限制，因为找到最后一个单词的时候，*str1永远也不为空格
    			str1++;
    		}
    		right = str1 - 1;               //此时str1指向单词后方的空格，需要减一方能指向单词的最后一个字母
    		reverse(left, right);               //继整体反转后再次反转单词，能使单词拼写顺序恢复过来
    		if (*str1 == ' ')             //等于空格让指针后移一位否则不能参与下次循环。
    		{
        
    			str1++;
    		}
    	}
    }
    int main(){
        
    	char arr[] = "student a am i";
    	int sz = strlen(arr);
    	reverse_str(arr, sz);
    	printf("%s", arr);
    	getchar();
    
    	system("pause");
    	return 0;
    }

## 3、左旋字符串 ##

**实现一个函数，可以左旋字符串中的k个字符。  
ABCD左旋一个字符得到BCDA  
ABCD左旋两个字符得到CDAB**

分析：旋转时将字符串第一位存放起来，后面的左移，最后将存放求来的第一位放入最后一位，旋转几次就操作几次。

#define _CRT_SECURE_NO_WARNINGS 1
    
    #include<stdio.h>
    #include<stdlib.h>
    #include <windows.h>
    
    
    char* rotate_string(char arr[], int n){
        
    	int len = strlen(arr);
    	for (int i = n; i > 0; i--){
        
    		int temp = arr[0];
    		for (int j = 0; j < len - 1; j++){
        
    			arr[j] = arr[j + 1];
    		}
    		arr[len - 1] = temp;
    	}
    	return arr;
    }
    int main(){
        
    	int n = 0;
    	char arr[100];
    	printf("请输入需要旋转的字符串：");
    	scanf("%s", &arr);
    	printf("请输入需要左旋字符的个数：");
    	scanf("%d", &n);
    	printf("旋转后的字符串：%s\n", rotate_string(arr, n));
    	system("pause");
    	return 0;
    }

##### 运行效果： #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDU3NDQz_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDU3NDQz_size_16_color_FFFFFF_t_70]: /images/20220218/778a272de7624287ac2f5c41b62a25e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDU3NDQz_size_16_color_FFFFFF_t_70 1]: /images/20220218/65f531ac44b6405aa3f1b433349e0bd9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDU3NDQz_size_16_color_FFFFFF_t_70 2]: /images/20220218/c1a0e3ac9ebd4f1daab26f8780af2d2e.png