【数据结构刷题】消失的数字和轮转数组-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构刷题】消失的数字和轮转数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一.消失的数字

方法一:异或全部元素

方法二:利用等差数列求和-该数组全部元素之和。

二.轮转数组

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

写法1:暴力求解

根据该题写出右旋转

写法2：三步旋转法(左逆序，右逆序，整体逆序)

根据左旋转写右旋转

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

方法1:根据strcmp函数比较两者字符串的ascll码值。

方法2:通过strstr函数查找

题型3:给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

思路1: 实际上就是右旋字符串，跟上面第一题的左旋字符串有着异曲同工之妙。

思路2:三步旋转法(搞清楚左部分和右部分)

思路3:空间换时间

复杂度的 oj 练习:

1.消失的数字

2.轮转数组

这篇文章是关于消失的数字和轮转数组的做题方法讲解。

一.消失的数字

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

思路:

从原题的示例2入手, [9,6,4,2,3,5,7,0,1] ，加上0就是9个数,但是0是什么都没有,所以说0这个位置就是缺的数字。那么原题是说:数组nums包含从0到n的所有整数，说明这个数组的元素的值是连续递增的,而且每次递增1。又因为原数组最大的元素为9，那么从1数过去,缺失的数字就是8。

方法一:异或全部元素

思路：

具体做法是将0到n（示例二的9）和nums（示例二的数组）中的所有数都异或起来，缺失的整数会在异或的过程中被找出来。异或满足结合律和交换律，因此最终的结果就是缺失的整数。

异或运算的规则如下：

0异或规则：
对于任意一个数a，a异或0的结果都是a本身，即a ^ 0 = a。

a ^ a规则：
对于任意一个数a，a异或a的结果是0，即a ^ a = 0。

画图:

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记所以说缺失的数字为8。

代码实现:

int missingNumber(int* nums, int numsSize)
{
	int x = 0;
	for (int i = 0; i < numsSize; i++)
	{
		x ^= nums[i];
	}
	for (int i = 0; i < numsSize+1; i++)
	{
		x ^= i;
	}

	return x;
}

int main()
{
	int num[9] = { 9,6,4,2,3,5,7,0,1 };
	int numsSize = sizeof(num)/sizeof(num[0]);
    int ret=missingNumber(num, numsSize);
	printf("消失的数字为:%d", ret);
	return 0;
}

执行:

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

方法二:利用等差数列求和-该数组全部元素之和。

等差数列的前n项和公式为：

Sn = n/2 * (a1 + an)

其中，Sn表示等差数列的前n项和，a1表示等差数列中第一项的值，an表示等差数列中第n项的值，n表示等差数列的项数。根据等差数列的前n项和公式，可以快速求得等差数列前n项的和。

缺失的数字=Sn - 数组nums的每一个值

代码实现:

int missingNumber(int* nums, int numsSize)
{
	int x = (1+numsSize)*numsSize/2;

	for (size_t i = 0; i < numsSize ; i++)
	{
		x -= nums[i];
	}

	return x;
}
int main()
{
	int num[9] = { 9,6,4,2,3,5,7,0,1 };
	int numsSize = sizeof(num)/sizeof(num[0]);
    int ret=missingNumber(num, numsSize);
	printf("消失的数字为:%d", ret);
	return 0;
}

执行:

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

二.轮转数组

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

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

例如：

ABCD左旋一个字符得到BCDA

ABCD左旋两个字符得到CDAB

写法1:暴力求解

思路:

取出数组第一个元素放到临时变量tmp内,接着所有元素往前挪动，挪动完毕把tmp内的元素放到数组最后一个位置。

以下是动图演示:这是左旋1个字符的效果

代码实现:

