leetcode-cn 2021年3月第二周 每日一题

算法之美
1

132. 分割回文串 II

难度困难276收藏分享切换为英文接收动态反馈

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

go

/*
 * @Description: 132
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-03-08 09:42:18
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-03-08 11:14:20
 * @FilePath: \132minCut\132.go
 */
package leetcode

/*
1. 时间换空间，计算任意两个位置是否是回文
2. 然后使用dp计算最小数量
*/
func minCut(s string) int {
	if len(s) <= 1 {
		return 0
	}

	isPaliLen := make([][]bool, len(s)) //保存以当前位置为右边节的最长回文串长度
	for i := 0; i < len(s); i++ {
		isPaliLen[i] = make([]bool, len(s))
	}

	var judgePaliFromMid = func(beg, end int, cnt int) {
		for beg >= 0 && end < cnt && s[beg] == s[end] {
			isPaliLen[beg][end] = true
			beg--
			end++
		}
	}

	for i := 0; i < len(s); i++ {
		judgePaliFromMid(i, i, len(s))
		judgePaliFromMid(i, i+1, len(s))
	}

	//以第i个位置为结尾的子串的最小分割次数
	dp := make([]int, len(s))
	for end := 1; end < len(s); end++ {
		dp[end] = len(s)
		for beg := 0; beg <= end; beg++ {
			if isPaliLen[beg][end] {
				//可以直接break
				if beg == 0 {
					dp[end] = 0
					break
				}
				if dp[beg-1]+1 < dp[end] {
					dp[end] = dp[beg-1] + 1
				}
			}
		}
	}

	return dp[len(s)-1]

}

rust

impl Solution {
    pub fn min_cut(s: String) -> i32 {
        if s.len() <= 1 {
            return 0;
        }
        let mut isPali = vec![vec![false; s.len()]; s.len()];

        let bs = s.into_bytes();
        //预先计算任意区间是否是回文字符串
        let mut judge = |mut x: usize, mut y: usize| {
            while y < bs.len() && bs[x] == bs[y] {
                isPali[x][y] = true;
                if x == 0 {
                    break;
                };
                x -= 1;
                y += 1;
            }
        };
        (0..bs.len()).for_each(|x| {
            judge(x, x);
            judge(x, x + 1);
        });

        //dp计算
        let mut dp = vec![0 as i32; bs.len()];
        for end in 1..bs.len() {

            dp[end] = bs.len() as i32 - 1;

            for beg in 0..end + 1 {
                if isPali[beg][end] {
                    if beg == 0 {
                        dp[end] = 0
                    } else if dp[beg - 1] + 1 < dp[end] {
                        dp[end] = dp[beg - 1] + 1
                    }
                }
            }
        }

        dp[dp.len() - 1]
    }
}
2

1047. 删除字符串中的所有相邻重复项

难度简单140收藏分享切换为英文接收动态反馈

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

go

/*
 * @Description: 1047
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-03-09 09:13:18
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-03-09 10:03:16
 * @FilePath: \1047removeDuplicates\1047.go
 */
package letcode

// 利用栈保存新生成的字符串，然后消消乐
func removeDuplicates(S string) string {

	stack := make([]byte, 0)
	for i := 0; i < len(S); i++ {

		if len(stack) > 0 && stack[len(stack)-1] == S[i] {
			stack = stack[0 : len(stack)-1]
		} else {
			stack = append(stack, S[i])
		}
	}

	return string(stack)

}

rust

/*
 * @Description: 
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-03-09 10:03:59
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-03-09 10:20:25
 * @FilePath: \1047removeDuplicates\remove_duplicates\src\lib.rs
 */
pub struct Solution;

impl Solution {
    pub fn remove_duplicates(s: String) -> String {
        // let s = s.into_bytes();
        let s = s.as_bytes(); //相比使用into_bytes(),内存从2.3M降低到2.2M
        let mut res = Vec::new();
        s.iter().for_each(|x|{
            if let Some(y) = res.last(){
                if y == x{
                    res.pop();
                }else{
                    res.push(*x);
                }
            }else{
                res.push(*x);
            }
        });

    //    unsafe { String::from_utf8_unchecked(res)}

       String::from_utf8_lossy(&res).to_string() //相比上面 从2.2M降低到2.1MB

    }
}

#[cfg(test)]
mod tests {
    use crate::Solution;

    #[test]
    fn it_works() {
        assert_eq!(Solution::remove_duplicates(String::from("abbaca")),String::from("ca"));
        assert_eq!(Solution::remove_duplicates(String::from("aaa")),String::from("a"));
    }
}
3

1047. 删除字符串中的所有相邻重复项

func removeDuplicates(S string) string {
    buf := []byte(S)
    for i:=0; i<len(buf); i++ {
        if i>0 && buf[i] == buf[i-1] {
            buf = append(buf[:i-1], buf[i+1:]...)
            i = i - 2
        }
    }
    return string(buf)
}