程序员面试宝典(第6版)之模拟系列算法

文章目录

• 程序员面试宝典(第6版)之模拟系列算法
• • 1.面试题01.05--一次编辑
  • • 1.1模拟
  • 2.面试题01.07--旋转矩阵
  • • 2.1模拟(辅助数组)
    • 2.2模拟(原地旋转)
  • 3.面试题01.08--零矩阵
  • • 3.1模拟(使用两个标记数组)
    • 3.2模拟(使用两个标记变量)
    • 3.3模拟(使用一个标记变量)
  • 4.面试题01.09--字符串轮转
  • • 4.1模拟
    • 4.2strings.Contains

程序员面试宝典(第6版)之模拟系列算法 1.面试题01.05–一次编辑 1.1模拟

func oneEditAway(first, second string) bool {
    m, n := len(first), len(second)
    if m < n {
        return oneEditAway(second, first)//保证m>=n,即保证second对应长的那个字符串
    }
    if m-n > 1 {
        return false
    }
    for i, ch := range second {
        if first[i] != byte(ch) {
            if m == n {
                return first[i+1:] == second[i+1:]
            }
            return first[i+1:] == second[i:]
        }
    }
    return true
}

//时间复杂度：O(m + n)
//空间复杂度：O(1)。

根据题意，两字符串 first , second 能够通过一次（或者零次）编辑互相转换的「充要条件」为:
1.两字符串 first , second 的长度之差≤1 ；
2.当 first , second 长度相等时，两字符串各对应位置只有一个字符不同；
3.当 first , second 长度之差为 1 时，「较短字符串」仅需在某位置添加一个字符，即可转化为「较长字符串」；

2.面试题01.07–旋转矩阵 2.1模拟(辅助数组)

func rotate(matrix [][]int) {
    n := len(matrix)
    tmp := make([][]int, n)
    for i := range tmp {
        tmp[i] = make([]int, n)
    }
    for i, row := range matrix {
        for j, v := range row {
            tmp[j][n-1-i] = v
        }
    }
    copy(matrix, tmp) // 拷贝 tmp 矩阵每行的引用
}

//时间复杂度：O(N^2)
//空间复杂度：O(N^2)

我们以题目中的示例二

对于矩阵中的第一行而言，在旋转后，它出现在倒数第一列的位置,并且，第一行的第 xx 个元素在旋转后恰好是倒数第一列的第 xx 个元素：

对于矩阵中的第二行而言，在旋转后，它出现在倒数第二列的位置：

对于矩阵中的第三行和第四行同理。这样我们可以得到规律：
对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置。

2.2模拟(原地旋转)

func rotate(matrix [][]int) {
    n := len(matrix)
    // 水平翻转
    for i := 0; i < n/2; i++ {
        matrix[i], matrix[n-1-i] = matrix[n-1-i], matrix[i]
    }
    // 主对角线翻转
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }
}

//时间复杂度：O(N^2)。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。
//空间复杂度：O(1)。为原地翻转得到的原地旋转。

我们还是以题目中的示例二

作为例子，先将其通过水平轴翻转得到：

再根据主对角线翻转得到：

3.面试题01.08–零矩阵 3.1模拟(使用两个标记数组)

func setZeroes(matrix [][]int) {
    row := make([]bool, len(matrix))
    col := make([]bool, len(matrix[0]))
    for i, r := range matrix {
        for j, v := range r {
            if v == 0 {
                row[i] = true
                col[j] = true
            }
        }
    }
    for i, r := range matrix {
        for j := range r {
            if row[i] || col[j] {
                r[j] = 0
            }
        }
    }
}

//时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。
//空间复杂度：O(m+n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们需要分别记录每一行或每一列是否有零出现。

我们可以用两个标记数组分别记录每一行和每一列是否有零出现。
具体地，我们首先遍历该数组一次，如果某个元素为 0，那么就将该元素所在的行和列所对应标记数组的位置置为 true。最后我们再次遍历该数组，用标记数组更新原数组即可。

3.2模拟(使用两个标记变量)

func setZeroes(matrix [][]int) {
    n, m := len(matrix), len(matrix[0])
    row0, col0 := false, false
    for _, v := range matrix[0] {
        if v == 0 {
            row0 = true
            break
        }
    }
    for _, r := range matrix {
        if r[0] == 0 {
            col0 = true
            break
        }
    }
    for i := 1; i < n; i++ {
        for j := 1; j < m; j++ {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }
    for i := 1; i < n; i++ {
        for j := 1; j < m; j++ {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }
    if row0 {
        for j := 0; j < m; j++ {
            matrix[0][j] = 0
        }
    }
    if col0 {
        for _, r := range matrix {
            r[0] = 0
        }
    }
}
//时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。
//空间复杂度：O(1)。我们只需要常数空间存储若干变量。

我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1)的额外空间。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 0。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。
在实际代码中，我们首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。

3.3模拟(使用一个标记变量)

func setZeroes(matrix [][]int) {
    n, m := len(matrix), len(matrix[0])
    col0 := false
    for _, r := range matrix {
        if r[0] == 0 {
            col0 = true
        }
        for j := 1; j < m; j++ {
            if r[j] == 0 {
                r[0] = 0
                matrix[0][j] = 0
            }
        }
    }
    for i := n - 1; i >= 0; i-- {
        for j := 1; j < m; j++ {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
        if col0 {
            matrix[i][0] = 0
        }
    }
}
//时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。
//空间复杂度：O(1)。我们只需要常数空间存储若干变量。

4.面试题01.09–字符串轮转 4.1模拟

func isFlipedString(s1 string, s2 string) bool {
    n := len(s1)
    if n != len(s2) {
        return false
    }
    if n == 0 {
        return true
    }
next:
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if s1[(i+j)%n] != s2[j] {
                continue next
            }
        }
        return true
    }
    return false
}

//时间复杂度：O(n^2)
//空间复杂度：O(1)。仅使用常数空间。

4.2strings.Contains

func isFlipedString(s1 string, s2 string) bool {
   return len(s1) == len(s2) && strings.Contains(s1+s1, s2)
}

//时间复杂度：O(n)，其中 n 是字符串 s1的长度。KMP 算法搜索子字符串的时间复杂度为 O(n)，其他搜索子字符串的方法会略有差异。
//空间复杂度：O(n)，其中 n 是字符串 s1 的长度。KMP 算法搜索子字符串的空间复杂度为O(n)，其他搜索子字符串的方法会略有差异。

首先，如果 s1 和 s2 ​的长度不一样，那么无论怎么轮转，s1 都不能得到 s2
，返回 false。字符串 s+s 包含了所有 s1 ​可以通过轮转操作得到的字符串，只需要检查 s2是否为 s+s 的子字符串即可.具体可以参考
28.实现strStr()的实现代码，本题解中采用直接调用库函数的方法。