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]++;
                    else
                        height[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));
    }
}

输出：

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]]

代码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));
    }
}