5263. 二维网格迁移

给你一个 n 行 m 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。
每次「迁移」操作将会引发下述活动：
位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
位于 grid[i][m - 1] 的元素将会移动到 grid[i + 1][0]。
位于 grid[n - 1][m - 1] 的元素将会移动到 grid[0][0]。
请你返回 k 次迁移操作后最终得到的 二维网格。

拿golang刷题简直有病

执行结果：通过
执行用时 :32 ms, 在所有 golang 提交中击败了100.00%的用户
内存消耗 :6.2 MB, 在所有 golang 提交中击败了100.00%的用户

func pos(n int, m int, k int, x int, y int) (int, int) {
    now := x*m + y
    tmp := (now + k) % (n * m)
    return tmp / m, tmp % m
}
func shiftGrid(grid [][]int, k int) [][]int {
    n := len(grid)
    m := len(grid[0])
    if n == m && n == 1 {
        return grid
    }
    k = k % (n * m)
    var ans = make([][] int, n)
    for i := 0; i < n; i++ {
        ans[i] = make([]int, m)
    }

    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            x, y := pos(n, m, k, i, j)
            ans[x][y] = grid[i][j]
        }
    }
    return ans
}

1261. 在受污染的二叉树中查找元素

给出一个满足下述规则的二叉树：
root.val == 0
如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2
现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。

请你先还原二叉树，然后实现 FindElements 类：

FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

题意比较裸,第一次遍历恢复树,剩余每次遍历按普通二叉树进行遍历即可每次查找O(n),初始化O(n).
优化点:可以将还原后的二叉树层序遍历存进数组,每次二分查找O(logn),初始化O(n)

type FindElements struct {
    root *TreeNode
}
func dfs(root *TreeNode,pre int){
    if root == nil{
        return
    }
    root.Val = pre
    dfs(root.Left,pre*2+1)
    dfs(root.Right, pre*2+2)
}
func Constructor(root *TreeNode) FindElements {
    tmp := new(FindElements)
    tmp.root = root
    dfs(tmp.root,0)
    return *tmp
}
func dfs_find(root *TreeNode, val int)bool{
    if root == nil {
        return false
    }
    if root.Val == val{
        return  true
    }
    return dfs_find(root.Left, val) || dfs_find(root.Right, val)
}
func (this *FindElements) Find(target int) bool {
    return dfs_find(this.root,target)
}

1262. 可被三整除的最大和

给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。
示例 1：

输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。
示例 2：

输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。
示例 3：

输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

很裸的想法,进行dp,每一次dp维护余数状态进行递推.结果也只和余数有关
dp(i,j) , i为数的位置,j为余数,dp(i,j)为总和.
dp(i-1,j)可更新的状态是dp(i,j)和dp(i,(j+now)%3) now为第i位数字
关于状态非法的情况,此处没有使用-1标识,而是允许余数为0且总和为0时进行递推,其他情况状态为0

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}
func maxSumDivThree(nums []int) int {
    n := len(nums)
    dp := make([][]int,n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, 3)
    }
    for i:=1;i<=n;i++{
        now := nums[i-1]
        for j:=0;j<=2;j++{
            if dp[i-1][j] != 0 || j==0 {
                dp[i][(j+now)%3] = max(dp[i-1][j]+now,dp[i][(j+now)%3])
            }
            dp[i][j] = max(dp[i][j],dp[i-1][j])
        }
    }
    return dp[n][0]
}

1263. 推箱子

「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。

游戏地图用大小为 n * m 的网格 grid 表示，其中每个元素可以是墙、地板或者是箱子。

现在你将作为玩家参与游戏，按规则将箱子 'B' 移动到目标位置 'T' ：

玩家用字符 'S' 表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。
地板用字符 '.' 表示，意味着可以自由行走。
墙用字符 '#' 表示，意味着障碍物，不能通行。
箱子仅有一个，用字符 'B' 表示。相应地，网格上有一个目标位置 'T'。
玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
玩家无法越过箱子。
返回将箱子推到目标位置的最小 推动 次数，如果无法做到，请返回 -1。

很久没写这种类型了 待补

有疑问加站长微信联系（非本文作者）