第30天--算法（Leetcode 124,125,127）

124.二叉树的最大路径和

public int maxPathSum(TreeNode root) {         if(root == null) {             return 0;         }         return process(root).max;     }     public Info process(TreeNode root) {         if(root == null) {             return null;         }         Info left = process(root.left);         Info right = process(root.right);         int beginX = root.val;         int max = root.val;         if(left != null) {             beginX = Math.max(beginX,root.val + left.beginX);             max = Math.max(max,left.max);         }         if(right != null) {             beginX = Math.max(beginX,root.val + right.beginX);             max = Math.max(max,right.max);         }         max = Math.max(beginX,max);         if(left != null && right != null) {             max = Math.max(max,left.beginX + root.val + right.beginX);         }
        return new Info(beginX,max);     } class Info {     int beginX;     int max;     public Info(int beginX,int max) {         this.beginX = beginX;         this.max = max;     } } 125.验证回文串 public boolean isPalindrome(String s) {         if(s == null || s.length() == 0) {             return true;         }         char s1[] = s.toCharArray();         int L = 0;         int R = s1.length - 1;         while(L < R) {             if(isValidChar(s1[L]) && isValidChar(s1[R])) {                 if(!isEqual(s1[L],s1[R])) {                     return false;                 }                 L ++;                 R --;             }else {                 if(!isValidChar(s1[L])) {                     L ++;                 }                 if(!isValidChar(s1[R])) {                     R --;                 }             }         }         return true;     }     public boolean isValidChar(char c) {         if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) {             return true;         }         return false;     }     public boolean isEqual(char c1,char c2) {         return String.valueOf(c1).equalsIgnoreCase(String.valueOf(c2));     } 127.单词接龙 public int ladderLength(String beginWord, String endWord, List wordList) {         HashSet dict = new HashSet<>(wordList);         if(!dict.contains(endWord)) {             return 0;         }         HashSet start = new HashSet<>();         HashSet end = new HashSet<>();         HashSet visit = new HashSet<>();         start.add(beginWord);         end.add(endWord);         for(int len = 2;!start.isEmpty();len ++) {             HashSet next = new HashSet<>();             for(String s : start) {                 for(int i = 0;i < s.length();i ++) {                     char s1[] = s.toCharArray();                     for(char temp = 'a';temp <= 'z';temp ++) {                         if(s1[i] != temp) {                             s1[i] = temp;                             String str = String.valueOf(s1);                             if(end.contains(str)) {                                 return len;                             }                             if(dict.contains(str) && !visit.contains(str)) {                                 visit.add(str);                                 next.add(str);                             }                         }                     }                 }             }             start = next.size() <= end.size() ? next : end;             end = next.size() > end.size() ? next : end;         }         return 0;     }