系列文章目录
前言
一、旋转数组
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.解题思路
- 找到 nums1的最后元素的下标end1-1
- 找到nums2的最后元素下标end2-1
- 找到合并数组元素的最后下标end1+end2-1
- 从后往前比较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
1.题目描述
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
2.解题思路
- 定义三个指针，其中指针s1和cp指针指向arr1的起始位置，指针p2指向arr2的起始位置
- 当*盘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;
}
总结
以上就是今天要讲的三道题目，本文仅仅简单三道题目的解法，这些题目在我们以后面试时可能会遇到，我们务必掌握。另外，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。
转载：https://blog.csdn.net/qq_44918090/article/details/115528727
查看评论