算法

找出字符串中第一个匹配项的下标 题目详解28. 找出字符串中第一个匹配项的下标 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。 示例 1： 输入：haystack = “sadbutsad”, needle = “sad”输出：0解释：”sad” 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。 示例 2： 输入：haystack = “leetcode”, needle = “leeto”输出：-1解释：”leeto” 没有在 “leetcode” 中出现，所以返回 -1 。 提示： 1 <= haystack.length, needle.length <= 104 haystack 和 needle 仅由小写英文字符组成 题解暴力求解发12345678910111213141516171819...

Z字形变换题目详解Z 字形变换 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下： P A H NA P L S I I GY I R 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。 请你实现这个将字符串进行指定行数变换的函数： string convert(string s, int numRows); 示例 1： 输入：s = “PAYPALISHIRING”, numRows = 3输出：”PAHNAPLSIIGYIR” 示例 2： 输入：s = “PAYPALISHIRING”, numRows = 4输出：”PINALSIGYAHRPI”解释：P I NA L S I GY A H RP I 示例 3： 输入：s = “A”, numR...

反转字符串中的单词题目详情反转字符串中的单词 给你一个字符串 s ，请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。 示例 1： 输入：s = “the sky is blue”输出：”blue is sky the” 示例 2： 输入：s = “ hello world “输出：”world hello”解释：反转后的字符串中不能存在前导空格和尾随空格。 示例 3： 输入：s = “a good example”输出：”example good a”解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。 提示： 1 <= s.length <= 104 s 包含英文大小写字母、数字和空格 ' '...

