TalkGo算法之美第五期

第五期来啦。本期主题是很常见的回文串专题,经常遇到,核心问题解题步骤固定,需要重点掌握。整理出模板,加快解题速度。

本期为期一个月,每周一三五早上八点半左右更新。

参考资料

第一周

周一: 5. 最长回文子串

先了解基本原理,解决基本问题

周三:125. 验证回文串 力扣 查找特殊字符 验证字符串

周五: 131. 分割回文串 力扣 回文串 dp 枚举 dfs

第二周

周一: 336. 回文对 力扣 贪心 字符串查询

周三: 516. 最长回文子序列 力扣 dp

周五: 564. 寻找最近的回文数 力扣 贪心 构造

第三周

周一: 647. 回文子串 力扣 扩展法 manacher dp串查询

周三: 730. 统计不同回文子序列 力扣 枚举 dp(判断)

周五: 866. 回文素数 力扣 素数 回文判断

第四周

周一: 906. 超级回文数 力扣 构造

周三: 1147. 段式回文 力扣 dp kmp

周五: 1177. 构建回文串检测 力扣 贪心 区间求和

3赞

中心扩散算法

func longestPalindrome(s string) string {

    start, end := 0, 0
    for i := range s {
        l, r := diffusion(s, i, i)
        if r-l > end-start {
            start, end = l, r
        }
        l, r = diffusion(s, i, i+1)
        if r-l > end-start {
            start, end = l, r
        }
    }
    return s[start:end+1]
}

func diffusion(s string, l, r int) (int, int) {
    for ;l>=0 && r<len(s) && s[l] == s[r]; l, r = l-1, r+1 {} 
    return l+1, r-1
}
1赞
// CreateTime: 2021-03-01 19:28:31
class Solution {
public:
    string ans = "";

    string longestPalindrome(string s) {
        int len = s.size();
        for (int i = 0; i < len; i++) {
            tryExpand(s, i, i);
            tryExpand(s, i, i+1);
        }
        return ans;
    }

    void tryExpand(string &s, int k1, int k2) {
        int len = s.size();
        while (k1 >= 0 && k2 < len && s[k1] == s[k2]) {
            if (k2-k1+1 > ans.size()) {
                ans = s.substr(k1, k2-k1+1);
            }

            k1--;
            k2++;
        }
    }
};

125

go


func isPalindrome(s string) bool {

	sLen := len(s)
	if sLen == 0 {
		return true
	}

	s = strings.ToLower(s)

	i := 0
	j := sLen - 1

	for i <= j {
		if !(('a' <= s[i] && s[i] <= 'z') || ('0' <= s[i] && s[i] <= '9')) {
			i++
			continue
		}
		if !(('a' <= s[j] && s[j] <= 'z') || ('0' <= s[j] && s[j] <= '9')) {
			j--
			continue
		}

		if s[i] != s[j] {
			return false
		}
		i++
		j--

	}

	return true
}

rust

/*
 * @Description: 
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-03-16 14:29:53
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-03-16 14:53:06
 * @FilePath: /125isPalindrome/is_palindrome/src/lib.rs
 */
pub struct  Solution;
impl Solution {
    pub fn is_palindrome1(s: String) -> bool {
        let b = s.into_bytes();
        let mut i = 0;
        let mut j = b.len()-1;

        while i<j {

            //跳过非字母或数字
            while i<j && (!b[i].is_ascii_alphanumeric()) {i+=1;};
            //跳过非字母或数字
            while i<j && (!b[j].is_ascii_alphanumeric()) {j-=1;};
            if i<j && b[i].to_ascii_uppercase()!=b[j].to_ascii_uppercase(){
                return false
            }
            //由于 j 是usize,所以j有可能变为0,然后 j-=1 后溢出
            if i ==j {
                return true
            }
            i+=1;
            j-=1;
            
        }

        true
    }

