#yyds干货盘点# LeetCode刷题集:11-20

2021年11月24日 阅读数:5
这篇文章主要向大家介绍#yyds干货盘点# LeetCode刷题集:11-20,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

博主私藏的LeetCode刷题集合node

有些较难的问题都有思路和注释git


11. 盛最多水的容器

给定 n 个非负整数 a1,a2,...,an,每一个数表明坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器能够容纳最多的水。 说明:你不能倾斜容器,且 n 的值至少为 2。 ![​​在这里插入图片描述​​ 图中垂直线表明输入数组 [1,8,6,2,5,4,8,3,7]。在此状况下,容器可以容纳水(表示为蓝色部分)的最大值为 49。 示例: 输入: [1,8,6,2,5,4,8,3,7] 输出: 49 来源:力扣(LeetCode) 连接:https://leetcode-cn.com/problems/container-with-most-water 著做权归领扣网络全部。商业转载请联系官方受权,非商业转载请注明出处。数组

class Solution {
public int maxArea(int[] height) {
int max= 0 ;
int a = 0;
for (int i = 0; i < height.length; i++) {
for (int j = i+1; j

12. 整数转罗马数字

罗马数字包含如下七种字符: I, V, X, L,C,D 和 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 到 3999 的范围内。 示例 1: 输入: 3 输出: "III" 示例 2: 输入: 4 输出: "IV" 示例 3: 输入: 9 输出: "IX" 示例 4: 输入: 58 输出: "LVIII" 解释: L = 50, V = 5, III = 3. 示例 5: 输入: 1994 输出: "MCMXCIV" 解释: M = 1000, CM = 900, XC = 90, IV = 4. 来源:力扣(LeetCode) 连接:https://leetcode-cn.com/problems/integer-to-roman 著做权归领扣网络全部。商业转载请联系官方受权,非商业转载请注明出处。网络

class Solution {
private static int[] nums = new int[] {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};


private static String[] strings = new String[] {
"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"
};


public String intToRoman(int num) {
StringBuilder sb = new StringBuilder();
int i = 0;
while (num > 0) {
if (num - nums[i] >= 0) {
sb.append(strings[i]);
num -= nums[i];
} else {
i++;
}
}
return sb.toString();
}
}

13. 罗马数字转整数

罗马数字包含如下七种字符: I, V, X, L,C,D 和 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 到 3999 的范围内。 示例 1: 输入: "III" 输出: 3 示例 2: 输入: "IV" 输出: 4 示例 3: 输入: "IX" 输出: 9 示例 4: 输入: "LVIII" 输出: 58 解释: L = 50, V= 5, III = 3. 示例 5: 输入: "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4. 来源:力扣(LeetCode) 连接:https://leetcode-cn.com/problems/roman-to-integer 著做权归领扣网络全部。商业转载请联系官方受权,非商业转载请注明出处。app

class Solution {
public int romanToInt(String s) {
int[] binary = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] chars = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};


String tmp;
int index = 0, end =0;
int res = 0, sum = 0;
for(int i = 0; i < chars.length; i++){
tmp = chars[i];
end = index + tmp.length();

while(end <= s.length() && s.substring(index, end).equals(tmp)){
sum += binary[i];
index = end;
end = index + tmp.length();
}
}
return sum;
}
}

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。 若是不存在公共前缀,返回空字符串 ""。 示例 1: 输入: ["flower","flow","flight"] 输出: "fl" 示例 2: 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 说明: 全部输入只包含小写字母 a-z 。 来源:力扣(LeetCode) 连接:https://leetcode-cn.com/problems/longest-common-prefix 著做权归领扣网络全部。商业转载请联系官方受权,非商业转载请注明出处。ide

class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0 ) return "";
String reg = strs[0];
for (String str : strs){
while (!str.startsWith(reg)) {
if (reg.length() == 1) {
return "";
}
reg = reg.substring(0, reg.length()-1);
}
}
return reg;
}
}

15. 三数之和

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出全部知足条件且不重复的三元组。 注意:答案中不能够包含重复的三元组。 示例: 给定数组 nums = [-1, 0, 1, 2, -1, -4], 知足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ] 来源:力扣(LeetCode) 连接:https://leetcode-cn.com/problems/3sum 著做权归领扣网络全部。商业转载请联系官方受权,非商业转载请注明出处。函数

