LeetCode热门100题算法和思路（day2）
2022-08-16 本文已影响0人
码农朱同学
LeetCode10 正则表达式匹配
题目详情
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '' 的正则表达式匹配。
'.' 匹配任意单个字符
'' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
输入：s = "aa", p = "a"
输出：true
解释：因为 '' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：
输入：s = "ab", p = "."
输出：true
解释："." 表示可匹配零个或多个（'*'）任意字符（'.'）。
提示：
1 <= s.length <= 20
1 <= p.length <= 30
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符
代码
public class LeetCode10 {
public static void main(String[] args) {
System.out.println(new Solution().isMatch("aaabaaacc", "a*ba*.."));
System.out.println(new Solution().isMatch1("aaabaaacc", "a*ba*.."));
System.out.println(new Solution().isMatch2("aaabaaacc", "a*ba*.."));
}
static class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] f = new boolean[m + 1][n + 1];
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p.charAt(j - 1) == '*') {
f[i][j] = f[i][j - 2];
if (matches(s, p, i, j - 1)) {
f[i][j] = f[i][j] || f[i - 1][j];
}
} else {
if (matches(s, p, i, j)) {
f[i][j] = f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
public boolean matches(String s, String p, int i, int j) {
if (i == 0) {
return false;
}
if (p.charAt(j - 1) == '.') {
return true;
}
return s.charAt(i - 1) == p.charAt(j - 1);
}
/*
动态规划
*/
public boolean isMatch1(String text, String pattern) {
boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
dp[text.length()][pattern.length()] = true;
for (int i = text.length(); i >= 0; i--) {
for (int j = pattern.length() - 1; j >= 0; j--) {
boolean first_match = (i < text.length() &&
(pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
dp[i][j] = dp[i][j + 2] || first_match && dp[i + 1][j];
} else {
dp[i][j] = first_match && dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}
/*
动态规划
*/
public boolean isMatch2(String s, String p) {
//此处为length+1的目的是放入一个额外的为空的字符情况，以便于判断当*时，添加的字符情况
boolean table[][] = new boolean[s.length() + 1][p.length() + 1];
table[0][0] = true;
for (int i = 1; i < table[0].length; i++) {
char ch = p.charAt(i - 1);
if (i > 1) {
//若ch=='*'，则看同一行内回退两格的boolean值：
//（因为相当于若回退两格为true，即在选择添加该字符时可以选择数量为0（因为是'*'））
if (ch == '*') {
table[0][i] = table[0][i - 2];
}
//因为第0行的s字符为空，所以和除了*以外的都不匹配，直接false
else table[0][i] = false;
} else {
//如果填第一个空格，且字符为*，则赋值为true（因为*的匹配可以选择0个字符）
if (ch == '*') table[0][i] = true;
}
}
//接下来按照行优先的顺序填充表格
for (int j = 1; j < table.length; j++) {
char ch01 = s.charAt(j - 1);
for (int h = 1; h < table[j].length; h++) {
char ch02 = p.charAt(h - 1);
//如果行和列对应的字符相等 || 列的字符为'.'，则当前位置的值由左斜上方的值确定
if (ch02 == ch01 || ch02 == '.') {
table[j][h] = table[j - 1][h - 1];
}
//如果列的字符为'*'
else if (ch02 == '*') {
if (h > 1) {
//按照规则，先在同一行回退两格，若该值为true则直接赋值true
if (table[j][h - 2] == true) table[j][h] = true;
else {
//若不为true，则比较当前行的字符（s里的）与当前列-1的字符（p里的）是否相等
char prev = p.charAt(h - 2);
//若相等 || 当前列-1的字符（p里的）为'.'，将当前位置上方的值赋给当前位置
if (ch01 == prev || prev == '.') table[j][h] = table[j - 1][h];
}
}
}
}
}
//返回table表的最右下方元素，即为整个字符串的匹配结果
return table[s.length()][p.length()];
}
}
}
LeetCode11 盛最多水的容器
题目详情
给定一个长度为 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.length
2 <= n <= 105
0 <= height[i] <= 104
代码
public class LeetCode11 {
public static void main(String[] args) {
System.out.println(new Solution().maxArea(new int[]{8, 10, 2, 2, 2, 2, 2, 99, 9}));
System.out.println(new Solution().maxArea1(new int[]{8, 10, 2, 2, 2, 2, 2, 99, 9}));
}
public static class Solution {
/*
暴力解法
*/
public int maxArea(int[] height) {
int maxarea = 0;
for (int i = 0; i < height.length; i++) {
for (int j = i + 1; j < height.length; j++) {
maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i));
}
}
return maxarea;
}
/*
双指针
关键词：左右两边
模式识别：需要移动左右两头的问题，可以考虑双指针
难点：如何移动指针
相同情况下两边距离越远越好
区域受限于较短边
*/
public int maxArea1(int[] height) {
int maxarea = 0, l = 0, r = height.length - 1;
while (l < r) {
maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
//最初我们考虑由最外面两条线段构成的区域。现在，为是使面积最大化，我们需要考虑更长的两条线段之间的区域。
//如果我们试图将指向较长线段的指针向内侧移动，矩形区域的面积将受限于较短的线段而不会获得任何增加。但是，在同样的条件下，移动
//较短的指针尽管造成了矩形宽度的减小，但却可能有助于面积的增大。因为移动较短的指针会得到相对较长的线段，这可以克服由宽度减小而引起的面积减少。
if (height[l] < height[r])
l++;
else
r--;
}
return maxarea;
}
}
}
LeetCode15 三数之和
题目详情
给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
代码
public class LeetCode15 {
public static void main(String[] args) {
int[] height = {-1, 0, 1, 2, -1, -4};
List<List<Integer>> ans = Solution.threeSum(height);
for (List<Integer> list : ans) {
System.out.println("------begin------");
for (Integer item : list) {
System.out.println(item);
}
}
}
/*
算法流程：
特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
对数组进行排序。
遍历排序后数组：
若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
对于重复元素：跳过，避免出现重复解
令左指针 L=i+1，右指针 R=R=n−1，当 L<R时，执行循环：
当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R移到下一位置，寻找新的解
若和大于 00，说明 nums[R] 太大，RR 左移
若和小于 00，说明 nums[L] 太小，LL 右移
*/
public static class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
int len = nums.length;
if (len < 3) return ans;
Arrays.sort(nums);
for (int i = 0; i < len; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int L = i + 1;
int R = len - 1;
while (L < R) {
int sum = nums[i] + nums[L] + nums[R];
if (sum == 0) {
ans.add(Arrays.asList(nums[i], nums[L], nums[R]));
while (L < R && nums[L] == nums[L + 1]) L++;
while (L < R && nums[R] == nums[R - 1]) R--;
L++;
R--;
} else if (sum < 0) L++;
else if (sum > 0) R--;
}
}
return ans;
}
/*
用Map改进的暴力解法
*/
public static List<List<Integer>> threeSum1(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
int len = nums.length;
if (len < 3) return ans;
return ans;
}
}
}
LeetCode17 电话号码的字母组合
题目详情
给定一个仅包含数字 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 <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
代码
public class LeetCode17 {
public static void main(String[] args) {
System.out.println(new Solution().letterCombinations("23"));
}
/*
回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。
*/
static class Solution {
Map<String, String> phone = new HashMap<String, String>() {{
put("2", "abc");
put("3", "def");
put("4", "ghi");
put("5", "jkl");
put("6", "mno");
put("7", "pqrs");
put("8", "tuv");
put("9", "wxyz");
}};
List<String> output = new ArrayList<String>();
public void backtrack(String combination, String next_digits) {
// if there is no more digits to check
if (next_digits.length() == 0) {
// the combination is done
output.add(combination);
}
// if there are still digits to check
else {
// iterate over all letters which map
// the next available digit
String digit = next_digits.substring(0, 1);
String letters = phone.get(digit);
for (int i = 0; i < letters.length(); i++) {
String letter = phone.get(digit).substring(i, i + 1);
// append the current letter to the combination
// and proceed to the next digits
backtrack(combination + letter, next_digits.substring(1));
}
}
}
public List<String> letterCombinations(String digits) {
if (digits.length() != 0)
backtrack("", digits);
return output;
}
}
}
LeetCode19 删除链表的倒数第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]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
代码
public class LeetCode19 {
public static void main(String[] args) {
ListNode.printNode(new Solution().removeNthFromEnd(ListNode.buildNode(new int[]{1, 2, 3, 4, 5}), 3));
ListNode.printNode(new Solution().removeNthFromEnd2(ListNode.buildNode(new int[]{1, 2, 3, 4, 5}), 3));
}
/*
算法
上述算法可以优化为只使用一次遍历。我们可以使用两个指针而不是一个指针。
第一个指针从列表的开头向前移动 n+1n+1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 nn 个结点分开。
我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 nn 个结点。
我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。
*/
static class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Advances first pointer so that the gap between first and second is n nodes apart
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
// Move first to the end, maintaining the gap
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
/*
回溯法后序遍历
*/
public ListNode removeNthFromEnd2(ListNode head, int n) {
int traverse = traverse(head, n);
if (traverse == n)
return head.next;
return head;
}
private int traverse(ListNode node, int n) {
if (node == null)
return 0;
int num = traverse(node.next, n);
if (num == n)
node.next = node.next.next;
return num + 1;
}
}
}
LeetCode20 有效的括号
题目详情
给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例2：
输入：s = "()[]{}"
输出：true
示例3：
输入：s = "(]"
输出：false
示例4：
输入：s = "([)]"
输出：false
示例5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
代码
public class LeetCode20 {
public static void main(String[] args) {
System.out.println(new Solution().isValid("([)]"));
System.out.println(new Solution2().isValid("([)]"));
}
static class Solution {
private Map<Character, Character> map = new HashMap<Character, Character>() {{
put('{', '}');
put('[', ']');
put('(', ')');
put('?', '?');
}};
public boolean isValid(String s) {
if (s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
LinkedList<Character> stack = new LinkedList<Character>() {{
add('?');
}};
for (Character c : s.toCharArray()) {
if (map.containsKey(c)) stack.addLast(c);
else if (map.get(stack.removeLast()) != c) return false;
}
return stack.size() == 1;
}
}
static class Solution2 {
private HashMap<Character, Character> mappings;
public Solution2() {
this.mappings = new HashMap<Character, Character>();
this.mappings.put(')', '(');
this.mappings.put('}', '{');
this.mappings.put(']', '[');
}
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (this.mappings.containsKey(c)) {
char topElement = stack.empty() ? '#' : stack.pop();
if (topElement != this.mappings.get(c)) {
return false;
}
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
}
}
LeetCode21 合并两个有序链表
题目详情
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
代码
public class LeetCode21 {
public static void main(String[] args) {
ListNode.buildNode(new int[]{1, 2, 3, 4, 5});
ListNode.printNode(new Solution().mergeTwoLists(ListNode.buildNode(new int[]{1, 2, 4}), ListNode.buildNode(new int[]{1, 3, 4})));
ListNode.printNode(new Solution().mergeTwoLists2(ListNode.buildNode(new int[]{1, 2, 4}), ListNode.buildNode(new int[]{1, 3, 4})));
}
static class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//在返回节点之前保持对节点的不变引用。
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
//此时 l1 和 l2 中的一个可以是非空的，因此将非空列表连接到合并列表的末尾。
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
/*
递归
*/
public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists2(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists2(l1, l2.next);
return l2;
}
}
}
}
LeetCode22 括号生成
题目详情
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
代码
public class LeetCode22 {
public static void main(String[] args) {
System.out.println(new Solution().generateParenthesis(3));
}
static class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
backtrack(ans, "", 0, 0, n);
return ans;
}
private void backtrack(List<String> ans, String cur, int open, int close, int max) {
if (cur.length() == max * 2) {
ans.add(cur);
return;
}
if (open < max) {
backtrack(ans, cur + "(", open + 1, close, max);
}
if (close < open) {
backtrack(ans, cur + ")", open, close + 1, max);
}
}
}
}
LeetCode23 合并K个升序链表
题目详情
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
代码
public class LeetCode23 {
public static void main(String[] args) {
ListNode.printNode(new Solution().mergeKLists(new ListNode[]{
ListNode.buildNode(new int[]{1, 4, 5}),
ListNode.buildNode(new int[]{1, 3, 4}),
ListNode.buildNode(new int[]{2, 6})}
));
}
static class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || 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;
ListNode l1 = merge(lists, left, mid);
ListNode l2 = merge(lists, mid + 1, right);
return mergeTwoLists(l1, l2);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
}
LeetCode31 下一个排列
题目详情
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100
代码
public class LeetCode31 {
public static void main(String[] args) {
int[] nums = new int[]{1, 2, 3};
new Solution().nextPermutation(nums);
System.out.println(Arrays.stream(nums).boxed().collect(Collectors.toList()));
}
static class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i + 1] <= nums[i]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
private void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
