package algorithm;

import java.util.*;

/**

* @ClassName Week6

* @Description

* @Author Administrator

* @Date 2020/12/20 21:30

* @Version 1.0

**/

public class Week6 {

/**

* 本周作业及下周预习

* *****************************************************************************************************************

* 本周作业

* 中等

* 最小路径和（亚马逊、高盛集团、谷歌在半年内面试中考过）

* 解码方法（亚马逊、Facebook、字节跳动在半年内面试中考过）

* 最大正方形（华为、谷歌、字节跳动在半年内面试中考过）

* 任务调度器（Facebook 在半年内面试中常考）

* 回文子串（Facebook、苹果、字节跳动在半年内面试中考过）

* 困难

* 最长有效括号（字节跳动、亚马逊、微软在半年内面试中考过）

* 编辑距离（字节跳动、亚马逊、谷歌在半年内面试中考过）

* 矩形区域不超过 K 的最大数值和（谷歌在半年内面试中考过）

* 青蛙过河（亚马逊、苹果、字节跳动在半年内面试中考过）

* 分割数组的最大值（谷歌、亚马逊、Facebook 在半年内面试中考过）

* 学生出勤记录 II （谷歌在半年内面试中考过）

* 最小覆盖子串（Facebook 在半年内面试中常考）

* 戳气球（亚马逊在半年内面试中考过）

* 下周预习

* 预习题目：

* 实现 Trie (前缀树)

* 单词搜索 II

* 岛屿数量

* 有效的数独

* N 皇后

* 单词接龙

* 二进制矩阵中的最短路径

*/

/**

* 62. 不同路径

* 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

* 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

* 问总共有多少条不同的路径？

* *****************************************************************************************************************

* 超哥方法1

*/

public int uniquePaths(int m, int n) {

int[][] dp = new int[m][n];

for (int i = 0; i < m; ++i) dp[i][0] = 1;

for (int j = 0; j < n; ++j) dp[0][j] = 1;

for (int i = 1; i < m; ++i) {

for (int j = 1; j < n; ++j) {

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

}

}

return dp[m - 1][n - 1];

}

/**

* 超哥方法2

* 从上往下 && 从左往右 循环

*/

public int uniquePaths2(int m, int n) {

int[][] dp = new int[m][n]; //从<start>走到(i,j)的不同路径数

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (i == 0 || j == 0)

dp[i][j] = 1;

else

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

}

}

return dp[m - 1][n - 1];

}

/**

* 超哥方法3

* 从下往上 && 从右往左 循环

*/

public int uniquePaths3(int m, int n) {

int[][] dp = new int[m][n]; //从(i,j)走到end的不同路径数

for (int i = m - 1; i >= 0; i--) {

for (int j = n - 1; j >= 0; j--) {

if (i == m - 1 || j == n - 1)

dp[i][j] = 1;

else

dp[i][j] = dp[i + 1][j] + dp[i][j + 1];

}

}

return dp[0][0];

}

/**

* 方法4

*/

public int uniquePaths4(int m, int n) {

int[] cur = new int[n];

Arrays.fill(cur, 1);

for (int i = 1; i < m; ++i) {

for (int j = 1; j < n; ++j) {

cur[j] += cur[j - 1];

}

}

return cur[n - 1];

}

/**

* 63. 不同路径 II （谷歌、美团、微软在半年内面试中考过）

* 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

* 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

* 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

* 网格中的障碍物和空位置分别用 1 和 0 来表示。

* 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

* 输出：2

* *****************************************************************************************************************

* 超哥的方法:

*/

public int uniquePathsWithObstacles(int[][] obstacleGrid) {

int m = obstacleGrid.length;

int n = obstacleGrid[0].length;

int[] dp = new int[n + 1];

dp[1] = 1;

for (int i = 0; i < m; i++) {

for (int j = 1; j <= n; j++) {

if (obstacleGrid[i][j - 1] == 1) { //障碍物

dp[j] = 0;

} else {

dp[j] = dp[j] + dp[j - 1]; //dp[i - 1][j] + dp[i][j - 1];

}

}

}

return dp[n];

}

public int uniquePathsWithObstacles2(int[][] obstacleGrid) {

int width = obstacleGrid[0].length;

int[] dp = new int[width];

dp[0] = 1;

for (int[] row : obstacleGrid) {

for (int j = 0; j < width; j++) {

if (row[j] == 1)

dp[j] = 0;

else if (j > 0)

dp[j] += dp[j - 1];

}

}

return dp[width - 1];

}

/**

* 1143. 最长公共子序列

* 给定两个字符串text1 和 text2，返回这两个字符串的最长公共子序列的长度。

* 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

* 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

* 若这两个字符串没有公共子序列，则返回 0。

* 输入：text1 = "abcde", text2 = "ace"

* 输出：3

* https://leetcode.com/problems/longest-common-subsequence/discuss/351689/JavaPython-3-Two-DP-codes-of-O(mn)-and-O(min(m-n))-spaces-w-picture-and-analysis

* 这边加一的目的是为了让索引为0的行和列表示空串，不需要额外限制条件去确保index是否是有效的

*/

public int longestCommonSubsequence(String s1, String s2) {

int[][] dp = new int[s1.length() + 1][s2.length() + 1];

for (int i = 0; i < s1.length(); ++i)

for (int j = 0; j < s2.length(); ++j)

if (s1.charAt(i) == s2.charAt(j)) dp[i + 1][j + 1] = 1 + dp[i][j];

else dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);

