TalkGo 算法之美第二期

TalkGo 算法之美第二期来啦!

活动简介

  1. 主要是以面试题为主,帮助大家了解面试题目
  2. 每次一个主题,周期一般是 1-2 周
  3. 小组内深度讨论,通过题解结识朋友

更详细的活动说明:https://github.com/talkgo/newspaper/blob/master/code_interview.md

活动形式

  1. 向组委会负责人缴纳 50 元保证金即成功报名
  2. 一次未按时打卡,扣 30 元,二次将被全部扣掉
  3. 扣除的保证金作为奖励金分给组长和全勤同学

活动流程

  1. 2020-09-20(本周日) 组长负责启动会(活动讲解、本期主题、规则)
  2. 2020-09-22 22:00:00 (下周二)前组员提交第一题答案,组长公布第二题
  3. 2020-09-24 22:00:00 (下周四)前组员提交第二题答案,组长公布第三题
  4. 2020-09-27 21:00:00 (下周日)本期复盘

参与方式

添加微信: mai_yang 缴纳 50 元保证金即可参与,请备注:TalkGo 算法之美

报名截止时间

2020-09-20 20:00:00 UTC+8

本期组长

binwu

个人介绍 :技术宅男、曾就职于某tiao,现一家共享出行公司架构师

本期题目

本期主题:字符串

题目一

给定字符串 S1,S2, 判断字符串 S1 中的字符是否都在字符串 S2 中(S1 长度 N,S2长度 M)

附加条件:(如果面试官要求时间复杂度O(N) 空间复杂度O(1)呢)

其他:可以模拟面试,逐步加大时间和空间的限制

题目二

2、给定一个字符 S,求 S 最长回文子序列(不是子串,可以不连续)

比如 S:[abfcbea]
返回: abfba 或 abcba

题目三

3、给定M个敏感词汇列表和一段文本,判断文本是否包含敏感词和各个敏感词的位置
例:
敏感词列表
[abc, de, af]
文本
dabcedeabfe

输出
abc->[1]
de->[5]

参考阅读

注:希望成员能能够先独立完成题目

MarkDown

package main

import "fmt"

// 给定字符串 S1,S2, 判断字符串 S1 中的字符是否都在字符串 S2 中(S1 长度 N,S2长度 M)
// 附加条件:(如果面试官要求时间复杂度O(N) 空间复杂度O(1)呢)

func contains(S1, S2 string) bool {
	var N, M int
	N = len(S1)
	M = len(S2)
	if N > M {
		return false
	} else if N == 0 {
		return true
	}

	var i, j int
	for i = 0; i < M-N+1; i++ { // M - (N -1)
		for j = 0; j < N; j++ {
			// 当S1[i] = S2[i+j], 继续右走
			if S2[i+j] != S1[j] {
				break
			}
		}
		if N == j {
			return true
		}
	}

	return false
}

func main() {
	S1 := "abbc"
	S2 := "sdrfafabbcfasd"
	fmt.Println(contains(S1, S2)) // true

	S1 = "abbc"
	S2 = "sdrfafabbdfasd"
	fmt.Println(contains(S1, S2)) // false
}

你的解法是求s1是否包含在s2 题目的意思是s1中的字符是否包含在s2中奥

时间/空间:O(N)/O(N)

func Contains(s1,s2 string)bool {
s2map :=make(map[string]int)
for i,v:=range s2{
s2map[string(v)]=i
}
for _,v:=range s1{
if _,ok:=s2map[string(v)];!ok{
return false
}
}
return true
}
思考:将s2原地排序(快排)后,再用2分法查找;或构建S2的二叉树,会不会好点?但会重构s2,如果要保留s2,map可能好点

第一题题解、两种解法:

import (
	"github.com/stretchr/testify/require"
	"testing"
)

// 用str1的字符,去str2中找有没有相等,如果没有相等的就直接返回false
// 时间复杂度O(N*M) 空间复杂度O(1)
func Solution1(str1, str2 string) bool {
	for _, v := range str1 {
		flag := false
		for _, k := range str2 {
			if v == k {
				flag = true
				break
			}
		}
		if !flag {
			return false
		}
	}
	return true
}

// 给str2建立一个map便签,用于表示str2中的字符存在状况
// 遍历str1,利用map来判断该字符是否存在于str2中
// 时间复杂度O(N) 空间复杂度O(N)
func Solution2(str1, str2 string) bool {
	m := make(map[rune]bool)

	for _, v := range str2 {
		m[v] = true
	}

	for _, v := range str1 {
		if _, ok := m[v]; !ok {
			return false
		}
	}
	return true
}

