刷leetCode算法题+解析（三十）

学生出勤记录1

题目：给定一个字符串来代表一个学生的出勤记录，这个记录仅包含以下三个字符：

'A' : Absent，缺勤
'L' : Late，迟到
'P' : Present，到场

如果一个学生的出勤记录中不超过一个'A'(缺勤)并且不超过两个连续的'L'(迟到),那么这个学生会被奖赏。你需要根据这个学生的出勤记录判断他是否会被奖赏。

示例 1:
输入: "PPALLP"
输出: True
示例 2:
输入: "PPALLL"
输出: False

思路:别的不说，题也不难，但是制度有点问题啊，只要不连续迟到，隔一天一迟到都奖赏，啧啧，继续说题目，其实这个应该是入门级，实现很容易，我目前打算用性能不咋地但是写起来贼方法的字符串处理方法。顺便附上一个测试案例吐个槽

这样的也是被奖赏的
算了，还是换个方法吧，说一下刚刚说的字符串处理的思路：整个字符串替换"A"为空，如果新串比原串短一个以上则false。
替换“LLL”为空，如果新串比原串短则false。
image.png

但是一想不断替换性能就好不了，所以放弃这种没技术含量的了，直接字符比对吧。

class Solution {
    public boolean checkRecord(String s) {
        int a = 0;
        int l = 0;
        char[] arr = s.toCharArray();
        for(char i:arr){
            if(i=='A'){
                a++;
                if(a>1) return false;
            }
            if(i=='L'){
                l++;
                if(l>2) return false;
            }else{
                l = 0;
            }
        }
        return true;
    }
}

这道题比较简单，不多说了，直接下一题。

反转字符串中的单词

题目：给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 1:
输入: "Let's take LeetCode contest"

输出: "s'teL ekat edoCteeL tsetnoc"
注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

思路：这个题，我听别人说面试的时候真的考过！！！额，关于字符串处理这一块，我是觉得不考虑性能超时啥的，怎么都能做出来。我现在的思路就是根据空格分隔，每个单词反转拼接。
还没写完，但是我已经预计到我这个方法的性能之低了。其实也不是没有别的方法，还有一种用数组处理也行，感觉性能也能高一点（参考上一篇的反转字符串。不过写起来没有这个简单其实。算了，还是追求追求性能吧。毕竟遇到送分题表现好点）

class Solution {
    public String reverseWords(String s) {
        int l = 0;
        char[] arr = s.toCharArray();
        for(int i=0;i<arr.length;i++){
            if(arr[i]==' '){
                reverse(arr,l,i-1);
                l = i+1;
            }
        }
        //最后一个单词是没空格的，所以要额外处理
        reverse(arr,l,arr.length-1);
        return new String(arr);

    }
    public void reverse(char[] arr,int l,int r){
        while(l<r){
            char temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            l++;
            r--;
        }
    }
}

一次完美通过。性能超过百分之九十七多的人。只能说我现在题感贼准，或者说对于性能有了点模糊的认识。比如我知道用字符串来回来去处理追加肯定不如这样，哈哈。既然这个性能已经不错了，我就不看题解了，直接下一题。

四叉树交集

题目：四叉树是一种树数据，其中每个结点恰好有四个子结点：topLeft、topRight、bottomLeft 和 bottomRight。四叉树通常被用来划分一个二维空间，递归地将其细分为四个象限或区域。我们希望在四叉树中存储 True/False 信息。四叉树用来表示 N * N 的布尔网格。对于每个结点, 它将被等分成四个孩子结点直到这个区域内的值都是相同的。每个节点都有另外两个布尔属性：isLeaf 和 val。当这个节点是一个叶子结点时 isLeaf 为真。val 变量储存叶子结点所代表的区域的值。

树A[图片上传中...(image.png-cde0dc-1577085907277-0)]
树B
树C

思路：说实话，题目是真的复杂。看了好几遍也没太看明白，直接看了解析，说下题目要求（自己再打一遍加深印象吧）

A || B 的意思是指

• 如果A为叶子节点，并且A的值等于true, 这时直接返回true, 不用管B
• 如果A为叶子节点，但是A的值等于false, 这时直接返回B就可以了（*注意 即使B不是一个叶子节点，也要直接返回）
• 如果A不为叶子节点， 原理一样，这时看B， 如果B为叶子节点，并且B的值为true, 则直接返回true, 不用管A
• 如果A不为叶子节点， B为叶子节点，并且B的值为false, 这时直接返回A
• 如果A和B都不为叶子节点， 这时分别再讲A, B的四个子节点传入下一次递归计算结果
• 最后， 如果A和B的四个子节点的值都会true的话， 这时需要进行合并为一个节点。

