43. 字符串相乘

题目描述 给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。 示例 1: 输入: num1 = “2”, num2 = “3” 输出: “6” 示例 2: 输入: num1 = “123”, num2 = “456” 输出: “56088” 说明: num1 和 num2 的长度小于110。 num1 和 num2 只包含数字 0-9。 num1 和 num2 均不以零开头,除非是数字 0 本身。 不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理。 https://leetcode-cn.com/problems/multiply-strings/ 解法1 首先, 我们观察示例2中123*456的竖式计算过程, 用乘数456的每一位与被乘数123相乘, 得到的乘积依次向左“移位”、相加. 123*6的乘积为738, 向左移动0位. 123*5的乘积为615, 向左移动1位. 123*4的乘积位492, 向左移动2位. 然后我们将这三个被向左移动了0位、1位、2位的数相加, 就模拟了乘法的过程.观察123*456竖式         1 2 3    x   4…

Read more

23. 合并K个排序链表

题目描述 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [   1->4->5,   1->3->4,   2->6 ] 输出: 1->1->2->3->4->4->5->6 https://leetcode-cn.com/problems/merge-k-sorted-lists/ 解法1 题目要求合并K个有序链表, 我们不妨先考虑合并两个有序链表. 为了便于操作, 我们创建一个头节点head, 该节点的value字段没有意义. 待合并的两个链表分别记为l1与l2, 为了保持合并后的链表仍然有序, 我们每次都从l1与l2中挑选当前最小的节点, 然后将其插入到头节点head. 现有链表l1, l2, 头节点head p = head if (l1.val < l2.val) { // 选取l1, l2当前最小的节点 p.next = l1; l1 = l1.next; } else { p.next = l2; l2 = l2.next; }…

Read more

16. 最接近的三数之和

题目描述 给定一个包括 n 个整数的数组 nums和 一个目标值 target。找出 nums中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 例如,给定数组 nums = [-1,2,1,-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2). https://leetcode-cn.com/problems/3sum-closest/ 解法1 这道题目与三数之和非常相似, 不同之处在于本题要求解的是最接近目标值的三数之和而不要求三数之和为0. 另一个不同点是, 题目给定的输入能保证只存在唯一答案. 我们还是使用“三数之和”解法1的做法, 首先将数组nums排序,以降低内层循环的时间复杂度. 变量i依次访问数组nums的每个元素, 作为外层循环. 内层循环中, 我们用j, k指针分别指向i之后数组的两端. 我们将nums[i]+nums[j]+nums[k]与target之差的绝对值记为diff, diff的初值为Integer.MAX_VALUE. 如果nums[i]+nums[j]+nums[k]与target之差的绝对值小于diff, 则更新diff. 题目要求nums[i]+nums[j]+nums[k]的和, 那么我们除了记录diff之外, 还应该记录与diff对应的三个数之和, 我们计作threeSum. 现在我们分析下如何维护变量j与k. 如果三个数之和小于target, 那么说明我们要找更大的数才能使三数之和更接近target, 所以j自增1. 如果三数之和大于target, 说明我们从右边选的数太大了, 应该k自减1. 如果三数之和与target相等, 那么三数之和与target的差距是0, 这是最接近target的情况了. 注意, 如果遇到这种情况,…

Read more

15. 三数之和

题目描述 给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。 注意:答案中不可以包含重复的三元组。 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ] https://leetcode-cn.com/problems/3sum/ 解法1 首先对原数组nums进行排序, 用指针i指向nums的每个元素, 然后另指针j=i+1, k=|nums|-1. 指针j与k相向而行, 直到nums[i]+nums[j]+nums[k] == 0我们就找到了一个解, 此时需要继续相向而行直到k>=j. 将数组排序可以把算法的时间复杂度降低到O(n^2). 若不对数组排序, 为了寻找j, k使得nums[i]+nums[j]+nums[k] == 0, 需要使用双重循环遍历nums, 这样会使复杂度达到O(n^3). 因为题目要求“不可以包含重复的三元组”, 这就需要我们一旦找到符合条件的i, j, k. 就需要跳过nums中相同的元素(代码中被标记的部分), 以避免寻找重复的解. 例如…

Read more

9. 回文数