// 测试
type testNode struct {
	str1     string
	str2     string
	expected bool
}

var data = []testNode{
	{"abc", "banana", false},
	{"abc", "cba", true},
	{"hello", "hello world", true},
	{"test", "tesla", true},
	{"there is a kitty", "there is a cat", false},
}

func TestAllInString1(t *testing.T) {
	for _, v := range data {
		answer := Solution1(v.str1, v.str2)
		require.EqualValues(t, v.expected, answer)
	}
}

func TestAllInString2(t *testing.T) {
	for _, v := range data {
		answer := Solution2(v.str1, v.str2)
		require.EqualValues(t, v.expected, answer)
	}
}

假设字符串只有字母,对于包含非字母的字符串使用map更合适

package main

import "fmt"

func main() {
    isContains := RuneContains("abceddddd", "abcd")
    fmt.Println("contains = ", isContains)
}

func RuneContains(src, dist string) bool {
    aCode := uint8('a')
    bitSet := make([]bool, 26)
    for i := 0; i < len(dist); i++ {
        ival := uint8(dist[i]) - aCode
        bitSet[ival] = true
    }
    
    for i := 0; i < len(src); i++ {
        ival := uint8(src[i]) - aCode
        if !bitSet[ival] {
            return false
        }
    }
    
    return true
}

代码地址:https://github.com/lixianliang/hello-go/tree/master/talkgo/algo02
/*
方法1: 使用hash将s已经存在的字符使用hashmap存储
主串s的长度记为M,子串的长度记为N
时间复杂度:O(N)
空间复杂度:O(M)
*/

func ContainsAny(s, chars string) bool {
	if len(s) == 0 || len(chars) == 0 {
		return false
	}

	chMap := make(map[rune]bool, len(s))
	for _, c := range s {
		chMap[c] = true
	}

	for _, ch := range chars {
		if v, ok := chMap[ch]; !ok {
			fmt.Println(v)
			return false
		}
	}
	return true
}
package s003

// 给定字符串 S1,S2, 判断字符串 S1 中的字符是否都在字符串 S2 中(S1 长度 N,S2长度 M)
func hasContains(str, substr string) bool {
	slen1 := len(str)
	slen2 := len(substr)
	if slen2 > slen1 {
		return false
	}
	for i := 0; i < slen1; i++ {
		tmp := str[i : i+slen2]
		if len(tmp) < slen2 {
			return false
		}
		if tmp == substr {
			return true
		}
	}
	return false
}

单元测试用例:

package s003

import (
	"testing"

	"github.com/stretchr/testify/require"
)

func TestHasContains(t *testing.T) {
	s1, s2 := "123", "12"
	ret := hasContains(s1, s2)
	require.True(t, ret)

	s1, s2 = "123", "1234"
	ret = hasContains(s1, s2)
	require.False(t, ret)

	s1, s2 = "123", "123"
	ret = hasContains(s1, s2)
	require.True(t, ret)
}

第二题解答

package main

import (
    "fmt"
)

func main() {
    s := "adbfcbda"
    ret := LongestPalindrome(s)
    fmt.Println("result = ", ret)
}

type PalindromeResult struct {
    N int
    SubString string
}

func LongestPalindrome(s string) PalindromeResult {
    n := len(s)
    // 初始化二维数组
    board := make([][]PalindromeResult, n)
        for i := range board {
            board[i] = make([]PalindromeResult, n)
        }   

        for i, c := range s {
        board[i][i] = PalindromeResult {
                N: 1,
                SubString: string(c),
        }
        }
    
    for i := n - 1; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            if s[i] == s[j] {
                board[i][j] = PalindromeResult {
                    N: board[i + 1][j - 1].N + 2, 
                    SubString: string(s[i]) + board[i + 1][j - 1].SubString + string(s[j]),
                }
            }else if board[i + 1][j].N > board[i][j - 1].N {
                board[i][j] = PalindromeResult {
                    N: board[i + 1][j].N, 
                    SubString: board[i + 1][j].SubString,
                }
            }else {
                board[i][j] = PalindromeResult {
                    N: board[i][j - 1].N, 
                    SubString: board[i][j - 1].SubString,
                }

            }
        }
    }
    
    return board[0][n - 1]
 }

第二题,一开始想着遍历暴力解,实际上机发现不行。实在想不出查了leetcode,好像也只是求长度,方法是用dp来做。
自己想的是使用两个数组来存储。回过头来看binwu的struct处理方式更加巧妙。代码就不上了,因为确实不是自己想出来的。

第二题脑容量需要的有点大,就不贴代码了,直接把学费交上。

