字符串

• leetcode3.无重复字符的最长字串
• leetcode30.串联所有单词的子串
• leetcode1234.替换子串得到平衡字符串

leetcode3.无重复字符的最长字串

public int lengthOfLongestSubstring(String s) {
       //如果s为空，length不大于0，是一个空串，就没有向下执行的必要了
        if(s != null && s.length() > 0 && s != ""){
            //String -> char[]
            char[] strChar = s.toCharArray();
            // 存储最长字串 key:char值，value:index下标
            ArrayList<String> maxStr = new ArrayList<>();
            //临时的字串存储空间
            ArrayList<String> tempStr = new ArrayList<>();
            //循环
            for(int i=0; i<strChar.length; i++){
                //char -> String
                String str = new String(new char[]{strChar[i]});
                //判断str是否存在于tempStr中
                if(tempStr.contains(str)){
                    //先判断tempStr的长度是否大于等于maxStr的长度,大于，才能将最长字串覆盖
                    if(tempStr.size() > maxStr.size()){
                        maxStr = new ArrayList<>(tempStr);
                    }
                    //存储重复字符
                    int reIndex = tempStr.indexOf(str);
                    // 删除tempStr中的重复字节及其之前的字符
                    for(int j=0;j<=reIndex;j++){
                        tempStr.remove(0);
                    }
                }
                //将当前字符存入tempStr中
                tempStr.add(str);
            }
            //最终判断
            if(tempStr.size() > maxStr.size()){
                maxStr = tempStr;
            }
            //返回最长字串的长度
            return maxStr.size();
        }
        return 0;
    }

leetcode30.串联所有单词的子串

public static List<Integer> findSubstring(String s, String... words) {List<Integer> list = new ArrayList<>();
	if (s.length() == 0 || words.length == 0)
		return list;
	int len = words[0].length();
	if (s.length() < words.length * len)
		return list;
	int idx = -1;
	char[] sCharS = s.toCharArray();
	Set<Integer> allSet = new HashSet<Integer>();// 存储在字符串S所有匹配的下标 去重 排序
	Map<String, Integer> wordMap = new HashMap<>();// 存储 word中各个单词的个数
	Map<Integer, String> idxMap = new HashMap<>();// 存储字符串s各下标对应的单词
	for (String word : words) {
		if (wordMap.containsKey(word)) {
			wordMap.put(word, wordMap.get(word) + 1);
			continue;
		}
		char[] tem = word.toCharArray();
		while ((idx = indexOf(sCharS, sCharS.length, tem, len, idx + 1)) > -1) {
			idxMap.put(idx, word);
			allSet.add(idx);
		}
		wordMap.put(word, 1);
	}

	String word;
	int slideLen = len * words.length;// 滑块长度
	int n;// 临时变量
	Map<String, Integer> temWordMap = new HashMap<>();
	for (int k = 0; k < len; k++) {
		int flagNum = 0;// 表示滑块中有效的单词个数
		for (int i = -1, j = k; j <= sCharS.length - len; j += len) {
			if (allSet.contains(j)) {
				if (i == -1) {// 初始化滑块
					i = j;
					flagNum = 0;
					temWordMap.clear();
					temWordMap.putAll(wordMap);
				}
				// 滑块长度增加 在尾部添加
				word = idxMap.get(j);
				n = temWordMap.get(word) - 1;
				temWordMap.put(word, n);
				if (n >= 0)
					flagNum++;
				if (j - i >= slideLen) {// 滑块长度减小 吐出头部数据
					word = idxMap.get(i);
					n = temWordMap.get(word) + 1;
					temWordMap.put(word, n);
					if (n > 0)
						flagNum--;
					i += len;
				}
				if (flagNum == words.length)
					list.add(i);
			} else {
				i = -1;// j所在的位置不是给定的单词 ，销毁滑块
			}
		}
	}
	return list;

}

leetcode1234.替换子串得到平衡字符串

 class Solution:
    def balancedString(self, s: str) -> int:
        n = len(s)
        b = n // 4
        from collections import Counter
        counter = Counter(s)
        counter = {key:value for key,value in counter.items() if value > b}
        
        if not counter or n < 4:
            return 0
        rmove = True
        
        l,r = 0,0
        minlen = n
        
        while l <= r and r < n:
            
            if s[r] in counter and rmove:
                counter[s[r]] -= 1
            elif l > 0 and s[l - 1] in counter and not rmove:
                counter[s[l - 1]] += 1

            if {key:value for key,value in counter.items() if value > b}:
                r += 1
                rmove = True
            else:
                minlen = min(minlen, r - l + 1)
                l += 1
                rmove = False
                         
        return minlen

• 点赞
• 收藏
• 分享
• • 文章举报

Guoliang Li 发布了39 篇原创文章 · 获赞 6 · 访问量 5574 私信 关注