leetcode 127 给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明:
如果不存在这样的转换序列，返回 0。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。 示例 1: 输入: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”] 输出: 5 解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。
**解法一：利用广度优先遍历 beginWord只能替换wordList中和自己相差一个字符的，我们利用getDifferent方法来计算相差字符，当相差字符为1时，我们记录变换长度Len+1，并且将新的字符加入队列，同时标识变量flag[i]=1，因为wordList的数组只能访问一次两次的话就是无限循环 这里有个技巧，也就是当需要往Queu中从两个数字时，利用Pair<String,Integer>。之后利用 Pair node=que.remove(); String str=(String)node.getKey(); int len=(int)node.getValue();取出值 三个呢？估计得自己创建对象了 **
import javafx.util.Pair; class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Queue<Pair<String,Integer>> que=new LinkedList<>(); int []flag=new int [wordList.size()]; que.add(new Pair(beginWord,0)); while(!que.isEmpty()){ Pair node=que.remove(); String str=(String)node.getKey(); int len=(int)node.getValue(); if(str.equals(endWord))return len+1; for(int i=0;i<wordList.size();i++){ int count=getDifferent(str,wordList.get(i)); if(count==1&&flag[i]==0){ que.add(new Pair(wordList.get(i),len+1)); flag[i]=1; } } } return 0; } public int getDifferent(String a,String b){ int count=0; char c1[]=a.toCharArray(); char c2[]=b.toCharArray(); for(int i=0;i<c1.length;i++){ if(c1[i]!=c2[i])count++; } return count; } }解法二：双向的广度优先遍历。我们从beginWord，endWord分别开始，利用tag作为标志，一个遍历一次。下面的代码有错，有时间再调吧
import javafx.util.Pair; class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Queue<Pair<String,Integer>> que_begin=new LinkedList<>(); Queue<Pair<String,Integer>> que_end=new LinkedList<>(); int []flag=new int [wordList.size()]; que_begin.add(new Pair(beginWord,0)); que_end.add(new Pair(endWord,0)); int tag=1; while(!que_begin.isEmpty()){ Queue<Pair<String,Integer>> que=tag==1?que_begin:que_end; Pair node=que.remove(); String str=(String)node.getKey(); int len=(int)node.getValue(); if(str!=beginWord&&flag[wordList.indexOf(str)]==3)return len+getlen(tag==1?que_begin:que_end,str); for(int i=0;i<wordList.size();i++){ int count=getDifferent(str,wordList.get(i)); if(count==1&&flag[i]!=tag){ flag[i]+=tag; que.add(new Pair(wordList.get(i),len+1)); } } tag=tag==1?2:1; } return 0; } public int getDifferent(String a,String b){ int count=0; char c1[]=a.toCharArray(); char c2[]=b.toCharArray(); for(int i=0;i<c1.length;i++){ if(c1[i]!=c2[i])count++; } return count; } public int getlen(Queue<Pair<String,Integer>> que,String str){ while(!que.isEmpty()){ Pair node=que.remove(); int len=(int)node.getValue(); String str1=(String)node.getKey(); if(str1.equals(str))return len; } return 0; } }leetcode 129 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。 例如，从根到叶子节点路径 1->2->3 代表数字 123。 计算从根到叶子节点生成的所有数字之和。 说明: 叶子节点是指没有子节点的节点。 示例 1: 输入: [1,2,3] 1 / 2 3 输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此，数字总和 = 12 + 13 = 25. 示例 2: 输入: [4,9,0,5,1] 4 / 9 0 / 5 1 输出: 1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495. 从根到叶子节点路径 4->9->1 代表数字 491. 从根到叶子节点路径 4->0 代表数字 40. 因此，数字总和 = 495 + 491 + 40 = 1026.
class Solution { int sum=0; public int sumNumbers(TreeNode root) { getValue(root,0); return sum; } public void getValue(TreeNode root,int value){ if(root==null) return ; value=value*10+root.val; if(root.left==null&&root.right==null)sum+=value; getValue(root.left,value); getValue(root.right,value); } }leetcode:130 给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。 找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。 示例: X X X X X O O X X X O X X O X X 运行你的函数后，矩阵变为： X X X X X X X X X X X X X O X X 解释: 被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
解法:利用取反的思想，我们把所有和边界相连的O替换为*,再一次遍历整个数组，将其中的O替换为X，*替换为O
class Solution { public void solve(char[][] board) { if (board == null || board.length == 0) return; int m = board.length; int n = board[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1; if (isEdge && board[i][j] == 'O') { dfs(board, i, j); } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == 'O') { board[i][j] = 'X'; } if (board[i][j] == '#') { board[i][j] = 'O'; } } } } public void dfs(char[][] board, int i, int j) { if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') { return; } board[i][j] = '#'; dfs(board, i - 1, j); // 上 dfs(board, i + 1, j); // 下 dfs(board, i, j - 1); // 左 dfs(board, i, j + 1); // 右 } }