一战通offer

题目一：关于split函数开头和结尾的空格

对于一个给定的字符串，我们需要在线性(也就是O(n))的时间里对它做一些变形。首先这个字符串中包含着一些空格，就像"Hello World"一样，然后我们要做的是把着个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。比如"Hello World"变形后就变成了"wORLD hELLO"。

注：字符串开头的空格，split函数仍人当成分隔符，返回的String[]strs前几个会有相应的空串，但是末尾的空白split不考虑。

import java.util.*;
public class Transform {
    public String trans(String s, int n) {
        // write code here
        if(s == null||n == 0)
            return s;
        int count=0;
        for(int i=s.length()-1;i>=0;i--)//统计字符串末尾的空白个数！
            {
            if(s.charAt(i) == ' ')
                {
                count++;
            }else{
                break;
            }
        }
        String[] strs=s.split(" ");
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<count;i++)
            {
            sb.append(" ");
        }
        for(int i=strs.length-1;i>=0;i--)
            {
            String reverse=reverseWord(strs[i]);
            sb.append(reverse);
            sb.append(' ');
        }
            sb.deleteCharAt(sb.length()-1);
        return sb.toString();
    }
    public String reverseWord(String s){
        if(s == null||s.length() == 0)
            return s;
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<s.length();i++)
            {
            if(s.charAt(i)>='a'&&s.charAt(i)<='z')//小写转大写
                {
                sb.append((char)(s.charAt(i)-'a'+'A'));
            }else{
                sb.append((char)(s.charAt(i)-'A'+'a'));//大写转小写
            }
        }
        return sb.toString();
    }
}

对于一棵由黑白点组成的二叉树，我们需要找到其中最长的单色简单路径，其中简单路径的定义是从树上的某点开始沿树边走不重复的点到树上的另一点结束而形成的路径，而路径的长度就是经过的点的数量(包括起点和终点)。而这里我们所说的单色路径自然就是只经过一种颜色的点的路径。你需要找到这棵树上最长的单色路径。

给定一棵二叉树的根节点(树的点数小于等于300，请做到O(n)的复杂度)，请返回最长单色路径的长度。这里的节点颜色由点上的权值表示，权值为1的是黑点，为0的是白点。

 注：通过本题找到了二叉树上任一值的最大连通路径的方法。灵活运用二叉树的递归。

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
import java.util.*;
public class LongestPath {
    public int findPath(TreeNode root) {
        // write code here
        if(root == null)
            return 0;
        int[] most1=new int[1];
        int[] most0=new int[1];
        mostPath(root,most1,1);
        mostPath(root,most0,0);
        return most1[0]>most0[0]?most1[0]:most0[0];
         
    }
    //值为cur的最长路径
    public int mostPath(TreeNode root,int[] data,int cur)
        {
        if(root == null)
            return 0;
        int current=1;
        if(root.val != cur)
            current=-10000;
        
        int left=mostPath(root.left,data,cur);
        int right=mostPath(root.right,data,cur);
        current+=left+right;
        if(current > data[0])
            data[0]=current;
        if(current > 0)
            {
            if(left > 0||right > 0)
                return left>right?left+1:right+1;
            else
                return 1;
        }else
        return 0;
    }
}