return dp[s1.length()][s2.length()];

}

/**

* 5 easy steps to DP

* ① define subproblems

* ② guess (part of solution)

* ③ relate subproblem solutions

* ④ recurse & memorize OR build DP table bottom-up

* ⑤ solve original problem

* MIT 动态规划课程最短路径算法

* https://www.bilibili.com/video/av53233912?from=search&seid=2847395688604491997

*/

/**

* 例如：s1="abcde"　　s2= "ace"，求两个字符串的公共子序列，答案是“ace”

* 1.　S{s1,s2,s3....si} T{t1,t2,t3,t4....tj}

* 2.　子问题划分

* (1) 如果S的最后一位等于T的最后一位，则最大子序列就是{s1,s2,s3...si-1}和{t1,t2,t3...tj-1}的最大子序列+1

* (2) 如果S的最后一位不等于T的最后一位，那么最大子序列就是

* ① {s1,s2,s3..si}和 {t1,t2,t3...tj-1} 最大子序列

* ② {s1,s2,s3...si-1}和{t1,t2,t3....tj} 最大子序列

* 以上两个自序列的最大值

* 3.　边界

* 只剩下{s1}和{t1}，如果相等就返回1，不等就返回0

* 4.　使用一个表格来存储dp的结果

* 如果 S[i] == T[j] 则dp[i][j] = dp[i-1][j-1] + 1

* 否则dp[i][j] = max(dp[i][j-1],dp[i-1][j])

* *****************************************************************************************************************

* 链接：https://leetcode-cn.com/problems/longest-common-subsequence/solution/chao-xiang-xi-dong-tai-gui-hua-jie-fa-by-shi-wei-h/

*/

public int longestCommonSubsequence2(String text1, String text2) {

char[] s1 = text1.toCharArray();

char[] s2 = text2.toCharArray();

int[][] dp = new int[s1.length + 1][s2.length + 1];

for (int i = 1; i < s1.length + 1; i++) {

for (int j = 1; j < s2.length + 1; j++) {

//如果末端相同

if (s1[i - 1] == s2[j - 1]) {

dp[i][j] = dp[i - 1][j - 1] + 1;

} else {

//如果末端不同

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

}

}

}

return dp[s1.length][s2.length];

}

/**

* https://leetcode.com/problems/longest-common-subsequence/discuss/351689/JavaPython-3-Two-DP-codes-of-O(mn)-and-O(min(m-n))-spaces-w-picture-and-analysis

*/

public int longestCommonSubsequence3(String s1, String s2) {

int m = s1.length(), n = s2.length();

if (m < n) return longestCommonSubsequence(s2, s1);

int[][] dp = new int[2][n + 1];

for (int i = 0, k = 1; i < m; ++i, k ^= 1)

for (int j = 0; j < n; ++j)

if (s1.charAt(i) == s2.charAt(j)) dp[k][j + 1] = 1 + dp[k ^ 1][j];

else dp[k][j + 1] = Math.max(dp[k ^ 1][j + 1], dp[k][j]);

return dp[m % 2][n];

}

/**

* https://leetcode.com/problems/longest-common-subsequence/discuss/351689/JavaPython-3-Two-DP-codes-of-O(mn)-and-O(min(m-n))-spaces-w-picture-and-analysis

*/

public int longestCommonSubsequence4(String text1, String text2) {

int m = text1.length(), n = text2.length();

if (m < n) {

return longestCommonSubsequence(text2, text1);

}

int[] dp = new int[n + 1];

for (int i = 0; i < text1.length(); ++i) {

for (int j = 0, prevRow = 0, prevRowPrevCol = 0; j < text2.length(); ++j) {

prevRowPrevCol = prevRow;

prevRow = dp[j + 1];

dp[j + 1] = text1.charAt(i) == text2.charAt(j) ? prevRowPrevCol + 1 : Math.max(dp[j], prevRow);

}

}

return dp[n];

}

/**

* 递归代码模版

* public void recur(int level, int param) {

* // terminator

* if (level > MAX_LEVEL) {

* // process result

* return;

* }

* // process current logic

* process(level, param);

* // drill down

* recur( level: level + 1, newParam);

* // restore current status

* }

*/

/**

* 分治代码模板

* def divide_conquer(problem, param1, param2, ...):

* # recursion terminator

* if problem is None:

* print_result

* return

*

* # prepare data

* data = prepare_data(problem)

* subproblems = split_problem(problem, data)

*

* # conquer subproblems

* subresult1 = self.divide_conquer(subproblems[0], p1, ...)

* subresult2 = self.divide_conquer(subproblems[1], p1, ...)

* subresult3 = self.divide_conquer(subproblems[2], p1, ...)

* …

*

* # process and generate the final result

* result = process_result(subresult1, subresult2, subresult3, …)

* # revert the current level states

*

* 感触

* 1. 人肉递归低效、很累

* 2. 找到最近最简方法，将其拆解成可重复解决的问题

* 3. 数学归纳法思维（抵制人肉递归的诱惑）

* 本质：寻找重复性 —> 计算机指令集

*/

