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

文章目录

• • 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;
}
           

运行效果：

时间复杂度小于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;
}
           

运行效果：

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;
}
           

运行效果：