目录

AaronJny

诗酒繁华,书剑天涯。

标签: leetcode (9)

leetcode题解第29题 Divide Two Integers (两数相除)

题目的大意如下: 给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。 简单来说,就是需要在不借助 python 内部的乘、除、去余运算的情况下,实现整数除法运算,并返回运算的商的。余数忽略。 且在此之外,还有几点额外说明: 除数永远不会为 0。 被除数和除数都是 32 位有符号整数。 假设计算机只能存储 32 位有符号整数,所以你返回的结果应该在 [−2^{31}, 2^{31} − 1]范围内,否则就返回 2^{31} − 1。 样例输入 1: dividend = 10, divisor = 3 样例输出 1: 3 样例输入 2: dividend = 7, divisor = -3 样例输出 2: -2 如果不借助语言内置的乘除法,应该怎么做除法运算呢? 一个最简单的方法是——不停累加除数,直到它大于被除数为止。这时,累加的次数-1 就是商。 这个方法看起来很美好,但是当被除数很大,而除数很小时,按这个方法就需要计算非常多次,时间复....

leetcode题解第24题 Swap Nodes in Pairs (两两交换链表中的节点)

题外话:之前说了写了代码也不一定会写题解,因为懒,然后我就真的没写……题目断断续续坚持在做,这代码都是好早之前写的了,题解嘛……果然,我就是个鸽子,咕咕咕。 反正你们应该也不需要我的题解,毕竟网上那么多,我就写着做个纪念。 好了,说正题。题目的大意是: 给定一个链表,你需要两两交换其中相邻的节点,并返回交换后的链表。但是你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 样例输入: 1->2->3->4 样例输出: 2->1->4->3 从示例可以看出,第一个节点和第二个节点做了交换,第三个节点和第四个节点做了交换。 leetcode 中的 python 链表是这样定义的: class ListNode: def __init__(self, x): self.val = x self.next = None 这就是一个简单的模拟题,直接上代码吧,注释很详细: class Solution: def swapPairs(self, head: ListNode) -> ListNode: """ 两两交换给定链表的节....

leetcode题解第23题 Merge k Sorted Lists(合并K个排序链表)

题目大意如下: 给定 k 个有序链表,请将这 k 个列表合并成一个有序链表,然后返回这个有序列表的头结点。 在 python 中,链表被这样实现: # Definition for singly-linked list. class ListNode: def __init__(self, x): self.val = x self.next = None 样例输入: [ 1->4->5, 1->3->4, 2->6 ] 样例输出: 1->1->2->3->4->4->5->6 题目链接:https://leetcode.com/problems/merge-k-sorted-lists 解题思路: 这道题考察的是链表的操作和归并排序,只不过这里做的是多个列表的归并。 输入是一个链表头结点组成的列表,我们需要创建一个指向这些链表头结点的指针构成的列表,和一个结果链表。 比较所有指针对应的值的大小,获取最小的节点的值,创建新节点,加入到结果链表中。然后将指向最小节点的指针后移一位。当一个指针走到头时,这....

leetcode题解第22题 Generate Parentheses(括号生成)

题目的大意如下: 给定一个整数 n,代表括号的对数,请给出所有合法的括号组合。 样例输入: 3 样例输出: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] 题目链接:https://leetcode.com/problems/generate-parentheses/ 解题思路: 生成 n 对括号,通过递归可以很轻松实现,问题的关键在于,什么样的生成式是正确的。 观察可以发现,合法的括号组合有如下特征: 假设 s 是一个合法的括号组合,则在 s 的任意位置,左边的左括号的数量一定大于等于右括号的数量。 emmm,大家可以举几个例子看一下,都是满足的。那么,在满足特征的情况下,使用递归生成所有组合方式即可。 样例代码: class Solution: # 最终的结果集 result = set() # 用于临时存储递归生成的一种合法组合的列表 curstring = [] def dfs(self, leftcnt, rightcnt): """ 递归搜索所有可能的合法组合,并加入到结果集中 :param le....

leetcode题解第19题 Remove Nth Node From End of List(删除链表的倒数第N个节点)

考查列表操作的一道题,题目大意如下: 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 样例输入: head = 1->2->3->4->5 n = 2 样例输出: 1->2->3->5 题目链接:https://leetcode.com/problems/remove-nth-node-from-end-of-list/ emmmm,题目相当简单,所以本来没打算写的,不过交了一发,时间击败了 100% python 代码,有点特别意义,就简单说一下吧。 解题思路: 我的想法很简单,先利用指针遍历一下链表,计算链表的长度 length。 然后从头开始,将指针移动到 length-n-1 的位置,改变一下节点的 Next 的值就行了。 样例代码: class Solution(object): def list_len(self, head): """ 计算给定链表的长度 :param head: :return: """ tmp_head = head cnt = 0 while tmp_head: cn....

