算法：字符串和二分搜索相关题目

时间：2022-12-11 11:00:00 dkk浓度传感器me61t

字符串面试的概念

回文
子串(连续)、子序列(不连续)
前缀树（Trie树)、后缀树和后缀数组
匹配
字典序

字符串主题类型

规则判断
判断字符串是否符合整数，浮点数
是否返回文本规则
数字运算
与大整数相关的加、减、乘、除操作
与数组操作有关排序技巧，快排划分技巧
字符计数类型
hash表、依据ascii固定长度数组用于统计255、65535
常见的计数题类型:滑动窗口，寻找无重复子串，变位词
动态规划
最长公共子串，最长公共子序列，最长回文子串，最长回文子序列
搜索类型
高级算法数据结构
- 最长回文子串 manachar算法马拉车算法
- kmp 解决字符串匹配问题

# KMP算法 def build_prefix_table(text):     ‘构建前缀表’     prefix = [0]*len(text)     ptr = 0 #公共前缀指针     i = 1     n = len(text)     while i < n:         if text[i] == text[ptr]:             ptr  = 1             prefix[i] = ptr             i  = 1         else:             if ptr > 0:                 ptr = prefix[ptr-1]             else:                 prefix[i] = 0                 i  = 1     print(prefix)     i = n-1     while i>0:         prefix[i] = prefix[i-1]         i -= 1     prefix[0] = -1     print(prefix)     return prefix  pattern = 'ABABCABAA' build_prefix_table(pattern)

def kmp(pattern, text):
    n = len(pattern)
    m = len(text)
    prefix_table = build_prefix_table(pattern)

    i = 0 #pattern索引
    j = 0 #text索引
    while j < m:
        if i == n-1 and pattern[i] == text[j]: #找到匹配字符串
            print("founded at", j-i)
            i = prefix_table[i]
        elif i < n and pattern[i] == text[j]:
            i += 1
            j += 1
        elif i<n:
            i = prefix_table[i]
            if i == -1:
                i += 1
                j += 1

kmp("ABABCABAA","ABABABCABAABABAB")

- 前缀树、后缀树、后缀数组 问题 -- 通常面试极少出现

备注：Java中string类型不可更改，需要使用stringbuffer,stringBuilder或者toCharArray的操作

经典题目

给定彼此独立的两棵树头节点分别为t1和t2，判断t1中是否有与t2树拓扑结构完全相同的子树。
（判断t2是否是t1的子树？）
常规解法：二叉树遍历 + 匹配问题 O(N*M) leetcode 572 树的子树
树A是树B的子树有如下三种情况：
这两个树相等；
树A是树B左子树的子树；
树A是树B右子树的子树；
基于此进行二叉树的遍历加匹配
最优解: 二叉树序列化 + KMP算法 O(N+M)
注意这里的序列化必须加上表示空节点的None，否则无法实现真正的一一对应。
且序列化时必须保证树的头尾也有分割符，这样才能保证字符串匹配时不会出现问题。
给定两个字符串 str1 和 str2 ，判断两个字符串是否互为变形词。
https://leetcode.cn/problems/dKk3P7/
哈希表统计词频 C++ 固定大小数组统计词频 done
给定两个字符串，判断这两个字符串是否互为旋转词。
str1和str2，str1+str1 其实穷举了所有旋转过程，然后使用kmp算法判断str2是否为str1的子串
https://www.nowcoder.com/questionTerminal/687deda2cc57473499e058207f6258cf
https://leetcode.cn/problems/rotate-string/ done
给定一个字符串，在单词间做逆序调整。
https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/
利用python特征 done
给定一个字符串str，以及整数i，请将str[0:i]移到右侧，str[i+1…N-1]移到左侧。要求时间复杂度O(N)，空间复杂度O(1)。
做三次逆序变换。
[0:i]内部做一次逆序；[i+1:N-1]内部做一次逆序
[0:N-1]内部统一做一次逆序

def reverseStr(str, i):
    charArr = list(str)
    n = len(charArr)
    reverse(charArr, 0, i-1)
    reverse(charArr, i, n-1)
    reverse(charArr, 0, n-1)
    print(charArr)

给定一个字符串string，将其中所有空格字符替换成"%20"，假设str后有足够的空间
lc:https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
nowcoder: 剑指offer 替换空格
给定一个字符串string，判断是不是整体有效的括号字符串。
只需要维护一个统计变量，计算右括号与左括号数量的差值。
给定一个字符串string，返回最长无重复字符串子串的长度。
最优：时间复杂度O（n），额外空间复杂度 O（n）
双指针：时间复杂度 O(n)，额外空间复杂度 O(字符串长度)
lc第3题：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

    def lengthOfLongestSubstring(self, s):
        """ :type s: str :rtype: int """
        if not s:
            return 0
        start = 0
        end = 1
        dic = { 
        s[0]:0}
        n = len(s)
        length = 1
        while end < n:
            if s[end] not in dic:
                dic[s[end]] = end
                length = max(length, end-start+1)
            else:
                last = dic[s[end]]
                start = max(last+1, start)
                length = max(length, end-start+1)
                dic[s[end]] = end
            end += 1
        return length

二分搜索

锐单商城拥有海量元器件数据手册、IC替代型号，打造电子元器件IC百科大全！

算法：字符串和二分搜索相关题目

相关文章