#include<string.h>
void reverse_left(char *arr,int k)
{
	int len = strlen(arr);
	//k = k % len;
	for (int i = 0; i < k; i++)//k是左旋几遍的意思
	{
		int j = 0;
		char tmp = arr[0];
		for (j = 0; j < len - 1; j++)
		{
			arr[j] = arr[j + 1];//元素往前挪动
		}
		arr[len - 1] = tmp;
	}
}
int main()
{
	char arr[] = "abcdef";
	int k = 0;
	scanf("%d",&k);//左旋k个字符串
	reverse_left(arr, k);
	printf("%s", arr);
}

代码执行:

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

特别说明:

k = k % len 这一行代码的作用是将 k 对字符串的长度 len 取模 (求余数)，从而确保旋转的位移量始终在字符串长度内。
例如，如果字符串长度为 6，k 的值为 8，则旋转 8 个字符实际上等于旋转 2 个字符，因为每旋转 6 个字符，字符串就会回到原始状态。因此，通过对 k 取模，可以确保旋转的位移量始终在字符串长度内，从而确保旋转的正确性。

根据该题写出右旋转:

//右旋转
void right_move(char arr[], int k)
{
	int i = 0;
	int len = strlen(arr);
	k = k % len;
	for (i = 0; i < k; i++) {
		int j = 0;
		char tmp = arr[len-1];
		for (j = len-1; j > 0; j--)
		{
			arr[j] = arr[j -1];
		}
		arr[0] = tmp;
	}
}
int main()
{
	char arr[20] = "abcdef";
	int k = 0;
	scanf("%d", &k);
	right_move(arr, k);

	printf("%s\n", arr);

}

代码执行:

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

写法2：三步旋转法(左逆序，右逆序，整体逆序)

abcdef
b a c d e f左部分旋转
b a f e d c右部分旋转
c d e f a b整体逆序

最后一步实际上是从旋转完左子串和右子串之后整体再旋转一遍，

但为了效率地看出结果,只要按着箭头的方向输出字符就是最终的结果。

代码实现:

//左旋转

#include<stdio.h>
#include<assert.h>
#include<string.h>
void reverse_string(char*left,char *right)
{
	assert(left && right);
	while (left < right)
	{
		char tmp = *left;
		*left = *right;
		*right = tmp; 
		left++;
		right--;
	}
}
void left_move(char arr[],int k)
{

	int len = strlen(arr);
	k = k % len;
	reverse_string(arr,arr+k-1);//左部分
	reverse_string(arr+k,arr+len-1);//右部分
	reverse_string(arr,arr+len-1);//整体
}
int main()
{
	char arr[] = "abcdef";
	int k = 0;
	scanf("%d",&k);
	left_move(arr, k);
	printf("%s\n", arr);
	return 0;
}

代码执行:

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

根据左旋转写右旋转

代码实现:

右旋转
void reverse_string(char* left, char* right)
{
	assert(left && right);
	while (left < right)
	{
		char tmp = *left;
		*left = *right;
		*right = tmp;
		left++;
		right--;
	}
}
void right_move(char arr[], int k)
{
	int len = strlen(arr);
	k = k % len;
	reverse_string(arr+len-k, arr + len-1);//右部分
	reverse_string(arr , arr + len -1-k);//左部分
	reverse_string(arr, arr + len - 1);//整体
}
int main()
{
	char arr[] = "abcdef";
	int k = 0;
	scanf("%d", &k);
	right_move(arr,k);
	printf("%s\n", arr);
	return 0;
}

代码执行:

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

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

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

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

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

AABCD左旋一个字符得到ABCDA

AABCD左旋两个字符得到BCDAA

AABCD右旋一个字符得到DAABC

方法1:根据strcmp函数比较两者字符串的ascll码值。

具体实现思路是：

通过循环将arr1向左移动一位（反复这个过程），并使用strcmp函数比较移动后的arr1和arr2是否相等，如果相等则返回1，表示可以通过左移变成arr2；

如果遍历完整个arr1后仍无法得到arr2，则返回0，表示无法通过左移变成arr2。

