=========================================================================

主頁點(diǎn)擊直達(dá)：個(gè)人主頁

我的小倉(cāng)庫(kù)：代碼倉(cāng)庫(kù)

C語言偷著笑：C語言專欄

數(shù)據(jù)結(jié)構(gòu)挨打小記：初階數(shù)據(jù)結(jié)構(gòu)專欄

Linux被操作記：Linux專欄

LeetCode刷題掉發(fā)記：LeetCode刷題

算法：算法專欄?

C++頭疼記：C++專欄

計(jì)算機(jī)網(wǎng)絡(luò)基礎(chǔ)：網(wǎng)絡(luò)專欄=========================================================================

目錄

LeetCode 1.兩數(shù)之和

LeetCode 4.尋找正序數(shù)組的中位數(shù)

LeetCode 28.找出字符串中第一個(gè)匹配項(xiàng)的下標(biāo)

?LeetCode 34.在排序數(shù)組中查找元素的第一個(gè)位置和最后一個(gè)位置

---

LeetCode 1.兩數(shù)之和

難度：簡(jiǎn)單

OJ鏈接

題目描述：

給定一個(gè)整數(shù)數(shù)組?nums?和一個(gè)整數(shù)目標(biāo)值?target，請(qǐng)你在該數(shù)組中找出?和為目標(biāo)值?target? 的那?兩個(gè)?整數(shù)，并返回它們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)。

你可以按任意順序返回答案。

示例 1：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因?yàn)?nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

輸入：nums = [3,2,4], target = 6
輸出：[1,2]

示例 3：

輸入：nums = [3,3], target = 6
輸出：[0,1]

思路講解：雙指針暴力遍歷求解

第一篇文章我們說到有關(guān)數(shù)組的題我們要優(yōu)先考慮雙/多指針，這道題目也不例外。定義兩個(gè)指針，一個(gè)在前一個(gè)在后，前一個(gè)遍歷數(shù)組看和后一個(gè)的值相加匹不匹配，如果不匹配兩個(gè)指針都向后加加知道，遍歷出結(jié)果。因?yàn)轭}目中明確規(guī)定只有兩個(gè)數(shù)，因此我們只開辟兩個(gè)空間大小的數(shù)組，遍歷出結(jié)果將兩個(gè)指針的值放在我們開辟的數(shù)組中，返回我們的數(shù)組即可。

實(shí)現(xiàn)代碼

int* twoSum(int* nums, int numsSize, int target, int* returnSize){int *a=(int *)malloc(sizeof(int)*2);for(int i=0;i<numsSize;i++){for(int j=i+1;j<numsSize;j++){if(nums[i]+nums[j]==target){a[0]=i;a[1]=j;break;}}}*returnSize=2;return a;
}

---

LeetCode 4.尋找正序數(shù)組的中位數(shù)

難度：困難

OJ鏈接

題目描述：

給定兩個(gè)大小分別為?m?和?n?的正序（從小到大）數(shù)組?nums1?和?nums2。請(qǐng)你找出并返回這兩個(gè)正序數(shù)組的?中位數(shù)?。

算法的時(shí)間復(fù)雜度應(yīng)該為?O(log (m+n))?。

示例 1：

輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
解釋：合并數(shù)組 = [1,2,3] ，中位數(shù) 2

示例 2：

輸入：nums1 = [1,2], nums2 = [3,4]
輸出：2.50000
解釋：合并數(shù)組 = [1,2,3,4] ，中位數(shù) (2 + 3) / 2 = 2.5

思路講解：雙指針暴力合并

首先使用兩個(gè)指針分別指向，兩個(gè)數(shù)組的頭，兩兩比較配合移動(dòng)，將小的放在新開辟的數(shù)組中。然后判斷新數(shù)組的大小的奇偶數(shù)，如果是奇數(shù)直接返回中間值，如果是偶數(shù)需要返回中間兩數(shù)之和的平均數(shù)。

注意：

1.有可能一個(gè)數(shù)組走完了，另一個(gè)數(shù)組還沒走完，哪一個(gè)我們也缺定不了，我們需要分別判斷指針和兩個(gè)數(shù)組距離的關(guān)系，將沒移動(dòng)完的數(shù)組全部放到新數(shù)組中。

2.有可能兩個(gè)數(shù)組都為0，特殊情況我們要判斷

3.數(shù)組總大小為偶數(shù)取平均數(shù)時(shí)，一定要除以浮點(diǎn)數(shù)。因?yàn)檎麛?shù)和整數(shù)相除只能得到整浮點(diǎn)數(shù)。

