系列文章目录

前言

一、旋转数组

旋转数组

1.题目描述

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
进阶：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

2.解题思路

这里实现第三种思路：
代码如下：

#define _CRT_SECURE_NO_WARNINGS   1
#include<stdio.h>
void reverse(int* arr, int left, int right)
{
	int tmp = 0;
	while (left <= right)
	{
		tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
		left++;
		right--;
	}
}
void rotate(int *arr, int k, int sz)
{
	k = k%sz;
	reverse(arr, 0, sz - k - 1);
	reverse(arr, sz - k, sz - 1);
	reverse(arr, 0, sz - 1);
}
int main()
{
	int k = 0;
	int arr[] = { 1, 2, 3, 4, 5, 6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	printf("请输入要旋转几个位置:>");
	scanf("%d", &k);
	rotate(arr, k,sz);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

二、合并两个有序数组

合并两个有序数组

1.题目描述

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

2.解题思路

1. 找到 nums1的最后元素的下标end1-1
2. 找到nums2的最后元素下标end2-1
3. 找到合并数组元素的最后下标end1+end2-1
4. 从后往前比较nums1和nums2元素的大小
   

代码如下：

#define _CRT_SECURE_NO_WARNINGS   1
#include<stdio.h>
#include<assert.h>
void merge(int arr1[], int arr2[], int sz1, int sz2)
{
	assert(arr1&&arr2);
	int end1 = sz1 - 1;
	int end2 = sz2 - 1;
	int end = sz1 + sz2 - 1;
	while (end1 >= 0 && end2 >= 0)
	{
		if (arr1[end1] > arr2[end2])
		{
			arr1[end] = arr1[end1];
			end1--;
			end--;
		}
		else
		{
			arr1[end] = arr2[end2];
			end2--;
			end--;
		}
	}
	while (end2 >= 0)
	{
		arr1[end] = arr2[end2];
		end2--;
		end--;
	}
}
int main()
{
	int arr1[] = { 1, 2, 3 };
	int arr2[] = { 4, 5, 6 };
	int sz1 = sizeof(arr1) / sizeof(arr1[0]);
	int sz2 = sizeof(arr2) / sizeof(arr2[0]);
	merge(arr1, arr2, sz1, sz2);
	int i = 0;
	for (i = 0; i < sz1+sz2; i++)
	{
		printf("%d ", arr1[i]);
	}
	printf("\n");
	return 0;
}

三、实现strStr

实现strStr

1.题目描述

实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

2.解题思路

1. 定义三个指针，其中指针s1和cp指针指向arr1的起始位置，指针p2指向arr2的起始位置
2. 当*盘p1==*p2时两指针向后移动，否则cp指针移动，在重新赋值
   

代码如下：

#define _CRT_SECURE_NO_WARNINGS   1
#include<stdio.h>
#include<string.h>
#include<assert.h>
int strStr(char* s1, char* s2)
{
	assert(s1&&s2);
	int len1 = strlen(s1);
	int len2 = strlen(s2);
	char* cp = s1;
	char* start = cp;
	while (*cp)
	{
		char* p1 = cp;
		char* p2 = s2;
		while ((*p1 != '\0') && (*p2 != '\0') && (*p1 == *p2))
		{
			p1++;
			p2++;
		}
		if (*p2 == '\0')
		{
			int ret = cp - start;
			return ret;
		}
		cp++;
	}
	if (len2 == 0)
	{
		return 0;
	}
	else
		return -1;
}
int main()
{
	char arr1[] = "bit edcuation";
	char arr2[] = "bit";
	int ret = strStr(arr1, arr2);
	printf("%d\n", ret);
	return 0;
}

总结

以上就是今天要讲的三道题目，本文仅仅简单三道题目的解法，这些题目在我们以后面试时可能会遇到，我们务必掌握。另外，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。