/**

*

* 动态规划 Dynamic Programming

* 1. Wiki 定义：

* https://en.wikipedia.org/wiki/Dynamic_programming

* 2.“Simplifying a complicated problem by breaking it down into

* simpler sub-problems”

* (in a recursive manner)

* 3.Divide & Conquer + Optimal substructure

* 分治 + 最优子结构

* *****************************************************************************************************************

* 关键点

* 动态规划 和 递归或者分治 没有根本上的区别（关键看有无最优的子结构）

* 共性：找到重复子问题

* 差异性：最优子结构、中途可以淘汰次优解

* *****************************************************************************************************************

* 状态转移方程（DP 方程）

* opt[i , j] = opt[i + 1, j] + opt[i, j + 1]

* 完整逻辑：

* if a[i, j] = ‘空地’:

* opt[i , j] = opt[i + 1, j] + opt[i, j + 1]

* else:

* opt[i , j] = 0

* *****************************************************************************************************************

* 实战例题二

* 路径计数 Count the paths

* 动态规划关键点

* 1. 最优子结构 opt[n] = best_of(opt[n-1], opt[n-2], …)

* 2. 储存中间状态：opt[i]

* 3. 递推公式（美其名曰：状态转移方程或者 DP 方程）

* Fib: opt[i] = opt[n-1] + opt[n-2]

* 二维路径：opt[i,j] = opt[i+1][j] + opt[i][j+1] (且判断a[i,j]是否空地）

* *****************************************************************************************************************

* 实战例题三

* 最长公共子序列

* 子问题

* • S1 = “ABAZDC”

* S2 = “BACBAD”

* • If S1[-1] != S2[-1]: LCS[s1, s2] = Max(LCS[s1-1, s2], LCS[s1, s2-1])

* LCS[s1, s2] = Max(LCS[s1-1, s2], LCS[s1, s2-1], LCS[s1-1, s2-1])

* • If S1[-1] == S2[-1]: LCS[s1, s2] = LCS[s1-1, s2-1] + 1

* LCS[s1, s2] = Max(LCS[s1-1, s2], LCS[s1, s2-1], LCS[s1-1, s2-1], LCS[s1-1][s2-1] + 1)

* *****************************************************************************************************************

* DP 方程

* • If S1[-1] != S2[-1]: LCS[s1, s2] = Max(LCS[s1-1, s2], LCS[s1, s2-1])

* • If S1[-1] == S2[-1]: LCS[s1, s2] = LCS[s1-1, s2-1] + 1

* 动态规划小结

* 1. 打破自己的思维惯性，形成机器思维

* 2. 理解复杂逻辑的关键

* 3. 也是职业进阶的要点要领

* MIT algorithm course

* B 站搜索： mit 动态规划

* https://www.bilibili.com/video/av53233912?from=search&seid=2847395688604491997

*/

/**

* 64. 最小路径和（亚马逊、高盛集团、谷歌在半年内面试中考过）

* 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

* 说明：每次只能向下或者向右移动一步。

* 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]

* 输出：7

* 解释：因为路径 1→3→1→1→1 的总和最小。

* https://leetcode-cn.com/problems/minimum-path-sum/solution/zui-xiao-lu-jing-he-dong-tai-gui-hua-gui-fan-liu-c/

* *****************************************************************************************************************

* 第5周 第12课 | 动态规划（一）

* 2. DP例题解析：Fibonacci数列、路径计数

* 所谓最优子结构：推导出的第n步的值，是前面几个值的最佳值的简单累加，或者最大值，或者最小值。

* 状态转移方程(DP方程)

* opt[i,j] = opt[i+1,j] + opt[i,j+1]

* 完整逻辑:

* if a[i,j] ='空地' :

* opt[i,j] = opt[i+1,j] + opt[i,j+1]

* else :

* opt[i,j] = 0

* 动态规划关键点

*/

public int minPathSum(int[][] grid) {

for (int i = 0; i < grid.length; i++) {

for (int j = 0; j < grid[0].length; j++) {

if (i == 0 && j == 0) continue;

else if (i == 0) grid[i][j] = grid[i][j - 1] + grid[i][j];

else if (j == 0) grid[i][j] = grid[i - 1][j] + grid[i][j];

else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];

}

}

return grid[grid.length - 1][grid[0].length - 1];

}

/**

* 64. Minimum Path Sum

*/

public int minPathSum2(int[][] grid) {

int row = grid.length - 1;

int col = grid[0].length - 1;

int[][] dp = new int[row + 1][col + 1];

return minPathSum(grid, row, col, dp);

}

public int minPathSum(int[][] grid, int row, int col, int[][] dp) {

if (row == 0 && col == 0) return grid[row][col];

if (dp[row][col] != 0) return dp[row][col];

if (row != 0 && col == 0) return dp[row][col] = grid[row][col] + minPathSum(grid, row - 1, col, dp);

if (row == 0 && col != 0) return dp[row][col] = grid[row][col] + minPathSum(grid, row, col - 1, dp);

return dp[row][col] = grid[row][col] + Math.min(minPathSum(grid, row - 1, col, dp), minPathSum(grid, row, col - 1, dp));

}