    //更巧妙的写法
    pub fn is_palindrome(s: String) -> bool {
        let b = s.into_bytes();
        let mut i = 0;
        let mut j = b.len()-1;

        while i<j {

            //跳过非字母或数字
            if !b[i].is_ascii_alphanumeric() {i+=1;continue;};
            //跳过非字母或数字
            if !b[j].is_ascii_alphanumeric() {j-=1;continue;};

            if b[i].to_ascii_uppercase()!=b[j].to_ascii_uppercase(){
                return false
            }
            i+=1;
            j-=1;
            
        }

        true
    }
}
#[cfg(test)]
mod tests {
    use crate::Solution;
    #[test]
    fn it_works() {
        assert_eq!(Solution::is_palindrome("A man, a plan, a canal: Panama".to_string()),true);
        assert_eq!(Solution::is_palindrome(String::from("race a car")),false);
        assert_eq!(Solution::is_palindrome(String::from("a.")),true);
        assert_eq!(Solution::is_palindrome(String::from(".")),true);
    }
}

125. 验证回文串

双指针暴力解就好,双百解法

func isPalindrome(s string) bool {
    var b1, b2 byte
    for i, j := 0, len(s)-1; i<j; i, j = i+1, j-1 {
        for ;i<j && (s[i]<'a' || s[i]>'z') && (s[i]<'A' || s[i]>'Z') && (s[i]<'0' || s[i]>'9'); i++ {}
        for ;i<j && (s[j]<'a' || s[j]>'z') && (s[j]<'A' || s[j]>'Z') && (s[j]<'0' || s[j]>'9'); j-- {}
        if (s[i]>='A' && s[i]<='Z') {
            b1 = 'a' + s[i] - 'A'
        } else {
            b1 = s[i]
        }
        if (s[j]>='A' && s[j]<='Z') {
            b2 = 'a' + s[j] - 'A'
        } else {
            b2 = s[j]
        }
        if b1 != b2 {
            return false
        }
    }
    return true
}
func needCheck(c byte) bool {
	return (c >= 'A' && c <= 'Z') ||
		(c >= 'a' && c <= 'z') ||
		(c >= '0' && c <= '9')
}

func getVal(c byte) int {
	if c >= 'A' && c <= 'Z' {
		return int(c - 'A') + 1000
	}
	if c >= 'a' && c <= 'z' {
		return int(c - 'a') + 1000
	}
	return int(c - '0')
}

func isPalindrome(s string) bool {
	n := len(s)
	i, j := 0, n-1
	for i < j {
		for i < j && !needCheck(s[i]) {
			i++
		}
		for i < j && !needCheck(s[j]) {
			j--
		}
		if i >= j {
			break
		}
		if getVal(s[i]) != getVal(s[j]) {
			return false
		}
		i++
		j--
	}
	return true
}
// CreateTime: 2021-03-04 10:15:43
class Solution {
public:
    bool isPalindrome(string s) {
        int l = 0;
        int r = s.size()-1;

        while (l < r) {
            while (l < r && !isOk(s[l])) {
                l++;
            }

            while (l < r && !isOk(s[r])) {
                r--;
            }

            if (l < r && !isEqual(s[l], s[r])) {
                return false;
            }
            l++;
            r--;
        }

        return true;
    }

    bool isEqual(char c1, char c2) {
        if (isNum(c1) && isNum(c2)) {
            return c1 == c2;
        } else if (isNum(c1) || isNum(c2)) {
            return false;
        }

        int s1 = 0;
        int s2 = 0;
        if (isUpper(c1)) {
            s1 = c1 - 'A';
        } else {
            s1 = c1 - 'a';
        }

        if (isUpper(c2)) {
            s2 = c2 - 'A';
        } else {
            s2 = c2 - 'a';
        }
        return s1 == s2;
    }

    bool isOk(char c) {
        return isNum(c) || isLower(c) || isUpper(c);
    }

    bool isNum(char c) {
        return '0' <= c && c <= '9';
    }

    bool isLower(char c) {
        return 'a' <= c && c <= 'z';
    }

    bool isUpper(char c) {
        return 'A' <= c && c <= 'Z';
    }
};

回溯

func partition(s string) [][]string {
    ans := make([][]string, 0)
    var backTrace func(str string, arr []string) 
    backTrace = func(str string, arr []string) {
        if len(str) == 0 {
            temp := make([]string, len(arr))
            copy(temp, arr)
            ans = append(ans, temp)
            return 
        }
        for i:=0; i<len(str); i++ {
            if check(str[:i+1]) {
                arr = append(arr, str[:i+1])
                backTrace(str[i+1:], arr)
                arr = arr[:len(arr)-1]
            }
        }
    }
    backTrace(s, []string{})
    return ans
}

