算法题解(Leetcode 11、15、17、19、20) 向右看齐 2022-09-10 10:10 94阅读 0赞 ### 文章目录 ### * * \[11. 盛最多水的容器 - 中等 - 9/7\](https://leetcode-cn.com/problems/container-with-most-water/) * \[15. 三数之和 - 中等 - 9/8\](https://leetcode-cn.com/problems/3sum/) * \[17. 电话号码的字母组合 - 中等 - 9/9\](https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/) * \[19. 删除链表的倒数第 N 个结点 - 中等 - 9/10\](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/) * \[20. 有效的括号 - 简单 - 9/11\](https://leetcode-cn.com/problems/valid-parentheses/) ## [11. 盛最多水的容器 - 中等 - 9/7][11. _ - _ - 9_7] ## 给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明:你不能倾斜容器。 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16] ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 1] ![在这里插入图片描述][927b6d3a753c44649b165fc7d3407da7.png] -------------------- 解析: 使用双指针,开始时,判断最左边的值 与 最右边的值 哪个小,取小的来计算容量,因为“水往低处流”;容量 = 较小值 \*(右下标-左下标);然后再移动指针,哪个指针指向的值小 就移动哪个指针。 class Solution { public int maxArea(int[] height) { int min = 0; //存放最小值 int sum = 0; //计算结果 int left = 0; //左指针 int right = height.length - 1; //右指针 while (left < right){ //当左边的值 小于等于 右边的值时,取两者较小的值,计算容量。容量 = 较小值 *(右下标-左下标)。然后移动左指针 if (height[left] <= height[right]){ min = height[left]; sum = Math.max(sum,min * (right-left)); left++; }else { //左边的值 大于 右边的值 min = height[right]; sum = Math.max(sum,min * (right-left)); right--; } } //返回结果 return sum; } } ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 2] 时间复杂度:O(n),双指针总计最多遍历整个数组一次。 空间复杂度:O(1),只需要额外的常数级别的空间 ## [15. 三数之和 - 中等 - 9/8][15. _ - _ - 9_8] ## 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 3] -------------------- 解析: ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 4] -------------------- class Solution { public List<List<Integer>> threeSum(int[] nums) { int len = nums.length; //待返回的数组 List<List<Integer>> ans = new ArrayList<>(); //如果数组为空 或者 数组的长度小于3 if (nums == null || len < 3) return ans; //排序 Arrays.sort(nums); //遍历 for (int i = 0; i < len; i++) { //如果当前 排序后的数大于0,则三数之和一定不为0 if (nums[i] > 0) break; //去重 if (i > 0 && nums[i] == nums[i - 1]) continue; //当前数后面的左指针 int left = i + 1; //当前数后面的右指针 int right = len - 1; //循环 while (left < right) { //计算和 int sum = nums[i] + nums[left] + nums[right]; //如果结果为0 if (sum == 0) { //添加到集合 ans.add(Arrays.asList(nums[i], nums[left], nums[right])); //去重 while (left < right && nums[left] == nums[left + 1]) left++; while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; } //如果sum<0,说明负数大了,应将左指针向右移动一位 else if (sum < 0) left++; else if (sum > 0) right--; } } return ans; } } ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 5] ## [17. 电话号码的字母组合 - 中等 - 9/9][17. _ - _ - 9_9] ## 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_11_color_FFFFFF_t_70_g_se_x_16] ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 6] -------------------- **解析:** 回溯算法 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_17_color_FFFFFF_t_70_g_se_x_16] 对于打印"2345"这样的字符串: 第一次递归就是上图中最下面的方格,然后处理完第一个字符2之后,将输入的字符改变成"345"并调用第二个递归函数 第二次递归处理3,将字符串改变成"45"后再次递归 第三次递归处理4,将字符串改变成"5"后继续递归 第四次递归处理5,将字符串改变成""后继续递归 最后发现字符串为空了,将结果放到列表中并返回 上面是从函数调用的角度去看的,而每次调用下一层递归时,都需要将本层的一些处理结果放到一个临时变量中,再传递给下一层,从这个变量层层传递的变化看,就像一棵树一样,这个算法的时间复杂度很高,是O(3^n)这个级别的,空间复杂度是O(n) ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_15_color_FFFFFF_t_70_g_se_x_16] -------------------- class Solution { //数字到字符串的映射 String[] str = { "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; //结果集 List<String> res = new ArrayList<>(); //路径 操作字符 StringBuilder sb = new StringBuilder(); public List<String> letterCombinations(String digits) { //特殊处理 if(digits == null || digits.length() == 0) return res; //调用回溯函数 backtrack(digits,0); return res; } //回溯函数 void backtrack(String digits,int index){ //退出条件 如果 输入字符的长度 等于 操作字符的长度 就把操作字符添加进去,然后返回 if(digits.length() == sb.length()){ res.add(sb.toString()); return; } //获取当前数字对应的字符串 String val = str[digits.charAt(index) - '2']; //遍历 for(char v: val.toCharArray()){ sb.append(v); //拼接字符 backtrack(digits,index+1); //递归调用,index+1是 使用下一个数字对应的字符串 //操作完成后删除刚才用过的字母 sb.deleteCharAt(sb.length()-1); } } } ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 7] ## [19. 删除链表的倒数第 N 个结点 - 中等 - 9/10][19. _ N _ - _ - 9_10] ## 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 进阶:你能尝试使用一趟扫描实现吗? ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 8] ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 9] -------------------- **解法一:** 删除一个结点,无非是遍历链表找到那个结点前边的结点,然后改变下指向就好了。但由于它是链表,它的长度我们并不知道,我们得先遍历一遍得到它的长度,之后用长度减去 n 就是要删除的结点的位置,然后遍历到结点的前一个位置就好了。 * 先遍历一遍链表,得出链表长度 * 特殊值处理 * 计算出待删除结点的位置 * 找到带删除结点的前一个结点 * 改变指向,就是删除 * 返回 /** * 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) { //记录长度 int len = 0; //复制一个头指针 ListNode h = head; //计算长度 while(h != null){ h = h.next; len++; } //长度等于 1 ,再删除一个结点就为 null 了 if(len == 1){ return null; } //计算待删除节点的位置 int rm_node_index = len - n; //如果删除的是头结点,返回后面的。 if(rm_node_index == 0){ return head.next; } //重新赋值 h = head; //找到删除结点的前一个结点位置 for(int i=0; i < rm_node_index-1; i++){ h = h.next; } //改变指向,就是删除 h.next = h.next.next; return head; } } ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 10] 时间复杂度:假设链表长度是 L ,那么就第一个循环是 L 次,第二个循环是 L - n 次,总共 2L - n 次,所以时间复杂度就是 O(L)。 空间复杂度:O(1)。 -------------------- **解法二:** 想象一下,两个人进行 100m 赛跑,假设他们的速度相同。开始的时候,第一个人就在第二个人前边 10m ,这样当第一个人跑到终点的时候,第二个人相距第一个人依旧是 10m ,也就是离终点 10m。 对比于链表,我们设定两个指针,先让第一个指针遍历 n 步,然后再让它俩同时开始遍历,这样的话,当第一个指针到头的时候,第二个指针就离第一个指针有 n 的距离,所以第二个指针的位置就刚好是倒数第 n 个结点。 /** * 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); //让它指向头指针 dummy.next = head; ListNode first = dummy; ListNode second = dummy; //第一个指针先移动 n 步 for (int i = 1; i <= n + 1; i++) { first = first.next; } //第一个指针到达终点停止遍历 while (first != null) { first = first.next; second = second.next; } //改变指针方向,即为删除结点 second.next = second.next.next; return dummy.next; } } ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 11] ## [20. 有效的括号 - 简单 - 9/11][20. _ - _ - 9_11] ## 给定一个只包括 ‘(’,’)’,’\{’,’\}’,’\[’,’\]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 12] ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 13] -------------------- **解析:** 暴力搜索这一组括号, 遇到左括号入栈,遇到右括号,那么我们拿这个右括号跟栈顶比较,如果能匹配,那么目前为止,这组括号有效,如果不能匹配,直接返回false。 class Solution { public boolean isValid(String s) { //创建一个栈 Stack<Character> stack = new Stack(); //遍历 for(Character c : s.toCharArray()){ if(c=='(' || c=='[' || c=='{'){ stack.push(c); //入栈 // 如果c是 )}] 并且栈不为空 则 判断栈顶是否为与之对应的左括号 是则出栈,不是则返回fasle }else if (c == ')' && !stack.empty() && stack.peek() == '('){ stack.pop(); //出栈 }else if (c == ']' && !stack.empty() && stack.peek() == '['){ stack.pop(); //出栈 }else if (c == '}' && !stack.empty() && stack.peek() == '{'){ stack.pop(); //出栈 }else{ return false; } } return stack.empty(); } } ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 14] -------------------- 解法二: 遍历整个字符串,遇到左括号就入栈,然后遇到和栈顶对应的右括号就出栈,遍历结束后,如果栈为空,就表示全部匹配。 class Solution { public boolean isValid(String s) { //创建栈 Stack<Character> brackets = new Stack<Character>(); for(int i = 0;i < s.length();i++){ char c = s.charAt(i); switch(c){ case '(': case '[': case '{': brackets.push(c); //入栈 break; case ')': if(!brackets.empty()){ if(brackets.peek()== '('){ //取栈顶字符来比较 brackets.pop(); //出栈 }else{ return false; } }else{ return false; } break; case ']': if(!brackets.empty()){ if(brackets.peek()=='['){ brackets.pop(); }else{ return false; } }else{ return false; } break; case '}': if(!brackets.empty()){ if(brackets.peek()=='{'){ brackets.pop(); }else{ return false; } }else{ return false; } } } return brackets.empty(); } } ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 15] 时间复杂度:O(n)。 空间复杂度:O(n)。 [11. _ - _ - 9_7]: https://leetcode-cn.com/problems/container-with-most-water/ [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/3895366cb9174a5cac4cc16210982892.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/e41610941abe47a6b11b717db5e103d3.png [927b6d3a753c44649b165fc7d3407da7.png]: /images/20220829/f98f14aefb5d48809babb83a2105cc5c.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/b04e2156045b446ea8adf59a5782bf7b.png [15. _ - _ - 9_8]: https://leetcode-cn.com/problems/3sum/ [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/dca68da475dc4528bda63033aad1c922.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/4488d85ddd764c7da5e0f6c6263c618d.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220829/1e92c8c88c3c4f9e84de150b5a46e6b9.png [17. _ - _ - 9_9]: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/ [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/a59d589e74754fc2be0e4702581336eb.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220829/6a577b6af64a4eebb747cfaea430ce81.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/824389ff69274b08a8d18fb91d2e46be.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/5e099948a29b4fe09e83693366660b51.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220829/989baf6404b84c659cb6b2eb601051bc.png [19. _ N _ - _ - 9_10]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/ [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220829/245398f43a59433ab2bb4ffc2bc62cf8.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220829/7ce17e847aa741d8bff7eeb2bceeeb9f.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220829/9c8d1d38b04e4b5dbf5cc6c2c8c02570.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220829/80044781ff7c49859404da77dba6e691.png [20. _ - _ - 9_11]: https://leetcode-cn.com/problems/valid-parentheses/ [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220829/d81e4a1b238d43c6a7d804b825f5332d.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 13]: /images/20220829/ec1fab4073b54620b1d6d4b9b59358d5.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 14]: /images/20220829/acd4d4c354854a89b70729f8273c831a.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 15]: /images/20220829/abaee85c69a74f038ad5a9bced425322.png
还没有评论,来说两句吧...