class Solution {
public List> threeSum(int[] nums) {
Arrays.sort(nums); //对数组进行排序
HashSet> Res=new HashSet<>(); //建立HashSet对象
for(int i=0;i<=nums.length-3;i++){
if(nums[i]>0)
break; //若数组中的最小数大于0,直接跳出循环
int left=i+1; //左指针
int right=nums.length-1; //右指针
while(left0){
right--; //大于0,右指针左移
}else{
Res.add(Arrays.asList(nums[i],nums[left++],nums[right--])); //等于0,知足条件,记录下来
}
}
}
return new ArrayList<>(Res);


}
}

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在惟一答案。 例如,给定数组 nums = [-1,2,1,-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2). 来源:力扣(LeetCode) 连接:https://leetcode-cn.com/problems/3sum-closest 著做权归领扣网络全部。商业转载请联系官方受权,非商业转载请注明出处。ui

class Solution {
public int threeSumClosest(int[] nums, int target) {
// 排序
Arrays.sort(nums);
int closestNum = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length - 2; i++) {
int l = i + 1, r = nums.length - 1;
while (l < r){
int threeSum = nums[l] + nums[r] + nums[i];
if (Math.abs(threeSum - target) < Math.abs(closestNum - target)) {
closestNum = threeSum;
}
if (threeSum > target) {
r--;
} else if (threeSum < target) {
l++;
} else {
// 若是已经等于target的话, 确定是最接近的
return target;
}


}


}


return closestNum;
}
}

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回全部它能表示的字母组合。 给出数字到字母的映射以下(与电话按键相同)。注意 1 不对应任何字母。 ![​​在这里插入图片描述​​ 示例: 输入:"23" 输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 来源:力扣(LeetCode) 连接:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number 著做权归领扣网络全部。商业转载请联系官方受权,非商业转载请注明出处。spa

class Solution {
public List letterCombinations(String digits) {
Listlist=new ArrayList<>();
String []s=new String[digits.length()];
int M=digits.length();
if(s.length==0){
return list;
}
for(int i=0;i getStringWithFor(String []s,int i,List list,String stemp) {


if(i

18. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出全部知足条件且不重复的四元组。 注意: 答案中不能够包含重复的四元组。 示例: 给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。 知足要求的四元组集合为: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ] 来源:力扣(LeetCode) 连接:https://leetcode-cn.com/problems/4sum 著做权归领扣网络全部。商业转载请联系官方受权,非商业转载请注明出处。3d

class Solution {
public List> fourSum(int[] nums, int target) {
int len = nums.length;
List> res = new ArrayList>();
if(nums.length<4) return res;
Arrays.sort(nums);
if(nums[0]>target/4 || nums[len-1]target/4) break;
if(i>0 && nums[i]==nums[i-1]) continue;
int sum = target-nums[i];
for(int j = i+1;jsum/3) break;
if(j>i+1 && nums[j]==nums[j-1]) continue;
int l = j+1;
int r = len-1;
while(lsum){//结果大了右指针往左
r--;
}else{//结果小了左指针往右
l++;
}
}
}
}
return res;
}
}

19. 删除链表的倒数第N个节点

给定一个链表,删除链表的倒数第 n 个节点,而且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明: 给定的 n 保证是有效的。 进阶: 你能尝试使用一趟扫描实现吗? 来源:力扣(LeetCode) 连接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list 著做权归领扣网络全部。商业转载请联系官方受权,非商业转载请注明出处。 PS: 递归大法:1ms

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
return removeNode(head,n)==n?head.next:head;
}
public int removeNode(ListNode node,int n) {
if(node.next == null) return 1;
int m = removeNode(node.next, n);
if(m == n)
if(m == 1) node.next = null;
else node.next = node.next.next;
return m+1;
}
}

20. 有效的括号

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需知足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 示例 1: 输入: "()" 输出: true 示例 2: 输入: "()[]{}" 输出: true 示例 3: 输入: "(]" 输出: false 示例 4: 输入: "([)]" 输出: false 示例 5: 输入: "{[]}" 输出: true 来源:力扣(LeetCode) 连接:https://leetcode-cn.com/problems/valid-parentheses 著做权归领扣网络全部。商业转载请联系官方受权,非商业转载请注明出处。

class Solution {
public boolean isValid(String s) {
Stackstack = new Stack();
for(char c: s.toCharArray()){
if(c=='(')stack.push(')');
else if(c=='[')stack.push(']');
else if(c=='{')stack.push('}');
else if(stack.isEmpty()||c!=stack.pop())return false;
}
return stack.isEmpty();
}
}