题目描述： 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。 解析： 动态规划 1.dp[i][j]为存储到点(i,j)时以此为右下角的正方形个数 2.只有当前值为1时才可能构成正方形 3.在上面前提下,最左边和最右边都只能构成边长为1的正方形 4.边长多大还取决于其它三个点的值 所以这边取其最小值+1，有一个为0都不能扩大 Java: class Solution { public int maximalSquare(char[][] matrix) { if(matrix == null || matrix.leng...

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 解析： 情况一：顺时针转 90 度：先转置再左右镜像 1  2  3    7  4  1 4  5  6    8  5  2 7  8  9    9  6  3 情况二：顺时针转 180 度:先上下镜像，再左右镜像（先左右再上下也可） 1  2  3    9  8  7 4  5  6    6  5  4 7  8  9 ...

29题目描述： 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 解析： 1.如果数组为空，则返回空数组 2.定义四个边界及当前方向 3.当左边界小于等于右边界，且上边界小于等于下边界时，执行while循环： 按照右、下、左、上的顺序，依次将路径上的字符添加到结果里 4.while循环结束后，返回结果 Java: class Solution { public int[] spiralOrder(int[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == ...

I题目描述： 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。 解析： 二分法 Java: class Solution { public int[] twoSum(int[] nums, int target) { int left = 0, right = nums.length - 1; for(int i = 0; i < nums.length; i++) { if(nums[left] + nums[right] < target)...

I题目描述： 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 解析： 位运算和Hashmap Java: class Solution { public int[] singleNumbers(int[] nums) { int a = 0, b = 0; for(int i = 0 ; i < nums.length; i++) { a ^= nums[i]; } int bit = a &...

题目描述： 给你一个整数数组 nums，请你将该数组升序排列。 解析： 快速排序： class Solution { public int[] sortArray(int[] nums) { qSort(nums, 0, nums.length - 1); return nums; } public void qSort(int[] arr, int start, int end) { int left = start, right = end; if(left < right) { ...

15题目描述： 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。 解析： 1.初始化数量统计变量count； 2.循环消去最右边的1：当n=0时跳出； n &= n - 1：消去数字最右边的1； count++：统计变量加1； 3.最后返回统计数量count。 Java: public class Solution { public int hammingWeight(int n) { int count = 0; while(n != 0) { ...

题目描述： 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 解析： 深度优先遍历 Java: class Solution { List<String> res = new ArrayList<>(); public List<String> generateParenthesis(int n) { dfs(n, n, ""); return res; } private void dfs(int left, int right, String c...

题目描述： 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 解析： 回溯法 Java: class Solution { List<String> list = new ArrayList<>(); public List<String> letterCombinations(String digits) { if(digits == null || digits.length() == 0) { ...

题目描述： 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明：你不能倾斜容器。 解析： 双指针 Java： class Solution { public int maxArea(int[] height) { int l = 0, r = height.length - 1; int res = 0; while(l < ...

33题目描述： 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 解析： 递归 二叉搜索树的特点是左子树的值<根节点<右子树的值; 而后续遍历的顺序是:左子节点→右子节点→根节点； Java: public boolean verifyPostorder(int[] postorder) { if(postorder == null || postorder.length == 0) { return true; } ...

7题目描述： 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 解析： 知识点： 前序遍历列表： 第一个元素永远是 【根节点 (root)】 中序遍历列表： 根节点 (root)【左边】的所有元素都在根节点的【左分支】，【右边】的所有元素都在根节点的【右分支】 算法思路： 通过【前序遍历列表】确定【根节点 (root)】 将【中序遍历列表】的节点分割成【左分支节点】和【右分支节点】 递归寻找【左分支节点】中的【根节点 (left child)】和 【右分支节点】中的【根节点 (right child)】 Java: ...

I题目描述: 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。 解析： 1.终止条件：当 root为空，说明已越过叶节点，因此返回深度0 2.递推工作：本质上是对树做后序遍历。 计算节点 root的左子树的深度，即调用 maxDepth(root.left)； 计算节点 root的右子树的深度，即调用 maxDepth(root.right)； 3.返回值：返回此树的深度，即 max(maxDepth(root.left), maxDepth(root.right)) + 1。 Java: public int m...

40题目描述： 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 解析： 1.库函数,首先把数组arr排序，定义一个新的数组res，数组的长度为k 2.遍历循环数组arr，把前k个数赋值到数组res 3.最后返回数组res即可 Java: public int[] getLeastNumbers(int[] arr, int k) { Arrays.sort(arr); int[] res = new int[k]; for(int i = 0; i <...