/**

* I had been struggling for recursive and DP problems before. But now I feeling like I am getting better.

* This is a simple explanations for those who are still not that good at these just like me.

* 1.Recursion:

* So basically let's begin with recursion because it is easier to understand and code. When we think about this problem, we could use a top down approach. To get a path, we need to travel from grid[0][0] to grid[row - 1][col - 1]. So let's set grid[0][0] as the basic case. This is when we jump out of recursion. On the other hand, grid[row - 1][col - 1] would be the starting point. We write a helper function to do the recursion work. At the starting point, this function returns (value of the end cell + value of the cell that has the less one). But we need to consider that things could happen that we reached the first row or column and we gotta make sure that we stay within the array index limit.

* At last, when we reach grid[0][0], we are done!

* 2.Dynamic Programming:

* Now, let's upgrade this algorithm from recursion to DP since we don't wanna get stackoverflow for large inputs.In fact, there is nothing fancy about DP.

* It is simply that we store or cache the results of every single calculation so that we don't need to calculate the same thing again and again.

* The whole idea is almost the same. We just involve an array to store the values. Now let's see the code:

*/

public int minPathSum3(int[][] grid) {

int height = grid.length;

int width = grid[0].length;

return min(grid, height - 1, width - 1);

}

public int min(int[][] grid, int row, int col) {

if (row == 0 && col == 0) return grid[row][col]; // this is the exit of the recursion

if (row == 0)

return grid[row][col] + min(grid, row, col - 1); /** when we reach the first row, we could only move horizontally.*/

if (col == 0)

return grid[row][col] + min(grid, row - 1, col); /** when we reach the first column, we could only move vertically.*/

return grid[row][col] + Math.min(min(grid, row - 1, col), min(grid, row, col - 1)); /** we want the min sum path so we pick the cell with the less value */

}

public static int minPathSum4(int[][] grid) {

int height = grid.length;

int width = grid[0].length;

for (int row = 0; row < height; row++) {

for (int col = 0; col < width; col++) {

if (row == 0 && col == 0) grid[row][col] = grid[row][col];

else if (row == 0 && col != 0) grid[row][col] = grid[row][col] + grid[row][col - 1];

else if (col == 0 && row != 0) grid[row][col] = grid[row][col] + grid[row - 1][col];

else grid[row][col] = grid[row][col] + Math.min(grid[row - 1][col], grid[row][col - 1]);

}

}

return grid[height - 1][width - 1];

}

/**

* 方法一：动态规划

* 由于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。

* 对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，因此可以使用动态规划求解。

* 创建二维数组 dp，与原始网格的大小相同，dp[i][j] 表示从左上角出发到 (i,j) 位置的最小路径和。显然，dp[0][0]=grid[0][0]。对于 dp 中的其余元素，通过以下状态转移方程计算元素值。

* 当 i>0 且 j=0 时，dp[i][0]=dp[i−1][0]+grid[i][0]。

* 当 i=0 且 j>0 时，dp[0][j]=dp[0][j−1]+grid[0][j]。

* 当 i>0 且 j>0 时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]。

* 最后得到 dp[m−1][n−1] 的值即为从网格左上角到网格右下角的最小路径和。

* *****************************************************************************************************************

* 复杂度分析

* 时间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。需要对整个网格遍历一次，计算 dp 的每个元素的值。

* 空间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。创建一个二维数组 dp，和网格大小相同。

* 空间复杂度可以优化，例如每次只存储上一行的 dp 值，则可以将空间复杂度优化到 O(n)。

* *****************************************************************************************************************

* 链接：https://leetcode-cn.com/problems/minimum-path-sum/solution/zui-xiao-lu-jing-he-by-leetcode-solution/

*/

public int minPathSum5(int[][] grid) {

if (grid == null || grid.length == 0 || grid[0].length == 0) {

return 0;

}

int rows = grid.length, columns = grid[0].length;

int[][] dp = new int[rows][columns];

dp[0][0] = grid[0][0];

for (int i = 1; i < rows; i++) {

dp[i][0] = dp[i - 1][0] + grid[i][0];

}

for (int j = 1; j < columns; j++) {

dp[0][j] = dp[0][j - 1] + grid[0][j];

}

for (int i = 1; i < rows; i++) {

for (int j = 1; j < columns; j++) {

dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];

}

}

return dp[rows - 1][columns - 1];

}

/**

* 91. 解码方法（亚马逊、Facebook、字节跳动在半年内面试中考过）

* 一条包含字母 A-Z 的消息通过以下方式进行了编码：

* 'A' -> 1

* 'B' -> 2

* ...

* 'Z' -> 26

* 给定一个只包含数字的非空字符串，请计算解码方法的总数。

* 题目数据保证答案肯定是一个 32 位的整数。

* *****************************************************************************************************************

* I optimize this answer by removing convert Char to Integer, and beats 98% solution:

*/

public int numDecodings2(String s) {

if (s == null || s.length() == 0) {

return 0;

}

int[] dp = new int[s.length()];

dp[0] = s.charAt(0) == '0' ? 0 : 1;

for (int i = 1; i < s.length(); i++) {

int cur = s.charAt(i) - '0';

int pre = (s.charAt(i - 1) - '0') * 10 + cur;

if (cur != 0) {

dp[i] += dp[i - 1];

}

if (pre >= 10 && pre <= 26) {

dp[i] += i >= 2 ? dp[i - 2] : 1;

}

}

return dp[s.length() - 1];

}