最长公共前缀题目详情最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串""。 示例 1： 输入：strs = [“flower”,”flow”,”flight”]输出：”fl” 示例 2： 输入：strs = [“dog”,”racecar”,”car”]输出：””解释：输入不存在公共前缀。 提示： 1 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] 仅由小写英文字母组成 题解 此题主要理解题干中的公共前缀， 例如 ​ “flower”,”flow”,”flight” 最长公共前缀为 “fl” ​ “bflower”, “afow”, “bflight” 就没有最长公共前缀 ，最长公共前缀为 “” 理解到这一层，此题也就迎刃而解了。 123456789101112131415161718192021222324252627class Solution { public...

最后一个单词的长度题目详情58. 最后一个单词的长度 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。 示例 1： 输入：s = “Hello World”输出：5解释：最后一个单词是“World”，长度为 5。 示例 2： 输入：s = “ fly me to the moon “输出：4解释：最后一个单词是“moon”，长度为 4。 示例 3： 输入：s = “luffy is still joyboy”输出：6解释：最后一个单词是长度为 6 的“joyboy”。 提示： 1 <= s.length <= 104 s 仅有英文字母和空格 ' ' 组成 s 中至少存在一个单词 题解此题比较简单，建议自己动手 123456789101112public static int lengthOfLastWord(String s) { String trim = s....

整数转罗马数字题目整数转罗马数字 七个不同的符号代表罗马数字，其值如下： 符号 值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则： 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。 只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。 给定一个整数，将其转换为罗马数字。 示例 1： 输入：num =...

罗马数字转整数题目详情 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 字符 数值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) 的左边，...

O(1)时间插入、删除和获取随机元素 题解题目详情 实现RandomizedSet 类： RandomizedSet() 初始化 RandomizedSet 对象 bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。 bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。 int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。 示例： 输入[“RandomizedSet”, “insert”, “remove”, “insert”, “getRandom”, “remove”, “insert”, “getRandom”][[], [1], [2], [2], [], [1], [2], []]输出[null, true, false, true, 2, tr...

除自身以外数组的乘积 题解题目详情 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。 示例 1: 输入: nums = [1,2,3,4]输出: [24,12,8,6] 示例 2: 输入: nums = [-1,1,0,-3,3]输出: [0,0,9,0,0] 提示： 2 <= nums.length <= 105 -30 <= nums[i] <= 30 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内 进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。） 解题思路与题解 此题题目已经很明确了，解题思路，我主要推荐空间换时间 题解一当然，老套路，这种题的暴力解法 1...

H指数 题解题目详情 给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，**h 指数** 是其中最大的那个。 示例 1： 输入：citations = [3,0,6,1,5]输出：3解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。 由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。 示例 2： 输入：citations = [1,3,1]输出：1 提示： n == citations.length 1 <= n <= 5000 0 <= citations[i] <= 1000 解题思路与题解 h 指数 是...

跳跃游戏II 题解题目详情 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处: 0 <= j <= nums[i] i + j < n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。 示例 1: 输入: nums = [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 示例 2: 输入: nums = [2,3,0,1,4]输出: 2 提示: 1 <= nums.length <= 104 0 <= nums[i] <= 1000 题目保证可以到达 nums[n-1] 解题思路与题解 题目中明确告诉们可以到 nums[n-1] 的位置，所以我们不需要...

跳跃游戏I 题解题目详情 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。 示例 1： 输入：nums = [2,3,1,1,4]输出：true解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。 示例 2： 输入：nums = [3,2,1,0,4]输出：false解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。 提示： 1 <= nums.length <= 104 0 <= nums[i] <= 105 题解题目重要内容解析： 首先，我们要注意，题干中的 你最初位于数组的 第一个下标 和 可以跳跃的最大长度，这句话非常关键，也就是说，我们在一个数组中，我们首先会跳到 nums[0] 对应的值的 对应的下标，也就是说我们最开始其实是位于 nums[nums[0...

买卖股票的最佳时机II 题解题目详情 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。 返回 你能获得的 最大 利润 。 示例 1： 输入：prices = [7,1,5,3,6,4]输出：7解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。 示例 2： 输入：prices = [1,2,3,4,5]输出：4解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这...

买卖股票的最佳时机I 题解题目详情 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 示例 1： 输入：[7,1,5,3,6,4]输出：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2： 输入：prices = [7,6,4,3,1]输出：0解释：在这种情况下, 没有交易完成, 所以最大利润为 0。 提示： 1 <= prices.length <= 105 0 <= prices[i] <= 104 题解 题目重要内容解析： 只能进行一次买卖 首先我们...

轮转数组 的题解题目详情 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 示例 1: 123456输入: nums = [1,2,3,4,5,6,7], k = 3输出: [5,6,7,1,2,3,4]解释:向右轮转 1 步: [7,1,2,3,4,5,6]向右轮转 2 步: [6,7,1,2,3,4,5]向右轮转 3 步: [5,6,7,1,2,3,4] 示例 2: 12345输入：nums = [-1,-100,3,99], k = 2输出：[3,99,-1,-100]解释: 向右轮转 1 步: [99,-1,-100,3]向右轮转 2 步: [3,99,-1,-100] 提示： 1 <= nums.length <= 105 -231 <= nums[i] <= 231 - 1 0 <= k <= 105 进阶： 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？ 首先暴力求解法1234567891011...

多数元素 题解题目详情 点击跳转->多数元素 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1： 输入：nums = [3,2,3]输出：3 示例 2： 输入：nums = [2,2,1,1,1,2,2]输出：2 提示： n == nums.length 1 <= n <= 5 * 104 -109 <= nums[i] <= 109 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。 解题思路与题解 思考过程： 在看到题干时，我们很容易想到的是，我们维护一个Map，然后Map的泛型为 <value,count> 然后遍历数组，并将值存入map中，最后判断哪一个value的count大于数组长度的一半，于是就有了如下解法 12345678910111213141516171819public static int majorityE...

删除有序数组中的重复项II 的题解题目详情 给你一个有序数组 nums ，请你 原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用O(1) 额外空间的条件下完成。 说明： 为什么返回数值是整数，但输出的答案是数组呢？ 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下: 12345678// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝int len = removeDuplicates(nums);// 在函数里修改输入数组对于调用者是可见的。// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。for (int i = 0; i < len; i++) { print(nums[i]);} 示例 1： 123输入：nums = [1,1,1,2,2,3]输出：5, nums = [1,1,2,2,3]解释：函数应返回新长度 length = ...