For example,
X X X X X O O X X X O X X O X X
After running your function, the board should be:
X X X X X X X X X X X X X O X X
分析：给你一个数组，里面包含了x(或者X) 还有 o(或者O)，要求我们把o(或者O)被x(或X)包围的情况，转换成 o -> x 而 O -> X
这个题目，其实是典型的广度搜索吧。。
解题方法：居然所有的边界o(或者O),我们都认为它是不被包围的，那么我们只要从边界入手就可以了...我们用一个二维数组flags来确定每个位置该出现什么字母，如：flags[row][col] = 0 则 row行 col列出现的字母为x(或者X), flags[row][col] = 1 则 row行 col列出现的字母为o(或者O),
把所有处于边界的o(或者O)加入到queue中，然后就是一个典型的BFS了，只需要循环出队入队，并做好标记，如果从队列中出去的话，证明这个位置一定是没有被X所包围的，那么标记这个位置flags[row][col] = 1;
之后只需要循环flags这个二维数组就可以了。
AC代码：
public class Solution {
private int[][] flags;//用来标记每个位置的字母
private int rowLength;//行数
private int colLength;//列数
/*自定义放入queue中的数据结构类型*/
class Node{
int i;
int j;
public Node(int i, int j) {
this.i = i;
this.j = j;
}
}
public void solve(char[][] board){
/*初始化*/
rowLength = board.length;
if (rowLength == 0 || board[0].length == 0)
return ;
colLength = board[0].length;
/*初始化flags, queue, 然后把board[][]中的边界字母为o(或者O)的取出放入queue*/
flags = new int[rowLength][colLength];
Queue
queue = new LinkedList
(); for (int i=0; i
= 0 && (board[row][col-1] == 'o' || board[row][col-1] == 'O' )&& flags[row][col-1] == 0){ queue.add(new Node(row,col-1)); } //right if (col+1 < colLength && (board[row][col+1] == 'o' || board[row][col+1] == 'O') && flags[row][col+1] == 0){ queue.add(new Node(row,col+1)); } //up if (row-1 >= 0 && (board[row-1][col] == 'o' || board[row-1][col] == 'O')&& flags[row-1][col] == 0){ queue.add(new Node(row-1,col)); } //down if (row+1 < rowLength && (board[row+1][col] == 'o' || board[row+1][col] == 'O')&& flags[row+1][col] == 0){ queue.add(new Node(row+1,col)); } } /*重新赋值board[][]*/ for (int i=0; i
题目四：
Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
分析：考察的其实就是对平衡二叉树概念的理解，和二叉树求深度的方法的掌握
一棵二叉树如果满足平衡的条件，那么包括它自身，和它的任何一个子树的左右子树的深度之差必须要小于2，这样问题就转换成了递归的了，一直递归下去，如果不满足条件，则把全局的标志flag置为false;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private boolean flag = true;
public boolean isBalanced(TreeNode root) {
calDeepthByTree(root);
return flag;
}
public int calDeepthByTree(TreeNode root) {
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 1;
int deepLeft = 0;
int deepRight = 0;
deepLeft = calDeepthByTree(root.left) + 1;
deepRight = calDeepthByTree(root.right) + 1;
if (Math.abs(deepRight - deepLeft) >= 2) {
flag = false;
}
return deepRight > deepLeft deepRight : deepLeft;
}
}
题目五：
Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
分析： 给我们一个二叉树，要求出从根结点到叶子结点的最短的路径（依旧还是递归哈！）
很简单，直接看代码：
AC代码：
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int minDepth(TreeNode root) {
/*递归结束条件*/
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 1;
int leftdepth = minDepth(root.left);
int rightdepth = minDepth(root.right);
/*当其中左右子树有一支是为null的时候，那么路径也只有另外一支了，不管多长都只能选那条路了*/
if (leftdepth == 0){
return rightdepth+1;
}
if (rightdepth == 0){
return leftdepth+1;
}
/*返回左右子树中较小的一边*/
return leftdepth > rightdepth rightdepth + 1 : leftdepth + 1;
}
}