面试题61：把二叉树打印成多行
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
travel(pRoot,res,0);
return res;
}
public void travel(TreeNode cur,ArrayList<ArrayList<Integer>> res,int level){
if(cur==null) return;
if(res.size()<=level){
ArrayList<Integer> newLevel = new ArrayList<Integer>();
res.add(newLevel);
}
ArrayList<Integer> col = res.get(level);
col.add(cur.val);
travel(cur.left,res,level+1);
travel(cur.right,res,level+1);
}
}
面试题62：序列化二叉树
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
String Serialize(TreeNode root) {
if(root == null) return "#!";
String res = root.val + "!";
res += Serialize(root.left);
res += Serialize(root.right);
return res;
}
TreeNode Deserialize(String str) {
String[] values = str.split("!");
Queue<String> queue = new LinkedList<String>();
for(int i=0;i<values.length;i++){
queue.offer(values[i]);
}
return recover(queue);
}
TreeNode recover(Queue<String> queue){
String value = queue.poll();
if(value.equals("#")){
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(value));
root.left = recover(queue);
root.right = recover(queue);
return root;
}
}
面试题63：二叉搜索树的第K个节点
import java.util.ArrayList;
public class Solution {
public ArrayList<TreeNode> res = new ArrayList<TreeNode>();
TreeNode KthNode(TreeNode pRoot, int k)
{
if(pRoot==null || k==0) return null;
inorderTra(pRoot);
if(k<=0 || k>res.size()) return null;
return res.get(k-1);
}
public void inorderTra(TreeNode root){
if(root == null) return ;
inorderTra(root.left);
res.add(root);
inorderTra(root.right);
}
}
补充第二种做法：
public class Solution {
public TreeNode res ;
public int cnt = 0;
TreeNode KthNode(TreeNode pRoot, int k)
{
cnt = k;
if(pRoot == null) return pRoot;
help(pRoot);
return res;
}
public void help(TreeNode p){
if(p.left!=null){
help(p.left);
}
cnt--;
if(cnt == 0){
res = p;
return;
}
if(p.right!=null){
help(p.right);
}
return;
}
}
面试题64：数据流中的中位数
import java.util.PriorityQueue;
import java.util.Collections;
public class Solution {
private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(5000,Collections.reverseOrder());
public void Insert(Integer num) {
if(maxHeap.isEmpty() || num<maxHeap.peek()){
maxHeap.offer(num);
}else{
minHeap.offer(num);
}
if(maxHeap.size() > minHeap.size() + 1){
minHeap.offer(maxHeap.poll());
}else if(minHeap.size() > maxHeap.size()){
maxHeap.offer(minHeap.poll());
}
}
public Double GetMedian() {
if(maxHeap.size() > minHeap.size()){
return (double)maxHeap.peek();
}else{
return (maxHeap.peek() + minHeap.peek())/2.0;
}
}
}
面试题65：滑动窗口的最大值
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> res = new ArrayList<Integer>();
if(num == null || size<=0){
return res;
}
int n = num.length;
Deque<Integer> queue = new ArrayDeque<Integer>();
for(int i=0;i<num.length;i++){
while(!queue.isEmpty() && queue.peek()<i-size+1){
queue.poll();
}
while(!queue.isEmpty() && num[queue.peekLast()]<num[i]){
queue.pollLast();
}
queue.offer(i);
if(i>=size-1){
res.add(num[queue.peek()]);
}
}
return res;
}
}
面试题66：矩阵中的路径
为什么这么写就不对？
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
if(matrix==null||rows<1||cols<1||str==null) return false;
boolean[] visited = new boolean[matrix.length];
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(dfs(matrix,rows,cols,i,j,0,str,visited)){
return true;
}
}
}
return false;
}
public boolean dfs(char[] matrix,int rows,int cols,int i,int j,int k,char[] str,boolean[] visited){
if(k == str.length - 1){
return true;
}
int index = i*cols+j;
boolean hasPath = false;
if(i>=0&&i<rows&&j>=0&&j<cols&&matrix[index]==str[k]&&visited[index]==false){
visited[index] = true;
hasPath = dfs(matrix,rows,cols,i,j+1,k+1,str,visited)
||dfs(matrix,rows,cols,i,j-1,k+1,str,visited)
||dfs(matrix,rows,cols,i+1,j,k+1,str,visited)
||dfs(matrix,rows,cols,i-1,j,k+1,str,visited);
visited[index] = false;
}
return hasPath;
}
}
这样写就可以
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
int flag[] = new int[matrix.length];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (helper(matrix, rows, cols, i, j, str, 0, flag))
return true;
}
}
return false;
}
private boolean helper(char[] matrix, int rows, int cols, int i, int j, char[] str, int k, int[] flag) {
int index = i * cols + j;
if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index] == 1)
return false;
if(k == str.length - 1) return true;
flag[index] = 1;
if (helper(matrix, rows, cols, i - 1, j, str, k + 1, flag)
|| helper(matrix, rows, cols, i + 1, j, str, k + 1, flag)
|| helper(matrix, rows, cols, i, j - 1, str, k + 1, flag)
|| helper(matrix, rows, cols, i, j + 1, str, k + 1, flag)) {
return true;
}
flag[index] = 0;
return false;
}
}
面试题67：机器人的运动范围
public class Solution {
public int movingCount(int threshold, int rows, int cols)
{
boolean[] visited = new boolean[rows*cols];
int res = count(0,0,rows,cols,threshold,visited);
return res;
}
public int count (int i,int j,int rows,int cols,int threshold,boolean[] visited){
int cnt = 0;
int index = i*cols+j;
if(check(threshold,i,j,rows,cols,visited) == true){
visited[index] = true;
cnt = 1 + count(i+1,j,rows,cols,threshold,visited)
+ count(i-1,j,rows,cols,threshold,visited)
+ count(i,j+1,rows,cols,threshold,visited)
+ count(i,j-1,rows,cols,threshold,visited);
}
return cnt;
}
public boolean check(int threshold,int i,int j,int rows,int cols,boolean[] visited){
int valRow = getVal(i);
int valCol = getVal(j);
if(i>=0&&i<rows&&j>=0&&j<cols&&valRow+valCol<=threshold&&visited[i*cols+j]==false){
return true;
}
return false;
}
public int getVal(int i){
int val = 0;
while(i>0){
val += i%10;
i /= 10;
}
return val;
}
}