面试题4、5、6、7

面试题4:二维数组中的查找

面试题4、5、6、7
以 matrix 中的左下角元素为标志数 flag,则有:

  • 若 flag > target,则 target 一定在 flag 所在行的上方,即 flag 所在行可被消去。
  • 若 flag < target,则 target 一定在 flag 所在列的右方,即 flag 所在列可被消去。

面试题4、5、6、7
面试题4、5、6、7

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.替换空格

面试题4、5、6、7

方法:遍历添加

1、初始化一个 StringBuilder,记为 res

2、遍历列表 s 中的每个字符 c:

  • 当 c 为空格时,向 res 后添加字符串“%20”;
  • 当 c 不为空格时:向 res后添加字符 c;

3、将 res 转化为字符串并返回

面试题4、5、6、7
面试题4、5、6、7
面试题4、5、6、7

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.从尾到头打印链表

面试题4、5、6、7

方法一:辅助栈法

解题思路:

链表的遍历顺序是从头到尾访问节点,而题目要求从尾到头输出,先入后出可以借助栈来实现

1、入栈:遍历链表,将各节点值 push 入栈

2、出栈:将各节点 pop 出栈,存储于数组并返回

面试题4、5、6、7

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、回溯阶段:层层回溯时,将当前节点值加入结果数组

面试题4、5、6、7
面试题4、5、6、7

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.重建二叉树

面试题4、5、6、7
解题思路:

前序遍历性质:节点按照 [ 根节点 | 左子树 | 右子树 ] 排序
中序遍历性质:节点按照 [ 左子树 | 根节点 | 右子树 ] 排序

1、前序遍历的首元素为树的根节点 root 的值

2、在中序遍历中搜索根节点 root 的索引,可将中序遍历划分为 [ 左子树 | 根节点 | 右子树 ]。

3、根据中序遍历中的左右子树的节点数量,可将前序遍历划分为 [ 根节点 | 左子树 | 右子树 ]。
面试题4、5、6、7
面试题4、5、6、7

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;
    }
}

变换题:从中序与后序遍历序列构造二叉树

面试题4、5、6、7
解题思路:

中序遍历性质:节点按照 [ 左子树 | 根节点 | 右子树 ] 排序
后序遍历性质:节点按照 [ 左子树 | 右子树 | 根节点 ] 排序

1、后序遍历的尾元素为树的根节点 root 的值

2、在中序遍历中搜索根节点 root 的索引,可将中序遍历划分为 [ 左子树 | 根节点 | 右子树 ]。

3、根据中序遍历中的左右子树的节点数量,可将前序遍历划分为 [ 左子树 | 右子树 | 根节点 ]。

面试题4、5、6、7
面试题4、5、6、7

/**
 * 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;					
    }
}
上一篇:第19课:郭盛华课程_VB编程之读取TXT文件


下一篇:VB 中自定义弹出提示框的位置