首页 > 代码库 > Leetcode::Longest Common Prefix && Search for a Range

Leetcode::Longest Common Prefix && Search for a Range

2024-07-07 14:48:43   221人阅读

一次总结两道题，两道题目都比较基础

Description:Write a function to find the longest common prefix string amongst an array of strings.

分析： 这道题目最重要的知道什么叫prefix前缀， 否则一不小心就做成了最长子序列。前缀就是两个序列的前多少位

都要是一样的，不能跳着对齐，这样就比较简单了，也可以求很多个序列的公共前缀。

 1 class Solution {
 2 public:
 3     string longestCommonPrefix(vector<string> &strs) {
 4         string result,comm;
 5         if(strs.empty()) return result;
 6         result= strs[0];
 7         for(int i=1;i<strs.size();i++)
 8         {
 9             comm = "";
10             for(int j=0;j<result.size();j++)
11             {
12                 if(j>=strs[i].size()) break;
13                 if(result[j]==strs[i][j]) comm.insert(comm.end(),result[j]);
14                 else break;
15             }
16             result = comm;
17         }
18         
19         return result;
20     }
21 };

题目二：Search for a range

Description: Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm‘s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

分析： 要找一个排序数组的某个元素的范围，要求复杂度是O(log n),则肯定是基于二分查找。因为有重复元素，则将二分查找

的边界条件变一下就可以了。

 1 class Solution {
 2 public:
 3     vector<int> searchRange(int A[], int n, int target) {
 4         vector<int> pos (2,-1) ;
 5         if(n<=0) return pos;
 6         //left bound
 7         int start=0,stop = n-1,mid;
 8         while(start<=stop)
 9         {
10             mid = (start+stop)/2;
11             if(A[mid]==target && (mid==0 || A[mid-1]<target))
12             {
13                 pos[0] = mid;
14                 break;
15             }
16             else if(A[mid]<target)
17                  {
18                      start = mid+1;
19                  }
20                  else{
21                      stop = mid-1;
22                  }
23         }
24         if(pos[0]==-1) return pos;
25         //right bound
26         start=0,stop = n-1;
27         while(start<=stop)
28         {
29             mid = (start+stop)/2;   
30             if(A[mid]==target && (mid==n-1 || A[mid+1]>target) )
31             {
32                 pos[1] = mid;
33                 break;
34             }
35             else if(A[mid]>target)
36                  {
37                      stop = mid-1;
38                  }
39                  else{
40                      start = mid+1;
41                  }
42         }
43         return pos;
44     }
45 };

 

 

 


联系
我们