func check(s string) bool {
    for i, j := 0, len(s)-1; i<j; i, j = i+1, j-1 {
        if s[i] != s[j] {
            return false
        }
    }
    return true
}
func partition(s string) [][]string {
    n := len(s)
    is := make([][]bool, n)
    ans := make([][]string, 0)
    for i := 0; i < n; i++ {
        is[i] = make([]bool, n)
        is[i][i] = true
    }
    for l := 2; l <= n; l++ {
        for i := 0; i + l - 1 < n; i++ {
            j := i + l - 1
            if i + 1 > j - 1 {
                is[i][j] = s[i] == s[j]
            } else {
                is[i][j] = is[i+1][j-1] && (s[i] == s[j])
            }
        }
    }

    var dfs func(p int, r []string)
    dfs = func(p int, r []string) {
        if p >= n {
            rr := make([]string, len(r))
            copy(rr, r)
            ans = append(ans, rr)
            return 
        }
        for i := p; i < n; i++ {
            if is[p][i] {
                r = append(r, s[p:i+1])
                dfs(i+1, r)
                r = r[:len(r)-1]
            }
        }
    }

    dfs(0, nil)
    return ans
}
// CreateTime: 2021-03-10 21:00:18
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.size();

        vector<vector<int>> f(len+1, vector<int>(len+1));

        for (int i = len-1; i >= 0; i--) {
            f[i][i] = 1;

            for (int j = i+1; j < len; j++) {
                if (s[i] == s[j]) {
                    f[i][j] = f[i+1][j-1]+2;
                } else {
                    f[i][j] = max(f[i][j-1], f[i+1][j]);
                }
            }
        }

        return f[0][len-1];
    }
};

131

go


// 131. 分割回文串 https://leetcode-cn.com/problems/palindrome-partitioning/
func partition(s string) [][]string {

	curList := make([]string, 0)
	result := make([][]string, 0)
	dfs(curList, s, &result)
	return result

}

/*
	dfs 没想到没有超时 8ms 5.3MB
*/
func dfs(curList []string, left string, result *[][]string) {

	if left == "" {
		// tmp := make([]string, len(curList))
		// copy(tmp, curList)
		curList = append(curList[:0:0], curList...) //https://github.com/go101/go101/wiki/How-to-perfectly-clone-a-slice%3F
		*result = append(*result, curList)
		return
	}

	for i := range left {

		if ispalindrome(left[:i+1]) {
			// golang的代码优势就在 这里 curList通过append传入后,传入的是一个新的slice,不会影响当前的 curList,无需回溯
			dfs(append(curList, left[:i+1]), left[i+1:], result)
		}

	}

	return
}

func ispalindrome(s string) bool {
	count := len(s)
	if count == 1 {
		return true
	}
	for i := 0; i < count/2; i++ {
		if s[i] != s[count-i-1] {
			return false
		}
	}

	return true
}

336


/*
1. 提前处理,记录每个单词的各个前缀 ,各个后缀是不是回文
2. 对于每个单词,如果某个前缀是回文,就判断这个单词除去前缀后剩下的部分是否和其他单词对称
3. 对于每个单词,如果某个后缀是回文,就判断这个单词除去后缀后剩下的部分是否和其他单词对称
*/
func palindromePairs(words []string) [][]int {

	//判断某个单词的某个区间是否是回文
	judgePali := func(i, beg, end int) bool {
		for beg < end {
			if words[i][beg] != words[i][end] {
				return false
			}
			beg++
			end--
		}

		return true
	}

	//预处理,提前记录每个单词的逆序的map
	reverseMap := make(map[string]int, 0)
	preMap := make(map[int][]int, 0)  //记录每个单词哪些前缀是回文
	suffMap := make(map[int][]int, 0) //记录每个单词哪些后缀是回文

	for i, w := range words {
		reverseMap[reverse(w)] = i
		for j := 0; j < len(w); j++ {
			if judgePali(i, 0, j) {
				preMap[i] = append(preMap[i], j)
			}
			if judgePali(i, j, len(w)-1) {
				suffMap[i] = append(suffMap[i], j)
			}
		}
	}

	res := make([][]int, 0)
	for i, w := range words {

		if j, ok := reverseMap[w]; ok {
			if i > j {
				res = append(res, []int{i, j})
				res = append(res, []int{j, i})
			}
		}

		//对于回文的每个前缀
		for _, endID := range preMap[i] {
			//判断剩下的部分是否存在 反向的单词
			if j, ok := reverseMap[(w[endID+1:])]; ok {
				res = append(res, []int{j, i})
			}
		}

		//对于回文的每个后缀
		for _, endID := range suffMap[i] {
			//判断剩下的部分是否存在 反向的单词
			if j, ok := reverseMap[(w[:endID])]; ok {
				res = append(res, []int{i, j})
			}
		}
	}

	return res
}

