头像

痛苦鸭嘴笔


访客:760

离线:11天前



题目描述

给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

样例

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

算法1

(动态规划) $O(n^2)$

定义状态f[i][j]为s1串的前i个字符和s2串的前j个字符之间的距离。由编辑规则可知存在四种状态转移规则:
1. 当s[i] == s[j]时,f[i][j] = f[i-1][j-1]
2. 当s[i] != s[j]时,f[i][j] 可以从三个状态转移,删除第i个字符,删除第j个字符,修改第i个或第j个字符,分别对应f[i-1][j], f[i][j-1], f[i-1][j-1],取最小,然后+1。

时间复杂度

参考文献

Golang 代码

func minDistance(word1 string, word2 string) int {
    slen1, slen2 := len(word1), len(word2)
    f := make([][]int, slen1+1)
    for i := range f {
        f[i] = make([]int, slen2+1)
        for j :=range f[i] {
            f[i][j] = 1<<31 - 1
        }
    }
    for i := 0; i <= slen1; i++ {
        f[i][0] = i
    }
    for i := 0; i <= slen2; i++ {
        f[0][i] = i
    }
    for i := 0; i < slen1; i++ {
        for j := 0; j < slen2; j++ {
            if word1[i] == word2[j] {
                f[i+1][j+1] = f[i][j]
            } else {
                f[i+1][j+1] = min(min(f[i][j+1], f[i+1][j]), f[i][j]) + 1
            }
        }
    }
    return f[slen1][slen2]
}
func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}




题目描述

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

样例

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

算法1

(区间dp) $O(n^2)$

本题求最长回文子串,考虑回文的特点,一个串是回文等价于两边字符相等,且去掉两边字符后中间串仍是回文串,因此可以使用区间dp来做。

定义bool类型f[i][j]为目标串从i到j是否为回文串,初始定义f[i][i]都为true,然后按照区间dp的套路做就行了。

时间复杂度

参考文献

Golang 代码

func longestPalindrome(s string) string {
    n := len(s)
    f := make([][]bool, n)
    for i := range f {
        f[i] = make([]bool, n)
        f[i][i] = true
    }
    for step := 2; step <= n; step++ {
        for i := 0; i <= n-step; i++ {
            j := i+step-1
            f[i][j] = s[i] == s[j] && ((i+1 <= j-1 &&f[i+1][j-1]) || i+1 > j-1)
        }
    }
    for step := n; step >= 1; step-- {
        for i := 0; i <= n-step; i++ {
            j := i+step-1
            if f[i][j] {
                return s[i:j+1]
            }
        }
    }
    return ""
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

算法2

(马拉车算法) $O(n)$

blablabla

时间复杂度

参考文献

Golang 代码

func longestPalindrome(s string) string {
    n := len(s)
    mana := make([]byte, 2*n+1)
    for i := 0; i < n; i++ {
        mana[2*i] = '*'
        mana[2*i+1] = s[i]
    }
    mana[2*n] = '*'
    radis := make([]int, 2*n+1)
    var lim, last int
    res := 0
    resIdx := 0
    var resstr []byte
    for i := 0; i < 2*n+1; i++ {
        if i < lim {
            radis[i] = min(radis[2*last-i], lim-i)
        }
        k := 1
        for i + k < 2*n+1 && i-k >= 0 {
            if mana[i+k] == mana[i-k] {
                radis[i]++
                k++
            } else {
                break
            }
        }
        if radis[i] > lim {
            lim = radis[i]
            last = i
        }
        if res < radis[i] {
            res, resIdx = radis[i], i
        }

    }
    //fmt.Println(res, resIdx)
    for k := resIdx-res; k <= resIdx+res; k++ {
        if mana[k] != '*' {
            resstr = append(resstr, mana[k])
        }
    }
    return string(resstr)
}
func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}



题目描述

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

算法1

(状态机dp) $O(n)$

本题为环形版本打家劫舍,正常来说碰到环形问题,都可以将原数组复值添加到自身后面,然后做一遍处理,取头分别为1到n的答案的最值。但本题并非如此,考察题目特点,对于头结点,最终的答案一定是max(偷了头结点,没偷头结点),所以其实只要对这两种情况求出相应的最高金额即可,还要注意,对于偷了头结点的情况,尾结点不能偷,用f[i][0]表示i结点没偷的最高金额,f[i][1]表示偷了的,所以我们最后返回的就是f[n][0],而没偷头结点的情况,等价于忽略原结点,从下一个结点开始走,最终取最大值是f[n][1],然后两种情况的最值就是结果。

