LeetCode 热题 HOT 100(P11~P20)

2024-03-16 02:44
文章标签 leetcode 100 热题 hot p11 p20

本文主要是介绍LeetCode 热题 HOT 100(P11~P20)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LC020valid_parentheses

. - 力扣（LeetCode）

题目：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

解法：

遇到右括号的时候需要判断有没有对应匹配的左括号，因为必须是类型相同的才能进行闭合，因此需要一个栈来维护遇到的左括号，看栈顶的左括号是否跟当前的右括号匹配。

 static Map<Character, Character> cache = new HashMap<>();static {cache.put(')', '(');cache.put('}', '{');cache.put(']', '[');}public boolean isValid(String s) {LinkedList<Character> stack = new LinkedList<>();for (char c : s.toCharArray()) {//  遇到右括号就需要一定要有匹配的左括号if (cache.containsKey(c)) {if (stack.isEmpty()) {return false;}if (cache.get(c) != stack.pop()) {return false;}} else {//左括号的情况，直接入栈stack.push(c);}}return stack.isEmpty();}

这里有个技巧，维护一个右括号为key 的map，这样方便判断和匹配。

LC021merge_two 

. - 力扣（LeetCode）

题目：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

解法：

遇到链表题，直接创建一个pre 节点，接着轮流比较两边的大小，比较繁琐的是需要判断很多临界情况。

 public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode pre = new ListNode();ListNode cur = pre;while (list1 != null || list2 != null) {ListNode next;if (list1 == null) {next = list2;list2 = list2.next;} else if (list2 == null) {next = list1;list1 = list1.next;} else {if (list1.val < list2.val) {next = list1;list1 = list1.next;} else {next = list2;list2 = list2.next;}}cur.next = next;cur = cur.next;}return pre.next;}

LC022generate_parentheses

. - 力扣（LeetCode）

题目：

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

题解：

一般这种题都是递归的思路，相当于有2n个位置，每个位置都可能至多有2种策略，不是放左括号就是放右括号，放好之后再接着放下一个。这里有个有效括号的限制，所以想清楚这个就相对容易了。

    List<String> result = new ArrayList<>();public List<String> generateParenthesis(int n) {dsf("", n, n);return result;}/*** 递归的写法** @param path  当前的字符串* @param left  左括号剩余使用次数* @param right 右括号剩余使用次数*/private void dsf(String path, int left, int right) {// 错误的情况if (left > right) {return;}if (left == 0 && right == 0) {result.add(path);return;}if (left > 0) {dsf(path + "(", left - 1, right);}if (right > 0) {dsf(path + ")", left, right - 1);}}

这里使用剩余使用测试，而不是已经使用次数，会让代码更加清晰。

递归的写法在熟悉递归模板之后，就是对什么时候跳出递归的判断，这一步思考清楚，后面就不难了。

LC023merge_k

. - 力扣（LeetCode）

题目：

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

题解：

其实就是利用递归的思路，先对半往下递归，最后是两个链表的合并（LC021merge_two ）。

public ListNode mergeKLists(ListNode[] lists) {if (lists.length == 0) {return null;}return merge(lists, 0, lists.length - 1);}private ListNode merge(ListNode[] lists, int left, int right) {if (left == right) {return lists[left];}int mid = left + (right - left) / 2;final ListNode l1 = merge(lists, left, mid);final ListNode l2 = merge(lists, mid + 1, right);return merge2(l1, l2);}private ListNode merge2(ListNode l1, ListNode l2) {if (l1 == null) {return l2;}if (l2 == null) {return l1;}if (l1.val < l2.val) {l1.next = merge2(l1.next, l2);return l1;} else {l2.next = merge2(l1, l2.next);return l2;}}

递归真是好东西啊，任何复杂的问题都能化繁为简。

LC031next_permutation

. - 力扣（LeetCode）

题目：

整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
给你一个整数数组 nums ，找出 nums 的下一个排列。

题解：

这类题目就是典型的套路题了，当初靠自己想破脑袋估计也想不出来，直接看题解知道套路，掌握思路后加上自己在事例上推演下也就能写出来了。

public void nextPermutation(int[] nums) {final int len = nums.length;if (len < 2) {return;}int i = len - 2, k = len - 1;//找到最右边的“小数”while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}//如果不是最后一种情况，注意这里包含=0 的情况if (i >= 0) {//从后往前，找到尽可能“小”的大数while (nums[i] >= nums[k]) {k--;}int tmp = nums[i];nums[i] = nums[k];nums[k] = tmp;}//需要将i+1 之后的数字排序//将「大数」换到前面后，需要将「大数」后面的所有数 重置为升序，升序排列就是最小的排列。Arrays.sort(nums, i + 1, len);}

LC032longest_valid

. - 力扣（LeetCode）

题目：

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度

题解：

“最*** ” 的基本是动态规划的思路。只是这里情况比较复杂，需要考虑很多边界情况

public int longestValidParentheses(String s) {final char[] chars = s.toCharArray();int[] dp = new int[chars.length];int max = 0;for (int i = 1; i < chars.length; i++) {//只有封闭的右括号才有可能配对if (chars[i] == ')') {//跟前一位刚好匹配if (chars[i - 1] == '(') {// 数量就是前前位+2，这里>= 还是> 实际是一样的，因为dp[0]=0dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;} else { // i-1 也是右括号final int pre = i - 1 - dp[i - 1];if (pre >= 0 && chars[pre] == '(') {dp[i] = (pre > 0 ? dp[pre - 1] : 0) + dp[i - 1] + 2;}}max = Math.max(max, dp[i]);}}return max;}

这个也可以算套路题吧，动态规划还是挺考验功力的，动态方程往往取决动态数组的定义。这类题只能靠多做，多培养感觉了。

LC033search_in

. - 力扣（LeetCode）

题目：

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

题解：

经典的二分查找啊，之前刚学二分查找的时候觉得这玩意还不简单，没有特意准备，结果是啪啪打脸了。先复习下二分查找模板：

left, right = 0, len(array) - 1 
/注意这里的=
while left <= right:mid = left+(right - left) / 2 if array[mid] == target:# find the target!!break or return result elif array[mid] < target:left = mid + 1 else:right = mid - 1

回到这道题，关键点是旋转数组始终有一半是有序的，这个时候针对有序的一边进行判断和处理，如果不在这一边就说明在另一边，说明当前这一边可以舍弃，继续下一步迭代。

public int search(int[] nums, int target) {if (nums.length == 0) {return -1;}int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;}//左边有序的情况if (nums[left] <= nums[mid]) {if (target >= nums[left] && target <= nums[mid]) {right = mid - 1;} else {left = mid + 1;}} else {if (target > nums[mid] && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;}}}return -1;}

LC34find_first

. - 力扣（LeetCode）

题目：

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

题解：

这道题比较有意思，一般我们通过折半查找都是确定具体的位置，这里是要找做边界和右边界，实际跟折半查找非常类似，只是左边界往小的那一边继续找，右边界就往大的那一边继续找。

public int[] searchRange(int[] nums, int target) {final int len = nums.length;if (len == 0) {return new int[]{ -1, -1 };}int left = 0, right = len - 1;int begin = -1, end = -1;//先找左边起始点while (left <= right) {int mid = left + (right - left) / 2;//要找左边界，需要往尽可能小的方向寻找if (nums[mid] == target) {begin = mid;right = mid - 1;} else if (target > nums[mid]) {left = mid + 1;} else {right = mid - 1;}}left = 0;right = len - 1;while (left <= right) {int mid = left + (right - left) / 2;//要找右边界，需要往尽可能大的方向寻找if (nums[mid] == target) {end = mid;left = mid + 1;} else if (target > nums[mid]) {left = mid + 1;} else {right = mid - 1;}}return new int[]{ begin, end };}

可以看到有挺多重复代码，可以提一个方法出来

public int[] searchRange(int[] nums, int target) {int left = 0, right = nums.length - 1;int begin = getLocation(nums, target, left, right, true);int end = getLocation(nums, target, left, right, false);return new int[]{ begin, end };}/*** 找到target 对应的下标** @param nums* @param target* @param left* @param right* @param isBegin 是否起始点* @return*/private int getLocation(int[] nums, int target, int left, int right, boolean isBegin) {int location = -1;while (left <= right) {int mid = left + (right - left) / 2;if (target == nums[mid]) {location = mid;//关键点在于找起止点的时候对左右游标的处理if (isBegin) {right = mid - 1;} else {left = mid + 1;}} else if (target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}}return location;}

LC39combination_sum

. - 力扣（LeetCode）

题目：

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

题解：

也是典型的递归思路，关键是怎么保证不走回头路，比如有整数数组是（1，2，3），在递归1 的时候，把所有可以跟1组合的所有数组都穷举了，那么递归到2 的时候，就不能再用1 了，因为这个组合肯定在之前递归1的时候已经存在了。

public List<List<Integer>> combinationSum(int[] candidates, int target) {if (candidates.length == 0) {return result;}dfs(candidates, new ArrayList<>(), 0, target);return result;}/*** 注意这里需要一个start 标识，用来避免走回头路引起的重复数据** @param candidates* @param path* @param start* @param target*/private void dfs(int[] candidates, ArrayList<Integer> path, int start, int target) {if (target == 0) {result.add(new ArrayList<>(path));return;}if (target < 0) {return;}for (int i = start; i < candidates.length; i++) {path.add(candidates[i]);dfs(candidates, path, i, target - candidates[i]);path.remove(path.size() - 1);}}

LC46permutations

. - 力扣（LeetCode）

题目：

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

题解：

也是用递归解决，难点在于去重。这里通过一个boolean 数组来标识已经使用过的数字。这里可以复习下上一篇的递归模板。

List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {boolean[] used = new boolean[nums.length];dfs(nums, new ArrayList<>(), used);return result;}private void dfs(int[] nums, ArrayList<Integer> path, boolean[] used) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (used[i]) {continue;}path.add(nums[i]);used[i] = true;dfs(nums, path, used);used[i] = false;path.remove(path.size() - 1);}}

这篇关于LeetCode 热题 HOT 100(P11~P20)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/814040。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
【JavaScript】LeetCode：16-20

【JavaScript】LeetCode：16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i，右指针j，从头遍历数组，若j指针指向的元素不在set中，则加入该元素，否则更新结果res，删除集合中i指针指向的元素，进入下一轮循环。 /*** @param
阅读更多...
LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵，找出只包含 1 的最大正方形，并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划
阅读更多...
LeetCode 第414场周赛个人题解

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析
阅读更多...
【JavaScript】LeetCode：21-25

【JavaScript】LeetCode：21-25

文章目录 21 最大子数组和22 合并区间23 轮转数组24 除自身以外数组的乘积25 缺失的第一个正数 21 最大子数组和 贪心 / 动态规划贪心：连续和（count）< 0时，放弃当前起点的连续和，将下一个数作为新起点，这里提供使用贪心算法解决本题的代码。动态规划：dp[i]：以nums[i]为结尾的最长连续子序列（子数组）和。 dp[i] = max(dp[i - 1]
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2