html5响应式公司网站模版,seo属于运营还是技术,wordpress使用腾讯cos,网站排名 优帮云主页点击直达#xff1a;个人主页
我的小仓库#xff1a;代码仓库
C语言偷着笑#xff1a;C语言专栏
数据结构挨打小记#xff1a;初阶数据结构专栏
Linux被操作记#xff1a;Linux专栏
LeetCode刷题掉发记#xff1a;LeetCode刷题
算法#xff1a;算法专栏
C头…
主页点击直达个人主页
我的小仓库代码仓库
C语言偷着笑C语言专栏
数据结构挨打小记初阶数据结构专栏
Linux被操作记Linux专栏
LeetCode刷题掉发记LeetCode刷题
算法算法专栏
C头疼记C专栏
计算机网络基础网络专栏
目录
LeetCode 1.两数之和
LeetCode 4.寻找正序数组的中位数
LeetCode 28.找出字符串中第一个匹配项的下标 LeetCode 34.在排序数组中查找元素的第一个位置和最后一个位置 LeetCode 1.两数之和
难度简单
OJ链接
题目描述
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1
输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2
输入nums [3,2,4], target 6
输出[1,2]示例 3
输入nums [3,3], target 6
输出[0,1]
思路讲解双指针暴力遍历求解
第一篇文章我们说到有关数组的题我们要优先考虑双/多指针这道题目也不例外。定义两个指针一个在前一个在后前一个遍历数组看和后一个的值相加匹不匹配如果不匹配两个指针都向后加加知道遍历出结果。因为题目中明确规定只有两个数因此我们只开辟两个空间大小的数组遍历出结果将两个指针的值放在我们开辟的数组中返回我们的数组即可。 实现代码
int* twoSum(int* nums, int numsSize, int target, int* returnSize){int *a(int *)malloc(sizeof(int)*2);for(int i0;inumsSize;i){for(int ji1;jnumsSize;j){if(nums[i]nums[j]target){a[0]i;a[1]j;break;}}}*returnSize2;return a;
} LeetCode 4.寻找正序数组的中位数
难度困难
OJ链接
题目描述
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。
示例 1
输入nums1 [1,3], nums2 [2]
输出2.00000
解释合并数组 [1,2,3] 中位数 2示例 2
输入nums1 [1,2], nums2 [3,4]
输出2.50000
解释合并数组 [1,2,3,4] 中位数 (2 3) / 2 2.5
思路讲解双指针暴力合并
首先使用两个指针分别指向两个数组的头两两比较配合移动将小的放在新开辟的数组中。然后判断新数组的大小的奇偶数如果是奇数直接返回中间值如果是偶数需要返回中间两数之和的平均数。
注意
1.有可能一个数组走完了另一个数组还没走完哪一个我们也缺定不了我们需要分别判断指针和两个数组距离的关系将没移动完的数组全部放到新数组中。
2.有可能两个数组都为0特殊情况我们要判断
3.数组总大小为偶数取平均数时一定要除以浮点数。因为整数和整数相除只能得到整浮点数。
实现代码
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){int begin1 0;int begin2 0;int* a (int*)malloc(sizeof(int) * (nums1Size nums2Size));if (a NULL){perror(malloc fail);}int i 0;double b 0;//根据大小合并两个数组while (begin1 nums1Size begin2 nums2Size){if (nums1[begin1] nums2[begin2]){a[i] nums1[begin1];begin1;i;}else{a[i] nums2[begin2];begin2;i;}}//判断数组是否合并完全while (begin1 nums1Size){a[i] nums1[begin1];begin1;i;}while (begin2 nums2Size){a[i] nums2[begin2];i;begin2;}//全为0的特殊情况if (a[nums1Size nums2Size - 1] 0){return b;}//偶数个数else if ((nums1Size nums2Size) % 2 0){b(a[(nums1Sizenums2Size)/2]a[(nums1Sizenums2Size)/2-1])/(double)2;//强制类型转化return b;}else{//奇数个数b a[(nums1Size nums2Size) / 2];return b;}
} LeetCode 28.找出字符串中第一个匹配项的下标
难度简单
OJ链接
题目描述相当于模拟实现strstr库函数
给你两个字符串 haystack 和 needle 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标下标从 0 开始。如果 needle 不是 haystack 的一部分则返回 -1 。
示例 1
输入haystack sadbutsad, needle sad
输出0
解释sad 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 所以返回 0 。示例 2
输入haystack leetcode, needle leeto
输出-1
解释leeto 没有在 leetcode 中出现所以返回 -1 。
思路讲解暴力双指针遍历求解
将两个指针分别指向两个数组向后依次移动判断是否匹配如果不匹配第一个数组的指针归于数组的第二个元素第二个指针归于指针头重新判断。当第一个指针移动到第一个数组长度减去第二个数组长度1时后面的就不必判断了。加一是为了防止两个数组的元素个数都为1。
实现代码
int strStr(char * haystack, char * needle){int next0;int next20;int len1strlen(haystack);int len2strlen(needle);for(int i0;ilen1-len2;i){nexti;next20;for(int j0;jlen21;j){if(haystack[next]needle[next2]){next;next2;if(len2next2){return i;}}else{break;}}}return -1;
}
ps这道题我的解法通过时间击败了LeetCode的100%的用户希望大家能写出比我更快的代码 LeetCode 34.在排序数组中查找元素的第一个位置和最后一个位置
难度中等
OJ链接
题目描述
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
示例 1
输入nums [5,7,7,8,8,10], target 8
输出[3,4]
示例 2
输入nums [5,7,7,8,8,10], target 6
输出[-1,-1]
示例 3
输入nums [], target 0
输出[-1,-1]
思路讲解双指针暴力遍历求解
先定义一个指针找到和目标值相等的位置在定义一个指针从这个位置找和目标值不等的位置后一个指针减一就是这个范围。
注意
1.如果后一个指针走到最后一个位置都没有找到那么后一个这个范围就是第一个指针的位置到数组大小减一的位置
2.如果两个指针的值都没有改变则表示这个数组中没有这个目标值
3.如果只有数组只有一个值直接判断是否和目标值相等相等的话返回[0,0]区间不相等返回[-1,-1]。
实现代码
int* searchRange(int* nums, int numsSize, int target, int* returnSize){int *a(int *)malloc(sizeof(int)*2);a[0]a[1]-1;int i0;if(1numsSize){if(nums[0]target)a[0]a[1]0;return a;}for( i0;inumsSize;i){if(nums[i]target){a[0]i;break;}}for(int ji;jnumsSize;j){if(nums[j]!target){a[1]j-1;break;}if(jnumsSize-1){a[1]numsSize-1;}}if(a[0]-1){return a;}*returnSize2;return a;
}
总结第一篇文章我提到数组的问题可以用双指针/多指针的问题来解决今天分享的这四道题目也基本都用到了双指针或者双指针的思想如果有更好的解法可以在评论区交流。
以后每天我会在LeetCode上面练习一道随机题目每一周给大家总结发出来分享我的方法思路希望大家看完后有收获。