这个除了A,B都不是叶子节点，别的都比较好处理。做完回来了！这个题有bug!自己测试结果前面一个id啥的，我的没有，看了半天没看出是啥玩意，反正和答案不一样，最后一狠心已提交，居然过了。。啧啧

image.png

反正这道题感谢刚刚看的那个大佬的总结，知道那几点规则就好做多了：

/*
// Definition for a QuadTree node.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    public Node() {}

    public Node(boolean _val,boolean _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/
class Solution {
    public Node intersect(Node quadTree1, Node quadTree2) {
        //如果1是叶子节点并且值是false，返回2  如果2是叶子节点值是true直接返回2
        if((quadTree1.isLeaf && !quadTree1.val) || (quadTree2.isLeaf && quadTree2.val)){
            return quadTree2;
        }
        //如果2是叶子节点并且是false，返回1  如果1 是叶子节点值是true直接返回1
        if((quadTree2.isLeaf && !quadTree2.val) || (quadTree1.isLeaf && quadTree1.val)){
            return quadTree1;
        }
        //到这说明1,2都不是叶子节点了，要递归了
        Node res = new Node(false, false, null, null, null, null);
        res.topLeft = intersect(quadTree1.topLeft, quadTree2.topLeft);
        res.topRight = intersect(quadTree1.topRight, quadTree2.topRight);
        res.bottomLeft = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
        res.bottomRight = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
        //合并
        if(res.topLeft.isLeaf && res.topRight.isLeaf
            && res.bottomLeft.isLeaf && res.bottomRight.isLeaf
            && res.topLeft.val == res.topRight.val
            && res.topRight.val == res.bottomLeft.val
            && res.bottomLeft.val == res.bottomRight.val){
            res = res.topLeft;
        }
        return res;
    }
}

其实实际上的代码没多少，一共就几种可能判断。1,2,都是true没必要额外判断一遍，这个属于1是叶子而且true里面。主要就是都不是叶子节点的递归比较麻烦。但是其实逻辑并不是很绕。还是感谢大佬的总结吧。

N叉树的最大高度

题目：给定一个 N 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

题目截图
思路：从二叉到多叉，这就是进步吧？其实我以前也没接触过多叉树，但是感觉应该跟二叉差不多？不知道，我去试试先。
回来了，跟二叉树差不多又有点区别，但是递归是不变的：

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public int maxDepth(Node root) {      
        if(root==null) return 0;
        int max = 0;
        for(int i = 0;i<root.children.size();i++){
            max = Math.max(maxDepth(root.children.get(i)),max);
        }
        return max+1;
    }
}

这个其实也没啥好说的，我测试半天得出正确递归版本，找好递归点就好了，注意逻辑：for循环一遍，但是整体算一层，我之前反正这个+1放循环里了然后得出的答案有点离谱。

数组拆分1

题目：给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。

示例 1:
输入: [1,4,3,2]
输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).

提示:

n 是正整数,范围在 [1, 10000].
数组中的元素范围在 [-10000, 10000].

思路：看了半天也没啥好规律，好像就是隔一个留一个。而且留的是较小的那个。比如一个排序数组，只能留下第0个，2个，反正是下标双数的那个（前提是偶数个元素。）我去写代码试试有啥特殊情况。
嗯嗯，没特殊情况，思路是对的。

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        for(int i=0;i<nums.length;i=i+2){
            res += nums[i];

        }
        return res;
    }
}

至今为止不知道考点在哪？难不成是数组排序么?我去试试手写排序能不能性能好点？算了，不折腾了，看了评论有点写不下去了。

image.png

二叉树的坡度

题目：给定一个二叉树，计算整个树的坡度。一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。整个树的坡度就是其所有节点的坡度之和。

题目截图

思路：这道题怎么说呢，读题没太明白，用两次测试案例大概看懂了。就是每个非叶子节点都有坡度。左右都有就是差的绝对值。单有左右就是左右的绝对值。一看这个题目首选的思路就是递归。每一个非叶子节点的坡度累加。我去试着写写代码。

image.png
image.png
很好，我从原则上就理解错了！也怪我审题不清，刚刚我因为是左子节点和右子节点。而且这个demo也比较短，看不出来啥，我只计算了左右两个直系节点，实际上是左节点和和右节点和的差。
image.png

我继续按照这个思路去做。好了，直接贴代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int sum = 0 ;
    public int findTilt(TreeNode root) {
        addAllNode(root);
        return sum;
    }
    public int addAllNode(TreeNode root){
        if(root==null) return 0;       
        int r = addAllNode(root.right);
        int l = addAllNode(root.left);
        sum +=Math.abs(l-r);
        return l + r + root.val;
    }
}

这个题其实只要审对题还是不难的，就是每一个节点的左节点和减去右节点和。存在sum中。然后递归。
今天这篇就这里到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！