/**

* https://leetcode.com/problems/decode-ways/discuss/30358/Java-clean-DP-solution-with-explanation

* *****************************************************************************************************************

* Java clean DP solution with explanation

* I used a dp array of size n + 1 to save subproblem solutions.

* dp[0] means an empty string will have one way to decode, dp[1] means the way to decode a string of size 1.

* I then check one digit and two digit combination and save the results along the way.

* In the end, dp[n] will be the end result.

* *****************************************************************************************************************

* Similar questions:

* 62. Unique Paths

* 70. Climbing Stairs

* 509. Fibonacci Number

* https://leetcode.com/problems/unique-paths/

* https://leetcode.com/problems/climbing-stairs/

* https://leetcode.com/problems/fibonacci-number/

* *****************************************************************************************************************

*/

public int numDecodings(String s) {

if (s == null || s.length() == 0) {

return 0;

}

int n = s.length();

int[] dp = new int[n + 1];

dp[0] = 1;

dp[1] = s.charAt(0) != '0' ? 1 : 0;

for (int i = 2; i <= n; i++) {

int first = Integer.parseInt(s.substring(i - 1, i));

int second = Integer.parseInt(s.substring(i - 2, i));

if (first >= 1 && first <= 9) {

dp[i] += dp[i - 1];

}

if (second >= 10 && second <= 26) {

dp[i] += dp[i - 2];

}

}

return dp[n];

}

/**

* 221. 最大正方形（华为、谷歌、字节跳动在半年内面试中考过）

* 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

* 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

* 输出：4

* 方法二：动态规划

* 方法一虽然直观，但是时间复杂度太高，有没有办法降低时间复杂度呢？

* 可以使用动态规划降低时间复杂度。我们用 dp(i, j) 表示以 (i, j) 为右下角，且只包含 1 的正方形的边长最大值。如果我们能计算出所有 dp(i, j) 的值，那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。

* 那么如何计算 dp 中的每个元素值呢？对于每个位置 (i, j)，检查在矩阵中该位置的值：

* 如果该位置的值是 0，则 dp(i, j) = 0，因为当前位置不可能在由 1 组成的正方形中；

* 如果该位置的值是 1，则 dp(i, j) 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：

* dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1

* 如果读者对这个状态转移方程感到不解，可以参考 1277. 统计全为 1 的正方形子矩阵的官方题解，其中给出了详细的证明。

* 此外，还需要考虑边界条件。如果 i 和 j 中至少有一个为 0，则以位置 (i, j) 为右下角的最大正方形的边长只能是 1，因此 dp(i, j) = 1。

* 链接：https://leetcode-cn.com/problems/maximal-square/solution/zui-da-zheng-fang-xing-by-leetcode-solution/

*/

public int maximalSquare(char[][] matrix) {

int maxSide = 0;

if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {

return maxSide;

}

int rows = matrix.length, columns = matrix[0].length;

int[][] dp = new int[rows][columns];

for (int i = 0; i < rows; i++) {

for (int j = 0; j < columns; j++) {

if (matrix[i][j] == '1') {

if (i == 0 || j == 0) {

dp[i][j] = 1;

} else {

dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;

}

maxSide = Math.max(maxSide, dp[i][j]);

}

}

}

return maxSide * maxSide;

}

/**

*

* *****************************************************************************************************************

* 理解 min(上, 左, 左上) + 1

* 如题，在其他动态规划方法的题解中，大都会涉及到下列形式的代码：

* // 伪代码

* if (matrix(i - 1, j - 1) == '1') {

* dp(i, j) = min(dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1)) + 1;

* }

* 其中，dp(i, j) 是以 matrix(i - 1, j - 1) 为 右下角 的正方形的最大边长。(感谢 @liweiwei1419 提出补充)

* 等同于：dp(i + 1, j + 1) 是以 matrix(i, j) 为右下角的正方形的最大边长

* 翻译成中文

* 若某格子值为 1，则以此为右下角的正方形的、最大边长为：上面的正方形、左面的正方形或左上的正方形中，最小的那个，再加上此格。

* 先来阐述简单共识

* 若形成正方形（非单 1），以当前为右下角的视角看，则需要：当前格、上、左、左上都是 1

* 可以换个角度：当前格、上、左、左上都不能受 0 的限制，才能成为正方形

* 图解如下链接所示

* https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/

* 上面详解了 三者取最小 的含义：

* 图 1：受限于左上的 0

* 图 2：受限于上边的 0

* 图 3：受限于左边的 0

* 数字表示：以此为正方形右下角的最大边长

* 黄色表示：格子 ? 作为右下角的正方形区域

* 就像 木桶的短板理论 那样——附近的最小边长，才与 ? 的最长边长有关。

* 此时已可得到递推公式

* // 伪代码

* if (grid[i - 1][j - 1] == '1') {

* dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;

* }

* *****************************************************************************************************************

* 从感性理解，到代码实现

* 从上述图解中，我们似乎得到的只是「动态规划 推进 的过程」，即「如何从前面的 dp 推出后面的 dp」，甚至还只是感性理解

* 距离代码我们还缺：dp 具体定义如何，数组多大，初值如何，如何与题目要求的面积相关

* dp 具体定义：dp[i + 1][j + 1] 表示 「以第 i 行、第 j 列为右下角的正方形的最大边长」

* 为何不是 dp[i][j]

* 回到图解中，任何一个正方形，我们都「依赖」当前格 左、上、左上三个方格的情况

* 但第一行的上层已经没有格子，第一列左边已经没有格子，需要做特殊 if 判断来处理

* 为了代码简洁，我们 假设补充 了多一行全 '0'、多一列全 '0'

* 如下链接所示

* 链接：https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/

* 此时 dp 数组的大小也明确为 new dp[height + 1][width + 1]

* 初始值就是将第一列 dp[row][0] 、第一行 dp[0][col] 都赋为 0，相当于已经计算了所有的第一行、第一列的 dp 值

* 题目要求面积。根据 「面积 = 边长 x 边长」可知，我们只需求出 最大边长 即可

* 定义 maxSide 表示最长边长，每次得出一个 dp，就 maxSide = max(maxSide, dp);

* 最终返回 return maxSide * maxSide;

* 参考代码

* 时间复杂度 O(height * width)

* 空间复杂度 O(height * width)

* *****************************************************************************************************************

* 链接：https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/

*/