int is_left_move(char arr1[], char arr2[])
{
	int len = strlen(arr1);
	int i = 0;
	for (i = 0; i < len; i++)//要是遍历完arr1数组，也没有出现和arr2相同的字符串那就返回0
	{
		char tmp = arr1[0];
		int j = 0;
		for (j = 0; j < len-1; j++)
		{
			arr1[j] = arr1[j + 1];
		}
		arr1[len-1] = tmp;
		if (strcmp(arr1, arr2) == 0)//比较ascll码值
		{
			return 1;
		}
	}
	return 0;
}
#include<stdio.h>
int main()
{
	char arr1[20] = "abcdef";//abcdefabcdef
	char arr2[] = "cdefab";
	int ret = is_left_move(arr1, arr2);
	if (ret == 1)
	{
		printf("yes\n");
	}
	else
	{
		printf("no\n");
	}
	return 0;
}

说明:

该代码实现了一个函数is_left_move，用于判断一个字符串arr1是否能通过左移若干个字符的方式变成另一个字符串arr2。

在这个例子中，"abcdef"可以通过左移两个字符的方式变成"cdefab"，因此最终输出"yes"。

执行:

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

方法2:通过strstr函数查找

关于strstr的说明:

strstr是C语言中的一个字符串查找函数，用于在一个字符串中查找另一个字符串的出现位置。

该函数的原型为：char *strstr(const char *str1, const char *str2);

其中，str1是要查找的字符串，str2是要在str1中查找的目标字符串，函数返回值是一个指向str1中第一次出现str2的指针，如果str2未出现，则返回NULL。

在查找str2时，函数会从str1的开头开始逐个比较字符，一旦发现不匹配的字符，就会重新从下一个字符开始继续匹配，直到找到第一个匹配的子串或者str1中的所有字符都被比较完为止。如果str2为空字符串，则函数返回str1本身。

代码实现:

int is_left_move(char arr1[], char arr2[])
{
	int len1 = strlen(arr1);
	int len2 = strlen(arr2);
	if (len1 != len2)
		return  0;

	strncat(arr1, arr1, len1);
		if (strstr(arr1, arr2))
			return 1;
		else
			return 0;
}

#include<stdio.h>
int main()
{
	char arr1[20] = "abcdef";
	char arr2[] = "cdefab";
	int ret = is_left_move(arr1, arr2);
	if (ret == 1)
	{
		printf("yes\n");
	}
	else
	{
		printf("no\n");
	}
	return 0;
}

简述一下此函数在这题的作用:

if (len1 != len2)
       return 0;

在arr1[]="abcdef"前提下,如果arr2[]=“cdef”那么在

if (strstr(arr1, arr2))
           return 1;
       else
           return 0;

函数中就会认为arr2是arr1的字串，直接返回1，但这样是不对的，题目的意思是说arr1能否左旋转

简述一下此函数在这题的作用:

strncat(arr1, arr1, len1);

在这个函数中，strncat(arr1, arr1, len1) 的作用是将 arr1 的内容复制一遍添加到 arr1 的末尾，从而形成一个新的字符串。这样做是为了处理环形移位的情况，即当将 arr1 的某些字符移动到末尾时，它们将出现在开头。通过将 arr1 复制一遍添加到末尾，可以将环形移位转换为普通的移位，从而简化字符串比较的逻辑。

代码执行:

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

题型3:给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

思路1: 实际上就是右旋字符串，跟上面第一题的左旋字符串有着异曲同工之妙。

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

void rotate(int* nums, int numsSize, int k){
       int i=0;
       k=k%numsSize;
     for(i=0;i<k;i++)
     {
       int j=0;
       int tmp=nums[numsSize-1];
       for(j=numsSize-1;j>0;j--)
          {
          nums[j]=nums[j-1];
          }
          nums[0]=tmp;
     }

}

这种方式属于暴力求解，要用较多的时间，但实际上放到vs2019上可以执行

