目录

1. 最大矩形  🌟🌟🌟

2. 回文对  🌟🌟🌟

3. 给表达式添加运算符  🌟🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

1. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = [["0"]]
输出：0

示例 4：

输入：matrix = [["1"]]
输出：1

示例 5：

输入：matrix = [["0","0"]]
输出：0

提示：

• rows == matrix.length
• cols == matrix[0].length
• 0 <= row, cols <= 200
• matrix[i][j] 为 '0' 或 '1'

出处：

https://edu.csdn.net/practice/23165386

代码：

import java.util.List;
import java.util.Arrays;
public class maxRectangle {public static class Solution {public int maximalRectangle(char[][] matrix) {if (matrix == null || matrix.length == 0)return 0;int m = matrix.length;int n = matrix[0].length;int[] left = new int[n];int[] right = new int[n];int[] height = new int[n];Arrays.fill(right, n);int cur_left = 0;int cur_right = n;int res = 0;for (int i = 0; i < m; i++) {cur_left = 0;cur_right = n;for (int j = 0; j < n; j++) {if (matrix[i][j] == '1')height[j]++;elseheight[j] = 0;}for (int j = 0; j < n; j++) {if (matrix[i][j] == '1') {left[j] = Math.max(left[j], cur_left);} else {left[j] = 0;cur_left = j + 1;}}for (int j = n - 1; j >= 0; j--) {if (matrix[i][j] == '1') {right[j] = Math.min(right[j], cur_right);} else {right[j] = n;cur_right = j;}}for (int j = 0; j < n; j++)res = Math.max(res, (right[j] - left[j]) * height[j]);}return res;}}public static void main(String[] args) {Solution s = new Solution();char[][] matrix = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};System.out.println(s.maximalRectangle(matrix));}
}

输出：

6

import java.util.Deque;
import java.util.LinkedList;
public class maxRectangle {public static class Solution {public int maximalRectangle(char[][] matrix) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return 0;}int m = matrix.length, n = matrix[0].length;int[] heights = new int[n];int ans = 0;for (int i = 0; i < m; ++i) {// 更新高度数组for (int j = 0; j < n; ++j) {if (matrix[i][j] == '1') {heights[j] += 1;} else {heights[j] = 0;}}// 计算最大矩形面积ans = Math.max(ans, largestRectangleArea(heights));}return ans;}private int largestRectangleArea(int[] heights) {int n = heights.length;int[] left = new int[n];int[] right = new int[n];Deque<Integer> stack = new LinkedList<>();// 计算 left 数组for (int i = 0; i < n; ++i) {while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {stack.pop();}left[i] = stack.isEmpty() ? -1 : stack.peek();stack.push(i);}stack.clear();// 计算 right 数组for (int i = n - 1; i >= 0; --i) {while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {stack.pop();}right[i] = stack.isEmpty() ? n : stack.peek();stack.push(i);}// 计算最大矩形面积int ans = 0;for (int i = 0; i < n; ++i) {ans = Math.max(ans, heights[i] * (right[i] - left[i] - 1));}return ans;}}public static void main(String[] args) {Solution s = new Solution();char[][] matrix = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};System.out.println(s.maximalRectangle(matrix));}
}

用一个一维数组 heights 来记录当前行中以每个元素为底的最大连续 1 的个数。

然后，对每一行都计算其最大矩形面积，并更新答案。

计算最大矩形面积的算法如下：

定义一个栈 stack 和两个数组 left 和 right，其中 left[i] 表示第 i 个元素左边第一个小于它的元素的下标，right[i] 表示第 i 个元素右边第一个小于它的元素的下标；

1. 从左到右遍历 heights 数组，对每个元素 heights[i]，执行以下操作：

如果栈为空或者栈顶元素对应的高度小于等于当前元素的高度，则将当前元素的下标入栈；
否则，弹出栈顶元素，更新 left[i] 为栈顶元素的下标，直到栈为空或者栈顶元素对应的高度小于当前元素的高度，然后将当前元素的下标入栈；

2. 从右到左遍历 heights 数组，对每个元素 heights[i]，执行以下操作：

如果栈为空或者栈顶元素对应的高度小于等于当前元素的高度，则将当前元素的下标入栈；
否则，弹出栈顶元素，更新 right[i] 为栈顶元素的下标，直到栈为空或者栈顶元素对应的高度小于当前元素的高度，然后将当前元素的下标入栈；

3. 最后，遍历 heights 数组，计算每个元素对应的最大矩形面积 heights[i] * (right[i] - left[i] - 1)，并更新答案； 返回答案。

2. 回文对

给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

示例 1：

输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]] 
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]