时间复杂度

参考文献

Golang 代码

func rob(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    } else if n == 1 {
        return nums[0]
    } else if n == 2 {
        return max(nums[1], nums[0])
    }
    f := make([][2]int, n)
    f[0][1] = nums[0]
    for i := 1; i < n; i++ {
        f[i][0] = max(f[i-1][0], f[i-1][1])
        f[i][1] = f[i-1][0] + nums[i]
    }
    res := f[n-1][0]
    f[1][0], f[1][1] = 0, nums[1]
    for i := 2; i < n; i++ {
        f[i][0] = max(f[i-1][0], f[i-1][1])
        f[i][1] = f[i-1][0] + nums[i]
    }
    res = max(res, f[n-1][1])
    return res
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}


算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla




算法1

($\mathcal{Tarjin}$缩点) $\mathcal O(n+m)$

本题翻译一下就是找出满足在反图中可以到达所有点的点。
$\mathbb 1$. 暴力做法直接建反图,枚举每个点看能否到达所有点,时间复杂度为平方级别,略高。

$\mathbb 2$. 优化做法是利用tarjin算法先将图缩点变成有向无环图,则在该图中,出度为0的强连通分量若只有一个,则说明有解,否则无解,而解的数量就是该出度为0的强连通分量的点的个数。

$\mathbb 3$. Tarjin算法复习:核心是通过dfs记录时间戳的方式,看能否遇见之前访问过的时间戳,遇到了说明就成环了,更新一路的时间戳。还需要通过栈来保存dfs访问节点的顺序,当碰到一个强连通分量的顶点后,就可以将此强连通分量出栈。

$\mathbb 4$. Tarjin重点数组:dfn保存节点的实际访问时间戳,low保存节点及它所有的子孙节点可以访问到的最小时间戳,若无环则dfn都等于low,并递增,若有环,则low要被更新为之前访问某点的dfn,因此会变小。stk保存所有还未形成强连通分量的点,instk标记点是否还在栈中。还需要视题目要求保存每个分量内点的个数,每个点对应哪个分量。同时最重要的一点,由于dfs的性质,最先形成的强连通分量一定在拓扑图中排最后,所以强连通分量的逆序即是拓扑序,这个性质可以保证不需要再进行拓扑排序了。

Golang 代码

package main
import (
    "os"
    "bufio"
    "strings"
    "strconv"
    "fmt"
)
func main() {
    sc := bufio.NewScanner(os.Stdin)
    buf := make([]byte, 1024*1024)
    sc.Buffer(buf, len(buf))
    sc.Scan()
    str := strings.Fields(sc.Text())
    n, _ := strconv.Atoi(str[0])
    m, _ := strconv.Atoi(str[1])
    head, next, to := make([]int, n+1), make([]int, m+1), make([]int, m+1)
    cnt := 0
    scc_cnt := 0
    timestamp := 0
    dfn, low := make([]int, n+1), make([]int, n+1)
    var stk []int
    instk := make([]bool, n+1)
    var size []int
    id := make([]int, n+1)
    add := func(a, b int) {
        cnt++
        next[cnt], to[cnt], head[a] = head[a], b, cnt
    }
    for i := 1; i <= m; i++ {
        sc.Scan()
        str = strings.Fields(sc.Text())
        a, _ := strconv.Atoi(str[0])
        b, _ := strconv.Atoi(str[1])
        add(a, b)
    }
    var tarjin func(int)
    tarjin = func(h int) {
        timestamp++
        dfn[h], low[h] = timestamp, timestamp
        stk = append(stk, h)
        instk[h] = true
        for i := head[h]; i != 0; i = next[i] {
            tot := to[i]
            if dfn[tot] == 0 {
                tarjin(tot)
                low[h] = min(low[h], low[tot])
            } else if instk[tot] {
                low[h] = min(low[h], dfn[tot])
            }
        }
        if dfn[h] == low[h] {
            size = append(size, 0)
            for {
                top := stk[len(stk)-1]
                stk = stk[:len(stk)-1]
                size[len(size)-1]++
                id[top] = scc_cnt
                instk[top] = false
                if top == h {
                    break
                }
            }
            scc_cnt++
        }
    }
    for i := 1; i <= n; i++ {
        if dfn[i] == 0 {
            tarjin(i)
        }
    }
    deg := make([]int, scc_cnt)
    for i := 1; i <= n; i++ {
        for j := head[i]; j != 0; j = next[j] {
            tot := to[j]
            if id[i] != id[tot] {
                deg[id[i]]++
            }
        }
    }
    ans_cnt := 0
    ans := 0
    for i := 0; i < scc_cnt; i++ {
        if deg[i] == 0 {
            ans_cnt++
            ans = size[i]
        }
    }
    if ans_cnt == 1 {
        fmt.Println(ans)
    } else {
        fmt.Println(0)
    }
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}
func abs(a int) int {
    if a > 0 {
        return a
    }
    return -a
}




