Moon

题目描述 题目链接 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 1234示例 1：输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4] 1234示例 2：输入：l1 = [], l2 = []输出：[] 1234示例 3：输入：l1 = [], l2 = [0]输出：[0] 算法1 归并思路 O(n+m)O(n + m)O(n+m) 1234567891011121314151617181920212223242526272829303132/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNod ...

题目描述 题目链接 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。 1234示例 1：输入：head = [1,2,3,4]输出：[2,1,4,3] 1234示例 2：输入：head = []输出：[] 1234示例 3：输入：head = [1]输出：[1] 算法1 遍历一次 时间：O(n)O(n)O(n) 空间：O(1)O(1)O(1) 思路： 借助 dummy 节点，完成以两个节点为一组的节点交换 12345678910111213141516171819202122232425262728293031/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nul ...

题目描述 题目链接 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。 1234示例 1:输入: num1 = "2", num2 = "3"输出: "6" 1234示例 2:输入: num1 = "123", num2 = "456"输出: "56088" 算法1 (高精度乘法) O(n2)O(n^2)O(n2) 思路： 首先按照低位 --> 高位的顺序将字符串的每一位转化为 int 后，存入vector中 可以发现， 两个数组相应位置的乘积之和就是最终答案位置之和处位置的答案 依照此规律将所得数据存好，并去除前导零，输出答案即可 123456789101112131415161718192021222324252627282930313233class Solution {public: ...

题目描述 题目链接 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。 1234示例 1：输入：x = 4输出：2 12345示例 2：输入：x = 8输出：2解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。 算法1 (暴力枚举) O(n)O(n)O(n) 可以从大到小枚举 小于 x 的数字 i， 直到 i * i 小于等于 x 为止，即为我们的要找的答案 但是这种枚举的方式当 x 很大时，容易超时，因此需要进一步优化 (二分查找) O(logn)O(logn)O(logn) 可以考虑单调性，由于从 1 ~ x ，所有的数字都是递增的，因此他们的平方也是递增的，所以具有单调性，可以使用二分查找的方式每次缩小一半的查找方式，因此可以达到 O(logn)O(logn)O(logn) 的时间复杂度 1234567891011121314class Solution { ...

题目描述 题目链接 给你一个字符串 s，找到 s 中最长的回文子串。 12345示例 1：输入：s = "babad"输出："bab"解释："aba" 同样是符合题意的答案。 1234示例 2：输入：s = "cbbd"输出："bb" 算法1 (暴力枚举) O(n2)O(n^2)O(n2) 对于整个字符串，可以有 n 个起点， 每个起点又有 n 个终点，所以枚举所有的情况并找到长度最长的回文子串，复杂度为 O(n2)O(n^2)O(n2) (枚举中心点 + 双指针) 可以考虑这么思考： 我们每次枚举的不是子串的起点，而是子串的中心点，那么我们只需要分为如下两种情况 子串的长度为奇数：那么我们枚举的就是中心点，在整个回文子串中，中心点的字符是不需要满足回文条件的，所以只需要向两边扩展，每次比较边界处的两个字符是否相同，若相同那么回文子串可以继续增长； 子串的长度为偶数：那么需要将中心点纳入回文的条件中对比，每次向边界扩展 最终，我们取两种情况中的最长者，即可得到最长的回文子串 123 ...

题目描述 题目链接 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。 123456示例 1：输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3输出：[1,2,2,3,5,6]解释：需要合并 [1,2,3] 和 [2,5,6] 。合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。 123456示例 2：输入：nums1 = [1], m = 1, nums2 = [], n = 0输出：[1]解释：需要合并 [1] 和 [] 。合并结果是 [1] 。 1234567示例 3：输入：nums1 ...

题目描述 题目链接 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 样例 1234示例 1:输入: [3,2,1,5,6,4] 和 k = 2输出: 5 1234示例 2:输入: [3,2,3,1,2,4,5,5,6] 和 k = 4输出: 4 算法1 (排序) O(nlogn)O(nlogn)O(nlogn) 最直观的思路是先排序然后选择，那么无论使用什么排序方法最快都是O(nlogn)O(nlogn)O(nlogn)的时间复杂度，代码如下 123456789101112131415161718192021222324252627282930313233class Solution {public: int findKthLargest(vector<int>& nums, int k) { int n = nums.size(); quick_sort(nums, 0, n - 1); ...

题目描述 题目链接 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 样例 1234示例 1：输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 1234示例 2：输入：nums = [0]输出：[[],[0]] 算法1 (递归搜索) O(n⋅2n)O(n·2^n)O(n⋅2n) 针对数组中的每一个数字，都有两种选择方案：选这个数或不选这个数 那么我们从第 i = 0 位开始枚举 nums 中的所有数字，当我们枚举至 i = n 时，说明所有的情况都已经枚举结束，返回当前的选择 C++ 代码 123456789101112131415161718192021222324252627282930class Solution {public: vector<vector<int>> res; vector<int> path; vector<b ...

题目描述题目链接 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn ）。 样例1234示例 1：输入：x = 2.00000, n = 10输出：1024.00000 1234示例 2：输入：x = 2.10000, n = 3输出：9.26100 12345示例 3：输入：x = 2.00000, n = -2输出：0.25000解释：2-2 = 1/22 = 1/4 = 0.25 算法1(快速幂) $O(logn)$如果每次乘以一个 x 来求 x 的 n 次幂的话，那么需要线性的时间，当 n 特别大时，明显效率过低，因此可以二进制的思想将 n 预处理 思路： 借助二进制的思想， n 的二进制表示就表明了 n 可以由 2 的多少次幂组成，那么我们可以预处理 $2^0, 2^1, 2^2 …. $ 整体的时间复杂度将会缩减至 $logn$ C++ 代码123456789101112131415161718class Solution {public: double myPow(double x, int n) { t ...

题目描述 题目链接 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组 是数组中的一个连续部分。 样例 12345示例 1：输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 1234示例 2： 输入：nums = [1]输出：1 1234示例 3：输入：nums ...