题目描述 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 示例 1: 输入: 121 输出: true 示例 2: 输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3: 输入: 10 输出: false 解释: 从右向左读, 为 01 。因此它不是一个回文数。进阶:你能不将整数转为字符串来解决这个问题吗? https://leetcode-cn.com/problems/palindrome-number/ 解法 我们按照进阶的要求,不将整数转化为字符串。代码模板中,变量x是int类型的。那么,将其反转结果使用long类型存放是不会溢出的。题目提到了一个case为“-121”,逆序读“121-”不是回文串。那么我们就可以推测,负数一定不是回文数。 我们按照“7.整数反转”这道题的技巧,判断反转后的数字与原数字是否一致来判定是否为回文数字即可。

Read more

7. 整数反转

题目描述 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例 1: 输入: 123 输出: 321  示例 2: 输入: -123 输出: -321 示例 3: 输入: 120 输出: 21 注意: 假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231,  231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。 https://leetcode-cn.com/problems/reverse-integer/ 解法 首先说明一点,如果直接转成StringBuffer,然后reverse以下再转成int就没意思了。我们尽可能不要使用这种straightforward的方法去做,才能够学到东西。 变量x存放了要被反转的数字,假设x=123.我们让x对10取余就能获得末尾数字,然后再另x=x/10,直到x为0. 例如:123%10==3,123->12; 12%10==2, 12->1; 1%10==1, 1->0循环结束。让我们对取过来对数字3、2、1记为n,分别带入公式result = result*10 + n,其中result初值为0。列如:分别带入3、2、1,0*10+3==3;3*10+2==32;32*10+1==321。 这样,我们通过一次循环就能逆序取出x的各位数字,然后带入result = result*10 + n就能得到逆序后的数字。还有一点是,题目要求发生溢出返回0。为了能够判定溢出,我们就要用比int范围更广的类型来存储逆序后的结果。每次循环,都要判定result变量是否小于Integer.MIN_VALUE或大于Integer.MAX_VALUE。

Read more

8. 字符串转换整数 (atoi)

请你来实现一个 atoi 函数,使其能将字符串转换成整数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。 当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。 该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。 注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。 在任何情况下,若函数不能进行有效的转换时,请返回 0。 说明: 假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围,请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。 示例 1: 输入: “42” 输出: 42 示例 2: 输入: ” -42″ 输出: -42 解释: 第一个非空白字符为 ‘-‘, 它是一个负号。   我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -42 。 示例 3: 输入: “4193 with words” 输出: 4193 解释: 转换截止于数字 ‘3’ ,因为它的下一个字符不为数字。 示例 4: 输入: “words and 987” 输出:…

Read more

最长公共子串

在计算机科学中,最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的,而子串却必须是。 https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E4%B8%B2 解法1 – 动态规划 Wiki中提到要寻找最长公共子串,可以在两个字符串中所有的前缀组合中寻找最长的公共后缀。 例如:S1=”ABAB”, S2=”BABA”。那么S1与S2的所有前缀组合有(A, B) (A, BA) (A, BAB), (A, BABA), …, (ABAB, BABA)。我们可以使用一个矩阵来描述所有前缀的组合,表头代表两个字符串,表中的数值代表两个前缀的最长后缀。表头中的双引号代表空串,因为空串是任何字符串的前缀。 “” A B A B “” 0 0 0 0 0 B 0 0 1 0 1 A 0 1 0 2 0 B 0 0 2 0 3 A 0 1 0 3 0 我们很容易我们可以填好S1或S2只取一个字符后与另一个字符串的最长公共后缀,如果相同则填1,不同填0。那么如果S1或S2取两个字符与另一个字符串的最长公共后缀怎么求呢?我们可以看两个前缀最后一个字符,如果不相同那么该位置肯定是0,因为公共子串要求相同的字符连续。如果两个前缀最后一个字符相同,我们再对两个前缀各往回看一个字符,也就是该位置的斜上方。我们用斜上方的数值+1填入矩阵即可。 总结成公式也就是:…

Read more

