输出二叉树
题目：在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：
行数 m 应当等于给定二叉树的高度。
列数 n 应当总是奇数。
根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。
每个未使用的空间应包含一个空的字符串""。
使用相同的规则输出子树。
思路：这个题怎么说呢，首先层数和list的元素数的关系：1-1 。2-3。3-7。4-15.就是上一个翻倍+1.翻倍就是左右，加1是中间。到这里思路还是很清楚的。然后先把二维数组列出来，往里一层一层填充元素得了。估计这个填充还要dfs。我去试试代码。
这个题特别有意思。我写个n个方法，以为低空略过，结果一次ac性能超过百分百。先贴代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int d = 0;
public List<List<String>> printTree(TreeNode root) {
List<List<String>> res = new ArrayList<List<String>>();
dfs(0, root);
int len = 1;
for(int i = 1;i<d;i++) len = len*2 + 1;
for(int i = 0;i<d;i++){
List<String> list = new ArrayList<String>();
for(int j = 0;j<len;j++) list.add("");
res.add(list);
}
dfs(res, root, 0, len-1, 0);
return res;
}
public void dfs(List<List<String>> res,TreeNode root,int start,int end,int len) {
if(root != null) {
int mid = (start+end)>>1;//因为下标从0开始。所以这里的结果正好是中间那个
res.get(len).set(mid, String.valueOf(root.val));
dfs(res, root.left, start, mid-1, len+1);
dfs(res, root.right, mid+1, end, len+1);
}
}
public void dfs(int temp,TreeNode root){
if(root.left == null && root.right == null) d = Math.max(d, temp+1);
if(root.left != null) dfs(temp+1, root.left);
if(root.right != null) dfs(temp+1,root.right);
}
}
大概的思路和预计的差不多，先获取这个二维数组的长宽。把空串填进去。然后再根据树一个一个元素替换，这里用了两次递归：一次是找树的高度。一次是填充元素。这么多代码我都快以为是我想错了，没成想这个题目就是这样的。刚刚看了下性能第一的代码和我这个思路差不多，所以这个题就这样了，下一题。
找到k个最接近的元素
题目：给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。整数 a 比整数 b 更接近 x 需要满足：|a - x| < |b - x| 或者|a - x| == |b - x| 且 a < b
示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]
示例 2：
输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]
提示：
1 <= k <= arr.length
1 <= arr.length <= 104
数组里的每个元素与 x 的绝对值不超过 104
思路：这个题怎么说呢，我个人感觉是分两部分：1.找出这些数。2.这些数字升序排列。至于怎么找出这些数应该是从给定数字往两头外扩吧。比如demo中从3开始两边扩充（3本身要入结果集）：2.4值一样，但是2小，所以2入结果集。再往下1,4中4绝对值小，所以4入结果集。再往下1,5绝对值一样但是1小，1入结果集。这个时候结果集满了，所以返回。。。思路很清楚，我去写代码了。
第一版本代码出来了，虽然ac的但是性能有点问题，我先贴出来：
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int len = arr.length-1;
int idx = -1;
if(arr[0]>=x) {//最小的数都大于x
idx = 0;
}else if(arr[len]<=x) {//最大的小于x。
idx = len;
}else {
for(int i = 0;i<len;i++) {
if(arr[i] == x) {
idx = i;
break;
}else if(arr[i]<x && arr[i+1]>x) {//x没落在正好的位置
idx = arr[i+1]-x<x-arr[i]?i+1:i;//返回距离比较近的那个.相等返回小的
break;
}
}
}
List<Integer> res = new ArrayList<Integer>();
res.add(arr[idx]);//最接近的元素直接放进去
//从idx开始双指针往外找。
int left = idx;
int right = idx;
//结果集没满就继续填充
while(res.size()<k) {
if(right==len) {//不能往后指了，只能往前走
res.add(arr[--left]);
}else if(left == 0){
res.add(arr[++right]);
}else {
//后面的绝对值小选择后面的，否则选择前面的
if((arr[right+1]-x)<(x-arr[left-1])) {
res.add(arr[++right]);
}else {
res.add(arr[--left]);
}
}
}
Collections.sort(res);
return res;
}
}
这个题怎么说呢，暂时优化思路都莫得，我感觉写的挺好的啊，我直接去看看性能第一的代码吧：
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int left = 0, right = k - 1;
while (right + 1 < arr.length && (arr[right + 1] <= x
|| arr[right + 1] - x < x - arr[left])) {
left++;
right++;
}
List<Integer> result = new ArrayList<>();
for (int i = left; i <= right; i++) {
result.add(arr[i]);
}
return result;
}
}
为什么都想到双指针了却没想到滑窗啊！！！为什么可以这么菜！！心态崩了啊，反正这个性能第一的代码就是一个滑窗。因为是递增序列。所以符合条件的结果集一定是一串挨着的元素。重点是判断出从哪里开始的连续数组中元素而已。
一看这个思路我就会了，但是自己就是琢磨不出来，哭了啊~最近刷题刷的心态爆炸，感觉刷了这么久还是没什么进步。做题靠直觉，思路纯暴力。哎，下一题下一题。
买卖股票的最佳时机含手续费
题目：给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1:
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.
思路：这个题我不记得我做没做过了，是今天的每日一题。买卖股票这块作为dp的经典题目，我记得我当年统一刷过啊。话不多说，说解题思路。首先这个手续费只收一笔，所以我们可以设置为在买入的时候比实际价格贵fee元。其次有一个概念：峰值一定是卖出或者留手，不可能最贵的时候买入。当然同理肯定是在谷值买入，不然不会买贵的不买便宜的。所以说这个题可以先把prices简化成峰值谷值峰值谷值。然后上一次卖不卖和这一次买不买是dp关系。差不多思路就这样，我再去结合题目试着写代码吧。
怎么说呢，ac倒是ac了，但是性能不咋地，而且最后也不是dp实现的。先贴代码：
class Solution {
public int maxProfit(int[] prices, int fee) {
int res = 0;
if(prices.length <2) return 0;//不管是没有元素还是只有一个元素都不买，0收益
//手续费可以算成是买入的时候+fee元。
//有一个概念：峰值一定是卖出或者留手，不可能最贵的时候买入
//不可能非谷值买入。干嘛不买便宜的买贵的？
//所以说这个题可以先把prices简化成峰值谷值峰值谷值。。
//因为买入加手续费，所以谷值直接+fee.第一个肯定是谷值
//所以说只要低价买入能赚就卖出就买
//因为买入要手续费，所以这个手续费直接算到买入价格
int buy = prices[0]+fee;
for(int i = 1;i<prices.length;i++) {
if(buy>prices[i]+fee) {//挑便宜的买，所以要替换买入价格
buy = prices[i] + fee;
}else if (prices[i]>buy){//现在买入的比价格卖了就是赚的，所以卖
res += prices[i]-buy;//赚的钱增加了
//因为这个prices[i]是卖出价格。有比这个价格高的直接这个不买下一个卖
//所以这个不用+fee。当然如果再遇到比这个便宜的会重新买入。
buy = prices[i];
}
}
return res;
}
}
这种题目的一个特点：思路理顺了做起来会简单的多。我觉得只要给我时间dp也不是不能实现，不过在写的过程中灵机一动发现这个其实不非要用dp。就是峰值谷值看了半天看出了规律：倒手挣钱就倒手。dp规律就是峰值谷值/下一次谷峰差值加上当前的大就档次转手再买再卖。否则一直留股到下次一起卖。我再去试试dp实现：
class Solution {
public int maxProfit(int[] prices, int fee) {
int res = 0;
if(prices.length <2) return 0;//不管是没有元素还是只有一个元素都不买，0收益
int buy = -prices[0];//记录前一天的状态，手里持股
int sell = 0;//前一天的状态，手里不持股
for(int i = 1;i<prices.length;i++) {
//这一天的状态是手里持股，那么就在前一天的基础上买股，要么就是不买股
buy = Math.max(buy, sell-prices[i]);
//这一天的状态是手里不持股的话，前一天没股和前一天持股但是卖掉哪个合适
sell = Math.max(sell, buy+prices[i]-fee);
}
//最终一定是不持股的状态
return sell;
}
}
真的有时候一开始思路有问题很难中途转过来。dp本身和峰值谷值莫得关系。只要判断当前的最优解就行了。每一天分两种状态：当前手里有股票，当前手里没股票。
我们只需要选择每一天都是最优解就行了。 手里不持股买当天的和手里持以前的股，哪个赚的更多选择哪个。同理当天卖股票还是前一天卖股票哪个更赚钱就选择哪个。
我刚刚看了下题解，这个可以用二维dp数组来实现。不过因为这个题只和上一天的状态有关，所以不用数组，用变量保存上一天的状态就行了。
反正完整版的代码如下，这个题也就这样了，下一题。
二叉树最大宽度
题目：给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
思路：这个题怎么说呢，审题几遍才看懂。我目前的想法就是遍历。所有不是首个节点的非空节点用null填充。最终统计每一次的有效元素数（首尾不是null的）。我大概会用0,1来表示吧，有个简单的思路，我去实现下。
第一个版本的代码超时了，虽然我自认为逻辑没错：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int widthOfBinaryTree(TreeNode root) {
int res = 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
int start = -1;
int end = -1;
int size = queue.size();
for(int i = 0;i<size;i++) {
TreeNode temp = queue.poll();
if(temp!=null && start == -1) start = i;//第一个有值的元素要记录
if(temp!=null) end = i;//最后一个有值的元素记录
//当前元素非空添加两个子节点
if(temp != null) {
queue.add(temp.left);
queue.add(temp.right);
}else if(start != -1){//有了非空元素才需要占位
queue.add(null);
queue.add(null);
}
}
res = Math.max(res, end-start+1);
//这一层都没有元素的了，说明树遍历完了
if(start == -1) return res;
}
return res;
}
}
当然也可能是做了很多无用功。而且我看了测试案例，觉得可能这种每一个元素都列出来是有问题的，我去想想优化思路。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int widthOfBinaryTree(TreeNode root) {
int res = 0;
LinkedList<TreeNode> queue = new LinkedList<>();
LinkedList<Integer> indexQueue = new LinkedList<>();
queue.add(root);
indexQueue.add(1);
while (!queue.isEmpty()) {
int left = indexQueue.peek();
int len = queue.size();
for (int i = 0; i < len; i++) {
TreeNode poll = queue.poll();
Integer index = indexQueue.poll();
res = Math.max(res, index - left + 1);
if (poll.left != null) {
queue.add(poll.left);
indexQueue.add(index * 2);
}
if (poll.right != null) {
queue.add(poll.right);
indexQueue.add(index * 2 + 1);
}
}
}
return res;
}
}
这个题我自己优化了三个版本才发现，我没必要一直想着剪枝（中间有一个版本end后面的删除）。重点是这个null就没必要占位。因为其实根据父节点一层一层就能推导出当前节点按照满树来讲所在的位置、同样能能推算出结束节点所在位置。这样不用null占位也知道中间隔了多少个值。于是最终版代码出现了，所有入队列的元素都是非空的，省去了很多性能。同样根据下标的位置判断最大差值。反正这个题的思路就这样了，我去看看题解吧。
看了性能排行第一的代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if(root == null) {
return 0;
}
Deque<TreeNode> queue = new LinkedList<>();
// 根节点编号为 0
root.val = 0;
queue.add(root);
int sum;
int ans = 0;
while(!queue.isEmpty()) {
sum = queue.size();
// 队头和队尾的编号值求差用来更新宽度
ans = Math.max(ans, queue.getLast().val - queue.getFirst().val + 1);
// 一次处理一层，进入这个循环前队列中是一层的所有非空节点
while(sum > 0) {
TreeNode temp = queue.remove();
// 子节点入队前修改 val, val = 满二叉树中节点编号
if(temp.left != null) {
queue.add(temp.left);
temp.left.val = temp.val * 2 + 1;
}
if(temp.right != null) {
queue.add(temp.right);
temp.right.val = temp.val * 2 + 2;
}
sum--;
}
}
return ans;
}
}
先说一下这个题用的双端队列。我之前有想到这个数据结构。但是没用。以为影响不会很大。其次两点就是用树节点的值表示当前所在位置。这个挺新颖的一个思路。相比于上面两个队列对应的代码这个可能更好计算一点吧。有时候不得不感慨大家长的是一个脑子么。。。这种代码属于看了能理解，自己想不出来的东西。这个题主要就是二叉树位置的计算-树的左节点位置是父节点位置2.右节点为止是父节点位置2+1。
只要知道这两个公式这个题做还是能做出来的，下一题了。
优美的排序2
题目：给定两个整数 n 和 k，你需要实现一个数组，这个数组包含从 1 到 n 的 n 个不同整数，同时满足以下条件：
- ① 如果这个数组是 [a1, a2, a3, ... , an] ，那么数组 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数；.
- ② 如果存在多种答案，你只需实现并返回其中任意一种.
示例 1:
输入: n = 3, k = 1
输出: [1, 2, 3]
解释: [1, 2, 3] 包含 3 个范围在 1-3 的不同整数， 并且 [1, 1] 中有且仅有 1 个不同整数 : 1
示例 2:
输入: n = 3, k = 2
输出: [1, 3, 2]
解释: [1, 3, 2] 包含 3 个范围在 1-3 的不同整数， 并且 [2, 1] 中有且仅有 2 个不同整数: 1 和 2
提示:
n 和 k 满足条件 1 <= k < n <= 104.
思路：简单说一下思路，感觉这个题应该比上一道简单的多。首先k=1就是顺序或者倒叙排列就不说了。如果k = n-1那么稳妥的首尾想插入。重点就是中间阶段的k怎么实现：因为确定是n个连续整数。所以想保证每一块的差值一样还是能做到的。可不可以这么做：前面插入，到k-1中值的时候顺序开始排列。保持差额是1。感觉可行性还挺高的，我去实现下试试。
一次ac，性能也不错，挺好的。思路就是我上面说的思路，两边插入，到达到的值就顺序往下递增或递减就ok了。
class Solution {
public int[] constructArray(int n, int k) {
int[] res = new int[n];
int idx = 0;
int start = 1;
int end = n;
boolean flag = true;//下一个要插入元素。true代表start.false代表end
while(k-->0) {
if(flag) {
res[idx++] = start++;
}else {
res[idx++] = end--;
}
flag = !flag;
}
if(!flag) {//顺序往下
while(start<=end) res[idx++] = start++;
}else {//倒叙往上
while(start<=end) res[idx++] = end--;
}
return res;
}
}
感觉我这个思路没啥问题，而且我看了人家给定的答案，我怀疑也是这种做法，只不过人家从多少种不同开始遍历，最后顺序往后顺延就行了。我去看看性能第一的代码，不出意外就这么过了:
class Solution {
public int[] constructArray(int n, int k) {
int[] res=new int[n];
int numk=k+1,numt=1;
//下标段[0,k]中，偶数填充[1、2、3...]
for(int i=0;i<=k;i+=2){
res[i]=numt++;
}
//下标段[0,k]中，奇数下标填充[k+1,k,k-1...]
for(int i=1;i<=k;i+=2){
res[i]=numk--;
}
//其余的部分顺序填充
for(int i=k+1;i<n;i++){
res[i]=i+1;
}
return res;
}
}
精巧的代码，我是用flag来填充大数小数。人家是奇偶数。这个题就这样了。下一题。
最大交换
题目：给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736
输出: 7236
解释: 交换数字2和数字7。
示例 2 :
输入: 9973
输出: 9973
解释: 不需要交换。
注意:
给定数字的范围是 [0, 108]
思路：这个题就简单了，首先不存在超时问题，其次非负整数不存在正负不同分两种情况的问题，最后大概思路就是第一位不是最大换成最大的，第一位是最大往下判断。如果这个数字已经是降序排列了那么就原样输出、差不多就这个思路。我先去实现下看看。
直接贴代码：
class Solution {
public int maximumSwap(int num) {
char[] arr = String.valueOf(num).toCharArray();
for(int i = 0;i<arr.length;i++ ) {
int idx = i;
char value = arr[i];
for(int j = i+1;j<arr.length;j++) {
if(arr[j]>=value && arr[i] != arr[j]) {
value = arr[j];
idx = j;
}
}
if(idx != i) {
char temp = arr[i];
arr[i] = value;
arr[idx] = temp;
return Integer.valueOf(new String(arr));
}
}
return num;
}
}
感觉这个题的难度可能就是细节处理比较繁琐？反正中间有个细节我坑了两次：首先如果非当前元素，有大于当前元素的多个相同元素，那么用较后的那个替换。所以这里判断条件是大于等于。但是如果和当前元素一样是没必要替换的，所以还要加arr[i]!=arr[j]。就这一点我一开始没想到所以提交了两次都是错误。不过只要注意到还是很容易改的。整体而言这个题不难。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利~！今日共勉语句：天道酬勤。
