LeetCode Weekly Contest 181

算法

字数统计: 1.7k阅读时长: 8 min

 2020/03/22   Share

总感觉周赛越来越水了，也许是题目的数据量比较小，所以不需要什么优化，简单模拟就能做出来。

按既定顺序创建目标数组

题目描述

给你两个整数数组 nums 和 index。你需要按照以下规则创建目标数组：

目标数组 target 最初为空。

按从左到右的顺序依次读取 nums[i] 和 index[i]，在 target 数组中的下标 index[i] 处插入值 nums[i] 。

重复上一步，直到在 nums 和 index 中都没有要读取的元素。

请你返回目标数组。

题目保证数字插入位置总是存在。

示例 1：

输入：nums = [0,1,2,3,4], index = [0,1,2,2,1]
输出：[0,4,1,3,2]
解释：
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

示例 2：

输入：nums = [1,2,3,4,0], index = [0,1,2,3,0]
输出：[0,1,2,3,4]
解释：
nums       index     target
1            0        [1]
2            1        [1,2]
3            2        [1,2,3]
4            3        [1,2,3,4]
0            0        [0,1,2,3,4]

提示：

1 <= nums.length, index.length <= 100
nums.length == index.length
0 <= nums[i] <= 100
0 <= index[i] <= i

解法

数据量小，随便怎么做都行，直接模拟一下。

func createTargetArray(nums []int, index []int) []int {
    target := make([]int, len(nums))
    for i := range target {
        target[i] = -1
    }
    for i := 0; i < len(nums); i++ {
        cur := index[i]
        if target[cur] != -1 {
            for j := i - 1; j >= cur; j-- {
                target[j], target[j+1] = target[j+1], target[j]
            }
        }
        target[cur] = nums[i]
    }
    return target
}

四因数

题目描述

给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。

如果数组中不存在满足题意的整数，则返回 0 。

示例：

输入：nums = [21,4,7]
输出：32
解释：
21 有 4 个因数：1, 3, 7, 21
4 有 3 个因数：1, 2, 4
7 有 2 个因数：1, 7
答案仅为 21 的所有因数的和。

提示：

1 <= nums.length <= 10^4
1 <= nums[i] <= 10^5

解法

需要注意的是，这里的因数指的是分成两个因子，而不是所有因子，那就很简单了。

func sumFourDivisors(nums []int) int {
    divisors := make(map[int][]int)
    for _, num := range nums {
        if _, ok := divisors[num]; ok {  // nums 出现了重复的
            continue
        }
        for j := 1; j <= int(math.Sqrt(float64(num))); j++ {
            if num%j == 0 {
                if j == num/j {
                    divisors[num] = append(divisors[num], j)
                } else {
                    divisors[num] = append(divisors[num], j, num/j)
                }
            }
        }
    }
    ans := 0
    for _, num := range nums {
        if len(divisors[num]) == 4 {
            ans += divisors[num][0] + divisors[num][1] + divisors[num][2] + divisors[num][3]
        }
    }
    return ans
}

检查网格中是否存在有效路径

题目描述

给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：

1 表示连接左单元格和右单元格的街道。
2 表示连接上单元格和下单元格的街道。
3 表示连接左单元格和下单元格的街道。
4 表示连接右单元格和下单元格的街道。
5 表示连接左单元格和上单元格的街道。
6 表示连接右单元格和上单元格的街道。

你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。

注意：你不能变更街道。

如果网格中存在有效的路径，则返回 true，否则返回 false 。

示例 1：

输入：grid = [[2,4,3],[6,5,2]]
输出：true
解释：如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m - 1, n - 1) 。

示例 2：

输入：grid = [[1,2,1],[1,2,1]]
输出：false
解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。

示例 3：

输入：grid = [[1,1,2]]
输出：false
解释：你会停在 (0, 1)，而且无法到达 (0, 2) 。

示例 4：

