第一题 最短路
第二题 玩游戏
第三题 数字游戏
别走错了
代码：
第一题：
标准的单源最短路径问题，用迪杰斯特拉就可以，但是比较抽象，用算法4 的写发：优先队列+松弛顶点，复杂度 VlogV + E
步骤：
1 用一个数组w保存所有顶点的权值，权值的含义是起点到当前顶点的距离，初始起始点权值0，其余顶点正无穷
2 弄一个优先队列，保存顶点，顶点权值越小越优先，然后把起始点加入队列
3 循环，每次从队列删除一个权值最小的顶点x，然后对于每条从x出发的边x-y，如果w[x] + w(x,y) < w[y]) ,则更新w[y] 和 把y加入队列，直到队列为空，结束循环
所以上述操作都是每次选择权值最小的，去更新w，所以说是松弛顶点，并且由于如果绕圈子肯定权值越绕越大，所以肯定不会绕圈子
第二题
01背包
第三题
贪心删除拐点，最后删除多余的0
import java.util.*;
public class Main {
/**
* @param
* @return bool布尔型
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
int k = in.nextInt();
for(int i=0;i<k;i++){
boolean b =false;
for(int j =0;j<s.length()-1;j++){//拐点
if(s.charAt(j) > s.charAt(j+1) ){
s = s.substring(0,j) + s.substring(j+1);
b = true;
break;
}
}
if(!b){
s = s.substring(0,s.length()-1);
}
}
int g = -1;
for(int i=0;i<s.length();i++){
if (s.charAt(i)!='0'){
g =i;
break;
}
}
s= g==-1 ? "0" : s.substring(g);
System.out.println(s);
}
}
全部评论
(12) 回帖