资阳网站设计,做网站干什么,生成短网址的平台,来几个好看的网站Leetcode: 0011-0020题速览 本文材料来自于LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer#xff08;第 2 版#xff09;》、《程序员面试金典#xff08;第 6 版#xff09;》题解 遵从开源协议为知识共享 版权归属-相同方式…Leetcode: 0011-0020题速览 本文材料来自于LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解 遵从开源协议为知识共享 版权归属-相同方式共享 4.0 国际 公共许可证 研一在读备战就业制此集合便于空闲时间浏览有任何疑惑问题欢迎讨论共同进步 目录 Leetcode: 0011-0020题速览[11. 盛最多水的容器](https://leetcode.cn/problems/container-with-most-water)题目描述解法方法一双指针Python3JavaC [12. 整数转罗马数字](https://leetcode.cn/problems/integer-to-roman)题目描述解法方法一贪心Python3JavaC [13. 罗马数字转整数](https://leetcode.cn/problems/roman-to-integer)题目描述解法方法一哈希表 模拟Python3JavaC [14. 最长公共前缀](https://leetcode.cn/problems/longest-common-prefix)题目描述解法方法一字符比较Python3JavaC [15. 三数之和](https://leetcode.cn/problems/3sum)题目描述解法方法一排序 双指针Python3JavaC [16. 最接近的三数之和](https://leetcode.cn/problems/3sum-closest)题目描述解法方法一排序 双指针Python3JavaC [17. 电话号码的字母组合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number)题目描述解法方法一遍历Python3JavaC [18. 四数之和](https://leetcode.cn/problems/4sum)题目描述解法方法一排序 双指针Python3JavaC [19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list)题目描述解法方法一快慢指针Python3JavaC [20. 有效的括号](https://leetcode.cn/problems/valid-parentheses)题目描述解法方法一栈Python3JavaC 11. 盛最多水的容器
题目描述 给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。 示例 1 输入[1,8,6,2,5,4,8,3,7] 输出49 解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。
示例 2
输入height [1,1] 输出1 提示
n height.length2 n 1050 height[i] 104
难度中等
标签贪心,数组,双指针 解法 方法一双指针
一开始我们考虑相距最远的两个柱子所能容纳水的容量。水的宽度是两根柱子之间的距离而水的高度取决于两根柱子之间较短的那个。
当前柱子是最两侧的柱子水的宽度最大其他的组合水的宽度都比这个小。不妨假设左侧柱子的高度小于等于右侧柱子的高度那么水的高度就是左侧柱子的高度。如果我们移动右侧柱子那么水的宽度就减小了而水的高度却不会增加因此水的容量一定减少。所以我们移动左侧柱子更新最大容量。
循环此过程直到两个柱子相遇。
时间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组 height 的长度。空间复杂度 O ( 1 ) O(1) O(1)。 Python3
class Solution:def maxArea(self, height: List[int]) - int:i, j 0, len(height) - 1ans 0while i j:t (j - i) * min(height[i], height[j])ans max(ans, t)if height[i] height[j]:i 1else:j - 1return ansJava
class Solution {public int maxArea(int[] height) {int i 0, j height.length - 1;int ans 0;while (i j) {int t Math.min(height[i], height[j]) * (j - i);ans Math.max(ans, t);if (height[i] height[j]) {i;} else {--j;}}return ans;}
}C
class Solution {
public:int maxArea(vectorint height) {int i 0, j height.size() - 1;int ans 0;while (i j) {int t min(height[i], height[j]) * (j - i);ans max(ans, t);if (height[i] height[j]) {i;} else {--j;}}return ans;}
};12. 整数转罗马数字
题目描述 七个不同的符号代表罗马数字其值如下
符号值I1V5X10L50C100D500M1000
罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则
如果该值不是以 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 3749 输出 MMMDCCXLIX
解释
3000 MMM 由于 1000 (M) 1000 (M) 1000 (M) 700 DCC 由于 500 (D) 100 © 100 © 40 XL 由于 50 (L) 减 10 (X) 9 IX 由于 10 (X) 减 1 (I) 注意49 不是 50 (L) 减 1 (I) 因为转换是基于小数位
示例 2 输入num 58 输出LVIII
解释
50 L 8 VIII
示例 3 输入num 1994 输出MCMXCIV
解释
1000 M 900 CM 90 XC 4 IV 提示
1 num 3999
难度中等
标签哈希表,数学,字符串 解法 方法一贪心
我们可以先将所有可能的符号 c s cs cs 和对应的数值 v s vs vs 列出来然后从大到小枚举每个数值 v s [ i ] vs[i] vs[i]每次尽可能多地使用该数值对应的符号 c s [ i ] cs[i] cs[i]直到数字 n u m num num 变为 0 0 0。
时间复杂度为 O ( m ) O(m) O(m)空间复杂度为 O ( m ) O(m) O(m)。其中 m m m 为符号的个数。 Python3
class Solution:def intToRoman(self, num: int) - str:cs (M, CM, D, CD, C, XC, L, XL, X, IX, V, IV, I)vs (1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)ans []for c, v in zip(cs, vs):while num v:num - vans.append(c)return .join(ans)Java
class Solution {public String intToRoman(int num) {ListString cs List.of(M, CM, D, CD, C, XC, L, XL, X, IX, V, IV, I);ListInteger vs List.of(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1);StringBuilder ans new StringBuilder();for (int i 0, n cs.size(); i n; i) {while (num vs.get(i)) {num - vs.get(i);ans.append(cs.get(i));}}return ans.toString();}
}C
class Solution {
public:string intToRoman(int num) {vectorstring cs {M, CM, D, CD, C, XC, L, XL, X, IX, V, IV, I};vectorint vs {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};string ans;for (int i 0; i cs.size(); i) {while (num vs[i]) {num - vs[i];ans cs[i];}}return ans;}
};13. 罗马数字转整数
题目描述 罗马数字包含以下七种字符: I V X LCD 和 M。
字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 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) 的左边来表示 400 和 900。
给定一个罗马数字将其转换成整数。 示例 1:
输入: s “III” 输出: 3
示例 2:
输入: s “IV” 输出: 4
示例 3:
输入: s “IX” 输出: 9
示例 4:
输入: s “LVIII” 输出: 58 解释: L 50, V 5, III 3.
示例 5:
输入: s “MCMXCIV” 输出: 1994 解释: M 1000, CM 900, XC 90, IV 4. 提示
1 s.length 15s 仅含字符 (I, V, X, L, C, D, M)题目数据保证 s 是一个有效的罗马数字且表示整数在范围 [1, 3999] 内题目所给测试用例皆符合罗马数字书写规则不会出现跨位等情况。IL 和 IM 这样的例子并不符合题目要求49 应该写作 XLIX999 应该写作 CMXCIX 。关于罗马数字的详尽书写规则可以参考 罗马数字 - 百度百科。
难度简单
标签哈希表,数学,字符串 解法 方法一哈希表 模拟
我们先用哈希表 d d d 记录每个字符对应的数值然后从左到右遍历字符串 s s s如果当前字符对应的数值小于右边字符对应的数值则减去当前字符对应的数值否则加上当前字符对应的数值。
时间复杂度 ( n ) (n) (n)空间复杂度 O ( m ) O(m) O(m)。其中 n n n 和 m m m 分别为字符串 s s s 的长度和字符集的大小。 Python3
class Solution:def romanToInt(self, s: str) - int:d {I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000}return sum((-1 if d[a] d[b] else 1) * d[a] for a, b in pairwise(s)) d[s[-1]]Java
class Solution {public int romanToInt(String s) {String cs IVXLCDM;int[] vs {1, 5, 10, 50, 100, 500, 1000};MapCharacter, Integer d new HashMap();for (int i 0; i vs.length; i) {d.put(cs.charAt(i), vs[i]);}int n s.length();int ans d.get(s.charAt(n - 1));for (int i 0; i n - 1; i) {int sign d.get(s.charAt(i)) d.get(s.charAt(i 1)) ? -1 : 1;ans sign * d.get(s.charAt(i));}return ans;}
}C
class Solution {
public:int romanToInt(string s) {unordered_mapchar, int nums{{I, 1},{V, 5},{X, 10},{L, 50},{C, 100},{D, 500},{M, 1000},};int ans nums[s.back()];for (int i 0; i s.size() - 1; i) {int sign nums[s[i]] nums[s[i 1]] ? -1 : 1;ans sign * nums[s[i]];}return ans;}
};14. 最长公共前缀
题目描述 编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀返回空字符串 。 示例 1
输入strs [“flower”,“flow”,“flight”] 输出“fl”
示例 2
输入strs [“dog”,“racecar”,“car”] 输出“” 解释输入不存在公共前缀。 提示
1 strs.length 2000 strs[i].length 200strs[i] 仅由小写英文字母组成
难度简单
标签字典树,字符串 解法 方法一字符比较
我们以第一个字符串 s t r s [ 0 ] strs[0] strs[0] 为基准依次比较后面的字符串的第 i i i 个字符是否与 s t r s [ 0 ] strs[0] strs[0] 的第 i i i 个字符相同如果相同则继续比较下一个字符否则返回 s t r s [ 0 ] strs[0] strs[0] 的前 i i i 个字符。
遍历结束说明所有字符串的前 i i i 个字符都相同返回 s t r s [ 0 ] strs[0] strs[0] 即可。
时间复杂度 ( n × m ) (n \times m) (n×m)其中 n n n 和 m m m 分别为字符串数组的长度以及字符串的最小长度。空间复杂度 O ( 1 ) O(1) O(1)。 Python3
class Solution:def longestCommonPrefix(self, strs: List[str]) - str:for i in range(len(strs[0])):for s in strs[1:]:if len(s) i or s[i] ! strs[0][i]:return s[:i]return strs[0]Java
class Solution {public String longestCommonPrefix(String[] strs) {int n strs.length;for (int i 0; i strs[0].length(); i) {for (int j 1; j n; j) {if (strs[j].length() i || strs[j].charAt(i) ! strs[0].charAt(i)) {return strs[0].substring(0, i);}}}return strs[0];}
}C
class Solution {
public:string longestCommonPrefix(vectorstring strs) {int n strs.size();for (int i 0; i strs[0].size(); i) {for (int j 1; j n; j) {if (strs[j].size() i || strs[j][i] ! strs[0][i]) {return strs[0].substr(0, i);}}}return strs[0];}
};15. 三数之和
题目描述 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。 示例 1
输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]] 解释 nums[0] nums[1] nums[2] (-1) 0 1 0 。 nums[1] nums[2] nums[4] 0 1 (-1) 0 。 nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意输出的顺序和三元组的顺序并不重要。
示例 2
输入nums [0,1,1] 输出[] 解释唯一可能的三元组和不为 0 。
示例 3
输入nums [0,0,0] 输出[[0,0,0]] 解释唯一可能的三元组和为 0 。 提示
3 nums.length 3000-105 nums[i] 105
难度中等
标签数组,双指针,排序 解法 方法一排序 双指针
我们注意到题目不要求我们按照顺序返回三元组因此我们不妨先对数组进行排序这样就可以方便地跳过重复的元素。
接下来我们枚举三元组的第一个元素 n u m s [ i ] nums[i] nums[i]其中 0 ≤ i n − 2 0 \leq i \lt n - 2 0≤in−2。对于每个 i i i我们可以通过维护两个指针 j i 1 j i 1 ji1 和 k n − 1 k n - 1 kn−1从而找到满足 n u m s [ i ] n u m s [ j ] n u m s [ k ] 0 nums[i] nums[j] nums[k] 0 nums[i]nums[j]nums[k]0 的 j j j 和 k k k。在枚举的过程中我们需要跳过重复的元素以避免出现重复的三元组。
具体判断逻辑如下
如果 i 0 i \gt 0 i0 并且 n u m s [ i ] n u m s [ i − 1 ] nums[i] nums[i - 1] nums[i]nums[i−1]则说明当前枚举的元素与上一个元素相同我们可以直接跳过因为不会产生新的结果。
如果 n u m s [ i ] 0 nums[i] \gt 0 nums[i]0则说明当前枚举的元素大于 0 0 0则三数之和必然无法等于 0 0 0结束枚举。
否则我们令左指针 j i 1 j i 1 ji1右指针 k n − 1 k n - 1 kn−1当 j k j \lt k jk 时执行循环计算三数之和 x n u m s [ i ] n u m s [ j ] n u m s [ k ] x nums[i] nums[j] nums[k] xnums[i]nums[j]nums[k]并与 0 0 0 比较
如果 x 0 x \lt 0 x0则说明 n u m s [ j ] nums[j] nums[j] 太小我们需要将 j j j 右移一位。如果 x 0 x \gt 0 x0则说明 n u m s [ k ] nums[k] nums[k] 太大我们需要将 k k k 左移一位。否则说明我们找到了一个合法的三元组将其加入答案并将 j j j 右移一位将 k k k 左移一位同时跳过所有重复的元素继续寻找下一个合法的三元组。
枚举结束后我们即可得到三元组的答案。
时间复杂度 O ( n 2 ) O(n^2) O(n2)空间复杂度 O ( log n ) O(\log n) O(logn)。其中 n n n 为数组的长度。 Python3
class Solution:def threeSum(self, nums: List[int]) - List[List[int]]:nums.sort()n len(nums)ans []for i in range(n - 2):if nums[i] 0:breakif i and nums[i] nums[i - 1]:continuej, k i 1, n - 1while j k:x nums[i] nums[j] nums[k]if x 0:j 1elif x 0:k - 1else:ans.append([nums[i], nums[j], nums[k]])j, k j 1, k - 1while j k and nums[j] nums[j - 1]:j 1while j k and nums[k] nums[k 1]:k - 1return ansJava
class Solution {public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);ListListInteger ans new ArrayList();int n nums.length;for (int i 0; i n - 2 nums[i] 0; i) {if (i 0 nums[i] nums[i - 1]) {continue;}int j i 1, k n - 1;while (j k) {int x nums[i] nums[j] nums[k];if (x 0) {j;} else if (x 0) {--k;} else {ans.add(List.of(nums[i], nums[j], nums[k--]));while (j k nums[j] nums[j - 1]) {j;}while (j k nums[k] nums[k 1]) {--k;}}}}return ans;}
}C
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(), nums.end());vectorvectorint ans;int n nums.size();for (int i 0; i n - 2 nums[i] 0; i) {if (i nums[i] nums[i - 1]) {continue;}int j i 1, k n - 1;while (j k) {int x nums[i] nums[j] nums[k];if (x 0) {j;} else if (x 0) {--k;} else {ans.push_back({nums[i], nums[j], nums[k--]});while (j k nums[j] nums[j - 1]) {j;}while (j k nums[k] nums[k 1]) {--k;}}}}return ans;}
};16. 最接近的三数之和
题目描述 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。 示例 1
输入nums [-1,2,1,-4], target 1 输出2 解释与 target 最接近的和是 2 (-1 2 1 2)。
示例 2
输入nums [0,0,0], target 1 输出0 解释与 target 最接近的和是 00 0 0 0。 提示
3 nums.length 1000-1000 nums[i] 1000-104 target 104
难度中等
标签数组,双指针,排序 解法 方法一排序 双指针
我们将数组排序然后遍历数组对于每个元素 n u m s [ i ] nums[i] nums[i]我们使用指针 j j j 和 k k k 分别指向 i 1 i1 i1 和 n − 1 n-1 n−1计算三数之和如果三数之和等于 t a r g e t target target则直接返回 t a r g e t target target否则根据与 t a r g e t target target 的差值更新答案。如果三数之和大于 t a r g e t target target则将 k k k 向左移动一位否则将 j j j 向右移动一位。
时间复杂度 O ( n 2 ) O(n^2) O(n2)空间复杂度 O ( log n ) O(\log n) O(logn)。其中 n n n 为数组长度。 Python3
class Solution:def threeSumClosest(self, nums: List[int], target: int) - int:nums.sort()n len(nums)ans inffor i, v in enumerate(nums):j, k i 1, n - 1while j k:t v nums[j] nums[k]if t target:return tif abs(t - target) abs(ans - target):ans tif t target:k - 1else:j 1return ansJava
class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int ans 1 30;int n nums.length;for (int i 0; i n; i) {int j i 1, k n - 1;while (j k) {int t nums[i] nums[j] nums[k];if (t target) {return t;}if (Math.abs(t - target) Math.abs(ans - target)) {ans t;}if (t target) {--k;} else {j;}}}return ans;}
}C
class Solution {
public:int threeSumClosest(vectorint nums, int target) {sort(nums.begin(), nums.end());int ans 1 30;int n nums.size();for (int i 0; i n; i) {int j i 1, k n - 1;while (j k) {int t nums[i] nums[j] nums[k];if (t target) return t;if (abs(t - target) abs(ans - target)) ans t;if (t target)--k;elsej;}}return ans;}
};17. 电话号码的字母组合
题目描述 给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1
输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2
输入digits “” 输出[]
示例 3
输入digits “2” 输出[“a”,“b”,“c”] 提示
0 digits.length 4digits[i] 是范围 [2, 9] 的一个数字。
难度中等
标签哈希表,字符串,回溯 解法 方法一遍历
我们先用一个数组或者哈希表存储每个数字对应的字母然后遍历每个数字将其对应的字母与之前的结果进行组合得到新的结果。
时间复杂度 O ( 4 n ) O(4^n) O(4n)。空间复杂度 O ( 4 n ) O(4^n) O(4n)。其中 n n n 是输入数字的长度。 Python3
class Solution:def letterCombinations(self, digits: str) - List[str]:if not digits:return []d [abc, def, ghi, jkl, mno, pqrs, tuv, wxyz]ans []for i in digits:s d[int(i) - 2]ans [a b for a in ans for b in s]return ansJava
class Solution {public ListString letterCombinations(String digits) {ListString ans new ArrayList();if (digits.length() 0) {return ans;}ans.add();String[] d new String[] {abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};for (char i : digits.toCharArray()) {String s d[i - 2];ListString t new ArrayList();for (String a : ans) {for (String b : s.split()) {t.add(a b);}}ans t;}return ans;}
}C
class Solution {
public:vectorstring letterCombinations(string digits) {if (digits.empty()) {return {};}vectorstring d {abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};vectorstring ans {};for (auto i : digits) {string s d[i - 2];vectorstring t;for (auto a : ans) {for (auto b : s) {t.push_back(a b);}}ans move(t);}return ans;}
};18. 四数之和
题目描述 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target
你可以按 任意顺序 返回答案 。 示例 1
输入nums [1,0,-1,0,-2,2], target 0 输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2
输入nums [2,2,2,2,2], target 8 输出[[2,2,2,2]] 提示
1 nums.length 200-109 nums[i] 109-109 target 109
难度中等
标签数组,双指针,排序 解法 方法一排序 双指针
我们注意到题目中要求找到不重复的四元组那么我们可以先对数组进行排序这样就可以方便地跳过重复的元素。
接下来我们枚举四元组的前两个元素 n u m s [ i ] nums[i] nums[i] 和 n u m s [ j ] nums[j] nums[j]其中 i j i \lt j ij在枚举的过程中我们跳过重复的 n u m s [ i ] nums[i] nums[i] 和 n u m s [ j ] nums[j] nums[j]。然后我们用两个指针 k k k 和 l l l 分别指向 n u m s [ i ] nums[i] nums[i] 和 n u m s [ j ] nums[j] nums[j] 后面的两端令 x n u m s [ i ] n u m s [ j ] n u m s [ k ] n u m s [ l ] x nums[i] nums[j] nums[k] nums[l] xnums[i]nums[j]nums[k]nums[l]我们将 x x x 与 t a r g e t target target 比较进行如下操作
如果 x t a r g e t x \lt target xtarget则更新 k k 1 k k 1 kk1 以得到更大的 x x x如果 x t a r g e t x \gt target xtarget则更新 l l − 1 l l - 1 ll−1 以得到更小的 x x x否则说明找到了一个四元组 ( n u m s [ i ] , n u m s [ j ] , n u m s [ k ] , n u m s [ l ] ) (nums[i], nums[j], nums[k], nums[l]) (nums[i],nums[j],nums[k],nums[l])将其加入答案然后我们更新指针 k k k 和 l l l并跳过所有重复的元素防止答案中包含重复的四元组继续寻找下一个四元组。
时间复杂度为 O ( n 3 ) O(n^3) O(n3)空间复杂度为 O ( log n ) O(\log n) O(logn)其中 n n n 是数组的长度。 Python3
class Solution:def fourSum(self, nums: List[int], target: int) - List[List[int]]:n len(nums)ans []if n 4:return ansnums.sort()for i in range(n - 3):if i and nums[i] nums[i - 1]:continuefor j in range(i 1, n - 2):if j i 1 and nums[j] nums[j - 1]:continuek, l j 1, n - 1while k l:x nums[i] nums[j] nums[k] nums[l]if x target:k 1elif x target:l - 1else:ans.append([nums[i], nums[j], nums[k], nums[l]])k, l k 1, l - 1while k l and nums[k] nums[k - 1]:k 1while k l and nums[l] nums[l 1]:l - 1return ansJava
class Solution {public ListListInteger fourSum(int[] nums, int target) {int n nums.length;ListListInteger ans new ArrayList();if (n 4) {return ans;}Arrays.sort(nums);for (int i 0; i n - 3; i) {if (i 0 nums[i] nums[i - 1]) {continue;}for (int j i 1; j n - 2; j) {if (j i 1 nums[j] nums[j - 1]) {continue;}int k j 1, l n - 1;while (k l) {long x (long) nums[i] nums[j] nums[k] nums[l];if (x target) {k;} else if (x target) {--l;} else {ans.add(List.of(nums[i], nums[j], nums[k], nums[l--]));while (k l nums[k] nums[k - 1]) {k;}while (k l nums[l] nums[l 1]) {--l;}}}}}return ans;}
}C
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {int n nums.size();vectorvectorint ans;if (n 4) {return ans;}sort(nums.begin(), nums.end());for (int i 0; i n - 3; i) {if (i nums[i] nums[i - 1]) {continue;}for (int j i 1; j n - 2; j) {if (j i 1 nums[j] nums[j - 1]) {continue;}int k j 1, l n - 1;while (k l) {long long x (long long) nums[i] nums[j] nums[k] nums[l];if (x target) {k;} else if (x target) {--l;} else {ans.push_back({nums[i], nums[j], nums[k], nums[l--]});while (k l nums[k] nums[k - 1]) {k;}while (k l nums[l] nums[l 1]) {--l;}}}}}return ans;}
};19. 删除链表的倒数第 N 个结点
题目描述 给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。 示例 1 输入head [1,2,3,4,5], n 2 输出[1,2,3,5]
示例 2
输入head [1], n 1 输出[]
示例 3
输入head [1,2], n 1 输出[1] 提示
链表中结点的数目为 sz1 sz 300 Node.val 1001 n sz 进阶你能尝试使用一趟扫描实现吗
难度中等
标签链表,双指针 解法 方法一快慢指针
我们定义两个指针 fast 和 slow初始时都指向链表的虚拟头结点 dummy。
接着 fast 指针先向前移动 n n n 步然后 fast 和 slow 指针同时向前移动直到 fast 指针到达链表的末尾。此时 slow.next 指针指向的结点就是倒数第 n 个结点的前驱结点将其删除即可。
时间复杂度 O ( n ) O(n) O(n)其中 n n n 为链表的长度。空间复杂度 O ( 1 ) O(1) O(1)。 Python3
## Definition for singly-linked list.
## class ListNode:
## def __init__(self, val0, nextNone):
## self.val val
## self.next next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:dummy ListNode(nexthead)fast slow dummyfor _ in range(n):fast fast.nextwhile fast.next:slow, fast slow.next, fast.nextslow.next slow.next.nextreturn dummy.nextJava
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy new ListNode(0, head);ListNode fast dummy, slow dummy;while (n-- 0) {fast fast.next;}while (fast.next ! null) {slow slow.next;fast fast.next;}slow.next slow.next.next;return dummy.next;}
}C
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy new ListNode(0, head);ListNode* fast dummy;ListNode* slow dummy;while (n--) {fast fast-next;}while (fast-next) {slow slow-next;fast fast-next;}slow-next slow-next-next;return dummy-next;}
};20. 有效的括号
题目描述 给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 示例 1 输入s () 输出true
示例 2 输入s ()[]{} 输出true
示例 3 输入s (] 输出false
示例 4 输入s ([]) 输出true 提示
1 s.length 104s 仅由括号 ()[]{} 组成
难度简单
标签栈,字符串 解法 方法一栈
遍历括号字符串 s s s遇到左括号时压入当前的左括号遇到右括号时弹出栈顶元素若栈为空直接返回 false判断是否匹配若不匹配直接返回 false。
也可以选择遇到左括号时将右括号压入栈中遇到右括号时弹出栈顶元素若栈为空直接返回 false判断是否是相等。若不匹配直接返回 false。 两者的区别仅限于括号转换时机一个是在入栈时一个是在出栈时。 遍历结束若栈为空说明括号字符串有效返回 true否则返回 false。
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)。其中 n n n 为括号字符串 s s s 的长度。 Python3
class Solution:def isValid(self, s: str) - bool:stk []d {(), [], {}}for c in s:if c in ({[:stk.append(c)elif not stk or stk.pop() c not in d:return Falsereturn not stkJava
class Solution {public boolean isValid(String s) {DequeCharacter stk new ArrayDeque();for (char c : s.toCharArray()) {if (c ( || c { || c [) {stk.push(c);} else if (stk.isEmpty() || !match(stk.pop(), c)) {return false;}}return stk.isEmpty();}private boolean match(char l, char r) {return (l ( r )) || (l { r }) || (l [ r ]);}
}C
class Solution {
public:bool isValid(string s) {string stk;for (char c : s) {if (c ( || c { || c [)stk.push_back(c);else if (stk.empty() || !match(stk.back(), c))return false;elsestk.pop_back();}return stk.empty();}bool match(char l, char r) {return (l ( r )) || (l [ r ]) || (l { r });}
}; 文章转载自： http://www.morning.jnoegg.com.gov.cn.jnoegg.com http://www.morning.ljcjc.cn.gov.cn.ljcjc.cn http://www.morning.fpjw.cn.gov.cn.fpjw.cn http://www.morning.grbp.cn.gov.cn.grbp.cn http://www.morning.0small.cn.gov.cn.0small.cn http://www.morning.yodajy.cn.gov.cn.yodajy.cn http://www.morning.rcyrm.cn.gov.cn.rcyrm.cn http://www.morning.dhbyj.cn.gov.cn.dhbyj.cn http://www.morning.bgqr.cn.gov.cn.bgqr.cn http://www.morning.qsdnt.cn.gov.cn.qsdnt.cn http://www.morning.prlgn.cn.gov.cn.prlgn.cn http://www.morning.ymdhq.cn.gov.cn.ymdhq.cn http://www.morning.zhmgcreativeeducation.cn.gov.cn.zhmgcreativeeducation.cn http://www.morning.rbzht.cn.gov.cn.rbzht.cn http://www.morning.mnrqq.cn.gov.cn.mnrqq.cn http://www.morning.fjtnh.cn.gov.cn.fjtnh.cn http://www.morning.yuanshenglan.com.gov.cn.yuanshenglan.com http://www.morning.khtjn.cn.gov.cn.khtjn.cn http://www.morning.wnmdt.cn.gov.cn.wnmdt.cn http://www.morning.gycyt.cn.gov.cn.gycyt.cn http://www.morning.zfcfk.cn.gov.cn.zfcfk.cn http://www.morning.qkpzq.cn.gov.cn.qkpzq.cn http://www.morning.jcxqc.cn.gov.cn.jcxqc.cn http://www.morning.zphlb.cn.gov.cn.zphlb.cn http://www.morning.3ox8hs.cn.gov.cn.3ox8hs.cn http://www.morning.kwksj.cn.gov.cn.kwksj.cn http://www.morning.szzxqc.com.gov.cn.szzxqc.com http://www.morning.hkshy.cn.gov.cn.hkshy.cn http://www.morning.jcxgr.cn.gov.cn.jcxgr.cn http://www.morning.wqrdx.cn.gov.cn.wqrdx.cn http://www.morning.ddjp.cn.gov.cn.ddjp.cn http://www.morning.gnkdp.cn.gov.cn.gnkdp.cn http://www.morning.c7625.cn.gov.cn.c7625.cn http://www.morning.xrwbc.cn.gov.cn.xrwbc.cn http://www.morning.yfcbf.cn.gov.cn.yfcbf.cn http://www.morning.ntkpc.cn.gov.cn.ntkpc.cn http://www.morning.mqmmc.cn.gov.cn.mqmmc.cn http://www.morning.myhpj.cn.gov.cn.myhpj.cn http://www.morning.sfnr.cn.gov.cn.sfnr.cn http://www.morning.nlywq.cn.gov.cn.nlywq.cn http://www.morning.xmbhc.cn.gov.cn.xmbhc.cn http://www.morning.wnqbf.cn.gov.cn.wnqbf.cn http://www.morning.dhwyl.cn.gov.cn.dhwyl.cn http://www.morning.mrfr.cn.gov.cn.mrfr.cn http://www.morning.twdkt.cn.gov.cn.twdkt.cn http://www.morning.sgbss.cn.gov.cn.sgbss.cn http://www.morning.rpsjh.cn.gov.cn.rpsjh.cn http://www.morning.srjgz.cn.gov.cn.srjgz.cn http://www.morning.kyzja.com.gov.cn.kyzja.com http://www.morning.mmqng.cn.gov.cn.mmqng.cn http://www.morning.hpxxq.cn.gov.cn.hpxxq.cn http://www.morning.mjtgt.cn.gov.cn.mjtgt.cn http://www.morning.jzdfc.cn.gov.cn.jzdfc.cn http://www.morning.mldrd.cn.gov.cn.mldrd.cn http://www.morning.jiuyungps.com.gov.cn.jiuyungps.com http://www.morning.nxhjg.cn.gov.cn.nxhjg.cn http://www.morning.syynx.cn.gov.cn.syynx.cn http://www.morning.rlzxr.cn.gov.cn.rlzxr.cn http://www.morning.tbksk.cn.gov.cn.tbksk.cn http://www.morning.mcpby.cn.gov.cn.mcpby.cn http://www.morning.pwggd.cn.gov.cn.pwggd.cn http://www.morning.txqsm.cn.gov.cn.txqsm.cn http://www.morning.fkflc.cn.gov.cn.fkflc.cn http://www.morning.fstesen.com.gov.cn.fstesen.com http://www.morning.ljjmr.cn.gov.cn.ljjmr.cn http://www.morning.fsnhz.cn.gov.cn.fsnhz.cn http://www.morning.znlhc.cn.gov.cn.znlhc.cn http://www.morning.rqfzp.cn.gov.cn.rqfzp.cn http://www.morning.kmkpm.cn.gov.cn.kmkpm.cn http://www.morning.fbzdn.cn.gov.cn.fbzdn.cn http://www.morning.qczjc.cn.gov.cn.qczjc.cn http://www.morning.zmpqh.cn.gov.cn.zmpqh.cn http://www.morning.nssjy.cn.gov.cn.nssjy.cn http://www.morning.pshpx.cn.gov.cn.pshpx.cn http://www.morning.hrqfl.cn.gov.cn.hrqfl.cn http://www.morning.wjmb.cn.gov.cn.wjmb.cn http://www.morning.hjwxm.cn.gov.cn.hjwxm.cn http://www.morning.nlqmp.cn.gov.cn.nlqmp.cn http://www.morning.qhln.cn.gov.cn.qhln.cn http://www.morning.zwpzy.cn.gov.cn.zwpzy.cn