public int maximalSquare2(char[][] matrix) {

// base condition

if (matrix == null || matrix.length < 1 || matrix[0].length < 1) return 0;

int height = matrix.length;

int width = matrix[0].length;

int maxSide = 0;

// 相当于已经预处理新增第一行、第一列均为0

int[][] dp = new int[height + 1][width + 1];

for (int row = 0; row < height; row++) {

for (int col = 0; col < width; col++) {

if (matrix[row][col] == '1') {

dp[row + 1][col + 1] = Math.min(Math.min(dp[row + 1][col], dp[row][col + 1]), dp[row][col]) + 1;

maxSide = Math.max(maxSide, dp[row + 1][col + 1]);

}

}

}

return maxSide * maxSide;

}

/**

* 优化空间

* 为了避免到边的判断处理，在最左侧加上一列 dp[i][0] = 0 ，在左上边加上一行 dp[0][j] = 0 ，这才有了官方题解中所谓的 matrix[i - 1][j - 1] == '1' 与 dp[i][j] ，其实都是指可对应上的"当前格子"

* 其实只需关注"当前格子的周边"，故可二维降一维优化

* 增加 northwest 西北角解决"左上角"的问题，感谢 @less 指出之前缺漏的 遍历每行时，还原回辅助的原值0 的问题 northwest = 0;

* *****************************************************************************************************************

* 时间复杂度 O(height * width)

* 空间复杂度 O(width)

* 链接：https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/

*/

public int maximalSquare3(char[][] matrix) {

if (matrix == null || matrix.length < 1 || matrix[0].length < 1) return 0;

int height = matrix.length;

int width = matrix[0].length;

int maxSide = 0;

int[] dp = new int[width + 1];

for (char[] chars : matrix) {

int northwest = 0; // 个人建议放在这里声明，而非循环体外

for (int col = 0; col < width; col++) {

int nextNorthwest = dp[col + 1];

if (chars[col] == '1') {

dp[col + 1] = Math.min(Math.min(dp[col], dp[col + 1]), northwest) + 1;

maxSide = Math.max(maxSide, dp[col + 1]);

} else dp[col + 1] = 0;

northwest = nextNorthwest;

}

}

return maxSide * maxSide;

}

/**

* https://leetcode.com/problems/maximal-square/discuss/61935/6-lines-Visual-Explanation-O(mn)

* class Solution:

* def maximalSquare(self, A):

* for i in range(len(A)):

* for j in range(len(A[i])):

* A[i][j] = int(A[i][j])

* if A[i][j] and i and j:

* A[i][j] = min(A[i-1][j], A[i-1][j-1], A[i][j-1]) + 1

* return len(A) and max(map(max, A)) ** 2

*/

/**

* 621. 任务调度器（Facebook 在半年内面试中常考）

* 给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

* 然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

* 你需要计算完成所有任务所需要的 最短时间 。

* *****************************************************************************************************************

* 示例 1：

* 输入：tasks = ["A","A","A","B","B","B"], n = 2

* 输出：8

* 解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B

* 在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

* *****************************************************************************************************************

* 示例 2：

* 输入：tasks = ["A","A","A","B","B","B"], n = 0

* 输出：6

* 解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0

* ["A","A","A","B","B","B"]

* ["A","B","A","B","A","B"]

* ["B","B","B","A","A","A"]

* ...

* 诸如此类

* *****************************************************************************************************************

* 示例 3：

* 输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2

* 输出：16

* 解释：一种可能的解决方案是：

* A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A

* *****************************************************************************************************************

* 方法(贪心算法)

* 容易想到的一种贪心策略为：先安排出现次数最多的任务，让这个任务两次执行的时间间隔正好为n。再在这个时间间隔内填充其他的任务。

* 例如：tasks = ["A","A","A","B","B","B"], n = 2

* 我们先安排出现次数最多的任务"A",并且让两次执行"A"的时间间隔为2。在这个时间间隔内，我们用其他任务类型去填充，又因为其他任务类型只有"B"一个，不够填充2的时间间隔，因此额外需要一个冷却时间间隔。具体安排如下图所示：

* 链接：https://leetcode-cn.com/problems/task-scheduler/solution/jian-ming-yi-dong-de-javajie-da-by-lan-s-jfl9/

* 其中，maxTimes为出现次数最多的那个任务出现的次数。maxCount为一共有多少个任务和出现最多的那个任务出现次数一样。

* 图中一共占用的方格即为完成所有任务需要的时间，即：

* (maxTimes - 1)*(n + 1) + maxCount

* 此外，如果任务种类很多，在安排时无需冷却时间，只需要在一个任务的两次出现间填充其他任务，然后从左到右从上到下依次执行即可，由于每一个任务占用一个时间单位，我们又正正好好地使用了tasks中的所有任务，而且我们只使用tasks中的任务来占用方格（没用冷却时间）。因此这种情况下，所需要的时间即为tasks的长度。

* 由于这种情况时再用上述公式计算会得到一个不正确且偏小的结果，因此，我们只需把公式计算的结果和tasks的长度取最大即为最终结果。

* 链接：https://leetcode-cn.com/problems/task-scheduler/solution/jian-ming-yi-dong-de-javajie-da-by-lan-s-jfl9/

*/

