今天又是阳光明媚的一天，而且不冷，心情大好~哈哈，打广告：java技术交流群：130031711，欢迎各位萌新大佬踊跃加入。然后开始刷题。
递增的三元子序列
题目：给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。数学表达式如下:如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，
使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。
示例 1:
输入: [1,2,3,4,5]
输出: true
示例 2:
输入: [5,4,3,2,1]
输出: false
思路：这个题我觉得是不是就看无序数组中有没有三个递增数组？我觉得还挺简单的啊，目前打算是一次遍历，设置一个计数器count。有一个递增count+1。count=2的时候返回true。如果遇到非递增count回归0。其实count初始值是1的话那就计数到3返回true。反正是一次遍历，常数空间额外复杂度。我不知道 我想的对不对，反正按照这个想法题目是简单的，我去代码实现下试试。
果然这么简单就不对，这个题目三个数不非要连着。。。哎，不过也不难，我打算用三个常量来表示第一个第二个第三个。第一个最小，第三个最大。如果第三个不是初值证明赋值了的，所以是true，不然是false。反正就是根据贪心算法得到的思路。如果后面值比前面的小的就替换这个小值。比这个大就往后续，续到第三个就说明实现了。我去写下代码。
好了，实现了，也不难，思路没问题，我直接贴代码：
class Solution {
public boolean increasingTriplet(int[] nums) {
int f = Integer.MAX_VALUE;//最小的
int s = Integer.MAX_VALUE;//第二的
for(int i = 0;i<nums.length;i++){
if(nums[i]<=f){//这个数比第一个数小，可以放到第一个数的位置。
f = nums[i];
}else if(nums[i]<=s){
s = nums[i];//这个数比第二个小，放到第二个的位置。
}else {//只要这个数大于第一，二个数，说明是第三个递增，所以直接true
return true;
}
}
return false;
}
}
然后因为其实到了第三个元素就已经true了。所以用了f,s常量存前两个就行。这个题没啥难度，所以就这么过了。
打家劫舍3
题目：在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
思路：攻克玩打家劫舍，买卖股票，我觉得我就像刷个题get了好多新技能啊。哈哈。咱们先说这个题，dp应该是没跑的。但是到底怎么动规呢？一开始我是想把根节点和两个枝节点比较的，后来发现其实不是，比如第二个例子，如果4下面的1，3换成一个更大的值，那么所偷的金额就可以是4下面的两个叶子节点+5了。所以说其实这个题我感觉复杂就复杂在有一定的元素是共同考虑元素，有一定的元素是自己的元素。怎么平衡好这个关系呢?如果只有两层树，那么选择就是很单纯的根节点还是叶子节点。但是如果有了3层。就应该把树左右分成两个部分，根节点和左右两子树的根节点作比较，如果根节点大，那么根作为第一个dp的结果，而第二层的一定不选，第三层的顺序往下。但是如果根节点较小，我现在觉得不好做的就是左边选根节点最大，右边不选根节点最大是怎么来计算得失的。。哎，说了这么多我还是去画图理解吧。
又有个想法了，一直盯着树盯出来个思路。。如果我从树的最底层开始往上判断呢？算出左子树的和和右子树的最大和，然后分别算出左树右树第三层的最大和+根节点。哪个大选择哪个。这样起码逻辑上是通 的，可以实现的。然后因为是二叉树，我觉得这个题可能是一个递归的dp。其实这种类型的动规我也是第一次做，有思路总比没有思路好，我去试着实现了。
!!!我两次ac了，而且性能超过百分之百的人，，，有点小激动啊，果然dp大体思路都一样，就是重复的子问题。找到其中一个就算是找到了全部，我直接贴代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rob(TreeNode root) {
int[] res = dfs(root);
return res[0];
}
//结果中，0是算上根节点的最大值。 1是左右子节点和的最大值
public int[] dfs(TreeNode root){
if(root == null) return new int[]{0,0};
if(root!=null && (root.left!=null || root.right!=null)){
int[] maxleft = dfs(root.left);
int[] maxright = dfs(root.right);
int f = maxleft[1]+maxright[1]+root.val;
int s = maxleft[0]+maxright[0];
//第一个是第三层值+当前节点值。 第二个是不算当前节点的最大值
return new int[]{f>s?f:s,s};
}else{//遍历到叶子节点了，所以子节点和是0，算上根节点是根节点值
return new int[]{root.val,0};
}
}
}
额，我觉得我注释写的不错了，所以。。。代码其实还是很简单的，也没啥可讲的，开心~~哈哈，我直接继续下一题了。
比特位计数
题目：给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]
进阶:
给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
要求算法的空间复杂度为O(n)。
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。
思路：怎么说呢，我单独说这个题还是很简单的，而且我觉得吧，其实都不一定非要用一个个化成2进制来计数。。。因为这个是有规律的。至于规律我暂时还没看，所以不确定，有的想法就是2位移一位就是4，再位移是8，依次乘2，3唯一一次是6。（11->110）。至于更具体的我去打印所有数的二进制1的个数去找找规律。
规律如图
看上面的正确结果：首先0是0 ，然后1是1，2是1.4是1，8是1，16是1，所以只要是2的翻倍都是1.其次3是2，6是2，12也是2.所以偶数的规律还是很好找到的。但是奇数的话。。我还没看出来，先找找看。奇数应该是他前面的那个偶数+1.（因为偶数最后一位是0，奇数最后一位是1，只会改变最后一位。）我去试试怎么写代码。
class Solution {
public int[] countBits(int num) {
int[] res = new int[num+1];
res[0] = 0;
for(int i = 1;i<=num;i++){
if((i&1)==0){
res[i] = res[i/2];
}else{
res[i] = res[(i-1)/2]+1;
}
}
return res;
}
}
说真的，我自我感觉思路还有写法都挺简单的，但是性能没预期的好。。我直接去看看性能排行第一的代码吧，感觉不是思路的问题，就是写法问题了。我甚至觉得是不是我这除法的问题？换成位移能不能好一点？要不我先去试试。
事实证明换成位移也还没好
我还是去看大佬代码吧：
class Solution {
int res[];
int max;
public int[] countBits(int num) {
res=new int[num+1];
max=num;
res[0]=0;
if (num==0)
return res;
res[1]=1;
plus(res[1],1);
return res;
}
void plus(int num,int sum){
num<<=1;
if (num<=max) {
res[num] = sum;
plus(num, sum);
}
num++;
if (num<=max){
res[num]=sum+1;
plus(num, sum+1);
}
}
}
？？？？惊呆我了，这是什么神仙处理办法？递归，一共只分两种情况：奇数偶数。这个数真的按照一个讨论走下去了啊。仔细看看代码都认识，也能理解。。但是我真的没想过要这么写。。递归比循环性能好咋的？啧啧，反正这个题就这样了。
今天还是不错的，三道题都比较简单。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利，生活健健康康！顺便打广告：java技术交流群，群号130031711，欢迎各位萌新大佬踊跃加入！
网友评论