输入：grid = [[1,1,1,1,1,1,3]]
输出：true

示例 5：

输入：grid = [[2],[2],[2],[2],[2],[2],[6]]
输出：true

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6

解法

将这六种街道转换成 3 * 3 的方格，就变成了普通的迷宫问题，深搜广搜都行。

func hasValidPath(grid [][]int) bool {
    m, n := len(grid)*3, len(grid[0])*3
    newGrid := make([][]bool, m)
    for i := range newGrid {
        newGrid[i] = make([]bool, n)
    }
    for i := range grid {  // i 行 j 列
        for j := range grid[i] {
            x, y := 3*j, 3*i  // y 行 x 列
            newGrid[y+1][x+1] = true
            switch grid[i][j] {
            case 1:
                newGrid[y+1][x] = true
                newGrid[y+1][x+2] = true
            case 2:
                newGrid[y][x+1] = true
                newGrid[y+2][x+1] = true
            case 3:
                newGrid[y+1][x] = true
                newGrid[y+2][x+1] = true
            case 4:
                newGrid[y+1][x+2] = true
                newGrid[y+2][x+1] = true
            case 5:
                newGrid[y+1][x] = true
                newGrid[y][x+1] = true
            case 6:
                newGrid[y][x+1] = true
                newGrid[y+1][x+2] = true
            }
        }
    }
    return dfs(1, 1, m, n, newGrid) // 注意起点
}

func dfs(i, j, m, n int, grid [][]bool) bool {
    if i == m-1 && j == n-2 { // 终点
        return true
    }
    if i < 0 || i >= m || j < 0 || j >= n || !grid[i][j] {
        return false
    }
    grid[i][j] = false
    return dfs(i-1, j, m, n, grid) || dfs(i, j-1, m, n, grid) ||
        dfs(i+1, j, m, n, grid) || dfs(i, j+1, m, n, grid)
}

最长快乐前缀

题目描述

「快乐前缀」是在原字符串中既是非空前缀也是后缀（不包括原字符串自身）的字符串。

给你一个字符串 s，请你返回它的 最长快乐前缀。

如果不存在满足题意的前缀，则返回一个空字符串。

示例 1：

输入：s = "level"
输出："l"
解释：不包括 s 自己，一共有 4 个前缀（"l", "le", "lev", "leve"）和 4 个后缀（"l", "el", "vel", "evel"）。最长的既是前缀也是后缀的字符串是 "l" 。

示例 2：

输入：s = "ababab"
输出："abab"
解释："abab" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。

示例 3：

输入：s = "leetcodeleet"
输出："leet"

示例 4：

输入：s = "a"
输出：""

提示：

1 <= s.length <= 10^5
s 只含有小写英文字母

解法

标为困难有点名过其实了，这题本质上就是 KMP 算法中的 Next table，看到有人暴力哈希也过了。

func longestPrefix(s string) string {
    n, k, j := len(s), -1, 0
    next := make([]int, n+1)
    next[0] = -1
    for j < n {
        if k == -1 || s[j] == s[k] {
            k++
            j++
            next[j] = k
        } else {
            k = next[k]
        }
    }
    return s[:next[n]]  // 注意是 n，假设末尾加一个字符
}

原文作者：wywwzjj

原文链接：https://wywwzjj.top/2020/03/22/LeetCode-Weekly-Contest-181/

发表日期：March 22nd 2020, 12:20:39 pm

更新日期：May 15th 2021, 11:53:20 am

Next Post

frida 初体验
Previous Post

LeetCode Weekly Contest 22（双周赛）

CATALOG

1. 按既定顺序创建目标数组
1. 1.1. 题目描述
2. 1.2. 解法
2. 四因数
1. 2.1. 题目描述
2. 2.2. 解法
3. 检查网格中是否存在有效路径
1. 3.1. 题目描述
2. 3.2. 解法
4. 最长快乐前缀
1. 4.1. 题目描述
2. 4.2. 解法