示例 2：

输入：words = ["bat","tab","cat"]
输出：[[0,1],[1,0]] 
解释：可拼接成的回文串为 ["battab","tabbat"]

示例 3：

输入：words = ["a",""]
输出：[[0,1],[1,0]]

提示：

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] 由小写英文字母组成

出处：

https://edu.csdn.net/practice/23165387

代码1：

import java.util.*;
public class palindromePairs {public static class Solution {private static List<List<Integer>> ans = new ArrayList<>();public List<List<Integer>> palindromePairs(String[] words) {if (words == null || words.length == 0) {return null;}ans = new ArrayList<>();TrieNode root = new TrieNode();for (int i = 0; i < words.length; i++) {addWord(root, words[i], i);}for (int i = 0; i < words.length; i++) {find(root, words[i], i);}return ans;}private static class TrieNode {int index;TrieNode[] next;List<Integer> palindIndex;public TrieNode() {index = -1;next = new TrieNode[26];palindIndex = new ArrayList<>();}}private static void addWord(TrieNode root, String word, int index) {for (int i = word.length() - 1; i >= 0; i--) {int ch = word.charAt(i) - 'a';if (root.next[ch] == null) {root.next[ch] = new TrieNode();}if (isPalindrome(word, 0, i)) {root.palindIndex.add(index);}root = root.next[ch];}root.index = index;root.palindIndex.add(index);}private static void find(TrieNode root, String word, int index) {for (int i = 0; i < word.length(); i++) {if (root.index != -1 && root.index != index && isPalindrome(word, i, word.length() - 1)) {ans.add(Arrays.asList(index, root.index));}if (root.next[word.charAt(i) - 'a'] == null) {return;}root = root.next[word.charAt(i) - 'a'];}for (int i : root.palindIndex) {if (i != index) {ans.add(Arrays.asList(index, i));}}}private static boolean isPalindrome(String string, int l, int r) {while (l < r) {if (string.charAt(l++) != string.charAt(r--)) {return false;}}return true;}}public static void main(String[] args) {Solution s = new Solution();String[] words = {"abcd","dcba","lls","s","sssll"};System.out.println(s.palindromePairs(words));String[] words1 = {"bat","tab","cat"};System.out.println(s.palindromePairs(words1));String[] words2 = {"a",""};System.out.println(s.palindromePairs(words2));}
}

输出：

[[0, 1], [1, 0], [2, 4], [3, 2]]
[[0, 1], [1, 0]]
[[0, 1], [1, 0]]

代码2：

思路：遍历单词列表，对于每个单词，将其拆分成左右两个部分，如果左边是回文串，那么找右边的逆序单词是否在单词列表中，如果在，则说明当前单词可以和右边的逆序单词拼接成回文串。同理，如果右边是回文串，那么找左边的逆序单词是否在单词列表中。

