Leetcode 周赛No.124 笔记

这次周赛四道题目也只做出来两道哈哈哈!不过呢上一次全球排名是三分之一,这次是四分之一了!有进步,继续努力~

不过因为这次周赛时leetcode中文网崩了,所以是在英文网上一边翻译一边做的题,有点点费劲。


993. 二叉树的堂兄弟节点

在二叉树中,根节点位于深度 0 处,每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同,但父节点不同,则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root,以及树中两个不同节点的值 xy

只有与值 xy 对应的节点是堂兄弟节点时,才返回 true。否则,返回 false

示例 1:

输入:root = [1,2,3,4], x = 4, y = 3
输出:false

示例 2:

输入:root = [1,2,3,null,4,null,5], x = 5, y = 4
输出:true

示例 3:

输入:root = [1,2,3,null,4], x = 2, y = 3
输出:false

提示:

  1. 二叉树的节点数介于 2 到 100 之间。
  2. 每个节点的值都是唯一的、范围为 1 到 100 的整数。

思路:

x、y是堂兄弟的两个条件:

  1. x、y不同父。
  2. x、y同层。

针对这两个条件,包装一个类记录节点的父、层数,然后遍历记录之,最后比对x、y的父和层数即可。

//my code
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNodePack root, xn, yn;
    int x, y;
    public boolean isCousins(TreeNode root, int x, int y) {
        this.root = new TreeNodePack(root, 0, new TreeNode(-1));
        this.x = x;
        this.y = y;
        this.dfs(this.root);
        if(this.xn.depth == this.yn.depth && this.xn.father.val != this.yn.father.val)  //判断是不是堂兄弟
            return true;
        return false;
    }
    /* 深搜每个点并封装,遇到x和y点就提出来记录 */
    public void dfs(TreeNodePack n){
        if(n.n.val == this.x)
            this.xn = n;
        if(n.n.val == this.y)
            this.yn = n;
        if(n.n.left != null){
            dfs(new TreeNodePack(n.n.left, n.depth + 1, n.n));
        }
        if(n.n.right != null){
            dfs(new TreeNodePack(n.n.right, n.depth + 1, n.n));
        }
    }
}
/* 包装类 */
class TreeNodePack{
    TreeNode n;  //包装点
    int depth;  //它的层数
    TreeNode father;  //它的父
    TreeNodePack(TreeNode n, int depth, TreeNode father){
        this.n = n;
        this.depth = depth;
        this.father = father;
    }
}

不过呢,把它们包装到一个类中其实有些麻烦了,只要在递归的dfs方法传入父、层数,就可以判断每个点的父、层数了!如下代码:

//neal_wu's code
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    pair<int, int> x_info, y_info;

    void dfs(TreeNode *node, int x, int y, int depth, int parent) {
        if (node->val == x)
            x_info = {depth, parent};

        if (node->val == y)
            y_info = {depth, parent};

        if (node->left != nullptr)
            dfs(node->left, x, y, depth + 1, node->val);

        if (node->right != nullptr)
            dfs(node->right, x, y, depth + 1, node->val);
    }

    bool isCousins(TreeNode *root, int x, int y) {
        dfs(root, x, y, 0, -1);
        return x_info.first == y_info.first && x_info.second != y_info.second;
    }
};

994. 腐烂的橘子

在给定的网格中,每个单元格可以有以下三个值之一:

  • 0 代表空单元格;
  • 1 代表新鲜橘子;
  • 2 代表腐烂的橘子。

每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1

示例 1:

输入:[[2,1,1],[1,1,0],[0,1,1]]
输出:4

示例 2:

输入:[[2,1,1],[0,1,1],[1,0,1]]
输出:-1
解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。

示例 3:

输入:[[0,2]]
输出:0
解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。

提示:

  1. 1 <= grid.length <= 10
  2. 1 <= grid[0].length <= 10
  3. grid[i][j] 仅为 0、1 或 2

思路:

每一分钟时对每一个腐烂橘子上下左右的橘子执行“预腐烂”操作,全部“预腐烂”成功后再将“预腐烂”状态的橘子腐烂掉。

完成条件:

  1. 没有新鲜橘子了。
  2. 即使有新鲜橘子也超过一定时间了(这个时间可以设置为长*宽)。
class Solution {
    int[][] g;
    public int orangesRotting(int[][] grid) {
        this.g = grid;
        int MAXMINUTE = 102;
        int minute = 0;
        for(int i=0; i<MAXMINUTE; i++){
            if(this.getFreshAmount() == 0)
                return minute;  //全烂了
            this.relax();  //芝麻腐烂!
            minute++;
        }
        return -1;
    }
    /* 执行一轮腐烂操作 */
    public void relax(){
        for(int i=0; i<g.length; i++){
            for(int j=0; j<g[0].length; j++){
                if(g[i][j] == 2){
                    if(i-1 >= 0 && g[i-1][j] == 1)
                        g[i-1][j] = 3;  //待腐烂状态
                    if(j-1 >= 0 && g[i][j-1] == 1)
                        g[i][j-1] = 3;
                    if(i+1 < g.length && g[i+1][j] == 1)
                        g[i+1][j] = 3;
                    if(j+1 < g[0].length && g[i][j+1] == 1)
                        g[i][j+1] = 3;
                }
            }
        }
        for(int i=0; i<g.length; i++){
            for(int j=0; j<g[0].length; j++){
                if(g[i][j] == 3)
                    g[i][j] = 2;
            }
        }
    }
    /* 获取当前有几个新鲜的 */
    public int getFreshAmount(){
        int ret = 0;
        for(int i=0; i<g.length; i++){
            for(int j=0; j<g[0].length; j++){
                if(g[i][j] == 1)
                    ret++;
            }
        }
        return ret;
    }
}

