学会LeetCood三道题

小鱼儿 2022-11-17 05:27 134阅读 0赞

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

# 系列文章目录 #

--------------------

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、旋转数组
 *   *   *   *  1.题目描述
             *  2.解题思路
 *  二、合并两个有序数组
 *   *   *   *  1.题目描述
             *  2.解题思路
 *  三、实现strStr
 *   *   *   *  1.题目描述
             *  2.解题思路
 *  总结

--------------------

# 前言 #

--------------------

![在这里插入图片描述][20210408191503570.png]

# 一、旋转数组 #

[旋转数组][Link 1]

#### 1.题目描述 ####

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

#### 2.解题思路 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 1]  
这里实现第三种思路：  
代码如下：

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

# 二、合并两个有序数组 #

[合并两个有序数组][Link 2]

#### 1.题目描述 ####

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

#### 2.解题思路 ####

1.  找到 nums1的最后元素的下标end1-1
2.  找到nums2的最后元素下标end2-1
3.  找到合并数组元素的最后下标end1+end2-1
4.  从后往前比较nums1和nums2元素的大小  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]

代码如下：

#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][strStr]

#### 1.题目描述 ####

实现 strStr() 函数。  
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]

#### 2.解题思路 ####

1.  定义三个指针，其中指针s1和cp指针指向arr1的起始位置，指针p2指向arr2的起始位置
2.  当\*盘p1==\*p2时两指针向后移动，否则cp指针移动，在重新赋值  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]

代码如下：

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

--------------------

# 总结 #

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/f97c538cbef34463a8014db4df965d3d.png
[20210408191503570.png]: /images/20221022/81e955c35ccc4ac0b398da3caa10115d.png
[Link 1]: https://leetcode-cn.com/problems/rotate-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221022/896e76d164714c9e8853c60676907205.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/343fce298f1842a9b328014d336ddccb.png
[Link 2]: https://leetcode-cn.com/problems/merge-sorted-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221022/0d2d49887ee44b80ada243605a10d3b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20221022/1c442a3c7e88444faf3e678f0e9db49a.png
[strStr]: https://leetcode-cn.com/problems/implement-strstr/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]: /images/20221022/117bf0a1bda34daf91444b53a72929f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]: /images/20221022/be199e4f9a7b409d8ba1cb231a75822a.png
[20210408195425897.png_pic_center]: /images/20221022/ffe5fba95bc34459b81f4c0d170e74f5.png