func reverse(s string) string {
	res := make([]byte, len(s))
	for i := 0; i < len(s); i++ {
		res[len(s)-i-1] = s[i]
	}
	return string(res)
}

516

//最长公共子序列的问题
func longestPalindromeSubseq(s string) int {

	if len(s) <= 1 {
		return len(s)
	}

	num := len(s)

	dp := make([][]int, num+1)

	for i := 0; i <= num; i++ {
		dp[i] = make([]int, num+1)
	}

	for i := num; i > 0; i-- {
		for j := i; j <= num; j++ {

			if i == j {
				dp[i][j] = 1
				continue
			}

			if s[i-1] == s[j-1] {
				dp[i][j] = dp[i+1][j-1] + 2
			} else {
				dp[i][j] = max(dp[i][j-1], dp[i+1][j])
			}

		}
	}

	return dp[1][num]

}

func max(i, j int) int {
	if i > j {
		return i
	}

	return j
}

866. 回文素数 力扣

func nextPalindrome(nums *[]int) int {
	n := len(*nums)
	(*nums)[(n-1)/2]++
	for i := (n-1)/2; i >=0; i-- {
		if (*nums)[i] ==10{
			if i ==0{
				*nums = append(*nums, 1)
				(*nums)[i]=1
			}else {
				(*nums)[i]=0
				(*nums)[i-1]++
			}
			(*nums)[n-1-i]=0
		}else {
			(*nums)[n-1-i]=(*nums)[i]
			break
		}
	}
	temp := 0
	for i := 0; i < len(*nums); i++ {
		temp=temp *10+(*nums)[i]
	}
	return temp
}


func Prime(n int) bool {
	if n <=2{
		return n==2
	}
	if n &1==0{
		return false
	}
	for i := 3; i*i <= n; i+=2 {
		if n %i ==0{
			return false
		}
	}
	return true
}

func primePalindrome(n int) int {
	var nums []int
	temp :=n
	for temp != 0 {
		nums = append(nums, temp%10)
		temp /= 10
	}
	for i := 0; i < len(nums); i++ {
		nums[i]=nums[len(nums)-1-i]
	}
	temp = 0
	for i := 0; i < len(nums); i++ {
		temp=temp *10+nums[i]
	}
	for n < 2e8 {
		if temp >=n && Prime(temp){
			break
		}
		temp = nextPalindrome(&nums)
	}
	return temp
}

func isPrime(x int) bool {
	if x == 2 {
		return true
	}
	if x%2 == 0 {
		return false
	}
	for i := 3; i*i <= x; i += 2 {
		if x%i == 0 {
			return false
		}
	}
	return true
}

func base(x int) int {
	r := 1
	for x >= r {
		r *= 10
	}
	return r
}

func calc1(x int) int {
	xx, yy := x, 0
	for x > 0 {
		yy = yy*10 + x%10
		x /= 10
	}
	return xx*base(xx) + yy
}

