leetcode13
描述
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
Example 1:
Input: strs = [“flower”,”flow”,”flight”] Output: “fl” Example 2:
Input: strs = [“dog”,”racecar”,”car”] Output: “” Explanation: There is no common prefix among the input strings.
xxxxxxxxxx class Solution {public: int threeSumClosest(vector& nums, int target) { int size=nums.size(); int sum; int dist_min=INT_MAX; int res=INT_MAX; sort(nums.begin(),nums.end()); //copy(nums.begin(),nums.end(),ostream_iterator(cout," ")); //cout<<endl; int lasti=INT_MIN; int i=0; while(i<size){ if(i!=size-2&&nums[i]==nums[i+1]){ for(int k=i+2;k<size;k++){ if(nums[i]+nums[i+1]+nums[k]==target){ return nums[i]+nums[i+1]+nums[k]; } else if(dist_min>abs(nums[i]+nums[i+1]+nums[k]-target)) { dist_min=abs(nums[i]+nums[i+1]+nums[k]-target); res=nums[i]+nums[i+1]+nums[k]; } } } do{ ++i; if(i==size-1) break; }while(nums[i-1]==nums[i]); if(i==size-1) break; lasti=nums[i]; int lp,rp; lp=0; rp=size-1; int lastlp=INT_MIN; int lastrp=INT_MAX; while(lp<i&&i<rp){ if(nums[lp]+nums[i]+nums[rp]<target){ if(dist_min>target-(nums[lp]+nums[i]+nums[rp])) { dist_min=target-(nums[lp]+nums[i]+nums[rp]); res=nums[lp]+nums[i]+nums[rp]; } lastlp=nums[lp]; while(lastlp==nums[++lp]&&lp<i&&i<rp) ; } else if(nums[lp]+nums[i]+nums[rp]>target){ if(dist_min>(nums[lp]+nums[i]+nums[rp])-target) { dist_min=(nums[lp]+nums[i]+nums[rp])-target; res=nums[lp]+nums[i]+nums[rp]; } lastrp=nums[rp]; while(lastrp==nums[--rp]&&lp<i&&i<rp) ; } else{ //copy(nums.begin(),nums.end(),ostream_iterator(cout," ")); //cout<<endl; return target; //cout<<lp<<" "<<i<<" "<<rp<<" "<<endl; lastlp=nums[lp]; while(lastlp==nums[++lp]&&lp<i&&i<rp) ; } } } return res; }};c++
超级大模拟，直接写就行，没啥可说的。
代码
class Solution {
public:
inline int mymax(int a,int b){
return a>b?a:b;
}
string longestCommonPrefix(const vector<string>& strs) {
string res="";
char cur;
int m_lenth=0;
for(const auto &s:strs){
m_lenth=mymax(m_lenth,s.length());
}
res.reserve(m_lenth);
for(int i=0;i<m_lenth;i++){
for(int j=0;j<strs.size();j++){
if(!j&&i){
res.push_back(cur);
}
if(strs[j].size()<=i){
return res;
}
else{
if(!j){
cur=strs[j][i];
}
else{
if(cur!=strs[j][i]){
return res;
}
}
}
}
}
res.push_back(cur);
return res;
}
};