地址:https://github.com/lixianliang/hello-go/blob/master/talkgo/algo02/palindrome.go

/*
	方法:动态规划
	字符串的长度为N
	时间复杂度:O(N*N)
	空间复杂度:O(N*N)
*/
func Palindrom(s string) (int, string) {
	if len(s) < 2 {
		return len(s), s
	}

	var maxN int
	var maxStr string
	// dp为二维数组,第一纬存储子字符串起始位置,第二纬存储终点 dp[i][j]存储s[i,j]回文字符串最大长度
	dp := make([][]int, len(s))
	for i := 0; i < len(s); i++ {
		dp[i] = make([]int, len(s))
	}

	// 构造最大回文字符串map,key为"i_j",value为[i,j]范围内最大的回文字符串
	maxStrMap := make(map[string]string, len(s))
	for i, _ := range dp {
		dp[i][i] = 1
		key := fmt.Sprintf("%d_%d", i, i)
		maxStrMap[key] = string(s[i])
	}

	for i := 1; i < len(s); i++ { // 回文动态规划范围为[2, N], i+1表示当前循环的字符串长度
		for j := 0; i+j < len(s); j++ { // 计算范围[j,i+j]的回文长度和回文字符串,j表示起始字符串
			var oldkey string
			key := fmt.Sprintf("%d_%d", j, i+j)
			if s[j] == s[i+j] { // 字符串s[j]和s[i+j]
				dp[j][i+j] = dp[j+1][i+j-1] + 2 //
				oldkey = fmt.Sprintf("%d_%d", j+1, i+j-1)
				maxStrMap[key] = string(s[j]) + maxStrMap[oldkey] + string(s[i+j])
			} else {
				if dp[j][i+j-1] > dp[j+1][i+j] {
					dp[j][i+j] = dp[j][i+j-1]
					oldkey = fmt.Sprintf("%d_%d", j, i+j-1)
					maxStrMap[key] = maxStrMap[oldkey]
				} else {
					oldkey = fmt.Sprintf("%d_%d", j+1, i+j)
					dp[j][i+j] = dp[j+1][i+j]
				}
				maxStrMap[key] = maxStrMap[oldkey]
			}
		}
	}

	maxN = dp[0][len(s)-1] // 回文最大长度
	key := fmt.Sprintf("%d_%d", 0, len(s)-1)
	maxStr, _ = maxStrMap[key] // 回文最长字符串
	return maxN, maxStr
}
package main

import (

    "fmt"

    "math"

)

// 给定字符串 S1,S2, 判断字符串 S1 中的字符是否都在字符串 S2 中(S1 长度 N,S2长度 M)

// 附加条件:(如果面试官要求时间复杂度O(N) 空间复杂度O(1)呢)

// 时间/空间: M*N/O(1)

func contains(S1, S2 string) bool {

    var N, M int

    N = len(S1)

    M = len(S2)

    if N > M {

        return false

    } else if N == 0 {

        return true

    }

    var i, j int

    for i = 0; i < N; i++ { // 取出S1中所有元素, 逐一进行s2遍历, 看是否存在

        var flag bool // 每遍历一次S1, flag需重置

        for j = 0; j < M; j++ {

            if S1[i] == S2[j] { // 如果存在, 继续走; 不存在则退出

                flag = true

                continue

            }

        }

        if !flag {

            return false

        }

    }

    return true

}

// 给定一个字符 S,求 S 最长回文子序列

// 提供下思路吧, 因为回文的特性: 前后的字符对称, 通过双向指针

// 1. 先从左边字符起(S[i]=a), 判断右边字符是否有一样的字符(j), 不存在则往左边走, 直到左边字符的右边字符(i+1) 

// 2. 若右边字符存在S[j]=a, 则添加到结果字符res=a a, 左边右移一位, 循环

// 3. 遍历出对称的字符(res=abba), 记录到最后满足条件字符的位置(S[i]=S[j])

// 4. 将i与j之间的字符取出(mid=cde), 遍历mid与res进行拼接(abcba, abdba, abeba)

func main() {

    S1 := "abbc"

    S2 := "sdrfafabbcfasd"

    fmt.Println(contains(S1, S2)) // true

    S1 = "abbe"

    S2 = "sdrfafabbdfasd"

    fmt.Println(contains(S1, S2)) // false

}

第三题:github.com/lixianliang/hello-go/talkgo/algo02/substr.go

