刷leetCode算法题+解析（四十二）
公平的糖果交换
题目：爱丽丝和鲍勃有不同大小的糖果棒：A[i] 是爱丽丝拥有的第 i 块糖的大小，B[j] 是鲍勃拥有的第 j 块糖的大小。因为他们是朋友，所以他们想交换一个糖果棒，这样交换后，他们都有相同的糖果总量。（一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。）返回一个整数数组 ans，其中 ans[0] 是爱丽丝必须交换的糖果棒的大小，ans[1] 是 Bob 必须交换的糖果棒的大小。如果有多个答案，你可以返回其中任何一个。保证答案存在。
示例 1：
输入：A = [1,1], B = [2,2]
输出：[1,2]
示例 2：
输入：A = [1,2], B = [2,3]
输出：[1,2]
示例 3：
输入：A = [2], B = [1,3]
输出：[2,3]
示例 4：
输入：A = [1,2,5], B = [2,4]
输出：[5,4]
提示：
1 <= A.length <= 10000
1 <= B.length <= 10000
1 <= A[i] <= 100000
1 <= B[i] <= 100000
保证爱丽丝与鲍勃的糖果总量不同。
答案肯定存在。
思路：这个题感觉操作起来比较麻烦，但是不难。首先要知道这两个孩子糖果数的差值是多少。也就是爱丽丝（+或-）多少等于鲍勃（+或-相同的数）。然后遍历其中一个，判断另一个孩子手中有没有能补平这个差值的，因为题目说肯定有了，直接在for循环返回。接下来我去写实现代码
class Solution {
public int[] fairCandySwap(int[] A, int[] B) {
int sumA = 0;
int sumB = 0;
Set<Integer> set = new HashSet<Integer>();
for(int a :A){
sumA += a;
}
for(int b :B){
sumB += b;
set.add(b);
}
int s = (sumB-sumA)/2;
for(int a:A){
if(set.contains(a+s)){
return new int[]{a,a+s};
}
}
return null;
}
}
性能超过百分之九十五，在我这算合格了。反正闲着也是闲着，我去瞅一眼排行第一的代码：
很新颖的思路。又是数组代替哈希。数组下标代码数字。boolean值代表是否存在。。只能说map或者set的contains太耗费性能。贴上代码瞻仰，然后下一题。
class Solution {
public int[] fairCandySwap(int[] A, int[] B) {
int sumA = 0;
int sumB = 0;
for (int i : A) {
sumA += i;
}
boolean[] flag = new boolean[100001];
for (int i : B) {
sumB += i;
flag[i]=true;
}
int delValue = (sumA - sumB) / 2;
for (int i : A) {
if(0<i-delValue&&i-delValue<=100000&&flag[i-delValue]){
return new int[]{i,i-delValue};
}
}
return null;
}
}
三维形体的表面积
题目：在 N * N 的网格上，我们放置一些 1 * 1 * 1 的立方体。每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。请你返回最终形体的表面积。
示例 1：
输入：[[2]]
输出：10
示例 2：
输入：[[1,2],[3,4]]
输出：34
示例 3：
输入：[[1,0],[0,2]]
输出：16
示例 4：
输入：[[1,1,1],[1,0,1],[1,1,1]]
输出：32
示例 5：
输入：[[2,2,2],[2,1,2],[2,2,2]]
输出：46
提示：
1 <= N <= 50
0 <= grid[i][j] <= 50
思路：虽然这道题我还没做，但是已经看着很眼熟了。昨天做了一个三维形体的阴影。那个是上面，前面，侧面三个方向的面积。这个是全面积，也就是上下前后左右六个面。但是大同小异。尤其是上面和下面是一样的，前后和后面是一样的，左边和右边是一样的。也就是昨天的 * 2。我直接去撸代码了。
好的吧，是我思路错了。这个表面积和阴影还是不一样的，主要是对于有某一位空着的时候，上下看是阴影。但是其实这个空着的左右也是表面积。所以这个要特殊处理。空着的上下左右都有方块多了四个面。只上下有块多了两个面（左右一边没块就行。目前没看到上下左右都没块的测试案例呢，一会儿我去试试有没有）。如果上下或者左右都有一边没块则面积不变，我按照这个思路去试试。
卧槽？？？真的能中空？？？就是外面一圈1，中间一圈0，最中间1.。。真佩服出题人的想象力。
image.png
哎，我觉得我就不应该受昨天那道题的影响，现在我觉得我整个思路都是懵的，我理理这道题要怎么做。
其实这道题可以换种思路反着算。这里的每一个元素是一摞正方形。面积是固定的（上下左右四个面+上下两个1。因为一个元素是摞成一摞的）。然后我们再用总面积去减挨着的面积（比如两个一的块凑一起了，就减去2.比如两个2的块凑一起了就减去4.比如一个1一个2凑一起了减去最小的接触面积，也就是2）以此类推，用总面积一点点减去。我去试着实现。
class Solution {
public int surfaceArea(int[][] grid) {
int result=0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if(grid[i][j]!=0) result += (grid[i][j]*4+2);
if(i<grid.length-1){
result -= Math.min(grid[i][j],grid[i+1][j])*2;
}
if(j<grid[0].length-1){
result -= Math.min(grid[i][j],grid[i][j+1])*2;
}
}
}
return result;
}
}
性能贼可怜，只超过了百分之六十多的人。。。这种感觉，辛苦半天写出来的，心都碎了。我去看看性能排行第一的代码是什么样的。还好在看之前我自己优化了下。以前记得有过这样的情况，这两个数组长度我在反复调用属于多余的计算，然后我这里就改成了常量，一次计算多次使用，果不其然性能上来了！！另外吐槽一下LeetCode的性能测试，真的是随机的么？改完之后性能没变不说消耗还多了，我这一看不科学啊，然后又提交了一次，结果性能飞升到百分之九十七。。
只能说及不及格看脸。不过既然这道题已经及格了，那我就不看别的代码了，直接下一题。
image.png
PS：这里要郑重说一件事，刷题刷恶心了，遇到一个题目，死活看不明白。别说做了。然后看了评论，更懵了，并且都是吐槽这道题的，所以这道题就先过了，实在不想浪费精力看中文阅读理解了。再报一下题号：
893特殊等价字符串组
单调数列
题目：如果数组是单调递增或单调递减的，那么它是单调的。如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。当给定的数组 A 是单调数组时返回 true，否则返回 false。
示例 1：
输入：[1,2,2,3]
输出：true
示例 2：
输入：[6,5,4,4]
输出：true
示例 3：
输入：[1,3,2]
输出：false
示例 4：
输入：[1,2,4,5]
输出：true
示例 5：
输入：[1,1,1]
输出：true
提示：
1 <= A.length <= 50000
-100000 <= A[i] <= 100000
思路：这道题其实也挺简单的，目前的想法创建两个方法，分别判断是否是升序数组和降序数组。然后返回值是二者的||、我去实现了。
思路没问题，一次过，性能超过百分之百。直接贴代码：
class Solution {
public boolean isMonotonic(int[] A) {
return isDesc(A)|| isEsc(A);
}
public boolean isDesc(int[] A){
for(int i=0;i<A.length-1;i++){
if(A[i]<A[i+1]) return false;
}
return true;
}
public boolean isEsc(int[] A){
for(int i=0;i<A.length-1;i++){
if(A[i]>A[i+1]) return false;
}
return true;
}
}
递增顺序查找树
题目：给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。提示：
给定树中的结点数介于 1 和 100 之间。
每个结点都有一个从 0 到 1000 范围内的唯一整数值。
示例如图
思路：指明了要中序遍历了就中序遍历呗。然后再新建个树往上挂右节点。这个没啥好思路，就是简单粗暴呗
中序排列，然后挂树，直接贴代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode increasingBST(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
getNode(root,list);
if(list.size()==0) return null;
TreeNode res = new TreeNode(list.get(list.size()-1));
TreeNode cur = res;
for(int i = list.size()-2;i>=0;i--){
cur = new TreeNode(list.get(i));
cur.right = res;
res = cur;
}
return res;
}
public void getNode(TreeNode root,List<Integer> list){
if(root==null) return;
getNode(root.left,list);
list.add(root.val);
getNode(root.right,list);
}
}
思路没问题，就是性能有点可怜，只超过百分之五十多。我去看看性能排行第一的代码。
看了题解，发现人家的做法，是只有一次
class Solution {
TreeNode res=null;
TreeNode cur=null;
public TreeNode increasingBST(TreeNode root) {
res=new TreeNode(0);
cur=res;
mid(root);
return cur.right;
}
public void mid(TreeNode node){
if(node==null){
return;
}
mid(node.left);
node.left=null;
res.right=node;
res=node;
mid(node.right);
}
}
我的做法是全部求出来数值，然后一个个再挂树上。而人家的做法是在求出一个值挂一个，其实这个做法才是最简洁的，我怎么就想不到呢~~哎这题过。反正自己也对付实现了一个版本，和上面的代码大同小异，但是还是贴出来献献丑，也是性能超过百分百的：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode res;
TreeNode cur;
public TreeNode increasingBST(TreeNode root) {
getTree(root);
return res.right;
}
public void getTree(TreeNode root){
if(root==null) return;
getTree(root.left);
while(cur==null){
res = new TreeNode(root.val);
cur = res;
}
cur.right = new TreeNode(root.val);
cur = cur.right;
getTree(root.right);
}
}
按奇偶排序数组
题目：给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。你可以返回满足此条件的任何数组作为答案。
示例：
输入：[3,1,2,4]
输出：[2,4,3,1]
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。
提示：
1 <= A.length <= 5000
0 <= A[i] <= 5000
思路：这个题很奇怪啊。居然没有进阶条件，比如说要在原数组基础上操作才是对滴呀~~哈哈。其实如果不考虑任何性能这个题还是很简单的，就是单纯的遍历就ok了。尤其是还说了非负数数组简直就是在告诉我们要用这个数据特性搞事情啊。第一思路：创建一个长度相等的数组。第一遍遍历，偶数放进去，第二遍遍历奇数放进去，over
ps:在真正做的时候发现了点问题，这个不用遍历两边，一遍就行了，奇数从后往前插入，偶数从前往后。
emmmmm...思路不错，简单粗暴的做完了，性能超过百分百，一次就过：
class Solution {
public int[] sortArrayByParity(int[] A) {
int[] res = new int[A.length];
int s = 0;
int e = A.length-1;
for(int i : A){
if(i%2==0) {
res[s] = i;
s++;
}else{
res[e] = i;
e--;
}
}
return res;
}
}
最小差值
题目：给定一个整数数组 A，对于每个整数 A[i]，我们可以选择任意 x 满足 -K <= x <= K，并将 x 加到 A[i] 中。在此过程之后，我们得到一些数组 B。返回 B 的最大值和 B 的最小值之间可能存在的最小差值。
示例 1：
输入：A = [1], K = 0
输出：0
解释：B = [1]
示例 2：
输入：A = [0,10], K = 2
输出：6
解释：B = [2,8]
示例 3：
输入：A = [1,3,6], K = 3
输出：0
解释：B = [3,3,3] 或 B = [4,4,4] 提示：
1 <= A.length <= 10000
0 <= A[i] <= 10000
0 <= K <= 10000
思路：这个题最大的难度是理解无能。等理解题意了也就知道了。就是有这么一个数。大于等于-k，小于等于k。然后这个数加到数组的每个元素中，使得数组最大值和最小值差别最小。我发现越简单的题越不用人话讲。我去实现了。
一次过，直接贴代码：
class Solution {
public int smallestRangeI(int[] A, int K) {
int max = 0;
int min = 10001;
for(int i : A){
if(max<i){
max = i;
}
if(min>i){
min = i;
}
}
return max-min-2*K>0?max-min-2*K:0;
}
}
真的，今天遇到两个奇葩的题目描述，我觉得现在刷算法算法是次要的，阅读理解是主要的，哎~~
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。顺便祝大家周末愉快哟~
