刚刚又把昨天做的几道题重新做了一遍，保证自己做过的都记住，现在开始今天的刷题啦~
两数之和四-输入BST
题目：给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
思路：除了遍历我也没啥思路啊。。好一点的这是一个二叉搜索树，遵循左小右大。。。不行，还是没思路。既然没思路那么最好的办法就是最暴力的实现！全遍历存list排序双指针！
emmm...我就这么无脑的实现了，不要考虑性能还是很不错的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean findTarget(TreeNode root, int k) {
List<Integer> list = new ArrayList<Integer>();
allNode(root,list);
Collections.sort(list);
int l = 0;
int r = list.size()-1;
while(l<r){
if(list.get(l)+list.get(r)==k) return true;
if(list.get(l)+list.get(r)>k){
r--;
}else{
l++;
}
}
return false;
}
public void allNode(TreeNode root,List<Integer> list){
if(root==null) return;
list.add(root.val);
allNode(root.left,list);
allNode(root.right,list);
}
}
看了代码性能第一的思路，就是在每一个给定值减去当前节点，然后遍历树看有没有这个差值，有说明是存在的。没有说明不存在接着判断下一个节点。我去试着写写代码，在改了N次以后终于通过了，鬼知道我经历了什么。
其实这个难点就是要用差值遍历整棵树，所以需要一个整棵树的参数但是还需要当前遍历的树的参数。我这里最大的坑就是两棵树总错来错去的。主要还是思路不清楚吧。也怪我名字起的不好，现在都做完了重新整理开始后悔，应该起的一个叫quan,一个叫dangqian。起码这样绝对不会弄混了（开玩笑的，但是确实因为名字一个root一个node，而且我的root是最开始给定的树也是当前遍历节点的树，所以总弄混。）反正就是一个双递归：
思路整理：
第一步：用给定数减去当前节点值，用差值遍历整个树看是否存在这个值，存在且不是当前节点说明是true。
第二步：如果当前节点差值不存在，则往下遍历，看下一个节点是否存在一对。
第三步：其实这就是一个小技巧。因为左小右大。所以如果给定值比当前节点小则只需要遍历当前节点的左边，反之右边。省去了一般的遍历。
接着贴代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean findTarget(TreeNode root, int k) {
return find(root,root,k);
}
//这两个树要区分好， node是全树 root是遍历到的节点
public boolean find(TreeNode root,TreeNode node, int k){
if(root==null) return false;
TreeNode res = isHasNode(node,k-root.val);
if(res!=root && res!=null) return true;
return find(root.left,node,k) || find(root.right,node,k);
}
public TreeNode isHasNode(TreeNode root,int k){
if(root==null) return null;
if(root.val==k) return root;
if(k<root.val) return isHasNode(root.left,k);
return isHasNode(root.right,k);
}
}
机器人能否返回原点
题目：在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。
示例 1:
输入: "UD"
输出: true
解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。
示例 2:
输入: "LL"
输出: false
解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。
思路:这道题的题目很麻烦，但是我觉得做起来应该相当相当相当简单，因为机器人上下是相互的，上下次数一样才能保证回到原来的水平位置。上移一次下移两次，则最终比原点向下。同样左移右移也要保证一样次数才能返回原来的垂直位置。只要判断上下和左右是不是一样就知道返回原点没有。我感觉思路没问题，我去做做看。
思路完全没问题，简单的不得了，就是不知道为啥性能不咋地。
class Solution {
public boolean judgeCircle(String moves) {
int r = 0;
int l = 0;
int u = 0;
int d = 0;
for(char i:moves.toCharArray()){
if(i=='R') r++;
if(i=='L') l++;
if(i=='U') u++;
if(i=='D') d++;
}
return r==l&&u==d;
}
}
我不知道为啥性能那么低，所以换成字符串，我勒个去，结果更低了：
class Solution {
public boolean judgeCircle(String moves) {
int len = moves.length();
if(len%2!=0) return false;
int r = len-moves.replace("R","").length();
int l = len-moves.replace("L","").length();
if(r!=l) return false;
int u = len-moves.replace("U","").length();
int d = len-moves.replace("D","").length();
if(u!=d) return false;
return true;
}
}
还是直接看性能第一的怎么写的吧：额，条条大路通罗马，我这里一个个if都得挨个判断，用if -else if -else好了。还有人用switch -case也行，
最高性能的是用的数组：
int[] move = new int[128];
for(char c : moves.toCharArray())
move[c]++;
return move['U'] == move['D'] && move['L'] == move['R'];
}
反正八仙过海吧，这个题比较简单，就不多说了。
图片平滑器
题目：包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。
示例 1:
输入:
[[1,1,1],
[1,0,1],
[1,1,1]]
输出:
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0
注意:
给定矩阵中的整数范围为 [0, 255]。
矩阵的长和宽的范围均为 [1, 150]。
思路：别说啥思路不思路啊，我觉得现在阅读理解都有问题了，看了两遍都没太看懂题目呢。系统给的例子太少了，而且我理解能力不行，自己测试了两个demo才多少有个了解了：如下图，每一个点都要判断周围一圈+自己的平均值（向下取整），这样把每一个点判断一次就行了。其实应该不难。就是因为是二维数组可能会实现略墨迹。我去写代码了。
这个题简直一言难尽，我就这么说吧，我做出来了，掉了一把头发的前提下做出来了，很符合java规范，循环不得超过三层：
然后差点没写吐了，我寻思看看大神的思路，简单明了清晰，完美四层循环解决问题。只能说只要思想不滑坡，办法总比问题多。我承认性能不是那么好，但是！！！起码代码写起来看起来都方便易懂。
虽然四层循环但是里面两层最多九次，其实也没那么可怕。反正我是爱了（题解里最爱这种方法了）。
class Solution {
public int[][] imageSmoother(int[][] M) {
int len = M.length;
int r = M[0].length;
int[][] res = new int[len][r];
for(int i=0;i<len;i++){
for(int j=0;j<r;j++){
int count = 0;
int sum = 0;
for(int k=i-1;k<=i+1;k++){
for(int l=j-1;l<=j+1;l++){
if(k>=0&&k<len&&l>=0&&l<r){
count++;
sum += M[k][l];
}
}
}
res[i][j] = sum/count;
}
}
return res;
}
}
至于别的性能优的解法说真的，反而没有什么亮点。就是生算。用大量代码来换性能。这么说吧，排第一的代码量差不多是上面代码的三倍还多。也贴出来看看：
class Solution {
public int[][] imageSmoother(int[][] M) {
if(M.length <= 1 && M[0].length <= 1) return M;
if(M.length <= 1) return singletonRow(M);
if(M[0].length <= 1)return singletonColunm(M);
//使用行列计算
int[] one = new int[M[0].length];
int[] two = new int[M[0].length];
int tail = M[0].length - 1;
int height = M.length - 1;//这里代表的是高度-1
//记录第一行的值,头和尾只加两个
one[0] = M[0][0] + M[0][1];
for(int i=1;i<tail;i++){
one[i] = M[0][i-1] + M[0][i] + M[0][i+1];
}
one[tail] = M[0][tail-1] + M[0][tail];
//记录第二行的值,并计算M的第一行
two[0] = M[1][0] + M[1][1];
M[0][0] = (one[0] + two[0]) / 4;
for(int i=1;i<tail;i++){
two[i] = M[1][i-1] + M[1][i] + M[1][i+1];
M[0][i] = (one[i] + two[i]) / 6;
}
two[tail] = M[1][tail-1] + M[1][tail];
M[0][tail] = (one[tail] + two[tail]) / 4;
//计算M的第2行到 M.length-2行
for(int i=1;i < height;i++){
int temp = 0 ;
//中间的部分
for(int j=1;j<tail;j++){
temp = M[i+1][j-1] + M[i+1][j] + M[i+1][j+1];
M[i][j] = (one[j] + two[j] + temp) / 9;
one[j] = two[j];
two[j] = temp;
}
//依然是计算每一行的第一个与最后一个
temp = M[i+1][0] + M[i+1][1];
M[i][0] = (one[0] + two[0] + temp) / 6;
one[0] = two[0];
two[0] = temp;
temp = M[i+1][tail-1] + M[i+1][tail];
M[i][tail] = (one[tail] + two[tail] + temp) / 6;
one[tail] = two[tail];
two[tail] = temp;
}
//计算最后一行进行收尾
M[height][0] = (one[0] + two[0]) / 4;
M[height][tail] = (one[tail] + two[tail]) / 4;
for(int i =1;i < tail;i++)
M[height][i] = (one[i] + two[i]) / 6;
return M;
}
public int[][] singletonRow(int[][] M){
int pre = M[0][0];
M[0][0] = (M[0][0] + M[0][1]) / 2;
for(int i = 1;i<M[0].length - 1;i++){
int temp = M[0][i];
M[0][i] = (pre + temp + M[0][i+1]) / 3;
pre = temp;
}
M[0][M[0].length - 1] = (pre + M[0][M[0].length - 1]) / 2;
return M;
}
public int[][] singletonColunm(int[][] M){
int pre = M[0][0];
M[0][0] = (M[0][0] + M[1][0]) / 2;
for(int i = 1;i<M.length - 1;i++){
int temp = M[i][0];
M[i][0] = (pre + temp + M[i+1][0]) / 3;
pre = temp;
}
M[M.length - 1][0] = (pre + M[M.length - 1][0]) / 2;
return M;
}
}
我不得不承认，所有情况都想到了，甚至很多一行一列的都单独列出来了。但是这个量真的有点吓人了。我还是喜欢四层循环。哈哈，这道题其实做起来不难，就是墨迹而且写着写着容易懵，反正我一把一把撸掉头发。下一题吧。
非递减数列
题目：给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。我们是这样定义一个非递减数列的： 对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。
示例 1:
输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:
输入: [4,2,1]
输出: False
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
说明: n 的范围为 [1, 10,000]。
思路：这个题看起来很高大上，还非递减数列，我仔细看了下，不就是要变成升序数组么？有点意思啊，是不是只要数组中有超过一个位置不对的就不能变成非递减数列了？我去试试。感觉应该没问题。
我惭愧啊，脸疼啊，我以为贼简单，实际上一点都不简单。只是想的简单了。
这个情况好多种，比如我上面的思路 3 4 1 2 3就过不去。实际上不合格的只有4-1.但是。。然后我就知道我思路错了，开始想新的思路。保存上一个第二大的值，再跳过比较？结果测试案例 1 3 3 2 4又测试不通过。
最后痛定思痛，好好琢磨思路，其实这个情况可以这么想，改变一个元素也可以理解为只有一个元素是异常的，除了这一个元素都遵从规律就说明是true。但是这个元素又不一定是哪个。当A>B的时候，我们不知道是A太大了还是B太小了。
所以两个都要考虑。如果A,B都抛出了还是不是顺序排序说明是false。
如下代码：
class Solution {
public boolean checkPossibility(int[] nums) {
int index = -1;
int value = 0;
int value1 = 0;
for(int i=0;i<nums.length-1;i++){
if(nums[i]>nums[i+1]){
index = i;
value = nums[i];
value1= nums[i+1];
break;
}
}
//遍历完都没改变。说明本来就是顺序的
if(index==-1) return true;
//A>B时，B赋值给A
nums[index] = value1;
if(isSort(nums)) return true;
//还不行就 A赋值给B（先还原A）
nums[index] = value;
nums[index+1] = value;
if(isSort(nums)) return true;
//都不行就是false
return false;
}
//判断一个数组是不是顺序的
public boolean isSort(int[] nums){
for(int i = 0;i<nums.length-1;i++){
if(nums[i]>nums[i+1]) return false;
}
return true;
}
}
其实这个性能超过百分百的，我注释写的比较墨迹，单纯代码很简单的。然后下一题吧。
修剪二叉搜索树
题目：给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
思路：这道题怎么说呢，我觉得就是一个判断节点挂节点的过程。前提是二叉搜索树，所以遵守左小右大。到了某节点可以只判断单边了。。
这种树的题其实大多数的特点就是代码简洁，逻辑比较绕，只要懂了几分钟做出来，不懂来回来去有问题!对，像我这样的人就是半懂不懂的那种。
继续说，其实只要判断当前节点要不要就行了。当前节点大于最大值，小于最小值就是不要的。不然就要遍历。
直接上代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if(root==null) return root;
if(root.val<L){
return trimBST(root.right,L,R);
}else if(root.val>R){
return trimBST(root.left,L,R);
}
root.left = trimBST(root.left,L,R);
root.right = trimBST(root.right,L,R);
return root;
}
}
这道题我是真的不知道要怎么说了，如果看不懂就是二叉树遍历，递归用的不熟。多练练吧。我记得我第一道题做二叉树也懵逼半天，看都看不懂，用eclipse调试模式一行代码一行代码看的。
二叉树中第二小的值
题目：给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
思路：这道题我看出窍门了！因为节点值不大于它的子节点值。所以肯定是越往下越大！根节点是最小值。只要存在比根节点大的值（可能一层出现多的）选择最小的就对了。我去代码实现了哈。
这道题是我想差了，虽然一个分支肯定是越往下越大（或者相等）但是两个分支啊，比如第一个示例左边的2下面如果再有3，就是3第二大了。
所以我放弃偷懒，直接全遍历了。
一直到结束，然后取不等于root的最小值。这里说下测试案例是真的棒，一猜肯定有int最大值果然中了。所以这个变量我用的long，这样能确定到底是第二大的值还是本身的值了。
直接贴代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int findSecondMinimumValue(TreeNode root) {
if(root==null) return -1;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
int val = root.val;
queue.add(root);
long max = 2147483648l;
while(!queue.isEmpty()){
int count = queue.size();
for(int i = 0;i<count;i++){
TreeNode n = queue.poll();
if(n.val>val){
max = Math.min(max,n.val);
}
if(n.left!=null) queue.add(n.left);
if(n.right!=null) queue.add(n.right);
}
}
return max!=2147483648l?(int)max:-1;
}
}
其实我真的觉得题做多了都差不多，这个队列遍历还是昨天取每一层的平均值中用到的。在这里只改了一点点逻辑剩下都差不多。
另外说一下，这个题用递归也很简单的，我现在还记得那句话:栈（队列）就是显式的递归!能用栈（队列）的一定也能用递归实现。反之亦然。
不过因为做过很多这种的了，所以我就不再用递归写了，其实就是一个遍历嘛！
今天的笔记就做到这里了，如果稍微帮到你了记得点个喜欢点个关注！！！然后也祝大家工作顺顺利利！
