漫漫长夜

题目描述 最长公共前缀 难度：简单 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。 示例 1： 123输入：strs = ["flower","flow","flight"]输出："fl" 示例 2： 123输入：strs = ["dog","racecar","car"]输出：""解释：输入不存在公共前缀。 解法 纵向扫描 选取第一个字符串作为标准向下进行比较 每次比较一个字符 如果出现比较的下标与某个字符串相等，直接返回 比较出现不相等的字，直接返回 12345678910111213141516171819class Solution { public String longestCommonPrefix(String[] strs) { for (int i = 0; i < strs[0].length(); i++) ...

题目描述罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 12345678字符 数值I 1V 5X 10L 50C 100D 500M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 ...

题目描述一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？ 输入：m = 3, n = 7 输出：28 示例 2： 输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下 示例 3： 输入：m = 7, n = 3 输出：28 示例 4： 输入：m = 3, n = 3 输出：6 提示： 1 <= m, n <= 100 题目数据保证答案小于等于 2 * 109 ## 解法 动态规划 dp[i] [j]表示到第[i] [j]格的路径有多少 每一格的路径由它上边格子的路径与左边格子的路径之和组成 需要注意第一行与第一列初始化为1，因为也只有一条路可走 1mat ...

题目描述给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的 下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。 示例 1： 123输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]输出：13解释：如图所示，为和最小的两条下降路径 示例 2： 123输入：matrix = [[-19,57],[-40,-5]]输出：-59解释：如图所示，为和最小的下降路径 提示： n == matrix.length == matrix[i].length 1 <= n <= 100 -100 <= matrix[i][j] <= 100 解法 动态规划 原地dp,改 ...

题目描述给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。 示例 1: 12输入: numRows = 5输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 示例 2: 12输入: numRows = 1输出: [[1]] 解法 动态规划 由于杨辉三角的每一个值是由上一行的值所推出来的，因此可以使用动态规划 1234567891011121314151617181920212223class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> rec =new ArrayList<>(numRows); //i表示是杨辉三角的哪一行 for (int i = 0; i <numRows; i++) { ...

题目描述 解法 动态规划+找规律 dp[i]为以第i个数结尾数组中所有等差数组的子个数 dp[i]在dp[i-1]的基础上会有两种情况 要么num[i]与前一个值继续组成等差数组 等差数列： 1 2 3 4 5 6 对应的子数组个数0 0 1 3 6 10 随着等差数列的长度增加，子数组的值也在增加 可以发现从第三个数开始 每增加一个数，他们的差值都会加一 3-1、6-3、10-6 直观的写就是$$dp[i]=dp[i-1]+(dp[i-1]-dp[i-2]+1);$$ 用公式就是$$dp[i]=dp[i-1]+(n-1)*(n-2)/2$$ 要么不能组成等差数组 不能组成就保持原有数值 12345678910111213141516171819202122232425262728class Solution { public int numberOfArithmeticSlices(int[] nums) { if(nums.length==1||nums.leng ...

题目描述 解法 动态规划 暂时将将黑色看作墙 通过直观的想法，我们比较容易想到当前位置能够接到的雨水取决于当前位置的左右墙的最高位置的最小值减去当前位置的高度 暴力解法超时的原因是进行了多次计算左右的最高位置 因此动态规划有 letf[i]表示从0到i(包括i位置)的最高位置（左->右） right[i]表示从n-到i(包括i位置)的最高位置(右->左) 12345678910111213141516171819202122232425class Solution { public int trap(int[] height) { if (height.length == 0) { return 0; } int res = 0; int[] dpLeftMax = new int[height.length];//dpLeftMax[i]表示从0到i包括i的最高位置 int[] dpRightMax = new int[heigh ...

题目描述 解法 动态规划 我们规定dp[i]表示字符串s的前i个字符组成的字符串s[0,i-1]是否能够被空格拆成若干个字典里出现的单词 因为具体空格在哪里是不知道的，所以必须枚举所以情况 转移时枚举包含位置i-1的最后一个单词，看它是否出现在字典中，以及除去后，剩下的部分是否合法。 12345678910111213141516171819202122class Solution { public boolean wordBreak(String s, List<String> wordDict) { HashSet<String> wordDictSet=new HashSet<>(wordDict); boolean dp[]=new boolean[s.length()+1]; //这里设置为length+1我个人考虑是有两点 //1.考虑了空串 //2.是考虑了substring函数取前不取后 dp[0]=true; ...

题目描述 解法 动态规划 使用之前我们先看下暴力求解的思路’ 1234567891011121314class Solution { public int maxScoreSightseeingPair(int[] values) { int max=-1; for (int i = 0; i < values.length; i++) { //对每个数之前的数进行遍历，找到其中符合题目要求的最大值 for (int j = 0; j < i; j++) { if(values[i]+values[j]+(j-i)>max){ max=values[i]+values[j]-(i-j); } } } return max; }} 由于时间复杂度过高， ...

题目描述给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串，我们保证它是唯一的答案。 示例 1： 12输入：s = "ADOBECODEBANC", t = "ABC"输出："BANC" 示例 2： 12输入：s = "a", t = "a"输出："a" 示例 3: 1234输入: s = "a", t = "aa"输出: ""解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。 提示： 1 <= s.length, t.length <= 10^5 s 和 t ...