T1直接奇偶性判断秒过了。
先是尝试用滑动窗口做，结果直接TLE，代码如下，虽然可以值得优化（放在后面），但是下面这种做法理论上来说也能过，就是O(N)的时间复杂度。问题出就出在 System.out.println(c)，这几个打印函数直接让我突破2s的限制，把它们去掉就能通过了。
class Solution {
public int longestContinuousSubstring(String s) {
int len=s.length();
int left=0;
int res=0;
Deque<Character> que=new ArrayDeque<>();
for(int right=0;right<len;right++){
char c=s.charAt(right);
while(left<right&&!que.isEmpty()&&que.peekLast()-c!=-1){
left++;
System.out.println(left+" "+right);
}
que.offer(c);
System.out.println(c);
res=Math.max(res,right-left+1);
}
return res;
}
}
此外，我们并不需要一个队列ArrayDeque来存储之前访问过的所有值，我们只需要在遍历一次的过程中，判断当前字母和前一个字母是否连续就行。
class Solution {
public int longestContinuousSubstring(String s) {
int len=s.length();
int left=0;
int res=1;
for(int right=1;right<len;right++){
while(left<right&&s.charAt(right)-s.charAt(right-1)!=1){
left++;
}
res=Math.max(res,right-left+1);
}
return res;
}
}
上面做法并不是最优，由于找连续最长的原因，left++这个逻辑可以直接改成left=right。
class Solution {
public int longestContinuousSubstring(String s) {
int len=s.length();
int left=0;
int res=1;
for(int right=1;right<len;right++){
if(s.charAt(right)-s.charAt(right-1)!=1){
//当不等的时候就将left移到当前位置，right还没变化
left=right;
}
//当排除了上面不满足条件的情况再算res，即使上一步left=right，算出来的也是1
res=Math.max(res,right-left+1);
}
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 TreeNode reverseOddLevels(TreeNode root) {
int level=1;
if(root==null) return null;
Deque<TreeNode> que=new ArrayDeque<>();
que.offer(root);
while(!que.isEmpty()){
int size=que.size();
int[]arr=que.stream().mapToInt(x->x.val).toArray();
for(int i=0;i<size;i++){
TreeNode top=que.poll();
//偶数层进行首尾交换
if(level%2==0){
top.val=arr[size-1-i];
}
if(top.left!=null) que.offer(top.left);
if(top.right!=null) que.offer(top.right);
}
level++;
}
return root;
}
}
递归做法如下：
和轴对称有关的递归。
/**
* 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 TreeNode reverseOddLevels(TreeNode root) {
if(root==null) return null;
dfs(root.left,root.right,2);
return root;
}
public void dfs(TreeNode left,TreeNode right,int level){
if(left==null) return ;
if(level%2==0){
int temp=right.val;
right.val=left.val;
left.val=temp;
}
dfs(left.left,right.right,level+1);
dfs(left.right,right.left,level+1);
}
}
关于字符串前缀问题，我的技能树中只能找到字典树，我写了一个专题讲字典树，引路->算法学习-字典树。这道题的每个答案是某个字符串所有子前缀的分数和。在建树的过程中，我们就可以在途径的节点上进行子前缀的次数记录。在查询一个单词所有子前缀的分数和时，其实就可以用判断是否是前缀的startWith逻辑，在查找的过程中就途径了它的所有子前缀，将它们的子前缀次数全部加起来，最终的结果就是该单词的前缀分数和。
刚开始纠结的点是，如果p.next[c-‘a’]是相同字母怎么办，会把不是该前缀但是相同字母结尾的数字全部加上去吗？其实不是的，字典树的建立和父节点息息相关，根结点是唯一的，以后当且仅当前缀相同的时候，才会指向同一数据地址。
class Solution {
public class TireNode{
//记录某一个前缀的分数
int preValue;
TireNode[] next=new TireNode[26];
}
TireNode root=new TireNode();
//插入的同时，进行子前缀次数的记录
public void insert(String s){
TireNode p=root;
int len=s.length();
for(int i=0;i<len;i++){
char c=s.charAt(i);
if(p.next[c-'a']==null){
p.next[c-'a']=new TireNode();
}
p.next[c-'a'].preValue++;
p=p.next[c-'a'];
}
}
//查找的过程中，进行子前缀出现次数的累加
public int prefixWord(String s){
int sum=0;
int len=s.length();
TireNode p=root;
for(int i=0;i<len;i++){
char c=s.charAt(i);
if(p.next[c-'a']==null){
return sum;
}
sum+=p.next[c-'a'].preValue;
p=p.next[c-'a'];
}
return sum;
}
public int[] sumPrefixScores(String[] words) {
int len=words.length;
for(String s:words){
insert(s);
}
int[]ans=new int[len];
for(int i=0;i<len;i++){
ans[i]=prefixWord(words[i]);
}
return ans;
}
}