993. 二叉树的堂兄弟节点

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

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

我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 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

提示：

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

解法一：

BFS 宽度优先搜索: 如果 x 和 y 同时出现在同一层，而且 x 和 y 的父节点不同即为 true, 其他情况为 false。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        queue<TreeNode*> que;
        que.push(root);
        while(que.size()) {
            int cnt = que.size();
            bool hasx = false, hasy = false;
            for(int i = 0; i < cnt; i++) {
                auto cur = que.front();
                que.pop();
                if(cur->val == x) hasx = true;
                if(cur->val == y) hasy = true;
                if(cur->left && cur->right) {
                    if(cur->left->val == x && cur->right->val == y || cur->left->val == y && cur->right->val == x) 
                        return false;
                }
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            if(hasx && hasy) return true;
        }
        return false;
    }
};

解法二：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* root1;
    TreeNode* root2;
    int depth1 = -1, depth2 = -1;

    void dfs(TreeNode* root, int x, int y, int h) {
        if(!root) return;
        if(root->left && root->left->val == x) root1 = root, depth1 = h;
        if(root->right && root->right->val == x) root1 = root, depth1 = h;
        if(root->left && root->left->val == y) root2 = root, depth2 = h;
        if(root->right && root->right->val == y) root2 = root, depth2 = h;
        dfs(root->left, x, y, h+1);
        dfs(root->right, x, y, h+1);
    }

    bool isCousins(TreeNode* root, int x, int y) {
        dfs(root, x, y, 0);
        return (depth1 == depth2) && (root1 != root2);
    }
};

解法三：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int getDepth(TreeNode* root, int target, int h) {
        if(!root) return 0;
        if(root->val == target) return h;
        int left = getDepth(root->left, target, h+1);
        int right = getDepth(root->right, target, h+1);
        return max(left, right);
    }

    int getFather(TreeNode* root, int target) {
        if(!root) return 0;
        if(root->left && root->left->val == target) return root->val;
        if(root->right && root->right->val == target) return root->val;
        int left = getFather(root->left, target);
        int right = getFather(root->right, target);
        return max(left, right);
    }

    bool isCousins(TreeNode* root, int x, int y) {
        return getDepth(root, x, 0) == getDepth(root, y, 0) && getFather(root, x) != getFather(root, y);
    }
};

解法四：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int depthx, depthy;
    int fatherx, fathery;

public:
    bool isCousins(TreeNode* root, int x, int y) {
        dfs(root, x, y, 0, 0);
        return depthx == depthy && fatherx != fathery;
    }

    void dfs(TreeNode* root, int x, int y, int depth, int father) {
        if(!root) return ;
        if(root->val == x) {
            depthx = depth;
            fatherx = father;
        }
        else if(root->val == y) {
            depthy = depth;
            fathery = father;
        }
        dfs(root->left, x, y, depth+1, root->val);
        dfs(root->right, x, y, depth+1, root->val);
    }
};

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 <= grid.length <= 10
  • 1 <= grid[0].length <= 10
  • grid[i][j] 仅为 0、1 或 2

解法一：

BFS 宽度优先搜索：将所有腐烂的橘子的坐标输入 queue<TreeNode*> 队列中，然后通过 BFS 将腐烂橘子附近的新鲜橘子腐蚀即可。

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int d[5] = {0, 1, 0, -1, 0};
        queue<pair<int,int>> que;
        int cnt = 0, step = 0;

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 2) que.push({i, j});
                if(grid[i][j] == 1) cnt++;
            }

        while(que.size()) {
            if(cnt == 0) return step;
            int t = que.size();
            while(t--) {
                auto cur = que.front();
                que.pop();
                for(int i = 0; i < 4; i++) {
                    int a = cur.first + d[i], b = cur.second + d[i+1];
                    if(a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == 1) {
                        cnt--;
                        que.push({a, b});
                        grid[a][b] = 2;
                    }
                }                
            }
            step++;
        }              
        return cnt == 0 ? step : -1;
    }
};

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 <= A.length <= 30000
1 <= K <= A.length

解法一：差分数组

由于对同一个子数组执行两次翻转操作不会改变该子数组，所以对每个长度为 k 的子数组，应至多执行一次翻转操作。

