计算质数 问题陈述 统计所有小于非负整数 n 的质数的数量。 思路分析 质数：除了1和本身之外，没有别的因数。因此可以对1<i<n, 判断s%i==0？ 代码实现 12345678910111213141516171819public int countPrimes(int n) { if (n <= 2) return 0; boolean[] primes = new boolean[n]; //创建整个素数数组 Arrays.fill(primes, true); //初始化全部为素数 primes[0] = false; primes[1] = false; //划掉0和1 int sqrt = (int)Math.sqrt(n); //设置上界 for (int i = 2; i <= sqrt; i++) { if (!primes[i]) continue; //不是素数，可以跳过 ...

从后序序列和中序序列构造二叉树 问题陈述 123456789前序序列 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]后序遍历 postorder = [9,15,7,20,3] 3 / \ 9 20 / \ 15 7 代码实现 12345678910111213141516171819202122232425//实现模板和前序加中序一样的，唯一在递归序列的索引划分。class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { HashMap<Integer,Integer> map=new HashMap<>(); for(int i=0;i<inorder.length;i++){ map.put(inorder[i],i); } return bu ...

把有序数组转换为二叉搜索树 问题陈述 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 123456789给定有序数组: [-10,-3,0,5,9],一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5 代码实现 123456789101112131415class Solution{ int[] nums; public TreeNode sortedToBST(int[] nums){ this.nums=nums; return helper(0,nums.length-1); } public TreeNode helper(int left,int right){ if(left>right) return null; ...

验证二叉搜索树 问题陈述 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 问题解决 根据中序遍历的特性，若为二叉搜索树，则中序结果必为有序，所以可以判断当前结点是否大于先前结点。 代码实现 123456789101112131415class Solution{ long pre=Long.MIN_VALUE; public boolean isBST(TreeNode root){ if(root==null) return true; //访问左子树 if(!isBST(root.left)) return false; //访问当前结点，是否小于先前结点。 if(root.val<pre) return false; pre=root.val; //访问右子树 ...

中序遍历 问题陈述 实现二叉树的中序遍历 问题解决 1、递归法 根据中序遍历“左根右”的特点，编写代码如下。 12345678910111213class Solution{ public List<Integer> inorderTravelsal(TreeNode root){ List<Integer> list=new ArrayList<>(); dfs(list,root); return list; } public void dfs(List<Integer> list,TreeNode root){ if(root==null) return null; dfs(list,root.left); list.add(root.val); dfs(list,root.right); }} 2、迭代法（基于栈） 123456789101112 ...

二叉树的层序及Z形遍历 问题陈述 1、给你一个二叉树，请你返回其按 层序遍历和Z形遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 示例： 二叉树：[3,9,20,null,null,15,7], 1234567891011121314151617 3 / \ 9 20 / \ 15 7层序返回结果：[ [3], [9,20], [15,7]]Z形返回结果：[ [3], [20,9], [15,7],] 层序遍历 12345678910111213141516171819202122232425262728class Solution{ public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new ArrayDeque<>( ...

从前序和中序序列构造二叉树 问题陈述 由中序序列和前序序列构造二叉树。 问题求解 12345678910111213141516171819202122232425262728public class PI_BuildTree { public TreeNode buildTree(int[] preOrder,int[] inOrder){ return buildHelper(preOrder,0,preOrder.length,inOrder,0,inOrder.length); } public TreeNode buildHelper(int[] preOrder,int p_start,int p_end,int[] inOrder,int i_start,int i_end){ if(p_start==p_end) return null; int root_val=preOrder[0]; TreeNode root=new TreeNode(root ...

二叉树的最大深度 问题陈述 给定一棵二叉树，求其深度。 问题详解 1、递归 12345678class Solution{ public int maxDeep(TreeNode root){ if(root==null) return 0; int left=maxDeep(root.left); int right=maxDeep(root.right); return Math.max(left,right)+1; }} 基于BFS的思想 12345678910111213141516public int maxDeep(TreeNode root){ if(root==null) return 0; LinkedList<TreeNode> list=new LinkedList<>(); list.add(root); int maxDepth=0; while(!list.isEmpty())& ...

柱状图中的最大矩形 问题陈述 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 如图，最大矩形面积为10。 问题解决 1、暴力法 设置两个指针，第一个指针i从第一个柱形到最后一个柱形，第二个指针j从i开始遍历到尾，实现穷举，每一轮找出一个最大面积。 2、代码实现 12345678910111213class Solution{ public int getMaxArea(int[] heights){ int Area=0; for(int i=0;i<heights.length;i++){ int h=Integer.MAX_VALUE; for(int j=i;j<heights.length;j++){ h=Math.min(h,height[j]); Area=Math.max(Area,(j- ...

矩阵置零 问题陈述 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用**原地算法。** 代码实现 12345678910111213141516171819202122232425class Solution{ public void setZero(int[][] matrix){ int R=matrix.length; int C=matrix[0].length; Set<Integer> row=new HashSet<Integer>(); Set<Integer> col=new HashSet<Integer>(); //遍历原始矩阵，找到值为0的行标和列标。并存储起来。 for(int i=0;i<R;i++){ for(int j=0;j<C;j++){ if(matrix[i] ...