public int leastInterval(char[] tasks, int n) {

int[] buckets = new int[26];

for (int i = 0; i < tasks.length; i++) {

buckets[tasks[i] - 'A']++;

}

Arrays.sort(buckets);

int maxTimes = buckets[25];

int maxCount = 1;

for (int i = 25; i >= 1; i--) {

if (buckets[i] == buckets[i - 1])

maxCount++;

else

break;

}

int res = (maxTimes - 1) * (n + 1) + maxCount;

return Math.max(res, tasks.length);

}

/**

* (c[25] - 1) * (n + 1) + 25 - i is frame size

* when inserting chars, the frame might be "burst", then tasks.length takes precedence

* when 25 - i > n, the frame is already full at construction, the following is still valid.

* *****************************************************************************************************************

* https://leetcode.com/problems/task-scheduler/discuss/104496/concise-Java-Solution-O(N)-time-O(26)-space

*/

public int leastInterval2(char[] tasks, int n) {

int[] c = new int[26];

for (char t : tasks) {

c[t - 'A']++;

System.out.print(" "+t);

System.out.print(t - 'A'+" ");

}

Arrays.sort(c);

int i = 25;

while (i >= 0 && c[i] == c[25]) i--;

return Math.max(tasks.length, (c[25] - 1) * (n + 1) + 25 - i);

}

/**

* 647. 回文子串（Facebook、苹果、字节跳动在半年内面试中考过）

* 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

* 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

* *****************************************************************************************************************

* 示例 1：

* 输入："abc"

* 输出：3

* 解释：三个回文子串: "a", "b", "c"

* *****************************************************************************************************************

* 示例 2：

* 输入："aaa"

* 输出：6

* 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

* *****************************************************************************************************************

* 647. 回文子串 动态规划方式求解

* 解题思路

* 这道题基本和5. 最长回文子串思路是一样的，同样使用动态规划的方法。这里需要找的是最长回文子串，首先第一步，我们需要定义dp数组的含义，定义二维布尔数组dp[i][j]dp[i][j]数组表示：

* 字符串s[i⋯j]是否为回文子串，如果是，dp[i][j] = true，如果不是，dp[i][j] = false。

* 我们看如下例子：

* 链接：https://leetcode-cn.com/problems/palindromic-substrings/solution/647-hui-wen-zi-chuan-dong-tai-gui-hua-fang-shi-qiu/

* 如何我们现在已经知道了dp[i+1][j-1]了，那我们如何计算dp[i][j]呢？通过观察，我们发现：

* 如果s[i] == s[j]那么说明只要dp[i+1][j-1]是回文子串，那么是dp[i][j]也就是回文子串

* 如果s[i] != s[j]那么说明dp[i][j]必定不是回文子串。

* if(s.charAt(i) == s.charAt(j)){

* dp[i][j] = dp[i+1][j-1]

* }else{

* dp[i][j] = false;

* }

* 接下来我们需要考虑base case，这里显而易见，当只有一个字母的时候肯定是回文子串，所以初始化的dp表应该如下图所示。

* 链接：https://leetcode-cn.com/problems/palindromic-substrings/solution/647-hui-wen-zi-chuan-dong-tai-gui-hua-fang-shi-qiu/

* 遍历的方式呢我们可以按照右下角开始遍历。从右下角遍历的原因是因为(i, j) 位置的值依赖于（i+1,j-1）

* for(int i = s.length()-1; i>=0; i--){

* for(int j = i+1; j<s.length(); j++){

* if(s.charAt(i) == s.charAt(j)){

* dp[i][j] = dp[i+1][j-1]

* }

* else{

* dp[i][j] = false;

* }

* }

* }

* 这样就基本完成了这道题目。但是这样会有一种情况通过不了例如给的例子中的“cbbd”

* 链接：https://leetcode-cn.com/problems/palindromic-substrings/solution/647-hui-wen-zi-chuan-dong-tai-gui-hua-fang-shi-qiu/

* 这道题中的回文子串应该为**“bb”**但是我们的dp表中并没有计算出来，这是因为当计算dp[i][j]dp[i][j]的时候，中间已经没有dp[i+1][j-1]dp[i+1][j−1]了，这是我们在base case中没有考虑到的。

* 由于我们在dp表中表示不出来，那我们就在计算的时候单独拿出来这种情况计算，即i和j相邻的时候:

* for(int i = s.length()-1; i>=0; i--){

* for(int j = i+1; j<s.length(); j++){

* if(s.charAt(i) == s.charAt(j)){

* //i和j相邻的时候

* if(j - i == 1){

* dp[i][j] = true;

* }

* else{

* dp[i][j] = dp[i+1][j-1]

* }

* }

* else{

* dp[i][j] = false;

* }

* }

* }

* 由于最终需要输出最长的回文子串的数量，我们在遍历的时候记录一下即可。

* *****************************************************************************************************************

* 我觉得有必要解释一下为什么从右下角遍历：因为在填dp表时，(i, j) 位置的值依赖于（i+1,j-1），也就是当前位置的左下方。

* 显然如果从上往下遍历，左下方的值就完全没有初始化，当然当前位置也会是错误的。但是从右下角遍历就保证了左下方的所有值都已经计算好了。

* *****************************************************************************************************************

* “回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

*/

