binwu
2020 年9 月 17 日 04:09
1
TalkGo 算法之美第二期来啦！
主要是以面试题为主，帮助大家了解面试题目
每次一个主题，周期一般是 1-2 周
小组内深度讨论，通过题解结识朋友
更详细的活动说明：https://github.com/talkgo/newspaper/blob/master/code_interview.md
向组委会负责人缴纳 50 元保证金即成功报名
一次未按时打卡，扣 30 元，二次将被全部扣掉
扣除的保证金作为奖励金分给组长和全勤同学
2020-09-20（本周日） 组长负责启动会（活动讲解、本期主题、规则）
2020-09-22 22:00:00 （下周二）前组员提交第一题答案，组长公布第二题
2020-09-24 22:00:00 （下周四）前组员提交第二题答案，组长公布第三题
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->[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
}
binwu
2020 年9 月 22 日 02:24
3
你的解法是求s1是否包含在s2 题目的意思是s1中的字符是否包含在s2中奥
Kydaa
2020 年9 月 22 日 06:59
5
第一题题解、两种解法：
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)
}
}
binwu
2020 年9 月 22 日 07:11
6
假设字符串只有字母，对于包含非字母的字符串使用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
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)
}
binwu
2020 年9 月 24 日 11:14
9
第二题解答
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]
}
Kydaa
2020 年9 月 24 日 12:37
10
第二题，一开始想着遍历暴力解，实际上机发现不行。实在想不出查了leetcode，好像也只是求长度，方法是用dp来做。
第二题脑容量需要的有点大，就不贴代码了，直接把学费交上。
地址：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
}
Kydaa
2020 年9 月 27 日 01:44
15
这道题比较难，尤其想使用高效算法。
解法一：
// 暴力解法：直接遍历寻找相等子串
// 时间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
}
}
binwu
2020 年9 月 27 日 05:55
17
第三题解答
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 个赞