- 给定一个二维数组matrix，可以从任何位置出发，每一步可以走向上、下、左、右，四个方向。返回最大递增链的长度。
例子：
matrix =
5 4 3
3 1 2
2 1 3
从最中心的1出发，是可以走出1 2 3 4 5的链的，而且这是最长的递增链。所以返回长度5
/**
* 给定一个二维数组matrix，可以从任何位置出发，每一步可以走向上、下、左、右，四个方向。返回最大递增链的长度。
* 例子：
* matrix =
* 5 4 3
* 3 1 2
* 2 1 3
* 从最中心的1出发，是可以走出1 2 3 4 5的链的，而且这是最长的递增链。所以返回长度5
*/
public class MaxLenLinked {
// 暴力递归
public static int maxLenLinked(int[][] matrix){
if(matrix == null || matrix[0].length == 0){
return 0;
}
int max = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
int process = process(matrix, i, j);
max = Math.max(process,max);
}
}
return max;
}
// 从i j 位置开始返回最长递增连，
private static int process(int[][] matrix,int i,int j){
int p1 = 0;
int p2 = 0;
int p3 = 0;
int p4 = 0;
int res = 0;
// up
if(i - 1 >= 0 && matrix[i][j] < matrix[i-1][j]){
p1 = process(matrix, i - 1, j);
}
// down
if(i+1 < matrix.length && matrix[i][j] < matrix[i+1][j]){
p2 = process(matrix,i+1,j);
}
// left
if(j-1 >= 0 && matrix[i][j] < matrix[i][j-1]){
p3 = process(matrix,i,j-1);
}
//right
if(j+1 < matrix[0].length && matrix[i][j] < matrix[i][j+1]){
p4 = process(matrix,i,j+1);
}
res = Math.max(p1,Math.max(p2,Math.max(p3,p4)))+1;
return res;
}
// 记忆化搜索
public static int dp1(int[][] matrix){
if(matrix == null || matrix[0].length == 0){
return 0;
}
int max = 0;
int[][] dp = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
int process = process2(matrix, i, j,dp);
max = Math.max(process,max);
}
}
return max;
}
private static int process2(int[][] matrix,int i,int j,int[][] dp){
if(dp[i][j] != 0){
// 来到这个点不可能是0,至少都是1,自己形成一个长度为1的路径
return dp[i][j];
}
int p1 = 0;
int p2 = 0;
int p3 = 0;
int p4 = 0;
int res = 0;
// up
if(i - 1 >= 0 && matrix[i][j] < matrix[i-1][j]){
p1 = process(matrix, i - 1, j);
}
// down
if(i+1 < matrix.length && matrix[i][j] < matrix[i+1][j]){
p2 = process(matrix,i+1,j);
}
// left
if(j-1 >= 0 && matrix[i][j] < matrix[i][j-1]){
p3 = process(matrix,i,j-1);
}
//right
if(j+1 < matrix[0].length && matrix[i][j] < matrix[i][j+1]){
p4 = process(matrix,i,j+1);
}
res = Math.max(p1,Math.max(p2,Math.max(p3,p4)))+1;
dp[i][j] = res;
return dp[i][j];
}
public static void main(String[] args) {
int[][] matrix = new int[][]{
{6,5,4,3},
{2,3,1,2},
{1,2,1,3}
};
System.out.println(maxLenLinked(matrix));
System.out.println(dp1(matrix));
}
}
- 给定一个数组arr，再给定一个k值,返回累加和小于等于k，但是离k最近的子数组累加和
/**
* 给定一个数组arr，再给定一个k值,返回累加和小于等于k，但是离k最近的子数组累加和
*/
public class MaxSubArray {
public static int maxSubArray(int[] arr,int k){
if(arr == null || arr.length == 0){
return 0;
}
// 可以这样做求i位置的子数组累加和小于等于k,实质就是求在0~i上是否存在
// 一个位置j使得0~j上的前缀和大于等于 sum - k
// 如果存在,那么久找到了一个，必须以i位置结尾的累加和小于等于k的子数组，每个位置求一遍
// 答案比在其中
TreeSet<Integer> set = new TreeSet<>();
// 一开始在0位置的时候，其以前的累加和为0；
set.add(0);
int sum = 0;
int res = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if(set.ceiling(sum - k) != null){
// 存在大于等于sum - k的数，也就是存在i位置的累加和小于等于k的子数组
res = Math.max(res,sum - set.ceiling(sum-k));
set.add(sum);
}
}
return res;
}
public static void main(String[] args) {
int[] arr = new int[]{1,1,3,8,1,8};
int k = 6;
System.out.println(maxSubArray(arr,k));
}
}
- 给定一个二维数组matrix，再给定一个k值,返回累加和小于等于k，但是离k最近的子矩阵累加和
/**
* 给定一个二维数组matrix，再给定一个k值,返回累加和小于等于k，但是离k最近的子矩阵累加和
*/
public class MaxSubMatrix {
public static int maxSubMatrix(int[][] matrix,int k){
if(matrix == null || matrix[0].length == 0){
return 0;
}
// 矩阵问题可以吧他转化为一维数组为题
// 0~0,0~1,0~2,...,0~n-1,行都算出一个答案
// 1~1，1~2，...,1~n-1 ,都算出一个答案
// ...
// 并且每个矩阵可以压缩为一个一维数组操作
int max = 0;
for (int start = 0; start < matrix.length; start++) {
int[] arr = new int[matrix[0].length];
TreeSet<Integer> set = new TreeSet<>();
// 一开始在0位置的时候，其以前的累加和为0；
for (int end = start; end < matrix.length; end++) {
// 内层循环每循环一遍相当与搞定一个矩阵，一共有n^2个举证
// 压缩矩阵
int sum = 0;
set.clear();
set.add(0);
for (int i = 0; i < matrix[0].length; i++) {
arr[i] += matrix[end][i];
sum += arr[i];
if(set.ceiling(sum - k) != null){
// 存在大于等于sum - k的数，也就是存在i位置的累加和小于等于k的子数组
max = Math.max(max,sum - set.ceiling(sum-k));
set.add(sum);
}
}
}
}
return max;
}
public static void main(String[] args) {
int[][] matrix = new int[][]{
{5,4,3},
{3,2,2},
{2,1,3}
};
int k = 11;
System.out.println(maxSubMatrix(matrix,k));
}
}
- 给定一个字符类型的二维数组board，和一个字符串组成的列表words。
可以从board任何位置出发，每一步可以走向上、下、左、右，四个方向，
但是一条路径已经走过的位置，不能重复走。
返回words哪些单词可以被走出来。
例子
board = [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
words = ["oath","pea","eat","rain"]
输出：["eat","oath"]
/**
* 给定一个字符类型的二维数组board，和一个字符串组成的列表words。
* 可以从board任何位置出发，每一步可以走向上、下、左、右，四个方向，
* 但是一条路径已经走过的位置，不能重复走。
* 返回words哪些单词可以被走出来。
* 例子
* board = [
* ['o','a','a','n'],
* ['e','t','a','e'],
* ['i','h','k','r'],
* ['i','f','l','v']
* ]
* words = ["oath","pea","eat","rain"]
* 输出：["eat","oath"]
*/
public class ContainsWords {
// 给定一个二维数组，和单词列表，返回能走出的单词列表
public static List<String> containsWords(char[][] board,String[] wrods){
if(board == null || board[0].length == 0 || wrods == null || wrods.length == 0){
return null;
}
// 流程（深度优先遍历，且不能走回头路）
// 1.先用要走的单词列表构建一颗前缀树
// 2.遍历board,根据前缀树排除不符合要求的点
// 3.每遍历一个点就判断是否已经来到了结尾，是的话就收集答案，
// 构建前缀树
Node root = new Node('1');
prefixTree(root,wrods);
List<String> res = new ArrayList<>();
List<Character> path = new ArrayList<>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
// 每个位置都去走，搜集答案
if(root.nexts[board[i][j]-'a'] != null){
process(board,i,j,root.nexts[board[i][j]-'a'],res,path);
}
}
}
return res;
}
private static int process(char[][] board,int i,int j,Node cur,List<String> res,List<Character> path){
path.add(cur.c);
if(cur.end != 0){
// 来到的当前节点end 不等于0,说明这是一个单词的结尾搜集答案
res.add(String.valueOf(path));
cur.end --;
}
// up
if(i-1 >= 0 && cur.nexts[board[i-1][j]-'a'] != null){
process(board,i-1,j,cur.nexts[board[i-1][j]-'a'],res,path);
}
// down
if(i+1 < board.length && cur.nexts[board[i+1][j]-'a'] != null){
process(board,i+1,j,cur.nexts[board[i+1][j]-'a'],res,path);
}
if(j-1 >= 0 && cur.nexts[board[i][j-1]-'a'] != null){
process(board,i,j-1,cur.nexts[board[i][j-1]-'a'],res,path);
}
if(j+1 < board[0].length && cur.nexts[board[i][j+1]-'a'] != null){
process(board,i,j+1,cur.nexts[board[i][j+1]-'a'],res,path);
}
path.remove(path.size()-1);
return res.size();
// 在前缀树中是否有往下的节点
}
private static void prefixTree(Node head,String[] words){
Set<String> set = new HashSet<>();
for(String word : words){
Node cur = head;
char[] c = word.toCharArray();
if(!set.contains(word)) {
for (int i = 0; i < c.length; i++) {
// 有就复用,没有就新建
int path = c[i] - 'a';
if (cur.nexts[path] == null) {
cur.nexts[path] = new Node(c[i]);
}
cur.path++;
cur = cur.nexts[path];
}
cur.end++;
set.add(word);
}
}
}
static class Node{
char c;
int path;
int end;
// 规定只有26个小写字母
Node[] nexts;
public Node(char c){
this.nexts = new Node[26];
this.c = c;
}
}
public static void main(String[] args) {
char[][] board = {
{'o','a', 'a', 'n'},
{'e', 't', 'a', 'e'},
{'i', 'h', 'k', 'r'},
{'i', 'f', 'l', 'v'}
};
String[] words = {"oath","pea","eat","rain"};
System.out.println(containsWords(board,words));
}
}
- 给定一个二维数组 map，含义是一张地图，例如，如下矩阵:
-2 -3 3
-5 -10 1
0 30 -5
游戏的规则如下:
骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
地图中每个位置的值代表骑士要遭遇的事情。
如果是负数，说明此处有怪兽，要让骑士损失血量。
如果是非负数，代表此处有血瓶，能让骑士回血。
骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。
为了保证骑士能见到公主，初始血量至少是多少?根据map，返回至少的初始血量。
/**
* 给定一个二维数组 map，含义是一张地图，例如，如下矩阵:
* -2 -3 3
* -5 -10 1
* 0 30 -5
* 游戏的规则如下:
* 骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
* 地图中每个位置的值代表骑士要遭遇的事情。
* 如果是负数，说明此处有怪兽，要让骑士损失血量。
* 如果是非负数，代表此处有血瓶，能让骑士回血。
* 骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。
* 为了保证骑士能见到公主，初始血量至少是多少?根据map，返回至少的初始血量。
*/
public class JiuGongZhu {
public static int jiuGongZhu(int[][] matrix){
return process(matrix,0,0);
}
// 暴力递归
// 骑士来到i,j位置还没有站稳，返回至少需要多少血量从i,j位置到右下角
private static int process(int[][] matrix,int i ,int j){
// 如果已经来到了右下角
int M = matrix.length;
int N = matrix[0].length;
if(i == M-1 && j == N-1){
// 1.如果此时i,j位置是负数则骑士登上i,j位置需要(-matrix[i][j]+1),因为血量不能低于1
// 2.如果此时i,j位置是非负数，那么只需要骑士剩余至少1滴血就可以了
return matrix[i][j] < 0 ? (-matrix[i][j] + 1) : 1;
}
// 骑士还没有到右下角
// 骑士在最后一行
if(i == M-1){
// 调用子过程
int p1 = process(matrix,i,j+1);
return matrix[i][j] < 0 ? (-matrix[i][j])+p1 : matrix[i][j] > p1 ? 1 : p1-matrix[i][j];
}
if(j == N-1){
// 调用子过程
int p2 = process(matrix,i+1,j);
return matrix[i][j] < 0 ? (-matrix[i][j])+p2 : matrix[i][j] > p2 ? 1 : p2-matrix[i][j];
}
// 普遍位置
int common = 0;
int p3 = Math.min(process(matrix,i+1,j),process(matrix,i,j+1));
return matrix[i][j] < 0 ? (-matrix[i][j])+p3 : matrix[i][j] > p3 ? 1 : p3-matrix[i][j];
}
public static int dp(int[][] matrix){
int M = matrix.length;
int N = matrix[0].length;
int[][] dp = new int[M][N];
dp[M-1][N-1] = matrix[M-1][N-1] < 0 ? (-matrix[M-1][N-1] + 1) : 1;
// 最后一行
for (int j = N-2; j >= 0; j--) {
int p1 = dp[M-1][j+1];
dp[M-1][j] = matrix[M-1][j] < 0 ? (-matrix[M-1][j])+p1 : matrix[M-1][j] > p1 ? 1 : p1-matrix[M-1][j];
}
// 最后一列
for (int i = M-2;i >= 0;i--){
int p2 = dp[i+1][N-1];
dp[i][N-1] = matrix[i][N-1] < 0 ? (-matrix[i][N-1])+p2 : matrix[i][N-1] > p2 ? 1 : p2-matrix[i][N-1];
}
// 普遍位置
for (int i = M-2; i >= 0 ; i--) {
for (int j = N-2; j >= 0 ; j--) {
int p3 = Math.min(dp[i+1][j],dp[i][j+1]);
dp[i][j] = matrix[i][j] < 0 ? (-matrix[i][j])+p3 : matrix[i][j] > p3 ? 1 : p3-matrix[i][j];
}
}
return dp[0][0];
}
public static void main(String[] args) {
int[][] map = { { -2, -3, 3 }, { -5, -10, 1 }, { 10, 30, -5 } };
System.out.println(jiuGongZhu(map));
System.out.println(dp(map));
}
}
- 给定一个矩阵matrix，先从左上角开始，每一步只能往右或者往下走，走到右下角。然后从右下角出发，每一步只能往上或者往左走，再回到左上角。任何一个位置的数字，只能获得一遍。返回最大路径和。
/**
* 给定一个矩阵matrix，先从左上角开始，每一步只能往右或者往下走，走到右下角。
* 然后从右下角出发，每一步只能往上或者往左走，再回到左上角。任何一个位置的数字，
* 只能获得一遍。返回最大路径和。
*/
public class MaxPath {
public static int maxPath(int[][] matrix){
return process(matrix,0,0,0);
}
// 递归含义： A,B两个人同时出发，每次都走一步来到aR,aC,bR,bC,返回从 A B两点到右下角的最大路径和
// 由于是同步走的，则B的纵坐标可以表示为 bC = aR+aC-bR
private static int process(int[][] matrix,int aR,int aC,int bR){
int M = matrix.length;
int N = matrix[0].length;
if(aR == M -1 && aC == N-1){
// 当A,B来到右下角
// 经过同一个点只记录一次
return matrix[M-1][N-1];
}
// 没有到达终点，那么有以下几种情况
// 1.A向下，B向下
// 2.A向下，B向右
// 3.A向右，B向右
// 4.A向右，B向下
int bC = aR + aC - bR;
int aDownBDown = 0;
if(aR+1 < M && bR+1 < M){
aDownBDown = process(matrix,aR + 1,aC,bR + 1);
}
int aDownBRight = 0;
if(aR+1 < M && bC+1 < N){
aDownBRight = process(matrix,aR + 1,aC,bR);
}
int aRightBRight = 0;
if(aC + 1 < N && bC+1 < N){
aRightBRight = process(matrix,aR,aC+1,bR);
}
int aRightBDown = 0;
if(aC +1< N && bR+1 < M){
aRightBDown = process(matrix,aR,aC+1,bR + 1);
}
// 如果来到的是同一个点,或者不同位置
int curNum = aR == bR ? matrix[aR][aC] : matrix[aR][aC]+matrix[bR][bC];
return Math.max(Math.max(aDownBDown,aDownBRight),Math.max(aRightBRight,aRightBDown))+curNum;
}
// 记忆化搜搜
public static int dp(int[][] matrix){
int M = matrix.length;
int N = matrix[0].length;
int[][][] dp = new int[M][N][M];
// 最后一个位置
dp[M-1][N-1][M-1] = matrix[M-1][N-1];
//普遍位置
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < M ; k++) {
dp[i][j][k] = Integer.MIN_VALUE;
}
}
}
return process2(matrix,0,0,0,dp);
}
private static int process2(int[][] matrix,int aR,int aC,int bR,int[][][] dp){
if(dp[aR][aC][bR] != Integer.MIN_VALUE){
return dp[aR][aC][bR];
}
int M = matrix.length;
int N = matrix[0].length;
if(aR == M -1 && aC == N-1){
// 当A,B来到右下角
// 经过同一个点只记录一次
return matrix[M-1][N-1];
}
// 没有到达终点，那么有以下几种情况
// 1.A向下，B向下
// 2.A向下，B向右
// 3.A向右，B向右
// 4.A向右，B向下
int bC = aR + aC - bR;
int aDownBDown = 0;
if(aR+1 < M && bR+1 < M){
aDownBDown = process(matrix,aR + 1,aC,bR + 1);
}
int aDownBRight = 0;
if(aR+1 < M && bC+1 < N){
aDownBRight = process(matrix,aR + 1,aC,bR);
}
int aRightBRight = 0;
if(aC + 1 < N && bC+1 < N){
aRightBRight = process(matrix,aR,aC+1,bR);
}
int aRightBDown = 0;
if(aC +1< N && bR+1 < M){
aRightBDown = process(matrix,aR,aC+1,bR + 1);
}
// 如果来到的是同一个点,或者不同位置
int curNum = aR == bR ? matrix[aR][aC] : matrix[aR][aC]+matrix[bR][bC];
int max = Math.max(Math.max(aDownBDown,aDownBRight),Math.max(aRightBRight,aRightBDown))+curNum;
dp[aR][aC][bR] = max;
return max;
}
public static void main(String[] args) {
int[][] matrix = {
{1,1,1,1,1,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,0},
{0,0,0,0,1,1,1,1,1,1}
};
System.out.println(maxPath(matrix));
System.out.println(dp(matrix));
}
}