public int countSubstrings(String s) {

if (s == null || s.equals("")) {

return 0;

}

int n = s.length();

boolean[][] dp = new boolean[n][n];

int result = s.length();

for (int i = 0; i < n; i++) dp[i][i] = true;

for (int i = n - 1; i >= 0; i--) {

for (int j = i + 1; j < n; j++) {

if (s.charAt(i) == s.charAt(j)) {

if (j - i == 1) {

dp[i][j] = true;

} else {

dp[i][j] = dp[i + 1][j - 1];

}

} else {

dp[i][j] = false;

}

if (dp[i][j]) {

result++;

}

}

}

return result;

}

/**

* 直接int数组，默认都是0，只需要置1确定是不是回文了，，，省去了赋值false哈哈哈

* boolen数组也是默认false的 其实加上这个赋值只是为了可读性

* *****************************************************************************************************************

* “回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

* 百度百科 https://baike.baidu.com/item/%E5%9B%9E%E6%96%87%E4%B8%B2/1274921?fr=aladdin

*/

public int countSubstrings2(String s) {

int n = s.length();

int[][] dp = new int[n][n];

int nums = s.length();

for (int i = n - 1; i >= 0; i--) {

dp[i][i] = 1;

for (int j = i + 1; j < n; j++) {

if (s.charAt(i) == s.charAt(j)) {

if (j - i < 3) {

dp[i][j] = 1;

} else {

dp[i][j] = dp[i + 1][j - 1];

}

}

if (dp[i][j] == 1) {

nums++;

}

}

}

return nums;

}

/**

* https://baike.baidu.com/item/%E5%9B%9E%E6%96%87%E4%B8%B2/1274921?fr=aladdin

* *****************************************************************************************************************

* 算法编辑

* 1、初始化标志flag=true；

* 2、输入字符串str，并获取其长度len；

* 3、定义并初始化游标i=0，j=len-1，分别指向字符串开头和末尾；

* 4、比较字符str[i]和str[j],若i==j，转至7，否则往下执行5；

* 5、若str[i]和str[j]相等，则游标i加1，游标j减1后转至4，否则往下执行6；

* 6、令标志位flag=flase，结束比较，str不是回文串，算法结束。

* 7、若str[i]和str[j]相等，结束比较，flag=true,str为回文串，算法结束。

* *****************************************************************************************************************

* Java实现该算法

*/

public static boolean check(String str) {

if (null == str || "".equals(str)) {

return false;

}

int i = 0;

int j = str.length() - 1;

String[] strings = str.split("");

boolean flag = false;

for (; i <= j; i++, j--) {

if (!strings[i].equals(strings[j])) {

return false;

}

}

return true;

}

/**

* 647. Palindromic Substrings

* Given a string, your task is to count how many palindromic substrings in this string.

* The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

* *****************************************************************************************************************

* Example 1:

* Input: "abc"

* Output: 3

* Explanation: Three palindromic strings: "a", "b", "c".

* Example 2:

* Input: "aaa"

* Output: 6

* Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

* *****************************************************************************************************************

* https://leetcode.com/problems/palindromic-substrings/discuss/105689/Java-solution-8-lines-extendPalindrome

* Idea is start from each index and try to extend palindrome for both odd and even length.

* *****************************************************************************************************************

* It is not recommended to have a class level variables, like count here.

* You can return an int count in the extendPalindrome() and then do summation of both in the main loop and then return the final count of all palindromes.

* *****************************************************************************************************************

* The extendPalindrome method could be simplified as:

* private void expand(String s, int i, int j) {

* while (i >= 0 && j < s.length() && s.charAt(i--) == s.charAt(j++)) count++;

* }

* *****************************************************************************************************************

* 图解如下:

* https://leetcode.com/problems/palindromic-substrings/discuss/105688/Very-Simple-Java-Solution-with-Detail-Explanation

*/

public int countSubstrings3(String s) {

int count = 0;

for (int i = 0; i < s.length(); i++) {

count += helper(s, i, i);

count += helper(s, i, i + 1);

}

return count;

}

public int helper(String s, int left, int right) {

int count = 0;

while ((left >= 0 && right <= s.length() - 1) && (s.charAt(left) == s.charAt(right))) {

left--;

right++;

count++;

}

return count;

}

/**

* https://leetcode-cn.com/problems/palindromic-substrings/solution/shui-kan-shui-xi-huan-by-lora-h-wr3k/

* [Java] Simple Code: DP, short

* https://leetcode.com/problems/palindromic-substrings/discuss/258917/Java-Simple-Code%3A-DP-short

* 0 1 2 3 4