面试题4：二维数组中的查找
以 matrix 中的左下角元素为标志数 flag，则有：
- 若 flag > target，则 target 一定在 flag 所在行的上方，即 flag 所在行可被消去。
- 若 flag < target，则 target 一定在 flag 所在列的右方，即 flag 所在列可被消去。
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
int len = matrix.length;
if(len < 1) return false;
int row = len - 1, col = 0;
while(row >= 0 && col < len) {
if(matrix[row][col] > target) row--;
else if(matrix[row][col] < target) col++;
else return true;
}
return false;
}
}
————————————————————————————————————————
面试题5.替换空格
方法：遍历添加
1、初始化一个 StringBuilder，记为 res
2、遍历列表 s 中的每个字符 c：
- 当 c 为空格时，向 res 后添加字符串“%20”；
- 当 c 不为空格时：向 res后添加字符 c；
3、将 res 转化为字符串并返回
class Solution {
public String replaceSpace(String s) {
StringBuilder res = new StringBuilder();
for(char c : s.toCharArray()){
if(c == ' ') res.append("%20");
else res.append(c);
}
return res.toString();
}
}
//调用库函数
class Solution {
public String replaceSpace(String s) {
return s.replaceAll(" ", "%20");
}
}
————————————————————————————————————————
面试题6.从尾到头打印链表
方法一：辅助栈法
解题思路：
链表的遍历顺序是从头到尾访问节点，而题目要求从尾到头输出，先入后出可以借助栈来实现
1、入栈：遍历链表，将各节点值 push 入栈
2、出栈：将各节点 pop 出栈，存储于数组并返回
class Solution {
public int[] reversePrint(ListNode head) {
LinkedList<Integer> stack = new LinkedList<>();
while(head != null) {
stack.addLast(head.val);
head = head.next;
}
int[] res = new int[stack.size()];
for(int i = 0; i < stack.size(); i++) {
res[i] = stack.removeLast();
}
return res;
}
}
方法二：递归
解题思路：
先走至链表末端，回溯时依次将节点值加入列表，这样就实现链表的倒序输出
1、递推阶段：每次传入 head.next，以 head == null 为递归终止条件
2、回溯阶段：层层回溯时，将当前节点值加入结果数组
class Solution {
int[] res; //结果数组
int i = 0; //记录链表的元素总个数，表示结果数组的长度
int j = 0; //数据要存入数组的索引
public int[] reversePrint(ListNode head) {
dfs(head);
return res;
}
public void dfs(ListNode head) {
if(head == null) {
res = new int[i];
return;
}
i++; //每遍历到一个元素，则总个数加1
dfs(head.next);
res[j] = head.val; //从尾到头输出，所以链表最后一个元素要存在数组第一个位置，依次往后存
j++;
}
}
————————————————————————————————————————
面试题7.重建二叉树
解题思路：
前序遍历性质：节点按照 [ 根节点 | 左子树 | 右子树 ] 排序
中序遍历性质：节点按照 [ 左子树 | 根节点 | 右子树 ] 排序
1、前序遍历的首元素为树的根节点 root 的值
2、在中序遍历中搜索根节点 root 的索引，可将中序遍历划分为 [ 左子树 | 根节点 | 右子树 ]。
3、根据中序遍历中的左右子树的节点数量，可将前序遍历划分为 [ 根节点 | 左子树 | 右子树 ]。
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;
if(preLen != inLen) return null;
return buildTree(preorder, 0, preLen - 1, inorder, 0, inLen - 1);
}
/**
* 使用数组preorder在索引区间[preLeft, preRight]中的所有元素
* 和数组inorder在索引区间[inLeft, inRight]中的所有元素来构造二叉树
*
* preorder 二叉树前序遍历的数组
* preLeft 前序遍历结果的左边界
* preRight 前序遍历结果的右边界
* inorder 二叉树中序遍历的数组
* inLeft 中序遍历结果的左边界
* inRight 中序遍历结果的右边界
* return 二叉树的根节点
*/
public TreeNode buildTree(int[] preorder, int preLeft, int preRight,
int[] inorder, int inLeft, int inRight) {
//先写递归终止条件
if(preLeft > preRight || inLeft > inRight) return null;
int pivot = preorder[preLeft];
TreeNode root = new TreeNode(pivot); //构造当前根节点
int pivotIndex = inLeft; //用来找pivot节点在inorder数组中的索引位置
while(pivotIndex < inRight && inorder[pivotIndex] != pivot) {
pivotIndex++;
}
//构建根节点的左子节点
root.left = buildTree(preorder, preLeft + 1, preLeft + pivotIndex - inLeft,
inorder, inLeft, pivotIndex - 1);
//构建根节点的右子节点
root.right = buildTree(preorder, preLeft + pivotIndex - inLeft + 1, preRight,
inorder, pivotIndex + 1, inRight);
return root; //返回当前根节点
}
}
优化
将中序遍历的值和索引存在一个哈希表中，这样就可以一下子找到根节点在中序遍历数组中的索引
public class Solution {
private int[] preorder;
private Map<Integer, Integer> hash;
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;
if (preLen != inLen) {
return null;
}
this.preorder = preorder;
this.hash = new HashMap<>();
for (int i = 0; i < inLen; i++) {
hash.put(inorder[i], i);
}
return buildTree(0, preLen - 1, 0, inLen - 1);
}
private TreeNode buildTree(int preLeft, int preRight, int inLeft, int inRight) {
// 因为是递归调用的方法，按照国际惯例，先写递归终止条件
if (preLeft > preRight || inLeft > inRight) {
return null;
}
// 先序遍历的起点元素很重要
int pivot = preorder[preLeft];
TreeNode root = new TreeNode(pivot);
int pivotIndex = hash.get(pivot); //这一步相较于前一个方法，就省去了遍历匹配的过程
root.left = buildTree(preLeft + 1, pivotIndex - inLeft + preLeft,
inLeft, pivotIndex - 1);
root.right = buildTree(pivotIndex - inLeft + preLeft + 1, preRight,
pivotIndex + 1, inRight);
return root;
}
}
变换题：从中序与后序遍历序列构造二叉树
解题思路：
中序遍历性质：节点按照 [ 左子树 | 根节点 | 右子树 ] 排序
后序遍历性质：节点按照 [ 左子树 | 右子树 | 根节点 ] 排序
1、后序遍历的尾元素为树的根节点 root 的值
2、在中序遍历中搜索根节点 root 的索引，可将中序遍历划分为 [ 左子树 | 根节点 | 右子树 ]。
3、根据中序遍历中的左右子树的节点数量，可将前序遍历划分为 [ 左子树 | 右子树 | 根节点 ]。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
Map<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
int inLen = inorder.length;
int postLen = postorder.length;
if(inLen != postLen) return null;
for(int i = 0; i < inLen; i++) {
map.put(inorder[i], i);
}
}
public TreeNode dfs(int[] inorder, int inLeft, int inRight,
int[] postorder, int postLeft, int postRight) {
if(inLeft > inRight || postLeft > postRight) return null;
int pivot = postorder[postRight];
int pivotIndex = map.get(pivot);
root.left = dfs(inorder, inLeft, pivot - 1,
postorder, postLeft, postLeft + pivot - inLeft - 1);
root.right = dfs(inorder, pivot + 1, inRight,
postorder, postLeft + pivot - inLeft, postRight - 1);
return root;
}
}