func calc2(x, d int) int {
	xx, yy := x, 0
	for x > 0 {
		yy = yy*10 + x%10
		x /= 10
	}
	bs := base(xx)
	return xx*bs*10 + d*bs + yy
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func primePalindrome(N int) int {
	ans := int(1e8 * 2)
	for i := 2; i < 10; i++ {
		if i >= N && isPrime(i) {
			return i
		}
	}
haha:
	for i := 1; i <= 1999; i++ {
		for j := 0; j < 10; j++ {
			xx := calc2(i, j)
			if xx >= N && isPrime(xx) {
				ans = minInt(ans, xx)
				break haha
			}
		}
	}

	for i := 1; i <= 9999; i++ {
		xx := calc1(i)
		if xx > ans {
			return ans
		}
		if xx >= N && isPrime(xx) {
			ans = minInt(ans, xx)
			break
		}
	}
	return ans
}
func maxInt(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func check(x int64) bool {
	xx, y := x, int64(0)
	for xx > 0 {
		y = y*10 + xx%10
		xx /= 10
	}
	return x == y
}

func base(x int64) int64 {
	bs := int64(1)
	for bs <= x {
		bs *= 10
	}
	return bs
}

func reverse(x int64) int64 {
	y := int64(0)
	for x > 0 {
		y = y * 10 + x % 10
		x /= 10
	}
	return y
}

func calc(limit int64) int64 {
	cnt := int64(0)
    // 
	for i := int64(1); i < 10 && i*i <= limit; i++ {
		if check(i*i) {
			cnt++
		}
	}
	// 10^4 x 10^4
	for i := int64(1); i <= 10000; i++ {
        bs := base(i)
        rr := reverse(i)
		for j := int64(0); j < 10; j++ {
			xx := i*bs*10 + j * bs + rr
			if xx*xx > limit {
				break
			}
			if check(xx*xx) {
				cnt++
			}
		}
	}
	// 10^4 10^4
	for i := int64(1); i <= 33333; i++ {
		xx := i * base(i) + reverse(i)
		if xx*xx > limit {
			break
		}
		if check(xx*xx) {
			cnt++
		}
	}
	return cnt
}

func superpalindromesInRange(left string, right string) int {
	leftI, _ := strconv.ParseInt(left, 10, 64)
	rightI, _ := strconv.ParseInt(right, 10, 64)
	ans := calc(rightI)
	if leftI - 1 > 0 {
		ans -= calc(leftI-1)
	}
	return int(ans)
}

// 马拉车。。。
func longestPalindrome(s string) string {
start, end := 0, -1
t := “#”
for i := 0; i < len(s); i++ {
t += string(s[i]) + “#”
}
t += “#”
s = t
arm_len := []int{}
right, j := -1, -1
for i := 0; i < len(s); i++ {
var cur_arm_len int
if right >= i {
i_sym := j * 2 - i
min_arm_len := min(arm_len[i_sym], right-i)
cur_arm_len = expand(s, i-min_arm_len, i+min_arm_len)
} else {
cur_arm_len = expand(s, i, i)
}
arm_len = append(arm_len, cur_arm_len)
if i + cur_arm_len > right {
j = i
right = i + cur_arm_len
}
if cur_arm_len * 2 + 1 > end - start {
start = i - cur_arm_len
end = i + cur_arm_len
}
}
ans := “”
for i := start; i <= end; i++ {
if s[i] != ‘#’ {
ans += string(s[i])
}
}
return ans
}

func expand(s string, left, right int) int {
for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1, right+1 { }
return (right - left - 2) / 2
}

func min(x, y int) int {
if x < y {
return x
}
return y
}

各位大佬看看哪错了

func longestPalindrome(s string) string {
	res := ""
	for i := 0; i < len(s); i++ {
		for l,r := i,i; l >= 0 && r < len(s) && s[l] == s[r]; l, r = l-1, r+1 {
			if len(res) < r-l+1 {
				res = s[l : r-l+1]
			}
		}
		for l,r := i,i+1; l >= 0 && r < len(s) && s[l] == s[r]; l, r = l-1, r+1 {
			if len(res) < r-l+1 {
				res = s[l : r-l+1]
			}
		}
	}
	return res
}

请教暴力写法:大佬看看怎么修改

func longestPalindrome(s string) string {
	res := ""
	for i := 0; i < len(s); i++ {
		for l,r := i,i; l >= 0 && r < len(s) && s[l] == s[r]; l, r = l-1, r+1 {
			if len(res) < r-l+1 {
				res = s[l : r-l+1]
			}
		}
		for l,r := i,i+1; l >= 0 && r < len(s) && s[l] == s[r]; l, r = l-1, r+1 {
			if len(res) < r-l+1 {
				res = s[l : r-l+1]
			}
		}
	}
	return res
}

res = s[l :r+1] 这样试试。切片用法理解错了。思路是对的。