/*
方法1: 使用朴素匹配算法
主串的长度记为n,子串的长度记为m
时间复杂度:O(n*m)
空间复杂度:O(1)
*/
func BfSubstr(s, substr string) int {
    if len(s) < len(substr) {
        return -1
    }
    if len(substr) == 0 {
        return 0
    }

    // 主串从起始位置[0 - n-m+1]范围内查找字串是否匹配
    for i := 0; i < len(s)-len(substr)+1; i++ {
        if s[i:i+len(substr)] == substr {
            return i
        }
    }

    return -1
}

/*
方法2: 使用BM匹配算法
主串的长度记为N,子串的长度记为M
时间复杂度:O(M)
空间复杂度:O(3*N)  计算比较复杂
*/
func BmSubstr(s, substr string) int {
    if len(s) < len(substr) {
        return -1
    }
    if len(substr) == 0 {
        return 0
    }

    // 字符集散列表,用于不匹配字符串的快速查找(坏字符)
    const CHAR_SIZE = 256
    var bc [CHAR_SIZE]int
    for i := 0; i < len(substr); i++ {
        ascii := int(substr[i])
        bc[ascii] = i
    }
    // fmt.Printf("bc: %v\n", bc)

    suffix, prefix := generateGS(substr)
    // fmt.Printf("suffix:%v prefix:%v\n", suffix, prefix)

    n := len(s)
    m := len(substr)
    i := 0
    for i <= n-m {
        j := 0
        for j = m - 1; j >= 0; j-- { // 从模式匹配串后往前匹配
            if s[i+j] != substr[j] { // 找到不匹配的的字符串
                break
            }
        }
        if j < 0 {
            return i
        }

        step1 := j - bc[int(s[i+j])] // 通过坏字符串计算滑动的位数
        step2 := 0
        if j < m-1 {
            step2 = moveByGS(j, m, suffix, prefix)
        }
        if step1 > step2 {
            i = i + step1
            i = i + step1
        } else {
            i = i + step2
        }
    }

    return -1
}

func generateGS(pattern string) ([]int, []bool) {
    m := len(pattern)
    suffix := make([]int, m)
    prefix := make([]bool, m)
    for i := 0; i < m; i++ {
        suffix[i] = -1
        prefix[i] = false
    }

    for i := 0; i < m-1; i++ { // 循环计算
        j := i
        k := 0 // 公共后缀字串的长度
        for j >= 0 && (pattern[j] == pattern[m-1-k]) {
            // 计算[0-j]的前缀字符串和后缀的公共字串长度
            j--
            k++
            suffix[k] = j + 1 // 后面找到的字符串位置会覆盖之前的,靠后的公共字串用于好后缀移位
        }

        if j == -1 {
            prefix[k] = true // prefix[k]也为前缀子串
        }
    }

    return suffix, prefix
}
func moveByGS(j, m int, suffix []int, prefix []bool) int {
    k := m - 1 - j // 好后缀长度
    if suffix[k] != -1 {
        return j - suffix[k] + 1
    }
    // 部分前缀需要移动的位置
    for i := j + 2; i <= m-1; i++ {
        if prefix[m-i] {
            return i
        }
    }
    return m
}

这道题比较难,尤其想使用高效算法。

解法一:

// 暴力解法:直接遍历寻找相等子串
// 时间O(NM),空间O(1)
func Solution(s1, s2 string) int {
	l1 := len(s1)
	l2 := len(s2)
	// s1长度为0
	if l1 == 0 {
		return 0
	}
	// s2的长度不够
	if l2 == 0 || l2 < l1 {
		return -1
	}

	for i := 0; i <= l2 - l1; i++ {
		if s2[i : i + l1] == s1 {
			return i
		}
	}
	return -1
}

解法二:
具体思路可以看一下这篇:https://www.zhihu.com/question/21923021

// KMP算法
// 时间O(M), 空间O(N)
func KMP(s1, s2 string) int {
	m:=len(s1)
	n:=len(s2)
	if m==0 {
		return 0
	}

	if n<m {
		return -1
	}
	next := computeNext(s1)

	q:=0
	for i:=0;i<n;i++ {
		for q>0 && s2[i]!=s1[q]{
			q=next[q-1]
		}
		if s2[i]==s1[q] {
			q++
		}
		if q == m {
			return i+1-m
		}
	}
	return -1

}

// 生成辅助数组
func computeNext(pattern string) []int {
	n:=len(pattern)
	next:=make([]int,n)
	k:=0
	for i:=1; i<n; i++ {
		for k>0 && pattern[k]!=pattern[i] {
			k=next[k-1]
		}
		if pattern[k]==pattern[i] {
			k++
		}
		next[i]=k
	}
	return next
}

测试:

// 测试
type testNode1 struct {
	str1     string
	str2     string
	expected int
}