import java.util.*;
public class palindromePairs {public static class Solution {public List<List> palindromePairs(String[] words) {List<List> res = new ArrayList<>();if (words == null || words.length < 2) return res;Map<String, Integer> map = new HashMap<>();for (int i = 0; i < words.length; i++) {map.put(words[i], i);}for (int i = 0; i < words.length; i++) {String word = words[i];for (int j = 0; j <= word.length(); j++) {String left = word.substring(0, j);String right = word.substring(j);if (isPalindrome(left)) {String reverseRight = new StringBuilder(right).reverse().toString();if (map.containsKey(reverseRight) && map.get(reverseRight) != i) {res.add(Arrays.asList(map.get(reverseRight), i));}}if (isPalindrome(right)) {String reverseLeft = new StringBuilder(left).reverse().toString();if (map.containsKey(reverseLeft) && map.get(reverseLeft) != i && right.length() != 0) {res.add(Arrays.asList(i, map.get(reverseLeft)));}}}}return res;}private boolean isPalindrome(String s) {int left = 0, right = s.length() - 1;while (left < right) {if (s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;}}public static void main(String[] args) {Solution s = new Solution();String[] words = {"abcd","dcba","lls","s","sssll"};System.out.println(s.palindromePairs(words));String[] words1 = {"bat","tab","cat"};System.out.println(s.palindromePairs(words1));String[] words2 = {"a",""};System.out.println(s.palindromePairs(words2));}
}

输出：

[[1, 0], [0, 1], [3, 2], [2, 4]]
[[1, 0], [0, 1]]
[[0, 1], [1, 0]]

3. 给表达式添加运算符

给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。

示例 1:

输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"] 

示例 2:

输入: num = "232", target = 8
输出: ["2*3+2", "2+3*2"]

示例 3:

输入: num = "105", target = 5
输出: ["1*0+5","10-5"]

示例 4:

输入: num = "00", target = 0
输出: ["0+0", "0-0", "0*0"]

示例 5:

输入: num = "3456237490", target = 9191
输出: []

提示：

• 1 <= num.length <= 10
• num 仅含数字
• -2^31 <= target <= 2^31 - 1

出处：

https://edu.csdn.net/practice/23165388

代码1：

import java.util.*;
public class addOperators {public static class Solution {int n;String num;List<String> ans;int target;public List<String> addOperators(String num, int target) {this.n = num.length();this.num = num;this.target = target;this.ans = new ArrayList<String>();StringBuffer expr = new StringBuffer();dfs(expr, 0, 0, 0);return ans;}private void dfs(StringBuffer sba, long sum, long prepareMultiply, int index) {StringBuffer sb = new StringBuffer(sba);if (index == n) {if (sum == target) {ans.add(sb.toString());}return;}int sign = sb.length();if (index > 0) {sb.append("0");}long val = 0;for (int i = index; i < n && (i == index || num.charAt(index) != '0'); i++) {val = val * 10 + (num.charAt(i) - '0');sb.append(num.charAt(i));if (index == 0) {dfs(sb, val, val, i + 1);continue;}sb.setCharAt(sign, '+');dfs(sb, sum + val, val, i + 1);sb.setCharAt(sign, '-');dfs(sb, sum - val, -val, i + 1);sb.setCharAt(sign, '*');dfs(sb, sum - prepareMultiply + prepareMultiply * val, prepareMultiply * val, i + 1);}}}public static void main(String[] args) {Solution s = new Solution();s.num = "123";s.target = 6;System.out.println(s.addOperators(s.num, s.target));s.num = "232";s.target = 8;System.out.println(s.addOperators(s.num, s.target));s.num = "105";s.target = 5;System.out.println(s.addOperators(s.num, s.target));}
}

输出：

[1+2+3, 1*2*3]
[2+3*2, 2*3+2]
[1*0+5, 10-5]

代码2：

import java.util.*;
public class addOperators {public static class Solution {int n;String num;List<String> ans;int target;public List<String> addOperators(String num, int target) {List<String> res = new ArrayList<>();if (num == null || num.length() == 0) {return res;}dfs(num, target, "", 0, 0, 0, res);return res;}private void dfs(String num, int target, String path, int pos, long eval, long multed, List<String> res) {if (pos == num.length()) {if (eval == target) {res.add(path);}return;}for (int i = pos; i < num.length(); i++) {if (i != pos && num.charAt(pos) == '0') {break;}long cur = Long.parseLong(num.substring(pos, i + 1));if (pos == 0) {dfs(num, target, path + cur, i + 1, cur, cur, res);} else {dfs(num, target, path + "+" + cur, i + 1, eval + cur, cur, res);dfs(num, target, path + "-" + cur, i + 1, eval - cur, -cur, res);dfs(num, target, path + "*" + cur, i + 1, eval - multed + multed * cur, multed * cur, res);}}}}public static void main(String[] args) {Solution s = new Solution();System.out.println(s.addOperators("123", 6));System.out.println(s.addOperators("232", 8));System.out.println(s.addOperators("105", 5));}
}

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏

周公解梦