力扣运行:

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

vs2019编译器:

#include<stdio.h>
void rotate(int* nums, int numsSize, int k) {
    int i = 0;
    k = k % numsSize;
    for (i = 0; i < k; i++)
    {
        int j = 0;
        int tmp = nums[numsSize - 1];
        for (j = numsSize - 1; j > 0; j--)
        {
            nums[j] = nums[j - 1];
        }
        nums[0] = tmp;
    }

}
int main()
{
    int nums[] = { 1, 2, 3, 4, 5, 6, 7 };
    int k = 0;
    scanf("%d", &k);
    int sz = sizeof(nums) / sizeof(nums[0]);
    rotate(nums, sz,  k);
    for (int i = 0; i < sz; i++) {
        printf("%d", nums[i]);
    }
}

代码执行:

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

思路2:三步旋转法(搞清楚左部分和右部分)

代码实现:

void reverse(int*a,int left, int right)
{
    while (left < right)
    {
      int tmp = a[left];
        a[left] = a[right];
        a[right] = tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numSize, int k)
{
    if (k > numSize)
        k %= numSize;
    reverse(nums, 0, numSize - k - 1);
    reverse(nums, numSize - k , numSize - 1);
    reverse(nums, 0, numSize  - 1);
}
int main()
{
    int nums[] = {1,2,3,4,5,6,7};
    int k = 0;
    scanf("%d", &k);
    int sz = sizeof(nums) / sizeof(nums[0]);
    rotate(nums, sz,  k);
    for (int i = 0; i < sz; i++) {
        printf("%d", nums[i]);
    }
}

思路3:空间换时间

思路:

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

简述一下memcpy的作用:

在 C 语言中，memcpy是一个函数，用于在内存之间复制一定数量的字节。其函数原型为：

void* memcpy(void* destination, const void* source, size_t num);

其中，destination 是目标内存区域的指针，source 是源内存区域的指针，num 是要复制的字节数。

memcpy 函数的作用是将源内存区域中的 `num` 个字节复制到目标内存区域中。如果源和目标内存区域重叠，行为是未定义的。

以下是一个示例：

#include <stdio.h>
#include <string.h>

int main() {
    char source[] = "hello";
    char destination[6];

    memcpy(destination, source, 6);

    printf("%s\n", destination);

    return 0;
}

输出结果为：

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记

在这个示例中，memcpy 函数将 source 数组中的 5 个字符复制到 destination 数组中。由于 destination 数组长度为 6，所以需要复制 6 个字节，其中最后一个字节会被设置为 NULL 字节，即字符串结束标志。最终输出结果为 hello

memcpy 函数通常用于需要将一个内存区域的数据复制到另一个内存区域的情况。例如，当你需要对一个字符串进行操作时，可以使用 memcpy 函数将其复制到一个缓冲区中进行处理，以避免改变原始字符串的值。此外，memcpy 函数还可以用于将任何类型的数据复制到内存中。

思路3代码实现:

#include<stdio.h>

void rotate(int* nums, int numSize, int k)
{
    if (k > numSize)
        k %= numSize;
    int* tmp = (int*)malloc(sizeof(int) * numSize);
    memcpy(tmp+k,nums,sizeof(int)*(numSize-k));
    memcpy(tmp,nums + numSize - k, sizeof(int) * (k));
    memcpy(nums, tmp, sizeof(int) * (numSize));
    free(tmp);
    tmp=NULL;
}
int main()
{
    int nums[] = {1,2,3,4,5,6,7};
    int k = 0;
    scanf("%d", &k);
    int sz = sizeof(nums) / sizeof(nums[0]);
    rotate(nums, sz,  k);
    for (int i = 0; i < sz; i++) {
        printf("%d", nums[i]);
    }
}

代码执行:

【数据结构刷题】消失的数字和轮转数组,C--数据结构刷题,数据结构,c语言,笔记