var data1 = []testNode1{
	{"abc", "banana", -1},
	{"abc", "cba", -1},
	{"hello", "hello world", 0},
	{"nice", "nicnicnihenicenoce", 10},
	{"abcba", "sjkfabgbaabcbasalkd", 9},
}

func TestAllInString3(t *testing.T) {
	for _, v := range data1 {
		answer := Solution(v.str1, v.str2)
		require.EqualValues(t, v.expected, answer)
	}
}

func TestAllInString4(t *testing.T) {
	for _, v := range data1 {
		answer := KMP(v.str1, v.str2)
		require.EqualValues(t, v.expected, answer)
	}
}
// 3、给定M个敏感词汇列表和一段文本,判断文本是否包含敏感词和各个敏感词的位置
func stringsIndex(S1, S2 string) (bool, int) {
	var N, M int
	N = len(S1)
	M = len(S2)
	if N > M {
		return false, -1
	} else if N == 0 {
		return true, 0
	}

	var i, j int
	for i = 0; i < M-N+1; i++ { // M - (N -1)
		for j = 0; j < N; j++ {
			// 当S1[i] = S2[i+j], 继续右走
			if S2[i+j] != S1[j] {
				break
			}
		}
		if N == j {
			return true, i
		}
	}

	return false, -1
}

func main() {
    S3 := []string{"abc", "de", "af"}
	S4 := "dabcedeabfe"
	for _, str := range S3 {
		fmt.Println(stringsIndex(str, S4)) // true 1, true 5, false -1
	}
}

第三题解答
典型的多模式匹配问题,通常解法:AC自动机
基本原理是Trie树+KMP

package main

import (
  "fmt"
)

func main() {
    p := []string{"he", "said", "her",}

    t := "he said that her wife is good at coding"
    trie := ConstructTrie(p)
    PrintTrie(trie)
    ret := Search(trie, t)
    fmt.Printf("p = %v, s = %s\n", p, t)
    fmt.Printf("ret, %v\n", ret)
}

type TrieNode struct {
    C           rune
    W           string
    IsRoot      bool
    IsWord      bool
    Children    map[rune]*TrieNode
    Fail        *TrieNode
}

// 构建trie树
func InsertNode(root *TrieNode, w string) {
    current := root
    for _, r := range w {
        child, exist := current.Children[r]
        if !exist {
            child = &TrieNode {
                C: r,
                IsRoot: false,
                IsWord: false,
                Children: make(map[rune]*TrieNode, 0),
            }
            current.Children[r] = child
        }
        current = child
    }
    current.W = w; //积累匹配到的值
    current.IsWord = true
}

func ConstructTrie(patterns []string) *TrieNode {
    root := &TrieNode {
        IsRoot: true,
        Children: make(map[rune]*TrieNode, 0),
    }

    for _, s := range patterns {
        InsertNode(root, s)
    }

    ConstructMap(root)
    
    return root
}

// 添加Fail跳转,类似kmp
func ConstructMap(root *TrieNode) {
    queue := []*TrieNode{root}
    for {
        if len(queue) <= 0 {
            break
        }
        var node = queue[0]
        for r, child := range node.Children {
            if node.IsRoot {
                child.Fail = node
            }else {
                current := node.Fail
                for {
                    if current == nil {
                        break
                    }
                    if other, ok := current.Children[r]; ok {
                            child.Fail = other;
                            break;
                    }
                    current = current.Fail;
                }
                if current == nil {
                    child.Fail = root
                }
            }
            queue = append(queue, child)
        }
        queue = queue[1:]
    }
}

func PrintTrie(root *TrieNode) {
    if !root.IsRoot {
        fmt.Printf("Hello, c = %s, is_root = %t, is_word = %t, fail = %v \n", string(root.C), root.IsRoot, root.IsWord, string(root.Fail.C))
    }
    for _, child := range root.Children {
        PrintTrie(child)
    }
}

func Search(root *TrieNode, text string) map[string][]int {
    result := make(map[string][]int, 0)
    current := root
    for i, r := range text {
        for {
            if _, ok := current.Children[r]; !ok && !current.IsRoot {
                current = current.Fail
            }else {
                break
            }
        }

        searched, ok := current.Children[r]
        if !ok {
            current = root
            continue
        }

        if !searched.IsRoot && searched.IsWord {
            if _, ok := result[searched.W]; !ok {
                result[searched.W] = make([]int, 0)
            }
            result[searched.W] = append(result[searched.W], i - len(searched.W) + 1)
        }

        current = searched
    }

    return result
}

1赞

算法之美第三期啥时候出呀

暂时还没有筹备算法之美第三期,谢谢你的关注

哦哦哦,我等你贝贝~