对于若干个 kk 位翻转操作，改变先后顺序并不影响最终翻转的结果。不妨从 nums[0] 开始考虑，若 nums[0]=0，则必定要翻转从位置 0 开始的子数组；若 nums[0]=1，则不翻转从位置 0 开始的子数组。

按照这一策略，我们从左到右地执行这些翻转操作。由于翻转操作是唯一的，若最终数组元素均为 1 ，则执行的翻转次数就是最小的。

用 n 表示数组 nums 的长度。若直接模拟上述过程，复杂度将会是 O(nk) 的。如何优化呢？

考虑不去翻转数字，而是统计每个数字需要翻转的次数。对于一次翻转操作，相当于把子数组中所有数字的翻转次数加 11。

这启发我们用差分数组的思想来计算当前数字需要翻转的次数。我们可以维护一个差分数组 diff，其中 diff[i] 表示两个相邻元素 nums[i−1] 和 nums[i] 的翻转次数的差，对于区间 [l,r]，将其元素全部加 1，只会影响到 l 和 r+1 处的差分值，故 diff[l] 增加 1， diff[r+1] 减少 1。

通过累加差分数组可以得到当前位置需要翻转的次数，我们用变量 revCntrevCnt 来表示这一累加值。

遍历到 nums[i] 时，若 nums[i]+revCnt 是偶数，则说明当前元素的实际值为 00，需要翻转区间 [i,i+k−1]，我们可以直接将 revCnt 增加 1, diff[i+k] 减少 1。

注意到若 i+k>n 则无法执行翻转操作，此时应返回 -1−1。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/solution/k-lian-xu-wei-de-zui-xiao-fan-zhuan-ci-s-bikk/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> diff(n+1);
        int ans = 0, revCnt = 0;
        for(int i = 0; i < n; i++) {
            revCnt += diff[i];
            if((nums[i] + revCnt) % 2 == 0) {
                if(i + k > n) return -1;
                revCnt++;
                ans++;
                diff[i+k]--;
            }
        }
        return ans;
    }
};

996. 正方形数组的数目

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

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

示例 1：

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

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-squareful-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：

class Solution {
    // 将满足完全平方数条件的两个点连接成一条边，回溯dfs计算哈密顿路径数量；
    map<int,int> count;         // 存储每个结点值数量
    map<int,vector<int>> graph; /** 存储邻接表，这里把每个结点本身都存进去作为一条
                                    虚拟边，如果该结点值有多个该边存在，如果唯一，
                                    该虚拟边不存在，在遍历邻接表的时候，每次遍历开始
                                    将count[x]--，这样遍历下一条边的时候可以通过count[x] != 0,来过滤掉唯一结点的虚拟边。
                                **/
public:
    int dfs(int x,int todo){   // x is current node,todo is numbers will to resolve
        count[x]--;     // 访问x结点
        int ans = 1;    // 尾结点直接返回 1
        if(todo != 0){
            ans = 0;    // 非尾结点归0，然后统计每个分支的哈密顿路径数
            for(auto& t : graph[x])
                if(count[t] != 0)   // 过滤唯一结点
                    ans += dfs(t,todo-1);    
        }
        count[x]++;     // 恢复x结点
        return ans;     // 尾结点就返回1 非尾结点就返回归零后统计的ans数量
    }
    int numSquarefulPerms(vector<int>& A) {
        // 本题恶心的地方在于去重，利用map存储然后遍历，可以巧妙避免对重复元素在同一深度的多次访问，与之前学习的i!=start && a[i] == a[i-1]一样功效
        int N = A.size();

        /** 初始化count 和 graph **/
        for(auto& i : A) count[i]++;    //count the numbers
        for(auto& p : count)
            for(auto& q : count){
                int sqrt_pq = sqrt(p.first+q.first);
                if(p.first+q.first == sqrt_pq*sqrt_pq) graph[p.first].push_back(q.first);   // every node square graph
            }
        
        /** dfs计算哈密顿路径数量 **/
        int ans = 0;
        for(auto& c : count) ans += dfs(c.first,N-1); 
        return ans;
    }
};
Last modification：July 25, 2021
© Allow specification reprint
如果觉得我的文章对你有用，请随意赞赏