【优选算法】(第三十一篇)

时间:2024-10-14 15:24:47

目录

最⻓公共前缀(easy)

题目解析

讲解算法原理

编写代码

最⻓回⽂⼦串(medium)

题目解析

讲解算法原理

编写代码


最⻓公共前缀(easy)

题目解析

1.题目链接:. - 力扣(LeetCode)

2.题目描述

编写⼀个函数来查找字符串数组中的最⻓公共前缀。
如果不存在公共前缀,返回空字符串""。
⽰例1:
输⼊:strs=["flower","flow","flight"]
输出:"fl"
⽰例2:
输⼊:strs=["dog","racecar","car"]
输出:""
解释:输⼊不存在公共前缀。

提⽰:
1<=strs.length<=200
0<=strs[i].length<=200
strs[i]仅由⼩写英⽂字⺟组成

讲解算法原理

解法:
算法思路:


解法⼀(两两⽐较):

我们可以先找出前两个的最⻓公共前缀,然后拿这个最⻓公共前缀依次与后⾯的字符串⽐较,这样就可以找出所有字符串的最⻓公共前缀。

解法⼆(统⼀⽐较):


题⽬要求多个字符串的公共前缀,我们可以逐位⽐较这些字符串,哪⼀位出现了不同,就在哪⼀位截⽌。

编写代码
解法一代码:

c++算法代码:

class Solution
{
public:
 string longestCommonPrefix(vector<string>& strs) 
 {
 // 解法⼀:两两⽐较
 string ret = strs[0];
 for(int i = 1; i < strs.size(); i++)
 ret = findCommon(ret, strs[i]);
 return ret;
 }
 string findCommon(string& s1, string& s2)
 {
 int i = 0;
 while(i < min(s1.size(), s2.size()) && s1[i] == s2[i]) i++;
 return s1.substr(0, i);
 }
};

java算法代码:

class Solution
{
 public String longestCommonPrefix(String[] strs) 
 {
 // 解法⼀:两两⽐较
 String ret = strs[0];
 for(int i = 1; i < strs.length; i++)
 {
 ret = findCommon(strs[i], ret);
 }
 return ret;
 }
 public String findCommon(String s1, String s2)
 {
 int i = 0;
 while(i < Math.min(s1.length(), s2.length()) && s1.charAt(i) == 
s2.charAt(i)) 
 i++;
 return s1.substring(0, i);
 }
}
 解法二代码:

c++算法代码:

class Solution
{
public:
 string longestCommonPrefix(vector<string>& strs) 
 {
 // 解法⼆:统⼀⽐较
 for(int i = 0; i < strs[0].size(); i++)
 {
 char tmp = strs[0][i];
 for(int j = 1; j < strs.size(); j++)
 if(i == strs[j].size() || tmp != strs[j][i])
 return strs[0].substr(0, i);
 }
 return strs[0];
 }
};

java算法代码:

class Solution
{
 public String longestCommonPrefix(String[] strs) 
 {
 // 解法⼆:统⼀⽐较
 for(int i = 0; i < strs[0].length(); i++)
 {
 char tmp = strs[0].charAt(i);
 for(int j = 1; j < strs.length; j++)
 {
 if(i == strs[j].length() || strs[j].charAt(i) != tmp)
 return strs[0].substring(0, i);
 }
 }
 return strs[0];
 }
}

最⻓回⽂⼦串(medium)

题目解析

1.题目链接:. - 力扣(LeetCode)

2.题目描述

给你⼀个字符串s,找到s中最⻓的回⽂⼦串。
如果字符串的反序与原始字符串相同,则该字符串称为回⽂字符串。
⽰例1:
输⼊:s="babad"
输出:"bab"
解释:"aba"同样是符合题意的答案。
⽰例2:
输⼊:s="cbbd"
输出:"bb"
提⽰:
1<=s.length<=1000
s仅由数字和英⽂字⺟组成

讲解算法原理

解法(中⼼扩散):
算法思路:

枚举每⼀个可能的⼦串⾮常费时,有没有⽐较简单⼀点的⽅法呢?
对于⼀个⼦串⽽⾔,如果它是回⽂串,并且⻓度⼤于2,那么将它⾸尾的两个字⺟去除之后,它仍然是个回⽂串。如此这样去除,⼀直除到⻓度⼩于等于2时呢?⻓度为1的,⾃⾝与⾃⾝就构成回⽂;⽽⻓度为2的,就要判断这两个字符是否相等了。
从这个性质可以反推出来,从回⽂串的中⼼开始,往左读和往右读也是⼀样的。那么,是否可以枚举回⽂串的中⼼呢?
从中⼼向两边扩展,如果两边的字⺟相同,我们就可以继续扩展;如果不同,我们就停⽌扩展。这样只需要⼀层for循环,我们就可以完成先前两层for循环的⼯作量。

编写代码

c++算法代码:

class Solution
{
public:
 string longestPalindrome(string s) 
 {
 // 中⼼扩展算法
 int begin = 0, len = 0, n = s.size();
 for(int i = 0; i < n; i++) // 依次枚举所有的中点
 {
 // 先做⼀次奇数⻓度的扩展
 int left = i, right = i;
 while(left >= 0 && right < n && s[left] == s[right])
 {
 left--;
 right++;
 }
 if(right - left - 1 > len)
 {
 begin = left + 1;
 len = right - left - 1;
 }
 // 偶数⻓度的扩展
 left = i, right = i + 1;
 while(left >= 0 && right < n && s[left] == s[right])
 {
 left--;
 right++;
 }
 if(right - left - 1 > len)
 {
 begin = left + 1;
 len = right - left - 1;
 }
 }
 return s.substr(begin, len);
 }
};

java算法代码:

class Solution
{
 public String longestPalindrome(String s) 
 {
 int begin = 0, len = 0, n = s.length();
 for(int i = 0; i < n; i++) // 固定所有的中间点
 {
 // 先扩展奇数⻓度的⼦串
 int left = i, right = i;
 while(left >= 0 && right < n && s.charAt(left) == s.charAt(right))
 {
 left--;
 right++;
 }
 if(right - left - 1 > len)
 {
 begin = left + 1;
 len = right - left - 1;
 }
 // 扩展偶数⻓度
 left = i; right = i + 1;
 while(left >= 0 && right < n && s.charAt(left) == s.charAt(right))
 {
 left--;
 right++;
 }
 if(right - left - 1 > len)
 {
 begin = left + 1;
 len = right - left - 1;
 }
 }
 return s.substring(begin, begin + len);
 }
}