1592.重新排列单词间的空格——easy

给你一个字符串 text ，该字符串由若干被空格包围的单词组成。每个单词由一个或者多个小写英文字母组成，并且两个单词之间至少存在一个空格。题目测试用例保证 text 至少包含一个单词 。

请你重新排列空格，使每对相邻单词之间的空格数目都 相等 ，并尽可能 最大化 该数目。如果不能重新平均分配所有空格，请 将多余的空格放置在字符串末尾 ，这也意味着返回的字符串应当与原 text 字符串的长度相等。

返回 重新排列空格后的字符串 。

示例 1：
**
输入：text = “ this is a sentence “
输出：”this is a sentence”
解释：总共有 9 个空格和 4 个单词。可以将 9 个空格平均分配到相邻单词之间，相邻单词间空格数为：9 / (4-1) = 3 个。

示例 2：
**
输入：text = “ practice makes perfect”
输出：”practice makes perfect “
解释：总共有 7 个空格和 3 个单词。7 / (3-1) = 3 个空格加上 1 个多余的空格。多余的空格需要放在字符串的末尾。

示例 3：
**
输入：text = “hello world”
输出：”hello world”

示例 4：
**
输入：text = “ walks udp package into bar a”
输出：”walks udp package into bar a “

示例 5：

输入：text = “a”
输出：”a”

提示：
**

  • 1 <= text.length <= 100
  • text 由小写英文字母和 ‘ ‘ 组成
  • text 中至少包含一个单词

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rearrange-spaces-between-words
思路：

  • 获取空格长度和单词个数。
  • 如果单词个数为1，则所有空格加到最后。
  • 如果单词个数不为1，则每个单词之间添加 (空格个数/(单词个数-1)) 个空格，结尾添加(空格个数/(单词个数-1))个空格。

复杂度分析：
时间复杂度O(n）
空间复杂度O(n)

  1. var reorderSpaces = function(text) {
  2.     let a = text.split(' ')
  3.     // split分割后的数组长度为 分隔符个数 + 1
  4.     let space = a.length - 1
  5.     let str = a.filter(item => item)
  6.     let n =str.length;
  7.     if(n===1){
  8.         text = str.join('') + ' '.repeat(space)
  9.     }else{
  10.         text = str.join(' '.repeat(space/(n-1))) + ' '.repeat(space%(n-1))
  11.     }
  12.     return text
  13. };

1593.拆分字符串使唯一子字符串的数目最大——medium

给你一个字符串 s ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。
字符串 s 拆分后可以得到若干 非空子字符串 ，这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是 唯一的 。
注意：子字符串 是字符串中的一个连续字符序列。

示例 1：
**
输入：s = “ababccc”
输出：5
解释：一种最大拆分方法为 [‘a’, ‘b’, ‘ab’, ‘c’, ‘cc’] 。像 [‘a’, ‘b’, ‘a’, ‘b’, ‘c’, ‘cc’] 这样拆分不满足题目要求，因为其中的 ‘a’ 和 ‘b’ 都出现了不止一次。

示例 2：
**
输入：s = “aba”
输出：2
解释：一种最大拆分方法为 [‘a’, ‘ba’] 。

示例 3：
**
输入：s = “aa”
输出：1
解释：无法进一步拆分字符串。

提示：

  • 1 <= s.length <= 16
  • s 仅包含小写英文字母

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-a-string-into-the-max-number-of-unique-substrings

思路：
二进制枚举每一次的分割方案，将分割好的字符串放进set中去重，当set.size大于答案时更新答案。这道题 n<=16，可做。
复杂度分析：
时间复杂度O(2n)
空间复杂度O(n)

/**
 * @param {string} s
 * @return {number}
 */
var maxUniqueSplit = function (s) {
    let n = s.length;
    let max = 1;
    for (let i = 0; i < (1 << n); i++) {
        let ans = 0;
        let set = new Set();
        let str = '';
        for (let j = 0; j < n; j++) {
            str += s[j];
            if ((i & (1 << j)) > 0) {
                ans++;
                set.add(str);
                str = '';
            }
        }
        if (str.length > 0) {
            ans++;
            set.add(str);
        }
        if (ans === set.size) {
            max = Math.max(max, ans);
        }

    }
    return max;
};

1594.矩阵的最大非负积——medium

给你一个大小为 rows x cols 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。

在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回 最大非负积 对 10 + 7 取余 的结果。如果最大积为负数，则返回 -1 。

注意，取余是在得到最大积之后执行的。

示例 1：
**
输入：grid = [[-1,-2,-3],
[-2,-3,-3],
[-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1

示例 2：
*
输入：grid = [[1,-2,1],
[1,-2,1],
[3,-4,1]]
输出：8
解释：最大非负积对应的路径已经用粗体标出 (1 1 -2 -4 * 1 = 8)

示例 3：
*
输入：grid = [[1, 3],
[0,-4]]
输出：0
解释：最大非负积对应的路径已经用粗体标出 (1 0 * -4 = 0)

示例 4：
*
输入：grid = [[ 1, 4,4,0],
[-2, 0,0,1],
[ 1,-1,1,1]]
输出：2
解释：最大非负积对应的路径已经用粗体标出 (1 -2 1 -1 1 1 = 2)

提示：

  • 1 <= rows, cols <= 15
  • -4 <= grid[i][j] <= 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-non-negative-product-in-a-matrix

思路：
用dp[i][j][0]表示(i,j)最大乘积，dp[i][j][1] 表示(i,j)最小乘积。
因为包含负数，dp[i][j][0]可能由左边的dp[i][j-1][0]乘正数的grid[i][j]得来，也可能由左边的dp[i][j-1][1]乘负数的grid[i][j] 得来。上方同理。dp[i][j][1]同理。
所以最后只需对dp[row-1][col-1][1]进行判断。

复杂度分析：
时间复杂度O(rowcol)
空间复杂度O(rowcol)

var maxProductPath = function (grid) {
    if (!grid.length && !grid[0].length) return -1;
    let row = grid.length;
    let col = grid[0].length;
    let dp = new Array(row).fill(undefined).map(() => {
        return new Array(col).fill(undefined).map(() => {
            return [-Infinity, Infinity];
        });
    });
    dp[0][0][0] = grid[0][0];
    dp[0][0][1] = grid[0][0];
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (i === 0 && j === 0) {
                continue;
            }
            if (i > 0) {
                dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][j][0] * grid[i][j], dp[i - 1][j][1] * grid[i][j]);
                dp[i][j][1] = Math.min(dp[i][j][1], dp[i - 1][j][0] * grid[i][j], dp[i - 1][j][1] * grid[i][j]);
            }
            if (j > 0) {
                dp[i][j][0] = Math.max(dp[i][j][0], dp[i][j - 1][0] * grid[i][j], dp[i][j - 1][1] * grid[i][j]);
                dp[i][j][1] = Math.min(dp[i][j][1], dp[i][j - 1][0] * grid[i][j], dp[i][j - 1][1] * grid[i][j]);
            }
        }
    }
    if (dp[row - 1][col - 1][0] < 0) {
        return -1;
    }
    let mod = 1e9 + 7;
    return dp[row - 1][col - 1][0] % mod;
};