今天周五，明天就放假了，开心心~~哈哈，刷题之前打个广告：java技术交流群：130031711，欢迎各位大佬萌新踊跃加入。然后开始刷题了。
区域和检索-数组可修改
题目：给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。
示例:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
说明:
数组仅可以在 update 函数下进行修改。
你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。
思路：首先这个题目是个开放题目，就是实现很简单，最无脑的方式也可以实现。其次这种题评论很不友好，优越感贼鸡儿高，所以我肯定是不打算看评论了。最后直接每次修改或者累加不太好。所以我还是得看看怎么优化一下。
算了，想不出怎么优化了，要么更加麻烦要么费大量空间，我觉得放弃了，简单粗暴的实现试试看吧。
class NumArray {
int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
}
public void update(int i, int val) {
nums[i] = val;
}
public int sumRange(int i, int j) {
int sum = 0;
for(int n = i;n<=j;n++){
sum += nums[n];
}
return sum;
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(i,val);
* int param_2 = obj.sumRange(i,j);
*/
性能不好是意料之中，解决办法我直接看性能排行第一的代码了，知识量不足，想不出什么好思路了。
看了题解，但是没看懂，，我可能是没救了。
直接附上两个性能排行考前的题解，然后我先过了：
class NumArray {
private int[] tree;
private int n;
public NumArray(int[] nums) {
n = nums.length;
tree = new int[ 2 * n];
for(int i = 0; i < n; i++) {
tree[i + n] = nums[i];
}
for(int i = n - 1; i > 0; i--) {
tree[i] = tree[ 2 * i] + tree[2 * i + 1];
}
}
public void update(int i, int val) {
i += n;
int add = val - tree[i];
while( i > 0) {
tree[i] += add;
i = i >> 1;
}
}
public int sumRange(int i, int j) {
int l = i + n;
int r = j + n;
int sum = 0;
while(l <= r) {
if(l % 2 == 1){
sum += tree[l];
l++;
}
if(r % 2 == 0) {
sum += tree[r];
r--;
}
l = l >> 1;
r = r >> 1;
}
return sum;
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(i,val);
* int param_2 = obj.sumRange(i,j);
*/
class NumArray {
private int[] nums;
private int[] c;
private int n;
public NumArray(int[] nums) {
this.nums = nums;
n = nums.length + 1;
c = new int[n];
for(int i = 0; i < nums.length; i++) {
updateAdd(i, nums[i]);
}
}
public void update(int i, int val) {
int add = val - nums[i];
nums[i] = val;
updateAdd(i, add);
}
private void updateAdd(int i, int val) {
i++;
while(i < n ) {
c[i] += val;
i += lowbit(i);
}
}
private int sum(int i) {
i++;
int res = 0;
while(i > 0) {
res += c[i];
i -= lowbit(i);
}
return res;
}
public int sumRange(int i, int j) {
return sum(j) - sum(i - 1);
}
private int lowbit(int x) {
return x & (-x);
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(i,val);
* int param_2 = obj.sumRange(i,j);
*/
最佳买卖股票时机包含冷冻期
题目：给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
思路：典型dp没说的，我记得最佳买卖股票本身就是一个典型动态规划的题目，好像还是我dp入门题目。这个只不过加个冷冻期但是大体的逻辑的不变的。我直接去写代码了。特么越写越不对，今天状态不好，还是来分析分析题目吧。首先第一点买入：一定是当前值小于下一个值的情况下才可能买。不然怎么也不对。所以买入的时机是可以按条件判断的。最后说卖出，也一定是当前值大于前一个值（小不小于后面的不一定）。所以以这两个点选择买入卖出。然后再用一个合适的dp算出最大值。好的呢，就这样了。我再去试试。
好了，代码出来了（上周五开始做，中间经历了吵架，辞职等好多事，这周一才开始写完代码，也是比较波折的一道题了。）
class Solution {
public int maxProfit(int[] prices) {
if(prices.length<2) return 0;
int[][] dp = new int[prices.length][2];
//第一个数赚钱数是不买不卖，0元收益
//第二个数是当前值买入
dp[0][0] = 0;
dp[0][1] = -prices[0];
//第二天钱如果大于第一天钱数则赚钱是1买2卖，否则就要不买不卖
dp[1][0] = prices[0]<prices[1]?prices[1]-prices[0]:0;
//昨天买入和今天买入哪个更合适选择哪个。（因为买入是花钱，所以是负数）
dp[1][1] = prices[0]<prices[1]?-prices[0]:-prices[1];
for(int i =2;i<prices.length;i++){
//主要是判断现在卖出是不是比昨天挣得多，是则今天卖出，不是则昨天收益是最多的
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
//因为中间有冷冻期，所以要i-2。前天最大盈利-今天买入 和 昨天最适合持有的股，哪个钱多选择哪个。
dp[i][1] = Math.max(dp[i-1][1],dp[i-2][0]-prices[i]);
}
return dp[prices.length-1][0];
}
}
其实我觉得这个题已经脱离了简单dp的范围，因为真正做的时候发现还是比较复杂的，因为分为三种情况：一种是买，一种是卖，还有一种是冷冻期，所以一个简单数组记录中间过程是实现不了了。中间我甚至都有过脱离dp，用笨办法实现了，其实这个买入和卖出是有规律的，比如当前值小于后一个值才会买入，不然是没必要买的，可以下一个再买。但是当前值小于后一个值卖不卖是要看冻结期统一规划的，所以我这里将整个思路划分成了两部分：
1. 当前天的最大收益。
2. 当前天最合适的买入股。
如上面代码：
- 第一天没啥疑问，不可能赚钱，所以dp[0][0]是0.dp[0][1]是-prices[0]，也就是没有课比较的，所以当天最合适的买入股就是今天的股。
- 第二天则开始判断：如果第二天钱数大于第一天的，那么就第一天买第二天卖，赚的钱就是差值。 而第二天手里应该有的股不考虑盈利的情况下，肯定是买便宜的那个（最开始会是负值，但是 -小值 是大的那个）。比如 1,0,3。这个的合理做法就是第一天不买不卖，第二天买， 第三天卖，这样才是最大值3.
所以如果是这个例子，第二天手里持股应该是0（买便宜的那个）。
因为是典型dp，前两天的情况列出来了，后面的是重叠子问题了，所以用循环填充数据：
每一个循环都是一个套路：
- 判断今天的最大利润是：昨天的最大利润 和 今天股票脱手赚的钱的哪个多，哪个多今天的最大利润就是哪个。
- 判断今天手中股应该是哪个: 昨天的手中最合适的股 和 前天的盈利（因为中间冷冻期1天，所以前天操作完昨天是冷冻期，今天才能买入，虽说前天的盈利不一定是卖了股，但是保险起见肯定是要做预留）+今天买入的钱哪个多，哪个多选择哪个。
大概逻辑是这样，但是我写出来之前是一直调试的，真的这样的二维dp我也第一次做。然后一点点改动，但是真的写出来了回看，思路才真正清晰起来了。
差不多可以看成把当天最大盈利和 手中持股分开判断情况。 而手中持股卖出是有一天冷冻期，所以要昨天的股 比较 前天的钱数-今天买入的钱数。
然后dp问题其实调试也是一个好的解决办法，但是要慢慢的一步一步走，毕竟本来代码就少，而且可能数据多的时候不一定哪一步出问题，反正我觉得调试真的是个考验耐心的活。
这道题就这样了，我上面代码的性能也不错，超过百分之九十九了，直接下一题了。
最小高度树
题目：对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。格式：该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。
示例 1:
输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
输出: [1]
示例 2:
输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
输出: [3, 4]
说明:
根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
树的高度是指根节点和叶子节点之间最长向下路径上边的数量。
思路：emmmm....亲自做了demo才明白了题目的意思。比如第一个图最小高度从1开始的话都是1，所以答案是1.第二个demo中，从3开始最小高度是2,（3-4-5），从4开始最小高度也是2（4-3-0,4-3-2,4-3-1）。所以答案是3，4。现在为止是题目明白了，具体怎么实现我觉得其实方式应该也不少，但是我能想到的也就是什么链表啊，map啊什么的。主要思路是从每一个点出发记录最长的高度。然后选出其中高度最小的们，加入到结果集返回。我去写代码试试。
在不断看题的基础上又有一些心得。首先，只出现一次的元素说明是一个边界元素，除了只有两个元素外，剩下只出现一次的元素是不可能成为最小高度的根节点的（我是观察并分析得出的结论，还没正式确定）。其次我现在用最笨的map方法存了每一个节点和其相连节点，但是现在又觉得不是那么有必要。因为上面第二个例子中，0,1,2到3的距离是一样的1，所以我觉得是不不是可以只取一个参与计算就行？另外因为不存在环，所以这个节点数最少一个，最多两个对吧？不可能出现三个最小高度是一样的。都是随着写随着出现的零散的思路，我再去好好整理一下用代码实现。
思路理好了，我觉得现在的问题是怎么把出现过一次的叶子节点抛出去。勉强做好了，性能可怜，而且我超时了好几次，真的是，心态都崩了：
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> result = new ArrayList<>();
if(n<1) {
return result;
}else if(n==1){
result.add(0);
return result;
}else if(n==2){
result.add(0);
result.add(1);
return result;
}
int[] edge = new int[n];
//构建每个结点的邻接表
HashMap<Integer,List<Integer>> adj = new HashMap<>();
for(int[] link : edges) {
edge[link[0]]++;
edge[link[1]]++;
if(!adj.containsKey(link[0])) {
adj.put(link[0],new ArrayList<>());
}
if(!adj.containsKey(link[1])) {
adj.put(link[1],new ArrayList<>());
}
List<Integer> temp = adj.get(link[0]);
temp.add(link[1]);
adj.put(link[0],temp);
temp = adj.get(link[1]);
temp.add(link[0]);
adj.put(link[1],temp);
}
//将每个边的数量为1的结点加入队列(叶子节点，不可能是根节点)
Queue<Integer> queue = new LinkedList<>();
for(int i=0;i<n;i++){
if(edge[i]==1) {
queue.add(i);
}
}
int count = 0;
while(!queue.isEmpty()) {
int size = queue.size();
//终止条件！当已入队的节点数量和剩余的队列中的节点数量和为n的时候，就是找到了root
if(count+size==n) {
for(int i=0;i<size;i++){
result.add(queue.poll());
}
return result;
}
count+=size;
//正常执行
for(int i=0;i<size;i++){
int head = queue.poll();
//将队中节点对应的邻接结点的边数量减一
for(int item:adj.get(head)) {
edge[item]-=1;
//发现边数量为1的节点将其入队
if(edge[item]==1) {
queue.add(item);
}
}
}
}
return result;
}
}
这个题的思路很简单，但是实现起来很麻烦。我上面的思路是对的，叶子节点不可能是根节点，所以不断排除叶子节点就行了。而问题也是在第一轮排除后怎么排除第二层叶子节点，我之前试过重新用二维数组表示，但是超时了。也试过叶子节点改值-1.还是超时了。最后还是用了map。我甚至都不报希望了，还好的就是没超时。不过也给自己写恶心了。
当然性能也不咋地。我去看看题解吧，是不是有什么更优雅的实现方式。
好了，回来了，确实是看到一个不错的算法：获取两个最长路径的节点，然后取中间节点（1,2个）作为根节点。
乍一看有点不理解，但是仔细想了就觉得这个思路挺好。因为两个路径最长的节点的中间节点使得节点到每个边的距离最小。没啥问题。然后实现代码我直接去cv吧。今天写的心态有点炸：
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> res = new ArrayList<>();
int[][] gra = new int[n][];
for(int[] edge : edges) {
int a = edge[0], b = edge[1];
if(gra[a] == null) gra[a] = edge;
else gra[b] = edge;
}
int root = getRoot(gra);
int[] node = getNode(gra, root);
root = reverse(gra, root, node[0]);
node = getNode(gra, root);
//System.out.println(root + "/" + node[0] + ":" + node[1]);
int len = node[1] / 2;
int p = node[0];
while(len-- != 0) p = getNext(gra, p);
res.add(p);
if((node[1] & 1) == 1) res.add(getNext(gra, p));
return res;
}
private int reverse(int[][] gra, int root, int p) {
int ret = p;
int[] pre = null;
while(p != root) {
int next = getNext(gra, p);
int[] temp = gra[p];
gra[p] = pre;
pre = temp;
p = next;
}
gra[root] = pre;
return ret;
}
private int[] getNode(int[][] gra, int root) {
int n = gra.length;
int max = 0, node = 0;
int[] h = new int[n];
int[] stack = new int[n];
int size = 0;
for(int i = 0; i < n; i++) {
int p = i, count = 0;
while(p != root && h[p] == 0) {
stack[size++] = p;
p = getNext(gra, p);
}
while(size != 0) {
int temp = stack[--size];
h[temp] = h[p] + 1;
if(h[temp] > max) {
max = h[temp];
node = temp;
}
p = temp;
}
}
return new int[]{node, h[node]};
}
private int getRoot(int[][] gra) {
int p = 0;
while(gra[p] != null) p = getNext(gra, p);
return p;
}
private int getNext(int[][] gra, int p) {
int[] ret = gra[p];
return ret[0] == p ? ret[1] : ret[0];
}
}
只有更麻烦，没有最麻烦。emmmm....怎么说呢，看第一的代码也写了这么多心里平衡多了。我又找了找，看到一种入度的方式更优雅的写法， 用的二维数组来处理的，我觉得还挺容易理解的，我再贴上来：
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> res = new ArrayList<>();
if (n < 2) {
if (n == 1) {
res.add(0);
}
return res;
}
int[] degrees = new int[n];
int[][] nodes = new int[n][];
int[] neighborsLen = new int[n];
for (int[] edge : edges) {
degrees[edge[0]]++;
degrees[edge[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
int count = n;
for (int i = 0; i < n; i++) {
nodes[i] = new int[degrees[i]];
if (degrees[i] == 1) {
queue.offer(i);
count--;
}
}
for (int[] edge : edges) {
nodes[edge[0]][neighborsLen[edge[0]]++] = edge[1];
nodes[edge[1]][neighborsLen[edge[1]]++] = edge[0];
}
while (count > 0) {
int len = queue.size();
for (int i = 0; i < len; i++) {
int v = queue.poll();
for (int neighbor : nodes[v]) {
if (--degrees[neighbor] == 1) {
queue.offer(neighbor);
count--;
}
}
}
}
return (List<Integer>)queue;
/*while (!queue.isEmpty()) {
res.add(queue.poll());
}
return res;*/
}
}
然后这道题就这样吧，说实话我觉得这种题处理的麻烦性比思路还不好想。我记得这个叫做拓扑排序，可能是我用的还不习惯。所以真的，list，map，数组之类的写的死去活来的，哈哈
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活健健康康！顺便打个广告。java技术交流群：130031711，欢迎各位大佬萌新踊跃加入。
