最长连续递增数列
题目：给定一个未经排序的整数数组，找到最长且连续的的递增序列。
示例 1:
输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。
示例 2:
输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。
注意：数组长度不会超过10000。
思路：这个题我真的觉得做过类似的，现有的思路：count=1，然后遍历数组，如果后一个比前一个大count++，当后一个比前一个小的时候cuount恢复到1、设置一个最大值max，max取count最大值。对了，还要判断数组是不是为空。是的话返回1。大早晨的思路如此清晰，哈哈，开门大吉么？我去写代码了。
思路完全没问题，性能超过百分百，直接贴代码下一题吧：
class Solution {
public int findLengthOfLCIS(int[] nums) {
if(nums.length==0) return 0;
int max = 1;
int count = 1;
for(int i=0;i<nums.length-1;i++){
if(nums[i]<nums[i+1]){
count++;
}else{
max = max>count?max:count;
count=1;
}
}
return max>count?max:count;
}
}
验证回文字符串2
题目：给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: "aba"
输出: True
示例 2:
输入: "abca"
输出: True
解释: 你可以删除c字符。
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
思路：这道题就是普通点的验证回文串的进化版，首先一个字符串本身就是回文串了，肯定是true的。其次在比较的时候如果抛去一个字符串可以做到回文还是true，不然是false。这个题昨天做过一个类似的，改变某元素能否成为升序数组的那个题就是这个思路。不过那道题比这个复杂， 那个题是改变其中一个元素，而这道题简单多了，就是删除而已。我先去试着写代码，现在有一个模糊的思路。
做是做出来了，鬼知道我经历了什么？越改性能越差？
image.png
最好性能超过百分之八十多，越改越低，所以直接上最麻烦版本的代码吧:
class Solution {
public boolean validPalindrome(String s) {
int l = 0;
int r = s.length()-1;
char[] c = s.toCharArray();
boolean flag = true;
boolean flag1 = true;
int count = 0;
while(l<r){
if(c[l]!=c[r]){
count++;
l++;
if(count==2) flag=false;
}else{
l++;
r--;
}
}
l = 0;
r = c.length-1;
count = 0;
while(l<r){
if(c[l]!=c[r]){
count++;
r--;
if(count==2) flag1=false;
}else{
l++;
r--;
}
}
return flag||flag1;
}
}
后期尝试优化，比如flag使用一个，或者在判断玩第一遍循环如果是true直接返回，我以为性能会更好，但是不知道为什么越来越糟，心塞~~
反正思路就是那样，遇到不同的要么删除左边的要么删除右边的，反正如果最终能回文说明true，还是不能回文就是false。
PS：刚刚发生件小事：我不是有个刷leetcode的群么，群友问了一道题，我去看了，一脸懵逼，就是一道二叉树动态规划的题。本来我动态规划都是一知半解，还加上二叉树，日狗了，智商上的碾压~~这里立个flag：今天群友推荐的dp讲解的视频一定要学了并做笔记！！！
棒球比赛
题目：你现在是棒球比赛记录员。给定一个字符串列表，每个字符串可以是以下四种类型之一：
1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
2. "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
3. "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
4. "C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。
示例 1:
输入: ["5","2","C","D","+"]
输出: 30
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到2分。总和是：7。
操作1：第2轮的数据无效。总和是：5。
第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
第4轮：你可以得到5 + 10 = 15分。总数是：30。
示例 2:
输入: ["5","-2","4","C","D","9","+","+"]
输出: 27
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到-2分。总数是：3。
第3轮：你可以得到4分。总和是：7。
操作1：第3轮的数据无效。总数是：3。
第4轮：你可以得到-4分（第三轮的数据已被删除）。总和是：-1。
第5轮：你可以得到9分。总数是：8。
第6轮：你可以得到-4 + 9 = 5分。总数是13。
第7轮：你可以得到9 + 5 = 14分。总数是27。
注意：
输入列表的大小将介于1和1000之间。
列表中的每个整数都将介于-30000和30000之间。
思路：还好这个题没说不能使用额外空间。我现在的建议就是每轮得分存放在一个数组里、这样也好知道上一轮，上两轮的分数啥的。用一个数字表示数组下标保证无效的，前两个得分和，上一个得分两倍的都能很容易找出。我去写代码试试。
嗯嗯，写出来了，思路还可以，但是字符串判断这块我觉得有点浪费性能？？反正效率不是很高，才超过百分之八十多的人，直接贴代码：
class Solution {
public int calPoints(String[] ops) {
int[] c = new int[ops.length];
int index = 0;
for(int i = 0; i<ops.length;i++){
if(ops[i].equals("+")){
c[index] = index==0?0:(index==1?c[index-1]:c[index-1]+c[index-2]);
index++;
}else if(ops[i].equals("D")){
c[index] = index==0?0:c[index-1]*2;
index++;
}else if(ops[i].equals("C")){
index --;
}else{
c[index] = Integer.valueOf(ops[i]);
index++;
}
}
int sum = 0;
for(int j=0;j<index;j++){
sum += c[j];
}
return sum;
}
}
其实这个判断，index从0开始，我在想如果从2开始 是不是就可以不用三目运算了？我再改一下试试。思路对了，改完之后超过百分百的人了：
class Solution {
public int calPoints(String[] ops) {
int[] c = new int[ops.length+2];
int index = 2;
for(int i = 0; i<ops.length;i++){
if(ops[i].equals("+")){
c[index] = c[index-1]+c[index-2];
index++;
}else if(ops[i].equals("D")){
c[index] = c[index-1]*2;
index++;
}else if(ops[i].equals("C")){
index --;
}else{
c[index] = Integer.valueOf(ops[i]);
index++;
}
}
int sum = 0;
for(int j=2;j<index;j++){
sum += c[j];
}
return sum;
}
}
重复叠加字符串匹配
题目：给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数，使得字符串B成为叠加后的字符串A的子串，如果不存在则返回 -1。举个例子，A = "abcd"，B = "cdabcdab"。答案为 3， 因为 A 重复叠加三遍后为 “abcdabcdabcd”，此时 B 是其子串；A 重复叠加两遍后为"abcdabcd"，B 并不是其子串。注意: A 与 B 字符串的长度在1和10000区间范围内。
思路：思路就是不断字符串匹配。其实这个题我做过类似的。这个题可以这么阐述：如果B是A的叠加然后掐头去尾形成的子串。返回A叠加的次数。如果不是返回-1。只要能明白这句话这个题就简单的多了。只不过因为都是字符串操作，所以性能上应该要优化。我先上第一版本的代码
class Solution {
public int repeatedStringMatch(String A, String B) {
if(A.indexOf(B)!=-1) return 1;
String aa = A;
int l = B.length()/A.length();
int res = 1;
//最多就是前面去了点，后面去了点但是中间不能去。所以是倍数+2
for(int i = 2;i<=l+2;i++){
A += aa;
res++;
if(A.indexOf(B)!=-1) return res;
}
return -1;
}
}
性能一言难尽，咱们换一个话题，说说怎么优化吧。感觉优化点有两个：
- string可以换成变长字符串stringBuffer。
- 我感觉这个规律可以更加优化的。
我去试着改良：不断改良从超过百分之五到超过百分之六十多。就是上面说的两个知识点。
image.png
下面是改良版的代码：
class Solution {
public int repeatedStringMatch(String A, String B) {
if(A.indexOf(B)!=-1) return 1;
StringBuffer sb = new StringBuffer(A);
int l = B.length()/A.length();
//最多就是前面去了点，后面去了点但是中间不能去。所以是倍数+2
for(int i = 2;i<=l+2;i++){
sb.append(A);
if(i>=l && sb.indexOf(B)!=-1) return i;
}
return -1;
}
}
剩下的我直接去看人家的代码吧，事先预测一下，性能好的应该是用char操作。看看预测的准不准：
好吧，我猜错了，人家也是用的字符串处理。直接上代码：
class Solution {
public int repeatedStringMatch(String A, String B) {
int i = 1;
StringBuilder s = new StringBuilder(A);
int blength = B.length();
while(s.length() < blength){
s.append(A);
i++;
}
return s.lastIndexOf(B) == -1?((s.append(A)).lastIndexOf(B)==-1?-1:i+1):i;
}
}
感觉相似度百分之六十以上，逻辑相似百分之九十。为什么性能差这么多呢？我也是循环追加啊。奇了怪了。
emmm...找到问题了！！！lastIndexOf比indexOf性能好！！！！一样一样的代码换成lastIndexOf性能就上去了！！
image.png
我去看看这两个方法的源码：事实证明应该是差不多的。而且我用了伪代码测试，还是indexOf快，只能接收群友的说法：leetcode测试案例的问题。算了算了，这个问题过吧，下一题。
测试demo
最长同值路径
题目：给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。注意：两个节点之间的路径长度由它们之间的边数表示。
题目截图
思路:总思路依然是递归。只不过除了参数树以外应该还传一个参数：也就是当前节点的值。然后我们去判断子节点是值是不是等于根节点的值，如果是的话计数+1.另外应该设置一个全局变量max，保证max是计数的最大值。暂时思路是这样的，我去实现下试试。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int max;
public int longestUnivaluePath(TreeNode root) {
if(root==null) return 0;
getMax(root,root.val);
return max;
}
public int getMax(TreeNode root,int val){
if(root==null) return 0;
int l = getMax(root.left,root.val);
int r = getMax(root.right,root.val);
max = Math.max(max,l+r);
if(root.val==val) return l+r+1;
return 0;
}
}
第一版本的代码！！！错的老惨了！！！
又是怪我审题不清，我以为是所有相连接的数值相同的路径数。结果不是，是一条线。画个图比喻：
题目要求图
讲真，一方面确实是我傻，没理解题意，另一方面两个例子太抽象了吧？非得用测试案例才能知道题目是啥意思。。。
呵！我去改了：
改完回来了，还好比较容易改，我上面代码返回的是左边+右边+1的值，现在返回左边右边中较大值+1就行了。如下代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int max;
public int longestUnivaluePath(TreeNode root) {
if(root==null) return 0;
getMax(root,root.val);
return max;
}
public int getMax(TreeNode root,int val){
if(root==null) return 0;
int l = getMax(root.left,root.val);
int r = getMax(root.right,root.val);
max = Math.max(max,l+r);
if(root.val==val) return Math.max(l,r)+1;
return 0;
}
}
我觉得这道题最大的坑点就是题意。。剩下的就是常规递归。不过我这个性能不咋地，我去看看性能第一的代码：
image.png
感觉代码差别不大、我这里用了一个val的参数，方便判断当前节点是不是一段路径。而人家的代码没有这个参数，通过判断当前节点和子节点是否相等从而判断是不是有一段路径。这个代码处于能看懂的阶段，但是自己想不出这么写。
而且我就很奇怪，我是在return中+1.他这个是每个l和r都+1.明明应该是我的运算少，为啥还会我的性能低呢？
唯一的区别也就是我我这里一个if-ese，人家是两个三目运算吧？今天做题还算顺利，但是让性能搞得我头疼。难不成是因为我每次都要多判断一个root==null？我去改动试试。
一样一样的代码，就是我变量名字不一样和方法名字不一样，结果我5ms运行，人家2ms运行？？？欺负人么？脑壳更疼了，下一题下一题吧。
员工的重要性
题目:给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。
示例 1:
输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出: 11
解释:
员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。
注意:
一个员工最多有一个直系领导，但是可以有多个直系下属
员工数量不超过2000。
思路：这个题要结合给的模板看，这个员工是一个对象。那就好找了，一层层往下找，知道下属都为空被。我去做做试试！讲真，我觉得这个要是一个sql题更加合适。。。
好了，第一版做出来了，思路没问题，性能不能聊：
/*
// Employee info
class Employee {
// It's the unique id of each node;
// unique id of this employee
public int id;
// the importance value of this employee
public int importance;
// the id of direct subordinates
public List<Integer> subordinates;
};
*/
class Solution {
int sum;
public int getImportance(List<Employee> employees, int id) {
List<Integer> list = null;
for(Employee e:employees){
if(e.id==id){
sum += e.importance;
list = e.subordinates;
break;
// employees.remove(e);
}
}
for(int i :list){
getImportance(employees,i);
}
return sum;
}
}
注意上面有一句被屏蔽的代码:remove();因为这个在循环里，如果删除会影响后续遍历，从而报错，所以不能加上。后来发现直接移除break倒是可以，但是性能还不如之前呢，所以这句就没算。
/*
// Employee info
class Employee {
// It's the unique id of each node;
// unique id of this employee
public int id;
// the importance value of this employee
public int importance;
// the id of direct subordinates
public List<Integer> subordinates;
};
*/
class Solution {
int sum;
public int getImportance(List<Employee> employees, int id) {
for(Employee e:employees){
if(e.id==id){
sum += e.importance;
for(int i :e.subordinates){
getImportance(employees,i);
}
break;
}
}
return sum;
}
}
优化再优化，依然性能感人，我怀疑我是思路上的错误！不是代码编写上的了。换个思路试试。
- 没忍住看了排名第一的代码，用了一个map中间集合来处理。其实想想也合理，毕竟map 的查找效率本来就比list强。。但是无缘无故突然多一个空间咋不说呢。。。哎，好吧，我就是在为我思路不开阔找借口。
附上代码吧，其实逻辑差不多，只不过我是用list遍历人家是用map。
/*
// Employee info
class Employee {
// It's the unique id of each node;
// unique id of this employee
public int id;
// the importance value of this employee
public int importance;
// the id of direct subordinates
public List<Integer> subordinates;
};
*/
class Solution {
Map<Integer,Employee> map;
int sum;
public int getImportance(List<Employee> employees, int id) {
map = new HashMap<Integer,Employee>();
for(Employee e:employees){
map.put(e.id,e);
}
getRes(id);
return sum;
}
public void getRes(int id){
Employee e = map.get(id);
sum += e.importance;
for(int i:e.subordinates){
getRes(i);
}
}
}
用了一层map性能顿时超过百分之九十八的人了，这道题其实不难，好了下一题吧。
交替位二进制数
题目：给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。
示例 1:
输入: 5
输出: True
解释:
5的二进制数是: 101
示例 2:
输入: 7
输出: False
解释:
7的二进制数是: 111
示例 3:
输入: 11
输出: False
解释:
11的二进制数是: 1011
示例 4:
输入: 10
输出: True
解释:
10的二进制数是: 1010
思路：额反正目前为止我觉得这道题是一个送分题。不就是要判断一个数的二进制有没有00或者11么？而且已经说了正整数，简直？？？估计考的又是性能了。我不觉得单纯解题上会有什么坑
我没用最无脑的字符串判断，用屁股想也知道肯定性能可怜的不行，而且用了一边flag标记状态，性能超过百分之八十多，直接贴代码:
class Solution {
public boolean hasAlternatingBits(int n) {
boolean flag = (n%2==0?false:true);
while(n>0){
if(n%2==0){
if(flag) return false;
flag = true;
}else{
if(!flag) return false;
flag = false;
}
n=n/2;
}
return true;
}
}
其实一开始我想用0 1来表示，加加减减的，如果超过1说明连续了。但是发现6的测试案例 110 ，先减 再加 再加，最后也没变化超过一，所以数字不能表示，然后换成布尔值了。
优化点的话，我觉得可能能更直观的判断？直接判断1，0吧，之前做的时候就有隐隐的想法，但是不确定0，1直接量会不会性能好啊，，
!!!!!!!!!我合理怀疑我被针对了，一样一样的代码，人家运行超过百分百(0ms)，我运行就只超过百分之八十一(1ms)???这是要闹哪样?
首先说一下，人家的思路就是直接比较字面量。然后我反正运行还是超过八十多，顺便贴上代码参考吧：
class Solution {
public boolean hasAlternatingBits(int n) {
int val = n%2;
n = n/2;
int temp = 0;
while(n!=0){
temp = n%2;
if(temp==val){
return false;
}
val = temp;
n=n/2;
}
return true;
}
}
反正就这样了，下一题吧。
计数二进制字串
题目：给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。重复出现的子串要计算它们出现的次数。
示例 1 :
输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
请注意，一些重复出现的子串要计算它们出现的次数。
另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
示例 2 :
输入: "10101"
输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
注意：
s.length 在1到50,000之间。
s 只包含“0”或“1”字符。
思路：其实可以这么看 0011 就包含两组， 000111包含三组。00001111包含四组。所以可以把每一个分界点单提出来。
很好，一次通过，可喜可贺。
这里要说一下，我上面的思路可能只有我自己懂了，但是没说清楚。
是这么个道理：比如 11100110。首先11100.三个1两个0只能组成2组，一个是1100一个是10。然后往下判断：0011能组成两组 0011和01.再往下110能组成1组。判断的依据就是挨着的相同元素的个数取少的那个。
然后我处理的第一步就是相同元素累加。我不用知道第一个元素是1还是0.反正是一种。第一种元素个数，第二种元素个数，第一种元素个数，第二种元素个数以此类推。比如11100011001010111
就变成了 3，3， 2，2，1，1，1，1，3（本来想画个图的，但是无奈我手残）
献丑了！
反正思路就是如图，接着上代码:
class Solution {
public int countBinarySubstrings(String s) {
int[] c = new int[s.length()];
int n = 0;
int count = 1;
char[] arr = s.toCharArray();
for(int i = 0;i<arr.length-1;i++){
if(arr[i]==arr[i+1]){
count++;
}else{
c[n]=count;
n++;
count=1;
}
}
//最后一个元素类型个数肯定没存呢，所以存进去
c[n] = count;
int res =0;
for(int j = 0; j<n; j++){
res += Math.min(c[j],c[j+1]);
}
return res;
}
}
其实这道题的这种思路性能一般，但是我觉得应该是我写的问题，不是思路问题，才超过百分之七十多的人。也不太能想出优化方案了，我直接看排行第一的代码去吧。怎么说呢，一样一样的代码我提交几次就有几次结果。从百分百到百分之七十多。。
不过我上面确实写累赘了！其实这个数组我们保存再判断可以，但是不保存数组直接算出来也ok，我贴一下新代码（其实就是上个思路的进化版）：
class Solution {
public int countBinarySubstrings(String s) {
int res =0;
int count = 1;
int last = 0;
char[] arr = s.toCharArray();
for(int i = 0;i<arr.length-1;i++){
if(arr[i]==arr[i+1]){
count++;
}else{
res +=(count>last?last:count);
last = count;
count=1;
}
}
res += Math.min(last,count);
return res;
}
}
image.png
另外注意下，两个判断我一个用三目运算一个用的Math.min();其实本质没什么区别，我之所以这么写只是为了测试性能。
然后今天的刷题记录就到这里了，很开心今天没遇到什么难题，然后刷了八道题，哈哈，给自己点赞！另外今天周五了，也祝大家周末愉快~~~~~如果稍微帮到你了记得点个喜欢点个关注呦！我先去看讲解动态规划的视频去了，每天进步一点点！
网友评论