算法1

(倍增法) $\mathcal{O}((n+m)*log_2n)$

倍增法求解$\mathbb{LCA}$问题分为两步。
$\mathcal 1$. 预处理出每个节点的father数组,对于fa[i][k],其含义为i号节点向上的第$2^k$个祖先节点的编号,从其定义不难看出可以利用递推求出。在具体求解时,还需要记录一个depth数组,保存i号节点的深度,规定根节点深度为1,利用bfs遍历树,对于每个出队的节点,可以利用该节点的深度更新所有其儿子节点的深度,同时还可以更新fa数组,假如i号节点有儿子j,则不难看出fa[j][0] = i,然后可以利用fa[j][0]继续往上更新fa[j][1],fa[j][2]…,规则为fa[j][k] = fa[fa[j][k-1]][k-1]。遍历完所有节点则depth和fa数组均预处理完毕。

$\mathcal 2$. 查询阶段,对于任意给定的两个节点a和b,思路是先看两个节点深度是否一致,不一致则将更深的节点上浮到浅的那一层,然后判断同深度的这两个节点是否是同一个,是则直接结束,否则还需要两个节点齐头并进上浮,直到两个节点到达同一个位置。具体而言,上浮是通过fa数组实现的,并且上浮的尺度是从大到小,逐位逼近,Tips是可以将depth[0]设为0,这样在更深节点上浮时,如果大尺度的上浮导致浮到了0号节点(无效节点),也可以继续缩小尺度循环(因为depth[0]一定不大于depth[b]);当a和b深度一致后,通过判断fa[a][k]是否等于fa[b][k],判断是否能结束循环,如果不等,则说明可以继续上浮$2^k$,最终结束时fa[a][0]就是答案了。

$\mathcal 3$. 本题就是在以上的基础上套了个距离,因为还是树,所以可以直接保存一个dist数组,在bfs时保存所有节点到root的距离,最终a和b和最短距离就是dist[a] + dist[b] - 2*dist[lca(a, b)]

Golang 代码

package main
import (
    "os"
    "bufio"
    "strings"
    "strconv"
    "fmt"
)
func main() {
    sc := bufio.NewScanner(os.Stdin)
    buf := make([]byte, 1024*1024)
    sc.Buffer(buf, len(buf))
    sc.Scan()
    str := strings.Fields(sc.Text())
    n, _ := strconv.Atoi(str[0])
    m, _ := strconv.Atoi(str[1])
    head, next, to, w := make([]int, n+1), make([]int, n<<1), make([]int, n<<1), make([]int, n<<1)
    cnt := 0
    add := func(a, b, c int) {
        cnt++
        next[cnt], to[cnt], w[cnt], head[a] = head[a], b, c, cnt
    }
    for i := 1; i < n; i++ {
        sc.Scan()
        str = strings.Fields(sc.Text())
        a, _ := strconv.Atoi(str[0])
        b, _ := strconv.Atoi(str[1])
        c, _ := strconv.Atoi(str[2])
        add(a, b, c)
        add(b, a, c)
    }
    dist := make([]int, n+1)
    depth := make([]int, n+1)
    fa := make([][16]int, n+1)
    for i := range dist {
        depth[i] = 1<<31 - 1
    }
    depth[0], depth[1] = 0, 1
    bfs := func(root int) {
        q := []int{root}
        for len(q) > 0 {
            cur := q[0]
            q = q[1:]
            for i := head[cur]; i != 0; i = next[i] {
                tot := to[i]
                if depth[tot] > depth[cur] + 1 {
                    depth[tot] = depth[cur] + 1
                    dist[tot] = dist[cur] + w[i]
                    fa[tot][0] = cur
                    q = append(q, tot)
                    for k := 1; k <= 15; k++ {
                        fa[tot][k] = fa[fa[tot][k-1]][k-1]
                    }
                }
            }
        }
    }
    bfs(1)
    lca := func(a, b int) int {
        if depth[a] < depth[b] {
            a, b = b, a
        }
        for i := 15; i >= 0; i-- {
            if depth[fa[a][i]] >= depth[b] {
                a = fa[a][i]
            }
        }
        if a == b {
            return a
        }
        for i := 15; i >= 0; i-- {
            if fa[a][i] != fa[b][i] {
                a, b = fa[a][i], fa[b][i]
            }
        }
        return fa[a][0]
    }
    for i := 1; i <= m; i++ {
        sc.Scan()
        str = strings.Fields(sc.Text())
        a, _ := strconv.Atoi(str[0])
        b, _ := strconv.Atoi(str[1])
        fmt.Println(dist[a]+dist[b]-2*dist[lca(a, b)])
    }
}



