刷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中。然后递归。
今天这篇就这里到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！