5. 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2: 输入: “cbbd” 输出: “bb” https://leetcode-cn.com/problems/longest-palindromic-substring/ 解法1 暴力法很容易想到,我们使用双层循环固定字串的起止位置,然后对字串判断是否为回文串。双层循环的时间复杂度是O(n^2),再嵌套一个回文判断循环O(n),时间复杂度为O(n^3)。但是这里,我们不打算使用暴力法,因为很容易想到,码代码就好了。 我们在这里使用了一种方法,我称之为中心扩展法,那么我们先来定义中心。中心是由单个字符或连续多个相同的字符组成的子串。我们第一次扫描,找到字符串所有的中心。然后遍历每个中心的左右两边的字符,如果相同就继续扩展直到遇到边界或两边字符不同,这样我们就找到了一个回文串。题目要求最长回文串,我们就遍历每个中心,都做相同的扩展操作,选取找到的最长的回文串既是答案。需要特殊注意的是,中心本身也是回文串,也是潜在的答案。 代码中我们使用List<int[]>来存放找到的中心列表,int[0]与int[1]分别是中心的起止索引,都是闭区间。 解法2 方法分析 解法1是我自己想的,解法2、3都是源于LeetCode官方题解。解法2首先对字符串s逆序(reverse),记为s’。我们对字符串s与s’求最长公共子串。 例如,s=”acbcd”, s’=”dcbca”。求s与s’的最长公共子串为”cbc”,在这个例子中,这样的方法成功的求出了答案。我们再举一个例子,s=”abcdxydcba”, s’=”abcdyxdcba”。s与s’的最长公共子串是”abcd”,这显然不是回文子串。 问题出在哪呢?LeetCode题解说道“当s的其他部分中存在非回文子串的反向副本时,最长公共子串法就会失败”。我们来分析下,正是因为s中存在了非回文子串的反向副本,导致非回文子串出现在s’中。我们对s与s’求最长公共子串,也就把非回文子串取了出来。 举例分析:s=”[abcd]xy[dcba]”, s’=”[abcd]yx[dcba]”。s中第一个括号是[abcd],他的反向副本[dcba]同样在s中出现了。我们观察s中第二个中括号[dcba],在对s进行逆序操作后跑到了s’中第一个括号中。这样,我们对s与s’求最长公共子串就得到了错误的”abcd”。 那我们如何修正这样对情况,使得这个方法正确呢?我们只需要确保找到的最长公共子串的索引(indexOf)与最长公共子串的逆序的索引相同,就能保证找到的子串是反向的。(我认为这与判断找到的最长公共子串是否是回文串的条件是等价的,不对的话望指正) 作者疑问 还有一个问题,真的只需要寻找最长公共子串,并且确定最长公共子串的索引与其逆序的索引相同就够了吗? 例如 s=”abacdfgdcaba”, s’=”abacdgfdcaba”。s与s’的最长公共子串为abacd,但其在s中的索引与其反向索引不同,一个是0,一个是7,所以该子串不是最长回文子串。可是,方法二所说的求s与s’的最长公共子串可只有一个啊,接下来没法玩了啊!!!。 那该方法说的是不是不准确啊,应该找出s与s’所有的公共子串,然后所有公共子串的索引与其逆序的索引是否相同。这么做不就和暴力法差不多了吗?暴力法是找到s所有的子串判断是否为回文串。这个方法是找到s与s’所有的公共子串,判断索引与其逆序的索引是否相同。 代码 好吧,带着疑问写代码。我的做法是求出s与s’所有的公共子串,然后求其索引与反向索引是否相同。运行了几个case答案是正确的,但是粘贴到LeetCode提示超时。这个方法不太可取,创建了大量的临时变量,还包含递归函数。 解法3 解法三使用动态规划,这个方法源自LeetCode官方题解。 状态转移方程:P(i, j) = S[i] == S[j] and P(i + 1, j – 1)…

Read more

6. Z 字形变换

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时,排列如下: L C I R E T O E S I I G E D H N 之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:”LCIRETOESIIGEDHN”。 请你实现这个将字符串进行指定行数变换的函数: string convert(string s, int numRows); 示例 1: 输入: s = “LEETCODEISHIRING”, numRows = 3 输出: “LCIRETOESIIGEDHN” 示例 2: 输入: s = “LEETCODEISHIRING”, numRows = 4 输出: “LDREOEIIECIHNTSG” 解释: L D R E O E I I…

Read more