實(shí)現(xiàn)代碼

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;//根據(jù)大小合并兩個(gè)數(shù)組while (begin1 < nums1Size && begin2 < nums2Size){if (nums1[begin1] <= nums2[begin2]){a[i] = nums1[begin1];begin1++;i++;}else{a[i] = nums2[begin2];begin2++;i++;}}//判斷數(shù)組是否合并完全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;}//偶數(shù)個(gè)數(shù)else if ((nums1Size + nums2Size) % 2 == 0){b=(a[(nums1Size+nums2Size)/2]+a[(nums1Size+nums2Size)/2-1])/(double)2;//強(qiáng)制類型轉(zhuǎn)化return b;}else{//奇數(shù)個(gè)數(shù)b = a[(nums1Size + nums2Size) / 2];return b;}
}

---

LeetCode 28.找出字符串中第一個(gè)匹配項(xiàng)的下標(biāo)

難度：簡(jiǎn)單

OJ鏈接

題目描述：相當(dāng)于模擬實(shí)現(xiàn)strstr庫(kù)函數(shù)

給你兩個(gè)字符串?haystack?和?needle?，請(qǐng)你在?haystack?字符串中找出?needle?字符串的第一個(gè)匹配項(xiàng)的下標(biāo)（下標(biāo)從 0 開始）。如果?needle?不是?haystack?的一部分，則返回??-1?。

示例 1：

輸入：haystack = "sadbutsad", needle = "sad"
輸出：0
解釋："sad" 在下標(biāo) 0 和 6 處匹配。
第一個(gè)匹配項(xiàng)的下標(biāo)是 0 ，所以返回 0 。

示例 2：

輸入：haystack = "leetcode", needle = "leeto"
輸出：-1
解釋："leeto" 沒有在 "leetcode" 中出現(xiàn)，所以返回 -1 。

思路講解：暴力雙指針遍歷求解

將兩個(gè)指針分別指向兩個(gè)數(shù)組，向后依次移動(dòng)判斷是否匹配，如果不匹配第一個(gè)數(shù)組的指針歸于數(shù)組的第二個(gè)元素，第二個(gè)指針歸于指針頭，重新判斷。當(dāng)?shù)谝粋€(gè)指針移動(dòng)到第一個(gè)數(shù)組長(zhǎng)度減去第二個(gè)數(shù)組長(zhǎng)度+1時(shí)，后面的就不必判斷了。加一是為了防止兩個(gè)數(shù)組的元素個(gè)數(shù)都為1。

實(shí)現(xiàn)代碼

int strStr(char * haystack, char * needle){int next=0;int next2=0;int len1=strlen(haystack);int len2=strlen(needle);for(int i=0;i<len1-len2;i++){next=i;next2=0;for(int j=0;j<len2+1;j++){if(haystack[next]==needle[next2]){next++;next2++;if(len2==next2){return i;}}else{break;}}}return -1;
}

ps：這道題我的解法通過時(shí)間擊敗了LeetCode的100%的用戶，希望大家能寫出比我更快的代碼！！！

---

LeetCode 34.在排序數(shù)組中查找元素的第一個(gè)位置和最后一個(gè)位置

難度：中等

OJ鏈接

題目描述：

給你一個(gè)按照非遞減順序排列的整數(shù)數(shù)組?nums，和一個(gè)目標(biāo)值?target。請(qǐng)你找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值?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]

思路講解：雙指針暴力遍歷求解

先定義一個(gè)指針找到和目標(biāo)值相等的位置，在定義一個(gè)指針從這個(gè)位置找和目標(biāo)值不等的位置，后一個(gè)指針減一就是這個(gè)范圍。

注意：

1.如果后一個(gè)指針走到最后一個(gè)位置都沒有找到那么后一個(gè)這個(gè)范圍就是第一個(gè)指針的位置到數(shù)組大小減一的位置

2.如果兩個(gè)指針的值都沒有改變則表示這個(gè)數(shù)組中沒有這個(gè)目標(biāo)值

3.如果只有數(shù)組只有一個(gè)值，直接判斷是否和目標(biāo)值相等，相等的話返回[0,0]區(qū)間，不相等返回[-1,-1]。

實(shí)現(xiàn)代碼

int* searchRange(int* nums, int numsSize, int target, int* returnSize){int *a=(int *)malloc(sizeof(int)*2);a[0]=a[1]=-1;int i=0;if(1==numsSize){if(nums[0]==target)a[0]=a[1]=0;return a;}for( i=0;i<numsSize;i++){if(nums[i]==target){a[0]=i;break;}}for(int j=i;j<numsSize;j++){if(nums[j]!=target){a[1]=j-1;break;}if(j==numsSize-1){a[1]=numsSize-1;}}if(a[0]==-1){return a;}*returnSize=2;return a;
}

總結(jié)：第一篇文章我提到數(shù)組的問題可以用雙指針/多指針的問題來解決，今天分享的這四道題目也基本都用到了雙指針或者雙指針的思想，如果有更好的解法可以在評(píng)論區(qū)交流。

以后每天我會(huì)在LeetCode上面練習(xí)一道隨機(jī)題目，每一周給大家總結(jié)發(fā)出來，分享我的方法思路希望大家看完后有收獲。