LeetCode 221.最大正方形
题目在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例：
12345678输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4
思路 + 代码是动态规划的题目。
关键在于问题的转化。
问题转化为最长边长。
然后截止当前位置的最长边长是左边、上边及右上三者中的最小值 + 1。
12345678910111213141516171819class Solution { public int maximalSquare(char[][] matrix) { if(matrix.length==0 || matrix[0].length==0) return 0; int row = matrix.length; int col = matrix[0].length; int[][] dp = new int[row+1][col+1]; int max_side = 0; for(in ...
LeetCode 62.不同路径
题目一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
思路 + 代码动态规划。。用回溯竟然做不出来
123456789101112131415161718class Solution { public int uniquePaths(int m, int n) { if(m<=0 || n<=0) return 0; int[][] dp = new int [m][n]; for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ if(i==0) dp[i][j] = 1; else if(j==0) ...
LeetCode 238.除自身以外数组的乘积
题目给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例：12输入: [1,2,3,4]输出: [24,12,8,6]
说明：请不要使用除法，且在 O(n) 时间复杂度内完成此题。
思路 + 代码不能常规的循环暴力解决，因为时间限制在O(n)内。
考虑上三角/下三角的乘法。
123456789101112131415161718class Solution { public int[] productExceptSelf(int[] nums) { int len = nums.length; int[] res = new int[len]; Arrays.fill(res, 1); int left = 1, right=1; for(int i=0; i<len; i++) { // 只经过左指针操作，res[0] = ...
LeetCode 114.二叉树展开为链表
题目给定一个二叉树，原地将它展开为链表。
例如，给定二叉树：
12345 1 / \ 2 5 / \ \3 4 6
将其展开为：
12345678910111 \ 2 \ 3 \ 4 \ 5 \ 6
题解 + 思路一开始想的是递归，但是递归是由底向顶递归生成，而这道题是由顶到底生成，虽然存在子问题，但是仍难以求解。
其实可以看做如下步骤：
找到左子树的最右节点。
12345 1 / \ 2 5 / \ \3 4 6
将右子树移到左子树的最右节点。
123456789 1 / 2 / \ 3 4 \ 5 \ 6
右子树换为左子树，左子树置为 null
1234567891 \ 2 / \ 3 4 \ 5 \ 6
从右节点开始，继续该操作
12345678910111 \ 2 \ ...
LeetCode 22.括号生成
题目给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
1234567[ "((()))", "(()())", "(())()", "()(())", "()()()"]
思路 + 代码回溯法，通过两个整数统计“（”与“）”的数量。
1234567891011121314151617181920class Solution { private List<String> res = new ArrayList<>(); public List<String> generateParenthesis(int n) { if(n<1) return res; backtracing("", 0, 0, n); return res; } ...
LeetCode 437.路径总和 III
题目给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例1：123456789101112131415root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \3 -2 1返回 3。和等于 8 的路径有:1. 5 -> 32. 5 -> 2 -> 13. -3 -> 11
思路 + 代码双重递归。
首先建立一个递归寻找以每个节点为根节点的路径查找。
再建立一个递归遍历每一个节点，并以该节点为根节点。
1234567891011121314151617181920212223242526272829303132/** * Definition for a binary t ...
LeetCode 494.目标和
题目给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例1：1234567891011输入: nums: [1, 1, 1, 1, 1], S: 3输出: 5解释: -1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3一共有5种方法让最终目标和为3。
注意：
数组非空，且长度不会超过20。
初始的数组的和不会超过1000。
保证返回的最终结果能被32位整数存下。
思路 + 代码首先是回溯方法。
12345678910111213141516class Solution { private int cnt = 0; public int findTargetSumWays(int[] nums, int S) { dfs(nums, S, 0, 0); ...
LeetCode 160.相交链表
题目编写一个程序，找到两个单链表相交的起始节点。
思路 + 代码1. 最容易想到的，两层遍历求解。
12345678910111213141516171819202122232425262728/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA==null || headB==null) return null; ListNode tmp; whi ...
LeetCode 23.合并K个排序链表
题目合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例：1234567输入:[ 1->4->5, 1->3->4, 2->6]输出: 1->1->2->3->4->4->5->6
思路 + 代码合并两个有序链表的翻版。
123456789101112131415161718192021222324252627282930313233343536373839/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists==null || li ...
LeetCode 543.二叉树的直径
题目给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例：给定二叉树12345 1 / \ 2 3 / \ 4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
思路 + 代码路径长度一定是以某个节点为根节点，左右子树的最大深度和。
与题目求二叉树的最大深度类似
1234567891011121314151617181920212223242526/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { private int sum; ...
