55分钟ak，九点钟更新代码
------------分割线-----------
第一题
题目大意:
给你一个矩阵，求最大子矩阵和
package nowcoder;
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main47 {
public static void main(String[] args) {
new Solve47().solve();
}
}
class Solve47{
public void solve(){
Scanner s=new Scanner(new BufferedInputStream(System.in));
int m=s.nextInt();
int n=s.nextInt();
int[][] martrix=new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
martrix[i][j]=s.nextInt();
}
}
int ans=Integer.MIN_VALUE;
for (int i = 0; i <m ; i++) {
int[] dp=new int[n];
for (int j = i; j < m; j++) {
for (int k = 0; k < n; k++) {
dp[k]+=martrix[j][k];
}
int[] sum=new int[n];
int min=0;
for (int k = 0; k < n; k++) {
sum[k]+=dp[k];
if (k>0)sum[k]+=sum[k-1];
ans=Math.max(ans,sum[k]-min);
min=Math.min(min,sum[k]);
}
// System.out.println(Arrays.toString(sum));
}
}
System.out.println(ans);
}
} 第二题
题目大意：
给你一个矩阵代表一个闯关方格，英雄最开始在(0,0)处，移动一次耗费1s，闯关方格上的数字代表着倒计时，每过一秒减一，当减到0时该格子无法通过，求到右下角的最短时间
package nowcoder;
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main48 {
public static void main(String[] args) {
new Solve48().solve();
}
}
class Solve48{
int row,col;
int[] dx={-1,1,0,0};
int[] dy={0,0,1,-1};
private class Node{
int x;
int y;
int hop;
public Node(int x, int y, int hop) {
this.x = x;
this.y = y;
this.hop = hop;
}
}
public void solve(){
Scanner s=new Scanner(new BufferedInputStream(System.in));
row=s.nextInt();
col=s.nextInt();
int[][] grid=new int[row][col];
for (int i = 0; i <row ; i++) {
for (int j = 0; j < col; j++) {
grid[i][j]=s.nextInt();
}
}
System.out.println(getAns(grid));
}
private int getAns(int[][] grid){
if (grid[0][0]<=0){
return -1;
}
int[][] minTime=new int[row][col];
for (int i = 0; i < row; i++) {
Arrays.fill(minTime[i],Integer.MAX_VALUE);
}
Queue<Node> queue=new LinkedList<>();
queue.add(new Node(0,0,0));
while (!queue.isEmpty()){
Node node=queue.poll();
int x=node.x;
int y=node.y;
int hop=node.hop;
// System.out.println(x+" "+y+" "+hop);
if (minTime[x][y]<=hop||grid[x][y]<hop)continue;
minTime[x][y]=hop;
if (x==row-1&&y==col-1)return hop;
for (int i = 0; i < dx.length; i++) {
int nextX=dx[i]+x;
int nextY=dy[i]+y;
if (!inGrid(nextX,nextY))continue;
queue.add(new Node(nextX,nextY,hop+1));
}
}
return -1;
}
private boolean inGrid(int x,int y){
return x>=0&&x<row&&y>=0&&y<col;
}
} 第三题
题目大意：给你一系列任务的完成时间及其前置依赖，任务可以并行，求完成所有任务的最短时间
输入：
第一行一个数n代表有n个任务，接下来n行代表每个任务的信息
当没有前置依赖的时候，这一行为-1 t，t代表完成时间
当有前置依赖的时候，前置依赖间用逗号隔开，1,2 t，t代表完成时间
Java split处理字符串yyds
拓扑排序加dp，其中dp[i]代表完成第i个任务需要的时间
package nowcoder;
import java.io.BufferedInputStream;
import java.util.*;
public class Main49 {
public static void main(String[] args) {
new Solve49().solve();
}
}
class Solve49{
public void solve(){
Scanner s=new Scanner(new BufferedInputStream(System.in));
int n=s.nextInt();
int[] times=new int[n];
s.nextLine();
List<List<Integer>> graph=new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < n; i++) {
String str=s.nextLine();
String[] strs=str.split(",");
for (int j = 0; j <strs.length-1 ; j++) {
int a=Integer.parseInt(strs[j]);
graph.get(a).add(i);
}
String[] curr=strs[strs.length-1].split(" ");
if (!curr[0].equals("-1")){
int a=Integer.parseInt(curr[0]);
graph.get(a).add(i);
}
int t=Integer.parseInt(curr[1]);
times[i]=t;
}
System.out.println(getAns(times,graph,n));
}
private int getAns(int[] times,List<List<Integer>> graph,int n){
int[] in=new int[n];
for(List<Integer> list:graph){
for(int i:list)in[i]++;
}
Queue<Integer> queue=new LinkedList<>();
int[] dp=new int[n];
Arrays.fill(dp,0);
int cnt=0;
for (int i = 0; i < n; i++) {
if (in[i]==0){
dp[i]=times[i];
queue.add(i);
}
}
while (!queue.isEmpty()){
int curr=queue.poll();
cnt++;
for(int i:graph.get(curr)){
in[i]--;
dp[i]=Math.max(dp[i],dp[curr]+times[i]);
if (in[i]==0)queue.add(i);
}
}
if (cnt!=n)return -1;
int ans=0;
for (int i = 0; i <dp.length ; i++) {
ans=Math.max(ans,dp[i]);
}
return ans;
}
} 
全部评论
(43) 回帖