算法1

(差分约束) $O(kE)$

看到这类左右不等式关系的,觉得可以用差分约束搞一搞啊,10万个点,建图也不是问题,SPFA的玄学时间复杂度,竟然还挺快的,400ms。。。

Golang 代码

package main
import (
    "os"
    "bufio"
    "strings"
    "strconv"
    "fmt"
)
func main() {
    sc := bufio.NewScanner(os.Stdin)
    buf := make([]byte, 1024*1024)
    sc.Buffer(buf, len(buf))
    sc.Scan()
    cases, _ := strconv.Atoi(sc.Text())
    for cases > 0 {
        cases--
        sc.Scan()
        n, _ := strconv.Atoi(sc.Text())
        if n == 1 {
            fmt.Println(1)
            continue
        }
        head, next, to, w := make([]int, n+1), make([]int, n<<1+1), make([]int, n<<1+1), make([]int, n<<1+1)
        cnt := 0
        add := func(a, b, c int) {
            cnt++
            next[cnt], to[cnt], w[cnt], head[a] = head[a], b, c, cnt
        }
        sc.Scan()
        str := strings.Fields(sc.Text())
        for i := 0; i < n; i++ {
            l, _ := strconv.Atoi(str[(i-1+n)%n])
            mid, _ := strconv.Atoi(str[(i+n)%n])
            r, _ := strconv.Atoi(str[(i+1)%n])
            if mid <= l && mid <= r {
                add(n, i, 1)
            } else { 
                if mid > l {
                    add((i-1+n)%n, i, 1)
                }
                if mid > r {
                    add((i+1)%n, i, 1)
                }
            }
        }
        spfa := func() int {
            dist := make([]int, n+1)
            q := []int{n}
            inq := make([]bool, n+1)
            for len(q) > 0 {
                cur := q[len(q)-1]
                q = q[:len(q)-1]
                inq[cur] = false
                for i := head[cur]; i != 0; i = next[i] {
                    tot := to[i]
                    if dist[tot] < dist[cur] + w[i] {
                        dist[tot] = dist[cur] + w[i]
                        if !inq[tot] {
                            q = append(q, tot)
                            inq[tot] = true
                        }
                    }
                }
            }
            ans := 0
            for i := 0; i < n; i++ {
                ans += dist[i]
            }
            return ans
        }
        fmt.Println(spfa())
    }
}




Go 代码

func printMatrix(matrix [][]int) []int {
    if len(matrix) == 0 {
        return nil
    }
    r, c := len(matrix), len(matrix[0])
    var res []int
    for i, j := 0, 0; i <= (r-1)>>1 && j <= (c-1)>>1; i, j = i+1, j+1 {
        res = append(res, matrix[i][j:c-j]...)
        for k := i+1; k < r-i-1; k++ {
            res = append(res, matrix[k][c-j-1])
        }
        if r-i-1 != i {
            for k := c-j-1; k >= j; k-- {
                res = append(res, matrix[r-i-1][k])
            }
        }
        if c-j-1 != j {
            for k := r-i-2; k >= i+1; k-- {
                res = append(res, matrix[k][j])
            }
        }
    }
    return res
}