字符串和数组

字符串和数组可以说是各大编程语言中最常见的两种数据结构了,所以要学好一门语言,数组和字符串是必备技能。

刚开始接触字符串最早应该是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);
    }

参考资料:

C语言数组与字符串

Python字符串实现原理

--------EOF---------
本文微信分享/扫码阅读