发现榜上的代码也没有特别简单的,就不贴啦。


后面两道题是我看过以后知道自己肯定想不出来的题!所以干脆不做了哈哈🤭。

995. K 连续位的最小翻转次数

在仅包含 0 和 1 的数组 A 中,一次 K 位翻转包括选择一个长度为 K 的(连续)子数组,同时将子数组中的每个 0 更改为 1,而每个 1 更改为 0。

返回所需的 K 位翻转的次数,以便数组没有值为 0 的元素。如果不可能,返回 -1

示例 1:

输入:A = [0,1,0], K = 1
输出:2
解释:先翻转 A[0],然后翻转 A[2]。

示例 2:

输入:A = [1,1,0], K = 2
输出:-1
解释:无论我们怎样翻转大小为 2 的子数组,我们都不能使数组变为 [1,1,1]。

示例 3:

输入:A = [0,0,0,1,0,1,1,0], K = 3
输出:3
解释:
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]

提示:

  1. 1 <= A.length <= 30000
  2. 1 <= K <= A.length

思路:

我想到的办法是人工智能的A*算法!!原谅我想太多哈哈哈,看了人家的代码发现其实挺简单的。从左往右遇到0就翻K位好像就ok了。可怕的是这个人这道题在2分10秒就做完了。

//jasonshieh's code
class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        if(A.empty() || K <= 0) return -1;  //特殊值
        int i = 0;
        int n = A.size();
        int res = 0;
        while(i < n){
            //略过数组前边一堆1
            while(i < n && A[i] == 1){
                i++;
            }
            //全为1的话就成了!
            if(i == n) break;
            //剩下的数不够K个就不可能翻成全1了!
            if(n - i < K) return -1;
            //如果能翻,从左往右数遇到的第一个0开始翻起,翻K个
            for(int t = 0; t < K; ++t){
                A[i+t] = (A[i+t] == 0 ? 1 : 0);
            }
            //步数+1
            res++;
        }
        return res;
    }
};

996. 正方形数组的数目

给定一个非负整数数组 A,如果该数组每对相邻元素之和是一个完全平方数,则称这一数组为正方形数组。

返回 A 的正方形排列的数目。两个排列 A1A2 不同的充要条件是存在某个索引 i,使得 A1[i] != A2[i]

示例 1:

输入:[1,17,8]
输出:2
解释:
[1,8,17] 和 [17,8,1] 都是有效的排列。

示例 2:

输入:[2,2,2]
输出:1

提示:

  1. 1 <= A.length <= 12
  2. 0 <= A[i] <= 1e9

思路:

没有思路!

数组相邻两项的平方和必须是一个平方数,用暴力法是可能几百年都无法计算出来的吧。

//nhho's code
//这个不知道是什么语言
/*
 * 思路:有条件的递归遍历解法
 */
bool ok[20][20], u[20];
int n;
int x[20];
int ans;
set<int> s;
class Solution {
public:
    /*
     * 对数组进行递归形式的遍历,递归第a层表示的是这个排列的第a个项
     * a:排列的第a项
     * b:这个排列的第a项的值
     * 排列完全按照题目要求进行排列,因此排完一次就是一个可行解
     */
    void go(int a, int b) {
        if (a == n)  //如果排到最后一项了就是可行解
            ans++;
        else
            /*
             * 否则对于每个剩余可行项尝试递归
             * u[i]:记录i值是否在这个排列中用到了
             */
            for (int i = 0; i < n; i++)
                if (!u[i] && (b == -1 || ok[b][i]) && (i == 0 || x[i] != x[i - 1] || u[i - 1])) {
                    u[i] = 1;
                    go(a + 1, i);
                    u[i] = 0;
                }
    }
    int numSquarefulPerms(vector<int>& A) {
        sort(A.begin(), A.end());
        //遍历2000000000以内平方数存入s
        for (int i = 0; i * i <= 2000000000; i++)
            s.insert(i * i);
        //将A中每两个数相加看看是否是平方数,并将真值存入ok[][]
        for (int i = 0; i < A.size(); i++)
            for (int j = 0; j < A.size(); j++)
                ok[i][j] = s.find(A[i] + A[j]) != s.end();
        //刻印A的副本x
        for (int i = 0; i < A.size(); i++)
            x[i] = A[i];
        ans = 0;
        n = A.size();
        go(0, -1);
        return ans;
    }
};
点赞
  1. Yusorai说道:
    Google Chrome Windows 10

    可能这就叫做大佬吧 φ( ̄∇ ̄o)

  2. 回味依旧说道:
    Google Chrome Windows 10

    这么多人用你的软件竟然都没发现你的博客 我过来逛逛 嘿嘿嘿

  3. 文龙说道:
    Google Chrome Windows 7

    发现软件更新下载好慢,然后就发现了这个博客

发表评论

电子邮件地址不会被公开。必填项已用 * 标注