leetcode题解第18题 4Sum(四数之和)

跟第 15 题、第 16 题比较相似的一道题,题目大意是说: 给定一个包含 n 个整数的数组 nums 和一个整数 target,从数组中找出所有不重复的四个数相加等于 0 的组合。 注意,仅字典序不同的、包含数字相同的四元组被认为是重复的,只能保留其中一个。 样例输入: nums = [1, 0, -1, 0, -2, 2] target = 0 样例输出: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ] 题目链接:https://leetcode.com/problems/4sum/ 解题思路: 最简单的思路当然是四层循环啦,但不用试,估计也会爆炸 =。= 怎么优化呢?对,还是二分,这几道题一直在考二分 orz... 总共 n 个数,我们可以把它们两两相加,产生一个新的列表。且列表中的每个元素不止保存两个数的和,还要保存这两个数的下标,可以通过类(python)或结构体(c/c++)来实现。 新的列表我们给它起个名字,比方说就叫 sumnums。对 sumnums 进行排序,方便后面使用二分查找。 枚举 sumnums....

leetcode第17题 Letter Combinations of a Phone Number(电话号码的字母组合)

比较简单,直接深搜 + 回溯就能够解决的问题。题目的大意是: 给定一个只包含 2-9 的字符串,按照手机按键的映射关系,将它转化为一个只包含 a-z 的字符串,输出这种所有可能的转换字符串。 数字到小写字母的映射关系可以表示如下: digits_chr_map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz', } 样例输入: "23" 样例输出: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] 题目链接:https://leetcode.com/problems/letter-combinations-of-a-phone-number/ 思路很简单,直接深搜 + 回溯就可以了,所以就不多说了,直接看代码吧,注释比较详细(python3): class Solution: # 存放所有可能的字符串的列表 combinations = [] # 数字到字母的映射....

leetcode第16题 3Sum Closest(最接近的三数之和)

这道题也比较简单,只是在第 15 题上加了一些变化。题目的大概意思是说: 给定一个长度为 n 的整数数组 nums 和一个整数 target,需要你从数组中找出三个数字,这三个数字相加的和与 target 最接近,返回这三个数字的和。 样例输入: nums = [-1,2,1,-4] target = 1 样例输出: 2 (-1 + 2 + 1 = 2) 题目链接:https://leetcode.com/problems/3sum-closest/ 相比较于第 15 题,大概有三个地方不同: 第 15 题里 target 固定为 0,这里的 target 是变化的 第 15 题里三个数相加必须等于 target,即假设三个数的和为 x,第 15 题要求 target-x==0,本题要求 abs(target-x)最小。 第 15 题要求返回所有满足条件的三个数的组合,而本题要求返回 abs(target-x)最小时的 x。 那么,可以借鉴第 15 题的思路,来解决这个问题。 解题思路: 首先,为数组排序。 实现一个二分查找算法,当查找成功时,返回给定值所在的坐标,不....

leetcode第15题 3Sum(三数之和)

比较简单的一道题,题目的大意是说: 给定一个长度为 n 的整数数组 nums,从数组中找出所有不重复的 (三个数相加等于 0 的组合)。 注意,仅字典序不同的、包含数字相同的三元组被认为是重复的,如(1,-1,0)和(0,1,,-1)被认为是重复的,只能保留其中一个。 样例输入: [-1, 0, 1, 2, -1, -4] 样例输出: [ [-1, 0, 1], [-1, -1, 2] ] 输出不一定要和样例输出完全一样(组合的字典序问题),但必须包含所有可能的组合。 题目链接:https://leetcode.com/problems/3sum/ 解题思路: 首先,最暴力的解法,直接三层循环,o(n^3)解决问题,这种方法很容易想到。时间复杂度太高了,我没交这种方法,不知道会不会超时。 怎么优化呢?可以用二分查找来做。 先对数组进行排序,使用内置的排序方法,时间复杂度认为在 O(nlogn)级别。 既然是要找三个数的和为 0 的组合,那么,当前两个数确定了之后,第三个符合条件的数就确定了。这样,我们可以枚举前两个数,然后再在数组中使用二分查找搜索第三个数。时间复杂度可以....