字符串和数组
字符串和数组可以说是各大编程语言中最常见的两种数据结构了，所以要学好一门语言，数组和字符串是必备技能。
刚开始接触字符串最早应该是C语言了，大学里学的。
在C语言中是没有字符串这个类型的，实际的字符串变量我们得到的是一连串字符的首地址。
比如：char *p = "hello ,string"; 单引号是字符，双引号是字符串。这个和Python还是不一样的。
p是指向一连串字符的首地址。其中字符串必须是以"\0"结尾的，这是指针扫描的结束标志位。
当然，C语言还是可以提供字符数组，其实就是普通的数组，只是存储的字符。这也是JAVA语言中String类型实现的基础结构。其实在Python中也是，字符串对像是一个PyStringObject，其内部使用了一个紧凑数组维护了一个字符串。
此外再提一下Redis的字符串，其实现方式一个比较特殊的结构，具体可见我之前写的文章： Redis数据结构 .主要是其设置了一个header，可以通过header获取长度，但其缺点是占内存，因为未达最大容量时，会使用字符进行填充。
在JAVA中提供字符串变量的共3种,String,StringBuilder和StringBuffer。
字符串的相关算法很多，在面试中也会经常问到，在各大语言中其实也有很多的实现。比如反转，分割，拼接，大小写转换，搜索啊，替换，去除空格啊，回文检查啊等等。比如Python,PHP，JAVA等内置的库还是很丰富的。
1、查询第一个最长不重复的字符串：
第一个最长的不重复字符串。主要是使用两个指针，从头开始遍历，并使用两个变量，一个保存当前最长字符串，一个保存临时不重复字符串。空间复杂度常数，即O(1)；时间复杂度：O(n)
JAVA：
package practice.structure;
import java.util.Objects;
/**
* 字符串相关
*/
public class StringData {
/**
* https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
* @param str
* @return
*/
public static String findFirstLongestUnDupString(String str){
if (Objects.isNull(str)||str.isEmpty()){
return null;
}
int len = str.length();
if (len == 1){
return str;
}
int left = 0;
int right = 1;
String longest =str.substring(left,right);
String temp = longest;
while (right <= len - 1){
String subStr = str.substring(right,right+1);
if (temp.contains(subStr)){
if (temp.length() > longest.length()){
longest = temp;
}
int pos = temp.indexOf(subStr);
left = pos + left + 1;
right++;
temp = str.substring(left,right);
} else {
temp = right == len - 1 ? str.substring(left) : str.substring(left,right+1);
right++;
}
}
if (temp.length() > longest.length()){
longest = temp;
}
return longest;
}
public static void main(String[] args){
String a = "pwwkew";
String b = "abcdaeq";
String c = "abcabcbb";
String d = "";
String e = "bbbbbb";
System.out.println(StringData.findFirstLongestUnDupString(a));
System.out.println(StringData.findFirstLongestUnDupString(b));
System.out.println(StringData.findFirstLongestUnDupString(c));
System.out.println(StringData.findFirstLongestUnDupString(d));
System.out.println(StringData.findFirstLongestUnDupString(e));
}
}
Python：
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
size = len(s)
if size <= 1:
return size
left = 0
right = 1
longest = s[0]
temp = longest
while right <= size - 1:
if s[right] in temp:
if len(temp) > len(longest):
longest = temp
left = left + self.findIndex(s[right],temp) + 1
right += 1
temp = s[left:right]
else:
temp = s[left:] if right >= size else s[left:right+1]
right += 1
if len(temp) > len(longest):
longest = temp
print(longest)
return len(longest)
def findIndex(self,cha,s):
for index,value in enumerate(s):
if value == cha:
return index
s = Solution()
print(s.lengthOfLongestSubstring("abcdaeq"))
print(s.lengthOfLongestSubstring("abcabcbb"))
print(s.lengthOfLongestSubstring("pwwkew"))
print(s.lengthOfLongestSubstring(""))
print(s.lengthOfLongestSubstring("bbbbbb"))另外使用hashmap的解法：
public static int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character,Integer> map = new HashMap<>();
int start = 0;
for (int end = 0;end < n;end++){
Character cur = s.charAt(end);
if (map.containsKey(cur)){
start = Math.max(map.get(cur),start);
}
ans = end - start + 1;
map.put(cur,end+1);
}
return ans;
}2、最长回文字符串
比较好的算法就是中心扩展法，有基数和偶数
Python：
def findlongestPalindrome1(string):
start,end = 0,0
for i in range(len(string)):
left1,right1 = exorter(string,i,i)
left2,right2 = exorter(string,i,i+1)
if right1 - left1 > end - start:
start,end = left1,right1
if right2 - left2 > end - start:
start,end = left2,right2
return string[start:end+1]
def exorter(string ,left,right):
while left>=0 and right<len(string) and string[left] == string[right]:
left -= 1
right += 1
return left + 1,right - 1
if __name__ == "__main__":
reslt = findlongestPalindrome1("abcdcbafeg")
print(reslt)JAVA版本：
/**
* 寻找最长回文字符串
* @param str
* @return
*/
public static String findLongestPalindrome(String str){
String sub = str.substring(0,1);
for(int i=0;i<str.length();i++){
String sub1 = exporter(str,i,i);
String sub2 = exporter(str,i,i+1);
if (sub1.length() > sub.length()){
sub = sub1;
}
if (sub2.length() > sub.length()){
sub = sub2;
}
}
return sub;
}
private static String exporter(String str, int left,int right){
while (left>= 0 && right<str.length() && str.charAt(left) == str.charAt(right)){
left--;
right ++;
}
return str.substring(left+1,right);
}
参考资料：
--------EOF---------
微信分享/微信扫码阅读
微信分享/微信扫码阅读
