Tyler-yin's blog

416. 分割等和子集难度中等218 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1: 12345输入: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11]. 示例 2: 12345输入: [1, 2, 3, 5]输... Continue reading...

221. 最大正方形难度中等428 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。 示例: 12345678输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 神必的dp 主要是状态的寻找,这题的状态是:$dp[i][j]$表示i,j点为右下角的矩形的最大宽度; 状态转移方程比较难像: $dp[i][j]=min(... Continue reading...

213. 打家劫舍 II难度中等284 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。 示例 1: 12... Continue reading...

198. 打家劫舍难度简单875 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 示例 1： 1234输入：[1,2,3,1]输出：4解释：偷窃 ... Continue reading...

96. 不同的二叉搜索树难度中等537 给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？ 示例: 12345678910输入: 3输出: 5解释:给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ ... Continue reading...

64. 最小路径和难度中等486 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例: 12345678输入:[ [1,3,1], [1,5,1], [4,2,1]]输出: 7解释: 因为路径 1→3→1→1→1 的总和最小。 1234567891011121314151617181920... Continue reading...

62. 不同路径难度中等560 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？ ... Continue reading...

53. 最大子序和难度简单 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 123输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 水题: dp[i]表示第i个之前的连续... Continue reading...

32. 最长有效括号难度困难784 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。 示例 1: 123输入: "(()"输出: 2解释: 最长有效括号子串为 "()" 示例 2: 123输入: ")()())"输出: 4解释: 最长有效括号子串为 "()(... Continue reading...

5. 最长回文子串难度中等 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 123输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。 示例 2： 12输入: "cbbd"输出: "bb" 这题目可以使用动态规划... Continue reading...